1、为什么Redis需要数据淘汰机制？
众所周知，Redis作为知名内存型NOSQL，极大提升了程序访问数据的性能，高性能互联网应用里，几乎都能看到Redis的身影。为了提升系统性能，Redis也从单机版、主从版发展到集群版、读写分离集群版等等，业界也有诸多著名三方扩展库（如Codis、Twemproxy）。
阿里云的企业版Redis（Tair）的性能增强型集群版更是“[豪]无人性”，内存容量高达4096 GB 内存，支持约61440000 QPS。Tair混合存储版更是使用内存和磁盘同时存储数据的集群版Redis实例，最高规格为1024 GB内存8192 GB磁盘（16节点）。【援引：https://help.aliyun.com/document_detail/26350.html 阿里云规格查询导航】
既然Redis这么牛，那我们就使劲把数据往里面存储吗？
32G DDR4 内存条大约 900 元，1TB 的 SSD 硬盘大约 1000 元，价格实在悬殊。此外，即使数据量很大，但常用数据其实相对较少，全放内存性价比太低。“二八原则”在这里也是适用的。
既然内存空间有限，为避免内存写满，就肯定需要进行内存数据淘汰了。
性价比；
内存空间有限；
2、Redis的8种数据淘汰策略
redis.conf中可配置Redis的最大内存量 maxmemory，如果配置为0，在64位系统下则表示无最大内存限制，在32位系统下则表示最大内存限制为 3 GB。当实际使用内存 mem_used 达到设置的阀值 maxmemory 后，Redis将按照预设的淘汰策略进行数据淘汰。
Redis的8种数据淘汰策略，Redis 4.0开始，共有8种数据淘汰机制。
淘汰策略名称策略含义
我们可以看到，除 noeviction 比较特殊外，allkeys 开头的将从所有数据中进行淘汰，volatile 开头的将从设置了过期时间的数据中进行淘汰。淘汰算法又核心分为 lru、random、ttl、lfu 几种。
让我们用一张图来概括：
在了解Redis近似LRU算法前，我们先来了解下原生的LRU算法。
3.1、LRU算法
LRU（Least Recently Used）最近最少使用。优先淘汰最近未被使用的数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。
LRU底层结构是 hash 表 + 双向链表。hash 表用于保证查询操作的时间复杂度是O(1)，双向链表用于保证节点插入、节点删除的时间复杂度是O(1)。
为什么是 双向链表而不是单链表呢？单链表可以实现头部插入新节点、尾部删除旧节点的时间复杂度都是O(1)，但是对于中间节点时间复杂度是O(n)，因为对于中间节点c，我们需要将该节点c移动到头部，此时只知道他的下一个节点，要知道其上一个节点需要遍历整个链表，时间复杂度为O(n)。
LRU GET操作：如果节点存在，则将该节点移动到链表头部，并返回节点值；
LRU PUT操作：①节点不存在，则新增节点，并将该节点放到链表头部；②节点存在，则更新节点，并将该节点放到链表头部。
LRU算法源码可参考Leetcode：https://www.programcreek.com/2013/03/leetcode-lru-cache-java。
3.2、近似LRU算法原理（approximated LRU algorithm）
Redis为什么不使用原生LRU算法？
原生LRU算法需要 双向链表 来管理数据，需要额外内存；
数据访问时涉及数据移动，有性能损耗；
Redis现有数据结构需要改造；
以上内容反过来就可以回答另一个问题：Redis近似LRU算法的优势？
在Redis中，Redis的key的底层结构是 redisObject，redisObject 中 lru:LRU_BITS 字段用于记录该key最近一次被访问时的Redis时钟 server.lruclock（Redis在处理数据时，都会调用lookupKey方法用于更新该key的时钟）。
不太理解Redis时钟的同学，可以将其先简单理解成时间戳（不影响我们理解近似LRU算法原理），server.lruclock 实际是一个 24bit 的整数，默认是 Unix 时间戳对 2^24 取模的结果，其精度是毫秒。
server.lruclock 的值是如何更新的呢？
Redis启动时，initServer 方法中通过 aeCreateTimeEvent 将 serverCron 注册为时间事件（serverCron 是Redis中最核心的定时处理函数）， serverCron 中 则会 触发 更新Redis时钟的方法 server.lruclock = getLRUClock() 。
当 mem_used > maxmemory 时，Redis通过 freeMemoryIfNeeded 方法完成数据淘汰。LRU策略淘汰核心逻辑在 evictionPoolPopulate（淘汰数据集合填充） 方法。
Redis 近似LRU 淘汰策略逻辑：
首次淘汰：随机抽样选出【最多N个数据】放入【待淘汰数据池 evictionPoolEntry】；
数据量N：由 redis.conf 配置的 maxmemory-samples 决定，默认值是5，配置为10将非常接近真实LRU效果，但是更消耗CPU；
samples：n.样本；v.抽样；
再次淘汰：随机抽样选出【最多N个数据】，只要数据比【待淘汰数据池 evictionPoolEntry】中的【任意一条】数据的 lru 小，则将该数据填充至 【待淘汰数据池】；
evictionPoolEntry 的容容量是 EVPOOL_SIZE = 16；
详见 源码 中 evictionPoolPopulate 方法的注释；
执行淘汰：挑选【待淘汰数据池】中 lru 最小的一条数据进行淘汰；
Redis为了避免长时间或一直找不到足够的数据填充【待淘汰数据池】，代码里（dictGetSomeKeys 方法）强制写死了单次寻找数据的最大次数是 [maxsteps = count*10; ]，count 的值其实就是 maxmemory-samples。从这里我们也可以获得另一个重要信息：单次获取的数据可能达不到 maxmemory-samples 个。此外，如果Redis数据量（所有数据 或 有过期时间 的数据）本身就比 maxmemory-samples 小，那么 count 值等于 Redis 中数据量个数。
LFU：Least Frequently Used，使用频率最少的（最不经常使用的）
优先淘汰最近使用的少的数据，其核心思想是“如果一个数据在最近一段时间很少被访问到，那么将来被访问的可能性也很小”。
4.1、LFU与LRU的区别
如果一条数据仅仅是突然被访问（有可能后续将不再访问），在 LRU 算法下，此数据将被定义为热数据，最晚被淘汰。但实际生产环境下，我们很多时候需要计算的是一段时间下key的访问频率，淘汰此时间段内的冷数据。
LFU 算法相比 LRU，在某些情况下可以提升 数据命中率，使用频率更多的数据将更容易被保留。
对比项近似LRU算法LFU算法
最先过期的数据最近未被访问的最近一段时间访问的最少的
适用场景数据被连续访问场景数据在一段时间内被连续访问
缺点新增key将占据缓存历史访问次数超大的key淘汰速度取决于lfu-decay-time
4.2、LFU算法原理
LFU 使用 Morris counter 概率计数器，仅使用几比特就可以维护 访问频率，Morris算法利用随机算法来增加计数，在 Morris 算法中，计数不是真实的计数，它代表的是实际计数的量级。
LFU数据淘汰策略下，redisObject 的 lru:LRU_BITS 字段（24位）将分为2部分存储：
Ldt：last decrement time，16位，精度分钟，存储上一次 LOG_C 更新的时间。
LOG_C：logarithmic counter，8位，最大255，存储key被访问频率。
注意：
LOG_C 存储的是访问频率，不是访问次数；
LOG_C访问频率随时间衰减；
为什么 LOG_C 要随时间衰减？比如在秒杀场景下，热key被访问次数很大，如果不随时间衰减，此部分key将一直存放于内存中。
新对象 的 LOG_C 值 为 LFU_INIT_VAL = 5，避免刚被创建即被淘汰。
LFU 的核心配置：
lfu-log-factor：counter 增长对数因子，调整概率计数器 counter 的增长速度，lfu-log-factor值越大 counter 增长越慢；lfu-log-factor 默认10。
lfu-decay-time：衰变时间周期，调整概率计数器的减少速度，单位分钟，默认1。
N 分钟未访问，counter 将衰减 N/lfu-decay-time，直至衰减到0；
若配置为0：表示每次访问都将衰减 counter；
counter 的区间是0-255， 其增长与访问次数呈现对数增长的趋势，随着访问次数越来越大，counter 增长的越来越慢。Redis 官网提供的在 不同 factor 下，不同命中率 时 counter 的值示例如下：
不同于 LRU 算法，LFU 算法下 Ldt 的值不是在key被访问时更新，而是在 内存达到 maxmemory 时，触发淘汰策略时更新。
Redis LFU 淘汰策略逻辑：
随机抽样选出N个数据放入【待淘汰数据池 evictionPoolEntry】；
再次淘汰：随机抽样选出【最多N个数据】，更新 Ldt 和 counter 的值，只要 counter 比【待淘汰数据池 evictionPoolEntry】中的【任意一条】数据的 counter 小，则将该数据填充至 【待淘汰数据池】；
evictionPoolEntry 的容容量是 EVPOOL_SIZE = 16；
执行淘汰：挑选【待淘汰数据池】中 counter 最小的一条数据进行淘汰；
在讲解近似LRU算法时，提及“Redis在处理数据时，都会调用lookupKey方法用于更新该key的时钟”，回过头来看，更为严谨的说法是“Redis在处理数据时，都会调用lookupKey方法，如果内存淘汰策略是 LFU，则会调用 ‘updateLFU()’ 方法计算 LFU 模式下的 lru 并更新，否则将更新该key的时钟 ‘val->lru = LRU_CLOCK()’”.
详细说明可在源码 evict.c 中 搜索 “LFU (Least Frequently Used) implementation”。
LFU 的核心配置：
lfu-log-factor：counter 增长对数因子，调整概率计数器 counter 的增长速度，lfu-log-factor值越大 counter 增长越慢；lfu-log-factor 默认10。
lfu-decay-time：衰变时间周期，调整概率计数器的减少速度，单位分钟，默认1。
N 分钟未访问，counter 将衰减 N/lfu-decay-time，直至衰减到0；
若配置为0：表示每次访问都将衰减 counter；
counter 的区间是0-255， 其增长与访问次数呈现对数增长的趋势，随着访问次数越来越大，counter 增长的越来越慢。Redis 官网提供的在 不同 factor 下，不同命中率 时 counter 的值示例如下：
不同于 LRU 算法，LFU 算法下 Ldt 的值不是在key被访问时更新，而是在 内存达到 maxmemory 时，触发淘汰策略时更新。
Redis LFU 淘汰策略逻辑：
随机抽样选出N个数据放入【待淘汰数据池 evictionPoolEntry】；
再次淘汰：随机抽样选出【最多N个数据】，更新 Ldt 和 counter 的值，只要 counter 比【待淘汰数据池 evictionPoolEntry】中的【任意一条】数据的 counter 小，则将该数据填充至 【待淘汰数据池】；
evictionPoolEntry 的容容量是 EVPOOL_SIZE = 16；
执行淘汰：挑选【待淘汰数据池】中 counter 最小的一条数据进行淘汰；
在讲解近似LRU算法时，提及“Redis在处理数据时，都会调用lookupKey方法用于更新该key的时钟”，回过头来看，更为严谨的说法是“Redis在处理数据时，都会调用lookupKey方法，如果内存淘汰策略是 LFU，则会调用 ‘updateLFU()’ 方法计算 LFU 模式下的 lru 并更新，否则将更新该key的时钟 ‘val->lru = LRU_CLOCK()’”.
5.1、为什么Redis要使用自己的时钟？
获取系统时间戳将调用系统底层提供的方法；
单线程的Redis对性能要求极高，从缓存中获取时间戳将极大提升性能。
5.2、如何发现热点key？
object freq key 命令支持 获取 key 的 counter，所以我们可以通过 scan 遍历所有key，再通过 object freq 获取counter。
需要注意的是，执行 object freq 的前提是 数据淘汰策略是 LFU。
Redis 4.0.3版本也提供了redis-cli的热点key功能，执行"./redis-cli --hotkeys"即可获取热点key。需要注意的是，hotkeys 本质上是 scan + object freq，所以，如果数据量特别大的情况下，可能耗时较长。
