文档章节

谈谈布隆过滤器(Bloom Filter)

tiankonguse
 tiankonguse
发布于 2017/03/20 00:07
字数 2247
阅读 62
收藏 0

零、背景

声明
这篇文章从公众号tiankonguse-code自动同步过来.
如果转载请加上署名:公众号tiankonguse-code. 并附上公众号二维码.

 

笔者多年前看编程之美时就了解过Bloom Filter, 但是当时作为一个搞算法的ACMer, 感觉这个算法没啥的, 就是一个hash, 工作中用到了对应的思想,这里简单记录一下.

 

之前在tiankonguse-code公众号里 《字符串hash函数的本质》介绍了hash算法, 其实是为它的兄弟Bloom Filter做准备的.

这篇文章以一个问题开始慢慢讲解Bloom Filter是如何诞生的.

 

一、问题之用户是否已存在

假设你有一个网站, 用户名是邮箱.
新用户注册的时候我们需要判断这个邮箱是否已经注册过.

 

假设我们希望在内存中来计算这个问题, 该如何计算呢?
大家第一时间想到的是set或者map<string, int>来打标记吧.

 

是的, 我大学ACM比赛的时候,对于字符串为key的问题大多数情况下都是通过set和map来标记这个key是否存在过.
这个算法很好, 但是存在一个问题: 数据量大了怎么办?


假设我们一个邮箱的平均长度是20字节,我们最多有10亿的用户, 则我们至少需要200亿(20G)的内存.
所以我们需要换个办法来打这个标记.

 

二、假设我们有牛逼的hash算法

假设我们有一个牛逼的hash算法, 一亿的邮箱可以hash出10亿内不同的值, 我们可以使用数组来储存数据, 0代表不存在,1代表存在.
这个时候我们只需要10亿乘以4字节即40亿(4G)的内存了.

 

然后很多人会想到可以只是一字节甚至使用位压缩来储存数据.
使用一字节的含义是10亿数组的类型是uint8类型的, 此时需要内存10亿(1G).
而位压缩的含义是一个整数的每一位都用来储存数据,则需要内存1.25亿(125M).

位压缩在ACM中也很常见,都是使用数组自己实现的, 虽然STL中已经有bitset.

 

使用位压缩我们已经把内存缩小到125M了, 前提是我们有一个很牛逼的hash算法.

 

事实上我们没有, 所以这个方法存在一个缺陷: 我们可能很大概率返回错的答案.
比如一个邮箱不存在, 但是hash出来的值与一个已存在的相同, 则我们没办法区分这两种情况.

hash冲突是一个概率问题, 当我们能够容忍这个问题是, 我们就能够解决一些问题了.

 

比如 tiankonguse-code 的公众号文章在《每秒千万级别的量是重生还是炼狱?》的 热key再次优化 中介绍过.


下面是原文:

 

之前的热key是直接使用多阶hash共享内存库实现的, key是字符串, 查找还是消耗性能的, 并且key的计数更新规则也存在问题.

为了性能, 自己写了一个基于共享内存的热key库, 实际储存会对key进行hash映射取模, 然后直接使用下标找到对应的数据.


对于计数规则, 原先是到达周期,按比例缩小, 计数波动较大, 优化后分成环, 环内计数求和, 大大提高计数稳定性, 不过对于冲突的key,按相同key处理了 .

PS: 这个之前也进入TOP10瓶颈点了,优化后性能完全可以忽略了。

 

可见虽然hash冲突这个问题没办法避免, 但是还是有些使用场景的.

其实我们看到这里可以对hash总结出两个结论:

 

  1. 如果账号存在, 则我们不可能查询为不存在

  2. 如果账号不存在, 则有概率查询为存在

三、降低hash冲突的概率

上面面临的问题是hash有时候会冲突, 如果这个概率不能接受, 我们就需要优化算法来降低冲突概率了.
很容易想到的是使用不同的hash算法多hash几个值, 是的, 就是这个方法.

 

我们hash一个值冲突的概率假设都是百分之一, 则hash两个值都冲突的概率就是万分之一.


当然这里考虑两个hash是有顺序(排列)的, 如果没有循序(组合)的话, 概率也不超过万分之5.
而且我们hash的个数越多, 冲突概率越小, 当然对应成本可能也越高.

 

这个方法其实在 tiankonguse-code 的公众号文章《每秒千万级别的量是重生还是炼狱?》 的小节中 设计缓存库与缓存策略 也谈到过.


原文如下:

 

关于缓存,之前在《谈谈cache》(公众号tiankonguse-code回复1704查看文章)曾介绍了很多策略与实践遇到各种问题。


而现在主要面临一个问题: 共享内存纯粹使用多阶HASH实现,key和value共存,内存使用率极低,性能也存在很多问题。
于是就有了下面的一系列优化了。 
… 
第三件事是对key生成多个不同的hash值,避免key冲突时进行字符串比较。


实践证明两三次就过滤所有冲突了,第三次hash和key长度的兜底比较一天也只有几次。

而我们面对判断邮箱是否存在的问题, 也可以hash出多个值, 然后对应位置设置为1, 查询时都为1才说明存在.
而Bloom Filter的核心思想就是hash出多个值来代替普通bitset的一个值.

 

当我们通过hash多个值的时候, 大大的降低了冲突的概率, 所以我们也可以适当的降低我们位压缩的内存大小了.


之前10亿用户位压缩需要内存1.25亿(125M), 现在我们可以使用1.25千万内存(12.5M)来储存数据.


这个需要多少个hash值与最终我们使用多大的内存是有科学公式的, 这里就不深入计算了,有兴趣的可以翻墙查看wiki.

 

四、如何hash多个值

这个问题很多人原始想法是找多个hash函数不就行了吗?
但是假设我们hash出20个值, 你能去找20个函数吗?

 

所以我们需要换个方法, 看看hash的本质是什么.
tiankonguse-code公众号的文章《字符串hash函数的本质》介绍了本质:

 

hash函数的本质是扫描字符串过程中, 根据之前的结果, 当前位置,当前字符的值使用一个公式计算出当前结果. 


当然稍微复杂的hash算法会考虑之前所有的的结果,位置以及字符, 甚至会迭代多次.

其实本质里面已经说了方法了: 迭代多次.
看到这里如果还没明白的话, 只能don't talk, show me code了.

 

五、产品说允许删除账号

我们通过hash出多个值降低了冲突的概率, 但是还面临着一个问题: 我们没办法删除数据.
这个时候我们需要先看看Bloom Filter的本质: 通过若干位的值是否都是1来判断对应的数据是否存在.

 

删除的话不能简单的都置为0,因为这样可能影响很多数据的,本来存在的查询为不存在,违背上面的两大结论了.

 

当然说到删除, 大家也会想到一个方法: 计数.
我们使用多位来储存一个值, 每次添加数据就加1.
这个是个不错的方法.

 

加上我们使用一字节来储存一个值, 则需要1亿万内存(100M)来储存数据. 
这个内存实际上很小了, 所以我们也可以接受.
唯一的缺点就是我们最多允许冲突255次, 而我们使用两字节,则允许65535次冲突, 达到这个的概率将很小很小了.

 

六、参考资料

  1. wiki Bloom filter

  2. 数学之美系列二十一 - 布隆过滤器

     

七、其他文章

UNION架构篇  UNION优化篇  UNION诞生篇   union运营篇 谈谈cache 浪潮之巅 排名算法 hash

 

八、关于作者

曾是一名ACMer, 现在是鹅长视频部门的后台开发

这里主要记录工作中的技术架构与经验,计算机相关的技术,数学、算法、生活上好玩的东西

长按二维码关注作者, 了解作者发布的最新好玩的东西

 

© 著作权归作者所有

tiankonguse
粉丝 0
博文 15
码字总数 26545
作品 0
深圳
程序员
私信 提问
布隆过滤器之Counting Bloom Filter

---title: 布隆过滤器之Counting Bloom Filtersubtitle: Counting Bloom Filterdescription: Spectral Bloom Filterkeywords: [算法,bloom filter,布隆]author: liyzdate: 2019-01-11tags: ......

freeli
01/14
181
0
布隆过滤器(Bloom Filter)

基本概念 如果想判断一个元素是不是在一个集合里,一般想到的是将所有元素保存起来,然后通过比较确定。链表、树、散列表(又叫哈希表,Hash table)等等数据结构都是这种思路。但是随着集合...

行者PHPer
2014/04/12
206
0
如何实现大数据集查询?Bloom Filter或许是你想要的

1、什么情况下需要布隆过滤器? 先来看几个比较常见的例子 字处理软件中,需要检查一个英语单词是否拼写正确 在 FBI,一个嫌疑人的名字是否已经在嫌疑名单上 在网络爬虫里,一个网址是否被访...

流川枫AI
2017/06/18
0
0
浅谈布隆过滤器Bloom Filter

先从一道面试题开始: 给A,B两个文件,各存放50亿条URL,每条URL占用64字节,内存限制是4G,让你找出A,B文件共同的URL。 这个问题的本质在于判断一个元素是否在一个集合中。哈希表以O(1)的时...

再见紫罗兰
08/03
0
0
Bloom filter在分布式环境中的应用

Bloom filter在分布式环境中的应用 未命名2017-05-0427 阅读 filter技术分布式 概述 布隆过滤器是一个应用非常广泛的概率型数据结构,一般用于判断一个元素是否存在一个集合中,比如在字处理...

未命名
2017/05/04
0
0

没有更多内容

加载失败,请刷新页面

加载更多

32位与64位Linux系统下各类型长度对比

64 位的优点:64 位的应用程序可以直接访问 4EB 的内存和文件大小最大达到4 EB(2 的 63 次幂);可以访问大型数据库。本文介绍的是64位下C语言开发程序注意事项。 1. 32 位和 64 位C数据类型...

mskk
20分钟前
5
0
Vue 实现点击空白处隐藏某节点(三种方式:指令、普通、遮罩)

在项目中往往会有这样的需求: 弹出框(或Popover)在 show 后,点击空白处可以将其 hide。 针对此需求,整理了三种实现方式,大家按实际情况选择。 当然,我们做项目肯定会用到 UI 框架,常...

张兴华ZHero
26分钟前
7
0
SpringBoot激活profiles你知道几种方式?

多环境是最常见的配置隔离方式之一,可以根据不同的运行环境提供不同的配置信息来应对不同的业务场景,在SpringBoot内支持了多种配置隔离的方式,可以激活单个或者多个配置文件。 激活Profi...

恒宇少年
28分钟前
7
0
PDF修改文字的方法有哪些?怎么修改PDF文件中的文字

PDF修改文字一直以来都是一个难以解决的问题,很多的办公族在办公的时候会有修改PDF文件中的文字的需要,可是PDF文件一般是不能进行编辑和修改的,难道就没有什么办法解决这个问题了嘛?不要...

趣味办公社
31分钟前
4
0
企业组织中采用服务网格的挑战

作者:Christian Posta 译者:罗广明 原文:https://blog.christianposta.com/challenges-of-adopting-service-mesh-in-enterprise-organizations/ 编者按 本文作者介绍了企业组织采用服务网...

jimmysong
40分钟前
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部