布隆过滤器

布隆过滤器

布隆过滤器由「初始值都为 0 的位图数组」和「 N 个哈希函数」两部分组成。当我们在写入数据库数据时，在布隆过滤器里做个标记，这样下次查询数据是否在数据库时，只需要查询布隆过滤器，如果查询到数据没有被标记，说明不在数据库中。

• 第一步，使用 N 个哈希函数分别对数据做哈希计算，得到 N 个哈希值；
• 第二步，将第一步得到的 N 个哈希值对位图数组的长度取模，得到每个哈希值在位图数组的对应位置。
• 第三步，将每个哈希值在位图数组的对应位置的值设置为 1；
• 查询的时****候只要有一个为 0，就认为数据 x 不在数据库中。
• 没有的一定没有，有的也可能没有

黑名单，爬虫去重

只有加入和查询，不要求删除，

极大减少内存，

但是必须允许一定程度的失误率，会误杀好人，但是不会漏杀坏人

布隆过滤器是一种数据结构，比较巧妙的概率型数据结构（probabilistic data structure），特点是高效地插入和查询，可以用来告诉你** “某样东西一定不存在或者可能存在”。**

• 如果存在那就是可能存在（hash的碰撞）
• 如果不存在那就一定不存在

相比于传统的 List、Set、Map 等数据结构，它更高效插入和查询、占用空间更少，但是缺点是其返回的结果可能是误判存在的，合理设置长度以及hash 函数的个数可以提高准确率。

痛点问题原始解决办法

• 原本有10亿个号码，现在又来了10万个号码，要快速准确判断这10万个号码是否在10亿个号码库中？

  • 解决办法一：将10亿个号码存入数据库中，进行数据库查询，准确性有了，但是速度会比较慢。
  • 解决办法二：将10亿个号码放入内存中，比如Redis缓存中，这里我们算一下占用内存大小：10亿*8字节=8GB，通过内存查询，准确性和速度都有了，但是大约8gb的内存空间，挺浪费内存空间的。

• 接触过爬虫的，应该有这么一个需求，需要爬虫的网站千千万万，对于一个新的网站url，我们如何判断这个url我们是否已经爬过了？

  • 解决办法还是上面的两种，很显然，都不太好。

上述问题最主要的场景是：我们不需要从中拿到数据来用，只是判断一下是否存在就好，所以实际简化的思路就是不存放实际的值，用更简单的值来代替（hash）

判断某个元素是否存在的数据结构：

• 数组、链表、树（平衡、Trie）、map：虽然这几种数据结构配合常见的排序、二分搜索可以快速高效的处理绝大部分判断元素是否存在集合中的需求。但是当集合里面的元素数量足够大，如果有500万条记录甚至1亿条记录呢？这个时候常规的数据结构的问题就凸显出来了。数组、链表、树等数据结构会存储元素的内容，一旦数据量过大，消耗的内存也会呈现线性增长，最终达到瓶颈。
• hashmap：将值映射到 HashMap 的 Key，然后可以在 O(1) 的时间复杂度内返回结果，效率奇高。
  • 缺点，例如存储容量占比高，考虑到负载因子的存在，通常空间是不能被用满的，而一旦你的值很多例如上亿的时候，那 HashMap 占据的内存大小就变得很可观了。
  • 还比如说你的数据集存储在远程服务器上，本地服务接受输入，而数据集非常大不可能一次性读进内存构建 HashMap 的时候，也会存在问题。
• 布隆过滤器：一个 bit 向量或者说 bit 数组（位数组）
  • 映射一个值到布隆过滤器中，多个无偏哈希函数对元素进行哈希，每一个hash函数算出一个整数索引值，然后对位数组长度进行取模运算得到一个位置，每个无偏哈希函数都会得到一个不同的位置。再把位数组的这几个位置都设置为1
  • 判断存在也不一定存在：随着增加的值越来越多，被置为 1 的 bit 位也会越来越多，这样某个值 “taobao” 即使没有被存储过，但是万一哈希函数返回的三个 bit 位都被其他值置位了 1 ，那么程序还是会判断 “taobao” 这个值存在。
  • 
  • 解决空间问题：通过hash实现数据的压缩，使用的是hash编码，只是确定是否存在不需要存放实际的数据的时候非常合适

布隆操作流程

布隆过滤器添加元素

• 将要添加的元素给k个哈希函数
• 得到对应于位数组上的k个位置
• 将这k个位置设为1

布隆过滤器查询元素

• 将要查询的元素给k个哈希函数
• 得到对应于位数组上的k个位置
• 如果k个位置有一个为0，则肯定不在集合中
• 如果k个位置全部为1，则可能在集合中

底层原理：位图

• 使用java实现简单的位图
  • 每一个位置只使用1比特放入，int[] arr = new int[10]; 相当于48 = 32，3210 = 320位的长度的位图
  • 如果想获得178位置的状态，先使用178 / 32 得到在第几个int上，之后使用178%32 得到在这个int中的偏移量
    • int numIndex = 178 / 32;
    • int bitIndex = 178 % 32;
    • int s = ((arr[numIndex] >> (bitIndex)) & 1); 移动到这个是数字的最右侧，和1 相与，得到这个数字的状态
  • 

布隆过滤器支持删除吗

• 不支持，因为某一位可能被多个值共同覆盖，删除的话其他的值也会被判断为不存在
• 解决：不使用bit位，而是使用计数，每对应一次槽对应的计数就+1。判断是否存在就看值是否大于0
• 注意：这种解决办法还是可能把不存在的判为存在，但是不会把存在的判为不存在

选择哈希函数个数和布隆过滤器长度

• hash函数个数k：哈希函数的个数也需要权衡，个数越多准确率高，则布隆过滤器 bit 位置为 1 的速度越快，且布隆过滤器的效率越低；但是如果太少的话，那我们的误报率会变高。
• 布隆过滤器长度n：过小的布隆过滤器很快所有的 bit 位均为 1，那么查询任何值都会返回“可能存在”，起不到过滤的目的了。布隆过滤器的长度会直接影响误报率，布隆过滤器越长其误报率越小。

k 为哈希函数个数，m 为布隆过滤器长度，n 为样本量，p 为误报率。

确定样本量，确定误报率就可以了。

一个URL是64字节这个信息没有用，只要确保hash函数可以接收这种参数就可以。

应用

利用布隆过滤器减少磁盘 IO 或者网络请求，因为一旦一个值必定不存在的话，我们可以不用进行后续昂贵的查询请求。

性能很低的哈希函数不是个好选择，推荐 MurmurHash、Fnv 这些。

大Value拆分

Redis 因其支持 setbit 和 getbit 操作，且纯内存性能高等特点，因此天然就可以作为布隆过滤器来使用。但是布隆过滤器的不当使用极易产生大 Value，增加 Redis 阻塞风险，因此生成环境中建议对体积庞大的布隆过滤器进行拆分。

拆分的形式方法多种多样，但是本质是不要将 Hash(Key) 之后的请求分散在多个节点的多个小 bitmap 上，而是应该拆分成多个小 bitmap 之后，对一个 Key 的所有哈希函数都落在这一个小 bitmap 上。

解决缓存穿透的问题

一般情况下，先查询缓存是否有该条数据，缓存中没有时，再查询数据库。当数据库也不存在该条数据时，每次查询都要访问数据库，这就是缓存穿透。缓存穿透带来的问题是，当有大量请求查询数据库不存在的数据时，就会给数据库带来压力，甚至会拖垮数据库。

可以使用布隆过滤器解决缓存穿透的问题，把已存在数据的key存在布隆过滤器中。当有新的请求时，先到布隆过滤器中查询是否存在，如果不存在该条数据直接返回；如果存在该条数据再查询缓存查询数据库。

黑名单校验

发现存在黑名单中的，就执行特定操作。比如：识别垃圾邮件，只要是邮箱在黑名单中的邮件，就识别为垃圾邮件。假设黑名单的数量是数以亿计的，存放起来就是非常耗费存储空间的，布隆过滤器则是一个较好的解决方案。把所有黑名单都放在布隆过滤器中，再收到邮件时，判断邮件地址是否在布隆过滤器中即可。

Redis中的布隆过滤器

之前的布隆过滤器可以使用Redis中的位图操作实现，直到Redis4.0版本提供了插件功能，Redis官方提供的布隆过滤器才正式登场。布隆过滤器作为一个插件加载到Redis Server中，就会给Redis提供了强大的布隆去重功能。

基本使用

在Redis中，布隆过滤器有两个基本命令，分别是：

• bf.add：添加元素到布隆过滤器中，类似于集合的sadd命令，不过bf.add命令只能一次添加一个元素，如果想一次添加多个元素，可以使用bf.madd命令。
• bf.exists：判断某个元素是否在过滤器中，类似于集合的sismember命令，不过bf.exists命令只能一次查询一个元素，如果想一次查询多个元素，可以使用bf.mexists命令。

> bf.add one-more-filter fans1
(integer) 1
> bf.add one-more-filter fans2
(integer) 1
> bf.add one-more-filter fans3
(integer) 1
> bf.exists one-more-filter fans1
(integer) 1
> bf.exists one-more-filter fans2
(integer) 1
> bf.exists one-more-filter fans3
(integer) 1
> bf.exists one-more-filter fans4
(integer) 0
> bf.madd one-more-filter fans4 fans5 fans6
1) (integer) 1
2) (integer) 1
3) (integer) 1
> bf.mexists one-more-filter fans4 fans5 fans6 fans7
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 0

上面的例子中，没有发现误判的情况，是因为元素数量比较少。当元素比较多时，可能就会发生误判，怎么才能减少误判呢？

上面的例子中使用的布隆过滤器只是默认参数的布隆过滤器，它在我们第一次使用bf.add命令时自动创建的。Redis还提供了自定义参数的布隆过滤器，想要尽量减少布隆过滤器的误判，就要设置合理的参数。

在使用bf.add命令添加元素之前，使用bf.reserve命令创建一个自定义的布隆过滤器。bf.reserve命令有三个参数，分别是：

• key：键
• error_rate：期望错误率，期望错误率越低，需要的空间就越大。
• capacity：初始容量，当实际元素的数量超过这个初始化容量时，误判率上升。

bf.reserve one-more-filter 0.0001 1000000

如果对应的key已经存在时，在执行bf.reserve命令就会报错。如果不使用bf.reserve命令创建，而是使用Redis自动创建的布隆过滤器，默认的error_rate是 0.01，capacity是 100。

对于不需要过于精确的场景，error_rate设置稍大一点也可以。布隆过滤器的capacity设置的过大，会浪费存储空间，设置的过小，就会影响准确率，所以在使用之前一定要尽可能地精确估计好元素数量，还需要加上一定的冗余空间以避免实际元素可能会意外高出设置值很多。总之，error_rate和 capacity都需要设置一个合适的数值。

依赖bitmaps实现

实现的基本的数据结构就是

ASCII码一个字符是一个字节，8位，所有字符组成一个字符串

位图bitmaps提供了一套命令来操作类似字符串中的字符的每一位

setbit key offset value

"b"的二进制表示为0110 0010，我们将第7位（从0开始）设置为1，那0110 0011 表示的就是字符“c”，所以最后的字符 “big”变成了“cig”。

getbit key offset	

获取位图指定范围值为1的个数,start和end指定的是字节的个数，而不是位数组下标

bitcount key [start end]

Redisson

Redis 实现布隆过滤器的底层就是通过 bitmap 这种数据结构，至于如何实现，这里就不重复造轮子了，介绍业界比较好用的一个客户端工具——Redisson。

Redisson 是用于在 Java 程序中操作 Redis 的库，利用Redisson 我们可以在程序中轻松地使用 Redis。

下面我们就通过 Redisson 来构造布隆过滤器。

package com.ys.rediscluster.bloomfilter.redisson;import org.redisson.Redisson;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.redisson.config.Config;public class RedissonBloomFilter {public static void main(String[] args) {Config config = new Config();config.useSingleServer().setAddress("redis://192.168.14.104:6379");config.useSingleServer().setPassword("123");//构造RedissonRedissonClient redisson = Redisson.create(config);RBloomFilter<String> bloomFilter = redisson.getBloomFilter("phoneList");//初始化布隆过滤器：预计元素为100000000L,误差率为3%bloomFilter.tryInit(100000000L,0.03);//将号码10086插入到布隆过滤器中bloomFilter.add("10086");//判断下面号码是否在布隆过滤器中System.out.println(bloomFilter.contains("123456"));//falseSystem.out.println(bloomFilter.contains("10086"));//true}
}

这是单节点的Redis实现方式，如果数据量比较大，期望的误差率又很低，那单节点所提供的内存是无法满足的，这时候可以使用分布式布隆过滤器，同样也可以用 Redisson 来实现

guava

不用Redis如何来实现布隆过滤器。guava 工具包相信大家都用过，这是谷歌公司提供的，里面也提供了布隆过滤器的实现。

package com.ys.rediscluster.bloomfilter;import com.google.common.base.Charsets;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnel;
import com.google.common.hash.Funnels;public class GuavaBloomFilter {public static void main(String[] args) {BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8),100000,0.01);bloomFilter.put("10086");System.out.println(bloomFilter.mightContain("123456"));System.out.println(bloomFilter.mightContain("10086"));}
}

https://www.cnblogs.com/heihaozi/p/12174478.html

https://zhuanlan.zhihu.com/p/43263751

https://www.cnblogs.com/ysocean/p/12594982.html