出處：https://juejin.cn/post/6923510255154528263

FIFO 先進先出

First In First Out ,先進先出

FIFO按照“先進先出（First In，First Out）”的原理淘汰資料，正好符合佇列的特性，資料結構上使用佇列Queue來實現。

新訪問的資料插入FIFO佇列尾部，資料在FIFO佇列中順序移動，淘汰FIFO佇列頭部的資料；

優點：

實現簡單

缺點：

無法根據資料的使用頻次、時間等維度進行最佳化，會導致快取命中率降低。

LRU 最近最少使用

Least Recently used 最近未使用，通常被翻譯為「最近最少使用」

B 和 A 都在淘汰程序之前使用過，更新最新的使用時間。 C 則一直沒有被使用，雖然不是最久的資料，但是根據 LRU，它需要被淘汰。

最近最少使用頁面置換演算法，也就是首先淘汰最長時間未被使用的頁面。

關鍵是看頁面最後一次被使用到發生排程的時間長短。

優點：

熱點快取將被持久命中

缺點：

當所有快取資料都變成熱點後，將失去 LRU 的優點。

LFU 最近最不常用

Least Frequently Used 最不常用淘汰演算法，通常被翻譯為「最近最不常用」

每當快取被使用的時候( C B A)，則將使用頻率加 1，當進行淘汰程序的時候，將使用頻率最低的資料淘汰( E )。

優點：

提高頻繁使用的資料的命中效率

缺點：

當所有資料都很頻繁訪問的時候，將失去優點

單純的 LFU 會有個問題會導致快取失效，當最新加入的 E 在 F 進來之前，沒有被訪問過，那麼它將被淘汰。還沒有給 E 被訪問的機會，E 就被淘汰了。所以我們可以在 E 進來的時候，設定一箇中位數的訪問頻率，保證新資料不會被馬上被淘汰。

ARC 自適應快取替換

Adaptive Replacement Cache 自適應快取替換演算法，是一種適應性Cache演算法, 它結合了LRU與LFU。

ARC 的精髓就是根據被淘汰資料的訪問情況，而增加對應 LRU 還是 LFU 連結串列的大小。

ARC 包含了四個連結串列。 LRU 和 LRU Ghost ， LFU 和 LFU Ghost， Ghost 連結串列為對應淘汰的資料記錄連結串列，不記錄資料，只記錄 ID 等資訊。

當資料 A 加入 LRU 後，如果 A 再次被訪問，則同時被放到 LFU 連結串列中。所以 LFU 連結串列的快取為 LRU 連結串列的多次訪問的資料。

當 LRU 連結串列淘汰了 B，那麼 B 的資訊則進入到 LRU Ghost 連結串列。如果 B 在之後再次被訪問，則增加 LRU 連結串列的大小，同時縮減 LFU 連結串列的大小。LFU 連結串列同理。

所以，這是一個根據最近未使用和最少頻率使用動態調整的演算法。

優點：

根據記憶體使用方式動態調整 LRU 和 LFU 的大小，以適應當前最佳的快取命中。

缺點：

佔用更多的記憶體空間

每一種演算法都有自己的特色，但是真正用在程式中，或多或少都會進行對應的最佳化。比如 Redis 會同時使用 LRU 和 LFU ，同時 LFU為了體現時間維度特徵而會主動將計數器減少等策略。

出處：https://juejin.cn/post/6923510255154528263