《三次給你聊清楚Redis》之Redis咋實現的
randomLevel() level := 1 // random()返回一個[0...1)的隨機數 while random() < p and level < MaxLevel do level := level + 1 return level
randomLevel()的偽碼中包含兩個參數，一個是p，一個是MaxLevel。在Redis的skiplist實現中，這兩個參數的取值為：
p = 1/4 MaxLevel = 32
2.2.2skiplist的算法性能分析
在這一部分，我們來簡單分析一下skiplist的時間復雜度和空間復雜度，以便對于skiplist的性能有一個直觀的了解。如果你不是特別偏執于算法的性能分析，那么可以暫時跳過這一小節的內容。
我們先來計算一下每個節點所包含的平均指針數目（概率期望）。節點包含的指針數目，相當于這個算法在空間上的額外開銷(overhead)，可以用來度量空間復雜度。
根據前面randomLevel()的偽碼，我們很容易看出，產生越高的節點層數，概率越低。定量的分析如下：
節點層數至少為1。而大于1的節點層數，滿足一個概率分布。
節點層數恰好等于1的概率為1-p。
節點層數大于等于2的概率為p，而節點層數恰好等于2的概率為p(1-p)。
節點層數大于等于3的概率為p^2，而節點層數恰好等于3的概率為p^2(1-p)。
節點層數大于等于4的概率為p^3，而節點層數恰好等于4的概率為p^3(1-p)。
......
因此，一個節點的平均層數（也即包含的平均指針數目），計算如下：
現在很容易計算出：
當p=1/2時，每個節點所包含的平均指針數目為2；
當p=1/4時，每個節點所包含的平均指針數目為1.33。這也是Redis里的skiplist實現在空間上的開銷。
接下來，為了分析時間復雜度，我們計算一下skiplist的平均查找長度。查找長度指的是查找路徑上跨越的跳數，而查找過程中的比較次數就等于查找長度加1。以前面圖中標出的查找23的查找路徑為例，從左上角的頭結點開始，一直到結點22，查找長度為6。
為了計算查找長度，這里我們需要利用一點小技巧。我們注意到，每個節點插入的時候，它的層數是由隨機函數randomLevel()計算出來的，而且隨機的計算不依賴于其它節點，每次插入過程都是完全獨立的。所以，從統計上來說，一個skiplist結構的形成與節點的插入順序無關。
這樣的話，為了計算查找長度，我們可以將查找過程倒過來看，從右下方第1層上最后到達的那個節點開始，沿著查找路徑向左向上回溯，類似于爬樓梯的過程。我們假設當回溯到某個節點的時候，它才被插入，這雖然相當于改變了節點的插入順序，但從統計上不影響整個skiplist的形成結構。
現在假設我們從一個層數為i的節點x出發，需要向左向上攀爬k層。這時我們有兩種可能：
如果節點x有第(i+1)層指針，那么我們需要向上走。這種情況概率為p。
如果節點x沒有第(i+1)層指針，那么我們需要向左走。這種情況概率為(1-p)。
用C(k)表示向上攀爬k個層級所需要走過的平均查找路徑長度（概率期望），那么：
C(0)=0 C(k)=(1-p)×(上圖中情況b的查找長度) + p×(上圖中情況c的查找長度)
代入，得到一個差分方程并化簡：
C(k)=(1-p)(C(k)+1) + p(C(k-1)+1) C(k)=1/p+C(k-1) C(k)=k/p
這個結果的意思是，我們每爬升1個層級，需要在查找路徑上走1/p步。而我們總共需要攀爬的層級數等于整個skiplist的總層數-1。
那么接下來我們需要分析一下當skiplist中有n個節點的時候，它的總層數的概率均值是多少。這個問題直觀上比較好理解。根據節點的層數隨機算法，容易得出：
第1層鏈表固定有n個節點；
第2層鏈表平均有n*p個節點；
第3層鏈表平均有n*p^2個節點；
...
所以，從第1層到最高層，各層鏈表的平均節點數是一個指數遞減的等比數列。容易推算出，總層數的均值為log1/pn，而最高層的平均節點數為1/p。
綜上，粗略來計算的話，平均查找長度約等于：
C(log1/pn-1)=(log1/pn-1)/p
即，平均時間復雜度為O(log n)。
當然，這里的時間復雜度分析還是比較粗略的。比如，沿著查找路徑向左向上回溯的時候，可能先到達左側頭結點，然后沿頭結點一路向上；還可能先到達最高層的節點，然后沿著最高層鏈表一路向左。但這些細節不影響平均時間復雜度的最后結果。另外，這里給出的時間復雜度只是一個概率平均值，但實際上計算一個精細的概率分布也是有可能的。
詳情還請參見William Pugh的論文《Skip Lists: A Probabilistic Alternative to Balanced Trees》。
2.2.3skiplist與平衡樹、哈希表的比較
skiplist和各種平衡樹（如AVL、紅黑樹等）的元素是有序排列的，而哈希表不是有序的。因此，在哈希表上只能做單個key的查找，不適宜做范圍查找。所謂范圍查找，指的是查找那些大小在指定的兩個值之間的所有節點。
在做范圍查找的時候，平衡樹比skiplist操作要復雜。在平衡樹上，我們找到指定范圍的小值之后，還需要以中序遍歷的順序繼續尋找其它不超過大值的節點。如果不對平衡樹進行一定的改造，這里的中序遍歷并不容易實現。而在skiplist上進行范圍查找就非常簡單，只需要在找到小值之后，對第1層鏈表進行若干步的遍歷就可以實現。
平衡樹的插入和刪除操作可能引發子樹的調整，邏輯復雜，而skiplist的插入和刪除只需要修改相鄰節點的指針，操作簡單又快速。
從內存占用上來說，skiplist比平衡樹更靈活一些。一般來說，平衡樹每個節點包含2個指針（分別指向左右子樹），而skiplist每個節點包含的指針數目平均為1/(1-p)，具體取決于參數p的大小。如果像Redis里的實現一樣，取p=1/4，那么平均每個節點包含1.33個指針，比平衡樹更有優勢。
查找單個key，skiplist和平衡樹的時間復雜度都為O(log n)，大體相當；而哈希表在保持較低的哈希值沖突概率的前提下，查找時間復雜度接近O(1)，性能更高一些。所以我們平常使用的各種Map或dictionary結構，大都是基于哈希表實現的。
從算法實現難度上來比較，skiplist比平衡樹要簡單得多。
2.2.4Redis中的skiplist和經典有何不同
分數(score)允許重復，即skiplist的key允許重復。這在最開始介紹的經典skiplist中是不允許的。
在比較時，不僅比較分數（相當于skiplist的key），還比較數據本身。在Redis的skiplist實現中，數據本身的內容唯一標識這份數據，而不是由key來唯一標識。另外，當多個元素分數相同的時候，還需要根據數據內容來進字典排序。
第1層鏈表不是一個單向鏈表，而是一個雙向鏈表。這是為了方便以倒序方式獲取一個范圍內的元素。
在skiplist中可以很方便地計算出每個元素的排名(rank)。
There are a few reasons:
1) They are not very memory intensive. It's up to you basically. Changing parameters about the probability of a node to have a given number of levels will make then less memory intensive than btrees.
2) A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees.
3) They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch (already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code.
有幾個原因：
1）它們的記憶力不是很強。基本上由你決定。更改有關節點具有給定數量級別的概率的參數將使內存密集度低于btree。
2）排序集通常是許多Zrange或Zrevrange操作的目標，即作為鏈表遍歷跳過列表。通過此操作，跳過列表的緩存區域性至少與其他類型的平衡樹一樣好。
3）它們易于實現、調試等。例如，由于跳過列表的簡單性，我收到了一個補丁（已經在redis master中），其中包含在o（log（n））中實現zrank的擴展跳過列表。它只需要對代碼稍作修改。
2.3HyperLogLog 專欄
HyperLogLog 是一種概率數據結構，用來估算數據的基數。數據集可以是網站訪客的 IP 地址，E-mail 郵箱或者用戶 ID。
基數就是指一個集合中不同值的數目，比如 a, b, c, d 的基數就是 4，a, b, c, d, a 的基數還是 4。雖然 a 出現兩次，只會被計算一次。
使用 Redis 統計集合的基數一般有三種方法，分別是使用 Redis 的 HashMap，BitMap 和 HyperLogLog。前兩個數據結構在集合的數量級增長時，所消耗的內存會大大增加，但是 HyperLogLog 則不會。
Redis 的 HyperLogLog 通過犧牲準確率來減少內存空間的消耗，只需要12K內存，在標準誤差0.81%的前提下，能夠統計2^64個數據。所以 HyperLogLog 是否適合在比如統計日活月活此類的對精度要不不高的場景。
這是一個很驚人的結果，以如此小的內存來記錄如此大數量級的數據基數。下面我們就帶大家來深入了解一下 HyperLogLog 的使用，基礎原理，源碼實現和具體的試驗數據分析。
2.3.1HyperLogLog 在 Redis 中的使用
Redis 提供了?PFADD?、?PFCOUNT?和?PFMERGE?三個命令來供用戶使用 HyperLogLog。
PFADD?用于向 HyperLogLog 添加元素。
> PFADD visitors alice bob carol (integer) 1 > PFCOUNT visitors (integer) 3
如果 HyperLogLog 估計的近似基數在?PFADD?命令執行之后出現了變化， 那么命令返回 1 ， 否則返回 0 。 如果命令執行時給定的鍵不存在， 那么程序將先創建一個空的 HyperLogLog 結構， 然后再執行命令。
PFCOUNT?命令會給出 HyperLogLog 包含的近似基數。在計算出基數后，?PFCOUNT?會將值存儲在 HyperLogLog 中進行緩存，知道下次?PFADD?執行成功前，就都不需要再次進行基數的計算。
PFMERGE?將多個 HyperLogLog 合并為一個 HyperLogLog ， 合并后的 HyperLogLog 的基數接近于所有輸入 HyperLogLog 的并集基數。
> PFADD customers alice dan (integer) 1 > PFMERGE everyone visitors customers OK > PFCOUNT everyone (integer) 4
2.3.2內存消耗對比實驗
我們下面就來通過實驗真實對比一下下面三種數據結構的內存消耗，HashMap、BitMap 和 HyperLogLog。
我們首先使用 Lua 腳本向 Redis 對應的數據結構中插入一定數量的數，然后執行 bgsave 命令，最后使用 redis-rdb-tools 的 rdb 的命令查看各個鍵所占的內存大小。
下面是 Lua 的腳本
local key = KEYS[1] local size = tonumber(ARGV[1]) local method = tonumber(ARGV[2]) for i=1,size,1 do if (method == 0) then redis.call('hset',key,i,1) elseif (method == 1) then redis.call('pfadd',key, i) else redis.call('setbit', key, i, 1) end end
我們在通過 redis-cli 的?script load?命令將 Lua 腳本加載到 Redis 中，然后使用?evalsha?命令分別向 HashMap、HyperLogLog 和 BitMap 三種數據結構中插入了一千萬個數，然后使用?rdb?命令查看各個結構內存消耗。
我們進行了兩輪實驗，分別插入一萬數字和一千萬數字，三種數據結構消耗的內存統計如下所示。
從表中可以明顯看出，一萬數量級時 BitMap 消耗內存最小， 一千萬數量級時 HyperLogLog 消耗內存最小，但是總體來看，HyperLogLog 消耗的內存都是 14392 字節，可見 HyperLogLog 在內存消耗方面有自己的獨到之處。
2.3.3基本原理
HyperLogLog 是一種概率數據結構，它使用概率算法來統計集合的近似基數。而它算法的最本源則是伯努利過程。
伯努利過程就是一個拋硬幣實驗的過程。拋一枚正常硬幣，落地可能是正面，也可能是反面，二者的概率都是 1/2 。伯努利過程就是一直拋硬幣，直到落地時出現正面位置，并記錄下拋擲次數k。比如說，拋一次硬幣就出現正面了，此時 k 為 1; 第一次拋硬幣是反面，則繼續拋，直到第三次才出現正面，此時 k 為 3。
對于 n 次伯努利過程，我們會得到 n 個出現正面的投擲次數值 k1, k2 ... kn , 其中這里的最大值是k_max。
根據一頓數學推導，我們可以得出一個結論： 2^{k_ max} 來作為n的估計值。也就是說你可以根據最大投擲次數近似的推算出進行了幾次伯努利過程。
下面，我們就來講解一下 HyperLogLog 是如何模擬伯努利過程，并最終統計集合基數的。
HyperLogLog 在添加元素時，會通過Hash函數，將元素轉為64位比特串，例如輸入5，便轉為101(省略前面的0，下同)。這些比特串就類似于一次拋硬幣的伯努利過程。比特串中，0 代表了拋硬幣落地是反面，1 代表拋硬幣落地是正面，如果一個數據最終被轉化了 10010000，那么從低位往高位看，我們可以認為，這串比特串可以代表一次伯努利過程，首次出現 1 的位數為5，就是拋了5次才出現正面。
所以 HyperLogLog 的基本思想是利用集合中數字的比特串第一個 1 出現位置的最大值來預估整體基數，但是這種預估方法存在較大誤差，為了改善誤差情況，HyperLogLog中引入分桶平均的概念，計算 m 個桶的調和平均值。
Redis 中 HyperLogLog 一共分了 2^14 個桶，也就是 16384 個桶。每個桶中是一個 6 bit 的數組。
HyperLogLog 將上文所說的 64 位比特串的低 14 位單獨拿出，它的值就對應桶的序號，然后將剩下 50 位中第一次出現 1 的位置值設置到桶中。50位中出現1的位置值最大為50，所以每個桶中的 6 位數組正好可以表示該值。
在設置前，要設置進桶的值是否大于桶中的舊值，如果大于才進行設置，否則不進行設置。
此時為了性能考慮，是不會去統計當前的基數的，而是將 HyperLogLog 頭的 card 屬性中的標志位置為 1，表示下次進行 pfcount 操作的時候，當前的緩存值已經失效了，需要重新統計緩存值。在后面 pfcount 流程的時候，發現這個標記為失效，就會去重新統計新的基數，放入基數緩存。
在計算近似基數時，就分別計算每個桶中的值，帶入到上文的 DV 公式中，進行調和平均和結果修正，就能得到估算的基數值。
2.3.4HyperLogLog 具體對象
我們首先來看一下 HyperLogLog 對象的定義
struct hllhdr { char magic[4]; /* 魔法值 "HYLL" */ uint8_t encoding; /* 密集結構或者稀疏結構 HLL_DENSE or HLL_SPARSE. */ uint8_t notused[3]; /* 保留位, 全為0. */ uint8_t card[8]; /* 基數大小的緩存 */ uint8_t registers[]; /* 數據字節數組 */ };
HyperLogLog 對象中的?registers?數組就是桶，它有兩種存儲結構，分別為密集存儲結構和稀疏存儲結構，兩種結構只涉及存儲和桶的表現形式，從中我們可以看到 Redis 對節省內存極致地追求。
我們先看相對簡單的密集存儲結構，它也是十分的簡單明了，既然要有 2^14 個 6 bit的桶，那么我就真使用足夠多的?uint8_t?字節去表示，只是此時會涉及到字節位置和桶的轉換，因為字節有 8 位，而桶只需要 6 位。
所以我們需要將桶的序號轉換成對應的字節偏移量 offsetbytes 和其內部的位數偏移量 offsetbits。需要注意的是小端字節序，高位在右側，需要進行倒轉。
當 offset_bits 小于等于2時，說明一個桶就在該字節內，只需要進行倒轉就能得到桶的值。
offset_bits 大于 2 ，則說明一個桶分布在兩個字節內，此時需要將兩個字節的內容都進行倒置，然后再進行拼接得到桶的值。
Redis 為了方便表達稀疏存儲，它將上面三種字節表示形式分別賦予了一條指令。
ZERO : 一字節，表示連續多少個桶計數為0，前兩位為標志00，后6位表示有多少個桶，最大為64。
XZERO : 兩個字節，表示連續多少個桶計數為0，前兩位為標志01，后14位表示有多少個桶，最大為16384。
VAL : 一字節，表示連續多少個桶的計數為多少，前一位為標志1，四位表示連桶內計數，所以最大表示桶的計數為32。后兩位表示連續多少個桶。
Redis從稀疏存儲轉換到密集存儲的條件是：
任意一個計數值從 32 變成 33，因為 VAL 指令已經無法容納，它能表示的計數值最大為 32
稀疏存儲占用的總字節數超過 3000 字節，這個閾值可以通過 hllsparsemax_bytes 參數進行調整。
2.4LRU專欄
2.4.1LRU介紹和代碼實現
LRU全稱是Least?Recently Used，即最近最久未使用的意思。
LRU算法的設計原則是：如果一個數據在最近一段時間沒有被訪問到，那么在將來它被訪問的可能性也很小。也就是說，當限定的空間已存滿數據時，應當把最久沒有被訪問到的數據淘汰。（這一段是找的，讓大家理解一下什么是LRU）。
說一下我們什么時候見到過LRU：其實老師們肯定都給大家舉過這么個例子：你在圖書館，你把書架子里的書拿到桌子上。。但是桌子是有限的，你有時候不得不把一些書放回去。這就相當于內存和硬盤。這個例子都說過吧？
LRU就是記錄你最長時間沒看過的書，就把它放回去。在cache那里見過吧
然后最近在研究redis，又看到了這個LRU，所以就想寫一下吧。
題目：設計一個結構，這個結構可以查詢K-V，但是容量有限，當存不下的時候就要把用的年代最久遠的那個東西扔掉。
其實思路很簡單，我們維護一個雙向鏈表即可，get也就是使用了，我們就把把它提到最安全的位置。新來的KV就依次放即可。
我們就先寫這個雙向鏈表結構
先寫節點結構：
public static class Node
然后寫雙向鏈表結構： 我們沒必要把鏈表操作都寫了，分析一下，我們只有三個操作：
1、加節點
2、使用了某個節點就把它調到尾，代表優先級最高
3、把優先級最低的移除，也就是去頭部
（不會的，翻我之前的鏈表操作都有寫）
public static class NodeDoubleLinkedList
鏈表操作封裝完了就要實現這個結構了。
具體思路代碼注釋
public static class MyCache
2.4.2Redis中的LRU算法改進
redis通常使用緩存，是使用一種固定最大內存的使用。當數據達到可使用的最大固定內存時，我們需要通過移除老數據來獲取空間。redis作為緩存是否有效的重要標志是如何尋找一種好的策略：刪除即將需要使用的數據是一種糟糕的策略，而刪除那些很少再次請求的數據則是一種好的策略。
在其他的緩存組件還有個命中率，僅僅表示讀請求的比例。訪問一個緩存中的keys通常不是分布式的。然而訪問經常變化，這意味著不經常訪問，相反，有些keys一旦不流行可能會轉向最經常訪問的keys。 因此，通常一個緩存系統應該盡可能保留那些未來最有可能被訪問的keys。針對keys淘汰的策略是：那些未來極少可能被訪問的數據應該被移除。
但有一個問題：redis和其他緩存系統不能夠預測未來。
LRU算法
緩存系統不能預測未來，原因是：那些很少再次被訪問的key也很有可能最近訪問相當頻繁。如果經常被訪問的模式不會突然改變，那么這是一種很有效的策略。然而，“最近經常被訪問”似乎更隱晦地標明一種 理念。這種算法被稱為LRU算法。最近訪問頻繁的key相比訪問少的key有更高的可能性。
舉個例子，這里有4個不同訪問周期的key，每一個“~”字符代表一秒，結尾的“|”表示當前時刻。
~~~~~A~~~~~A~~~~~A~~~~A~~~~~A~~~~~A~~| ~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~| ~~~~~~~~~~C~~~~~~~~~C~~~~~~~~~C~~~~~~| ~~~~~D~~~~~~~~~~D~~~~~~~~~D~~~~~~~~~D|
A key每5秒請求一次，B周期是2秒，C、D都是10秒。
訪問頻率最高的是B，因為它的空閑時間最短，這意味著B是4個key中未來最有可能被訪問的key。
同樣的A和C目前的空閑時間是2s和6s也能很好地反映它們本身的周期。然而你可以看到不夠嚴謹：D的訪問周期是10秒，但它卻是4個key中最近被訪問的。
當然，在一個很長的運行周期中，LRU算法能工作得很好。通常有一個更高訪問頻率的key當然有一個更低的空閑周期。LRU算法淘汰最少被訪問key，那些有最大空閑周期的key。實現上也相當容易，只需要額外跟蹤最近被訪問的key即可，有時甚至都需要：把所有我們想要淘汰的對象放到一個鏈表中，當一個對象訪問就移除鏈表頭部元素，當我們要淘汰元素是就直接淘汰鏈表尾部開始。
redis中的LRU:起因
最初，redis不支持LRU算法。當內存有效性成為一個必須被解決的問題時，后來才加上了。通過修改redis對象結構，在每個key對象增加24bit的空間。沒有額外的空間使用鏈表把所有對象放到一個鏈表中（大指針），因此需要實現得更加有效，不能因為key淘汰算法而讓整個服務改動太大。
24bits的對象已經足夠去存儲當前的unxi時間戳。這個表現，被稱為“LRU 時鐘”，key元數據經常被更新，所以它是一個有效的算法。
然后，有另一個更加復雜的問題需要解決：如何選擇訪問間隔最長的key，然后淘汰它。
redis內部采用一個龐大的hash table來保存，添加另外一個數據結構存儲時間間隔顯然不是一個好的選擇。然而我們希望能達到一個LRU本身是一個近似的，通過LRU算法本身來實現。
redis原始的淘汰算法簡單實現：**當需要淘汰一個key時，隨機選擇3個key，淘汰其中間隔時間最長的key。**基本上，我們隨機選擇key，淘汰key效果很好。后來隨機3個key改成一個配置項"N隨機key"。但把默認值提高改成5個后效果大大提高。考慮到它的效果，你根本不用修改他。
然而，你可能會想這個算法如何有效執行，你可以看到我們如何搗毀了很多有趣的數據。也許簡單的N key，我們會遇到很多好的決策，但是當我們淘汰最好的，下一個周期又開始抓。
驗證規則第一條：用肉眼觀察你的算法
其中有一個觀點已經應用到Redis 3.0正式版中了。在redis2.8中一個LRU緩存經常被使用在多個環境，用戶關于淘汰的沒有抱怨太多，但是很明顯我可以提高它，通過不僅僅是增加額外的空間，還有額外的CPU時間。
然而為了提高某項功能，你必須觀察它。有多個不同的方式去觀察LRU算法。你可以通過寫工具觀察，例如模擬不同的工作負載、校驗命中率和失誤率。
程序非常簡單：增加一些指定的keys，然后頻繁地訪問這些keys以至于每一個key都有一個下降的空閑時間。最終超過50%的keys被增加，一半的老key需要被淘汰。
一個完美理想的LRU實現，應該是沒有最新加的key被淘汰，而是淘汰最初的50%的老key。
規則二：不要丟棄重要信息
借助最新的可視化工具，我可以在嘗試新的方法觀察和測試幾分鐘。使用redis最明顯有效的提高算法就是，積累對立的垃圾信息在一個淘汰池中。
基本上，當N keys算法被采用時，通常會分配一個很大的線程pool（默認為16key），這個池按照空閑時間排序，所以只有當有一個大于池中的一個或者池為空的時候，最新的key只會進入到這個池中。
同時，一個新的redis-cli模式去測量LRU算法也增加了(看這個-lru-test選項)。
還有另外一個方式去檢驗LRU算法的好壞，通過一個冪等訪問模式。這個工具通常校驗用一個不同的測試，新算法工作工作效果好于真實世界負載。它也同樣使用流水線和每秒打印訪問日志，因此可以被使用不用為了基準不同的思想，至少可以校驗和觀察明顯的速度回歸。
規則三、最少使用原則（LFU算法）
一切源于一個開放性問題：但你有多個redis 3.2數據庫時，而淘汰算法只能在本機選擇。因此，假如你全部空閑小的key都是DB0號機器，空閑時間長的key都是1號機器，redis每臺機器都會淘汰各自的key。一個更好的選擇當然是先淘汰DB1，最后再淘汰DB0。
當redis被當作緩存使用時很少有情況被分成不同的db上，這不是一個好的處理方式。然而這也是我為什么我再一次修改淘汰代碼的原因。最終，我能夠修改緩存池包括數據庫id，使用單緩存池為多個db，代替多緩存池。這種實現很麻煩，但是通過優化和修改代碼，最終它比普通實現要快到20%。
然而這時候，我對這個redis緩存淘汰算法的好奇心又被點燃。我想要提升它。我花費了幾天想要提高LRU算法實現：或許可以使用更大的緩存池？通過歷史時間選擇最合適被淘汰的key？
經過一段時間，通過優化我的工具，我理解到：LRU算法受限于數據庫中的數據樣本，有時可能相反的場景效果非常好，因此要想提高非常非常難。實際上，能通過展示不同算法的圖片上看這有點非常明顯：每個周期10個keys幾乎和理論的LRU算法表現一致。
當原始算法很難提高時，我開始測試新的算法。 如果我們倒回到博客開始，我們說過LRU實際上有點嚴格。哪些key需要我們真正想要保留：將來有最大可能被訪問，最頻繁被訪問，而不是最近被訪問的key。
淘汰最少被訪問的key算法成為：LFU（Least Frequently Used），將來要被淘汰騰出新空間給新key。
理論上LFU的思想相當簡單，只需要給每個key加一個訪問計數器。每次訪問就自增1，所以也就很容易知道哪些key被訪問更頻繁。
當然，LFU也會帶起其他問題，不單單是針對redis，對于LFU實現：
1、不能使用“移除頂部元素”的方式，keys必須要根據訪問計數器進行排序。每訪問一次就得遍歷所有key找出訪問次數最少的key。
2、LFU不能僅僅是只增加每一訪問的計數器。正如我們所講的，訪問模式改變隨時變化，因此一個有高訪問次數的key，后面很可能沒有人繼續訪問它，因此我們的算法必須要適應超時的情況。
在redis中，第一個問題很好解決：我們可以在LRU的方式一樣：隨機在緩存池中選舉，淘汰其中某項。第二個問題redis還是存在，因此一般對于LFU的思想必須使用一些方式進行減少，或者定期把訪問計數器減半。
24位的LFU實現
LFU有它本身的實現，在redis中我們使用自己的24bit來記錄LRU。
為了實現LFU僅僅需要在每個對象額外新增24bit：
1、一部分用于保存訪問計數器；
2、足夠用于決定什么時候將計數器減半的信息；
我的解決方法是把24bit分成兩列：
16bits8bitslast decr timeLOG_C
16位記錄最后一次減半時間，那樣redis知道上一次減半時間，另外8bit作為訪問計數器。
你可能會想8位的計數器很快就會溢出，是的，相對于簡單計數器，我采用邏輯計數器。邏輯計數器的實現：
uint8_t LFULogIncr(uint8_t counter) { if (counter == 255) return 255; double r = (double)rand()/RAND_MAX; double baseval = counter - LFU_INIT_VAL; if (baseval < 0) baseval = 0; double p = 1.0/(baseval*server.lfu_log_factor+1); if (r < p) counter++; return counter; }
基本上計數器的較大者，更小的可能計數器會增加：上面的代碼計算p位于0~1之間，但計數器增長時會越來越小，位于0-1的隨機數r，只會但滿足r 你可以配置計數器增長的速率，如果使用默認配置，會發生： 100次訪問后，計數器=10； 1000次訪問是是18； 10萬次訪問是142； 100萬次訪問后達到255，并不在繼續增長； 下面，讓我們看看計數器如果進行衰減。16位的被儲存為unix時間戳保留到分鐘級別，redis會隨機掃描key填充到緩存池中，如果最后一個下降的時間大于N分鐘前（可配置化），如果計數器的值很大就減半，或者對于值小的就直接簡單減半。 這里又衍生出另外一個問題，就是新進來的key是需要有機會被保留的。由于LFU新增是得分都是0，非常容易被選舉替換掉。在redis中，開始默認值為5。這個初始值是根據增長數據和減半算法來估算的。模擬顯示得分小于5的key是首選。 代碼和性能 上面描述的算法已經提交到一個非穩定版的redis分支上。我最初的測試顯示：它在冪等模式下優于LRU算法，測試情況是每個key使用用相同數量的內存，然而真實世界的訪問可能會有很大不同。時間和空間都可能改變得很不同，所以我會很開心去學習觀察現實世界中LFU的性能如何，兩種方式在redis實現中對性能的改變。 因此，新增了一個OBJECT FREQ子命令，用于報告給定key的訪問計數器，不僅僅能有效提觀察一個計數器，而且還能調試LFU實現中的bug。 注意運行中切換LRU和LFU，剛開始會隨機淘汰一些key，隨著24bit不能匹配上，然而慢慢會適應。 還有幾種改進實現的可能。Ben Manes發給我這篇感興趣的文章，描述了一種叫TinyLRU算法。鏈接 這篇文章包含一個非常厲害的觀點：相比于記錄當前對象的訪問頻率，讓我們（概率性地）記錄全部對象的訪問頻率，看到了，這種方式我們甚至可以拒絕新key，同樣，我們相信這些key很可能得到很少的訪問，所以一點也不需要淘汰，如果淘汰一個key意味著降低命中/未命中率。 我的感覺這種技術雖然很感興趣GET/SET LFU緩存，但不適用與redis性質的數據服務器：用戶期望keys被創建后至少存在幾毫秒。拒絕key的創建似乎在redis上就是一種錯誤。 然而，redis保留了LFU信息，當一個key被覆蓋時，舉個例子： SET oldkey some_new_value 24位的LFU計數器會從老的key復制到新對象中。 新的redis淘汰算法不穩定版本還有以下幾個好消息： 1、跨DB策略。在過去的redis只是基于本地的選舉，現在修復為所有策略，不僅僅是LRU。 2、易變ttl策略。基于key預期淘汰存活時間，如今就像其他策略中的使用緩存池。 3、在緩存池中重用了sds對象，性能更好。 這篇博客比我預期要長，但是我希望它反映出一個見解：在創新和對于已經存在的事物實現上，一種解決方案去解決一個特定問題，一個基礎工具。由開發人員以正確的方式使用它。許多redis的用戶把redis作為一個緩存的解決方案，因此提高淘汰策略這一塊經常一次又一次被拿出來探討。 Redis 數據結構
版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。
版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。
相關文章