我在我的previous post中谈论了Redis驱逐政策。
在这篇文章中，我想描述Dragonfly Cache背后的设计。

如果您没有听说过Dragonfly-请检查一下。它使用 - 我希望的 - 近年来[1]
的研究支持的新颖而有趣的想法
和[2]。它的目的是解决当今Redis存在的许多问题。在过去的7个月中，我一直从事蜻蜓的工作，这是我做过的更有趣和具有挑战性的项目之一！

无论如何，回到缓存设计。我们将从简短的概述LRU缓存及其一般的缺点开始，然后专门分析REDIS实现。

lru

顾名思义，最近使用的最少使用的（LRU）缓存策略驱逐了最近使用的项目。它这样起作用，因为一种缓存算法努力优化命中率，或者将来将访问其项目的概率。

如果缓存已满，则需要撤离物品以腾出空间以供新添加。缓存通过删除最低有价值的项目来释放新添加的空间，假设 最近使用的项目也是最少有价值的。。。 P>

假设是合理的，但是不幸的是，如果上述假设不存在，该算法的行为却很差。例如，考虑使用Long tail distribution的访问模式。在这里，y轴代表了缓存中项目的归一化访问频率，x轴表示从最高频率到最低的订购的项目。

在这种情况下，许多新添加的具有低访问频率的“黄色”项目可能会推出罕见但有价值的“绿色”项目，这些物品负责绝大多数命中。结果，由于交通波动，LRU政策可以将其内容与有价值的“绿色”实体一起扫描。

LRU实施效率

lru是一种可以有效实现的简单算法。
确实，它将所有项目维护在双连锁列表中。当访问项目时，LRU将其移至列表的头部。为了撤离LRU项目，它从列表的尾部弹出。请参阅上面的图。所有操作均在O(1)中完成，每个项目的内存开销为2个指针，即64位体系结构上的16个字节。

LRU在Redis

Redis实施了一些驱逐政策启发式方法。其中一些被描述为“近似LRU”。为什么要近似？因为redis在经典LRU中没有保持确切的全球秩序。相反，它在每个条目中存储最后一个访问时间戳。

当它需要驱逐项目时，Redis会对整个密钥空间进行随机抽样，并选择K候选物。然后，它在这些K候选物中选择了最近使用的时间戳，并将其撤离。这样，redis可以按一个全球顺序订购项目所需的每个条目16个字节。这种启发式是lru.redis维护者have recently discussed的一个非常粗略的近似，通过实施具有全球秩序的经典LRU政策，可以在Redis中添加额外的启发式，但最终决定反对。

蜻蜓缓存

蜻蜓实现缓存：

• 与LRU不同。
• 不需要随机抽样或其他近似近似。
• 有零每项内存开销。
• 有很小的O(1)运行时间开销。

在学术研究中，这是一种新颖的缓存设计方法。

蜻蜓高速缓存（DASH CACH）基于1994 paper-“ 2Q：低架空高性能缓冲区替换算法”的另一个著名的缓存策略。

2q通过引入两个独立的缓冲区来解决LRU的问题。 2q还考虑了每个项目的访问频率，而不是将重新度视为一个因素。它首先将最近的项目纳入所谓的试用缓冲液（见下文）。该缓冲区仅容纳缓存空间的一小部分，含量不到10％。所有新添加的项目在此缓冲区内相互竞争。

只有至少一次访问了一个试用项目，才能证明它是 worthy ，并升级到受保护的缓冲区。通过这样做，它将受保护的缓冲区回到试用缓冲区的最近使用的项目驱逐出来。您可以阅读this post以获取更多详细信息。

2q通过承认仅仅因为添加了一个新项目，就可以改善LRU - 并不意味着它有用。 2q需要至少一次访问一次，才能被视为高质量物品。这样，2Q缓存已被证明比LRU策略更强大，并获得更高的命中率。

可在60秒内涂抹

为了深入研究蜻蜓在蜻蜓中的使用，我建议您阅读此post或the original paper。

今天就我们的目的，我们需要了解有关蜻蜓实施中有关dashtable的以下事实：

1. 它由恒定大小的片段组成。每个片段都有56个常规存储桶，并带有多个插槽。每个插槽都有一个用于单个项目的空间。
2. Dashtable的路由算法使用项目的哈希值来计算其段ID。此外，它可以预先定义56个存储桶中的2个，其中该项目可以驻留在细分市场中。该项目可以驻留在这两个水桶中的任何免费插槽中。
3. 除了常规存储桶外，一个可敲打的细分市场还管理了4个藏匿桶，这些存储桶可能会收集分配的存储桶中没有空间的溢出项目。该路由算法永远不会直接分配固定存储桶。取而代之的是，只有当它的2个家庭存储桶已满时，该物品才能居住在4个储藏桶中的任何一个中。这大大增加了细分市场的利用。
4. 一旦一个段变满了，并且在其家庭桶中或在藏匿桶中没有免费的地方，可以通过添加新片段并将完整段的内容分为一半来生长。

段完整的点是将任何类型的驱逐策略添加到Dashtable中的方便时间，因为这是可敲打的时候。此外，为了防止破折号的增长，我们只能从整个细分市场中驱逐项目。这构成了一个非常精确的驱逐框架，该框架在O(1)运行时复杂性中运行。

2Q实施

蜻蜓在上面的想法上扩展。一种天真的解决方案是将空语条目分为两个缓冲区：带有FIFO排序的试用缓冲区，以及使用LRU链接列表的受保护缓冲液。那会起作用，但需要使用其他元数据和浪费宝贵的记忆。

相反，蜻蜓利用了Dashtable的独特设计，并使用其薄弱的订购特性来获得优势。

要解释2Q如何与Dashtable一起工作，我们需要解释如何定义试用缓冲区和受保护的缓冲区，如何将试用项目促进试用项目中受保护的缓冲区以及我们如何从缓存中驱逐项目。

。

我们覆盖了以下原始语义：

1. 存储桶内的插槽现在具有排名或优先级。左侧的一个插槽具有最高的(0)，右侧的最后一个插槽的排名最低。
2. 将片段内的藏匿处用作试用缓冲区。当将新项目添加到整个段中时，将其添加到插槽0处的藏匿桶中。存储桶中的所有其他项目都正确地移动，并且存储桶中的最后一个项目被驱逐出去。这样，水桶是试用项目的FIFO队列。
3. 每个缓存点击“推广”其项目：
   • 如果该物品在藏匿桶中，它立即将其移至最后一个插槽中。
   • 如果它位于slot i的家庭桶中
   • slot 0处的项目留在同一位置。
4. 当试用项目被提升为受保护的水桶时，它已移至那里的最后一个插槽。以前的物品被降级回到试用桶中。

基本上，Dash-Cache驱逐策略由（2）描述的“驱逐”步骤以及（3）描述的正增强步骤。

。

就是这样。无需额外的元数据。高质量的物品将非常迅速地居住在他们的家庭存储桶中，而新添加的物品在藏匿/试用桶中相互竞争。在我们的实施中，每个存储桶都有14个插槽，这意味着每个试用项目在被驱逐出缓存之前可以转移14次，除非它证明其有用性并得到促进。每个细分市场都有56个常规存储桶和4个藏匿桶；因此，我们将6.7%分配给了试用缓冲区。

都足以捕获高质量的物品。

我希望您喜欢阅读蜻蜓缓存设计如何利用看似无关的概念，以达到其优势。

我要感谢winding caffeine package的作者Ben Manes的早期评论和有关如何使用咖啡因模拟器的指导，以将蜻蜓缓存与其他缓存进行比较。