Meet Top-K: an Awesome probistic Addition to RedisBloom

背景

您可能会发现自己不知道是否应该在代码中使用更多的概率数据结构。答案一如既往，视情况而定。如果您的数据集相对较小，并且您有所需的可用内存，那么在索引中保留数据的另一份副本可能是有意义的。您将保持100%的准确性，并得到一个快速的执行时间。

然而，当数据集变得相当大时，您当前的解决方案将很快变成一个缓慢的内存消耗，因为它存储了项或项标识符的额外副本。因此，当您处理大量的项目时，您可能想要放松100%准确性的要求，以获得速度和节省内存空间。在这些情况下，使用适当的概率数据结构可以发挥神奇的作用——支持高精度、预定义的内存允许和与数据集大小无关的时间复杂度。

Top-K介绍

在数据集或流中查找最大的K元素(也就是关键字频率)是许多现代应用程序的常见功能需求。这通常是一项关键任务，用于跟踪网络流量，用于市场营销或网络安全目的，或作为游戏排行榜或简单的文字计数器。Top-K在我们RedisBloom模块使用了一种名为HeavyKeeper的算法¹这是由一组研究人员提出的。他们放弃了惯常的做法计算所有或admit-all-count-some之前算法使用的策略，如节省空间或不同的计数草图。相反，他们选择了一个count-with-exponential-decay策略。的设计指数衰减对小流量有偏见，对大流量影响有限。这确保了较高的准确性和更短的执行时间，比以前的概率算法所允许的，同时保持内存利用率为一个排序集通常需要的一小部分。

使用这个Top-K概率数据结构的另一个好处是，当元素进入或从Top-K列表中删除时，您将实时收到通知。如果一个元素add-命令进入列表，将返回被删除的元素。然后，您可以使用这些信息来帮助防止DoS攻击，与顶级玩家进行交互，或者在一本书中发现写作风格的变化。

在RedisBloom中初始化Top-K键需要四个参数:

• K——你清单上项目的数量;
• Width -每个数组的计数器数目;
• Depth—数组的数量;和
• 衰减-在发生碰撞的情况下计数器的几率会降低¹．

根据经验法则，k*log(k)的宽度，log(k)的深度或最小值为5，衰减0.9，会产生良好的结果。您可以运行一些测试，根据数据的性质对这些参数进行微调。

排行榜基准使用Sorted Set vs. Top-K

Redis ' Sorted Set数据结构提供了一种简单和流行的方法来保持简单，准确排行榜²．使用这种方法，您可以通过调用ZINCRBY并通过调用来检索列表ZREVRANGE在理想范围内。另一方面，Top-K是用TOPK。储备命令。调用TOPK。添加将更新计数器，如果Top-K列表已更改，则将返回删除的项目。最后,TOPK。列表，如您所料，返回当前的K项列表。为了比较这两个选择，我们使用排行榜用例运行了一个简单的基准。

在该基准测试，我们提取了书中最常见的单词列表战争与和平，字数超过50万字。为了完成这一任务，Redis Sorted Set只需要不到6秒的时间，并且需要几乎4MB的RAM，保证100%的准确性。相比之下，Top-K平均占用了四分之一的时间和一小部分内存，特别是对于较低的K值。在大多数情况下，它的准确率是100%，除了非常高的k，它“只”达到了99.9%的准确率^3.．

从上述结果中可以得出以下有趣的结论:

• K值对执行时间影响不大。
• 深度不足不仅降低了精确度，还增加了执行时间。这可能是由于Top-K列表的频繁更改以及所需的处理时间。
• 空间效率非常高，对于任何合理的使用情况，我们都希望节省99%的RAM。

需要注意的是，不同类型的数据可能对不同的变量敏感。在我的实验中，一些数据集的执行时间对K更敏感。“在其他情况下，对于相同的宽度和深度值，较低的衰减值产生较高的精度。

RedisBloom中新的Top-K概率数据结构具有快速、精简和超精确的特点。对于任何具有低内存使用需求的流或不断增长的数据集的项目，可以考虑使用它。就我个人而言，这是我在Redis的第一个项目，我感到很幸运有机会在这样一个独特的算法上工作。我对这个结果非常满意!

如果您有一个想要讨论的用例，或者只是想分享一些想法，欢迎光临给我发邮件．

脚注

［1］HeavyKeeper:一种寻找Top-K象流的精确算法

［2］Redis的前3个改变游戏的用例．

图表中较低的结果没有遵循宽度和深度的指导原则。