沒(méi)有人能說(shuō)清哪種緩存算法優(yōu)于其他的緩存算法。（以下的幾種緩存算法，有的我也理解不好，如果感興趣，你可以Google一下）
Least Frequently Used（LFU）：
大家好，我是 LFU，我會(huì)計(jì)算為每個(gè)緩存對(duì)象計(jì)算他們被使用的頻率。我會(huì)把最不常用的緩存對(duì)象踢走。
Least Recently User（LRU）：
我是LRU緩存算法，我把最近最少使用的緩存對(duì)象給踢走。
我總是需要去了解在什么時(shí)候，用了哪個(gè)緩存對(duì)象。如果有人想要了解我為什么總能把最近最少使用的對(duì)象踢掉，是非常困難的。
瀏覽器就是使用了我（LRU）作為緩存算法。新的對(duì)象會(huì)被放在緩存的頂部，當(dāng)緩存達(dá)到了容量極限，我會(huì)把底部的對(duì)象踢走，而技巧就是：我會(huì)把最新被訪問(wèn)的緩存對(duì)象，放到緩存池的頂部。
所以，經(jīng)常被讀取的緩存對(duì)象就會(huì)一直呆在緩存池中。有兩種方法可以實(shí)現(xiàn)我，array 或者是 linked list。
我的速度很快，我也可以被數(shù)據(jù)訪問(wèn)模式適配。我有一個(gè)大家庭，他們都可以完善我，甚至做的比我更好（我確實(shí)有時(shí)會(huì)嫉妒，但是沒(méi)關(guān)系）。我家庭的一些成員包括LRU2 和 2Q，他們就是為了完善 LRU 而存在的。
Least Recently Used 2（LRU2）：
我是 Least Recently Used 2，有人叫我最近最少使用twice，我更喜歡這個(gè)叫法。我會(huì)把被兩次訪問(wèn)過(guò)的對(duì)象放入緩存池，當(dāng)緩存池滿了之后，我會(huì)把有兩次最少使用的緩存對(duì)象踢走。 因?yàn)樾枰檶?duì)象2次，訪問(wèn)負(fù)載就會(huì)隨著緩存池的增加而增加。如果把我用在大容量的緩存池中，就會(huì)有問(wèn)題。另外，我還需要跟蹤那么不在緩存的對(duì)象，因?yàn)樗?們還沒(méi)有被第二次讀取。我比LRU好，而且是 adoptive to access 模式 。
Two Queues（2Q）：
我是 Two Queues；我把被訪問(wèn)的數(shù)據(jù)放到LRU的緩存中，如果這個(gè)對(duì)象再一次被訪問(wèn)，我就把他轉(zhuǎn)移到第二個(gè)、更大的LRU緩存。
我踢走緩存對(duì)象是為了保持第一個(gè)緩存池是第二個(gè)緩存池的1/3。當(dāng)緩存的訪問(wèn)負(fù)載是固定的時(shí)候，把 LRU 換成 LRU2，就比增加緩存的容量更好。這種機(jī)制使得我比 LRU2 更好，我也是 LRU 家族中的一員，而且是 adoptive to access 模式 。
Adaptive Replacement Cache（ARC）：
我是 ARC，有人說(shuō)我是介于 LRU 和 LFU 之間，為了提高效果，我是由2個(gè) LRU 組成，第一個(gè)，也就是 L1，包含的條目是最近只被使用過(guò)一次的，而第二個(gè) LRU，也就是 L2，包含的是最近被使用過(guò)兩次的條目。因此， L1 放的是新的對(duì)象，而 L2 放的是常用的對(duì)象。所以，別人才會(huì)認(rèn)為我是介于 LRU 和 LFU 之間的，不過(guò)沒(méi)關(guān)系，我不介意。
我被認(rèn)為是性能最好的緩存算法之一，能夠自調(diào)，并且是低負(fù)載的。我也保存著歷史對(duì)象，這樣，我就可以記住那些被移除的對(duì)象，同時(shí)，也讓我可以看到被移除的對(duì)象是否可以留下，取而代之的是踢走別的對(duì)象。我的記憶力很差，但是我很快，適用性也強(qiáng)。
Most Recently Used（MRU）：
我是 MRU，和 LRU 是對(duì)應(yīng)的。我會(huì)移除最近最多被使用的對(duì)象，你一定會(huì)問(wèn)我為什么。好吧，讓我告訴你，當(dāng)一次訪問(wèn)過(guò)來(lái)的時(shí)候，有些事情是無(wú)法預(yù)測(cè)的，并且在緩存系統(tǒng)中找出最少最近使用的對(duì)象是一項(xiàng)時(shí)間復(fù)雜度非常高的運(yùn)算，這就是為什么我是最好的選擇。
我是數(shù)據(jù)庫(kù)內(nèi)存緩存中是多么的常見(jiàn)！每當(dāng)一次緩存記錄的使用，我會(huì)把它放到棧的頂端。當(dāng)棧滿了的時(shí)候，你猜怎么著？我會(huì)把棧頂?shù)膶?duì)象給換成新進(jìn)來(lái)的對(duì)象！
First in First out（FIFO）：
我是先進(jìn)先出，我是一個(gè)低負(fù)載的算法，并且對(duì)緩存對(duì)象的管理要求不高。我通過(guò)一個(gè)隊(duì)列去跟蹤所有的緩存對(duì)象，最近最常用的緩存對(duì)象放在后面，而更早的緩存對(duì)象放在前面，當(dāng)緩存容量滿時(shí)，排在前面的緩存對(duì)象會(huì)被踢走，然后把新的緩存對(duì)象加進(jìn)去。我很快，但是我并不適用。
Second Chance：
大家好，我是 second chance，我是通過(guò)FIFO修改而來(lái)的，被大家叫做 second chance 緩存算法，我比 FIFO 好的地方是我改善了 FIFO 的成本。我是 FIFO 一樣也是在觀察隊(duì)列的前端，但是很FIFO的立刻踢出不同，我會(huì)檢查即將要被踢出的對(duì)象有沒(méi)有之前被使用過(guò)的標(biāo)志（1一個(gè)bit表示），沒(méi)有沒(méi)有被使用 過(guò)，我就把他踢出；否則，我會(huì)把這個(gè)標(biāo)志位清除，然后把這個(gè)緩存對(duì)象當(dāng)做新增緩存對(duì)象加入隊(duì)列。你可以想象就這就像一個(gè)環(huán)隊(duì)列。當(dāng)我再一次在隊(duì)頭碰到這個(gè) 對(duì)象時(shí)，由于他已經(jīng)沒(méi)有這個(gè)標(biāo)志位了，所以我立刻就把他踢開(kāi)了。我在速度上比FIFO快。
CLock
我是Clock，一個(gè)更好的FIFO，也比 second chance更好。因?yàn)槲也粫?huì)像second chance那樣把有標(biāo)志的緩存對(duì)象放到隊(duì)列的尾部，但是也可以達(dá)到second chance的效果。
我持有一個(gè)裝有緩存對(duì)象的環(huán)形列表，頭指針指向列表中最老的緩存對(duì)象。當(dāng)緩存miss發(fā)生并且沒(méi)有新的緩存空間時(shí)，我會(huì)問(wèn)問(wèn)指針指向的緩存對(duì)象的標(biāo) 志位去決定我應(yīng)該怎么做。如果標(biāo)志是0，我會(huì)直接用新的緩存對(duì)象替代這個(gè)緩存對(duì)象；如果標(biāo)志位是1，我會(huì)把頭指針遞增，然后重復(fù)這個(gè)過(guò)程，知道新的緩存對(duì) 象能夠被放入。我比second chance更快。
Simple time-based：
我是 simple time-based 緩存算法，我通過(guò)絕對(duì)的時(shí)間周期去失效那些緩存對(duì)象。對(duì)于新增的對(duì)象，我會(huì)保存特定的時(shí)間。我很快，但是我并不適用。
Extended time-based expiration：
我是 extended time-based expiration 緩存算法，我是通過(guò)相對(duì)時(shí)間去失效緩存對(duì)象的；對(duì)于新增的緩存對(duì)象，我會(huì)保存特定的時(shí)間，比如是每5分鐘，每天的12點(diǎn)。
Sliding time-based expiration：
我是 sliding time-based expiration，與前面不同的是，被我管理的緩存對(duì)象的生命起點(diǎn)是在這個(gè)緩存的最后被訪問(wèn)時(shí)間算起的。我很快，但是我也不太適用。
好了！聽(tīng)了那么多緩存算法的自我介紹，其他的緩存算法還考慮到了下面幾點(diǎn)：
- 成本。如果緩存對(duì)象有不同的成本，應(yīng)該把那些難以獲得的對(duì)象保存下來(lái)。
- 容量。如果緩存對(duì)象有不同的大小，應(yīng)該把那些大的緩存對(duì)象清除，這樣就可以讓更多的小緩存對(duì)象進(jìn)來(lái)了。
- 時(shí)間。一些緩存還保存著緩存的過(guò)期時(shí)間。電腦會(huì)失效他們，因?yàn)樗麄円呀?jīng)過(guò)期了。
根據(jù)緩存對(duì)象的大小而不管其他的緩存算法可能是有必要的。
原文：http://www.zavakid.com/27