布隆过滤器的原理及使用_谷歌布隆过滤器

一、什么是布隆过滤器？

首先，我们需要了解布隆过滤器的概念

布隆过滤器（Bloom Filter）是一个叫做 Bloom 的人于 1970 年提出的。我们可以把它看作由二进制向量（或者说位数组）和一系列随机映射函数（哈希函数）两部分组成的数据结构。相比于我们平时常用的的 List、Map 、Set 等数据结构，它占用空间更少并且效率更高，但是缺点是其返回的结果是概率性的，而不是非常准确的。理论情况下添加到集合中的元素越多，误报的可能性就越大。并且，存放在布隆过滤器的数据不容易删除。

布隆过滤器示意图

位数组中的每个元素都只占用 1 bit ，并且每个元素只能是 0 或者 1。这样申请一个 100w 个元素的位数组只占用 1000000Bit / 8 = 125000 Byte = 125000/1024 kb ≈ 122kb 的空间。

总结：一个名叫 Bloom 的人提出了一种来检索元素是否存在于大集合中的数据结构，这种数据结构效率高，但缺点是具有一定的误判性，并且理论情况下，添加到集合中的元素越多，误判的可能性就越大

二、布隆过滤器的使用场景

1. 判断给定数据是否存在：比如判断一个数字是否存在于包含大量数字的数字集中（数字集很大，5 亿以上！）
2. 网页爬虫对URL的去重，避免爬取相同的URL地址
3. 长链接生成短链接（我的一个项目），进行映射，需要判断 url 是否重复
4. 反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱(同理，垃圾短信)
5. 缓存击穿，将已存在的缓存放到布隆中，当黑客访问不存在的缓存时迅速返回避免缓存及DB挂掉
6. 抽奖程序中排除非会员参与

三、布隆过滤器的设计原理

当一个元素加入布隆过滤器中的时候，会进行如下操作：

1. 使用布隆过滤器中的哈希函数对元素值进行计算，得到哈希值（有几个哈希函数得到几个哈希值）
2. 根据得到的哈希值，在位数组中把对应下标的值置为 1

当我们需要判断一个元素是否存在于布隆过滤器的时候，会进行如下操作：

1. 对给定元素再次进行相同的哈希计算
2. 得到值之后判断位数组中的元素的每个计算结果是否都为 1，如果值都为 1，那么说明这个值在布隆过滤器中，如果存在一个值不为
   1，说明该元素不在布隆过滤器中

举个简单的例子：

如图所示，当字符串存储要加入到布隆过滤器中时，该字符串首先由多个哈希函数生成不同的哈希值，然后将对应的位数组的下标设置为 1（当位数组初始化时，所有位置均为 0）。当第二次存储相同字符串时，因为先前的对应位置已设置为 1，所以很容易知道此值已经存在（去重非常方便）

如果我们需要判断某个字符串是否在布隆过滤器中时，只需要对给定字符串再次进行相同的哈希计算，得到值之后判断位数组中元素的每个计算结果是否都为 1，如果值都为 1，那么说明这个值在布隆过滤器中，如果存在一个值不为 1，说明该元素不在布隆过滤器中

不同的字符串可能哈希出来的位置相同，这种情况就是我们常说的hahs碰撞，解决办法：我们可以适当增加位数组大小或者调整hash函数以及增加hash函数次数

综上，我们可以得出：布隆过滤器说某个元素存在，小概率会误判。布隆过滤器说某个元素不在，那么这个元素一定不在

四、Google布隆过滤器

在Google Guava library中Google为我们提供了一个布隆过滤器的实现BloomFilter。下面我们来通过一个例子说明下Google布隆过滤器的入门使用。
（1）引入依赖

<dependency>
  <groupId>com.google.guava</groupId>
  <artifactId>guava</artifactId>
  <version>21.0</version>
</dependency>
1
2
3
4
5

（2）准备数据库语句

DROP TABLE IF EXISTS `sys_user`;
CREATE TABLE `sys_user` (
  `id` int(11) unsigned NOT NULL AUTO_INCREMENT,
  `user_name` varchar(11) CHARACTER SET utf8mb4 DEFAULT NULL COMMENT '用户名',
  `image` varchar(11) CHARACTER SET utf8mb4 DEFAULT NULL COMMENT '用户头像',
  PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8;

INSERT INTO `sys_user` VALUES (1, 'calvin', 'xxx');
INSERT INTO `sys_user` VALUES (2, 'bobb', 'yyy');
INSERT INTO `sys_user` VALUES (3, 'liming', 'zzz');

1
2
3
4
5
6
7
8
9
10
11
12

（3）BloomFilterService

package com.calvin.service;

import com.calvin.entity.SysUser;
import com.calvin.mapper.SysUserMapper;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import java.util.List;
import javax.annotation.PostConstruct;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.stereotype.Service;
import org.springframework.util.CollectionUtils;

/**
 * @Title BloomFilterService
 * @Description google布隆过滤器
 * @author calvin
 * @date: 2019/12/19 11:37 PM 
 */
@Service
public class BloomFilterService {

    @Autowired
    private SysUserMapper sysUserMapper;

    private BloomFilter<Integer> bf;

    /**
     * 程序启动时候加载此方法
     */
    @PostConstruct
    public void initBloomFilter() {
        List<SysUser> sysUsers = sysUserMapper.selectAll();
        if (CollectionUtils.isEmpty(sysUsers)) {
            return;
        }
        // 创建布隆过滤器（默认误差3%）
        bf = BloomFilter.create(Funnels.integerFunnel(), sysUsers.size());
        // 将数据库中所有用户id压入布隆过滤器，存于JVM内存
        sysUsers.stream().forEach(user -> bf.put(user.getId()));
    }

    /**
     * 判断用户id是否存在于布隆过滤器
     * @param userId
     * @return
     */
    public boolean userIdExist(Integer userId) {
        return bf.mightContain(userId);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

（4）BloomFilterController

package com.calvin.controller;

import com.calvin.service.BloomFilterService;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RestController;
import javax.annotation.Resource;

/**
 * @Title GoogleBloomFilterController
 * @Description
 * @author calvin
 * @date: 2019/12/20 11:25 AM
 */
@RestController
public class GoogleBloomFilterController {

    @Resource
    private BloomFilterService bloomFilterService;

    /**
     * 使用google布隆过滤器判断元素是否存在
     * @param id
     * @return
     */
    @RequestMapping("/bloom/idExists")
    public boolean ifExists(int id) {
        return bloomFilterService.userIdExist(id);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

（5）测试

浏览器中输入：http://localhost:8082/google/bloom/idExists?id=1

同理id=2，id=3结果返回都是true，说明id=1，2，3都是存在于布隆过滤器中，返回true。

当输入：http://localhost:8082/google/bloom/idExists?id=4

id=4不在布隆过滤器中，返回false

根据与数据库存在的用户id做对比，发现测试结果与预期相同，这就是Google布隆过滤器的使用

从上面的例子可以看到Google布隆过滤器有如下的缺点：

• 基于JVM内存的一种布隆过滤器
• 重启即失效
• 本地内存无法用在分布式场景
• 不支持大数据量存储

因此接下来介绍Redis布隆过滤器

五、Redis布隆过滤器

相对于Google布隆过滤器，Redis布隆过滤器有以下的优点：

• 可扩展性Bloom过滤器：一旦Bloom过滤器达到容量，就会在其上创建一个新的过滤器

• 不存在重启即失效或者定时任务维护的成本：基于Google实现的布隆过滤器需要启动之后初始化布隆过滤器

缺点：

• 需要网络IO，性能比Google布隆过滤器低

Redis如果需要使用布隆过滤器，先要安装rebloom

## 从github下载rebloom
git clone git://github.com/RedisLabsModules/rebloom

## 编译模块
cd rebloom
make
1
2
3
4
5
6

编译模块之后，可以看到文件夹中生成了一个redisbloom.so文件

接着，在redis的配置文件中加入该模块

loadmodule /Users/calvin/Documents/Work/install/rebloom/redisbloom.so
1

redis指定配置文件启动

./redis-server ../redis.conf
1

可以看到rebloom这个模块已经随着redis的启动而加载

Redis布隆过滤器命令：

• bf.add：添加元素到布隆过滤器中，只能添加一个元素，如果想要添加多个使用bf.madd命令
• bf.exists：判断某个元素是否在过滤器中，只能判断一个元素，如果想要判断多个使用bf.mexists命令

127.0.0.1:6379> bf.add calvinBloom 111
(integer) 1
127.0.0.1:6379> bf.add calvinBloom 222
(integer) 1
127.0.0.1:6379> bf.add calvinBloom 333
(integer) 1
127.0.0.1:6379> bf.exists calvinBloom 111
(integer) 1
127.0.0.1:6379> bf.exists calvinBloom 222
(integer) 1
127.0.0.1:6379> bf.exists calvinBloom 333
(integer) 1
127.0.0.1:6379> bf.exists calvinBloom 444
(integer) 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14

可以看到，定义的布隆过滤器名称为：calvinBloom，加入进去的元素为：111，222，333

而元素444不在过滤器中，因此返回0

六、基于lua脚本实现SpringBoot和Redis布隆过滤器的整合

（1）编写Lua脚本

bloomFilterAdd.lua

local bloomName = KEYS[1]
local value = KEYS[2]

-- 添加bloom过滤器及元素
local result_1 = redis.call('BF.ADD', bloomName, value)
return result_1
1
2
3
4
5
6

bloomFilterExist.lua

local bloomName = KEYS[1]
local value = KEYS[2]

-- 判断指定的布隆过滤器是否存在指定元素
local result_1 = redis.call('BF.EXISTS', bloomName, value)
return result_1
1
2
3
4
5
6

（2）使用redisTemplate加载Lua脚本

		/**
     * 添加bloom过滤器及元素
     * @param filterName 过滤器名称
     * @param value 要添加的元素
     * @return
     */
    public Boolean bloomFilterAdd(String filterName, int value) {
        DefaultRedisScript<Boolean> bloomAdd = new DefaultRedisScript<>();
        bloomAdd.setScriptSource(new ResourceScriptSource(new ClassPathResource("bloomFilterAdd.lua")));
        bloomAdd.setResultType(Boolean.class);
        List<Object> keyList = new ArrayList<>();
        keyList.add(filterName);
        keyList.add(value + "");
        Boolean result = (Boolean) redisTemplate.execute(bloomAdd, keyList);
        return result;
    }

    /**
     * 判断指定的布隆过滤器是否存在指定元素
     * @param filterName 过滤器名称
     * @param value 需要判断是否存在的元素
     * @return
     */
    public Boolean bloomFilterExists(String filterName, int value) {
        DefaultRedisScript<Boolean> bloomExists = new DefaultRedisScript<>();
        bloomExists.setScriptSource(new ResourceScriptSource(new ClassPathResource("bloomFilterExist.lua")));
        bloomExists.setResultType(Boolean.class);
        List<Object> keyList = new ArrayList<>();
        keyList.add(filterName);
        keyList.add(value + "");
        Boolean result = (Boolean) redisTemplate.execute(bloomExists, keyList);
        return result;
    }
    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

（3）RedisBloomFilterController

package com.calvin.controller;

import com.calvin.service.RedisService;
import javax.annotation.Resource;
import org.springframework.web.bind.annotation.RequestMapping;
import org.springframework.web.bind.annotation.RestController;

/**
 * @Title RedisBloomFilterController
 * @Description
 * @author calvin
 * @date: 2019/12/20 11:40 AM
 */
@RestController
@RequestMapping("redis")
public class RedisBloomFilterController {

    @Resource
    private RedisService redisService;

    private static final String BLOOM_FILTER_NAME = "redisBloom";

    /**
     * 添加bloom过滤器及元素
     * @param id
     * @return
     */
    @RequestMapping("/bloom/add")
    public boolean redisidAdd(int id) {
        return redisService.bloomFilterAdd(BLOOM_FILTER_NAME, id);
    }

    /**
     * 判断指定的布隆过滤器是否存在指定元素
     * @param id
     * @return
     */
    @RequestMapping("/bloom/idExists")
    public boolean redisidExists(int id) {
        return redisService.bloomFilterExists(BLOOM_FILTER_NAME, id);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

（4）测试
浏览器中输入：http://localhost:8082/redis/bloom/add?id=1，存入布隆过滤器

同样，将id=2，id=3也存入redis布隆过滤器中

接着我们来测试元素是否存在过滤器中

浏览器输入：http://localhost:8082/google/bloom/idExists?id=1

同样，id=2，id=3返回的都是true，而id=4返回的是false。说明布隆过滤器判断是正确的