計(jì)算機(jī)科學(xué)中只有兩件難事：緩存失效和命名。-- Phil Karlton

緩存驅(qū)逐是從緩存中刪除數(shù)據(jù)，以便在緩存容量達(dá)到極限時(shí)為新條目騰出空間的過(guò)程。這有時(shí)會(huì)由緩存失效觸發(fā)，即從緩存中刪除不再被視為有效或新鮮的數(shù)據(jù)。

下圖顯示了最常見(jiàn)的緩存驅(qū)逐策略。

1.LRU（最近最少使用）

LRU 驅(qū)逐策略首先刪除最近訪問(wèn)次數(shù)最少的項(xiàng)目。這種方法的原理是，最近訪問(wèn)過(guò)的項(xiàng)目在不久的將來(lái)更有可能再次被訪問(wèn)。LRU 可以通過(guò)哈希表和雙鏈表的組合來(lái)實(shí)現(xiàn)。

2.MRU（最近使用）

與 LRU 相反，MRU 算法首先刪除最近使用的項(xiàng)目。在最近訪問(wèn)的項(xiàng)目不太可能很快再次被訪問(wèn)的情況下，這種策略非常有用。不過(guò)，由于 MRU 采用了與直覺(jué)相反的緩存管理方法，因此并不常用。

3.SLRU（分段式 LRU）

SLRU 將高速緩存分為兩段：緩存段和保護(hù)段。新項(xiàng)目最初被放入試用段。如果緩存段中的項(xiàng)目再次被訪問(wèn)，它就會(huì)被提升到保護(hù)段。從緩存段的 LRU 端開(kāi)始驅(qū)逐，保護(hù)段中的項(xiàng)目會(huì)被賦予更高的優(yōu)先級(jí)，以留在緩存中。這種方法旨在將 LRU 的優(yōu)勢(shì)與保護(hù)頻繁訪問(wèn)項(xiàng)目的附加層結(jié)合起來(lái)。

4.LFU（最不常用算法）

LFU 算法會(huì)驅(qū)逐訪問(wèn)頻率最低的項(xiàng)目。與考慮訪問(wèn)時(shí)間的 LRU 不同，LFU 側(cè)重于項(xiàng)目被訪問(wèn)的次數(shù)，因此更有利于長(zhǎng)期重復(fù)訪問(wèn)的項(xiàng)目。LFU 的實(shí)現(xiàn)可能比較復(fù)雜，因?yàn)樗枰櫾L問(wèn)次數(shù)，并有可能動(dòng)態(tài)調(diào)整整個(gè)緩存。

5.FIFO（先進(jìn)先出）

FIFO 是最簡(jiǎn)單的緩存策略之一，緩存以類似隊(duì)列的方式運(yùn)行，先驅(qū)逐最舊的項(xiàng)目，而不管其訪問(wèn)模式或頻率如何。雖然 FIFO 容易實(shí)現(xiàn)，但它并不考慮項(xiàng)目的實(shí)際使用情況，因此可能導(dǎo)致緩存性能不理想。

6.TTL（生存時(shí)間）

TTL 并非嚴(yán)格意義上的驅(qū)逐算法，它是一種為每個(gè)緩存項(xiàng)設(shè)定特定生命周期的策略。當(dāng) TTL 過(guò)期時(shí)，該項(xiàng)目將被視為過(guò)時(shí)項(xiàng)目，并在下次訪問(wèn)緩存時(shí)被自動(dòng)刪除或標(biāo)記為符合驅(qū)逐條件。TTL 可與其他驅(qū)逐策略結(jié)合使用，以管理緩存的新鮮度。

7.雙層緩存

在雙層緩存策略中，第一層使用內(nèi)存緩存，第二層使用分布式緩存。第一層通常保存經(jīng)常使用的數(shù)據(jù)。

8.RR（隨機(jī)替換）

隨機(jī)替換算法隨機(jī)選擇一個(gè)緩存項(xiàng)并將其驅(qū)逐，為新項(xiàng)目騰出空間。這種方法實(shí)施起來(lái)也很簡(jiǎn)單，不需要跟蹤訪問(wèn)模式或頻率。不過(guò)，它的簡(jiǎn)單性也帶來(lái)了代價(jià)，那就是可能純屬偶然地移除使用率高的項(xiàng)目。