视频
Count-Min Sketch：估计事物的艺术与科学
了解更多
Redis 8 来了——而且是开源的
了解更多
分享
大家好！我叫 Savannah，我是 Redis 的一位新晋开发者布道师。我曾在直播中与我们的高级开发者布道师 Justin 和 Guy 讨论 RedisJSON，并探讨了概率数据结构。与 Guy 的探讨在 Twitch 上是短暂的，但我最近使用了一些更多的概率数据结构进行了一些编码，您可以在 YouTube 上观看。人们可能对概率数据结构是什么感到困惑，因此我认为我应该花一些时间写下这些处理大型数据集的数据结构的重点。
Google Chrome、Akami 和您的 ISP 可能会使用某些类型的概率数据结构来做一些可以改善您作为最终用户生活的事情。因此，如果您有大型数据集，认为数据结构很酷，或者想看看那些大公司会在哪里使用这些东西，请继续阅读！
下载我们的白皮书“Redis HyperLogLog：深度剖析”。
Redis 提供了几种不同的概率数据结构——一些在 RedisBloom 模块中（包含在 redis-py 中，我选择的语言），一个在核心 Redis 中，但 RedisBloom 现在包含在所有客户端库中，因此如果您使用 Redis Stack，则无需导入任何其他内容。在这篇文章中，我将告诉您关于 Bloom 过滤器、Cuckoo 过滤器、Top-K、Count-Min Sketch 和 Hyperloglog 的信息。我们将了解每种概率的本质、它们工作原理的概要介绍以及一些关键用例。我们将从以下 Redis 连接和这些代码示例的定义开始。
r = redis.Redis(
host='localhost',
port=6379,
db=0,
decode_responses=True
)
以第一个写下这个想法的人的名字命名，Bloom 过滤器可以告诉我们概率成员资格，也就是说，某件事是否已添加到过滤器中。
Bloom 过滤器的工作原理类似于位数组，其中添加项目并设置某些位。这可能会有重叠；但是，多个事物可能会映射到一些相同的位。这些项目被添加到过滤器中没有问题，除非它们对应的所有位都已被设置，在这种情况下，响应是该项目可能已经被添加到过滤器中。由于未设置的位表示未添加某个项目，因此没有假阴性。
但是，由于不同项目的位重叠以及 Bloom 过滤器不存储关于什么被添加的任何信息，因此无法删除。我们将展示如何创建我们的 Bloom 过滤器、一个多添加和一个多存在性检查。此处的输出是概率性的，可能是误报或真阴性。在这种情况下，仅向设置为存储 1,000 个项目的过滤器添加三件事，几乎可以保证是真阴性。
r.bf().create('Bloom', 0.01, 1000)
r.bf().madd('Bloom', foo, bar, baz)
r.bf().mexists('Bloom', foo, faz) #1 0 OR 1 1
还有其他命令可用于获取有关 Bloom 过滤器的信息、保存和加载它以及其他一些命令。但是，创建它、向其中添加内容以及检查这些内容是否存在是完成 Bloom 过滤器的主要目的所需的全部操作。
这些过滤器可以快速代替测试大型数据集的集合成员资格。例如，Google Chrome 浏览器维护一个恶意 URL 的 Bloom 过滤器。当有人尝试在 Chrome 中访问网站时，浏览器首先检查 Bloom 过滤器。由于没有假阴性，如果过滤器返回它不存在，Chrome 会允许用户快速访问该 URL，而无需检查大型数据集。由于 Bloom 过滤器只是位数组，它们通常可以存储在浏览器缓存中，从而节省了与大型且遥远的数据库查找相比的时间。
除了我上面解释的标准 Bloom 过滤器之外，Redis 实现还可以选择成为 Scaling Bloom 过滤器。多年来，人们在 Bloom 过滤器上添加了一些不同的东西，添加了不同的功能，同时在很大程度上保持了核心思想。例如，Stable Bloom 过滤器可以更好地处理无限数据而无需缩放，但可能会引入假阴性。其他类型的 Bloom 过滤器包括 Counting Bloom 过滤器、Distributed Bloom 过滤器、Layered Bloom 过滤器等等。
以一种著名的将其他鸟类的蛋推出巢穴并取而代之的鸟类命名，Cuckoo 过滤器也告诉我们概率成员资格，但方式与 Bloom 过滤器截然不同。
Cuckoo 过滤器保留了已添加的每个项目的指纹，并将多个指纹存储在每个存储桶中。指纹的长度（以位为单位）决定了发生冲突的速度，这有助于确定您需要的存储桶数量以及您可以获得的错误率。当发生冲突时，存储桶中的其中一个指纹将被踢出并放入不同的存储桶中，因此得名。
由于存储了指纹，因此 Cuckoo 过滤器确实支持删除。但是，冲突仍然存在，您最终可能会删除您不想删除的内容，这可能会导致一些假阴性。与 Bloom 过滤器一样，我们要做的主要事情是创建一个、向其中添加内容并检查它们是否存在。但是，我们必须使用 `insert` 命令将多个项目添加到 Cuckoo 过滤器。Cuckoo 过滤器还有一个 命令，用于在项目不存在时添加项目：`addnx`。
但是，由于 `exists` 命令是概率性的，因此尝试删除以此方式添加的项目可能会导致假阴性。在这里，我们将看到与 Bloom 过滤器相同的 `mexists` 的概率输出。
r.cf().create('cuckoo', 1000)
r.cf().addnx('cuckoo', foo)
r.cf().insert('cuckoo', bar, baz)
r.cf().delete('cuckoo', foo)
r.cf().mexists('cuckoo', foo, faz) #1 0 OR 1 1
Cuckoo 过滤器的主要吸引力是能够删除条目，除了那些需要此功能的用例外，通常使用 Bloom 过滤器。
就像草图是粗略的图画一样，Count-Min Sketch（又名 CM Sketch）将返回对项目添加到草图中的次数的最小计数的粗略猜测。这意味着，此数据结构可以回答项目频率问题。在某些方面，CM Sketch 类似于 HyperLogLog，因为它们都计算元素，关键区别在于 CM Sketch 不计算唯一元素，而是计算您添加到其中的每个元素的副本数。
就像 Top-K 结构的一部分一样，Count-Min Sketch 是一个表，其中每行代表正在使用的不同哈希函数，并且添加的每个项目在每行中都有一个位置。但是，与 Top-K 不同，此数据结构只是计数，而不考虑这些计数附加到什么。因此，在发生冲突的情况下，计数只会递增，而不用担心计数现在是两个不同事物组合在一起的计数。这就是为什么当您查询项目的计数时，会考虑每行的计数，并且您会得到最小值。
对于 Count-Min Sketch，我们可以通过我们要维护的概率或我们想要的维度来初始化它。这将非常重要，因为要合并两个 Count-Min Sketch，它们必须具有相同的维度。
一些重要的事情需要注意（关于下面 Python 代码中的 命令），您实际上没有将任何内容添加到 Count-Min Sketch，而是使用 `incrby` 并按指定的量增加计数。即使您只递增一件事，也必须将其作为列表传递。然后可以使用指定的权重合并它们，其中权重本质上乘以各自 Sketch 中的计数。然后查询合并的 Sketch。
在这段代码中，我不再能够看到 `cms1` 中曾经的内容，但我仍然可以使用原始的 `cms2`。我也可以创建一个新的 Count-Min Sketch `cms3`（具有相同的维度），然后将 `cms1` & `cms2` 合并到 `cms3` 中，从而保留 `cms1` & `cms2` 的原始数据。
查询 baz 的输出是 6，因为我们使用了 `incrby` 与 2，然后使用了权重 3。但是，一旦添加了大量内容，此计数将变得不太准确。
r.cms().initbydim('cms1', 2000, 5)
r.cms().initbydim('cms2', 2000, 5)
r.cms().incrby('cms1', [foo], [4])
r.cms().incrby('cms1', [bar, baz], [1, 2])
r.cms().incrby('cms2', [foo], [1])
r.cms().merge('cms1', 2, ['cms1', 'cms2'], weights=[3,1])
r.cms().query('cms1', baz) #6
当存储每个项目变得不切实际时，此数据结构可以用于大量数据，因为您只存储数字表而不是存储项目的内容。然后，您可以查询任何给定项目已添加多少次，并获得它映射到的空间的最小计数，这可能仍然会略微膨胀，具体取决于发生的冲突数量。
Top-K 数据结构以其功能命名，它会返回存储在其中的 Top-K 计数的近似值。
这里涉及到两个数据结构：一个表，用于跟踪指纹及其计数；以及一个最小堆结构，用于跟踪表中 Top-K 的事物。表中的每一行代表正在使用的不同哈希函数，因此添加的每个项目都会被哈希到每一行中的一个位置。特别是，Redis 的实现使用了一种名为 HeavyKeeper 的算法。使用此算法，基本思想是，每当指纹之间发生冲突时，已经存在的内容的计数有可能会被递减。这意味着被大量添加的项目具有高计数和低衰减概率，而那些没有被大量添加的项目会随着时间的推移被覆盖。
要了解有关可用 Top-K 命令的更多信息，我们将为一个命令保留空间，首先指定我们要保存的 top 事物的数量，然后是我们想要的宽度、深度和衰减（redis-py 需要，但在 Redis CLI 中不需要，正如您可以在我们的其中一个 Redis Live 录音中看到我发现的那样）。我们可以将事物添加到 Top-K，我们可以使用相同的命令添加多个事物或仅添加一个。然后，我们可以获取我们已添加的任何事物的计数。
但是，当我们使用 `query` 时，我们只能找出我们查询的事物是否在我们指定的 Top-K 项目中。因此，例如，我们将“topk”初始化为仅在最小堆中保留 top 1 项。因此，查询 bar 将返回 0，因为我们多次添加“foo”。查询“foo”将返回 1。我们还可以获取 Top-K 项目的列表。当添加大量事物并经历概率衰减时，此 Top-K 可能会失去一些精度。
r.topk().reserve('topk', 1, 8, 7, 0.9)
r.topk().add('topk', foo, bar, baz)
r.topk().add('topk', foo)
r.topk().add('topk', foo)
r.topk().count('topk', bar) #1
r.topk().count('topk', foo) #3
r.topk().query('topk', bar) #0
r.topk().query('topk', foo) #1
r.topk().list('topk') #[foo]
使用的哈希函数越多，发生冲突的可能性就越小。在 Top-K 结构中，单个项目的最大计数将与最小堆进行比较。因此，要真正减少一个项目的计数，它必须在每一行上都有哈希冲突。这仍然意味着 Top-K 最小堆最终可能会包含例如第六个最常见添加的事物，而不是第五个。此数据结构通常用于监视网络流量并跟踪哪些 IP 地址正在泛洪网络并可能尝试引起 DDoS。
在从线性计数开始，然后转向概率计数之后，这个名称最初来自 2003 年的论文，该论文提出了 LogLog 算法和一个改进的版本 Super-LogLog，现在我们有了 HyperLogLog。
HyperLogLog 是 Redis 中最早提供的数据结构之一，它保持对已添加的唯一项目数量的概率计数。与 Bloom 过滤器一样，此数据结构通过哈希函数运行项目，然后在某种类型的位域中设置位。此外，与 Bloom 过滤器一样，此结构不保留有关 添加的单个项目的信息，因此这里没有删除。此数据结构没有太多可用的命令，因此比其他数据结构更容易使用。只有添加、计数、合并和两个测试命令，我们可以很容易地看到你可以做什么。你可以将事物添加到其中，获取已添加的唯一事物的计数，并将它们合并在一起。将它们合并在一起将产生一个 HyperLogLog，其中仅包含来自每个 HyperLogLog 的唯一项目——也就是说——两个 HyperLogLog 中都存在的项目不会重复，并且它们在合并的 HyperLogLog 中仅被计算为一个唯一项目。
由于 HyperLogLog 位于核心 Redis 中，而不是 RedisBloom 模块中，因此在下面的命令中，我们看不到`r.hll().add`，也不必实际创建或保留一个；我们只是开始向其中添加事物。我们可以将多个 HyperLogLog 合并在一起，并获得其中有多少唯一事物的概率计数。同样，添加的事物越多，此计数就越有可能失去一些精度。
r.pfadd('hll1', foo, bar, baz)
r.pfadd('hll2', foo)
r.pfmerge('hll3', 'hll1', 'hll2')
r.pfcount('hll1') #3
r.pfcount('hll2') #1
r.pfcount('hll3') #3
此数据结构对于计算大型数据集中的唯一项目非常有用，例如，访问网站的唯一 IP 地址、唯一的视频观看者等。
嗯，如果你有一个非常大的数据集或一个大数据应用程序，你可能想要从它那里快速获得一些可以接受某些不准确性的东西，因为这些不准确性会带来巨大的空间节省。快速知道某事物肯定不存在可能值得以误报率为代价。知道在你的前 10 名中，你可能有一些实际上在前 15 名中的东西，并且缺少了一些前 10 名中的东西，但这取决于你希望用该信息做什么，这没关系。如果你正在使用Chrome、Akami 或互联网的任何部分，你可能正在从一些概率数据结构中受益。
我希望你了解了一些关于为什么以及何时概率数据结构可以帮助你获取有关大型数据集的信息，同时不占用太多空间——当然，信息的精度会降低一些。我希望你查看 Redis 为你提供的概率数据结构。如果您有任何问题，请在discord上找到我们，或者查看 Redis YouTube 频道 ，看看你可以用 Redis 做什么。
