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