1、為什么Redis需要數(shù)據(jù)淘汰機(jī)制柠贤？
??眾所周知拳话，Redis作為知名內(nèi)存型NOSQL，極大提升了程序訪問數(shù)據(jù)的性能种吸，高性能互聯(lián)網(wǎng)應(yīng)用里弃衍，幾乎都能看到Redis的身影。為了提升系統(tǒng)性能坚俗，Redis也從單機(jī)版镜盯、主從版發(fā)展到集群版、讀寫分離集群版等等猖败，業(yè)界也有諸多著名三方擴(kuò)展庫（如Codis速缆、Twemproxy）。
??阿里云的企業(yè)版Redis（Tair）的性能增強(qiáng)型集群版更是“[豪]無人性”恩闻，內(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)）破停。【援引：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à)比太低蚯撩。“二八原則”在這里也是適用的烛占。
??既然內(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)下則表示無最大內(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è)置了過期時(shí)間的數(shù)據(jù)中進(jìn)行淘汰呻袭。淘汰算法又核心分為 lru眨八、random、ttl左电、lfu 幾種廉侧。
讓我們用一張圖來概括：
在了解Redis近似LRU算法前，我們先來了解下原生的LRU算法篓足。
3.1段誊、LRU算法
??LRU（Least Recently Used）最近最少使用。優(yōu)先淘汰最近未被使用的數(shù)據(jù)纷纫，其核心思想是“如果數(shù)據(jù)最近被訪問過枕扫，那么將來被訪問的幾率也更高”陪腌。
??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算法需要 雙向鏈表 來管理數(shù)據(jù)辰斋，需要額外內(nèi)存；
數(shù)據(jù)訪問時(shí)涉及數(shù)據(jù)移動(dòng)瘸味，有性能損耗宫仗；
Redis現(xiàn)有數(shù)據(jù)結(jié)構(gòu)需要改造；
以上內(nèi)容反過來就可以回答另一個(gè)問題：Redis近似LRU算法的優(yōu)勢旁仿？
??在Redis中藕夫，Redis的key的底層結(jié)構(gòu)是 redisObject，redisObject 中 lru:LRU_BITS 字段用于記錄該key最近一次被訪問時(shí)的Redis時(shí)鐘 server.lruclock（Redis在處理數(shù)據(jù)時(shí)枯冈，都會(huì)調(diào)用lookupKey方法用于更新該key的時(shí)鐘）毅贮。
??不太理解Redis時(shí)鐘的同學(xué)，可以將其先簡單理解成時(shí)間戳（不影響我們理解近似LRU算法原理）尘奏，server.lruclock 實(shí)際是一個(gè) 24bit 的整數(shù)滩褥，默認(rèn)是 Unix 時(shí)間戳對(duì) 2^24 取模的結(jié)果，其精度是毫秒炫加。
server.lruclock 的值是如何更新的呢瑰煎？
??Redis啟動(dòng)時(shí)铺然，initServer 方法中通過 aeCreateTimeEvent 將 serverCron 注冊為時(shí)間事件（serverCron 是Redis中最核心的定時(shí)處理函數(shù)）， serverCron 中 則會(huì) 觸發(fā) 更新Redis時(shí)鐘的方法 server.lruclock = getLRUClock() 酒甸。
當(dāng) mem_used > maxmemory 時(shí)魄健，Redis通過 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為了避免長時(shí)間或一直找不到足夠的數(shù)據(jù)填充【待淘汰數(shù)據(jù)池】，代碼里（dictGetSomeKeys 方法）強(qiáng)制寫死了單次尋找數(shù)據(jù)的最大次數(shù)是 [maxsteps = count*10; ]殖属，count 的值其實(shí)就是 maxmemory-samples姐叁。從這里我們也可以獲得另一個(gè)重要信息：單次獲取的數(shù)據(jù)可能達(dá)不到 maxmemory-samples 個(gè)。此外洗显，如果Redis數(shù)據(jù)量（所有數(shù)據(jù) 或 有過期時(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í)間很少被訪問到，那么將來被訪問的可能性也很小”玄组。
4.1滔驾、LFU與LRU的區(qū)別
??如果一條數(shù)據(jù)僅僅是突然被訪問（有可能后續(xù)將不再訪問），在 LRU 算法下俄讹，此數(shù)據(jù)將被定義為熱數(shù)據(jù)哆致，最晚被淘汰。但實(shí)際生產(chǎn)環(huán)境下患膛，我們很多時(shí)候需要計(jì)算的是一段時(shí)間下key的訪問頻率摊阀，淘汰此時(shí)間段內(nèi)的冷數(shù)據(jù)。
??LFU 算法相比 LRU，在某些情況下可以提升 數(shù)據(jù)命中率胞此，使用頻率更多的數(shù)據(jù)將更容易被保留臣咖。
對(duì)比項(xiàng)近似LRU算法LFU算法
最先過期的數(shù)據(jù)最近未被訪問的最近一段時(shí)間訪問的最少的
適用場景數(shù)據(jù)被連續(xù)訪問場景數(shù)據(jù)在一段時(shí)間內(nèi)被連續(xù)訪問
缺點(diǎn)新增key將占據(jù)緩存歷史訪問次數(shù)超大的key淘汰速度取決于lfu-decay-time
4.2、LFU算法原理
??LFU 使用 Morris counter 概率計(jì)數(shù)器豌鹤，僅使用幾比特就可以維護(hù) 訪問頻率亡哄，Morris算法利用隨機(jī)算法來增加計(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被訪問頻率酝豪。
注意：
LOG_C 存儲(chǔ)的是訪問頻率涛碑，不是訪問次數(shù)；
LOG_C訪問頻率隨時(shí)間衰減孵淘；
為什么 LOG_C 要隨時(shí)間衰減蒲障？比如在秒殺場景下，熱key被訪問次數(shù)很大瘫证，如果不隨時(shí)間衰減揉阎，此部分key將一直存放于內(nèi)存中。
新對(duì)象 的 LOG_C 值 為 LFU_INIT_VAL = 5背捌，避免剛被創(chuàng)建即被淘汰毙籽。
LFU 的核心配置：
lfu-log-factor：counter 增長對(duì)數(shù)因子，調(diào)整概率計(jì)數(shù)器 counter 的增長速度毡庆，lfu-log-factor值越大 counter 增長越慢惧财；lfu-log-factor 默認(rèn)10。
lfu-decay-time：衰變時(shí)間周期扭仁，調(diào)整概率計(jì)數(shù)器的減少速度垮衷，單位分鐘，默認(rèn)1乖坠。
N 分鐘未訪問搀突，counter 將衰減 N/lfu-decay-time，直至衰減到0熊泵；
若配置為0：表示每次訪問都將衰減 counter仰迁；
??counter 的區(qū)間是0-255甸昏， 其增長與訪問次數(shù)呈現(xiàn)對(duì)數(shù)增長的趨勢，隨著訪問次數(shù)越來越大徐许，counter 增長的越來越慢施蜜。Redis 官網(wǎng)提供的在 不同 factor 下，不同命中率 時(shí) counter 的值示例如下：
不同于 LRU 算法雌隅，LFU 算法下 Ldt 的值不是在key被訪問時(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í)鐘”柬唯，回過頭來看，更為嚴(yán)謹(jǐn)?shù)恼f法是“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ì)說明可在源碼 evict.c 中 搜索 “LFU (Least Frequently Used) implementation”恕酸。
LFU 的核心配置：
lfu-log-factor：counter 增長對(duì)數(shù)因子，調(diào)整概率計(jì)數(shù)器 counter 的增長速度袱箱，lfu-log-factor值越大 counter 增長越慢；lfu-log-factor 默認(rèn)10发笔。
lfu-decay-time：衰變時(shí)間周期，調(diào)整概率計(jì)數(shù)器的減少速度了讨，單位分鐘，默認(rèn)1前计。
N 分鐘未訪問胞谭，counter 將衰減 N/lfu-decay-time，直至衰減到0男杈；
若配置為0：表示每次訪問都將衰減 counter丈屹；
??counter 的區(qū)間是0-255， 其增長與訪問次數(shù)呈現(xiàn)對(duì)數(shù)增長的趨勢伶棒，隨著訪問次數(shù)越來越大旺垒，counter 增長的越來越慢。Redis 官網(wǎng)提供的在 不同 factor 下苞冯，不同命中率 時(shí) counter 的值示例如下：
不同于 LRU 算法袖牙，LFU 算法下 Ldt 的值不是在key被訪問時(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í)鐘”梳玫，回過頭來看爹梁，更為嚴(yán)謹(jǐn)?shù)恼f法是“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，所以我們可以通過 scan 遍歷所有key唠椭，再通過 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í)較長云石。
