先贴一段生产环境里的代码。这是一个活动弹窗通知的配置新活动上线后要给会员弹窗口每个用户只弹一次不能重复弹。publicstaticclassPopupBloomFilterConfig{// 弹窗持续5天过滤器过期时间 弹窗天数 1publicstaticfinallongEXPIRE60*60*24*6;// 预期数据量参考会员总数publicstaticfinallongEXPECTED_SIZE30000000;// 误判率1%publicstaticfinaldoubleFALSE_PROBABILITY0.01;}三个参数预期数据量3000万误判率1%过期时间6天。用的是Redisson的布隆过滤器初始化代码长这样RBloomFilterObjectbloomFilterredissonClient.getBloomFilter(key);if(!bloomFilter.isExists()){bloomFilter.tryInit(expectedInsertions,falseProbability);bloomFilter.expire(expire,TimeUnit.SECONDS);}用户在请求进来时先拿用户ID去布隆过滤器里查一下。返回false说明这个用户还没弹过窗执行弹窗逻辑然后把用户ID写进过滤器。返回true说明已经弹过了跳过。这就是布隆过滤器在生产环境里最常见的用法海量数据的存在性判断。这个问题还能怎么解看完上面的代码一个自然的问题是不用布隆过滤器行不行3000万用户要记住谁看过弹窗最直接的方案是用HashSet存用户ID。Java里一个Long对象加上HashSet内部的Node结构、对象头、数组开销3000万条数据大约要占700MB到1GB内存。如果是分布式环境还得把这个数据放到Redis里占用更大。另一个方案是查数据库。每次用户请求时查一次记录表看这个用户有没有弹窗记录。能跑但一个活动弹窗要扛住短时间内几千万次查询数据库压力很大。还可以用Redis的Bitmap。Bitmap用1个bit表示一个用户3000万用户大约占3.58MB空间很省。但Bitmap要求用户ID能直接映射到位数组的下标如果用户ID是连续的1、2、3…3000万Bitmap很合适。可实际业务中的用户ID往往跨度很大比如ID最大到了10亿位数组就得按10亿来分配实际只用了3000万个位大量空间浪费在没用的ID段上。布隆过滤器在这些方案之间找到了一个平衡点用接近Bitmap的空间开销做到可控误判率的存在性判断。3000万用户、1%误判率的配置下布隆过滤器大约只占35MB。布隆过滤器的原理布隆过滤器的底层结构就两样东西一个位数组和几个哈希函数。位数组就是一长串0和1每个位置只占1个bit。假设位数组长度是m初始状态全是0。写入一个元素的时候用k个哈希函数分别对这个元素做哈希运算每个哈希函数算出一个位置编号然后把位数组中对应位置的值设为1。比如用3个哈希函数元素A算出来的位置是2、7、15那就把位数组的第2位、第7位、第15位都设成1。查询一个元素是否存在同样用这k个哈希函数算出k个位置检查这些位置是否全是1。全是1判断为存在只要有一个是0判断为不存在。这个设计有一个好处判断不存在是100%准确的。因为一个元素如果真的写入过它的k个位置一定都是1。只要有任何一个位置是0说明这个元素肯定没写入过。而且布隆过滤器只会把0变成1从来不会把1重新变回0所以一个已经写入的元素不会因为后续插入其他元素而丢失。不存在假阴性。为什么会有误判布隆过滤器的误判只有一种方向一个本来不存在的元素被判断为存在。这种情况叫假阳性。原因不难想。位数组的位数是有限的不同元素经过哈希运算后可能在某些位置上重叠。比如元素A把第2、7、15位设成了1元素B把第5、7、20位设成了1。这时候来查元素C如果C算出来的位置刚好是2、5、7这三个位置都已经被A和B设为1了布隆过滤器就会误认为C存在。前面生产配置里的1%误判率意思就是查100个确实不存在的元素大约有1个会被误判为存在。在弹窗场景里误判的后果是漏弹某些还没弹过窗的用户被误判为已弹过返回true就不会收到弹窗。对弹窗通知这种场景来说漏掉一些用户的通知问题不大所以1%是可接受的。布隆过滤器的判断有一个不对称性说不存在一定准确说存在有一定概率是误判。这个特性决定了它适合那些能容忍少量漏判、不能容忍误放的场景。对应到布隆过滤器的术语假阳性误判为存在就是漏弹能忍假阴性误判为不存在就是多弹不能忍。弹窗通知就是典型例子漏弹几个用户问题不大但已经弹过的用户再弹一次用户会觉得系统在出bug。三个关键参数怎么定生产代码里那三个参数不是随便填的每个都有讲究。位数组的大小不是拍脑袋定的背后有一个公式m -n * ln§ / (ln2)^2。其中n是预期数据量p是误判率。Redisson内部就是根据预期数据量和误判率用这个公式自动计算位数组大小。后面速查表里的数字都是这个公式算出来的。预期数据量expectedInsertions。这个数字决定了位数组的长度。定小了实际存入的元素超过预期位数组会越来越密误判率会远超设定值。宁可按偏大的值来估。实际项目中如果会员数是2500万定3000万是合理的留一些余量。误判率falseProbability。误判率越低需要的位数组越大空间成本越高。几个常见取值对应的空间开销差异很明显1%3000万数据约占35MB0.1%3000万数据约占52MB0.01%3000万数据约占70MB从1%降到0.1%空间多用了差不多50%。大多数业务场景下1%够用了对准确性要求更高的场景可以设到0.1%或0.01%。过期时间expire。这个参数跟布隆过滤器本身的原理无关但在实际项目里很关键。布隆过滤器不支持删除单个元素但可以给整个过滤器设过期时间让系统自动回收。弹窗展示5天过期时间设6天。权益改版通知要持续1年过期时间就设365天。过期后过滤器自动清除下次请求时重新创建。下面这张速查表列出了不同参数组合下的位数组大小和哈希函数个数做技术选型时可以直接查数据量误判率位数组大小哈希函数个数内存占用100万1%958万位71.14MB100万0.1%1437万位101.71MB100万0.01%1917万位132.29MB1000万1%9585万位711.43MB1000万0.1%1.44亿位1017.13MB1000万0.01%1.92亿位1422.85MB3000万1%2.88亿位734.28MB3000万0.1%4.31亿位1051.38MB1亿1%9.59亿位7114.27MB1亿0.01%19.17亿位14228.54MB哈希函数个数的计算方式是 -(ln(误判率) / ln2)。误判率越低需要的哈希函数越多写入时的计算开销也越大。不能删除的问题布隆过滤器有一个经常被问到的限制不支持删除单个元素。原因在于位数组的位置是共享的。元素A占了第2、7、15位元素B占了第5、7、20位第7位是共用的。如果删除元素A把第2、7、15位清零第7位变成0元素B查询时就会发现第7位是0被误判为不存在。计数布隆过滤器Counting Bloom Filter是解决这个问题的一个变体。它把每个位从1bit的0/1改成一个计数器写入时计数器加1删除时计数器减1查询时检查计数器是否大于0。这样删除一个元素不会影响其他元素的判断。代价是空间翻了好几倍。原来每个位占1bit改成计数器后每个位至少占4bit。3000万数据量、1%误判率的配置下空间从35MB涨到140MB。实际项目中大多数场景用不着计数布隆过滤器。给整个过滤器设一个过期时间到期自动清除重建比维护单个元素的删除逻辑要省事。一些分布式存储系统在内部使用了支持删除的布隆过滤器变体但由于空间和维护成本更高普通业务中用得不算多。布隆过滤器不能无限写入布隆过滤器在初始化时位数组大小就已经固定了。随着不断写入元素越来越多的位被置为1。当写入量远超预期数据量时位数组会变得越来越密误判率也随之飙升。极端情况下如果位数组几乎全是1任何元素查进来都会被判为存在误判率接近100%布隆过滤器就失去了过滤的意义。所以布隆过滤器是一种容量固定的数据结构不是想加多少就加多少。生产环境在创建时就要估算好expectedInsertions留够余量。如果数据量真的超过了设计容量需要创建一个新的布隆过滤器来替换旧的。这也是为什么前面配置里的预期数据量会按会员总数的1.2到1.5倍来设定。实际项目中的两种用法Java生态里用布隆过滤器常见的有两个库。单机场景用Guava的BloomFilter。Guava提供了标准的创建接口指定预期数据量和误判率就行内部会自动计算位数组大小和哈希函数个数。单机部署时直接创建使用代码很简洁。分布式场景用Redisson的RBloomFilter。多个服务实例需要共享同一个布隆过滤器时单机版就不够用了因为每个实例各自维护一份位数组数据不互通。Redisson把布隆过滤器的数据存在Redis里所有实例都能读写同一份数据。前面贴的生产代码就是Redisson的方案。在实际项目里通常会在Redis层封装一层initBloomFilter和getBloomFilter处理过滤器不存在时的自动创建、分布式锁防止并发初始化这些细节。两种方案的选型依据就看部署方式单实例用Guava多实例用Redisson。小结布隆过滤器的价值在于用很小的空间代价解决海量数据的存在性判断问题。3000万条记录35MB内存就够了这个空间效率是HashSet这类数据结构做不到的。面试的时候把三个关键点讲明白就行位数组是存储结构多个哈希函数是写入和查询的机制假阳性是它区别于精确判断的核心特征。假阳性只有单方向判断不存在一定准确判断存在可能误判。做技术选型时多留意预期数据量这个参数。定小了会导致误判率飙升定大了浪费空间尽量提前估算准确。
先贴一段生产环境里的代码。这是一个活动弹窗通知的配置新活动上线后要给会员弹窗口每个用户只弹一次不能重复弹。publicstaticclassPopupBloomFilterConfig{// 弹窗持续5天过滤器过期时间 弹窗天数 1publicstaticfinallongEXPIRE60*60*24*6;// 预期数据量参考会员总数publicstaticfinallongEXPECTED_SIZE30000000;// 误判率1%publicstaticfinaldoubleFALSE_PROBABILITY0.01;}三个参数预期数据量3000万误判率1%过期时间6天。用的是Redisson的布隆过滤器初始化代码长这样RBloomFilterObjectbloomFilterredissonClient.getBloomFilter(key);if(!bloomFilter.isExists()){bloomFilter.tryInit(expectedInsertions,falseProbability);bloomFilter.expire(expire,TimeUnit.SECONDS);}用户在请求进来时先拿用户ID去布隆过滤器里查一下。返回false说明这个用户还没弹过窗执行弹窗逻辑然后把用户ID写进过滤器。返回true说明已经弹过了跳过。这就是布隆过滤器在生产环境里最常见的用法海量数据的存在性判断。这个问题还能怎么解看完上面的代码一个自然的问题是不用布隆过滤器行不行3000万用户要记住谁看过弹窗最直接的方案是用HashSet存用户ID。Java里一个Long对象加上HashSet内部的Node结构、对象头、数组开销3000万条数据大约要占700MB到1GB内存。如果是分布式环境还得把这个数据放到Redis里占用更大。另一个方案是查数据库。每次用户请求时查一次记录表看这个用户有没有弹窗记录。能跑但一个活动弹窗要扛住短时间内几千万次查询数据库压力很大。还可以用Redis的Bitmap。Bitmap用1个bit表示一个用户3000万用户大约占3.58MB空间很省。但Bitmap要求用户ID能直接映射到位数组的下标如果用户ID是连续的1、2、3…3000万Bitmap很合适。可实际业务中的用户ID往往跨度很大比如ID最大到了10亿位数组就得按10亿来分配实际只用了3000万个位大量空间浪费在没用的ID段上。布隆过滤器在这些方案之间找到了一个平衡点用接近Bitmap的空间开销做到可控误判率的存在性判断。3000万用户、1%误判率的配置下布隆过滤器大约只占35MB。布隆过滤器的原理布隆过滤器的底层结构就两样东西一个位数组和几个哈希函数。位数组就是一长串0和1每个位置只占1个bit。假设位数组长度是m初始状态全是0。写入一个元素的时候用k个哈希函数分别对这个元素做哈希运算每个哈希函数算出一个位置编号然后把位数组中对应位置的值设为1。比如用3个哈希函数元素A算出来的位置是2、7、15那就把位数组的第2位、第7位、第15位都设成1。查询一个元素是否存在同样用这k个哈希函数算出k个位置检查这些位置是否全是1。全是1判断为存在只要有一个是0判断为不存在。这个设计有一个好处判断不存在是100%准确的。因为一个元素如果真的写入过它的k个位置一定都是1。只要有任何一个位置是0说明这个元素肯定没写入过。而且布隆过滤器只会把0变成1从来不会把1重新变回0所以一个已经写入的元素不会因为后续插入其他元素而丢失。不存在假阴性。为什么会有误判布隆过滤器的误判只有一种方向一个本来不存在的元素被判断为存在。这种情况叫假阳性。原因不难想。位数组的位数是有限的不同元素经过哈希运算后可能在某些位置上重叠。比如元素A把第2、7、15位设成了1元素B把第5、7、20位设成了1。这时候来查元素C如果C算出来的位置刚好是2、5、7这三个位置都已经被A和B设为1了布隆过滤器就会误认为C存在。前面生产配置里的1%误判率意思就是查100个确实不存在的元素大约有1个会被误判为存在。在弹窗场景里误判的后果是漏弹某些还没弹过窗的用户被误判为已弹过返回true就不会收到弹窗。对弹窗通知这种场景来说漏掉一些用户的通知问题不大所以1%是可接受的。布隆过滤器的判断有一个不对称性说不存在一定准确说存在有一定概率是误判。这个特性决定了它适合那些能容忍少量漏判、不能容忍误放的场景。对应到布隆过滤器的术语假阳性误判为存在就是漏弹能忍假阴性误判为不存在就是多弹不能忍。弹窗通知就是典型例子漏弹几个用户问题不大但已经弹过的用户再弹一次用户会觉得系统在出bug。三个关键参数怎么定生产代码里那三个参数不是随便填的每个都有讲究。位数组的大小不是拍脑袋定的背后有一个公式m -n * ln§ / (ln2)^2。其中n是预期数据量p是误判率。Redisson内部就是根据预期数据量和误判率用这个公式自动计算位数组大小。后面速查表里的数字都是这个公式算出来的。预期数据量expectedInsertions。这个数字决定了位数组的长度。定小了实际存入的元素超过预期位数组会越来越密误判率会远超设定值。宁可按偏大的值来估。实际项目中如果会员数是2500万定3000万是合理的留一些余量。误判率falseProbability。误判率越低需要的位数组越大空间成本越高。几个常见取值对应的空间开销差异很明显1%3000万数据约占35MB0.1%3000万数据约占52MB0.01%3000万数据约占70MB从1%降到0.1%空间多用了差不多50%。大多数业务场景下1%够用了对准确性要求更高的场景可以设到0.1%或0.01%。过期时间expire。这个参数跟布隆过滤器本身的原理无关但在实际项目里很关键。布隆过滤器不支持删除单个元素但可以给整个过滤器设过期时间让系统自动回收。弹窗展示5天过期时间设6天。权益改版通知要持续1年过期时间就设365天。过期后过滤器自动清除下次请求时重新创建。下面这张速查表列出了不同参数组合下的位数组大小和哈希函数个数做技术选型时可以直接查数据量误判率位数组大小哈希函数个数内存占用100万1%958万位71.14MB100万0.1%1437万位101.71MB100万0.01%1917万位132.29MB1000万1%9585万位711.43MB1000万0.1%1.44亿位1017.13MB1000万0.01%1.92亿位1422.85MB3000万1%2.88亿位734.28MB3000万0.1%4.31亿位1051.38MB1亿1%9.59亿位7114.27MB1亿0.01%19.17亿位14228.54MB哈希函数个数的计算方式是 -(ln(误判率) / ln2)。误判率越低需要的哈希函数越多写入时的计算开销也越大。不能删除的问题布隆过滤器有一个经常被问到的限制不支持删除单个元素。原因在于位数组的位置是共享的。元素A占了第2、7、15位元素B占了第5、7、20位第7位是共用的。如果删除元素A把第2、7、15位清零第7位变成0元素B查询时就会发现第7位是0被误判为不存在。计数布隆过滤器Counting Bloom Filter是解决这个问题的一个变体。它把每个位从1bit的0/1改成一个计数器写入时计数器加1删除时计数器减1查询时检查计数器是否大于0。这样删除一个元素不会影响其他元素的判断。代价是空间翻了好几倍。原来每个位占1bit改成计数器后每个位至少占4bit。3000万数据量、1%误判率的配置下空间从35MB涨到140MB。实际项目中大多数场景用不着计数布隆过滤器。给整个过滤器设一个过期时间到期自动清除重建比维护单个元素的删除逻辑要省事。一些分布式存储系统在内部使用了支持删除的布隆过滤器变体但由于空间和维护成本更高普通业务中用得不算多。布隆过滤器不能无限写入布隆过滤器在初始化时位数组大小就已经固定了。随着不断写入元素越来越多的位被置为1。当写入量远超预期数据量时位数组会变得越来越密误判率也随之飙升。极端情况下如果位数组几乎全是1任何元素查进来都会被判为存在误判率接近100%布隆过滤器就失去了过滤的意义。所以布隆过滤器是一种容量固定的数据结构不是想加多少就加多少。生产环境在创建时就要估算好expectedInsertions留够余量。如果数据量真的超过了设计容量需要创建一个新的布隆过滤器来替换旧的。这也是为什么前面配置里的预期数据量会按会员总数的1.2到1.5倍来设定。实际项目中的两种用法Java生态里用布隆过滤器常见的有两个库。单机场景用Guava的BloomFilter。Guava提供了标准的创建接口指定预期数据量和误判率就行内部会自动计算位数组大小和哈希函数个数。单机部署时直接创建使用代码很简洁。分布式场景用Redisson的RBloomFilter。多个服务实例需要共享同一个布隆过滤器时单机版就不够用了因为每个实例各自维护一份位数组数据不互通。Redisson把布隆过滤器的数据存在Redis里所有实例都能读写同一份数据。前面贴的生产代码就是Redisson的方案。在实际项目里通常会在Redis层封装一层initBloomFilter和getBloomFilter处理过滤器不存在时的自动创建、分布式锁防止并发初始化这些细节。两种方案的选型依据就看部署方式单实例用Guava多实例用Redisson。小结布隆过滤器的价值在于用很小的空间代价解决海量数据的存在性判断问题。3000万条记录35MB内存就够了这个空间效率是HashSet这类数据结构做不到的。面试的时候把三个关键点讲明白就行位数组是存储结构多个哈希函数是写入和查询的机制假阳性是它区别于精确判断的核心特征。假阳性只有单方向判断不存在一定准确判断存在可能误判。做技术选型时多留意预期数据量这个参数。定小了会导致误判率飙升定大了浪费空间尽量提前估算准确。
