1、為什么Redis需要數(shù)據(jù)淘汰機(jī)制？
??眾所周知，Redis作為知名內(nèi)存型NOSQL，極大提升了程序訪問(wèn)數(shù)據(jù)的性能，高性能互聯(lián)網(wǎng)應(yīng)用里，幾乎都能看到Redis的身影。為了提升系統(tǒng)性能，Redis也從單機(jī)版、主從版發(fā)展到集群版、讀寫分離集群版等等，業(yè)界也有諸多著名三方擴(kuò)展庫(kù)（如Codis、Twemproxy）。
??阿里云的企業(yè)版Redis（Tair）的性能增強(qiáng)型集群版更是“[豪]無(wú)人性”，內(nèi)存容量高達(dá)4096 GB 內(nèi)存，支持約61440000 QPS。Tair混合存儲(chǔ)版更是使用內(nèi)存和磁盤同時(shí)存儲(chǔ)數(shù)據(jù)的集群版Redis實(shí)例，最高規(guī)格為1024 GB內(nèi)存8192 GB磁盤（16節(jié)點(diǎn)）?！驹?a target="_blank">https://help.aliyun.com/document_detail/26350.html? 阿里云規(guī)格查詢導(dǎo)航】
??既然Redis這么牛，那我們就使勁把數(shù)據(jù)往里面存儲(chǔ)嗎？
??32G DDR4 內(nèi)存條大約 900 元，1TB 的 SSD 硬盤大約 1000 元，價(jià)格實(shí)在懸殊。此外，即使數(shù)據(jù)量很大，但常用數(shù)據(jù)其實(shí)相對(duì)較少，全放內(nèi)存性價(jià)比太低?！岸嗽瓌t”在這里也是適用的。
??既然內(nèi)存空間有限，為避免內(nèi)存寫滿，就肯定需要進(jìn)行內(nèi)存數(shù)據(jù)淘汰了。
性價(jià)比；
內(nèi)存空間有限；
2、Redis的8種數(shù)據(jù)淘汰策略
??redis.conf中可配置Redis的最大內(nèi)存量 maxmemory，如果配置為0，在64位系統(tǒng)下則表示無(wú)最大內(nèi)存限制，在32位系統(tǒng)下則表示最大內(nèi)存限制為 3 GB。當(dāng)實(shí)際使用內(nèi)存 mem_used 達(dá)到設(shè)置的閥值 maxmemory 后，Redis將按照預(yù)設(shè)的淘汰策略進(jìn)行數(shù)據(jù)淘汰。
??Redis的8種數(shù)據(jù)淘汰策略，Redis 4.0開始，共有8種數(shù)據(jù)淘汰機(jī)制。
淘汰策略名稱策略含義
我們可以看到，除 noeviction 比較特殊外，allkeys 開頭的將從所有數(shù)據(jù)中進(jìn)行淘汰，volatile 開頭的將從設(shè)置了過(guò)期時(shí)間的數(shù)據(jù)中進(jìn)行淘汰。淘汰算法又核心分為 lru、random、ttl、lfu 幾種。
讓我們用一張圖來(lái)概括：
在了解Redis近似LRU算法前，我們先來(lái)了解下原生的LRU算法。
3.1、LRU算法
??LRU（Least Recently Used）最近最少使用。優(yōu)先淘汰最近未被使用的數(shù)據(jù)，其核心思想是“如果數(shù)據(jù)最近被訪問(wèn)過(guò)，那么將來(lái)被訪問(wèn)的幾率也更高”。
??LRU底層結(jié)構(gòu)是 hash 表 + 雙向鏈表。hash 表用于保證查詢操作的時(shí)間復(fù)雜度是O(1)，雙向鏈表用于保證節(jié)點(diǎn)插入、節(jié)點(diǎn)刪除的時(shí)間復(fù)雜度是O(1)。
??為什么是 雙向鏈表而不是單鏈表呢？單鏈表可以實(shí)現(xiàn)頭部插入新節(jié)點(diǎn)、尾部刪除舊節(jié)點(diǎn)的時(shí)間復(fù)雜度都是O(1)，但是對(duì)于中間節(jié)點(diǎn)時(shí)間復(fù)雜度是O(n)，因?yàn)閷?duì)于中間節(jié)點(diǎn)c，我們需要將該節(jié)點(diǎn)c移動(dòng)到頭部，此時(shí)只知道他的下一個(gè)節(jié)點(diǎn)，要知道其上一個(gè)節(jié)點(diǎn)需要遍歷整個(gè)鏈表，時(shí)間復(fù)雜度為O(n)。
LRU GET操作：如果節(jié)點(diǎn)存在，則將該節(jié)點(diǎn)移動(dòng)到鏈表頭部，并返回節(jié)點(diǎn)值；
LRU PUT操作：①節(jié)點(diǎn)不存在，則新增節(jié)點(diǎn)，并將該節(jié)點(diǎn)放到鏈表頭部；②節(jié)點(diǎn)存在，則更新節(jié)點(diǎn)，并將該節(jié)點(diǎn)放到鏈表頭部。
??LRU算法源碼可參考Leetcode：https://www.programcreek.com/2013/03/leetcode-lru-cache-java。
3.2、近似LRU算法原理（approximated LRU algorithm）
Redis為什么不使用原生LRU算法？
原生LRU算法需要 雙向鏈表 來(lái)管理數(shù)據(jù)，需要額外內(nèi)存；
數(shù)據(jù)訪問(wèn)時(shí)涉及數(shù)據(jù)移動(dòng)，有性能損耗；
Redis現(xiàn)有數(shù)據(jù)結(jié)構(gòu)需要改造；
以上內(nèi)容反過(guò)來(lái)就可以回答另一個(gè)問(wèn)題：Redis近似LRU算法的優(yōu)勢(shì)？
??在Redis中，Redis的key的底層結(jié)構(gòu)是 redisObject，redisObject 中 lru:LRU_BITS 字段用于記錄該key最近一次被訪問(wèn)時(shí)的Redis時(shí)鐘 server.lruclock（Redis在處理數(shù)據(jù)時(shí)，都會(huì)調(diào)用lookupKey方法用于更新該key的時(shí)鐘）。
??不太理解Redis時(shí)鐘的同學(xué)，可以將其先簡(jiǎn)單理解成時(shí)間戳（不影響我們理解近似LRU算法原理），server.lruclock 實(shí)際是一個(gè) 24bit 的整數(shù)，默認(rèn)是 Unix 時(shí)間戳對(duì) 2^24 取模的結(jié)果，其精度是毫秒。
server.lruclock 的值是如何更新的呢？
??Redis啟動(dòng)時(shí)，initServer 方法中通過(guò) aeCreateTimeEvent 將 serverCron 注冊(cè)為時(shí)間事件（serverCron 是Redis中最核心的定時(shí)處理函數(shù)）， serverCron 中 則會(huì) 觸發(fā) 更新Redis時(shí)鐘的方法 server.lruclock = getLRUClock() 。
當(dāng) mem_used > maxmemory 時(shí)，Redis通過(guò) freeMemoryIfNeeded 方法完成數(shù)據(jù)淘汰。LRU策略淘汰核心邏輯在 evictionPoolPopulate（淘汰數(shù)據(jù)集合填充） 方法。
Redis 近似LRU 淘汰策略邏輯：
首次淘汰：隨機(jī)抽樣選出【最多N個(gè)數(shù)據(jù)】放入【待淘汰數(shù)據(jù)池 evictionPoolEntry】；
數(shù)據(jù)量N：由 redis.conf 配置的 maxmemory-samples 決定，默認(rèn)值是5，配置為10將非常接近真實(shí)LRU效果，但是更消耗CPU；
samples：n.樣本；v.抽樣；
再次淘汰：隨機(jī)抽樣選出【最多N個(gè)數(shù)據(jù)】，只要數(shù)據(jù)比【待淘汰數(shù)據(jù)池 evictionPoolEntry】中的【任意一條】數(shù)據(jù)的 lru 小，則將該數(shù)據(jù)填充至 【待淘汰數(shù)據(jù)池】；
evictionPoolEntry 的容容量是 EVPOOL_SIZE = 16；
詳見 源碼 中 evictionPoolPopulate 方法的注釋；
執(zhí)行淘汰：挑選【待淘汰數(shù)據(jù)池】中 lru 最小的一條數(shù)據(jù)進(jìn)行淘汰；
Redis為了避免長(zhǎng)時(shí)間或一直找不到足夠的數(shù)據(jù)填充【待淘汰數(shù)據(jù)池】，代碼里（dictGetSomeKeys 方法）強(qiáng)制寫死了單次尋找數(shù)據(jù)的最大次數(shù)是 [maxsteps = count*10; ]，count 的值其實(shí)就是 maxmemory-samples。從這里我們也可以獲得另一個(gè)重要信息：?jiǎn)未潍@取的數(shù)據(jù)可能達(dá)不到 maxmemory-samples 個(gè)。此外，如果Redis數(shù)據(jù)量（所有數(shù)據(jù) 或 有過(guò)期時(shí)間 的數(shù)據(jù)）本身就比 maxmemory-samples 小，那么 count 值等于 Redis 中數(shù)據(jù)量個(gè)數(shù)。
LFU：Least Frequently Used，使用頻率最少的（最不經(jīng)常使用的）
優(yōu)先淘汰最近使用的少的數(shù)據(jù)，其核心思想是“如果一個(gè)數(shù)據(jù)在最近一段時(shí)間很少被訪問(wèn)到，那么將來(lái)被訪問(wèn)的可能性也很小”。
4.1、LFU與LRU的區(qū)別
??如果一條數(shù)據(jù)僅僅是突然被訪問(wèn)（有可能后續(xù)將不再訪問(wèn)），在 LRU 算法下，此數(shù)據(jù)將被定義為熱數(shù)據(jù)，最晚被淘汰。但實(shí)際生產(chǎn)環(huán)境下，我們很多時(shí)候需要計(jì)算的是一段時(shí)間下key的訪問(wèn)頻率，淘汰此時(shí)間段內(nèi)的冷數(shù)據(jù)。
??LFU 算法相比 LRU，在某些情況下可以提升 數(shù)據(jù)命中率，使用頻率更多的數(shù)據(jù)將更容易被保留。
對(duì)比項(xiàng)近似LRU算法LFU算法
最先過(guò)期的數(shù)據(jù)最近未被訪問(wèn)的最近一段時(shí)間訪問(wèn)的最少的
適用場(chǎng)景數(shù)據(jù)被連續(xù)訪問(wèn)場(chǎng)景數(shù)據(jù)在一段時(shí)間內(nèi)被連續(xù)訪問(wèn)
缺點(diǎn)新增key將占據(jù)緩存歷史訪問(wèn)次數(shù)超大的key淘汰速度取決于lfu-decay-time
4.2、LFU算法原理
??LFU 使用 Morris counter 概率計(jì)數(shù)器，僅使用幾比特就可以維護(hù) 訪問(wèn)頻率，Morris算法利用隨機(jī)算法來(lái)增加計(jì)數(shù)，在 Morris 算法中，計(jì)數(shù)不是真實(shí)的計(jì)數(shù)，它代表的是實(shí)際計(jì)數(shù)的量級(jí)。
LFU數(shù)據(jù)淘汰策略下，redisObject 的 lru:LRU_BITS 字段（24位）將分為2部分存儲(chǔ)：
Ldt：last decrement time，16位，精度分鐘，存儲(chǔ)上一次 LOG_C 更新的時(shí)間。
LOG_C：logarithmic counter，8位，最大255，存儲(chǔ)key被訪問(wèn)頻率。
注意：
LOG_C 存儲(chǔ)的是訪問(wèn)頻率，不是訪問(wèn)次數(shù)；
LOG_C訪問(wèn)頻率隨時(shí)間衰減；
為什么 LOG_C 要隨時(shí)間衰減？比如在秒殺場(chǎng)景下，熱key被訪問(wèn)次數(shù)很大，如果不隨時(shí)間衰減，此部分key將一直存放于內(nèi)存中。
新對(duì)象 的 LOG_C 值 為 LFU_INIT_VAL = 5，避免剛被創(chuàng)建即被淘汰。
LFU 的核心配置：
lfu-log-factor：counter 增長(zhǎng)對(duì)數(shù)因子，調(diào)整概率計(jì)數(shù)器 counter 的增長(zhǎng)速度，lfu-log-factor值越大 counter 增長(zhǎng)越慢；lfu-log-factor 默認(rèn)10。
lfu-decay-time：衰變時(shí)間周期，調(diào)整概率計(jì)數(shù)器的減少速度，單位分鐘，默認(rèn)1。
N 分鐘未訪問(wèn)，counter 將衰減 N/lfu-decay-time，直至衰減到0；
若配置為0：表示每次訪問(wèn)都將衰減 counter；
??counter 的區(qū)間是0-255， 其增長(zhǎng)與訪問(wèn)次數(shù)呈現(xiàn)對(duì)數(shù)增長(zhǎng)的趨勢(shì)，隨著訪問(wèn)次數(shù)越來(lái)越大，counter 增長(zhǎng)的越來(lái)越慢。Redis 官網(wǎng)提供的在 不同 factor 下，不同命中率 時(shí) counter 的值示例如下：
不同于 LRU 算法，LFU 算法下 Ldt 的值不是在key被訪問(wèn)時(shí)更新，而是在 內(nèi)存達(dá)到 maxmemory 時(shí)，觸發(fā)淘汰策略時(shí)更新。
Redis LFU 淘汰策略邏輯：
隨機(jī)抽樣選出N個(gè)數(shù)據(jù)放入【待淘汰數(shù)據(jù)池 evictionPoolEntry】；
再次淘汰：隨機(jī)抽樣選出【最多N個(gè)數(shù)據(jù)】，更新 Ldt 和 counter 的值，只要 counter 比【待淘汰數(shù)據(jù)池 evictionPoolEntry】中的【任意一條】數(shù)據(jù)的 counter 小，則將該數(shù)據(jù)填充至 【待淘汰數(shù)據(jù)池】；
evictionPoolEntry 的容容量是 EVPOOL_SIZE = 16；
執(zhí)行淘汰：挑選【待淘汰數(shù)據(jù)池】中 counter 最小的一條數(shù)據(jù)進(jìn)行淘汰；
??在講解近似LRU算法時(shí)，提及“Redis在處理數(shù)據(jù)時(shí)，都會(huì)調(diào)用lookupKey方法用于更新該key的時(shí)鐘”，回過(guò)頭來(lái)看，更為嚴(yán)謹(jǐn)?shù)恼f(shuō)法是“Redis在處理數(shù)據(jù)時(shí)，都會(huì)調(diào)用lookupKey方法，如果內(nèi)存淘汰策略是 LFU，則會(huì)調(diào)用 ‘updateLFU()’ 方法計(jì)算 LFU 模式下的 lru 并更新，否則將更新該key的時(shí)鐘 ‘val->lru = LRU_CLOCK()’”.
?詳細(xì)說(shuō)明可在源碼 evict.c 中 搜索 “LFU (Least Frequently Used) implementation”。
LFU 的核心配置：
lfu-log-factor：counter 增長(zhǎng)對(duì)數(shù)因子，調(diào)整概率計(jì)數(shù)器 counter 的增長(zhǎng)速度，lfu-log-factor值越大 counter 增長(zhǎng)越慢；lfu-log-factor 默認(rèn)10。
lfu-decay-time：衰變時(shí)間周期，調(diào)整概率計(jì)數(shù)器的減少速度，單位分鐘，默認(rèn)1。
N 分鐘未訪問(wèn)，counter 將衰減 N/lfu-decay-time，直至衰減到0；
若配置為0：表示每次訪問(wèn)都將衰減 counter；
??counter 的區(qū)間是0-255， 其增長(zhǎng)與訪問(wèn)次數(shù)呈現(xiàn)對(duì)數(shù)增長(zhǎng)的趨勢(shì)，隨著訪問(wèn)次數(shù)越來(lái)越大，counter 增長(zhǎng)的越來(lái)越慢。Redis 官網(wǎng)提供的在 不同 factor 下，不同命中率 時(shí) counter 的值示例如下：
不同于 LRU 算法，LFU 算法下 Ldt 的值不是在key被訪問(wèn)時(shí)更新，而是在 內(nèi)存達(dá)到 maxmemory 時(shí)，觸發(fā)淘汰策略時(shí)更新。
Redis LFU 淘汰策略邏輯：
隨機(jī)抽樣選出N個(gè)數(shù)據(jù)放入【待淘汰數(shù)據(jù)池 evictionPoolEntry】；
再次淘汰：隨機(jī)抽樣選出【最多N個(gè)數(shù)據(jù)】，更新 Ldt 和 counter 的值，只要 counter 比【待淘汰數(shù)據(jù)池 evictionPoolEntry】中的【任意一條】數(shù)據(jù)的 counter 小，則將該數(shù)據(jù)填充至 【待淘汰數(shù)據(jù)池】；
evictionPoolEntry 的容容量是 EVPOOL_SIZE = 16；
執(zhí)行淘汰：挑選【待淘汰數(shù)據(jù)池】中 counter 最小的一條數(shù)據(jù)進(jìn)行淘汰；
??在講解近似LRU算法時(shí)，提及“Redis在處理數(shù)據(jù)時(shí)，都會(huì)調(diào)用lookupKey方法用于更新該key的時(shí)鐘”，回過(guò)頭來(lái)看，更為嚴(yán)謹(jǐn)?shù)恼f(shuō)法是“Redis在處理數(shù)據(jù)時(shí)，都會(huì)調(diào)用lookupKey方法，如果內(nèi)存淘汰策略是 LFU，則會(huì)調(diào)用 ‘updateLFU()’ 方法計(jì)算 LFU 模式下的 lru 并更新，否則將更新該key的時(shí)鐘 ‘val->lru = LRU_CLOCK()’”.
5.1、為什么Redis要使用自己的時(shí)鐘？
獲取系統(tǒng)時(shí)間戳將調(diào)用系統(tǒng)底層提供的方法；
單線程的Redis對(duì)性能要求極高，從緩存中獲取時(shí)間戳將極大提升性能。
5.2、如何發(fā)現(xiàn)熱點(diǎn)key？
??object freq key 命令支持 獲取 key 的 counter，所以我們可以通過(guò) scan 遍歷所有key，再通過(guò) object freq 獲取counter。
??需要注意的是，執(zhí)行 object freq 的前提是 數(shù)據(jù)淘汰策略是 LFU。
Redis 4.0.3版本也提供了redis-cli的熱點(diǎn)key功能，執(zhí)行"./redis-cli --hotkeys"即可獲取熱點(diǎn)key。需要注意的是，hotkeys 本質(zhì)上是 scan + object freq，所以，如果數(shù)據(jù)量特別大的情況下，可能耗時(shí)較長(zhǎng)。
