algorithm - 布隆过滤器使用

Question

我正在努力理解布隆过滤器的有用性。我得到了它的基本逻辑、空间压缩、快速查找、误报等。我只是不能把这个概念放到现实生活中，因为它是有益的。一种常见的应用是在 Web 缓存中使用布隆过滤器。我们使用布隆过滤器来确定给定的 URL 是否在缓存中。为什么我们不简单地访问缓存来确定呢？如果我们得到一个是，我们仍然需要去缓存来检索网页（可能不存在），但如果不是，我们可以使用缓存得到相同的答案（这可能为快速查找而优化反正？）。

Answer 1

布隆过滤器设计用于误报是非常糟糕的事情并且误报是可以接受的情况。

例如，假设您正在制作 Web 浏览器并且拥有已知的诈骗网站黑名单。您的黑名单非常庞大 - 以数百 GB 为单位 - 因此您无法将其与浏览器一起发布。但是，您可以将其存储在您自己的服务器上。在这种情况下，您可以为浏览器提供一个包含所有 URL 的适当大小的 Bloom 过滤器。在访问一个站点之前，您在过滤器中查找它。然后，如果您得到“否”的回答，则可以保证该 URL 没有被列入黑名单并且可以访问该站点。如果您得到“是”的答案，则该站点可能是邪恶的，因此您可以让浏览器调用您的主服务器以获得真正的答案。在不牺牲准确性的情况下，您可以在此处保存对服务器的大量调用，这一事实很重要。

缓存的想法与此设置类似。您可以查询过滤器以查看页面是否在缓存中。如果您得到“否”的答案，则可以保证它没有被缓存，并且可以执行昂贵的操作来从主源中提取数据。否则，您可以检查缓存以查看它是否真的存在。在极少数情况下，您可能需要检查缓存，看看它不存在，然后从主源中提取，但您永远不会意外错过缓存中的某些内容。

希望这可以帮助！

Answer 2

当满足以下两个条件时，布隆过滤器可能很有用：

• 假阴性是不可接受的
• 相对于 Bloom Filter 中的查找成本，查找成本较高

第一点非常简单。当布隆过滤器可以存储在主内存中时，第二点通常变得很重要，但实际查找可能会导致数据库命中，相对于在键上执行一定数量的哈希然后在内存中查找（即布隆过滤器）。

如果仅满足上述条件之一，则布隆过滤器不是解决问题的最佳方案。

当人们可以消除昂贵的查找时，就会节省成本，因为众所周知，不可能找到匹配项。这是第一个点的值 - 布隆过滤器不会产生误报，因此如果在过滤器中未找到匹配项，则没有必要进入下一个更昂贵的步骤，即检索与键关联的数据。

当过滤器命中时，需要进行昂贵的查找来验证命中（消除误报）并检索相关数据。这里有可能由于误报而找不到任何东西，这就是为什么需要调整过滤器以将这种风险降至可接受的水平。功能性布隆过滤器必须具有低误报率，因此查找的总体成本仍然很低。

现在，如您所说，如果您的缓存已经针对快速查找进行了优化，那么布隆过滤器的实用性可能会存在问题。

Answer 3

问题是你的例子不是很好。

在 web 缓存中，如果 url 不存在，无论如何您都必须对网络进行昂贵的调用，因此节省磁盘访问并不是什么大问题。因此，您对此提出质疑是正确的（并且 Diego Basch 的评论没有经过深思熟虑，恕我直言）。

所以我去寻找你为什么使用那个例子。事实证明，维基百科文章提到鱿鱼网络缓存使用布隆过滤器。但它们没有按照您描述的方式使用。相反，它们用于决定从一组分布式缓存中选择哪个缓存。并且它们主要用于节省空间（因为 squid 可以缓存很多对象，所以这些表会非常大）。

有关 squid 和布隆过滤器的更多信息，请参阅http://wiki.squid-cache.org/SquidFaq/CacheDigests

否则，来自 templatetypedef 的另一个答案很好 - 检查坏网站是一个更好的例子。