你好世界！我叫 Savannah，是 Redis 的一名新晋开发者倡导者。我跳上直播与我们的高级开发倡导者 Justin 和 Guy 讨论RedisJSON ，讨论概率数据结构。与 Guy 的探索在 Twitch 上是短暂的，但我最近使用一些您可以在YouTube 上观看的概率数据结构进行了一些编码。关于什么是概率数据结构可能会有一些混淆，所以我想我会花一些时间来写出这些采用大型数据集的数据结构的亮点。
Google Chrome、Akami 和您的 ISP 可能会使用某些类型的概率数据结构来做可以改善您作为最终用户的生活的事情。因此，如果您有大型数据集，认为数据结构很酷，或者想看看那些大牌会在哪里使用这些东西，请继续阅读！
下载我们的白皮书“ Redis HyperLogLog: A Deep Dive ”。
Redis 提供了一些不同的概率数据结构——一些在RedisBloom模块中（包含在我选择的语言 redis-py 中）和一个在核心 Redis 中，但是RedisBloom现在包含在所有客户端库中，因此无需如果您使用的是Redis Stack ，请导入其他任何内容。在这篇文章中，我将介绍Bloom 过滤器、布谷鸟过滤器、Top-K、Count-Min Sketch和Hyperloglog。我们将介绍每种方法的概率性质、它们如何工作的高级 概述以及一些关键用例。我们将从这些代码示例的以下 Redis 连接和定义开始。
r = redis.Redis(
host='localhost',
port=6379,
db=0,
decode_responses=True
)
布隆过滤器
以第一个写下这个想法的人命名，布隆过滤器可以告诉我们概率成员，即过滤器中是否添加了一些东西。
布隆过滤器作为位数组工作，在其中添加项目并设置某些位。这可能有重叠；但是，多个事物可以映射到一些相同的位。除非已经设置了它们对应的所有位，否则这些项目将毫无问题地添加到过滤器中，在这种情况下，响应是该项目可能已经添加到过滤器中。由于未设置位表示尚未添加项目，因此没有误报。
但是，由于不同项目的位重叠以及布隆过滤器不存储有关已添加内容的任何信息这一事实，因此没有删除。我们将展示如何创建我们的 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 过滤器的信息、保存和加载它以及其他一些命令。但是创建它、添加东西并检查这些东西是否存在是完成布隆过滤器的主要目的所需要的。
这些过滤器可用于快速代替大型数据集的测试集成员资格。例如，Google Chrome 浏览器维护恶意 URL 的 Bloom 过滤器。当有人尝试在 Chrome 中访问网站时，浏览器首先会检查 Bloom 过滤器。由于没有误报，如果过滤器返回它不存在，Chrome 允许用户快速访问 URL，而无需检查大型数据集。因为 Bloom 过滤器只是位数组，它们通常可以存储在浏览器缓存中，从而节省大型和远距离数据库查找的时间。
除了我上面解释过的标准 Bloom 过滤器之外，Redis 实现还可以选择成为 Scaling Bloom 过滤器。多年来，人们在 Bloom 过滤器中添加了一些不同的东西，添加了不同的功能，同时主要保持了核心思想。例如，稳定的布隆过滤器可以更好地处理无界数据而无需扩展，但可能会引入假阴性。其他类型的布隆过滤器包括计数布隆过滤器、分布式布隆过滤器、分层布隆过滤器等。
布谷鸟过滤器
布谷鸟过滤器以一种著名的将其他鸟的蛋从巢中推出并接管它们的鸟命名，它也告诉我们概率成员资格，但与布隆过滤器的方式非常不同。
Cuckoo 过滤器保留每个已添加项目的指纹，并在每个存储桶中存储多个指纹。指纹的长度（以位为单位）决定了发生冲突的速度，这有助于确定您需要的存储桶数量以及可以获得的错误率。当发生碰撞时，桶中的一个指纹将被踢出并放入另一个桶中，因此得名。
因为存储了指纹，所以布谷鸟过滤器确实支持删除。但是，冲突仍然存在，您最终可能会删除一些您不想删除的内容，这可能会导致一些误报。与 Bloom 过滤器一样，我们要做的主要事情是创建一个，向其中添加内容，并检查它们是否存在。但是，我们必须使用 insert 命令向 cuckoo 过滤器添加多个内容。cuckoo过滤器还有一个命令，用于添加不存在的项目：addnx。
但是，由于 exists 命令是概率性的，尝试删除以这种方式添加的项目可能会导致误报。在这里，我们将看到 mexists 的概率输出与 Bloom 过滤器相同。
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
布谷鸟过滤器的主要优点是删除条目的能力，除了必要的情况外，通常使用布隆过滤器。
计数-最小值草图
就像草图是粗略的绘图一样，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。
在这段代码中，我不再能够看到以前在 cms1 中的内容，但我仍然可以使用原来的 cms2。我还可以创建一个新的 Count-Min Sketch cms3（具有相同的尺寸），然后将 cms1 和 cms2 合并到 cms3 中，保留 cms1 和 cms2 的原始数据。
查询 baz 的输出是 6，因为我们使用了带有 2 和权重 3 的 incrby。但是，一旦添加了大量的东西，这个计数就会变得不那么准确。
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
当存储每个项目变得不切实际时，此数据结构可用于大量数据，因为您只存储一个数字表，而不是存储项目是什么。然后，您可以查询任何给定项目已添加了多少次，并获取它映射到的空间的最小计数，根据发生的碰撞次数，该空间可能仍会略微膨胀。
前K
Top-K 数据结构以其功能命名，将为您提供存储在其中的 Top-K 计数的近似值。
这里有两种数据结构；一个跟踪指纹及其计数的表和一个跟踪表中 Top-K 事物的最小堆结构。表中的每一行代表正在使用的不同哈希函数，因此添加的每个项目都会被哈希到每一行中的一个点。特别是 Redis 的实现使用了一种称为 HeavyKeeper 的算法。使用这种算法，基本思想是每当指纹之间发生冲突时，已有指纹的计数有可能会减少。这意味着大量添加的项目具有高计数和低衰减概率，而没有添加的项目将随着时间的推移被覆盖。
要了解有关可用Top-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。
作为 Redis 中最早可用的数据结构之一，HyperLogLog 保留了添加了多少唯一项的概率计数。与布隆过滤器一样，这种数据结构通过散列函数运行项目，然后在一种位域中设置位。此外，与 Bloom 过滤器一样，此结构不会保留有关 正在添加的单个项目的信息，因此这里没有删除。这种数据结构没有太多可用的命令，因此比其他数据结构更容易使用。仅使用 add、count、merge 和两个测试命令，我们可以轻松了解您可以做什么。您可以向其中添加东西，计算有多少独特的东西已被添加，并将它们合并在一起。将它们合并在一起将产生一个 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 做什么。
原文标题：Probabilistic Data Structures in Redis
原文作者：Savannah Norem
原文地址：https://redis.com/blog/streaming-analytics-with-probabilistic-data-structures/
