浅谈Redis 中的 LRU/LFU
发布网友
发布时间：2024-10-24 11:12
共1个回答
热心网友
时间：2024-11-07 03:23
欢迎关注我的公众号：窗有老梅
本文基于 antirez.com/news/109，讨论了 Redis 中 LRU/LFU 算法实现的基本问题。
理论上最优的 cache 淘汰算法应该是：总是淘汰未来被访问到的可能性最低的 key。但实际工程中实现起来有亿点点难，因为需要有预测未来的能力。
学过操作系统的同学应该都知道 LRU 算法，其是一个工程应用中的经典 cache 淘汰算法，基于最近一次被访问到的时间来搞，其本质上理论最优算法的近似。
LFU 差不多，基于被访问到的频度来搞。
理论上最优的 cache 淘汰算法应该是：总是淘汰未来被访问到的可能性最低的 key。但实际工程中实现起来有亿点点难，因为需要有预测未来的能力。
学过操作系统的同学应该都知道 LRU 算法，其是一个工程应用中的经典 cache 淘汰算法，基于最近一次被访问到的时间来搞，其本质上理论最优算法的近似。
LFU 差不多，基于被访问到的频度来搞。
所基于的思想：最近（recently）频繁被访问到的 key，未来很可能会被再次访问到。其本质就是用历史预测未来。
所基于的理论：访问模式（pattern）通常不会发生突变，以及程序的局部性原理等，所以 LRU 实际工程中往往很有效。
但获取“最近频繁被访问到”这个信息并不是那么简单的，LRU（Least Recently Used）实际上是更简化了一步，或者说是在近似实现“最近频繁被访问到”：LRU 只记录 key 最近一次被访问到的时间。其底层思想是：更高频度被访问到的 keys，其被访问到的时间间隔也大概率会更小。
LRU 只看一个 key 最近一次被访问到的时间，这在工程上会导致一些问题。
假设有如下访问模式（“~”表示一秒，“|”表示当前时刻）：
很明显 B 和 A 是相对“最近频繁被访问到”的。
但虽然 D 的访问频度最低，但其“最近一次被访问到”的时间是最近的，如果按 LRU 算法来搞，D 是最不应该被淘汰的，但根据“最近频繁被访问到”的原则来看，D 其实是最应该被淘汰的。
但问题还是不大，从长久范围来看，LRU 还是可以近似“最近频繁被访问到”的原则。
LRU 的核心就是将 keys 按照“最近一次被访问”的时间排序，所以关键就是高效的排序及排序管理。
你可能会想到二项堆或者平衡树（红黑树等），但实际上不需要那么复杂：压根都不需要真的记录访问时间，用单链表把所有 keys 串起来，每当一个 key 被访问到，就将其提到链表的最前端。
淘汰 key 的时候直接选链表的最尾端（最久没被访问到的 key）即可。
Redis 中 LRU 实现的核心问题是：redis 中的 Redis Object 数据结构只有 24 个 bit 可以用来做文章，按照文章中的意思，该数据结构应该是不可以乱动的，无法在里面愉快地添加链表（指针）等字段，所以也就不可以施展上一节中的“提到链表头部操作”。
作者用此 24 bit 来存放 key 最近一次被访问到的时间（秒为单位，最大可以存 0xFFFFFF 秒，也就是 194 天，足够了），既然没法愉快地使用“提到链表的头部操作”，那如何来实现“极速”“待淘汰 key 选择”算法呢？
作者采用了近似算法：每次随机采样 N 个 key，挑选出其中最差（最近一次访问时间最久远）的 key 进入候选池（相当于链表实现下最差的 key 自动进入链表的尾端），需要淘汰的时候从候选池中选一个即可。
作者提出，N 取 5 可以达到算法性能和速度的最佳平衡。
每次随机采样 N 个 key，然后只取其中最差的 key。看了这么多信息，却只做了这么一个简单的操作，有点暴殄天物，浪费了很多有用的信息，比如说，没准这 N 个 key 里面，其实最佳的候选 key 并不止一个，是吧？
那怎么把这些浪费掉的信息回收再利用呢？
作者提出了一个小的改进：用一个池子（这个池子不用太大，默认大小是 16）维护合适的候选 key 们，池子里的 key 按“最近一次被访问到”的时间排序，每一轮对 N 个 key 进行采样，只有当这 N 个 key 中最差的 key 的访问时间，比池子里最近一次被访问时间最近的 key 更久远时，才可以进入这个池子。
说白了，就是充分地利用“key 被访问到的时间”这一信息。
作者引入 LFU 的原因，是 LRU 算法所基于的思想已经没有更高的提升空间。在 redis 的 LRU 实现中，算法准确度主要受限于“随机采样 N 个 key”中的 N，但是 N 取 10 时，准确度基本等同于理论上的 LRU 实现，已无提升空间。
LFU，Least Frequently Used，淘汰访问频度最低的 key。
理论上 LFU 实现也很简单，记录 key 的访问频度，并按照频度排序即可。
但其实没那么简单：
第一个问题本质就是算法复杂度的问题，但实际工程中这也不算是真正的问题，因为可以采用和 LRU 一样的手法：随机采样。
但第二个问题仍然不好搞，作者主要就是阐述解决这个问题的方法。
作者对这 24 个 bit 做了功能划分，16 bit 用来记录 key 上一次做“减少（decrement）”操作的时间戳（分钟为单位），另外 8 bit 用来记录访问频度。
正常情况下，一个 8 bit 的计数器（255）很快就溢出了，为了避免这个情况，作者做了点小的设计，下面是对频度计数做增加的算法：
作者称其为“对数计数”（自己脑补一下对数函数的曲线就明白了）。这里我不是很明白的是，为啥要基于概率来实现，直接计算对数也不是很麻烦。
采用了一个比较拍脑袋的算法：如果“last decrement time”超过 N 分钟（N 可配置），则频度计数直接折半，否则减减（--）。这么干是为了更好地区分很少被访问到的 key，因为计数的分辨率很低（只有 8 个 bit）。
对于新加入的 key 来说，其频度此时很低（0），对于 LFU 来说，这种 key 是非常好的淘汰对象。但显然这是不太合理的，规避新加入 key 被淘汰的手法就是，key 新加入时频度计数为一个非零值（5），保证新加入的 key 能在最近的几次淘汰中能存活下来。
通过模拟可以看出，频度计数低于 5（很久没有被访问到的）的是非常适合用来淘汰的。
LRU 的方*原理是“time locality”，LFU 的方*原理是“偏态分布”。
