布隆过滤器是一种概率数据结构,它告诉我们元素要么肯定不在集合中,要么可能在集合中。与 Hashmap 相比,Bloom filter 占用的空间更少(取决于配置的哈希函数和错误率)。Hashmap 可以确定一个元素是否存在,而bloomfilter 只能确定性地检查一个元素是否不存在。
让我们看一下 Google Chrome 用例。当用户输入一个 URL 时,它应该验证该 URL 是否安全。为了验证 URL,chrome 可以调用 google 服务(内部 google 可以维护任何数据结构来找出这一点)。然而,这种方法的挑战是多方面的。对于在 chrome 上提供的每个 URL 请求,URL 验证都是通过 Google 服务器进行的,这增加了对 google 服务器的额外依赖、网络往返时间以及保持高可用性以验证所有 URL 的要求来自世界各地的 chrome 浏览器的 URL。
由于此数据不会经常更改(可能会在一小时左右更新),因此 chrome 可能已考虑将所有恶意站点数据捆绑为布隆过滤器,并且 google 可能会定期与客户端同步此数据(与恶意站点相比,恶意站点较少)完整的网站。)。当用户在 chrome 中打开一个 url 时,如果该 URL 不存在,它会检查布隆过滤器,它是安全的。如果存在,则布隆过滤器不确定,因此流量会转到谷歌服务器进行验证(与路由所有流量相比,此流量会少得多)。