LRU算法介紹
LRU算法全稱Least Recently Used长赞，也就是檢查最近最少使用的數(shù)據(jù)的算法渠啤。這個算法通常使用在內(nèi)存淘汰策略中跛锌，用于將不常用的數(shù)據(jù)轉(zhuǎn)移出內(nèi)存贱呐，將空間騰給最近更常用的“熱點(diǎn)數(shù)據(jù)”丧诺。
初識這個算法忘了是在操作系統(tǒng)課還是計(jì)算機(jī)組成原理課上，其在Redis奄薇、Guava等工具中也有非常廣泛的應(yīng)用驳阎，甚至是最核心的思想之一。如果今后需要自己設(shè)計(jì)系統(tǒng)馁蒂，即使不自己實(shí)現(xiàn)這個算法呵晚，LRU的思想也仍然是很重要的。
算法很簡單远搪，只需要將所有數(shù)據(jù)按使用時間排序劣纲，在需要篩選出LRU數(shù)據(jù)時，取排名靠后的即可谁鳍。
算法實(shí)現(xiàn)
Redis中的LRU
Redis中的數(shù)據(jù)量通常很龐大，如果每次對全量數(shù)據(jù)進(jìn)行排序劫瞳，勢必將對服務(wù)吞吐量造成影響倘潜。因此，Redis在LRU淘汰部分key時志于，使用的是采樣并計(jì)算近似LRU的涮因，因此淘汰的是局部LRU數(shù)據(jù)。
Redis內(nèi)存淘汰策略
maxmemory-policy配置可選參數(shù)：
-
noeviction：不淘汰伺绽，內(nèi)存超限后寫命令會返回錯誤(如OOM, del命令除外) -
allkeys-lru：所有key的LRU機(jī)制 在所有key中按照最近最少使用LRU原則剔除key养泡，釋放空間 -
volatile-lru：易失key的LRU 僅以設(shè)置過期時間key范圍內(nèi)的LRU(如均為設(shè)置過期時間，則不會淘汰) -
allkeys-random：所有key隨機(jī)淘汰 一視同仁奈应，隨機(jī) -
volatile-random：易失Key的隨機(jī) 僅設(shè)置過期時間key范圍內(nèi)的隨機(jī) -
volatile-ttl：易失key的TTL淘汰 按最小TTL的key優(yōu)先淘汰
Redis LRU的效果
左上-理論LRU效果澜掩；右上-Redis3.0中的近似LRU(采樣值10)；左下-Redis2.8中的近似LRU(采樣值5)杖挣；右下-Redis3.0中的近似LRU(采樣值5)
淺灰色-被淘汰肩榕；灰色-未被淘汰；綠色-新寫入
補(bǔ)充說明：
- 達(dá)到設(shè)定的內(nèi)存占用閾值時才會進(jìn)行內(nèi)存淘汰
-
maxmemory-samples配置表示采樣值惩妇，每次刪除時采集的樣本數(shù)——采樣值10株汉，表示從設(shè)置中定義的key中取10個key進(jìn)行LRU計(jì)算并刪除LRU的那個key - Redis3.0中的算法建立了一個“候選池”，使得算法的效率和準(zhǔn)確率都比2.8有提高歌殃，因?yàn)榉秶s小了
結(jié)論：
- Redis3.0通過增加候選池提高了LRU準(zhǔn)確性乔妈，效果比2.8好
- 采樣值越高越結(jié)果越接近理論LRU（但是采樣值越高效率低）
- 差不多采樣率5就已經(jīng)足夠準(zhǔn)確了，當(dāng)然使用10已經(jīng)基本接近理論LRU結(jié)果氓皱，但是損失效率
Java中的LRU實(shí)現(xiàn)思路
根據(jù)LRU算法路召，在Java中實(shí)現(xiàn)需要這些條件：
- 底層數(shù)據(jù)使用雙向鏈表贮懈，方便在鏈表的任意位置進(jìn)行刪除，在鏈表尾進(jìn)行添加
這一點(diǎn)用單鏈表比較費(fèi)勁优训，當(dāng)然用數(shù)組等結(jié)構(gòu)也都很費(fèi)勁
當(dāng)然雙向鏈表在查找時也麻煩朵你，但下述可以結(jié)合HashMap使用 - 需要將鏈表按照訪問（使用）順序排序
- 數(shù)據(jù)量超過一定閾值后，需要刪除Least Recently Used數(shù)據(jù)
Java中一個簡單的LRUCache實(shí)現(xiàn)
對于上述的實(shí)現(xiàn)思路揣非，java.util.LinkedHashMap已經(jīng)實(shí)現(xiàn)了其中的99%抡医，因此直接基于LinkedHashMap實(shí)現(xiàn)LRUCache非常簡單。
LinkedHashMap為LRUCache鋪墊了什么
- 構(gòu)造方法提供了
accessOrder選項(xiàng)早敬，開啟后會get方法會有額外操作保證鏈表順序按訪問順序逆序排列 - 底層結(jié)構(gòu)使用雙向鏈表忌傻，查找可以使用HashMap的特點(diǎn)
- 覆蓋了父類HashMap的
newNode方法和newTreeNode方法，這兩個方法在HashMap中只是創(chuàng)建Node用的搞监，而在LinkedHashMap中不但創(chuàng)建Node水孩，還將Node放在鏈表末尾 - 父類HashMap提供了3個void的Hook方法，方法沒做任何事：
-
afterNodeRemoval父類在remove一個集合中存在的元素后調(diào)用 -
afterNodeInsertion父類在put琐驴、compute俘种、merge后調(diào)用 -
afterNodeAccess父類在replace、compute绝淡、merge等替換值后會調(diào)用宙刘，LinkedHashMap在get中開啟accessOrder時調(diào)用，究其根本是在對數(shù)據(jù)有操作時會調(diào)用
-
- LinkedHashMap本質(zhì)上還是復(fù)用HashMap的絕大部分功能牢酵，包括底層的Node<K, V>[]悬包，因此能支持原本HashMap的功能
- 但是LinkedHashMap實(shí)現(xiàn)了父類HashMap的3個Hook方法：
-
afterNodeRemoval實(shí)現(xiàn)鏈表的刪除操作 -
afterNodeInsertion并沒有實(shí)現(xiàn)鏈表的插入操作，但新添加了一個Hook方法boolean removeEldestEntry馍乙，當(dāng)這個Hook方法返回true時布近，刪除鏈表頭的節(jié)點(diǎn) -
afterNodeAccess如前所述，開啟accessOrder后會將被操作的節(jié)點(diǎn)放在鏈表末尾丝格，保證鏈表順序按訪問順序逆序排列
-
- 上一條3個方法是用來構(gòu)建雙向鏈表的撑瞧，LinkedHashMap還覆蓋了父類的3個方法：
-
newNode在創(chuàng)建一個Node的同時，將Node添加到鏈表末尾 -
newTreeNode創(chuàng)建TreeNode的同時铁追，將Node添加到鏈表末尾 -
get完成get功能的同時季蚂，如果accessOrder開啟，會調(diào)用afterNodeAccess將Node移動到鏈表末尾
覆蓋newNode和newTreeNode方法后琅束，在put方法中調(diào)用的newNode和newTreeNode方法也就連帶實(shí)現(xiàn)了鏈表的插入操作
-
綜上扭屁，我們可以了解到LinkedHashMap為什么能夠輕松實(shí)現(xiàn)LRUCache
- 繼承父類HashMap，擁有HashMap的功能涩禀，因此在查找一個節(jié)點(diǎn)時時間復(fù)雜度為O(1)料滥，再加上鏈表是雙向，做鏈表任意節(jié)點(diǎn)的刪除工作就非常簡單
- 通過HashMap提供的3個Hook方法并覆蓋了2個創(chuàng)建Node的方法艾船，實(shí)現(xiàn)了自身鏈表的添加葵腹、刪除工作高每，保證在不影響原本Array功能的前提下，正確完成自身的鏈表構(gòu)建践宴；這個過程實(shí)際上均是通過Hook方式增強(qiáng)原有功能的鲸匿，因?yàn)樵镜腍ashMap中創(chuàng)建節(jié)點(diǎn)其實(shí)也是使用的Hook方法
- 提供屬性
accessOrder并實(shí)現(xiàn)了afterNodeAccess方法，因此能夠根據(jù)訪問或操作順序?qū)⒆罱褂没蜃罱迦氲臄?shù)據(jù)放在鏈表尾阻肩，越久沒被使用的數(shù)據(jù)就越靠近鏈表頭带欢，實(shí)現(xiàn)了整個鏈表按照LRU的要求排序 - 提供了一個Hook方法
boolean removeEldestEntry，這個方法返回true時將會刪除表頭節(jié)點(diǎn)烤惊，即LRU中應(yīng)當(dāng)淘汰的節(jié)點(diǎn)乔煞，但是這個方法在LinkedHashMap中的實(shí)現(xiàn)永遠(yuǎn)返回false
到這為止，實(shí)現(xiàn)一個LRUCache就很簡單了：實(shí)現(xiàn)這個removeEldestEntryHook方法柒室，給LinkedHashMap設(shè)置一個閾值渡贾，那么超過這個閾值時就會進(jìn)行LRU淘汰。
網(wǎng)上隨處可見的Java代碼實(shí)現(xiàn)
// 繼承LinkedHashMap
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
private final int MAX_CACHE_SIZE;
public LRUCache(int cacheSize) {
// 使用構(gòu)造方法 public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)
// initialCapacity雄右、loadFactor都不重要
// accessOrder要設(shè)置為true空骚，按訪問排序
super((int) Math.ceil(cacheSize / 0.75) + 1, 0.75f, true);
MAX_CACHE_SIZE = cacheSize;
}
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
// 超過閾值時返回true，進(jìn)行LRU淘汰
return size() > MAX_CACHE_SIZE;
}
}
看似幾行代碼解決的事兒不脯，其實(shí)只是冰山一角而已府怯。
參考資料
Using Redis as an LRU cache – Redis
本文搬自我的博客，歡迎參觀防楷！
