布隆过滤器的原理、使用场景和注意事项

待我称王封你为后i 2023-01-14 01:48 173阅读 0赞

**目录**

引题

哈希函数

Bitmap

BloomFilter实现原理

构建布隆的误差率

布隆过滤器实现

JVM实现

guava实现

redis中的布隆过滤器

参考

--------------------

# 引题 #

有50亿个电话号码，现在给你10万个电话号码，如何快速准确的判断出这些号码是否存在？

方案A： DB ？ ----> 50亿的电话号码，这查询效率 ？  
方案B: 内存 ？ —> 就按1个电话号码8个字节 ， 50亿\*8字节= 40G 内存…

我们业务中就有这种情况，比如redis缓存击穿

当集合特别大时，用常规map等方法是不合适的。就需要用到布隆过滤器

### 哈希函数 ###

哈希函数的概念是：将任意大小的数据转换成特定大小的数据的函数，转换后的数据称为哈希值或哈希编码。

像Java里的hashmap，Java7和Java8就有不同变化，但是都是hash得到一个int类型的值

### Bitmap ###

位图（bitmap）是一种非常常用的结构，在索引，数据压缩等方面有广泛应用。位图是通过将数组下标与应用中的一些值关联映射，数组中该下标所指定的位置上的元素可以用来标识应用中值的情况（是否存在或者数目 或者计数等），位图数组中每个元素在内存中占用1位，所以可以节省存储空间。位图是一种非常简洁快速的数据结构，它能同时使存储空间和速度最优化。如可用一个10位长的字符串来表示一个所有元素都小于10的简单的非负整数集合，例如，可以用如下字符串表示集合\{1,2,4,5,8\} ，对应位置数字存在标记为1，否则标记为0。

假如，我们要存储的数据范围为0-15，这里的数据是16bit:

数据为\[5, 1, 7, 15, 0, 4, 6, 10\]

Bitset

JDK实现的bitmap

<table> 
 <tbody> 
  <tr> 
   <td> <p><code>public</code>&nbsp;<code>void</code>&nbsp;<code>set(</code><code>int</code>&nbsp;<code>pos): 位置pos的字位设置为</code><code>true</code><code>。</code></p> <p><code>public</code>&nbsp;<code>void</code>&nbsp;<code>set(</code><code>int</code>&nbsp;<code>bitIndex,&nbsp;</code><code>boolean</code>&nbsp;<code>value) 将指定索引处的位设置为指定的值。</code></p> <p><code>public</code>&nbsp;<code>void</code>&nbsp;<code>clear(</code><code>int</code>&nbsp;<code>pos): 位置pos的字位设置为</code><code>false</code><code>。</code></p> <p><code>public</code>&nbsp;<code>void</code>&nbsp;<code>clear() : 将此 BitSet 中的所有位设置为&nbsp;</code><code>false</code><code>。</code></p> <p><code>public</code>&nbsp;<code>int</code>&nbsp;<code>cardinality() 返回此 BitSet 中设置为&nbsp;</code><code>true</code>&nbsp;<code>的位数。</code></p> <p><code>public</code>&nbsp;<code>boolean</code>&nbsp;<code>get(</code><code>int</code>&nbsp;<code>pos): 返回位置是pos的字位值。</code></p> <p><code>public</code>&nbsp;<code>void</code>&nbsp;<code>and(BitSet other): other同该字位集进行与操作，结果作为该字位集的新值。</code></p> <p><code>public</code>&nbsp;<code>void</code>&nbsp;<code>or(BitSet other): other同该字位集进行或操作，结果作为该字位集的新值。</code></p> <p><code>public</code>&nbsp;<code>void</code>&nbsp;<code>xor(BitSet other): other同该字位集进行异或操作，结果作为该字位集的新值。</code></p> <p><code>public</code>&nbsp;<code>void</code>&nbsp;<code>andNot(BitSet set) 清除此 BitSet 中所有的位,set - 用来屏蔽此 BitSet 的 BitSet</code></p> <p><code>public</code>&nbsp;<code>int</code>&nbsp;<code>size(): 返回此 BitSet 表示位值时实际使用空间的位数。</code></p> <p><code>public</code>&nbsp;<code>int</code>&nbsp;<code>length() 返回此 BitSet 的“逻辑大小”：BitSet 中最高设置位的索引加&nbsp;</code><code>1</code><code>。</code></p> <p><code>public</code>&nbsp;<code>int</code>&nbsp;<code>hashCode(): 返回该集合Hash 码， 这个码同集合中的字位值有关。</code></p> <p><code>public</code>&nbsp;<code>boolean</code>&nbsp;<code>equals(Object other): 如果other中的字位同集合中的字位相同，返回</code><code>true</code><code>。</code></p> <p><code>public</code>&nbsp;<code>Object clone() 克隆此 BitSet，生成一个与之相等的新 BitSet。</code></p> <p><code>public</code>&nbsp;<code>String toString() 返回此位 set 的字符串表示形式。</code></p> </td> 
  </tr> 
 </tbody> 
</table>

# BloomFilter实现原理 #

布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。

当一个元素被加入集合时，通过 K 个 Hash 函数将这个元素映射成一个位阵列（Bit array）中的 K 个点，把它们置为 1。检索时，我们只要看看这些点是不是都是 1 就（大约）知道集合中有没有它了：

如果这些点有任何一个 0，则被检索元素一定不在； 如果都是 1，则被检索元素很可能在。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l2ZXJzb24yMDEwMTEyMjI4_size_16_color_FFFFFF_t_70][]

# 构建布隆的误差率 #

参数： m个二进制向量， n个预备数据，k个哈希函数

构建布隆过滤器： n个预备数据走一遍上面过程

判断元素存在与否：将这个数据，重走一遍构建的过程（进行k次hash运算），如果都是1，则表示存在，反之不存在。

很显然，过小的布隆过滤器很快所有的 bit 位均为 1，那么查询任何值都会返回“可能存在”，起不到过滤的目的了。布隆过滤器的长度会直接影响误报率，布隆过滤器越长其误报率越小。

另外，哈希函数的个数也需要权衡，个数越多则布隆过滤器 bit 位置位 1 的速度越快，且布隆过滤器的效率越低；但是如果太少的话，那我们的误报率会变高。

m/n 与误差率成反比， k与误差率成反比

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l2ZXJzb24yMDEwMTEyMjI4_size_16_color_FFFFFF_t_70 1][]

# 布隆过滤器实现 #

### JVM实现 ###

用bitset实现

### guava实现 ###

Guava 中布隆过滤器的实现算是比较权威的，所以实际项目中我们不需要手动实现一个布隆过滤器。

<table> 
 <tbody> 
  <tr> 
   <td> <p><code>// 创建布隆过滤器对象</code></p> <p><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>BloomFilter&lt;Integer&gt; filter = BloomFilter.create(</code></p> <p><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>Funnels.integerFunnel(),</code></p> <p><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>1500</code><code>,</code></p> <p><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>0.01</code><code>);</code></p> <p><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// 判断指定元素是否存在</code></p> <p><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.println(filter.mightContain(</code><code>1</code><code>));</code></p> <p><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.println(filter.mightContain(</code><code>2</code><code>));</code></p> <p><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>// 将元素添加进布隆过滤器</code></p> <p><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>filter.put(</code><code>1</code><code>);</code></p> <p><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>filter.put(</code><code>2</code><code>);</code></p> <p><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.println(filter.mightContain(</code><code>1</code><code>));</code></p> <p><code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code><code>System.out.println(filter.mightContain(</code><code>2</code><code>));</code></p> </td> 
  </tr> 
 </tbody> 
</table>

原理

BloomFilter类的成员属性

<table> 
 <tbody> 
  <tr> 
   <td> <p><code>&nbsp;&nbsp;</code><code>/** The bit set of the BloomFilter (not necessarily power of 2!) */</code></p> <p><code>//bits即上文讲到的长度为m的位数组，采用LockFreeBitArray类型做了封装。</code></p> <p><code>&nbsp;&nbsp;</code><code>private</code>&nbsp;<code>final</code>&nbsp;<code>LockFreeBitArray bits;</code></p> <p>&nbsp;</p> <p><code>&nbsp;&nbsp;</code><code>/** Number of hashes per element */</code></p> <p><code>//numHashFunctions即哈希函数的个数k。</code></p> <p><code>&nbsp;&nbsp;</code><code>private</code>&nbsp;<code>final</code>&nbsp;<code>int</code>&nbsp;<code>numHashFunctions;</code></p> <p>&nbsp;</p> <p><code>&nbsp;&nbsp;</code><code>/** The funnel to translate Ts to bytes */</code></p> <p><code>//funnel是Funnel接口实现类的实例，它用于将任意类型T的输入数据转化为Java基本类型的数据（byte、int、char等等）。这里是会转化为byte。</code></p> <p><code>&nbsp;&nbsp;</code><code>private</code>&nbsp;<code>final</code>&nbsp;<code>Funnel&lt;?&nbsp;</code><code>super</code>&nbsp;<code>T&gt; funnel;</code></p> <p>&nbsp;</p> <p><code>&nbsp;&nbsp;</code><code>/** The strategy we employ to map an element T to {@code numHashFunctions} bit indexes. */</code></p> <p><code>//strategy是布隆过滤器的哈希策略，即数据如何映射到位数组，其具体方法在BloomFilterStrategies枚举中。</code></p> <p><code>&nbsp;&nbsp;</code><code>private</code>&nbsp;<code>final</code>&nbsp;<code>Strategy strategy;</code></p> </td> 
  </tr> 
 </tbody> 
</table>

构造

static <T> BloomFilter<T> create(
          Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy)

该方法接受4个参数：funnel是插入数据的Funnel，expectedInsertions是期望插入的元素总个数n，fpp即期望假阳性率p，strategy即哈希策略。

### redis中的布隆过滤器 ###

Redis v4.0 之后有了 Module（模块/插件） 功能，Redis Modules 让 Redis 可以使用外部模块扩展其功能 。布隆过滤器就是其中的 Module。详情可以查看 Redis 官方对 Redis Modules 的介绍 ：[https://redis.io/modules][https_redis.io_modules]

另外，官网推荐了一个 RedisBloom 作为 Redis 布隆过滤器的 Module,地址：[https://github.com/RedisBloom/RedisBloom][https_github.com_RedisBloom_RedisBloom]. 其他还有：

*  redis-lua-scaling-bloom-filter （lua 脚本实现）：[https://github.com/erikdubbelboer/redis-lua-scaling-bloom-filter][https_github.com_erikdubbelboer_redis-lua-scaling-bloom-filter]
 *  pyreBloom（Python中的快速Redis 布隆过滤器） ：[https://github.com/seomoz/pyreBloom][https_github.com_seomoz_pyreBloom]
 *  ......

RedisBloom 提供了多种语言的客户端支持，包括：Python、Java、JavaScript 和 PHP。

# 参考 #

[https://github.com/Snailclimb/JavaGuide/blob/master/docs/dataStructures-algorithms/data-structure/bloom-filter.md][https_github.com_Snailclimb_JavaGuide_blob_master_docs_dataStructures-algorithms_data-structure_bloom-filter.md]

[https://www.jianshu.com/p/bef2ec1c361f\#%E5%81%87%E9%98%B3%E6%80%A7%E7%8E%87%E7%9A%84%E8%AE%A1%E7%AE%97][https_www.jianshu.com_p_bef2ec1c361f_E5_81_87_E9_98_B3_E6_80_A7_E7_8E_87_E7_9A_84_E8_AE_A1_E7_AE_97]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l2ZXJzb24yMDEwMTEyMjI4_size_16_color_FFFFFF_t_70]: /images/20221022/310f8205a0a64958b3e3fa414d304dac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2l2ZXJzb24yMDEwMTEyMjI4_size_16_color_FFFFFF_t_70 1]: /images/20221022/4ec009ea07254aafa690a1c19517a041.png
[https_redis.io_modules]: https://redis.io/modules
[https_github.com_RedisBloom_RedisBloom]: https://github.com/RedisBloom/RedisBloom
[https_github.com_erikdubbelboer_redis-lua-scaling-bloom-filter]: https://github.com/erikdubbelboer/redis-lua-scaling-bloom-filter
[https_github.com_seomoz_pyreBloom]: https://github.com/seomoz/pyreBloom
[https_github.com_Snailclimb_JavaGuide_blob_master_docs_dataStructures-algorithms_data-structure_bloom-filter.md]: https://github.com/Snailclimb/JavaGuide/blob/master/docs/dataStructures-algorithms/data-structure/bloom-filter.md
[https_www.jianshu.com_p_bef2ec1c361f_E5_81_87_E9_98_B3_E6_80_A7_E7_8E_87_E7_9A_84_E8_AE_A1_E7_AE_97]: https://www.jianshu.com/p/bef2ec1c361f#%E5%81%87%E9%98%B3%E6%80%A7%E7%8E%87%E7%9A%84%E8%AE%A1%E7%AE%97