前言
LRU(least recently used)是一種緩存置換算法。即在緩存有限的情況下，如果有新的數(shù)據(jù)需要加載進(jìn)緩存，則需要將最不可能被繼續(xù)訪問的緩存剔除掉。
基于 HashMap 和 雙向鏈表實(shí)現(xiàn) LRU
- 整體的設(shè)計(jì)思路是，可以使用 HashMap 存儲(chǔ) key，這樣可以做到 save 和 get key的時(shí)間都是 O(1)，而 HashMap 的 Value 記錄需要緩存數(shù)據(jù)在 LRU 存儲(chǔ)中的槽。
image
- 而 LRU 存儲(chǔ)是基于雙向鏈表實(shí)現(xiàn)的，下面的圖演示了它的原理。其中 h 代表雙向鏈表的表頭，t 代表尾部。如果存儲(chǔ)滿了，可以通過 O(1) 的時(shí)間淘汰掉雙向鏈表的尾部，并更新隊(duì)頭。
image
下面總結(jié)一下核心操作的步驟:
- save(key)，首先通過 hash 算法，在key space 找到 key，并且嘗試把數(shù)據(jù)存儲(chǔ)到LRU空間，如果LRU空間足夠，則不需要淘汰舊的內(nèi)容；如果緩存空間不足，會(huì)淘汰掉 tail 指向的內(nèi)容，并更新隊(duì)頭，存儲(chǔ)后返回使用槽下標(biāo)，更新key space 的value。
- get(key)，通過 hash 找到 key，然后通過 value 找到 LRU空間對(duì)應(yīng)的槽，更新LRU指向關(guān)系。
- 完整基于 Java 的代碼參考如下
class DLinkedNode {
int 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(int 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(int 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中的LRU算法
首先Redis并沒有使用雙向鏈表實(shí)現(xiàn)一個(gè)LRU算法。
Redis整體上是一個(gè)大的dict,key是一個(gè)string,而value都會(huì)保存為一個(gè)robj（redisObject）。
在Redis的dict中每次按key獲取一個(gè)值的時(shí)候，都會(huì)調(diào)用lookupKey函數(shù),如果配置使用了LRU模式,該函數(shù)會(huì)更新value中的lru字段為當(dāng)前秒級(jí)別的時(shí)間戳。
Redis3.0的LRU實(shí)現(xiàn)算法：
1.第一次隨機(jī)選取的key都會(huì)放入一個(gè)pool中(pool的大小為16),pool中的key是按lru時(shí)間戳大小順序排列的。
2.接下來每次隨機(jī)選取的key的lru值必須小于pool中最小的lru才會(huì)繼續(xù)放入，直到將pool放滿。
3.放滿之后，每次如果有新的key需要放入，需要將pool中l(wèi)ru最大的一個(gè)key取出。
4.需要淘汰的時(shí)候，直接從pool中選取一個(gè)lru最小的值然后將其淘汰。
