這篇文章給大家介紹LRU原理及實(shí)現(xiàn)是怎樣的，內(nèi)容非常詳細(xì)，感興趣的小伙伴們可以參考借鑒，希望對(duì)大家能有所幫助。
創(chuàng)新互聯(lián)建站成都企業(yè)網(wǎng)站建設(shè)服務(wù)，提供成都網(wǎng)站建設(shè)、網(wǎng)站制作網(wǎng)站開發(fā),網(wǎng)站定制,建網(wǎng)站,網(wǎng)站搭建,網(wǎng)站設(shè)計(jì),成都響應(yīng)式網(wǎng)站建設(shè),網(wǎng)頁設(shè)計(jì)師打造企業(yè)風(fēng)格網(wǎng)站,提供周到的售前咨詢和貼心的售后服務(wù)。歡迎咨詢做網(wǎng)站需要多少錢:18980820575
硬盤容量大訪問速度慢，內(nèi)存空間小訪問速度塊，內(nèi)存空間如何實(shí)現(xiàn)淘汰機(jī)制呢？LFU、LRU、ARC、FIFO、MRU
最不經(jīng)常使用算法（LFU）：在一般標(biāo)準(zhǔn)的操作系統(tǒng)教材里，會(huì)用下面的方式來演示 LRU 原理，假設(shè)內(nèi)存只能容納3個(gè)頁大小，按照 7 0 1 2 0 3 0 4 的次序訪問頁。假設(shè)內(nèi)存按照棧的方式來描述訪問時(shí)間，在上面的，是最近訪問的，在下面的是，最遠(yuǎn)時(shí)間訪問的，LRU就是這樣工作的。
但是如果讓我們自己設(shè)計(jì)一個(gè)基于 LRU 的緩存，這樣設(shè)計(jì)可能問題很多，這段內(nèi)存按照訪問時(shí)間進(jìn)行了排序，會(huì)有大量的內(nèi)存拷貝操作，所以性能肯定是不能接受的。
那么如何設(shè)計(jì)一個(gè)LRU緩存，使得放入和移除都是 O(1) 的，我們需要把訪問次序維護(hù)起來，但是不能通過內(nèi)存中的真實(shí)排序來反應(yīng)，有一種方案就是使用雙向鏈表。
基于 HashMap 和 雙向鏈表實(shí)現(xiàn) LRU 的
整體的設(shè)計(jì)思路是，可以使用 HashMap 存儲(chǔ) key，這樣可以做到 save 和 get key的時(shí)間都是 O(1)，而 HashMap 的 Value 指向雙向鏈表實(shí)現(xiàn)的 LRU 的 Node 節(jié)點(diǎn)，如圖所示。
LRU 存儲(chǔ)是基于雙向鏈表實(shí)現(xiàn)的，下面的圖演示了它的原理。其中 head 代表雙向鏈表的表頭，tail 代表尾部。首先預(yù)先設(shè)置 LRU 的容量，如果存儲(chǔ)滿了，可以通過 O(1) 的時(shí)間淘汰掉雙向鏈表的尾部，每次新增和訪問數(shù)據(jù)，都可以通過 O(1)的效率把新的節(jié)點(diǎn)增加到對(duì)頭，或者把已經(jīng)存在的節(jié)點(diǎn)移動(dòng)到隊(duì)頭。
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存儲(chǔ)的在存儲(chǔ)和訪問過程中的變化。為了簡(jiǎn)化圖復(fù)雜度，圖中沒有展示 HashMap部分的變化，僅僅演示了上圖 LRU 雙向鏈表的變化。我們對(duì)這個(gè)LRU緩存的操作序列如下：相應(yīng)的 LRU 雙向鏈表部分變化如下：
s = save, g = get
總結(jié)一下核心操作的步驟:
save(key, value)，首先在 HashMap 找到 Key 對(duì)應(yīng)的節(jié)點(diǎn)，如果節(jié)點(diǎn)存在，更新節(jié)點(diǎn)的值，并把這個(gè)節(jié)點(diǎn)移動(dòng)隊(duì)頭。如果不存在，需要構(gòu)造新的節(jié)點(diǎn)，并且嘗試把節(jié)點(diǎn)塞到隊(duì)頭，如果LRU空間不足，則通過 tail 淘汰掉隊(duì)尾的節(jié)點(diǎn)，同時(shí)在 HashMap 中移除 Key。
get(key)，通過 HashMap 找到 LRU 鏈表節(jié)點(diǎn)，因?yàn)楦鶕?jù)LRU 原理，這個(gè)節(jié)點(diǎn)是最新訪問的，所以要把節(jié)點(diǎn)插入到隊(duì)頭，然后返回緩存的值。
完整基于 Java 的代碼參考如下
class DLinkedNode {
String key;
int value;
DLinkedNode pre;
DLinkedNode post;
}LRU Cache
public class LRUCache {
private Hashtable
cache = new Hashtable();
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 如何實(shí)現(xiàn)，這個(gè)問題這么問肯定是有坑的，那就是redis肯定不是這樣實(shí)現(xiàn)的。
Redis的LRU實(shí)現(xiàn)
如果按照HashMap和雙向鏈表實(shí)現(xiàn)，需要額外的存儲(chǔ)存放 next 和 prev 指針，犧牲比較大的存儲(chǔ)空間，顯然是不劃算的。所以Redis采用了一個(gè)近似的做法，就是隨機(jī)取出若干個(gè)key，然后按照訪問時(shí)間排序后，淘汰掉最不經(jīng)常使用的，具體分析如下：
為了支持LRU，Redis 2.8.19中使用了一個(gè)全局的LRU時(shí)鐘，server.lruclock，定義如下，
#define REDIS_LRU_BITS 24
unsigned lruclock:REDIS_LRU_BITS; /* Clock for LRU eviction */
默認(rèn)的LRU時(shí)鐘的分辨率是1秒，可以通過改變REDIS_LRU_CLOCK_RESOLUTION宏的值來改變，Redis會(huì)在serverCron()中調(diào)用updateLRUClock定期的更新LRU時(shí)鐘，更新的頻率和hz參數(shù)有關(guān)，默認(rèn)為100ms一次，如下，
#define REDIS_LRU_CLOCK_MAX ((1<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時(shí)間戳，當(dāng) lruclock 的值超出REDIS_LRU_CLOCK_MAX時(shí)，會(huì)從頭開始計(jì)算，所以在計(jì)算一個(gè)key的最長(zhǎng)沒有訪問時(shí)間時(shí)，可能key本身保存的lru訪問時(shí)間會(huì)比當(dāng)前的lrulock還要大，這個(gè)時(shí)候需要計(jì)算額外時(shí)間，如下，
/* 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)淘汰策略包括，
當(dāng)進(jìn)行LRU淘汰時(shí)，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會(huì)基于server.maxmemory_samples配置選取固定數(shù)目的key，然后比較它們的lru訪問時(shí)間，然后淘汰最近最久沒有訪問的key，maxmemory_samples的值越大，Redis的近似LRU算法就越接近于嚴(yán)格LRU算法，但是相應(yīng)消耗也變高，對(duì)性能有一定影響，樣本值默認(rèn)為5。
Redis的過期策略，是有定期刪除+惰性刪除兩種。
定期好理解，默認(rèn)100s就隨機(jī)抽一些設(shè)置了過期時(shí)間的key，去檢查是否過期，過期了就刪了。
為啥不掃描全部設(shè)置了過期時(shí)間的key呢？
假如Redis里面所有的key都有過期時(shí)間，都掃描一遍？那太恐怖了，而且我們線上基本上也都是會(huì)設(shè)置一定的過期時(shí)間的。全掃描跟你去查數(shù)據(jù)庫不帶where條件不走索引全表掃描一樣，100s一次，Redis累都累死了。
如果一直沒隨機(jī)到很多key，里面不就存在大量的無效key了？
好問題，惰性刪除，見名知意，惰性嘛，我不主動(dòng)刪，我懶，我等你來查詢了我看看你過期沒，過期就刪了還不給你返回，沒過期該怎么樣就怎么樣。
最后就是如果的如果，定期沒刪，我也沒查詢，那可咋整？
內(nèi)存淘汰機(jī)制！
官網(wǎng)上給到的內(nèi)存淘汰機(jī)制是以下幾個(gè)：
noeviction:返回錯(cuò)誤當(dāng)內(nèi)存限制達(dá)到并且客戶端嘗試執(zhí)行會(huì)讓更多內(nèi)存被使用的命令（大部分的寫入指令，但DEL和幾個(gè)例外）
allkeys-lru: 嘗試回收最少使用的鍵（LRU），使得新添加的數(shù)據(jù)有空間存放。
volatile-lru: 嘗試回收最少使用的鍵（LRU），但僅限于在過期集合的鍵,使得新添加的數(shù)據(jù)有空間存放。
allkeys-random: 回收隨機(jī)的鍵使得新添加的數(shù)據(jù)有空間存放。
volatile-random: 回收隨機(jī)的鍵使得新添加的數(shù)據(jù)有空間存放，但僅限于在過期集合的鍵。
volatile-ttl: 回收在過期集合的鍵，并且優(yōu)先回收存活時(shí)間（TTL）較短的鍵,使得新添加的數(shù)據(jù)有空間存放。
如果沒有鍵滿足回收的前提條件的話，策略volatile-lru, volatile-random以及volatile-ttl就和noeviction 差不多了。
Redis為什么不使用真實(shí)的LRU實(shí)現(xiàn)是因?yàn)檫@需要太多的內(nèi)存。不過近似的LRU算法對(duì)于應(yīng)用而言應(yīng)該是等價(jià)的。使用真實(shí)的LRU算法與近似的算法可以通過下面的圖像對(duì)比。
其實(shí)在大家熟悉的LinkedHashMap中也實(shí)現(xiàn)了LRU算法的，
在LinkedHashMap里。我們只需要擴(kuò)展下即可，代碼示例如下：
/**
* Constructs an empty LinkedHashMap 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 - true for
* access-order, false 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 eldest) {
return false;
}使用accessOrder來標(biāo)識(shí)是使用訪問順序，還是插入順序。默認(rèn)為插入順序。當(dāng)accessOrder為訪問順序、容量固定時(shí)，即為L(zhǎng)RU
舉例如下：
當(dāng)容量超過100時(shí)，開始執(zhí)行LRU策略：將最近最少未使用的對(duì)象 evict 掉。
Map LRUCollection = Collections.synchronizedMap(new LinkedHashMap(100, .75F, true)
{
@Override
protected boolean removeEldestEntry(Map.Entry eldest)
{
return size() > 100;
}
});
真實(shí)面試中會(huì)讓你寫LUR算法，你可別搞原始的那個(gè)，那真TM多，寫不完的，你要么懟上面這個(gè)，要么懟下面這個(gè)，找一個(gè)數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)下Java版本的LRU還是比較容易的，知道啥原理就好了。
class LRULinkedHashMap extends LinkedHashMap {
/**
*
*/
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 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 map = new LinkedHashMap(5, 0.75f, true);
map.put(1, 1);
map.put(2, 2);
map.put(3, 3);
map.put(4, 4);
map.put(5, 5);
//此時(shí)輸出1,2,3,4,5
for(Iterator> it = map.entrySet().iterator(); it.hasNext();) {
System.out.println(it.next().getValue());
}
map.put(4, 4);
map.put(6, 6);
//此時(shí)輸出1,2,3,5,4,6（自動(dòng)擴(kuò)容）
for(Iterator> it = map.entrySet().iterator(); it.hasNext();) {
System.out.println(it.next().getValue());
}
}
public static void testLRULinkedHashMap() {
//容量固定，accessOrder=true
Map map = new LRULinkedHashMap(5);
map.put(1, 1);
map.put(2, 2);
map.put(3, 3);
map.put(4, 4);
map.put(5, 5);
//此時(shí)輸出1,2,3,4,5
for(Iterator> it = map.entrySet().iterator(); it.hasNext();) {
System.out.println(it.next().getValue());
}
map.put(4, 4);
map.put(6, 6);
//此時(shí)輸出2,3,5,4,6（容量鎖定，進(jìn)行刪除）
for(Iterator> it = map.entrySet().iterator(); it.hasNext();) {
System.out.println(it.next().getValue());
}
}
}
關(guān)于LRU原理及實(shí)現(xiàn)是怎樣的就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，可以學(xué)到更多知識(shí)。如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到。
網(wǎng)站欄目：LRU原理及實(shí)現(xiàn)是怎樣的
URL地址：
http://weahome.cn/article/pigjsg.html
重慶分公司
重慶分公司
