视频
Count-Min Sketch: 估算的艺术与科学
了解更多
快速的未来正在您所在城市的活动中到来。
加入我们在 Redis 发布会上
分享
大家好！我的名字是 Savannah，我是 Redis 的一名新开发倡导者。我跳上了直播来谈谈 RedisJSON ，与我们高级开发倡导者 Justin 和 Guy 一起讨论概率数据结构。与 Guy 的探索在 Twitch 上是短暂的，但我最近在 YouTube 上使用了一些概率数据结构进行了一些编码。人们可能会对概率数据结构是什么感到困惑，所以我认为我应该花一些时间来写出这些处理大型数据集的数据结构的要点。
Google Chrome、Akami 和您的 ISP 可能会使用一些类型的概率数据结构来做一些事情，这些事情可以改善您作为最终用户的体验。所以，如果您拥有大型数据集，认为数据结构很酷，或者想看看这些大公司如何使用这些东西，请继续阅读！
下载我们的白皮书“Redis HyperLogLog: 深入探讨”。
Redis 提供了一些不同的概率数据结构 - 一些在 RedisBloom 模块中（包含在 redis-py 中，这是我的首选语言），一个在核心 Redis 中，但是 RedisBloom 现在已包含在所有客户端库中，因此如果您使用的是 Redis Stack，则无需导入任何其他内容。在这篇文章中，我将告诉您有关 布隆过滤器、库克过滤器、Top-K、计数最小草图 和 Hyperloglog 的信息。我们将逐步介绍每个结构的概率性质，它们工作原理的高级 概述，以及一些关键用例。我们将从以下 Redis 连接和这些代码示例的定义开始。
r = redis.Redis(
host='localhost',
port=6379,
db=0,
decode_responses=True
)
布隆过滤器以第一个写下这个想法的人命名，可以告诉我们概率成员资格，即某个东西是否已添加到过滤器中。
布隆过滤器作为位数组工作，其中添加了项目，并设置了某些位。这可能会导致重叠；但是，多个事物可能会映射到一些相同的位。这些项目可以毫无问题地添加到过滤器中，除非它们所对应的所有位都已设置，在这种情况下，响应是该项目可能已添加到过滤器中。由于未设置的位表示未添加项目，因此不存在假阴性。
但是，由于不同项目的位重叠以及布隆过滤器不存储有关已添加内容的任何信息这一事实，因此无法删除。我们将展示如何创建布隆过滤器，进行多添加和多存在检查。这里的输出是概率性的，可能是假阳性或真阴性。在这种情况下，仅将三件事添加到设置为存储 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
还有其他命令可用于获取有关布隆过滤器的信息，保存和加载它，以及其他一些命令。但是，创建它，向其中添加东西，以及检查这些东西是否存在，就是完成布隆过滤器主要目的所需的一切。
这些过滤器可以用来快速代替测试大型数据集的集合成员资格。例如，Google Chrome 浏览器维护着恶意 URL 的布隆过滤器。当有人尝试在 Chrome 中访问某个网站时，浏览器首先检查布隆过滤器。由于不存在假阴性，如果过滤器返回它不存在，Chrome 允许用户快速地访问 URL，而无需检查大型数据集。由于布隆过滤器只是位数组，因此它们通常可以存储在浏览器缓存中，节省了大量时间，无需进行远程数据库查找。
除了我上面解释的标准布隆过滤器之外，Redis 实现还提供了一个选项，可以将其变为可伸缩的布隆过滤器。多年来，人们在布隆过滤器上增加了一些功能，在很大程度上保留了核心思想的同时，增加了不同的功能。例如，稳定的布隆过滤器可以更好地处理无界数据，而无需扩展，但会引入假阴性。其他类型的布隆过滤器包括计数布隆过滤器、分布式布隆过滤器、分层布隆过滤器等。
库克过滤器以一种著名的鸟类命名，这种鸟类以将其他鸟类的卵从它们的巢中推出来并占为己有而闻名，库克过滤器也可以告诉我们概率成员资格，但与布隆过滤器的方式完全不同。
库克过滤器保存了每个已添加项目的指纹，并在每个桶中存储多个指纹。指纹的位长决定了冲突发生的快慢，这有助于确定您需要的桶数以及可以获得的错误率。发生冲突时，桶中的一个指纹会被踢出并放入另一个桶中，因此得名。
由于存储了指纹，因此库克过滤器确实支持删除。但是，冲突仍然存在，您最终可能会删除您不想删除的东西，这会导致一些假阴性。与布隆过滤器一样，我们想要做的主要事情是创建一个过滤器，向其中添加东西，并检查它们是否存在。但是，我们必须使用 `insert` 命令向库克过滤器添加多个东西。库克过滤器还有一个 命令 用于在项目不存在时添加它：`addnx`。
但是，由于 `exists` 命令是概率性的，因此尝试删除以这种方式添加的项目可能会导致假阴性。在这里，我们将看到与布隆过滤器相同的 `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
库克过滤器的主要吸引力是能够删除条目，除了删除是基本要求的情况之外，布隆过滤器通常被使用。
就像草图是粗略的图画一样，计数最小草图（也称为 CM 草图）将返回一个粗略的猜测，即项目添加到草图中的最小次数。这意味着，这种数据结构可以回答项目频率问题。在某些方面，CM 草图类似于 HyperLogLog，因为它们都计算元素，但关键区别在于 CM 草图不计算唯一元素，而是计算您添加到其中的每个元素的副本数量。
就像 Top-K 结构的一部分一样，计数最小草图是一个表，其中每一行代表一个不同的哈希函数被使用，每个添加的项目在每一行中都有一个位置。但是，与 Top-K 不同，这种数据结构仅仅是计数，而不考虑计数所附加的内容。因此，在发生冲突的情况下，计数只是被递增，而不关心计数现在是两个不同事物的计数的组合。这就是为什么当您查询项目的计数时，会考虑每一行的计数，并返回最小值。
对于计数最小草图，我们可以通过我们想要维护的概率或我们想要的维度来初始化它。这在某种程度上很重要，因为要合并两个计数最小草图，它们必须具有相同的维度。
需要注意的一些重要事项（关于 命令，在下面的 Python 代码中），您实际上并没有将事物添加到计数最小草图中，而是使用 `incrby` 并将计数增加指定数量。即使您只递增一项，也必须将其作为列表传递。然后，它们可以以指定的权重合并，其中权重本质上是将各个草图中的计数相乘。然后查询合并后的草图。
在这段代码中，我无法再看到以前在 `cms1` 中的内容，但我仍然可以使用原始的 `cms2`。我也可以创建一个新的计数最小草图 `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 计数的近似值。
这里涉及两种数据结构：一个用于跟踪指纹及其计数的表格，以及一个用于跟踪表格中前 K 个元素的最小堆结构。表格中的每一行都代表着一种不同的哈希函数，因此每个添加的项目都会被哈希到每一行的某个位置。特别是 Redis 的实现使用了名为 HeavyKeeper 的算法。在这个算法中，基本的想法是，只要指纹之间发生冲突，就有一定概率会减少之前已经存在的元素的计数。这意味着，被添加了很多次的元素会有很高的计数和很低的衰减概率，而那些没有被添加很多次的元素则会随着时间的推移而被覆盖。
要了解更多关于可用的 Top-K 命令，我们将预留一个空间，首先指定我们要保存的前 K 个元素的数量，然后指定我们想要的宽度、深度和衰减率（redis-py 需要，但 Redis CLI 不需要，正如你可以在我们的 Redis Live 录制中看到的那样）。我们向 Top-K 添加元素时，可以使用同一个命令添加多个元素或只添加一个元素。然后，我们可以获取我们添加的任何元素的计数。
但是，当我们使用 `query` 时，我们只能找出我们查询的元素是否在我们指定的 Top-K 元素中。例如，我们将 ‘topk’ 初始化为只保存最小堆中的前 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 中最早出现的数据结构之一，它对添加的唯一项目的数量进行概率计数。与布隆过滤器类似，这种数据结构通过哈希函数运行项目，然后在一种位域中设置位。同样，与布隆过滤器类似，这种结构不保留有关被添加的单个项目的信息，因此这里没有删除操作。这种数据结构没有提供很多命令，使其比其他数据结构更容易使用。只有添加、计数、合并和两个测试命令，我们可以轻松地看到你能做什么。你可以向它添加元素，获取已添加的唯一元素数量的计数，并将它们合并在一起。将它们合并在一起将得到一个仅包含每个 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 做些什么。
