4

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

Redis 如何确保首先删除旧的（较少使用的）密钥（如果我们没有易失性密钥并且我们没有设置 TTL 过期）？

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

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

4

2 回答 2

7

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

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

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

于 2012-01-10T06:46:28.317 回答
1

自 v3.0.0 (2014) 以来，LRU 算法使用 15 个密钥池，其中填充了 N 个密钥的不同采样中的最佳候选者（其中 N 由 定义maxmemory-samples）。

每次需要驱逐一个密钥时，都会随机选择 N 个新密钥并针对池进行检查。如果它们是更好的候选者（较旧的键），则将它们添加到其中，而最差的候选者（最近的键）将被取出，使池保持在 15 个键的恒定大小。

在回合结束时，从池中选出最佳驱逐候选人。

来源：来自 Redis 源代码的 evict.c 文件中的代码和注释

于 2018-12-19T01:18:59.667 回答