緩存一般從以下三個特征進行描述：
命中率
返回正確結(jié)果數(shù)/請求緩存次數(shù)，命中率問題是緩存中的一個非常重要的問題，它是衡量緩存有效性的重要指標。命中率越高，表明緩存的使用率越高。
最大元素（或最大空間）
緩存中可以存放的最大元素的數(shù)量，一旦緩存中元素數(shù)量超過這個值（或者緩存數(shù)據(jù)所占空間超過其最大支持空間），那么將會觸發(fā)緩存啟動清空策略根據(jù)不同的場景合理的設(shè)置最大元素值往往可以一定程度上提高緩存的命中率，從而更有效使用緩存。
淘汰（替換）策略
如上描述，緩存的存儲空間有限制，當緩存空間被用滿時，如何保證在穩(wěn)定服務的同時有效提升命中率？這就由淘汰（替換）策略來處理，設(shè)計適合自身數(shù)據(jù)特征的淘汰策略能有效提升命中率。
因此，選擇一個適合使用場景的淘汰（替換）策略非常重要，能夠大大提升緩存命中率，從而加速業(yè)務處理
緩存的淘汰（替換）根據(jù)訪問模式可以分為基于時間或者訪問頻率兩類，下面分別對這兩類進行詳細描述：
基于訪問時間：此類算法按各緩存項的被訪問時間來組織緩存隊列,決定替換對象，如LRU。
基于訪問頻率：此類算法用緩存項的被訪問頻率來組織緩存。如LFU、LRU-2、2Q、LIRS。
?LRU
基本思想：如果數(shù)據(jù)最近被訪問過，那么將來被訪問的幾率也更高
常見實用方法：一般采用unordered_map+list來實現(xiàn)，訪問數(shù)據(jù)時，直接從unordered_map通過key在O(1)時間內(nèi)獲取到所需數(shù)據(jù)。有新數(shù)據(jù)時，插入到鏈表的頭部；當緩存命中時，也將數(shù)據(jù)移動到鏈表頭部；當緩存滿時將鏈表尾部的數(shù)據(jù)丟棄。
命中率分析
當存在熱點數(shù)據(jù)時，LRU的效率很好，但偶發(fā)性的、周期性的批量操作會導致LRU命中率急劇下降，緩存污染情況比較嚴重。
MySQL對樸素LRU算法的改進
由于樸素的LRU算法會存在緩存污染問題，若直接讀取到的頁放入到LRU的首部，那么某些SQL操作可能會使緩沖池中的頁被刷新出，從而影響緩沖池的效率。常見的這類操作為索引或數(shù)據(jù)的掃描操作。這類操作需要訪問表中的許多頁，甚至是全部的頁，而這些頁通常來說又僅在這次查詢操作中需要，并不是活躍的熱點數(shù)據(jù)。如果頁被放入LRU列表的首部，那么非?？赡軐⑺枰臒狳c數(shù)據(jù)頁從LRU列表移除，而在下一次需要讀取該頁時，InnoDB存儲引擎需要再次訪問磁盤。
解決方案
InnoDB存儲引擎引入了另一個參數(shù)來進一步管理LRU列表，這個參數(shù)是Innodb_old_blocks_time，用于表示頁讀取到mid位置后需要等待多久才會被加入到LRU列表的熱端。鏈表按照5:3的比例分為young區(qū)和old區(qū)，新加入的數(shù)據(jù)放在old區(qū)，若old區(qū)的數(shù)據(jù)在LRU鏈表中存在時間超過了1秒，則將其移動到鏈表頭部，如果數(shù)據(jù)在LRU old區(qū)鏈表中存在的時間少于1秒，則保持位置不變，淘汰時優(yōu)先淘汰old區(qū)的數(shù)據(jù)。這樣可以避免全表掃描對LRU鏈表的污染，全表掃描的冷數(shù)據(jù)很快會被淘汰出去。
?LFU
基本思想：如果數(shù)據(jù)過去被訪問多次，那么將來被訪問的頻率也更高。
注意LFU和LRU的區(qū)別，LRU的淘汰規(guī)則是基于訪問時間，而LFU是基于訪問次數(shù)
常見實現(xiàn)方法：與LRU類似，LFU一般也采用unordered_map+list來實現(xiàn)，訪問數(shù)據(jù)時，直接從unordered_map通過key在O(1)時間內(nèi)獲取到所需數(shù)據(jù)。有新數(shù)據(jù)時，插入到鏈表的尾部；
當緩存命中時，增加該key的引用計數(shù)，鏈表按照引用計數(shù)排序。為了避免節(jié)點在鏈表中頻繁移動，一般會將鏈表劃分為多個區(qū)域或者使用多個鏈表，如果引用計數(shù)落入某個范圍，將該節(jié)點加入到相應的鏈表中，當引用計數(shù)超出閾值時將當前節(jié)點移動到上一個區(qū)間的鏈表。當緩存滿時將引用計數(shù)最小的區(qū)域的數(shù)據(jù)丟棄。
命中率分析
LFU命中率要優(yōu)于LRU，且能夠避免周期性或者偶發(fā)性的操作導致緩存命中率下降的問題，但LFU需要記錄數(shù)據(jù)的歷史訪問記錄，一旦數(shù)據(jù)訪問模式改變，LFU需要更長時間來適用新的訪問模式，即LFU存在歷史數(shù)據(jù)影響將來數(shù)據(jù)的"緩存污染"問題。
?LRU-K
LRU-K中的K代表最近使用的次數(shù)，因此LRU可以認為是LRU-1。LRU-K的主要目的是為了解決LRU算法"緩存污染"的問題，其核心思想是將"最近使用過1次"的判斷標準擴展為"最近使用過K次"
常用實現(xiàn)如下
數(shù)據(jù)第一次被訪問，加入到訪問歷史列表；如果數(shù)據(jù)在訪問歷史列表里后沒有達到K次訪問，則按照LRU淘汰；當訪問歷史隊列中的數(shù)據(jù)訪問次數(shù)達到K次后，將數(shù)據(jù)索引從歷史隊列刪除，將數(shù)據(jù)移到緩存隊列中，并緩存此數(shù)據(jù)，緩存隊列重新按照時間排序；緩存數(shù)據(jù)隊列中被再次訪問后，重新排序；需要淘汰數(shù)據(jù)時，淘汰緩存隊列中排在末尾的數(shù)據(jù)，即淘汰"倒數(shù)第K次訪問離現(xiàn)在最久"的數(shù)據(jù)。
命中率分析
LRU-K具有LRU的優(yōu)點，同時能夠避免LRU的缺點，實際應用中LRU-2是綜合各種因素后最優(yōu)的選擇，LRU-3或者更大的K值命中率會高，但適應性差，需要大量的數(shù)據(jù)訪問才能將歷史訪問記錄清除掉。LRU-K降低了"緩存污染"帶來的問題，命中率比LRU要高。
2Q與LRU-2類似，不同點在于將LRU-2算法中的訪問歷史隊列改成了一個FIFO隊列，這里不再贅述。上面介紹了4個常用的緩存淘汰算法，實現(xiàn)起來也不是很復雜。當然還有一些其他的算法，這里就不再介紹了，感興趣的朋友可以查找資料學習一下。
