Redis 内幕 - 采样的 LRU 实现

Question

有人知道基于 Redis LRU 的驱逐/删除的内部结构吗。

Redis 如何确保首先删除较旧(较少使用)的键(如果我们没有 volatile 键并且我们没有设置 TTL 过期时间)？

我确定 Redis 有一个配置参数“maxmemory-samples”，它控制用于删除键的样本大小 - 所以如果你将样本大小设置为 10，那么它会对 10 个键进行采样并从中删除最旧的这些。

我不知道它是否完全随机地对这些 key 进行采样，或者它是否有某种机制允许它自动从“较旧/较少使用的一代”的等价物中进行采样？

Answer 1

这是我在 antirez.com/post/redis-as-LRU-cache.html 找到的- 使用“样本三”算法的全部意义在于节省内存。我认为这比精度更有值(value)，特别是因为这种随机算法很少被很好地理解。举个例子:与完美的 LRU 算法相比，仅使用三个对象进行采样将使 999 个数据集中的 666 个对象过期，错误率仅为 14%。而在剩余的 14% 中，几乎没有元素在非常常用的元素范围内。因此毫无疑问，内存增益将支付精度。

因此，尽管 Redis 随机采样(暗示这不是实际的 LRU .. 并且是一种近似算法)，但准确度相对较高，增加采样大小会进一步提高准确度。但是，如果有人需要精确的 LRU(对错误零容忍)，那么 Redis 可能不是正确的选择。

架构......正如他们所说......是关于权衡......所以使用这种(Redis LRU)方法来权衡原始性能的准确性。