後端工程師面試考什麼 - 快取的置換策略(Cache replacement policies)
談到快取，一定會談到 Cache 的置換策略，也就是快取滿了要怎麼處理的問題。
理想上，能將所有資料都快取起來的話，就可以有效加速系統回應時間以及減輕資料庫負擔，但這是相當耗費/浪費系統資源的作法，除了系統資源有限之外（記憶體有限、儲存空間有限），另外根據 80/20 法則，系統中 80% 的資料存取要求，可能僅僅來自那 20% 的資料，我們僅需要針對這 20% 的資料進行快取就能夠在有限資源的條件下，十分有效地提升系統效能。
所以一般快取都會設定大小(size)，不會無限制的快取任何資料，也因此談到快取就會談到快取的置換策略，在 cache 滿的時候選擇刪除哪些舊資料以容納新資料的方法。
本文將介紹幾種面試常見的快取置換策略。
先進先出 FIFO (First In First Out)
FIFO 是最簡單的快取策略，先加到快取的資料將先被刪除。
這代表在快取滿時，最舊的快取資料將被移除，腾出的空間就成為新資料的儲存空間。
實際應用場景
FIFO 策略實作相當直覺簡單，但其假設最早快取的資料，是最不容易被再次存取，所以會被優先置換，這容易導致即使最早加入的資料是頻繁存取的熱點(hot spot)，也可能因為其快取的建立時間相當早，所以被優先淘汰，最終導致系統因為熱點的快取被刪而瞬間負載(loading)過大而倒站，所以一般較少見到使用 FIFO 策略作為快取置換策略，反而以 LRU 或 LFU 作為快取置換策略居多。
但如果是類似 YOY(Year-Over-Year) 的分析比較報表就相當適合使用 FIFO 置換策略，因為先進入的快取的資料到後期根本用不到，所以可以放心捨去，例如 2023 年只需要與 2022 年進行比較，將 2022 的資料快取起來，以方便 2023 年進行比較，所以可以放心捨去 2021 年的資料。
LRU (Least Recently Used)
LRU 是一種基於時間使用頻率的快取置換策略，當快取滿的時候，最久未被造訪的資料將被刪除。
概念上，我們會有類似一張表紀錄所有 Cache 最近 1 次的存取時間，如果在 Cache 滿的時候就將最久沒被存取的 Cache 刪掉，然後騰出空間存放新資料，例如下圖 index 1 是最久沒被使用到的快取，因此快取滿的時候， index 1 將會優先被置換掉：
實作上，這張紀錄存取時間的表，只需要將所有的快取按照最近存取時間排序即可，就可省略存取時間所需的記憶體空間，例如最少被存取的快取放在第 1 個（或最後 1 個），如果快取滿了，只要將第 1 個（或最後 1 個）快取拿掉即可。
實際應用場景
LRU 可用於快取昂貴的運算结果，例如一些需要大量運算或者運算成本較高的資料，而且會被頻繁存取的資料，譬如近 24 個月銷售數據分析報告，因為銷售數據分析報告通常需要經過分類、彙總(aggregation)、比較等多道手續產生，運算量相對龐大，而近 24 個月銷售數據分析報告又比起過於久遠前的資料更容易被存取，所以可以使用 LRU 快取策略，在此策略下太古老的銷售數據就很可能因為久未有使用者存取而被置換。
著名的 Redis 也有提供使用 LRU 作為快取置換策略的設定，詳見 Key eviction | Redis ，不過其所使用的 LRU 並不是正統的 LRU 而是 Approximated LRU algorithm ，它是用抽樣方法從樣本中挑出一個可以淘汰的快取。
Redis LRU algorithm is not an exact implementation. This means that Redis is not able to pick the best candidate for eviction, that is, the key that was accessed the furthest in the past. Instead it will try to run an approximation of the LRU algorithm, by sampling a small number of keys, and evicting the one that is the best (with the oldest access time) among the sampled keys.
LFU (Least Frequently Used)
LFU 與 LRU 十分相似，不過 LFU 是一種基於使用頻率的快取策略，當快取滿的時候，其中使用頻率最低的快取將被置換。
最簡單的使用頻率可以使用次數越高作為指標，存取次數越高代表使用頻率越高。不過使用存取次數作為指標會有副作用，該副作用是對使用次數低的快取資料相當不利，相較於存取次數高的快取資料來說，新加入的快取資料很高機率被其他新加入的快取資料給超越取代，造成存取次數高的快取一直不會消失，但使用次數排名較低的快取資料總是一直在變動。當然，你也可以實作適合自己的使用頻率指標。
實際應用場景
對於被存取的資料總是集中在少部分的情況，使用 LFU 快取策略可以有效降低系統負載並提高回應速度。例如電商的熱門商品就很適合使用 LFU 作為快取策略，畢竟多數流量都是熱門商品，因此熱門商品的存取次數會相對於其他商品來的更高，從而確保熱門商品的存取要求總是存在於快取之中。
Bloom Filter (布隆過濾器)
Bloom Filter 是一種儲存空間利用效率非常高的資料結構，用於檢查一個元素是否存在於一個集合中。
它的運作原理也很直覺暴力，用一個長度為 n 的 bit 陣列(array)儲存所有的快取，再透過 k 個雜湊函數(hash function)計算資料的在 bit array 中的索引值(index)，所以 1 筆資料可以得到 k 個索引值，如果查詢 bit array 這 k 個索引值都為 1, 就代表快取存在，只要任一索引值為 0 就代表快取不存在。
它通常被用於快速檢查一個資料是否已經存在於快取中，如果不存在就不必查詢資料庫系統，以藉此減輕資料庫的查詢負擔。
不過 Bloom Filter 有個缺點是會有機率發生誤報(false positive), 原因在於 hash function 有機率發生碰撞(collision)，如果某筆不存在的資料經過雜湊所得到的索引與一筆已經存在的快取資料雜湊索引值相同，就會導致誤報，這是在使用 Bloom Filter 時需要特別注意的事情。
實際應用場景
Bloom Filter 可用於快取大型資料集的索引。對於需要高效率查詢的大型資料集，使用 Bloom Filter 可以大大減少查詢資料庫的次數，提高系統效能，例如 Google Bigtable 使用了 Bloom Filter 減少查詢資料的次數。
ARC (Adaptive Replacement Cache)
ARC 是一種由 IBM 所提出的自動調整式快取置換策略，結合了 LRU 和 LFU 的優點。 ARC 快取策略會根據近期存取模式調整自己的行為，自動選擇 LRU 或 LFU 策略來最小化快取未命中的次數。但這應該比較少會被問到⋯⋯，不過這個演算法思路很有趣，可以應用在一些類似的問題上。
簡單解釋一下 ARC 運作原理，以下是 ARC 演算法的視覺化：
ARC 演算法主要會同時維護 LRU 與 LFU 2 種快取，並且紀錄這 2 種演算法哪些快取被置換掉，也就是上圖中的 Ghost list B1 與 Ghost list B2, 這 2 個 list 都是只存快取索引，不存快取資料，如果近期的快取要求都是打中 Ghost list B1, 那麼演算法就會調整成使用 LRU 策略的快取資料比較多，使用 LFU 策略的快取資料會變少，也就是 T1 的部分會長大，T2 的部分會變小，反之亦然。
更詳細演算法可以參閱 Adaptive replacement cache - Wikipedia 。
總結
快取的置換策略有相當多種，其中 LRU 與 LFU 幾乎是經常會被問到的面試問題，甚至 Leetcode 也有相對應的題目，而且工作上也都會經常遇到 LRU 或 LFU 相關的 issue 或應用，所以是ㄧ定要了解的 2 種快取置換策略，建議 Leetcode 也都要刷一下這 2 題，其他種策略則可以按照興趣自行研究。
References
Adaptive replacement cache - Wikipedia
Bloom Filter | Brilliant Math & Science Wiki
資料結構與演算法：LRU 快取機制 - Joseph’s blog
Least frequently used - Wikipedia
