玩转Redis-Redis中布隆过滤器的使用及原理

2020-09-21 400

《玩转Redis》系列文章主要讲述Redis的基础及中高级应用。本文是《玩转Redis》系列第【11】篇，最新系列文章请前往公众号“zxiaofan”查看，或百度搜索“玩转Redis zxiaofan”即可。

本文关键字：玩转Redis、Bloom filter、布隆过滤器、无偏hash函数；

大纲

布隆过滤器介绍
- 什么是布隆过滤器
- 布隆过滤器有什么特性
Redis布隆过滤器实战
- rebloom的安装
- 布隆过滤器的命令详解及示例
布隆过滤器的底层原理
- 布隆过滤器的底层结构
- 最佳hash函数数量与错误率的关系
- 所需存储空间与错误率及容量关系
- 布隆过滤器如何扩容
布隆过滤器有哪些应用场景
布隆过滤器的优缺点
延伸拓展

1、布隆过滤器介绍

先前我们学习了HyperLogLog（传送门《玩转Redis-HyperLogLog原理探索》《玩转Redis-HyperLogLog统计微博日活月活》），非常适合大数据下的基数计算场景，但其有个缺陷，无法判断某个值是否已存在。

Hash、Set、String的BitMap等可以实现判断元素是否存在的功能，但这些实现方式要么随着元素增多会占用大量内存（Hash、Set），要么无法动态伸缩和保持误判率不变（BitMap）。因此，我们非常需要一种可以高效判断大量数据是否存在且允许一定误判率的数据结构。

1.1、什么是布隆过滤器（Bloom Filter）

布隆过滤器由Burton Howard Bloom于1970年提出，用于判断一个元素是否在集合中。

布隆过滤器（Bloom filter）是一种非常节省空间的概率数据结构（space-efficient probabilistic data structure），运行速度快（时间效率），占用内存小（空间效率），但是有一定的误判率且无法删除元素。本质上由一个很长的二进制向量和一系列随机映射函数组成。

1.2 布隆过滤器有什么特性

检查一个元素是否在集成中；
检查结果分为2种：一定不在集合中、可能在集合中；
布隆过滤器支持添加元素、检查元素，但是不支持删除元素；
检查结果的“可能在集合中”说明存在一定误判率；
- 已经添加进入布隆过滤器的元素是不会被误判的，仅未添加过的元素才可能被误判；
相比set、Bitmaps非常节省空间：因为只存储了指纹信息，没有存储元素本身；
添加的元素超过预设容量越多，误报的可能性越大。

2、Redis布隆过滤器实战

2.1、rebloom的安装

还没有安装Redis的同学，可以参考我先前的文章安装，传送门《玩转Redis-Redis安装、后台启动、卸载》。Redis 4.0开始以插件形式提供布隆过滤器。

# docker方式安装

&gt; docker pull redislabs/rebloom  # 拉取镜像
&gt; docker run -p6379:6379 redislabs/rebloom  # 运行容器
&gt; redis-cli  # 连接容器中的 redis 服务

# linux服务器直接安装

&gt;git clone git://github.com/RedisLabsModules/rebloom
&gt;cd rebloom
&gt;make
# 当前路径会生成一个rebloom.so文件
# 在redis的配置中（通常在/etc/redis/redis.conf）增加一行配置 loadmodule /"rebloom.so的绝对路径"/rebloom.so
# 重启Redis即可

上述的安装提到需要重启Redis，但是生产环境的Redis可不是你想重启就重启的。有什么方式可以不重启Redis就加载rebloom插件吗，MODULE LOAD命令就派上用场了。

# 不重启Redis加载rebloom插件

1、查看redis当前已加载的插件
&gt; MODULE LOAD /"rebloom.so的绝对路径"/redisbloom.so
&gt; module list
1) 1) "name"
   2) "bf"
   3) "ver"
   4) (integer) 999999
# 看到以上数据则说明redisbloom加载成功了，模块名name为"bf"，模块版本号ver为999999。

# 动态执行模块卸载
# MODULE UNLOAD 模块名

# 当然，为了防止Redis重启导致动态加载的模块丢失，我们还是应该在redis.conf 中加上相关配置。

2.2、布隆过滤器的命令详解及示例

完整指令说明可前往官网查看：https://oss.redislabs.com/redisbloom/Bloom_Commands/。

2.2.1、Bloom命令简述

【核心命令】添加元素：BF.ADD（添加单个）、BF.MADD（添加多个）、BF.INSERT（添加多个）；

【核心命令】检查元素是否存在：BF.EXISTS（查询单个元素）、BF.MEXISTS（查询多个元素）

命令	功能	参数
BF.RESERVE	创建一个大小为capacity，错误率为error_rate的空的Bloom	BF.RESERVE {key} {error_rate} {capacity} [EXPANSION expansion] [NONSCALING]
BF.ADD	向key指定的Bloom中添加一个元素item	BF.ADD {key} {item}
BF.MADD	向key指定的Bloom中添加多个元素	BF.MADD {key} {item} [item...]
BF.INSERT	向key指定的Bloom中添加多个元素，添加时可以指定大小和错误率，且可以控制在Bloom不存在的时候是否自动创建	BF.INSERT {key} [CAPACITY {cap}] [ERROR {error}] [EXPANSION expansion] [NOCREATE] [NONSCALING] ITEMS {item...}
BF.EXISTS	检查一个元素是否可能存在于key指定的Bloom中	BF.EXISTS {key} {item}
BF.MEXISTS	同时检查多个元素是否可能存在于key指定的Bloom中	BF.MEXISTS {key} {item} [item...]
BF.SCANDUMP	对Bloom进行增量持久化操作	BF.SCANDUMP {key} {iter}
BF.LOADCHUNK	加载SCANDUMP持久化的Bloom数据	BF.LOADCHUNK {key} {iter} {data}
BF.INFO	查询key指定的Bloom的信息	BF.INFO {key}
BF.DEBUG	查看BloomFilter的内部详细信息（如每层的元素个数、错误率等）	BF.DEBUG {key}

2.2.2、BF.RESERVE

参数
- BF.RESERVE {key} {error_rate} {capacity}
功能
- 创建一个大小为capacity，错误率为error_rate的空的BloomFilter
时间复杂度
- O(1)
参数说明
- key：布隆过滤器的key；
- error_rate：期望的错误率（False Positive Rate），该值必须介于0和1之间。该值越小，BloomFilter的内存占用量越大，CPU使用率越高。
- capacity：布隆过滤器的初始容量，即期望添加到布隆过滤器中的元素的个数。当实际添加的元素个数超过该值时，布隆过滤器将进行自动的扩容，该过程会导致性能有所下降，下降的程度是随着元素个数的指数级增长而线性下降。
可选参数
- expansion：当添加到布隆过滤器中的数据达到初始容量后，布隆过滤器会自动创建一个子过滤器，子过滤器的大小是上一个过滤器大小乘以expansion。expansion的默认值是2，也就是说布隆过滤器扩容默认是2倍扩容。
- NONSCALING：设置此项后，当添加到布隆过滤器中的数据达到初始容量后，不会扩容过滤器，并且会抛出异常（(error) ERR non scaling filter is full）。
返回值
- 成功：OK；
- 其它情况返回相应的异常信息。
备注
- BloomFilter的扩容是通过增加BloomFilter的层数来完成的。每增加一层，在查询的时候就可能会遍历多层BloomFilter来完成，每一层的容量都是上一层的两倍（默认）。

# 公众号@zxiaofan
# 创建一个容量为5且不允许扩容的过滤器；
127.0.0.1:6379&gt; bf.reserve bf2 0.1 5 NONSCALING
OK
127.0.0.1:6379&gt; bf.madd bf2 1 2 3 4 5
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 1
5) (integer) 1

# 添加第6个元素时即提示BloomFilter已满；
127.0.0.1:6379&gt; bf.madd bf2 6
1) (error) ERR non scaling filter is full
127.0.0.1:6379&gt; bf.info bf2
 1) Capacity
 2) (integer) 5
 3) Size
 4) (integer) 155
 5) Number of filters
 6) (integer) 1
 7) Number of items inserted
 8) (integer) 5
 9) Expansion rate
10) (integer) 2

2.2.3、BF.ADD

参数
- BF.ADD {key} {item}
功能
- 向key指定的Bloom中添加一个元素item。
时间复杂度
- O(log N)，N是过滤器的层数。
参数说明
- key：布隆过滤器的名字；
- item：待插入过滤器的元素；
返回值
- 元素不存在插入成功：返回1；
- 元素可能已经存在：返回0；
- 其它情况返回相应的异常信息。

2.2.3、BF.MADD

参数
- BF.MADD {key} {item} [item...]
功能
- 向key指定的Bloom中添加多个元素item。
时间复杂度
- O(log N)，N是过滤器的层数。
参数说明
- key：布隆过滤器的名字；
- item：待插入过滤器的元素，可插入多个；
返回值
- 成功：返回一个数组，数组的每一个元素可能为1或0，当item一定不存在时数组元素值为1，当item可能已经存在时数组元素值为0。
- 其它情况返回相应的异常信息。

2.2.5、BF.EXISTS

参数
- BF.EXISTS {key} {item}
功能
- 检查一个元素是否可能存在于key指定的Bloom中
时间复杂度
- O(log N)，N是过滤器的层数。
参数说明
- key：布隆过滤器的名字；
- item：待检查的元素；
返回值
- 元素一定不存在：0；
- 元素可能存在：1；
- 其它情况返回相应的异常信息。

2.2.6、BF.MEXISTS

参数
- BF.MEXISTS <key> <item> [item...]
功能
- 检查多个元素是否可能存在于key指定的Bloom中
时间复杂度
- O(log N)，N是过滤器的层数。
参数说明
- key：布隆过滤器的名字；
- item：待检查的元素，可设置多个；
返回值
- 成功：返回一个数组，数组的每一个元素可能为1或0，当item一定不存在时数组元素值为0，当item可能已经存在时数组元素值为1。
- 其它情况返回相应的异常信息。

# 公众号@zxiaofan
# 向BloomFilter添加单个元素
127.0.0.1:6379&gt; bf.add bf1 itemadd1
(integer) 1

# 向BloomFilter批量添加多个元素
127.0.0.1:6379&gt; bf.madd bf1 itemmadd1 itemmadd2
1) (integer) 1
2) (integer) 1
127.0.0.1:6379&gt; bf.exists itemmadd1
(error) ERR wrong number of arguments for 'bf.exists' command
127.0.0.1:6379&gt; bf.exists bf1 itemmadd1
(integer) 1

# 批量检查多个元素是否存在于BloomFilter
127.0.0.1:6379&gt; bf.mexists bf1 itemadd1 itemmadd1 itemmadd2
1) (integer) 1
2) (integer) 1
3) (integer) 1

```c

### 2.2.7、BF.INSERT
- 参数
  - BF.INSERT {key} [CAPACITY {cap}] [ERROR {error}] [EXPANSION expansion] [NOCREATE] [NONSCALING] ITEMS {item...}
- 功能
  - 向key指定的Bloom中添加多个元素，添加时可以指定大小和错误率，且可以控制在Bloom不存在的时候是否自动创建	
- 时间复杂度
  - O(log N)，N是过滤器的层数。
- 参数说明
  - key：布隆过滤器的名字；
  - CAPACITY：[如果过滤器已创建，则此参数将被忽略]。更多的信息参考<bf.reserve>；
  - ERROR：[如果过滤器已创建，则此参数将被忽略]。更多的信息参考<bf.reserve>；
  - expansion：布隆过滤器会自动创建一个子过滤器，子过滤器的大小是上一个过滤器大小乘以expansion。expansion的默认值是2，也就是说布隆过滤器扩容默认是2倍扩容。
  - NOCREATE：如果设置了该参数，当布隆过滤器不存在时则不会被创建。用于严格区分过滤器的创建和元素插入场景。该参数不能与CAPACITY和ERROR同时设置。
  - NONSCALING：设置此项后，当添加到布隆过滤器中的数据达到初始容量后，不会扩容过滤器，并且会抛出异常（(error) ERR non scaling filter is full）。
  - ITEMS：待插入过滤器的元素列表，该参数必传。
- 返回值
  - 成功：返回一个数组，数组的每一个元素可能为1或0，当item一定不存在时数组元素值为1，当item可能已经存在时数组元素值为0。
  - 其它情况返回相应的异常信息。


```c
127.0.0.1:6379&gt; del bfinsert
(integer) 1

127.0.0.1:6379&gt; bf.insert bfinsert CAPACITY 5 ERROR 0.1 EXPANSION 2  NONSCALING ITEMS item1 item2
1) (integer) 1
2) (integer) 1
127.0.0.1:6379&gt; bf.exists bfinsert item5
(integer) 0
127.0.0.1:6379&gt; bf.insert bfinsert CAPACITY 5 ERROR 0.1 EXPANSION 2  NONSCALING ITEMS item1 item2 item3 item4 item5
1) (integer) 0
2) (integer) 0
3) (integer) 1
4) (integer) 1
5) (integer) 0
127.0.0.1:6379&gt; bf.add bfinsert item5
(integer) 0
127.0.0.1:6379&gt; bf.info bfinsert
 1) Capacity
 2) (integer) 5
 3) Size
 4) (integer) 155
 5) Number of filters
 6) (integer) 1
 7) Number of items inserted
 8) (integer) 4
 9) Expansion rate
10) (integer) 2
127.0.0.1:6379&gt; bf.add bfinsert item6
(integer) 1
127.0.0.1:6379&gt; bf.add bfinsert item5
(integer) 0
127.0.0.1:6379&gt; bf.exists bfinsert item5
(integer) 1

# 这里有个比较有意思的现象，item5未显示添加成功，但是后续却显示exists
# 这说明发生了hash冲突，误判就是这样产生的。

2.2.8、BF.SCANDUMP

参数
- BF.SCANDUMP {key} {iter}
功能
- 对Bloom进行增量持久化操作（增量保存）；
时间复杂度
- O(log N)，N是过滤器的层数。
参数说明
- key：布隆过滤器的名字；
- iter：首次调用传值0，或者上次调用此命令返回的结果值；
返回值
- 返回连续的(iter, data)对，直到(0,NULL)，表示DUMP完成。
备注

127.0.0.1:6378&gt; bf.madd bfdump d1 d2 d3 d4 d5 d6 d7
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 1
5) (integer) 1
6) (integer) 1
7) (integer) 1
127.0.0.1:6378&gt; bf.scandump bfdump 0
1) (integer) 1
2) "\a\x00\x00\x00\x00\x00\x00\x00\x01\x00\x00\x00\x05\x00\x00\x00\x02\x00\x00\x00\x8a\x00\x00\x00\x00\x00\x00\x00P\x04\x00\x00\x00\x00\x00\x00\a\x00\x00\x00\x00\x00\x00\x00{\x14\xaeG\xe1zt?\xe9\x86/\xb25\x0e&amp;@\b\x00\x00\x00d\x00\x00\x00\x00\x00\x00\x00\x00"
127.0.0.1:6378&gt; bf.scandump bfdump 1
1) (integer) 139
2) "\x80\x00\b\n\x00$\x00 \b\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\b\x00\x00\x00\x00\x82$\x04\x00@\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x02\x04\x00\x00\x00\x00\x00\x00\x04\x01@\xa0\x00@\x00\x00\x00\x00\x00\x10@\x00\x02\"\x00 \x00\x00\x04\x00\x00\x00\x00\x00 \x00\x80\x00\x00\"\x04\x04\x04\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x80\x00\x00\x00\x00\x00 \x80$\x00 \x00\x00 \x0c$\x00\x00\x00\b`\x00\x00\x00\x00\x00\x00\x00\x00\b\x80\x02 \x04\x00\x00\x00\x00\x00"
127.0.0.1:6378&gt; bf.scandump bfdump 139
1) (integer) 0
2) ""

2.2.9、BF.LOADCHUNK

参数
- BF.LOADCHUNK {key} {iter} {data}
功能
- 加载SCANDUMP持久化的Bloom数据；
时间复杂度
- O(log N)，N是过滤器的层数。
参数说明
- key：目标布隆过滤器的名字；
- iter：SCANDUMP返回的迭代器的值，和data一一对应；
- data：SCANDUMP返回的数据块（data chunk）；
返回值
- 成功则返回OK。

# Python 伪代码
# 来源于：https://oss.redislabs.com/redisbloom/Bloom_Commands/

chunks = []
iter = 0
# SCANDUMP
while True:
    iter, data = BF.SCANDUMP(key, iter)
    if iter == 0:
        break
    else:
        chunks.append([iter, data])

# LOADCHUNK
for chunk in chunks:
    iter, data = chunk
    BF.LOADCHUNK(key, iter, data)

2.2.10、BF.INFO

参数
- BF.INFO {key}
功能
- 返回BloomFilter的相关信息；
时间复杂度
- O(1)；
参数说明
- key：目标布隆过滤器的名字；
返回值
- Capacity：预设容量；
- Size：实际占用情况，但如何计算待进一步确认；
- Number of filters：过滤器层数；
- Number of items inserted：已经实际插入的元素数量；
- Expansion rate：子过滤器扩容系数（默认2）；

127.0.0.1:6379&gt; bf.info bf2
 1) Capacity
 2) (integer) 5
 3) Size
 4) (integer) 155
 5) Number of filters
 6) (integer) 1
 7) Number of items inserted
 8) (integer) 5
 9) Expansion rate
10) (integer) 2

2.2.11、BF.DEBUG

参数
- BF.DEBUG {key}
功能
- 查看BloomFilter的内部详细信息（如每层的元素个数、错误率等）；
时间复杂度
- O(log N)，N是过滤器的层数；
参数说明
- key：目标布隆过滤器的名字；
返回值
- size：BloomFilter中已插入的元素数量；
- 每层BloomFilter的详细信息
  - bytes：占用字节数量；
  - bits：占用bit位数量，bits = bytes * 8；
  - hashes：该层hash函数数量；
  - hashwidth：hash函数宽度；
  - capacity：该层容量（第一层为BloomFilter初始化时设置的容量，第2层容量 = 第一层容量 * expansion，以此类推）；
  - size：该层中已插入的元素数量（各层size之和等于BloomFilter中已插入的元素数量size）；
  - ratio：该层错误率（第一层的错误率 = BloomFilter初始化时设置的错误率 * 0.5，第二层为第一层的0.5倍，以此类推，ratio与expansion无关）；

# 公众号 @zxiaofan
# 创建一个容量为5的BloomFilter，其key为“bfexp”；
127.0.0.1:6379&gt; bf.reserve bfexp 0.1 5
OK

# 查看BloomFilter的内部信息，此时BloomFilter的层数为1
127.0.0.1:6379&gt; bf.debug bfexp
1) "size:0"
2) "bytes:4 bits:32 hashes:5 hashwidth:64 capacity:5 size:0 ratio:0.05"

127.0.0.1:6379&gt; bf.madd bfexp 1 2 3 4 5
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 1
5) (integer) 1
127.0.0.1:6379&gt; bf.debug bfexp
1) "size:5"
2) "bytes:4 bits:32 hashes:5 hashwidth:64 capacity:5 size:5 ratio:0.05"

127.0.0.1:6379&gt; bf.madd bfexp 11 12 13 14 15
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 0
5) (integer) 1

# 添加10个元素后，此时BloomFilter的层数变为2；
# BloomFilter的元素数量为2层过滤器之和（5+4=9），添加“14”时实际因为hash冲突没添加成功；
127.0.0.1:6379&gt; bf.debug bfexp
1) "size:9"
2) "bytes:4 bits:32 hashes:5 hashwidth:64 capacity:5 size:5 ratio:0.05"
3) "bytes:10 bits:80 hashes:6 hashwidth:64 capacity:10 size:4 ratio:0.025"

127.0.0.1:6379&gt; bf.madd bfexp 21 22 23
1) (integer) 1
2) (integer) 1
3) (integer) 1
127.0.0.1:6379&gt; bf.debug bfexp
1) "size:12"
2) "bytes:4 bits:32 hashes:5 hashwidth:64 capacity:5 size:5 ratio:0.05"
3) "bytes:10 bits:80 hashes:6 hashwidth:64 capacity:10 size:7 ratio:0.025"
127.0.0.1:6379&gt; bf.madd bfexp  24 25
1) (integer) 1
2) (integer) 1
127.0.0.1:6379&gt; bf.debug bfexp
1) "size:14"
2) "bytes:4 bits:32 hashes:5 hashwidth:64 capacity:5 size:5 ratio:0.05"
3) "bytes:10 bits:80 hashes:6 hashwidth:64 capacity:10 size:9 ratio:0.025"
127.0.0.1:6379&gt; bf.madd bfexp 31 32 33 34 35
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 1
5) (integer) 1

# 添加20个元素后，此时BloomFilter的层数变为3；
127.0.0.1:6379&gt; bf.debug bfexp
1) "size:19"
2) "bytes:4 bits:32 hashes:5 hashwidth:64 capacity:5 size:5 ratio:0.05"
3) "bytes:10 bits:80 hashes:6 hashwidth:64 capacity:10 size:10 ratio:0.025"
4) "bytes:23 bits:184 hashes:7 hashwidth:64 capacity:20 size:4 ratio:0.0125"

3、布隆过滤器的底层原理

3.1、布隆过滤器的底层结构

布隆过滤器本质是一个巨大的bit数组（bit array）+几个不同的无偏hash函数。

布隆过滤器添加一个item("zxiaofan")，其操作步骤是：

使用多个无偏哈希函数对item进行hash运算，得到多个hash值hash(zxiaofan)；
每个hash值对bit数组取模得到位数组中的位置index(zxiaofan)；
判断所有index位是否都为1 ；
位都为1则说明该元素可能已经存在了；
任意一位不为1则说明一定不存在，此时会将不为1的位置为1；

需要注意的是，虽然使用了无偏hash函数，使得hash值尽可能均匀，但是不同的item计算出的hash值依旧可能重复，所以布隆过滤器返回元素存在，实际是有可能不存在的。

> 取模运算（“Modulus Operation”）和取余运算（“Remainder Operation ”）两个概念有重叠的部分但又不完全一致。主要的区别在于对负整数进行除法运算时操作不同。取模主要是用于计算机术语中。取余则更多是数学概念。a mod b = c，a、b符号一致时，取模、取余计算得出的C相同；a、b符号不一致时，取模计算的c其符号和b一致，取余计算的C其符号和a一致。

3.2、最佳hash函数数量与错误率的关系

源码中的hash函数数量计算公式：

# hash函数数量计算公式：

# ceil(value)：返回不小于value的最小整数；
# log(error)：以10为底的对数函数；
# ln(x)：以e为底的对数函数；
# ln(2) ≈ 0.693147180559945;
# ln(2)^2 ≈ 0.480453013918201;

bloom-&gt;hashes = (int)ceil(0.693147180559945 * bloom-&gt;bpe);

static double calc_bpe(double error) {
    static const double denom = 0.480453013918201; // ln(2)^2
    double num = log(error);

    double bpe = -(num / denom);
    if (bpe &lt; 0) {
        bpe = -bpe;
    }
    return bpe;
}

我们通过创建不同错误率不同容量的布隆过滤器，整理hash函数数量与错误率的关系。

# 公众号@zxiaofan
# 创建一个key为“bf0.1-2”的布隆过滤器，其错误率为0.1，初始容量为100；
127.0.0.1:6379&gt; bf.reserve bf0.1-2 0.1 100
OK
127.0.0.1:6379&gt; bf.reserve bf0.1-3 0.1 1000
OK
127.0.0.1:6379&gt; bf.reserve bf0.01-3 0.01 1000
OK
127.0.0.1:6379&gt; bf.reserve bf0.01-4 0.01 10000
OK
127.0.0.1:6379&gt; bf.reserve bf0.001-4 0.001 10000
OK
127.0.0.1:6379&gt; bf.reserve bf0.001-5 0.001 100000
OK
127.0.0.1:6379&gt; bf.reserve bf0.0001-5 0.0001 100000
OK
127.0.0.1:6379&gt; bf.reserve bf0.00001-5 0.00001 100000
OK
127.0.0.1:6379&gt; bf.reserve bf0.000001-5 0.000001 100000
OK
127.0.0.1:6379&gt; bf.reserve bf0.000001-4 0.000001 10000
OK

# 创建一个key为“bf0.0000001-4”的布隆过滤器，其错误率为0.0000001，初始容量为10000；
127.0.0.1:6379&gt; bf.reserve bf0.0000001-4 0.0000001 10000
OK

# 查看key为“bf0.1-2”的布隆过滤器信息，hashes表示内部使用的hash函数数量；
127.0.0.1:6379&gt; bf.debug bf0.1-2
1) "size:0"
2) "bytes:78 bits:624 hashes:5 hashwidth:64 capacity:100 size:0 ratio:0.05"

127.0.0.1:6379&gt; bf.debug bf0.1-3
1) "size:0"
2) "bytes:780 bits:6240 hashes:5 hashwidth:64 capacity:1000 size:0 ratio:0.05"

127.0.0.1:6379&gt; bf.debug bf0.01-4
1) "size:0"
2) "bytes:13785 bits:110280 hashes:8 hashwidth:64 capacity:10000 size:0 ratio:0.005"

127.0.0.1:6379&gt; bf.debug bf0.001-5
1) "size:0"
2) "bytes:197754 bits:1582032 hashes:11 hashwidth:64 capacity:100000 size:0 ratio:0.0005"
# 197754 bytes = 197754/1024/1024 ≈ 0.19 M。 

127.0.0.1:6379&gt; bf.debug bf0.0001-5
1) "size:0"
2) "bytes:257661 bits:2061288 hashes:15 hashwidth:64 capacity:100000 size:0 ratio:5e-05"

127.0.0.1:6379&gt; bf.debug bf0.00001-5
1) "size:0"
2) "bytes:317567 bits:2540536 hashes:18 hashwidth:64 capacity:100000 size:0 ratio:5e-06"

127.0.0.1:6379&gt; bf.debug bf0.000001-5
1) "size:0"
2) "bytes:377474 bits:3019792 hashes:21 hashwidth:64 capacity:100000 size:0 ratio:5e-07"

127.0.0.1:6379&gt; bf.debug bf0.000001-4
1) "size:0"
2) "bytes:37748 bits:301984 hashes:21 hashwidth:64 capacity:10000 size:0 ratio:5e-07"

127.0.0.1:6379&gt; bf.debug bf0.0000001-4
1) "size:0"
2) "bytes:43738 bits:349904 hashes:25 hashwidth:64 capacity:10000 size:0 ratio:5e-08"

由上面的执行结果可以看出，Redis布隆过滤器中最佳hash函数数量与错误率的关系如下：

错误率{error_rate}	hash函数的最佳数量
0.1	5
0.01	8
0.001	11
0.0001	15
0.00001	18
0.000001	21
0.0000001	25

3.3、所需存储空间与错误率及容量关系

通过创建不同错误率不同容量的布隆过滤器，整理存储空间与错误率及容量的关系。

127.0.0.1:6379&gt; bf.reserve bf0.0001-6 0.0001 1000000
OK
127.0.0.1:6379&gt; bf.reserve bf0.0001-7 0.0001 10000000
OK
127.0.0.1:6379&gt; bf.reserve bf0.0001-8 0.0001 100000000
OK

127.0.0.1:6379&gt; bf.debug bf0.0001-6
1) "size:0"
2) "bytes:2576602 bits:20612816 hashes:15 hashwidth:64 capacity:1000000 size:0 ratio:5e-05"

127.0.0.1:6379&gt; bf.debug bf0.0001-7
1) "size:0"
2) "bytes:25766015 bits:206128120 hashes:15 hashwidth:64 capacity:10000000 size:0 ratio:5e-05"

127.0.0.1:6379&gt; bf.debug bf0.0001-8
1) "size:0"
2) "bytes:257660148 bits:2061281184 hashes:15 hashwidth:64 capacity:100000000 size:0 ratio:5e-05"
# 257660148 bytes = 257660148/1024/1024 ≈ 245.7 M。

错误率{error_rate}	元素数量{capacity}	占用内存（单位M）
0.001	10万	0.19
0.001	1百万	1.89
0.001	1千万	18.9
0.001	1亿	188.6
0.0001	10万	0.25
0.0001	1百万	2.5
0.0001	1千万	24.6
0.0001	1亿	245.7
0.00001	10万	0.3
0.00001	1百万	3.01
0.00001	1千万	30.1
0.00001	1亿	302.9

占用内存（单位M） = bytes值/1024/1024。

从上述对比分析可以看出，错误率{error_rate}越小，所需的存储空间越大；初始化设置的元素数量{capacity}越大，所需的存储空间越大，当然如果实际远多于预设时，准确率就会降低。

在1千万数据场景下，error_rate为0.001、0.0001、0.00001实际占用内存都是30M以下，此时如果对准确性要求高，初始化时将错误率设置低一点是完全无伤大雅的。

RedisBloom官方默认的error_rate是 0.01，默认的capacity是 100，源码如下：

// RedisBloom/src/rebloom.c

static double BFDefaultErrorRate = 0.01;
static size_t BFDefaultInitCapacity = 100;

3.4、布隆过滤器如何扩容

先执行几行命令，看看实际效果。

# 公众号 @zxiaofan
# 创建一个容量为5的BloomFilter，其key为“bfexp”；
127.0.0.1:6379&gt; bf.reserve bfexp 0.1 5
OK

# 查看BloomFilter的内部信息，此时BloomFilter的层数为1
127.0.0.1:6379&gt; bf.debug bfexp
1) "size:0"
2) "bytes:4 bits:32 hashes:5 hashwidth:64 capacity:5 size:0 ratio:0.05"

127.0.0.1:6379&gt; bf.madd bfexp 1 2 3 4 5
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 1
5) (integer) 1
127.0.0.1:6379&gt; bf.debug bfexp
1) "size:5"
2) "bytes:4 bits:32 hashes:5 hashwidth:64 capacity:5 size:5 ratio:0.05"

127.0.0.1:6379&gt; bf.madd bfexp 11 12 13 14 15
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 0
5) (integer) 1

# 添加10个元素后，此时BloomFilter的层数变为2；
# BloomFilter的元素数量为2层过滤器之和（5+4=9），添加“14”时实际因为hash冲突没添加成功；
127.0.0.1:6379&gt; bf.debug bfexp
1) "size:9"
2) "bytes:4 bits:32 hashes:5 hashwidth:64 capacity:5 size:5 ratio:0.05"
3) "bytes:10 bits:80 hashes:6 hashwidth:64 capacity:10 size:4 ratio:0.025"

127.0.0.1:6379&gt; bf.madd bfexp 21 22 23
1) (integer) 1
2) (integer) 1
3) (integer) 1
127.0.0.1:6379&gt; bf.debug bfexp
1) "size:12"
2) "bytes:4 bits:32 hashes:5 hashwidth:64 capacity:5 size:5 ratio:0.05"
3) "bytes:10 bits:80 hashes:6 hashwidth:64 capacity:10 size:7 ratio:0.025"
127.0.0.1:6379&gt; bf.madd bfexp  24 25
1) (integer) 1
2) (integer) 1

# 添加14个元素后，还未达到BloomFilter扩容阈值，层数依旧为2；
127.0.0.1:6379&gt; bf.debug bfexp
1) "size:14"
2) "bytes:4 bits:32 hashes:5 hashwidth:64 capacity:5 size:5 ratio:0.05"
3) "bytes:10 bits:80 hashes:6 hashwidth:64 capacity:10 size:9 ratio:0.025"

127.0.0.1:6379&gt; bf.madd bfexp 31 32 33 34 35
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 1
5) (integer) 1

# 添加20个元素后，此时BloomFilter的层数变为3；
127.0.0.1:6379&gt; bf.debug bfexp
1) "size:19"
2) "bytes:4 bits:32 hashes:5 hashwidth:64 capacity:5 size:5 ratio:0.05"
3) "bytes:10 bits:80 hashes:6 hashwidth:64 capacity:10 size:10 ratio:0.025"
4) "bytes:23 bits:184 hashes:7 hashwidth:64 capacity:20 size:4 ratio:0.0125"

BloomFilter扩容逻辑：

插入m个元素，计算实际插入BloomFilter的元素数量；
如果实际插入元素数量 > BloomFilter的容量，则触发扩容；
扩容的倍数为BloomFilter初始化时设置的expansion（默认2）；

BloomFilter扩容注意事项：

扩容触发的条件是实际插入 > 容量，实际插入数量 = 容量时，是不会触发扩容的；
实际插入指的是插入成功，即使计划插入的数据过滤器中没有，但由于hash冲突导入插入失败，这种也不算实际插入成功。假设容量是20，如果插入21个元素，但由于重复甚至于hash冲突，导致实际插入的数量不足21个，此时也不会触发扩容；

4、布隆过滤器有哪些应用场景

4.1、邮件黑名单&网站黑名单

邮箱地址数十亿计且长度不固定，我们需要从海量的邮箱地址中识别出垃圾邮箱地址。当一个邮箱地址被判定为垃圾邮箱后，就将此地址添加进布隆过滤器中即可。

同理，万维网上的URL地址中包含了大量的非法或恶意URL，利用布隆过滤器也可以快速判断此类URL。当布隆过滤器返回结果为存在时，才对URL进行进一步判定处理。

4.2、新闻推荐去重

对于百度新闻、头条新闻等信息推荐平台，为了尽可能提升用户体验，应最大可能保证推荐给用户的新闻不重复，将已推荐给用户的文章ID存入布隆过滤器，再次推荐时先判断是否已推送即可。

4.3、缓存穿透&恶意攻击

缓存穿透：是指查询了缓存和数据库中都没有的数据。当此类查询请求量过大时（比如系统被恶意攻击），缓存系统或数据库的压力将增大，极容易宕机。

方式1：当查询DB中发现某数据不存在时，则将此数据ID存入布隆过滤器，每次查询时先判断是否存在于布隆过滤器，存在则说明数据库无此数据，无需继续查询了。当然此种方式仅能处理同一个ID重复访问的场景。

方式2：如果攻击者恶意构造了大量不重复的且数据库中不存在的数据呢，此时可将数据库中已有的数据的唯一ID放入布隆过滤器，每次查询时先判断是否存在于布隆过滤器，存在才调用后端系统查询，则可有效过滤恶意攻击。

使用方式1需要防止指定ID最初不存在于DB中，遂将此ID存入“数据不存在的过滤器”中，但后续DB又新增了此ID，因为布隆过滤器不支持删除操作，一旦发生此类场景，就肯定会出现误判了。

使用方式2需要注意数据的增量，避免数据库中新增了数据而过滤器中还没有导致无法查询到数据。当然如果此时DB中删除了指定数据，布隆过滤器是无法随之删除指纹标记的。

了解了原理方能如臂使指。此外建议，生产数据的ID应定义生成规则及校验规则（比如身份证的最后一位就是校验位），这样每次查询先判断这个ID是否有效，有效才进行后续的步骤，这样可以充分过滤外部的恶意攻击。

4.4、网页爬虫URL去重

网络爬虫是一个自动提取网页的程序，它为搜索引擎从万维网上下载网页，是搜索引擎的重要组成。传统爬虫从一个或若干初始网页的URL开始，获得初始网页上的URL，在抓取网页的过程中，不断从当前页面上抽取新的URL放入队列,直到满足系统的一定停止条件。由于网站之间存在互相引用，抓取的URL可能存在重复，为了避免爬取重复的数据，可以将已爬取的URL放入布隆过滤器中，每次爬取新URL时先做判断。

4.5、查询加速

Google BigTable、Apache HBase、Apache Cassandra、Postgresql 等Key-Value存储系统，使用布隆过滤器确定数据是否存在，从而减少代价相对较高的磁盘查询。

在HBase中，一个HFile一旦被写完就只会被查询不会被更新。将文件的所有key进行计算，生成这个文件的布隆过滤器，并将其写入到元数据中，以后所有对该文件的查询都会先查询对应的布隆过滤器，如果在布隆过滤器中不存在则不需要访问该文件，节省了大量的对磁盘的低速访问。

Cassandra原理类似，采用了追加而不是修改的方式来处理数据文件。一块完整的数据被dump到文件后就不会再被更新。在每个文件被dump到硬盘上时，都会对该文件生成一个布隆过滤器，而该布隆过滤器会被存放到内存中。所有对该文件的访问都会先访问对应的布隆过滤器，如果布隆过滤器返回不存在则无需访问硬盘上的文件。从而大大提高了查询的效率。

4.6、防止重复请求

第一次请求，将请求参数放入布隆过滤器中，第二次请求时，先判断请求参数是否存在于BloomFilter中。

4.7、区块链应用

区块链中使用布隆过滤器来加快钱包同步；以太坊使用布隆过滤器用于快速查询以太坊区块链的日志。

比特币钱包如何知道有多少钱（比特币钱包如何知道有多少UTXO），比特币系统没有余额的概念，它使用的是UTXO模型（Unspent Transaction Outputs，未使用过的交易输出）。比特币每一笔交易记录了时间、发送人、接收人和金额。那如果要计算A的余额，那么就要遍历所有跟A有关的交易，减去A发送的每一笔金额，并加上A接收的每一笔金额。

轻客户端下载完整的区块链账本自己查询，这显然是不现实的，如果轻客户端告诉全节点自己的钱包地址，则又泄漏了隐私。现有的实现方式是，钱包节点以布隆过滤器的方式告诉全节点自己的钱包地址，全节点返回可能相关的UTXO。

以太坊记录交易日志也采用了布隆过滤器，以太坊的每个区块头包含当前区块中所有收据的日志的布隆过滤器logsBloom，便于高效查询日志数据。

数学改变生活。

5、布隆过滤器的优缺点

5.1、布隆过滤器的优势

【适合大数据场景】：支持海量数据场景下高效判断元素是否存在；
【节省空间】：不存储数据本身，仅存储hash结果取模运算后的位标记；
【数据保密】：不存储数据本身，适合某些保密场景；

5.2、布隆过滤器的缺点

【误判】：由于存在hash碰撞，匹配结果如果是“存在于过滤器中”，实际不一定存在；
【不可删除】：没有存储元素本身，所以只能添加但不可删除；
【空间利用率不高】：创建过滤器时需提前预估创建，当错误率越低时，为了尽可能避免hash碰撞，冗余的空间就越多；需要注意的是，空间利用率不高和节省空间并不冲突；
【容量满时误报率增加】当容量快满时，hash碰撞的概率变大，插入、查询的错误率也就随之增加了。

5.3、布隆过滤器其他问题

【不支持计数】：同一个元素可以多次插入，但效果和插入一次相同；
【查询速度受错误率影响】：由于错误率影响hash函数的数量，当hash函数越多，每次插入、查询需做的hash操作就越多；

6、延伸拓展

6.1、超大规模布隆过滤器如何处理

除自建Redis外，阿里云-云数据库Redis是又一不错的选择，即买即用。但需要注意的是，阿里云的社区版主从版Redis单机支持10W QPS，如果数据量过大，需要迁移到集群版；4096GB集群性能增强版最大支持6KW QPS。

面对超大规模数据，除了使用更大规格的集群版Redis，我们是否还有其他解决方式呢？结合前人的优秀思路（Oracle大型机转为分布式MySQL集群），拆分key也一个不错的思路，即让key均匀分散到不同的小集群中。

回到我们的问题，如果我们需要校验的数据量超大，比如搜索引擎的爬虫需要判重URL，使用一个布隆过滤器性能肯定受影响。那么我们可以取Hash(URL)的前几位作为不同布隆过滤器的标记，此时URL就将均匀的分布到不同的布隆过滤器中。

【玩转Redis系列文章近期精选 @zxiaofan】
《玩转Redis-HyperLogLog原理探索》

《玩转Redis-HyperLogLog统计微博日活月活》

《玩转Redis-京东签到领京豆如何实现》

《玩转Redis-老板带你深入理解分布式锁》

《玩转Redis-如何高效访问Redis中的海量数据》

>祝君好运！
Life is all about choices！
将来的你一定会感激现在拼命的自己！
【CSDN】【GitHub】【OSCHINA】【掘金】【语雀】【微信公众号】

微信关注我们

原文链接：https://my.oschina.net/zxiaofan/blog/4618142

转载内容版权归作者及来源网站所有！

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

栈：如何实现有效括号的判断？

点击上方蓝字，关注：无量测试之道作者 |无量测试之道编辑 |小晴有效括号，刷过LeetCode的也许对这道题很熟悉。 1.开篇问题：有效的括号[1] 假如现在要你来解这道题，你会想到怎样的解法了？这就要用到我们今天要讲的“栈”这种数据结构。带着这个问题，我们来学习今天的内容。 2.如何理解“栈”？关于栈，有一个非常贴切的游戏--汉诺塔。玩这个游戏的时候，我们都是从下往上一个一个放；取的时候，我们也是从上往下一个一个地依次取，不能从中间任意抽出。后进者先出，先进者后出，这就是典型的“栈”结构。从栈的操作特性上来看，栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。栈的定义[2]：栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。 3.如何实现栈从刚才栈的定义里，我们可以看出，栈主要包含两个操作，入...

2020-09-21

517

前几天和丙弟交流，他说我们写作的人都是在不停地燃烧自己，所以需要不停地补充燃料。对于他的观点，我不能再苟同了——所以我开始狂补计算机方面的基础知识，这其中就包括我相对薄弱的数据结构。百度百科对数据结构的定义是：相互之间存在一种或多种特定关系的数据元素的集合。定义很抽象，需要大声地朗读几遍，才有点感觉。怎么让这种感觉来得更强烈，更亲切一些呢？我来列举一下常见的 8 种数据结构，数组、链表、栈、队列、树、堆、图、哈希表。这 8 种数据结构有什么区别呢？ ①、数组优点：按照索引查询元素的速度很快；按照索引遍历数组也很方便。缺点：数组的大小在创建后就确定了，无法扩容；数组只能存储一种类型的数据；添加、删除元素的操作很耗时间，因为要移动其他元素。 ②、链表《算法（第 4 版）》一书中是这样定义链表的：链表是一种递归的数据结构，它或者为空（null），或者是指向一个结点（node）的引用，该节点还有一个元素和一个指向另一条链表的引用。 Java 的 LinkedList 类可以很形象地通过代码的形式来表示一个链表的结构： publicclassLinkedList<E&...

2020-09-18

476

资源下载

更多资源

优质分享App

近一个月的开发和优化，本站点的第一个app全新上线。该app采用极致压缩，本体才4.36MB。系统里面做了大量数据访问、缓存优化。方便用户在手机上查看文章。后续会推出HarmonyOS的适配版本。

Mario

马里奥是站在游戏界顶峰的超人气多面角色。马里奥靠吃蘑菇成长，特征是大鼻子、头戴帽子、身穿背带裤，还留着胡子。与他的双胞胎兄弟路易基一起，长年担任任天堂的招牌角色。

Spring

Spring框架（Spring Framework）是由Rod Johnson于2002年提出的开源Java企业级应用框架，旨在通过使用JavaBean替代传统EJB实现方式降低企业级编程开发的复杂性。该框架基于简单性、可测试性和松耦合性设计理念，提供核心容器、应用上下文、数据访问集成等模块，支持整合Hibernate、Struts等第三方框架，其适用范围不仅限于服务器端开发，绝大多数Java应用均可从中受益。

Rocky Linux

Rocky Linux（中文名：洛基）是由Gregory Kurtzer于2020年12月发起的企业级Linux发行版，作为CentOS稳定版停止维护后与RHEL（Red Hat Enterprise Linux）完全兼容的开源替代方案，由社区拥有并管理，支持x86_64、aarch64等架构。其通过重新编译RHEL源代码提供长期稳定性，采用模块化包装和SELinux安全架构，默认包含GNOME桌面环境及XFS文件系统，支持十年生命周期更新。