Redis Internals - 用于采样的LRU实现

Question

有人知道基于Redis LRU的驱逐/删除的内部.

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

我确信Redis有一个配置参数"maxmemory-samples"来管理它用于删除键的样本大小 - 所以如果你设置一个样本大小为10,那么它会对10个密钥进行采样并从中删除最旧的密钥.

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

Answer 1

这就是我在antirez.com/post/redis-as-LRU-cache.html上发现的- 使用"样本三"算法的全部意义在于节省内存.我认为这比精确度更有价值,特别是因为这种随机算法很少被很好地理解.例如:仅使用三个对象进行采样将使999数据集中的666个对象失效,与完美LRU算法相比,错误率仅为14%.并且在剩余的14%中,几乎没有元素属于非常常用的元素.因此,内存增益将毫无疑问地支付精度.

因此,尽管Redis随机采样(暗示这不是实际的LRU ......并且作为这样的近似算法),但是精度相对较高并且增加采样尺寸将进一步增加这一点.但是,如果有人需要精确的LRU(误差容差为零),那么Redis可能不是正确的选择.

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