溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
這篇文章給大家介紹LRU原理及實現(xiàn)是怎樣的，內(nèi)容非常詳細(xì)，感興趣的小伙伴們可以參考借鑒，希望對大家能有所幫助。
硬盤容量大訪問速度慢，內(nèi)存空間小訪問速度塊，內(nèi)存空間如何實現(xiàn)淘汰機(jī)制呢？LFU、LRU、ARC、FIFO、MRU
最不經(jīng)常使用算法（LFU）：在一般標(biāo)準(zhǔn)的操作系統(tǒng)教材里，會用下面的方式來演示 LRU 原理，假設(shè)內(nèi)存只能容納3個頁大小，按照 7 0 1 2 0 3 0 4 的次序訪問頁。假設(shè)內(nèi)存按照棧的方式來描述訪問時間，在上面的，是最近訪問的，在下面的是，最遠(yuǎn)時間訪問的，LRU就是這樣工作的。
但是如果讓我們自己設(shè)計一個基于 LRU 的緩存，這樣設(shè)計可能問題很多，這段內(nèi)存按照訪問時間進(jìn)行了排序，會有大量的內(nèi)存拷貝操作，所以性能肯定是不能接受的。
那么如何設(shè)計一個LRU緩存，使得放入和移除都是 O(1) 的，我們需要把訪問次序維護(hù)起來，但是不能通過內(nèi)存中的真實排序來反應(yīng)，有一種方案就是使用雙向鏈表。
整體的設(shè)計思路是，可以使用 HashMap 存儲 key，這樣可以做到 save 和 get key的時間都是 O(1)，而 HashMap 的 Value 指向雙向鏈表實現(xiàn)的 LRU 的 Node 節(jié)點，如圖所示。
LRU 存儲是基于雙向鏈表實現(xiàn)的，下面的圖演示了它的原理。其中 head 代表雙向鏈表的表頭，tail 代表尾部。首先預(yù)先設(shè)置 LRU 的容量，如果存儲滿了，可以通過 O(1) 的時間淘汰掉雙向鏈表的尾部，每次新增和訪問數(shù)據(jù)，都可以通過 O(1)的效率把新的節(jié)點增加到對頭，或者把已經(jīng)存在的節(jié)點移動到隊頭。
save("key1", 7)
save("key2", 0)
save("key3", 1)
save("key4", 2)
get("key2")
save("key5", 3)
get("key2")
save("key6", 4)下面展示了，預(yù)設(shè)大小是 3 的，LRU存儲的在存儲和訪問過程中的變化。為了簡化圖復(fù)雜度，圖中沒有展示 HashMap部分的變化，僅僅演示了上圖 LRU 雙向鏈表的變化。我們對這個LRU緩存的操作序列如下：相應(yīng)的 LRU 雙向鏈表部分變化如下：
s = save, g = get
總結(jié)一下核心操作的步驟:
save(key, value)，首先在 HashMap 找到 Key 對應(yīng)的節(jié)點，如果節(jié)點存在，更新節(jié)點的值，并把這個節(jié)點移動隊頭。如果不存在，需要構(gòu)造新的節(jié)點，并且嘗試把節(jié)點塞到隊頭，如果LRU空間不足，則通過 tail 淘汰掉隊尾的節(jié)點，同時在 HashMap 中移除 Key。
get(key)，通過 HashMap 找到 LRU 鏈表節(jié)點，因為根據(jù)LRU 原理，這個節(jié)點是最新訪問的，所以要把節(jié)點插入到隊頭，然后返回緩存的值。
完整基于 Java 的代碼參考如下
class DLinkedNode {
String key;
int value;
DLinkedNode pre;
DLinkedNode post;
}LRU Cache
public class LRUCache {
private Hashtable<Integer, DLinkedNode>
cache = new Hashtable<Integer, DLinkedNode>();
private int count;
private int capacity;
private DLinkedNode head, tail;
public LRUCache(int capacity) {
this.count = 0;
this.capacity = capacity;
head = new DLinkedNode();
head.pre = null;
tail = new DLinkedNode();
tail.post = null;
head.post = tail;
tail.pre = head;
}
public int get(String key) {
DLinkedNode node = cache.get(key);
if(node == null){
return -1; // should raise exception here.
}
// move the accessed node to the head;
this.moveToHead(node);
return node.value;
}
public void set(String key, int value) {
DLinkedNode node = cache.get(key);
if(node == null){
DLinkedNode newNode = new DLinkedNode();
newNode.key = key;
newNode.value = value;
this.cache.put(key, newNode);
this.addNode(newNode);
++count;
if(count > capacity){
// pop the tail
DLinkedNode tail = this.popTail();
this.cache.remove(tail.key);
--count;
}
}else{
// update the value.
node.value = value;
this.moveToHead(node);
}
}
/**
* Always add the new node right after head;
*/
private void addNode(DLinkedNode node){
node.pre = head;
node.post = head.post;
head.post.pre = node;
head.post = node;
}
/**
* Remove an existing node from the linked list.
*/
private void removeNode(DLinkedNode node){
DLinkedNode pre = node.pre;
DLinkedNode post = node.post;
pre.post = post;
post.pre = pre;
}
/**
* Move certain node in between to the head.
*/
private void moveToHead(DLinkedNode node){
this.removeNode(node);
this.addNode(node);
}
// pop the current tail.
private DLinkedNode popTail(){
DLinkedNode res = tail.pre;
this.removeNode(res);
return res;
}
}那么問題的后半部分，是 Redis 如何實現(xiàn)，這個問題這么問肯定是有坑的，那就是redis肯定不是這樣實現(xiàn)的。
如果按照HashMap和雙向鏈表實現(xiàn)，需要額外的存儲存放 next 和 prev 指針，犧牲比較大的存儲空間，顯然是不劃算的。所以Redis采用了一個近似的做法，就是隨機(jī)取出若干個key，然后按照訪問時間排序后，淘汰掉最不經(jīng)常使用的，具體分析如下：
為了支持LRU，Redis 2.8.19中使用了一個全局的LRU時鐘，server.lruclock，定義如下，
#define REDIS_LRU_BITS 24 unsigned lruclock:REDIS_LRU_BITS; /* Clock for LRU eviction */
默認(rèn)的LRU時鐘的分辨率是1秒，可以通過改變REDIS_LRU_CLOCK_RESOLUTION宏的值來改變，Redis會在serverCron()中調(diào)用updateLRUClock定期的更新LRU時鐘，更新的頻率和hz參數(shù)有關(guān)，默認(rèn)為100ms一次，如下，
#define REDIS_LRU_CLOCK_MAX ((1<<REDIS_LRU_BITS)-1) /* Max value of obj->lru */
#define REDIS_LRU_CLOCK_RESOLUTION 1 /* LRU clock resolution in seconds */
void updateLRUClock(void) {
server.lruclock = (server.unixtime / REDIS_LRU_CLOCK_RESOLUTION) &
REDIS_LRU_CLOCK_MAX;
}server.unixtime是系統(tǒng)當(dāng)前的unix時間戳，當(dāng) lruclock 的值超出REDIS_LRU_CLOCK_MAX時，會從頭開始計算，所以在計算一個key的最長沒有訪問時間時，可能key本身保存的lru訪問時間會比當(dāng)前的lrulock還要大，這個時候需要計算額外時間，如下，
/* Given an object returns the min number of seconds the object was never
* requested, using an approximated LRU algorithm. */
unsigned long estimateObjectIdleTime(robj *o) {
if (server.lruclock >= o->lru) {
return (server.lruclock - o->lru) * REDIS_LRU_CLOCK_RESOLUTION;
} else {
return ((REDIS_LRU_CLOCK_MAX - o->lru) + server.lruclock) *
REDIS_LRU_CLOCK_RESOLUTION;
}
}Redis支持和LRU相關(guān)淘汰策略包括，
volatile-lru 設(shè)置了過期時間的key參與近似的lru淘汰策略
allkeys-lru 所有的key均參與近似的lru淘汰策略
當(dāng)進(jìn)行LRU淘汰時，Redis按如下方式進(jìn)行的，
......
/* volatile-lru and allkeys-lru policy */
else if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)
{
for (k = 0; k < server.maxmemory_samples; k++) {
sds thiskey;
long thisval;
robj *o;
de = dictGetRandomKey(dict);
thiskey = dictGetKey(de);
/* When policy is volatile-lru we need an additional lookup
* to locate the real key, as dict is set to db->expires. */
if (server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)
de = dictFind(db->dict, thiskey);
o = dictGetVal(de);
thisval = estimateObjectIdleTime(o);
/* Higher idle time is better candidate for deletion */
if (bestkey == NULL || thisval > bestval) {
bestkey = thiskey;
bestval = thisval;
}
}
}
......Redis會基于server.maxmemory_samples配置選取固定數(shù)目的key，然后比較它們的lru訪問時間，然后淘汰最近最久沒有訪問的key，maxmemory_samples的值越大，Redis的近似LRU算法就越接近于嚴(yán)格LRU算法，但是相應(yīng)消耗也變高，對性能有一定影響，樣本值默認(rèn)為5。
Redis的過期策略，是有定期刪除+惰性刪除兩種。
定期好理解，默認(rèn)100s就隨機(jī)抽一些設(shè)置了過期時間的key，去檢查是否過期，過期了就刪了。
為啥不掃描全部設(shè)置了過期時間的key呢？
假如Redis里面所有的key都有過期時間，都掃描一遍？那太恐怖了，而且我們線上基本上也都是會設(shè)置一定的過期時間的。全掃描跟你去查數(shù)據(jù)庫不帶where條件不走索引全表掃描一樣，100s一次，Redis累都累死了。
如果一直沒隨機(jī)到很多key，里面不就存在大量的無效key了？
好問題，惰性刪除，見名知意，惰性嘛，我不主動刪，我懶，我等你來查詢了我看看你過期沒，過期就刪了還不給你返回，沒過期該怎么樣就怎么樣。
最后就是如果的如果，定期沒刪，我也沒查詢，那可咋整？
內(nèi)存淘汰機(jī)制！
官網(wǎng)上給到的內(nèi)存淘汰機(jī)制是以下幾個：
noeviction:返回錯誤當(dāng)內(nèi)存限制達(dá)到并且客戶端嘗試執(zhí)行會讓更多內(nèi)存被使用的命令（大部分的寫入指令，但DEL和幾個例外）
allkeys-lru: 嘗試回收最少使用的鍵（LRU），使得新添加的數(shù)據(jù)有空間存放。
volatile-lru: 嘗試回收最少使用的鍵（LRU），但僅限于在過期集合的鍵,使得新添加的數(shù)據(jù)有空間存放。
allkeys-random: 回收隨機(jī)的鍵使得新添加的數(shù)據(jù)有空間存放。
volatile-random: 回收隨機(jī)的鍵使得新添加的數(shù)據(jù)有空間存放，但僅限于在過期集合的鍵。
volatile-ttl: 回收在過期集合的鍵，并且優(yōu)先回收存活時間（TTL）較短的鍵,使得新添加的數(shù)據(jù)有空間存放。
如果沒有鍵滿足回收的前提條件的話，策略volatile-lru, volatile-random以及volatile-ttl就和noeviction 差不多了。
Redis為什么不使用真實的LRU實現(xiàn)是因為這需要太多的內(nèi)存。不過近似的LRU算法對于應(yīng)用而言應(yīng)該是等價的。使用真實的LRU算法與近似的算法可以通過下面的圖像對比。
其實在大家熟悉的LinkedHashMap中也實現(xiàn)了LRU算法的，
在LinkedHashMap里。我們只需要擴(kuò)展下即可，代碼示例如下：
/**
* Constructs an empty <tt>LinkedHashMap</tt> instance with the
* specified initial capacity, load factor and ordering mode.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @param accessOrder the ordering mode - <tt>true</tt> for
* access-order, <tt>false</tt> for insertion-order
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
//方法為protected ，擺明了是想被繼承、重寫
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}使用accessOrder來標(biāo)識是使用訪問順序，還是插入順序。默認(rèn)為插入順序。當(dāng)accessOrder為訪問順序、容量固定時，即為LRU
舉例如下：
當(dāng)容量超過100時，開始執(zhí)行LRU策略：將最近最少未使用的對象 evict 掉。
Map<Long, String> LRUCollection = Collections.synchronizedMap(new LinkedHashMap<Long, String>(100, .75F, true)
{
@Override
protected boolean removeEldestEntry(Map.Entry<Long, String> eldest)
{
return size() > 100;
}
});真實面試中會讓你寫LUR算法，你可別搞原始的那個，那真TM多，寫不完的，你要么懟上面這個，要么懟下面這個，找一個數(shù)據(jù)結(jié)構(gòu)實現(xiàn)下Java版本的LRU還是比較容易的，知道啥原理就好了。
class LRULinkedHashMap<K,V> extends LinkedHashMap<K,V> {
/**
*
*/
private static final long serialVersionUID = 1882839504956564761L;
private int capacity;
public LRULinkedHashMap(int capacity) {
super(capacity,0.75f,true);
this.capacity = capacity;
}
@Override
public boolean removeEldestEntry(Map.Entry<K,V> eldest) {
System.out.println("即將根據(jù)LRU算法，刪除最近最少使用元素：key= "+eldest.getKey()+" value= "+eldest.getValue()+" .");
//此行代碼是關(guān)鍵，一旦容量超出限制，即按照LRU進(jìn)行刪除
return size()>capacity;
}
}
public class Test {
public static void main(String[] args) {
testLinkedHashMap();
testLRULinkedHashMap();
}
public static void testLinkedHashMap() {
//容量固定，accessOrder=true
Map<Integer, Integer> map = new LinkedHashMap<Integer, Integer>(5, 0.75f, true);
map.put(1, 1);
map.put(2, 2);
map.put(3, 3);
map.put(4, 4);
map.put(5, 5);
//此時輸出1,2,3,4,5
for(Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator(); it.hasNext();) {
System.out.println(it.next().getValue());
}
map.put(4, 4);
map.put(6, 6);
//此時輸出1,2,3,5,4,6（自動擴(kuò)容）
for(Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator(); it.hasNext();) {
System.out.println(it.next().getValue());
}
}
public static void testLRULinkedHashMap() {
//容量固定，accessOrder=true
Map<Integer, Integer> map = new LRULinkedHashMap<Integer, Integer>(5);
map.put(1, 1);
map.put(2, 2);
map.put(3, 3);
map.put(4, 4);
map.put(5, 5);
//此時輸出1,2,3,4,5
for(Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator(); it.hasNext();) {
System.out.println(it.next().getValue());
}
map.put(4, 4);
map.put(6, 6);
//此時輸出2,3,5,4,6（容量鎖定，進(jìn)行刪除）
for(Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator(); it.hasNext();) {
System.out.println(it.next().getValue());
}
}
}關(guān)于LRU原理及實現(xiàn)是怎樣的就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，可以學(xué)到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進(jìn)行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號
手機(jī)網(wǎng)站二維碼