LIRS算法是非常優秀的cache淘汰算法，被用于mysql 5.1之後的版本，這篇文章主要來源于對LIRS的發表論文《LIRS: An Efficient Low Interreference Recency Set Replacement Policy to Improve Buffer Cache Performance》的翻譯。
LRU(Least Recently Used):算法起源可追溯到1965年（甚至更早），是最為經典的頁面置換算法，算法思想為淘汰最長時間未被使用的頁面。LRU最友好的資料模型為具有時間局部性的請求隊列。但是由于未考慮頻率因素，偶發性的、周期性的批量操作時效果較差，緩存污染嚴重。使用hashmap和雙向連結清單實作，可以讓時間複雜度降至O（1）。
LFU(Least Frequently Used),淘汰一定時期内被通路次數最少的頁。
OPT（OPTimal replacement，最佳淘汰算法）：根據未來實際使用情況将未來的近期裡不用的頁替換出去。這種算法是用來評價期它替換算法好壞的标準。不可能實作。所選擇的被淘汰頁面将是以後永不使用的，或者是在最長時間内不再被通路的頁面。
MRU（最近最頻繁使用算法，Most Recently Used），最近最頻繁使用算法和最近最少使用算法相反，它會首先丢棄最近最常使用的資料。
LRU-2，隻有當資料的通路次數達到2次的時候，才将資料放入緩存。當需要淘汰資料時，LRU-2會淘汰第2次通路時間距目前時間最大的資料。可以拓展為LRU-K。
2Q（Two queues）：LRU2的改進，不同點在于2Q将LRU-2算法中的通路曆史隊列改為一個FIFO緩存隊列（即包含FIFO隊列和LRU隊列）。可拓展為MQ算法（ Multi Queue）。
Clock算法（Not Recently Used, NRU）：簡單的CLOCK算法是給每一幀關聯一個附加位，稱為使用位。當某一頁首次裝入主存時，該幀的使用位設定為1;當該頁随後再被通路到時，它的使用位也被置為1。當需要替換一頁時，系統掃描緩沖區，以查找使用位被置為0的一幀。每當遇到一個使用位為1的幀時，作業系統就将該位重新置為0；如果在這個過程開始時，緩沖區中所有幀的使用位均為0，則選擇遇到的第一個幀替換；如果所有幀的使用位均為1,則指針在緩沖區中完整地循環一周，把所有使用位都置為0。
LIRS是針對LRU做優化的算法，在很多文章中被給予很高的評價，并且已經被應用在mysql 5.1之後的版本中。
傳統的LRU算法有如下的問題：
1）對冷資料突發性通路抵抗能力差，可能會是以淘汰掉熱的檔案。好的算法裡：熱檔案不應該被冷檔案淘汰掉。
2）對于大量資料的循環通路抵抗能力查，極端情況下可能會出現命中率0%。好的算法裡：這種情況miss rate應該約等于buffer space shortage ratio。
3）不能按照資料的通路機率進行淘汰。好的算法：能夠按照資料的通路機率進行淘汰，隻有高機率通路的檔案才能在cache中長時間存活。一個例子如下：
一個B樹，每個leaf node指向一個block，有20000個block。每個leaf node有20B，每個block有2000B。Cache的每一個page有4000B。是以20000個leaf node需要用100個page進行存儲，20000個block需要用10000個page進行存儲。而實際上這個時候我們的cache隻有101個page，這個時候的最佳緩存政策為：cache中僅緩存leaf node，因為leaf node page的通路機率為0.005，而檔案的page通路機率0.00005。而LRU并不能做到這一點。
LIRS算法使用兩個參數來衡量一個cache 塊，分别是IRR(Inter-Reference Recency)和R（Recency），IRR為一個頁面最近兩次的通路間隔，當第一次被通路時IRR的值為無窮大（inf）。R為頁面最近一次通路到目前時間内有多少頁面曾經被通路過（LRU數值）。下面兩張圖為計算IRR和R值的方式和例子。
LIRS算法将資料塊分為LIR和HIR兩級的方式：
1）LIR：熱資料塊，已經被通路兩次的資料塊。
2）HIR：冷資料塊，還僅僅隻被通路一次的資料塊。任意HIR塊的IRR值小于Rmax就可以轉化為LIR塊。所有R值小于Rmax的HIR塊可以保留在棧S中。
LIRS算法會設定一個棧和一個FIFO隊列，棧S負責熱資料（LIR塊）淘汰，隊列Q中負責冷資料（HIR塊）淘汰。在棧S中的HIR塊索引分為兩種情況：資料存在于cache中和資料已經被淘汰（HIR塊）。典型的一種情形如下：
關于棧S和隊列Q的基本使用原則如下：
1）棧S存儲LIR塊以及R值小于所有LIR塊的Rmax的HIR塊。
2）隊列Q存儲所有存在的HIR塊。是以大小為Lhirs。
3）算法初始化之後新通路的塊都被當作LIR塊。當達到Llirs之後，新通路（或者通路過已經在棧S裡被淘汰的）的轉為HIR塊。
4）當需要一個free block時，從隊列Q移除一個HIR block，并将棧s中的這個block設定為non-resident。
5）確定棧S的底部為LIR塊。
6）當有HIR塊再次被通路，則将其更新為LIR塊放于棧頂，并将棧s底部的LIR塊降級為HIR塊，并将其放至隊列Q頂部。同時進行棧剪枝（stack push）。
Ps 棧剪枝的概念如下：
（1）.棧底一定要是LIR塊
（2）.如果棧底的LIR塊被移除，和上一個LIR塊之間的HIR塊也要被移除。
當通路一個block時，可能會出現如下情況：
1.通路棧中的LIR塊：将其移至棧頂，如果這個LIR原本在棧底，則進行剪枝。
2.通路棧S中的resident HIR塊：有兩種情況：
1）這個塊已經在棧S中存在了，此時将其移至棧首，并将其從隊列Q中删除，棧S底部的LIR塊轉為HIR塊，并被移動至隊列Q，接下來會進行剪枝操作。
2）這個塊在棧S中不存在，我們将他設定為HIR塊，并放至棧S頂和隊Q尾。
3.通路棧S non-resident HIR塊：隊列Q的隊首元素移除，并在cache中徹底删除它，并用于存儲新資料塊，并将其置于棧S頂部。接下來有兩種情況：
1）如果這個塊在棧S中，我們将其轉化為LIR塊并移動至棧頂，将棧S底部資料塊轉化為HIR塊移至隊列Q，然後對棧S剪枝。
2）如果這個塊不在棧S中，則将其置入隊列Q隊尾。
下面是來源于wiki的練習題，假設圖a為初始狀态，箭頭辨別此時對某個元素進行通路，箭頭所指向的圖為通路之後的棧S和隊列Q的結構。
論文中測試采用四種資料通路模式：
1）.從不重複通路（這個和第二個循環通路重合，是以将這種模式和第二種合并）
2）.循環通路
3）.集中性通路，每個block都會被集中通路。
4）.機率性通路（每個block都有固定機率）。
下圖是在循環通路模式下，各個算法的命中率，可以看到，LRU的命中率在cache較小的時候命中率基本為0。而LIRS此時的miss rate約等于buffer space shortage ratio。
下圖是在各個block機率性通路的通路模式下的性能分析，在cache size為50blocks的時候，LRU的命中率為9.3%，LIRS的命中率為55%，相差較大。
下圖是在每個block集中通路的情況下的性能分析。如果将圖像放大可以發現，LRU的命中率在cache size稍大的時候要優于LRU。因為此時通路序列具有時間局部性，當通路熱點偏移會為LIRS帶來一定性能退化（miss）。不過由于這種偏移并不頻繁且熱點通路較為集中，這種影響是有限的。
多種通路情況組合的性能分析如下,LIRS的性能明顯較優：
通過下面調整Lhirs值的大小的實驗分析，Lhirs的大小為L的1%為合适的，實驗如下。
通過實驗分析，HIR轉為LIR的門檻值在Rmax附近變化時，結果并無明顯卻差別，但是當調制550%Rmax時，命中率向LRU靠近。特别指出，LRU可以近似看作轉化門檻值為正無窮的LIRS。
複雜度分析：時間複雜度上，LIRS可以通過實作達到和LRU一樣的O（1）。空間複雜度如下圖，下圖是Rmax（棧S大小）和L的比值，可以看到，在這種正常的通路模式下，棧S的大小會大于L，但是也是小于3.5倍的關系。
LIRS算法在空間使用上有一定缺陷，即為棧S的大小在極端情況下會變的無法預期的大，文中提供了一種簡單的抑制方法，即超過大小限制之後移除棧最底部的HIR塊。下面是對棧S大小限制的性能測試，LIRS後面的數字為sizeof(S)/L，可以看出對棧S的大小限制并不會對性能産生過為惡劣的影響。