[[437580]]

 引言

我們都聽過 cache，當(dāng)你問他們是什么是緩存的時候，他們會給你一個完美的答案，可是他們不知道緩存是怎么構(gòu)建的，或者沒有告訴你應(yīng)該采用什么標(biāo)準(zhǔn)去選擇緩存框架。在這篇文章，我們會去討論緩存，緩存算法，緩存框架以及哪個緩存框架會更好。

面試

“緩存就是存貯數(shù)據(jù)（使用頻繁的數(shù)據(jù)）的臨時地方，因為取原始數(shù)據(jù)的代價太大了，所以我可以取得快一些。”

這就是 programmer one （programmer one 是一個面試者）在面試中的回答（一個月前，他向公司提交了簡歷，想要應(yīng)聘要求在緩存，緩存框架，大規(guī)模數(shù)據(jù)操作有著豐富經(jīng)驗的 java 開發(fā)職位）。

programmer one 通過 hash table 實現(xiàn)了他自己的緩存，但是他知道的只是他的緩存和他那存儲著150條記錄的 hash table，這就是他認(rèn)為的大規(guī)模數(shù)據(jù)（緩存 = hashtable，只需要在 hash table 查找就好了），所以，讓我們來看看面試的過程吧。

面試官：你選擇的緩存方案，是基于什么標(biāo)準(zhǔn)的？

programmer one：呃，（想了5分鐘）嗯，基于，基于，基于數(shù)據(jù)（咳嗽……）

面試官：excese me ! 能不能重復(fù)一下？

programmer one：數(shù)據(jù)？！

面試官：好的。說說幾種緩存算法以及它們的作用

programmer one：（凝視著面試官，臉上露出了很奇怪的表情，沒有人知道原來人類可以做出這種表情 ）

面試官：好吧，那我換個說法，當(dāng)緩存達(dá)到容量時，會怎么做？

programmer one：容量？嗯（思考……hash table 的容量時沒有限制的，我能任意增加條目，它會自動擴充容量的）（這是 programmer one 的想法，但是他沒有說出來）

面試官對 programmer one 表示感謝（面試過程持續(xù)了10分鐘），之后一個女士走過來說：謝謝你的時間，我們會給你打電話的，祝你好心情。這是 programmer one 最糟糕的面試（他沒有看到招聘對求職者有豐富的緩存經(jīng)驗背景要求，實際上，他只看到了豐厚的報酬 ）。

說到做到

programmer one 離開之后，他想要知道這個面試者說的問題和答案，所以他上網(wǎng)去查，programmer one 對緩存一無所知，除了：當(dāng)我需要緩存的時候，我就會用 hash table。

在他使用了他最愛的搜索引擎搜索之后，他找到了一篇很不錯的關(guān)于緩存文章，并且開始去閱讀……

為什么我們需要緩存？

很久很久以前，在還沒有緩存的時候……用戶經(jīng)常是去請求一個對象，而這個對象是從數(shù)據(jù)庫去取，然后，這個對象變得越來越大，這個用戶每次的請求時間也越來越長了，這也把數(shù)據(jù)庫弄得很痛苦，他無時不刻不在工作。所以，這個事情就把用戶和數(shù)據(jù)庫弄得很生氣，接著就有可能發(fā)生下面兩件事情：

１.用戶很煩，在抱怨，甚至不去用這個應(yīng)用了（這是大多數(shù)情況下都會發(fā)生的）

２.數(shù)據(jù)庫為打包回家，離開這個應(yīng)用，然后，就出現(xiàn)了大麻煩（沒地方去存儲數(shù)據(jù)了）（發(fā)生在極少數(shù)情況下）

上帝派來了緩存

在幾年之后，IBM（60年代）的研究人員引進了一個新概念，它叫“緩存”。

什么是緩存？

正如開篇所講，緩存是“存貯數(shù)據(jù)（使用頻繁的數(shù)據(jù)）的臨時地方，因為取原始數(shù)據(jù)的代價太大了，所以我可以取得快一些。”

緩存可以認(rèn)為是數(shù)據(jù)的池，這些數(shù)據(jù)是從數(shù)據(jù)庫里的真實數(shù)據(jù)復(fù)制出來的，并且為了能別取回，被標(biāo)上了標(biāo)簽（鍵 ID）。太棒了

programmer one 已經(jīng)知道這點了，但是他還不知道下面的緩存術(shù)語。

命中：

當(dāng)客戶發(fā)起一個請求（我們說他想要查看一個產(chǎn)品信息），我們的應(yīng)用接受這個請求，并且如果是在第一次檢查緩存的時候，需要去數(shù)據(jù)庫讀取產(chǎn)品信息。

如果在緩存中，一個條目通過一個標(biāo)記被找到了，這個條目就會被使用、我們就叫它緩存命中。所以，命中率也就不難理解了。

Cache Miss：

但是這里需要注意兩點：

１.如果還有緩存的空間，那么，沒有命中的對象會被存儲到緩存中來。

２.如果緩存滿了，而又沒有命中緩存，那么就會按照某一種策略，把緩存中的舊對象踢出，而把新的對象加入緩存池。而這些策略統(tǒng)稱為替代策略（緩存算法），這些策略會決定到底應(yīng)該提出哪些對象。

存儲成本：

當(dāng)沒有命中時，我們會從數(shù)據(jù)庫取出數(shù)據(jù)，然后放入緩存。而把這個數(shù)據(jù)放入緩存所需要的時間和空間，就是存儲成本。

索引成本：

和存儲成本相仿。

失效：

當(dāng)存在緩存中的數(shù)據(jù)需要更新時，就意味著緩存中的這個數(shù)據(jù)失效了。

替代策略：

當(dāng)緩存沒有命中時，并且緩存容量已經(jīng)滿了，就需要在緩存中踢出一個老的條目，加入一條新的條目，而到底應(yīng)該踢出什么條目，就由替代策略決定。

最優(yōu)替代策略：

最優(yōu)的替代策略就是想把緩存中最沒用的條目給踢出去，但是未來是不能夠被預(yù)知的，所以這種策略是不可能實現(xiàn)的。但是有很多策略，都是朝著這個目前去努力。

Java 街惡夢：

當(dāng) programmer one 在讀這篇文章的時候，他睡著了，并且做了個惡夢（每個人都有做惡夢的時候）。

programmer one：nihahha，我要把你弄失效！（瘋狂的狀態(tài)）

緩存對象：別別，讓我活著，他們還需要我，我還有孩子。

programmer one：每個緩存對象在失效之前都會那樣說。你從什么時候開始有孩子的？不用擔(dān)心，現(xiàn)在就永遠(yuǎn)消失吧！

哈哈哈哈哈……programmer one 恐怖的笑著，但是警笛打破了沉靜，警察把 programmer one 抓了起來，并且控告他殺死了（失效）一個仍需被使用的緩存對象，他被押到了監(jiān)獄。

programmer one 突然醒了，他被嚇到了，渾身是汗，他開始環(huán)顧四周，發(fā)現(xiàn)這確實是個夢，然后趕緊繼續(xù)閱讀這篇文章，努力的消除自己的恐慌。

在programmer one 醒來之后，他又開始閱讀文章了。

緩存算法

沒有人能說清哪種緩存算法優(yōu)于其他的緩存算法

Least Frequently Used（LFU）：

大家好，我是 LFU，我會計算為每個緩存對象計算他們被使用的頻率。我會把最不常用的緩存對象踢走。

Least Recently User（LRU）：

我是 LRU 緩存算法，我把最近最少使用的緩存對象給踢走。

我總是需要去了解在什么時候，用了哪個緩存對象。如果有人想要了解我為什么總能把最近最少使用的對象踢掉，是非常困難的。

瀏覽器就是使用了我（LRU）作為緩存算法。新的對象會被放在緩存的頂部，當(dāng)緩存達(dá)到了容量極限，我會把底部的對象踢走，而技巧就是：我會把最新被訪問的緩存對象，放到緩存池的頂部。

所以，經(jīng)常被讀取的緩存對象就會一直呆在緩存池中。有兩種方法可以實現(xiàn)我，array 或者是 linked list。

我的速度很快，我也可以被數(shù)據(jù)訪問模式適配。我有一個大家庭，他們都可以完善我，甚至做的比我更好（我確實有時會嫉妒，但是沒關(guān)系）。我家庭的一些成員包括 LRU2 和 2Q，他們就是為了完善 LRU 而存在的。

Least Recently Used 2（LRU2）：

我是 Least Recently Used 2，有人叫我最近最少使用 twice，我更喜歡這個叫法。我會把被兩次訪問過的對象放入緩存池，當(dāng)緩存池滿了之后，我會把有兩次最少使用的緩存對象踢走。因為需要跟蹤對象2次，訪問負(fù)載就會隨著緩存池的增加而增加。如果把我用在大容量的緩存池中，就會有問題。另外，我還需要跟蹤那么不在緩存的對象，因為他們還沒有被第二次讀取。我比LRU好，而且是 adoptive to access 模式 。

Two Queues（2Q）：

我是 Two Queues；我把被訪問的數(shù)據(jù)放到 LRU 的緩存中，如果這個對象再一次被訪問，我就把他轉(zhuǎn)移到第二個、更大的 LRU 緩存。

我踢走緩存對象是為了保持第一個緩存池是第二個緩存池的1/3。當(dāng)緩存的訪問負(fù)載是固定的時候，把 LRU 換成 LRU2，就比增加緩存的容量更好。這種機制使得我比 LRU2 更好，我也是 LRU 家族中的一員，而且是 adoptive to access 模式 。

Adaptive Replacement Cache（ARC）：

我是 ARC，有人說我是介于 LRU 和 LFU 之間，為了提高效果，我是由2個 LRU 組成，第一個，也就是 L1，包含的條目是最近只被使用過一次的，而第二個 LRU，也就是 L2，包含的是最近被使用過兩次的條目。因此， L1 放的是新的對象，而 L2 放的是常用的對象。所以，別人才會認(rèn)為我是介于 LRU 和 LFU 之間的，不過沒關(guān)系，我不介意。

我被認(rèn)為是性能最好的緩存算法之一，能夠自調(diào)，并且是低負(fù)載的。我也保存著歷史對象，這樣，我就可以記住那些被移除的對象，同時，也讓我可以看到被移除的對象是否可以留下，取而代之的是踢走別的對象。我的記憶力很差，但是我很快，適用性也強。

Most Recently Used（MRU）：

我是 MRU，和 LRU 是對應(yīng)的。我會移除最近最多被使用的對象，你一定會問我為什么。好吧，讓我告訴你，當(dāng)一次訪問過來的時候，有些事情是無法預(yù)測的，并且在緩存系統(tǒng)中找出最少最近使用的對象是一項時間復(fù)雜度非常高的運算，這就是為什么我是最好的選擇。

我是數(shù)據(jù)庫內(nèi)存緩存中是多么的常見！每當(dāng)一次緩存記錄的使用，我會把它放到棧的頂端。當(dāng)棧滿了的時候，你猜怎么著？我會把棧頂?shù)膶ο蠼o換成新進來的對象！

First in First out（FIFO）：

我是先進先出，我是一個低負(fù)載的算法，并且對緩存對象的管理要求不高。我通過一個隊列去跟蹤所有的緩存對象，最近最常用的緩存對象放在后面，而更早的緩存對象放在前面，當(dāng)緩存容量滿時，排在前面的緩存對象會被踢走，然后把新的緩存對象加進去。我很快，但是我并不適用。

Second Chance：

大家好，我是 second chance，我是通過 FIFO 修改而來的，被大家叫做 second chance 緩存算法，我比 FIFO 好的地方是我改善了 FIFO 的成本。我是 FIFO 一樣也是在觀察隊列的前端，但是很FIFO的立刻踢出不同，我會檢查即將要被踢出的對象有沒有之前被使用過的標(biāo)志（1一個 bit 表示），沒有沒有被使用過，我就把他踢出；否則，我會把這個標(biāo)志位清除，然后把這個緩存對象當(dāng)做新增緩存對象加入隊列。你可以想象就這就像一個環(huán)隊列。當(dāng)我再一次在隊頭碰到這個對象時，由于他已經(jīng)沒有這個標(biāo)志位了，所以我立刻就把他踢開了。我在速度上比 FIFO 快。

CLock：

我是 Clock，一個更好的 FIFO，也比 second chance 更好。因為我不會像 second chance 那樣把有標(biāo)志的緩存對象放到隊列的尾部，但是也可以達(dá)到 second chance 的效果。

我持有一個裝有緩存對象的環(huán)形列表，頭指針指向列表中最老的緩存對象。當(dāng)緩存 miss 發(fā)生并且沒有新的緩存空間時，我會問問指針指向的緩存對象的標(biāo)志位去決定我應(yīng)該怎么做。如果標(biāo)志是0，我會直接用新的緩存對象替代這個緩存對象；如果標(biāo)志位是1，我會把頭指針遞增，然后重復(fù)這個過程，知道新的緩存對象能夠被放入。我比 second chance 更快。

Simple time-based：

我是 simple time-based 緩存算法，我通過絕對的時間周期去失效那些緩存對象。對于新增的對象，我會保存特定的時間。我很快，但是我并不適用。

Extended time-based expiration：

我是 extended time-based expiration 緩存算法，我是通過相對時間去失效緩存對象的；對于新增的緩存對象，我會保存特定的時間，比如是每5分鐘，每天的12點。

Sliding time-based expiration：

我是 sliding time-based expiration，與前面不同的是，被我管理的緩存對象的生命起點是在這個緩存的最后被訪問時間算起的。我很快，但是我也不太適用。

其他的緩存算法還考慮到了下面幾點：

成本：如果緩存對象有不同的成本，應(yīng)該把那些難以獲得的對象保存下來。

容量：如果緩存對象有不同的大小，應(yīng)該把那些大的緩存對象清除，這樣就可以讓更多的小緩存對象進來了。

時間：一些緩存還保存著緩存的過期時間。電腦會失效他們，因為他們已經(jīng)過期了。

根據(jù)緩存對象的大小而不管其他的緩存算法可能是有必要的。

電子郵件！

在讀完這篇文章之后，programmer one 想了一會兒，然后決定給作者發(fā)封郵件，他感覺作者的名字在哪聽過，但是已經(jīng)想不起來了。不管怎樣，他還是把郵件發(fā)送出來了，他詢問了作者在分布式環(huán)境中，緩存是怎么樣工作的。

文章的作者收到了郵件，具有諷刺意味的是，這個作者就是面試 programmer one 的人 ，作者回復(fù)了……

在這一部分中，我們來看看如何實現(xiàn)這些著名的緩存算法。以下的代碼只是示例用的，如果你想自己實現(xiàn)緩存算法，可能自己還得加上一些額外的工作。

LeftOver 機制

在 programmer one 閱讀了文章之后，他接著看了文章的評論，其中有一篇評論提到了 leftover 機制——random cache。

Random Cache

我是隨機緩存，我隨意的替換緩存實體，沒人敢抱怨。你可以說那個被替換的實體很倒霉。通過這些行為，我隨意的去處緩存實體。我比 FIFO 機制好，在某些情況下，我甚至比 LRU 好，但是，通常LRU都會比我好。

現(xiàn)在是評論時間

當(dāng) programmer one 繼續(xù)閱讀評論的時候，他發(fā)現(xiàn)有個評論非常有趣，這個評論實現(xiàn)了一些緩存算法，應(yīng)該說這個評論做了一個鏈向評論者網(wǎng)站的鏈接，programmer one順著鏈接到了那個網(wǎng)站，接著閱讀。

看看緩存元素（緩存實體）

publicclassCacheElement 
 
{ 
 
privateObjectobjectValue; 
 
privateObjectobjectKey; 
 
privateintindex; 
 
privateinthitCount;// getters and setters 
 
} 
 
//這個緩存實體擁有緩存的key和value，這個實體的數(shù)據(jù)結(jié)構(gòu)會被以下所有緩存算法用到。 
 
//緩存算法的公用代碼 
 
publicfinalsynchronizedvoidaddElement(Objectkey,Objectvalue) 
 
{ 
 
intindex; 
 
Objectobj; 
 
// get the entry from the table 
 
obj = table.get(key); 
 
// If we have the entry already in our table 
 
// then get it and replace only its value. 
 
obj = table.get(key); 
 
if(obj != null) 
 
{ 
 
CacheElement element; 
 
element = (CacheElement)obj; 
 
element.setObjectValue(value); 
 
element.setObjectKey(key); 
 
return; 
 
} 
 
｝ 

上面的代碼會被所有的緩存算法實現(xiàn)用到。這段代碼是用來檢查緩存元素是否在緩存中了，如果是，我們就替換它，但是如果我們找不到這個 key 對應(yīng)的緩存，我們會怎么做呢？那我們就來深入的看看會發(fā)生什么吧！

現(xiàn)場訪問

今天的專題很特殊，因為我們有特殊的客人，事實上他們是我們想要聽的與會者，但是首先，先介紹一下我們的客人：Random Cache，F(xiàn)IFO Cache。讓我們從 Random Cache開始。

看看隨機緩存的實現(xiàn)

publicfinalsynchronizedvoidaddElement(Objectkey,Objectvalue) 
 
{ 
 
intindex; 
 
Objectobj; 
 
obj = table.get(key); 
 
if(obj != null) 
 
{ 
 
CacheElement element;// Just replace the value. 
 
element = (CacheElement)obj; 
 
element.setObjectValue(value); 
 
element.setObjectKey(key); 
 
return; 
 
}// If we haven't filled the cache yet, put it at the end. 
 
if(!isFull()) 
 
{ 
 
index = numEntries; 
 
++numEntries; 
 
} 
 
else{// Otherwise, replace a random entry. 
 
index = (int)(cache.length * random.nextFloat()); 
 
table.remove(cache[index].getObjectKey()); 
 
} 
 
cache[index].setObjectValue(value); 
 
cache[index].setObjectKey(key); 
 
table.put(key,cache[index]); 
 
} 
 
//看看FIFO緩算法的實現(xiàn) 
 
publicfinalsynchronizedvoidaddElement(Objectkey,Objectvalue) 
 
{ 
 
intindex; 
 
Objectobj; 
 
obj = table.get(key); 
 
if(obj != null) 
 
{ 
 
CacheElement element;// Just replace the value. 
 
element = (CacheElement)obj; 
 
element.setObjectValue(value); 
 
element.setObjectKey(key); 
 
return; 
 
} 
 
// If we haven't filled the cache yet, put it at the end. 
 
if(!isFull()) 
 
{ 
 
index = numEntries; 
 
++numEntries; 
 
} 
 
else{// Otherwise, replace the current pointer, 
 
// entry with the new one. 
 
index = current; 
 
// in order to make Circular FIFO 
 
if(++current >= cache.length) 
 
current = 0; 
 
table.remove(cache[index].getObjectKey()); 
 
} 
 
cache[index].setObjectValue(value); 
 
cache[index].setObjectKey(key); 
 
table.put(key,cache[index]); 
 
} 

看看LFU緩存算法的實現(xiàn)

publicsynchronizedObjectgetElement(Objectkey) 
 
{ 
 
Objectobj; 
 
obj = table.get(key); 
 
if(obj != null) 
 
{ 
 
CacheElement element = (CacheElement)obj; 
 
element.setHitCount(element.getHitCount() + 1); 
 
returnelement.getObjectValue(); 
 
} 
 
returnnull; 
 
} 
 
publicfinalsynchronizedvoidaddElement(Objectkey,Objectvalue) 
 
{ 
 
Objectobj; 
 
obj = table.get(key); 
 
if(obj != null) 
 
{ 
 
CacheElement element;// Just replace the value. 
 
element = (CacheElement)obj; 
 
element.setObjectValue(value); 
 
element.setObjectKey(key); 
 
return; 
 
} 
 
if(!isFull()) 
 
{ 
 
index = numEntries; 
 
++numEntries; 
 
} 
 
else 
 
{ 
 
CacheElement element = removeLfuElement(); 
 
index = element.getIndex(); 
 
table.remove(element.getObjectKey()); 
 
} 
 
cache[index].setObjectValue(value); 
 
cache[index].setObjectKey(key); 
 
cache[index].setIndex(index); 
 
table.put(key,cache[index]); 
 
} 
 
publicCacheElement removeLfuElement() 
 
{ 
 
CacheElement[]elements = getElementsFromTable(); 
 
CacheElement leastElement = leastHit(elements); 
 
returnleastElement; 
 
} 
 
publicstaticCacheElement leastHit(CacheElement[]elements) 
 
{ 
 
CacheElement lowestElement = null; 
 
for(inti = 0;i < elements.length;i++) 
 
{ 
 
CacheElement element = elements[i]; 
 
if(lowestElement == null) 
 
{ 
 
lowestElement = element; 
 
} 
 
else{ 
 
if(element.getHitCount() < lowestElement.getHitCount()) 
 
{ 
 
lowestElement = element; 
 
} 
 
} 
 
} 
 
returnlowestElement; 
 
} 

今天的專題很特殊，因為我們有特殊的客人，事實上他們是我們想要聽的與會者，但是首先，先介紹一下我們的客人：Random Cache, FIFO Cache。讓我們從 Random Cache開始。

最重點的代碼，就應(yīng)該是 leastHit 這個方法，這段代碼就是把

hitCount 最低的元素找出來，然后刪除，給新進的緩存元素留位置。

看看LRU緩存算法實現(xiàn)

privatevoidmoveToFront(intindex) 
 
{ 
 
intnextIndex,prevIndex; 
 
if(head != index) 
 
{ 
 
nextIndex = next[index]; 
 
prevIndex = prev[index]; 
 
// Only the head has a prev entry that is an invalid index 
 
// so we don't check. 
 
next[prevIndex] = nextIndex; 
 
// Make sure index is valid. If it isn't, we're at the tail 
 
// and don't set prev[next]. 
 
if(nextIndex >= 0) 
 
prev[nextIndex] = prevIndex; 
 
else 
 
tail = prevIndex; 
 
prev[index] = -1; 
 
next[index] = head; 
 
prev[head] = index; 
 
head = index; 
 
} 
 
} 
 
publicfinalsynchronizedvoidaddElement(Objectkey,Objectvalue) 
 
{ 
 
intindex;Objectobj; 
 
obj = table.get(key); 
 
if(obj != null) 
 
{ 
 
CacheElement entry; 
 
// Just replace the value, but move it to the front. 
 
entry = (CacheElement)obj; 
 
entry.setObjectValue(value); 
 
entry.setObjectKey(key); 
 
moveToFront(entry.getIndex()); 
 
return; 
 
} 
 
// If we haven't filled the cache yet, place in next available 
 
// spot and move to front. 
 
if(!isFull()) 
 
{ 
 
if(_numEntries > 0) 
 
{ 
 
prev[_numEntries] = tail; 
 
next[_numEntries] = -1; 
 
moveToFront(numEntries); 
 
} 
 
++numEntries; 
 
} 
 
else{// We replace the tail of the list. 
 
table.remove(cache[tail].getObjectKey()); 
 
moveToFront(tail); 
 
} 
 
cache[head].setObjectValue(value); 
 
cache[head].setObjectKey(key); 
 
table.put(key,cache[head]); 
 
} 

這段代碼的邏輯如 LRU算法 的描述一樣，把再次用到的緩存提取到最前面，而每次刪除的都是最后面的元素。

結(jié)論

我們已經(jīng)看到 LFU緩存算法 和 LRU緩存算法的實現(xiàn)方式，至于如何實現(xiàn)，采用數(shù)組還是 LinkedHashMap，都由你決定，不夠我一般是小的緩存容量用數(shù)組，大的用 LinkedHashMap。