视频
Redis 中的概率数据结构
了解更多
快速的未来正在你所在的城市举办的活动中。
加入我们在 Redis 发布会上
分享
这篇文章将讨论我认为世界上最令人兴奋的两件事：概率数据结构和 Redis 模块。如果你听说过其中之一，那么你一定能理解我的热情，但如果你想了解地球上最酷的东西，请继续阅读。
我将从以下陈述开始：大规模低延迟数据处理具有挑战性。所涉及的数据量和速度会使实时分析变得极其困难。由于其高性能和多功能性，Redis 通常用于解决此类挑战。它在亚毫秒延迟内存储、操作和提供多种形式数据的能力使其成为许多需要在线计算的用例的理想数据容器。
但一切都是相对的，有些规模非常极端，以至于使准确的实时分析成为现实中的不可能。复杂的难题随着规模的增大而变得更加困难，但我们往往忘记简单的难题也遵循相同的规律。即使像求和这样基本的操作，一旦数据量太大、速度太快或我们没有足够的资源来处理它，也会变成一项艰巨的任务。而且，虽然资源总是有限且昂贵的，但数据却像没有人一样在不断增长。
Count-min Sketch（也称为 CM Sketch）是一种概率数据结构，一旦你掌握了它的工作原理，更重要的是，如何使用它，它就会非常有用。
幸运的是，CM Sketch 的简单特性使其相对容易被新手理解（事实证明，我很多朋友无法理解这篇文章 Top-K 博客）。
CM Sketch 已成为 Redis 模块多年，最近作为 RedisBloom 模块 v2.0 的一部分进行了重写。但在深入研究 CM Sketch 之前，了解为什么要使用任何概率数据结构很重要。在速度、空间和准确性的三角形中，概率数据结构牺牲了一些准确性以换取空间——可能很多空间！速度的影响根据算法和集合大小而有所不同。
正确的概率数据结构允许你只保留数据集中的部分信息，以换取降低的准确性。当然，在许多情况下（例如银行账户），降低准确性是不可接受的。但对于推荐电影或向网站用户展示广告，相对罕见的错误的成本很低，而空间节省可能很大。
基本上，CM Sketch 通过将数据集中的所有项目的计数聚合到几个计数器数组中来工作。在查询时，它返回所有数组中项目的最小计数，这保证了最小化由冲突引起的计数膨胀。出现率或分数较低的项目（“鼠标流”）的计数低于错误率，因此你将丢失有关其真实计数的任何数据，并将它们视为噪声。对于出现率或分数较高的项目（“大象流”），只需使用接收到的计数即可。考虑到 CM Sketch 的大小是恒定的，它可以用于无限数量的项目，因此你可以看到在存储空间方面节省的巨大潜力。
作为背景，sketch 是数据结构和它们伴随的算法的一类。它们捕捉你数据的本质，以便在使用恒定或亚线性空间的同时回答有关它的问题。CM Sketch 由 Graham Cormode 和 S. Muthu Muthukrishnan 在 2005 年的一篇名为“改进的数据流摘要：Count-Min Sketch 及其应用” 的论文中描述。
CM Sketch 使用几个计数器数组来支持其主要用例。我们称数组的数量为“深度”，每个数组中的计数器数量为“宽度”。
每当我们收到一个项目时，我们使用哈希函数（它将一个元素——单词、句子、数字或二进制——转换为一个可以用作集合/数组中的位置或指纹的数字）来计算项目的位置，并为每个数组增加该计数器。每个关联计数器的值都等于或高于项目的真实值。当我们进行查询时，我们使用相同的哈希函数遍历所有数组，并获取与我们的项目相关的计数器。然后，我们返回遇到的最小值，因为我们知道我们的值是膨胀的（或相等的）。
即使我们知道许多项目贡献了大多数计数器，但由于自然冲突（当不同的项目接收到相同的位置时），我们接受“噪声”，只要它保持在我们的预期错误率范围内即可。
数学表明，深度为 10，宽度为 2,000，没有错误的概率为 99.9%，错误率为 0.1%。（这是总增量的百分比，而不是唯一项目的百分比）。
用实际数字来说，这意味着如果你添加 100 万个唯一项目，平均每个项目将接收一个值为 500 的值（1M/2K）。虽然这看起来不成比例，但这远低于我们的 0.1% 的错误率，即 100 万个项目中 1,000 个项目的错误率。
同样，如果 10 头大象分别出现 10,000 次，那么它们在所有集合上的值都将是 10,000 或更多。无论何时我们将来计数它们，我们都会看到一只大象出现在我们面前。对于所有其他数字（即所有真实计数为 1 的老鼠），它们不太可能与所有集合上的大象发生冲突（因为 CM Sketch 仅考虑最小计数），因为这种情况发生的概率很小，如果你在初始化 CM Sketch 时增加深度，这种概率会进一步减小。
现在我们了解了 CM Sketch 的行为，我们能用这个小东西做什么呢？以下是一些常见的用例
在 RedisBloom 中，CM Sketch 的 API 简单易用
以下命令用于创建本文顶部所示的动画示例
正如你所看到的，“Redis”的值为 4 而不是 3。这是预期的行为，因为在 CM Sketch 中，项目的计数很可能被夸大了。
软件工程就是权衡取舍，而一种流行的以成本效益的方式解决这些挑战的方法是牺牲准确性以换取效率。Redis 对 HyperLogLog 的实现就体现了这种方法，它是一种 数据结构，旨在有效地提供有关集合基数的查询答案。HyperLogLog 是一个名为“sketch”的数据结构系列的成员，就像它们在现实世界的艺术对应物一样，通过对它们的主题的近似表示来传达信息。
简而言之，草图是数据结构（及其配套算法），用于捕捉数据的本质——对数据问题的答案，而无需实际存储数据本身。正式地说，草图很有用，因为它们具有亚线性渐进计算复杂度，因此需要更少的计算能力和/或存储空间。但是，天下没有免费的午餐，效率的提升是以答案的准确性为代价的。然而，在许多情况下，只要误差能控制在阈值以下，误差是可以接受的。一个好的数据草图应该能够轻松地承认其误差，事实上，许多草图会将误差（或误差发生的概率）参数化，以便用户可以对其进行定义。
好的草图效率高，误差概率有界，但优秀的草图是可以并行计算的。可并行化的草图是指可以在数据的部分独立地准备，并允许将其部分组合成有意义且一致的聚合的草图。由于优秀的草图的每个部分都可以在不同的位置和/或时间进行计算，因此并行性使得能够采用简单地分治方法来解决扩展难题。
前面提到的 HyperLogLog 是一种优秀的草图，但它只适合回答特定类型的问题。另一个宝贵的工具是 Count Min Sketch (CMS)，如 G. Cormode 和 S. Muthukrishnan 在论文 “An Improved Data Stream Summary: The Count-Min Sketch and its Applications” 中所述。这个巧妙的装置是为了提供有关样本频率的答案而设计的，这是大量分析过程中的一个常见组成部分。
如果有足够的时间和资源，计算样本频率是一个简单的过程——只需对每个样本（看到的对象）的观测次数（看到的次数）进行计数，然后将其除以观测总数即可得到该样本的频率。然而，在高规模低延迟数据处理的背景下，时间和资源永远不够。无论数据规模如何，都必须立即提供答案，并且采样空间的巨大规模使得为每个样本保存计数器变得不可行。
因此，我们可以尝试估计频率，而不是准确地跟踪每个样本。一种方法是随机采样观测值，并希望样本能大体反映整体的属性。这种方法的问题是，确保真正的随机性是一项困难的任务，因此随机采样的成功可能会受到我们的选择过程和/或数据本身属性的限制。这就是 CMS 的用武之地，它采用了一种截然不同的方法，乍一看，它可能与优秀的草图背道而驰：CMS 不仅记录每个观测值，而且每个观测值都被记录在多个计数器中！
当然，这里面有一个巧妙的地方，这个巧妙的地方既简单又聪明。原始论文（及其名为 “Approximating Data with the Count-Min Data Structure” 的轻量级版本）对这一点解释得很好，但我会尝试对其进行总结。CMS 的巧妙之处在于它存储样本的方式：它不独立地跟踪每个唯一的样本，而是使用它的哈希值。样本的哈希值用作指向固定大小（在论文中参数化为 d）的计数器数组的索引。通过使用多个（参数 w）不同的哈希函数及其各自的数组，草图通过从样本所有相关计数器中选取最小值来处理在查询结构时发现的哈希冲突。
需要一个例子，所以让我们做一个简单的草图来说明数据结构的内部工作原理。为了使草图保持简单，我们将使用较小的参数值。我们将 w 设置为 3，这意味着我们将使用三个哈希函数——分别表示为 h1、h2 和 h3，并将 d 设置为 4。为了存储草图的计数器，我们将使用一个 3×4 数组，总共 12 个元素，初始化为 0。
现在，我们可以检查当样本添加到草图中时会发生什么。假设样本一个接一个地到达，并且第一个样本的哈希值，表示为 s1，为：h1(s1) = 1、h2(s1) = 2 和 h3(s1) = 3。为了在草图中记录 s1，我们将相应索引处每个哈希函数的计数器加 1。下表显示了数组的初始状态和当前状态
虽然草图中只有一个样本，但我们已经可以有效地对其进行查询。请记住，样本的观测次数是所有计数器的最小值，因此对于 s1，它通过以下方式获得
min(array[1][h1(s1)], array[2][h2(s1)], array[3][h3(s1)]) =草图还回答有关尚未添加的样本的查询。假设 h1(s2) = 4，h2(s2) = 4，h3(s2) = 4，请注意，查询 s2 将返回结果 0。让我们继续将 s2 和 s3 (h1(s3) = 1，h2(s3) = 1，h3(s3) = 1) 添加到草图中，得到以下结果
min(array[1][1], array[2][2], array[3][3]) =
min(1,1,1) = 1
在我们这个人为的例子中，几乎所有样本的哈希值都映射到唯一的计数器，唯一的例外是 h1(s1) 和 h1(s3) 的冲突。由于这两个哈希值相同，因此 h1 的第 1 个计数器现在包含值 2。由于草图选取所有计数器的最小值，因此对 s1 和 s3 的查询仍然返回正确的结果 1。然而，最终，一旦发生足够多的冲突，查询的结果将变得不太准确。
CMS 的两个参数——w 和 d——决定了它的空间/时间需求，以及误差的概率和最大值。初始化草图的一种更直观的方法是提供误差的概率和上限，使其能够推导出 w 和 d 的所需值。并行化是可能的，因为只要使用相同的参数和哈希函数构建子草图，就可以将任意数量的子草图简单地合并为数组的总和。
通过回顾 Count Min Sketch 的需求，可以证明其效率。CMS 的空间复杂度是 w、d 和它使用的计数器的宽度之积。例如，一个误差率为 0.01%，概率为 0.01% 的草图是用 10 个哈希函数和 2000 个计数器数组创建的。假设使用 16 位计数器，则生成的草图数据结构的总内存需求为 40KB（还需要几个字节来存储观测总数和一些指针）。草图的其他计算方面同样令人满意——由于哈希函数生成和计算成本低廉，因此访问数据结构（无论是读还是写）也以恒定时间完成。
CMS 还有更多内容；草图的作者还展示了它如何用于回答其他类似问题。这些包括估计百分位数和识别热点（频繁项目），但不在本文的讨论范围之内。
CMS 当然是一个优秀的草图，但至少有两件事阻止了它达到完美。我对 CMS 的第一个保留意见是它可能会存在偏差，因此会高估观测次数较少的样本的频率。CMS 的偏差是众所周知的，并且已经提出了一些改进方案。最新的是 Count Min Log Sketch (“Approximately counting with approximate counters” 来自 G. Pitel 和 G. Fouquier)，它本质上是用对数寄存器替换了 CMS 的线性寄存器，以降低相对误差，并在不增加计数器寄存器宽度的情况下允许更高的计数。
虽然以上保留意见是每个人都持有的（虽然只有那些理解数据结构的人持有），但我第二个保留意见是针对 Redis 社区的。为了解释，我必须介绍 Redis 模块。
Redis 模块是在今年早些时候的 RedisConf 上由 antirez 公布的，它彻底改变了我们的世界。模块不过是在服务器上可加载的动态库，它们允许 Redis 用户比 Redis 本身运行得更快，并去往以前从未梦寐以求的地方。虽然这篇文章不是介绍模块是什么或如何创建模块的，但 这篇是（以及 这篇文章，以及 这个网络研讨会）。
除了其极大的实用性之外，我还想编写 Count Min Sketch Redis 模块还有几个原因。其中一部分是为了学习体验，一部分是为了评估模块 API，但最重要的是，将一个新的数据结构建模到 Redis 中真的很有趣。该模块为向草图添加观测值、查询草图和将多个草图合并为一个草图提供了 Redis 接口。
该模块将草图数据存储在 Redis 字符串中，并使用直接内存访问 (DMA) 将键的内容映射到其内部数据结构。我还没有对其进行详尽的性能基准测试，但从本地测试中获得的初步印象是，它的性能与任何核心 Redis 命令一样好。像我们的其他模块一样，countminsketch 是开源的，我鼓励您尝试一下并进行修改。
在结束之前，我想履行承诺，分享我对 CMS 的 Redis 特定保留意见。这个问题也适用于其他草图和数据结构，即 CMS 需要您在使用它之前设置/初始化/创建它。要求强制性初始化阶段，如 CMS 参数设置，违反了 Redis 的一个基本模式——数据结构不需要在使用之前明确声明，因为它们可以按需创建。为了使模块看起来更像 Redis，并解决这种反模式，该模块在隐式暗示新草图时（即在非现有键上使用 CMS.ADD 命令）使用默认参数值，但也允许使用给定参数创建新的空草图。
概率数据结构，或草图，是令人惊叹的工具，它们让我们能够以高效且足够准确的方式跟上大数据的增长和延迟预算的缩减。这篇文章中提到的两种草图，以及其他草图，如 Bloom Filter 和 T-digest，正迅速成为现代数据分析师工具库中不可或缺的工具。模块允许您使用自定义数据类型和命令扩展 Redis，这些命令以原生速度运行，并可以本地访问数据。可能性是无限的，没有什么是不可能的。
想了解更多关于 Redis 模块及其开发方法吗？您是否想要讨论或添加到 Redis 的数据结构（概率的或非概率的）？欢迎您通过我的 Twitter 帐户或 电子邮件 与我联系——我随时可用 🙂
