一、LRU-K算法
1、算法思想
LRU-K中的K代表最近使用的次數(shù)，因此LRU可以認為是LRU-1。LRU-K的主要目的是為了解決LRU算法“緩存污染”的問題，其核心思想是將“最近使用過1次”的判斷標(biāo)準(zhǔn)擴展為“最近使用過K次”。
2、工作原理
相比LRU，LRU-K需要多維護一個隊列，用于記錄所有緩存數(shù)據(jù)被訪問的歷史。只有當(dāng)數(shù)據(jù)的訪問次數(shù)達到K次的時候，才將數(shù)據(jù)放入緩存。當(dāng)需要淘汰數(shù)據(jù)時，LRU-K會淘汰第K次訪問時間距當(dāng)前時間最大的數(shù)據(jù)。詳細實現(xiàn)如下
(1). 數(shù)據(jù)第一次被訪問，加入到訪問歷史列表；
(2). 如果數(shù)據(jù)在訪問歷史列表里后沒有達到K次訪問，則按照一定規(guī)則（FIFO，LRU）淘汰；
(3). 當(dāng)訪問歷史隊列中的數(shù)據(jù)訪問次數(shù)達到K次后，將數(shù)據(jù)索引從歷史隊列刪除，將數(shù)據(jù)移到緩存隊列中，并緩存此數(shù)據(jù)，緩存隊列重新按照時間排序；
(4). 緩存數(shù)據(jù)隊列中被再次訪問后，重新排序；
(5). 需要淘汰數(shù)據(jù)時，淘汰緩存隊列中排在末尾的數(shù)據(jù)，即：淘汰“倒數(shù)第K次訪問離現(xiàn)在最久”的數(shù)據(jù)。
LRU-K具有LRU的優(yōu)點，同時能夠避免LRU的缺點，實際應(yīng)用中LRU-2是綜合各種因素后最優(yōu)的選擇，LRU-3或者更大的K值命中率會高，但適應(yīng)性差，需要大量的數(shù)據(jù)訪問才能將歷史訪問記錄清除掉。
二、Two queues（2Q）
1、算法思想
該算法類似于LRU-2，不同點在于2Q將LRU-2算法中的訪問歷史隊列（注意這不是緩存數(shù)據(jù)的）改為一個FIFO緩存隊列，即：2Q算法有兩個緩存隊列，一個是FIFO隊列，一個是LRU隊列。
2、工作原理
當(dāng)數(shù)據(jù)第一次訪問時，2Q算法將數(shù)據(jù)緩存在FIFO隊列里面，當(dāng)數(shù)據(jù)第二次被訪問時，則將數(shù)據(jù)從FIFO隊列移到LRU隊列里面，兩個隊列各自按照自己的方法淘汰數(shù)據(jù)。詳細實現(xiàn)如下：
(1). 新訪問的數(shù)據(jù)插入到FIFO隊列；
(2). 如果數(shù)據(jù)在FIFO隊列中一直沒有被再次訪問，則最終按照FIFO規(guī)則淘汰；
(3). 如果數(shù)據(jù)在FIFO隊列中被再次訪問，則將數(shù)據(jù)移到LRU隊列頭部；
(4). 如果數(shù)據(jù)在LRU隊列再次被訪問，則將數(shù)據(jù)移到LRU隊列頭部；
(5). LRU隊列淘汰末尾的數(shù)據(jù)。
參考資料：
The LRU-K Page Replacement Algorithm For Database Disk Buffering
2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm
