布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。
- 优点: 空间效率和查询时间都比一般的算法要好的多
- 缺点: 有一定的误识别率及删除困难。
bloom的设计思想
bloom实现的总体思想是使用bitset，存储数据的hash值，一般一个数据会使用多个hash函数生成值
这样查看目标数据是否存在的时候，只要看相应的hash值对应的位置是否都为1，即可判断是否不存在。
这里要注意的是：
bloom返回true，不代表一定存在，因为有一定的误差范围
bloom返回false，则说明数据一定不存在，因为同样的数据产生的hash值总是相同，所以只要加入bitset，则下次查询相应位一定为1.
bloom能精确判断数据不存在，模糊判断数据存在（精度度可控制），不能反查出原生数据
原理
布隆过滤器是由一个可变长度为N的二进制数组与一组数量可变M的哈希函数构成。其中，哈希函数为确定性函数，所有哈希函数的输出值都在1~N之间，与二进制数组相对应。因此，每一个元素使用布隆过滤器的哈希函数进行运算都将会得到相同的结果。
插入元素
假设我们需要插入一个元素到布隆过滤器中，我们需要使用不同的哈希函数进行运算生成不同的哈希值，并且根据生成的哈希值将二进制数组对应的Bit位置为1.例如插入字符串"Bloom"到过滤器中，使用三种哈希函数进行计算所得到的哈希值分别为1,3,7，那么布隆过滤器的二进制数组则会变为:
假设我们插入第二个字符串"Filter"到过滤器中，同样，我们使用相同的哈希函数进行运算，假设哈希值分别为2,4,7，那么二进制数组则会变为:
因为在插入第一个字符串时，哈希值为7的Bit位置已经被置为1，因此不需要更改，只需要将Bit位为2,4置为1即可。
查询元素
假设需要查询某个元素是否存在，只需要使用相同的哈希函数进行运算，然后与二进制数组进行Bit值匹配即可。比如，我们需要查询字符串"hash"是否存在，使用之前的哈希函数进行运算，假设输出的哈希值为4,5,7，由于Bit位为5的位置仍然为0，所以对于字符串"hash"并不存在。
但是如果运算的哈希值为2,3,7，我们也只能说该字符串有可能存在。因为随着存储的数组越多，将会有越多的Bit位被置为1，即使某个字符串没有存储，但是有可能该字符串的哈希值与其他被存储的数据哈希值重复，仍然可能误判为该字符串存在。
因此，对于查询某个元素，只能判定某个元素一定不存在或者有可能存在，并不能判定某个元素一定存在。
布隆过滤器有两个组成元素，一是一个大型的位数组，二是几个不一样的无偏hash函数。如下图所示，f、g、h就是对应的hash函数。无偏的意思就是把计算元素的hash值时尽量均匀，映射到维数组上的位置比较随机。
控制布隆过滤器的准确率
选择合适的数组长度与哈希函数数量
因此需要设置合适的数组长度与哈希函数数量。
- 数组越短则更容易所有的位置被置为1，那么可能查询任何值都会被判断可能存在，过滤的效率将大大降低。
- 数组越长则会增加过滤效率，但是过长则会耗费大量空间。
哈希函数数量也会影响过滤效率.
- 哈希函数越多则二进制位置1的次数越多，效率也会变低
- 但是数量过少的话误判率将会变高。
可以通过以下公式计算合适的数组长度与哈希函数数量:
其中k为哈希函数个数，m 为布隆过滤器长度，n 为插入的元素个数，p 为误报率。
使用场景
- 爬虫系统中对已经爬取过的URL去重。
- Google Chrome 使用布隆过滤器识别恶意 URL
- 反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱
- 使用布隆过滤器避免推荐给用户已经读过的文章/视频
- 集合重复元素的判别；
- 查询加速（比如基于key-value的存储系统）等。
- NoSql，当用户查询某个数据时，可以先通过内存中的布隆过滤器判断是否存在，这样可以大大降低DB的IO请求数量。
- 鉴权服务，当用户登录的时候可以先用布隆过滤器判断下，而不是直接去redis、数据库查
构建大量不存在缓存中的key向服务器发起缓存穿透攻击，qps 足够高可以直接把数据库打挂。可以把不存在于数据库的key放到缓存中。
将设有100亿条数据，每个key为64个字节，也就是6400G，需要花费这么多内存缓存。
这个时候布隆过滤器在适合不过。
Guava 提供布隆过滤器
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
public class BloomFilterTest {
public static void main(String[] args) {
int total = 100000; //总数量
BloomFilter<Integer> bf = BloomFilter.create(Funnels.integerFunnel(), total);
// 初始化数据到布隆过滤器中
for (int i = 0; i < total; i++) {
bf.put(i);
}
// 判断值是否存在过滤器中
int count = 0;
for (int i = total; i < total + 10000; i++) {
if (bf.mightContain(i)) {
count++;
}
}
System.out.println("误判的数量 ～ " + count);
}
}
|
误判率的默认值为0.03，修改误判率为0.01
1
|
BloomFilter<Integer> bf = BloomFilter.create(Funnels.integerFunnel(), total, 0.01);
|
Redis 实现
RedisBloom (推荐)
布隆过滤器可以使用Redis中的位图(bitmap)操作实现，直到Redis4.0版本提供了插件功能，Redis官方提供的布隆过滤器才正式登场，布隆过滤器作为一个插件加载到Redis Server中，官网推荐了一个 RedisBloom 作为 Redis 布隆过滤器的 Module。
1
2
3
4
5
|
git clone https://github.com/RedisBloom/RedisBloom.git
cd RedisBloom
make #编译 会生成一个rebloom.so文件
redis-server --loadmodule /path/to/rebloom.so
redis-cli -h 127.0.0.1 -p 6379
|
基于 bitmap
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
52
53
|
/**
* 布隆过滤器核心类
*
* @param <T>
* @author jack xu
*/public class BloomFilterHelper<T> { private int numHashFunctions;
private int bitSize;
private Funnel<T> funnel;
public BloomFilterHelper(int expectedInsertions) {
this.funnel = (Funnel<T>) Funnels.stringFunnel(Charset.defaultCharset());
bitSize = optimalNumOfBits(expectedInsertions, 0.03);
numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, bitSize);
}
public BloomFilterHelper(Funnel<T> funnel, int expectedInsertions, double fpp) {
this.funnel = funnel;
bitSize = optimalNumOfBits(expectedInsertions, fpp);
numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, bitSize);
}
public int[] murmurHashOffset(T value) {
int[] offset = new int[numHashFunctions];
long hash64 = Hashing.murmur3_128().hashObject(value, funnel).asLong();
int hash1 = (int) hash64;
int hash2 = (int) (hash64 >>> 32);
for (int i = 1; i <= numHashFunctions; i++) {
int nextHash = hash1 + i * hash2;
if (nextHash < 0) {
nextHash = ~nextHash;
}
offset[i - 1] = nextHash % bitSize;
}
return offset;
}
/**
* 计算bit数组长度
*/ private int optimalNumOfBits(long n, double p) {
if (p == 0) {
p = Double.MIN_VALUE;
}
return (int) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
}
/**
* 计算hash方法执行次数
*/ private int optimalNumOfHashFunctions(long n, long m) {
return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
}
}
|
这里在操作redis的位图bitmap
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
/**
* redis操作布隆过滤器
*
* @param <T>
* @author xhj
*/public class RedisBloomFilter<T> {
@Autowired private RedisTemplate redisTemplate;
/**
* 删除缓存的KEY
*
* @param key KEY
*/ public void delete(String key) {
redisTemplate.delete(key);
}
/**
* 根据给定的布隆过滤器添加值，在添加一个元素的时候使用，批量添加的性能差
*
* @param bloomFilterHelper 布隆过滤器对象
* @param key KEY
* @param value 值
* @param <T> 泛型，可以传入任何类型的value
*/ public <T> void add(BloomFilterHelper<T> bloomFilterHelper, String key, T value) {
int[] offset = bloomFilterHelper.murmurHashOffset(value);
for (int i : offset) {
redisTemplate.opsForValue().setBit(key, i, true);
}
}
/**
* 根据给定的布隆过滤器添加值，在添加一批元素的时候使用，批量添加的性能好，使用pipeline方式(如果是集群下，请使用优化后RedisPipeline的操作)
*
* @param bloomFilterHelper 布隆过滤器对象
* @param key KEY
* @param valueList 值，列表
* @param <T> 泛型，可以传入任何类型的value
*/ public <T> void addList(BloomFilterHelper<T> bloomFilterHelper, String key, List<T> valueList) {
redisTemplate.executePipelined(new RedisCallback<Long>() {
@Override public Long doInRedis(RedisConnection connection) throws DataAccessException {
connection.openPipeline();
for (T value : valueList) {
int[] offset = bloomFilterHelper.murmurHashOffset(value);
for (int i : offset) {
connection.setBit(key.getBytes(), i, true);
}
}
return null;
}
});
}
/**
* 根据给定的布隆过滤器判断值是否存在
*
* @param bloomFilterHelper 布隆过滤器对象
* @param key KEY
* @param value 值
* @param <T> 泛型，可以传入任何类型的value
* @return 是否存在
*/ public <T> boolean contains(BloomFilterHelper<T> bloomFilterHelper, String key, T value) {
int[] offset = bloomFilterHelper.murmurHashOffset(value);
for (int i : offset) {
if (!redisTemplate.opsForValue().getBit(key, i)) {
return false;
}
}
return true;
}
}
|
Test
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
public static void main(String[] args) {
RedisBloomFilter redisBloomFilter = new RedisBloomFilter();
int expectedInsertions = 1000;
double fpp = 0.1;
redisBloomFilter.delete("bloom");
BloomFilterHelper<CharSequence> bloomFilterHelper = new BloomFilterHelper<>(Funnels.stringFunnel(Charset.defaultCharset()), expectedInsertions, fpp);
int j = 0;
// 添加100个元素 List<String> valueList = new ArrayList<>();
for (int i = 0; i < 100; i++) {
valueList.add(i + "");
}
long beginTime = System.currentTimeMillis();
redisBloomFilter.addList(bloomFilterHelper, "bloom", valueList);
long costMs = System.currentTimeMillis() - beginTime;
log.info("布隆过滤器添加{}个值，耗时：{}ms", 100, costMs);
for (int i = 0; i < 1000; i++) {
boolean result = redisBloomFilter.contains(bloomFilterHelper, "bloom", i + "");
if (!result) {
j++;
}
}
log.info("漏掉了{}个,验证结果耗时：{}ms", j, System.currentTimeMillis() - beginTime);
}
|
addList，它的底层是pipelining管道，而add方法的底层是一个个for循环的setBit，这样的速度效率是很慢的，但是他能有返回值，知道是否插入成功，而pipelining是不知道的，所以具体选择用哪一种方法看你的业务场景，以及需要插入的速度决定。
Redisson - RBloomFilter
Redis based distributed RBloomFilter bloom filter for Java. Number of contained bits is limited to 2^32.
Must be initialized with capacity size by tryInit(expectedInsertions, falseProbability) method before usage.
1
2
3
4
5
6
7
8
9
10
11
|
RBloomFilter<SomeObject> bloomFilter = redisson.getBloomFilter("sample");
// initialize bloom filter with
// expectedInsertions = 55000000
// falseProbability = 0.03
bloomFilter.tryInit(55000000L, 0.03);
bloomFilter.add(new SomeObject("field1Value", "field2Value"));
bloomFilter.add(new SomeObject("field5Value", "field8Value"));
bloomFilter.contains(new SomeObject("field1Value", "field8Value"));
bloomFilter.count();
|
布隆过滤器工作位置
第一步是将数据库所有的数据加载到布隆过滤器。第二步当有请求来的时候先去布隆过滤器查询，如果bf说没有，第三步直接返回。
最佳实践
常见的适用常见有，利用布隆过滤器减少磁盘 IO 或者网络请求，因为一旦一个值必定不存在的话，我们可以不用进行后续昂贵的查询请求。
另外，既然你使用布隆过滤器来加速查找和判断是否存在，那么性能很低的哈希函数不是个好选择，推荐 MurmurHash、Fnv 这些。
大Value拆分
Redis 因其支持 setbit 和 getbit 操作，且纯内存性能高等特点，因此天然就可以作为布隆过滤器来使用。但是布隆过滤器的不当使用极易产生大 Value，增加 Redis 阻塞风险，因此生成环境中建议对体积庞大的布隆过滤器进行拆分。
拆分的形式方法多种多样，但是本质是不要将 Hash(Key) 之后的请求分散在多个节点的多个小 bitmap 上，而是应该拆分成多个小 bitmap 之后，对一个 Key 的所有哈希函数都落在这一个小 bitmap 上。
