结识 Top-K：Redis 特性的绝妙概率强化功能

背景

您可能会好奇是否应该在代码中使用更多概率数据结构。答案是，与往常一样，这取决于具体情况。如果您的数据集相对较小并且有足够的可用内存，那么在索引中保留另一份数据副本可能是有意义的。您将保持 100% 的准确性并获得快速的执行时间。

但是，当数据集变得庞大时，当前的解决方案很快会变成缓慢的内存消耗大户，因为它会存储项目或项目标识符的附加副本。因此，当您处理大量的项目时，您可能希望放松 100% 准确性的要求，以便提高速度和节省内存空间。在这些情况下，使用适当的概率数据结构可以创造奇迹 - 支持高准确性、预定义的内存分配以及与数据集大小无关的时间复杂度。

Top-K 简介

在数据集或流中找出最大的 K 个元素（也称为关键字频率）是许多现代应用程序的常见功能需求。这通常是一项用于出于营销或网络安全目的追踪网络流量的关键任务，或者可用作游戏排行榜或简单的单词计数器。我们概率特性的最新 Top-K 实现使用一种由一组研究人员提出的名为 HeavyKeeper¹ 的算法。他们放弃了之前的算法（例如节约空间或不同的计数草图）使用的常规 完全计数或 全部接纳部分计数策略。相反，他们选择了 指数衰减计数策略。 指数衰减的设计针对鼠标（小）流量有偏差，对大象（大）流量的影响有限。这确保了比以前允许的概率算法更高的准确性和更短的执行时间，同时内存利用率保持在排序集合通常所需的部分。

使用此 Top-K 概率数据结构的另一优点是，每当元素进入或退出 Top-K 列表时，您都将收到实时通知。如果元素添加命令进入列表，则会返回被删除的元素。然后，您可以使用此信息来帮助防止 DoS 攻击、与顶级选手互动或发现书中写作风格的变化。

在概率中初始化 Top-K 密钥需要四个参数

K – 列表中的项目数；
宽度 – 每个数组中的计数器数量；
深度 – 数组数量；和
衰减 – 计数器在碰撞时减少的概率¹。

根据经验，宽度为 k*log(k)，深度为 log(k) 或最小 5，衰减为 0.9，可以得到不错的结果。你可以运行一些测试，根据你的数据性质微调这些参数。

使用排序集合对比 Top-K 的排行榜基准

Redis 的排序集合数据结构提供了一种简单易行、足够准确的方式维护一个简单的 排行榜²。利用这种方式，你可以通过调用ZINCRBY 更新成员分数，并通过调用 ZREVRANGE 和理想范围获取列表。另一方面，Top-K 通过 TOPK.RESERVE 命令初始化。调用 TOPK.ADD 将更新计数器，而且如果你的 Top-K 列表更改，则会返回移除的项目。最后，TOPK.LIST 会如你所料返回当前 K 个项目的列表。为了对比这两个选项，我们使用排行榜用例运行了一个简单的基准。

在此基准中，我们提取了一本包含 500,000 多个单词的书籍战争与和平中出现频率最高的单词列表。为了完成此任务，Redis 排序集合花费不到 6 秒，而且内存需求约为 4MB，保证了 100% 的准确性。相比之下，Top-K 平均花费四分之一时间，使用的内存很小，尤其是较低的 K 值。在大多数情况下，它的准确性为 100%，但对于非常高的 K 值，“仅”达到 99.9% 的准确性³。

从上述结果中获得的一些有趣结论包括

执行时间几乎不受 K 值影响。
深度不足不仅会降低准确性，而且还会增加执行时间。这可能是由于 Top-K 列表经常更改，导致处理时间变长。
空间效率很高，对于任何合理的用例，我们预计能够节省 99% 的 RAM。

需要注意的是，不同类型的数据可能对不同变量很敏感。在我的实验中，某些数据集执行时间对“K”更敏感。在其他情况下，较低的衰减值会使相同宽度和深度值得到更高的准确性。

Probabilistic 中新的 Top-K 概率数据结构快速、精简且超级准确。对于需要低内存使用率的具有流或增长数据集的任何项目，都可以考虑使用它。个人来说，这是我在 Redis 的第一个项目，我感到很幸运能够有机会研究这种独特的算法。我对结果非常满意！

如果您有想要讨论的用例，或者只是想分享一些想法，请随时给我们发送电子邮件。

脚注

[1] HeavyKeeper：由主要作者：君志·恭和杨童共同撰写的查找 Top-K 巨型流的准确算法。

[2] 三大改变游戏规则的 Redis 用例。

[3] 图表中较低的结果不符合宽度和深度的指导原则。