Redis的数据过期策略和内存淘汰策略经常会弄混，所以我将在这边文章中对它们进行详细地阐述，相信看完之后读者盆友应该可以对这两种策略的原理如数家珍了。
数据过期策略
指的是Redis如何处理已过期的kv。
实际上Redis采用的策略是Lazy+Cron，二者可以互补：
- Lazy 惰性删除：key被访问时，如果发现已过期则立刻删除 => 弥补了Cron定期执行导致一些key过期后仍能查到的问题
- Cron 定期删除：定期遍历过期字典Expire（key=key，value=过期时间），删除过期key => 避免因为Lazy，某些key没有被访问导致该key一直不删除
注意：从服务器不操作过期键，以主服务器为准。主服务器删除某个过期键后，发送DEL命令给从服务器同步 => 保证了主从数据强一致
内存淘汰策略
指的是Redis中数据量超过储量时自动淘汰部分数据的策略。
如何查看和修改：在redis的配置文件修改或者用config get/set命令查看和修改。
可选策略-共8种：volatile=只处理有过期时间的keys，allkeys=处理全部的keys
- LRU、LFU、Random（随机）策略：volatile, allkeys
- TTL-Volatile：淘汰最接近过期的数据
- No-Enviction：不淘汰数据，满了之后写入直接报错
LRU策略的实现方式和演进：
标准LRU
逻辑：使用数据结构 —— 哈希表+双向链表
- 哈希表key=key, value=双向链表中的节点指针；便于O(1)时间复杂度读取和在双向链表中移动操作
- 双向链表：新get/set的数据放到双向链表的头部，淘汰时从尾部取数据
问题 —— 内存开销较大：所以OS和Redis中都采用是近似实现而非标准实现
- 每个value都要额外储存prev和next两个指针
- 额外使用哈希表存储节点指针
- 双向链表和哈希表中要维护全量的数据"
操作系统 - 页面置换策略中的LRU
逻辑：每个页面维护一个8位的访问记录
- 每个页面维护一个访问记录，在一个时钟周期内该页面被访问过这一位就置为1
- 10010000 代表最近的第1，第4个时钟周期内被访问过 => 越近的访问权重越大
- 换出页面时选择访问记录数值最小的即可
问题：
- 无法区分同一时钟周期内访问的先后关系
- 只有8位的记录，较早的访问记录失效
Redis 2.8版本 LRU
逻辑：每个key用24位记录一个lru字段（秒级别时间戳，最多可以存储194天）
- 读写key操作时更新lru
- 需要淘汰时随机选取5个元素，取lru最小的淘汰（最久未被访问）
问题：因为是随机选取，可能选取出来的数据是较新的 => 增加随机选取的数量可以缓解这一问题
Redis 3.0版本 LRU
逻辑：在2.8版本的基础上，增加了一个大小的为16个pool，维护其中lru的最大值和最小值
- 需要淘汰时随机选取10个元素，尝试插入pool中
- 比pool中最大值要大的（相对更新），忽略
- 比pool中最大值要小的，将pool中最大值推出，将其插入，然后选择pool中最小值进行淘汰
虽然仍是随机选取，但是增加了pool的缓冲区，比2.8版本的LRU更加稳定了，基本上可以较为准确的淘汰 —— 详细测试数据可以参考（Redis的缓存淘汰策略LRU与LFU）
Redis 4.0版本 LFU引入
Redis 4.0版本增加了LFU的策略，LRU策略的核心是按照访问时间先后排序，LFU在此基础上还增加了访问次数的维度 => 之前访问较多的，将来被访问的可能性也更大
- 标准LFU：
- 数据结构：哈希表（key->节点指针）+哈希表（key=frequency, value=当前访问频率的链表，最新的在链表头）
- 和标准LRU一样，因为数据结构内存开销较大，所以Redis LFU采用的也是近似实现
- Redis LFU：用8位记录一个counter（最大255）
- 新加入数据的counter初始值为5，为了避免新数据counter过小一开始就被淘汰
- counter每分钟自动衰减1
- 每次访问时，当随机数<1/(counter+1)时候，counter+1 => 使得counter越大时，递增就越难
- 淘汰数据时和LRU一致，也是随机选择10个数据，然后插入一个大小为16的pool，从pool中选择counter最小的淘汰
参考：
