Redis 内部结构 - 用于采样的 LRU 实现
有人知道基于 Redis LRU 驱逐/删除的内部结构吗？
Redis 如何确保较旧的（较少使用的）密钥首先被删除（如果我们没有易失性密钥并且我们没有设置 TTL 过期）？
我确信 Redis 有一个配置参数“maxmemory-samples”，它控制用于删除键的样本大小 - 因此，如果您将样本大小设置为 10，那么它会采样 10 个键，并从其中删除最旧的键。
我不知道的是它是否完全随机地对这些密钥进行采样，或者它是否有某种机制允许它自动从“较旧/较少使用的一代”的等效项中进行采样？
Does someone know about the internals of Redis LRU based eviction / deletion.
How does Redis ensure that the older (lesser used) keys are deleted first (in case we do not have volatile keys and we are not setting TTL expiration)?
I know for sure that Redis has a configuration parameter "maxmemory-samples" that governs a sample size that it uses for removing keys - so if you set a sample size of 10 then it samples 10 keys and removes the oldest from amongst these.
What I don't know is whether it sample these key's completely randomly, or does it somehow have a mechanism that allows it to automatically sample from an equivalent of an "older / less used generation"?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这是我在 antirez.com/post/redis-as-LRU-cache 找到的.html - 使用“示例三”算法的全部目的是节省内存。我认为这比精度更有价值，特别是因为这种随机算法很少被很好地理解。举个例子：仅使用三个对象进行采样将使 999 个数据集中的 666 个对象过期，与完美的 LRU 算法相比，错误率仅为 14%。而在剩下的 14% 中，几乎没有属于常用元素范围的元素。因此，毫无疑问，内存增益将为精度付出代价。
因此，尽管 Redis 是随机采样的（这意味着这不是实际的 LRU ......并且是一种近似算法），但精度相对较高，并且增加采样大小将进一步提高精度。然而，如果有人需要精确的 LRU（对错误零容忍），那么 Redis 可能不是正确的选择。
架构......正如他们所说......是关于权衡的......所以使用这种（Redis LRU）方法来权衡原始性能的准确性。
This is what I found at antirez.com/post/redis-as-LRU-cache.html - the whole point of using a "sample three" algorithm is to save memory. I think this is much more valuable than precision, especially since this randomized algorithms are rarely well understood. An example: sampling with just three objects will expire 666 objects out of a dataset of 999 with an error rate of only 14% compared to the perfect LRU algorithm. And in the 14% of the remaining there are hardly elements that are in the range of very used elements. So the memory gain will pay for the precision without doubts.
So although Redis samples randomly (implying that this is not actual LRU .. and as such an approximation algorithm), the accuracy is relatively high and increasing the sampling size will further increase this. However, in case someone needs exact LRU (there is zero tolerance for error), then Redis may not be the correct choice.
Architecture ... as they say ... is about tradeoffs .. so use this (Redis LRU) approach to tradeoff accuracy for raw performance.
自 v3.0.0 (2014) 起，LRU 算法使用 15 个键的池，并填充 N 个键的不同采样中的最佳候选键（其中 N 由 maxmemory-samples 定义）。
每次需要驱逐一个密钥时，都会随机选择 N 个新密钥并与池进行检查。如果它们是更好的候选者（较旧的密钥），则会将它们添加到其中，而最差的候选者（最新的密钥）将被删除，使池的大小保持在 15 个密钥的恒定大小。
在本轮结束时，从池中选出最佳驱逐候选者。
来源：evict.c 文件中的代码和注释来自Redis源代码
Since v3.0.0 (2014) the LRU algorithm uses a pool of 15 keys, populated with the best candidates out of the different samplings of N keys (where N is defined by
maxmemory-samples).Every time a key needs to be evicted, N new keys are selected randomly and checked against the pool. If they're better candidates (older keys), they're added in it, while the worst candidates (most recent keys) are taken out, keeping the pool at a constant size of 15 keys.
At the end of the round, the best eviction candidate is selected from the pool.
Source: Code and comments in evict.c file from Redis source code