大数据处理利器:布鲁姆过滤器

工欲善其事,必先利其器。在大数据时代,海量数据快速查询是关键需求,支撑基于AI的智慧计算。布鲁姆过滤器(Bloom Filter)是一种空间紧凑、快速查询的数据结构,广泛应用于网络和存储领域。

问题

布鲁姆过滤器解决一个简单的查询问题:数据是否在一个数据集中?例如,在一个10亿数据集中,查询数据x是否在该数据集中。因此,面临两个问题:首先,如何高效存储一个海量(10亿)数据集?其次,如何快速查询数据是否在该数据集中?

应用场景

网络应用:在防火墙中,网络管理员制订一份黑名单(即一个非法网址的数据集),阻止用户的非法网址请求。对于每个网址请求,查询该网址是否在黑名单中,如果在黑名单中,丢弃该网址请求;否则,转发该网址请求至服务器。

存储应用:存储系统缓存已访问的数据在数据缓存中,加速用户的数据请求响应。对于每个数据请求,查询该数据是否在缓存中,如果在该缓存中,返回缓存数据给用户;否则,访问数据存储中的数据,加载至缓存,并响应该数据请求。

原理

布鲁姆过滤器是一种位图数据结构,采用哈希映射存储一个数据集。例如,一个数据集包含n个数据,布鲁姆过滤器采用k个哈希函数映射n个数据到一个m比特的位图。布鲁姆过滤器的存储开销小(即m/n)、查询速度快(k次存储访问)。数据的类型可以是整数,也可以是字符串,或者其他任何类型。

插入算法

当插入数据时,布鲁姆过滤器采用k个哈希函数,计算该数据映射的k个位置,并设置该k个比特为1。当多个数据哈希映射到同一个位置时,该比特仅一次置为1。

查询算法

当查询数据时,布鲁姆过滤器采用相同k个哈希函数,计算该数据映射的k个位置,并检查该k个比特是否均为1。如果k个比特均为1,该数据在数据集中;如果至少1个比特为0,该数据不在数据集中。当查询数据不在数据集中,但是该数据映射的k个比特均为1,布鲁姆过滤器的查询产生假阳性错误,其原因是位图的一个比特可被多个数据置为1。在实际应用中,布鲁姆过滤器的假阳性错误率非常低(低于千分之一),是可容忍和可调整的。

总结

布鲁姆过滤器具有存储开销小、近似查询快等特性。例如,给定假阳性错误率为0.1%,布鲁姆过滤器采用10个哈希函数,每个数据的存储开销为14.4比特。布鲁姆过滤器加速大数据处理性能,减少不必要的数据处理。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181113A06JXK00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券