系统设计：布隆过滤器

原文towardsdatascience.com/system-design-bloom-filter-a2e19dcd4810https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/350b777cef6f9090c441e88a64b5066c.png简介哈希表是最广为人知和使用的几种数据结构之一。通过明智地选择哈希函数哈希表可以在常数时间内产生插入、搜索和删除查询的最佳性能。哈希表的主要缺点是潜在的冲突。为了避免冲突一种标准方法包括增加哈希表的大小。虽然这种方法在大多数情况下效果良好但有时我们仍然在使用大量内存空间方面受到限制。必须记住哈希表始终对任何查询提供正确响应。它可能会遇到冲突并且有时会变慢但它始终****保证 100%的正确响应。结果发现在某些系统中我们并不总是需要从查询中收到正确信息。这种准确性的降低可以用来关注改进系统的其他方面。在这篇文章中我们将发现一种名为布隆过滤器的创新数据结构。简单来说它是一种标准哈希表的修改版本它以牺牲少量准确性为代价来换取内存空间的增加。布隆过滤器布隆过滤器以大小为 m 的布尔数组的形式组织。最初其所有元素都被标记为 0假。除此之外还需要选择 k 个哈希函数这些函数以对象为输入并将它们映射到范围[0, m – 1]。每个输出值将后来对应于该索引处的数组元素。为了获得更好的结果建议哈希函数输出值其分布接近均匀。…/Images/7dba5ee0846bd115fe72bc134613d834.png在我们的例子中我们将使用大小为 m 13 且 k 3 个哈希函数的布隆过滤器。这些函数中的每一个都将输入对象映射到范围[0, 12]。插入每当需要添加一个新的对象时它将通过 k 个预定义的哈希函数。对于每个输出的哈希值该索引处的相应元素变为 1真。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/3e5eabb3a50f512d1340ec5bff493439.png“香蕉”对象被添加到布隆过滤器中。哈希函数输出的值是 6、2 和 9。那些索引处的数组元素变为 1。如果从哈希函数输出的数组元素的索引已经被设置为 1那么它就简单地保持为 1。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/89944f4964055253a1fef694708c4226.png“苹果”对象被添加到布隆过滤器中。数组索引为 10、9 和 4 的元素被分配为 1。即使数组的第 9 个元素已经被分配为 1其值在这里也不会改变。事实上任何数组元素上 1 的存在都充当了一个部分证据表明实际哈希到相应数组索引的元素确实存在于布隆过滤器中。搜索要检查一个对象是否存在需要计算其 k 个哈希值。可能有两种情况如果至少有一个哈希值对应的数组元素等于 0这意味着对象不存在。在插入过程中一个对象会与多个标记为 1 的数组元素相关联。如果一个对象确实存在于过滤器中那么所有的哈希函数都会确定性地输出指向 1 的相同序列的索引。然而指向值为 0 的数组元素显然表明当前对象不存在于数据结构中。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/29ed491a69dc07f6ddbf6370d2b3e067.png检查“橙子”对象是否存在于布隆过滤器中。由于至少有一个哈希函数在我们的情况下恰好是两个输出数组索引7 和 12该数组的元素等于 0这意味着“橙子”不存在于过滤器中。如果对于所有哈希值相应的数组元素都等于 1这意味着对象****可能存在不是 100%。正是这一陈述使得布隆过滤器成为一个概率数据结构。如果一个对象之前被添加过那么在搜索过程中布隆过滤器保证该对象的哈希值将与之前相同因此可以找到该对象。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/4080375783a28508c39ed9dc034f8e34.png检查“香蕉”对象是否存在于布隆过滤器中。由于哈希函数是确定的它们输出与之前在插入“香蕉”时使用的完全相同的数组位置。因此“香蕉”存在于过滤器中。尽管如此当对象实际上不存在但 Bloom 过滤器声称存在时Bloom 过滤器可以产生误报响应。这种情况发生在所有针对该对象的哈希函数返回的哈希值都对应于过滤器中已插入的其他对象的数组元素值 1 时。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/8ec2cf705980c8e6857abe68c7180a90.png误报响应的示例。尽管“cherry”之前没有被添加但过滤器认为它存在因为“cherry”的所有输出哈希值都指向值为 1 的数组元素。当插入的对象数量相对于 Bloom 过滤器数组的尺寸较高时容易出现误报答案。误报错误估计在给定 Bloom 过滤器的结构的情况下可以估计得到误报错误概率。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/c58f6a7eae7bf5057bc61638a5f80f3b.png作者采用的图像。来源Bloom 过滤器 | 维基百科该公式的完整证明可以在维基百科上找到。基于该表达式我们可以做出一些有趣的观察随着哈希函数数量 k 的增加、数组大小 m 的增加和插入对象数量 n 的减少FP 概率降低。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/5c945c50a37332233f18bb50f2c57f91.pngk 值增加、m 值增加或 n 值减少导致 FP 率降低在将对象插入 Bloom 过滤器之前如果我们知道数组大小 m并且可以估计未来将插入的对象数量 n我们可以找到将最小化 FP 概率所需的最佳哈希函数数量 k。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/19fa842627470e7b68db235309b004ac.png最小化 FP 概率的最佳哈希函数数量 k降低 FP 概率的另一种方法是几个独立 Bloom 过滤器AND 连接的组合。只有当一个元素存在于所有 Bloom 过滤器中时才最终认为该元素存在于数据结构中。约束条件与哈希表不同Bloom 过滤器的标准实现不支持删除。在开始时选择的哈希函数数量 k 和数组大小 m 之后不能更改。如果有这样的需求唯一的方法是通过插入所有先前存储的对象来构建具有新设置的另一个 Bloom 过滤器。应用根据维基百科页面Bloom 过滤器在大型系统中被广泛使用类似于Apache HBase、Apache Cassandra和PostgreSQL的数据库使用布隆过滤器来检查不存在的行或列。这种方法比使用磁盘查找要快得多。Medium使用布隆过滤器来过滤掉已经向用户推荐过的页面。Google Chrome以前使用布隆过滤器来识别恶意网址。如果一个网址在布隆过滤器中返回负响应则认为它是安全的。否则将执行完整的检查。https://github.com/OpenDocCN/towardsdatascience-blog-zh-2024/raw/master/docs/img/c3414d2a7c8ab83f2ac9084e02abe344.pngGoogle 用于检查恶意网址的算法。使用布隆过滤器可以显著减少对大量安全链接所需进行的更多计算量大的完整检查。结论在本文中我们介绍了一种构建哈希表的替代方法。当可以牺牲少量准确性以换取更有效的内存使用时布隆过滤器在许多分布式系统中成为了一种稳健的解决方案。通过调整布隆过滤器大小的哈希函数数量我们可以找到准确性和性能要求之间最合适的平衡。资源布隆过滤器 | 维基百科布隆过滤器计算器所有图像除非另有说明均为作者所有。