布隆过滤器

0x00 适用场景

一开始学这个布隆过滤器是为了一个分布式爬虫的项目,在这个项目中有一个需求就是判断队列中的URL是否先前已经爬取过了。如果先前已经爬取过了,那就不爬了,如果没有,那就爬取这个URL。然后就了解到了这个布隆过滤器和RedisBloom

布隆过滤器说白了主要应用于在大量数据中判断给定数据是否存在。 这是一种基于概率的算法,什么意思呢,就是说,不存在的一定返回false,而返回true的却不一定存在。也就说它有一定的误判率。

0x01 基本原理

布隆过滤器的基本组件其实很简单,一系列的hash函数以及一个存放位序列的大表。现在我们假定一个长度为8的表,初始状态下,表中的元素均为0:

+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+

现在有一组Hash函数,hash1(data)hash2(data)。对于一个给定数据liu,我们假设hash1hash2函数的返回值分别为为2, 4,那在这个大表中,翻置下标为2和4的元素为1,如下:

+---+---+---+---+---+---+---+---+
| 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+

对于另外一个给定数据shao,我们假设hash1hash2函数的返回值分别为为3, 2,继续翻置,如下:

+---+---+---+---+---+---+---+---+
| 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+

当我们试图判断数据liu是否存在时,我们对这组新的数据计算那两个Hash函数,如果返回的下标在大表中所指向的字节均为1的话,那么数据存在,否则,数据不存在。

但是这样就会出现一个问题,在上面的例子中,输入数据liushao均翻置了下标为2的元素,这一位被2个不同的值的hash共同覆盖了。假设我们要删除数据liu然后把下标为2和4的数据重新置为0的话,那么当我们试图判断数据shao是否存在时就会返回false,显然这是错误的,因为我们并没有删除数据shao。基于此点布隆过滤器是不支持删除的

除此之外,对于两组不相同的数据,两个hash函数可能返回相同的下标地址,假设对于输入数据liuqun而言,两组hash函数均分别返回下标2和4,那我当插入数据liu之后,在过滤器中判断数据qun是否存在,过滤器是会返回true的,这就是误判。在Guava中,BloomFilter默认的误判率是3%,这个值在Guava中可以调的,误判率越低,这个大表就越大。这个大表的大小m和误判率fpp以及预估数据量n之间的关系为:

m=nln(fpp)(ln2)2m=-\frac{n\ln(\text{fpp})}{(\ln2)^2}

hash函数的个数k与表的大小m和预估数据量n之间的关系为:

k=mnln2k=\frac{m}{n}\ln 2

有此我们可见,误判率的大小和大表的大小m和hash函数的个数k都是呈负相关的。同时还有一幅图可以参考一下:

在Guava中,计算大表长度m和hash函数的个数k就是用的如上公式:

/**
* 计算 Bloom Filter的bit位数m
*
* <p>See http://en.wikipedia.org/wiki/Bloom_filter#Probability_of_false_positives for the
* formula.
*
* @param n 预期数据量
* @param p 误判率 (must be 0 < p < 1)
*/
@VisibleForTesting
static long optimalNumOfBits(long n, double p) {
if (p == 0) {
p = Double.MIN_VALUE;
}
return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
}
/**
* 计算最佳k值,即在Bloom过滤器中插入的每个元素的哈希数
*
* <p>See http://en.wikipedia.org/wiki/File:Bloom_filter_fp_probability.svg for the formula.
*
* @param n 预期数据量
* @param m bloom filter中总的bit位数 (must be positive)
*/
@VisibleForTesting
static int optimalNumOfHashFunctions(long n, long m) {
// (m / n) * log(2), but avoid truncation due to division!
return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
}

0x02 RedisBloom的使用

0x00 基于docker的快速部署

我们可以使用docker快速部署一个RedisBloom应用:

docker pull redislabs/rebloom:latest # 拉取镜像
docker run -d -p 6379:6379 --name redis-redisbloom redislabs/rebloom:latest # 启动镜像

0x01 控制台下使用RedisBloom

首先我们进入刚刚用docker启动的RedisBloom应用:

docker exec -it redis-redisbloom redis-cli

BF.RESERVE:创建一个新的布隆过滤器

BF.RESERVE {key} {error_rate} {capacity} [EXPANSION expansion] [NONSCALING]

必选参数:

  • key:新过滤器的名字

  • error_rate:预设的错误率

  • capacity:预计添加到布隆过滤器中的元素的个数

可选参数:

  • NONSCALING:如果设置了此项,当添加到布隆过滤器中的数据达到初始容量之后,不会扩容过滤器,并且超过初始设置容量的添加会抛出异常。

  • expansion:与上一项相反,当设置了此项,布隆过滤器中存储的元素达到初始容量后会自动创建一个子过滤器,子过滤器的大小是上一个过滤器大小乘以参数expansion

复杂度为: O(1)O(1)

示例:

127.0.0.1:6379> BF.RESERVE newFilter 0.03 100 EXPANSION 2
OK
(0.51s)

创建一个新的布隆过滤器命名为newFilter,预设的错误率为0.03 (3%),预计添加100个元素,超出之后自动创建子过滤器,子过滤器的大小是最后一个过滤器大小的2倍。

BF.ADD:向布隆过滤器中添加一个元素,BF.MADD:批量添加元素

BF.ADD {key} {item}
BF.MADD {key} {item} [item...]
  • key:过滤器名

  • item:需添加的元素

返回结果为1表示插入成功,返回结果为0表示插入的元素此前可能已经存在,也可能是发生了冲突,也就是此前添加的元素和当前添加的元素产生了相同的hash值。对于BF.MADD将会返回一个数组,数组内各数意义上同。

复杂度: O(n×k)O(n \times k)nn 为插入的元素的个数, kk 为hash函数的个数。

示例:

127.0.0.1:6379> BF.ADD newFilter shaoqun-liu
(integer) 1

BF.EXISTS:判断值是否在布隆过滤器中存在,BF.MEXISTS:批量判断

BF.EXISTS {key} {item}
BF.MEXISTS {key} {item} [item...]
  • key:过滤器名

  • item:查询的元素

返回0表示元素不存在,返回1表示元素可能存在。

复杂度: O(n×k)O(n \times k)nn 为插入的元素的个数, kk 为hash函数的个数。

示例:

127.0.0.1:6379> BF.EXISTS newFilter shaoqun-liu
(integer) 1
127.0.0.1:6379> BF.EXISTS newFilter shaoqun
(integer) 0

BF.INFO:查询某布隆过滤器的详细信息

BF.INFO {key}
  • key:过滤器名

示例:

127.0.0.1:6379> BF.INFO newFilter
1) Capacity
2) (integer) 100
3) Size
4) (integer) 262
5) Number of filters
6) (integer) 1
7) Number of items inserted
8) (integer) 1
9) Expansion rate
10) (integer) 2

其它命令可参考官方文档:

RedisBloom Bloom Filter Command Documentation

0x02 Java API

首先,我们可以使用Maven导入依赖:

<!-- https://mvnrepository.com/artifact/com.redislabs/jrebloom -->
<dependency>
<groupId>com.redislabs</groupId>
<artifactId>jrebloom</artifactId>
<version>1.2.0</version>
</dependency>

我在我们的项目中,将其Client注册成了一个bean,方便日后调用,首先我们在项目的application.yml文件中配置了相关的Redis地址信息:

redis:
bloom:
url: 192.168.50.131
port: 6379
init-capacity: 10000
error-rate: 0.01

这几个字段都是我自定义的,如果有需要可以自己设置,然后我们创建一个Spring boot的Configuration类,导出用于操作的Client的bean,如下:

package com.cstiaoji.spider.configuration;
import org.springframework.beans.factory.annotation.Value;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;
import io.rebloom.client.Client;
@Configuration
public class RedisConfiguration {
// 从application.yml文件中引入配置信息
@Value("${redis.bloom.url:#{null}}")
private String rebloomUrl;
@Value("${redis.bloom.port:#{null}}")
private Integer rebloomPort;
@Value("${redis.bloom.init-capacity:#{null}}")
private Integer rebloomInitCapacity;
@Value("${redis.bloom.error-rate:#{null}}")
private Double rebloomErrorRate;
// 导出bean
@Bean("rebloomClient")
public Client rebloomClient() {
Client client = new Client(rebloomUrl, rebloomPort);
// 创建一个新的bloom过滤器
client.createFilter("cstiaoji-spider", rebloomInitCapacity, rebloomErrorRate);
return client;
}
}

然后在我们的业务逻辑代码中,就可以使用如下代码进行相关的操作了:

// 向名为cstiaoji-spider的布隆过滤器中添加值"www.baidu.com"
// 返回true
client.add("cstiaoji-spider", "www.baidu.com");
// 在名为cstiaoji-spider的布隆过滤器中判断值"www.baidu.com"是否存在
// 返回一个boolean类型的值,为true则可能存在,为false则不存在
client.exists("cstiaoji-spider", "www.baidu.com");

更多信息可参考当前项目GitHub