本文主要講的是目前存在的幾種緩存算法, 沒錯, 我又來誤人子弟了.

內容會圍繞近幾年比較流行的LFU, LRU, 還有W-TinyLRU這麼三種緩存算法來講, 儘量使用最簡練的文本.

LFU

近期最少使用算法，即LFU算法（Least Frequently Used algorithm）。 這種算法會淘汰近期最少訪問的緩存, 仔細分析一下, 沒錯，這是一種非常合理的算法，因為到目前為止最少使用的頁面， 很可能也是將來最少訪問的頁面。 該算法既充分利用了內存中緩存調度情況的歷史信息，又正確反映了程序的局部性。

但是，這種算法的開銷極其高, 為了記錄每個緩存的使用情況, 你不得不為每一個緩存增加一個很大的計數器, 每次到達臨界點, 我們還需要找到所有計數器中最少的緩存, 淘汰它.

核心思想：如果一個數據在最近一段時間內使用次數很少，那麼在將來一段時間內被使用的可能性也很小.

通常我們會這麼去實現:

外部結構為Array, 存儲元素為KV. K: 該緩存訪問次數. V: 緩存本身. 數組按照K排序. 每次緩存大小即將臨界, 淘汰K最小的緩存.

順便一提 Window-LFU 它是LFU算法的改良版. LFU中緩存的訪問次數記錄的時間範圍為整個程序的生命週期, 在Window-LFU中只對特定範圍的訪問次數進行淘汰. (比如最近10次訪問的緩存.)

LRU

最久沒有使用算法，即LRU算法（Least Recently Used algorithm）。 這種算法把近期最久沒有被訪問過的頁面作為被替換的頁面。 它把LFU算法中要記錄數量上的"多"與"少"簡化成判斷"有"與"無"，因此，實現起來比較容易。

核心思想：如果在一段時間內長時間不訪問的頁面將來也不會訪問.

實現很簡單:

假設我們的緩存容量大小為2, 最多緩存2個元素. 下面是緩存的訪問順序.

1 2 2 3

第一次: [1]

第二次: [2, 1]

第三次: [2, 1]

第四次: [3, 2]

最新訪問的緩存會放在首位, 很久沒有訪問的緩存自然而然的就到了末尾, 然後被淘汰.

W-TinyLRU

知名緩存框架 caffeine 就是使用的這種算法 這種算法結合LRU和LFU算法，解決了突發流量問題帶來的。

整個算法數據結構分成三個段,分別為  Eden,Probation,Protected 三個隊列

  • Eden隊列: 在caffeine中規定只能為緩存容量的%1,如果size=100, 那這個隊列的有效大小就等於1。這個隊列中記錄的是新到的數據， 防止突發流量由於之前沒有訪問頻率，而導致被淘汰。 比如有一部新劇上線，在最開始其實是沒有訪問頻率的， 防止上線之後被其他緩存淘汰出去，而加入這個區域。

  • Probation隊列:叫做緩刑隊列，在這個隊列就代表你的數據相對比較冷，馬上就要被淘汰了。
    這個有效大小為size減去eden減去protected。

  • Protected隊列:在這個隊列中，可以稍微放心一下了，你暫時不會被淘汰， 但是別急，如果Probation隊列沒有數據了或者Protected數據滿了， 你也將會被面臨淘汰的尷尬局面。當然想要變成這個隊列， 需要把Probation訪問一次之後，就會提升為Protected隊列。 這個有效大小為(size減去eden) X 80% 如果size =100，就會是79。

區域規則:

  1. 所有的新數據都會進入Eden。
  2. Eden滿了，淘汰進入Probation。
  3. 如果在Probation中訪問了其中某個數據，則這個數據升級為Protected。
  4. 如果Protected滿了又會繼續降級為Probation。

Probation的淘汰算法也比較有意思, 取出隊尾和隊首的元素, 然後讓這兩皇城PK, 輸了就淘汰了.

皇城PK規則:

1.如果隊尾元素的頻度大於隊首，那麼就直接淘汰隊首，

2.當隊尾頻度小於等於隊首，且頻度小於5的時候，直接將其淘汰

3.當隊尾頻度小於等於隊首，且頻度大於5的時候，通過隨機的方式進行淘汰任意一個。(看誰運氣好咯)