Redis 的布隆过滤器数据类型

点击此处下载概率模块，它支持可扩展性布隆和库库过滤器。

什么是布隆过滤器？

布隆过滤器是一种概率数据结构，由 Burton Howard 于 1970 年构思，它提供了一种高效的方法来验证某个条目肯定不在一组内。当尝试在访问成本很高的资源（例如，网络或磁盘）上搜索条目时，这将特别理想：如果我有一个大的磁盘数据库，并且我想知道键foo是否存在于其中，我首先可以查询布隆过滤器，这会明确告知我它可能是否存在（然后可以继续磁盘查找），或者它是否不存在，在这种情况下，我可以放弃高成本的磁盘查找，只向上发送一个否定的回复。

虽然可以使用其他数据结构（例如，哈希表）来执行此操作，但布隆过滤器的特别之处还在于，它们为每个元素占用的空间非常小，通常以位数（非字节！）计算。将存在一定百分比的误报（这是可控的），但对于在集合中是否存在键的初始测试，它们提供了出色的速度，最重要的是出色的空间效率。

布隆过滤器在各种各样的应用程序中得到使用，例如广告服务——确保用户不会看到广告的频率太高；同样，在内容推荐系统中——确保推荐出现的频率不会太高，在数据库中——在磁盘上访问某个条目之前快速检查该条目是否存在于表中，等等。

布隆过滤器的工作原理

布隆过滤器的工作原理是，通过快速哈希函数来运行一个条目，然后从该哈希中采样位，并在位域中的特定时间间隔内将它们从 0 设置为 1。为了检查在布隆过滤器中的存在性，对同一组位进行采样。许多条目可能具有重叠的位，但是由于关系哈希函数会生成唯一的标识符，如果哈希中的某个位仍然为 0，所以我们知道它以前没有被添加。k 哈希函数是这一流程中的关键组成部分，它确定应该为每个条目检查或设置的位数组中的位置。

关于布隆过滤器的文献大多使用高度符号化和/或数学化的描述。如果您像我一样数学苦手，您可能会发现我的解释更有用。

布隆过滤器是一个由许多位组成的数组。当某个元素“添加到”布隆过滤器中时，对元素进行哈希处理。然后，将 bit[hashval % nbits] 设置为 1。这看起来与在哈希表中映射存储空间的方式十分类似，它利用的是关系哈希函数。要检查条目是否存在，计算哈希，然后过滤器会查看对应的位是否已设置。

当然，这可能会发生冲突。如果发生冲突，过滤器将返回一个假阳性——表示确实找到了该条目（请注意，布隆过滤器永远不会返回一个假阴性，也就是说，当某物实际上存在时，布隆过滤器不会声称该物不存在）。

为了降低出现冲突的风险，一个条目可以采用多个位：将该条目哈希 bits_per_element (bpe) 次，为每一次迭代使用不同的种子，产生不同的哈希值，并且对于每一个哈希值，设置对应的 hash % nbits 的位。为了检查某个条目是否存在，同样将候选键哈希 bpe 次，如果任何对应的位为 未设置，则可以明确确定该条目不存在。

bpe 的实际值是在创建过滤器时决定的。通常，每个元素的位越多，出现假阳性的可能性就越低。

在上面的示例中，所有三个位都需要被设置，过滤器才能返回一个正确的结果。

影响布隆过滤器准确性的另一个值是其填充率，或者实际已设置的过滤器中的位数。如果过滤器设置了绝大多数位，则任何特定查找返回错误的可能性均会降低，因此过滤器返回假阳性的可能性会增加。

布隆过滤器的进阶版本

计数布隆过滤器和布谷鸟过滤器是传统布隆过滤器的进阶版本，提供了额外的功能。计数布隆过滤器允许通过保留已设置位次数的计数来移除元素，而不是简单地将其设置为 1。这对于元素需要随着时间而被添加和删除的动态数据集特别有用。

另一方面，布谷鸟过滤器提供了比布隆过滤器更节省空间的替代方案，并允许删除项目而不显著增加假阳性率。它们的运作方式是使用不同类型的哈希函数和可以重新定位项目以解决哈希冲突的存储桶系统。

另一个近期进展是Ribbon 过滤器，这种过滤器被设计为比布隆过滤器和布谷鸟过滤器更节省空间，同时仍然提供了快速的查找时间。Ribbon 过滤器以一种新颖的方式使用一系列哈希函数来创建一个紧凑高效的数据结构。

可扩展布隆过滤器

通常，必须在预先了解布隆过滤器将包含多少个条目后才能创建布隆过滤器。bpe 数需要是固定的，同样，位数组的宽度也是固定的。
与哈希表不同，Bloom 过滤器无法“重新平衡”，因为无法知道哪些条目是过滤器的一部分（过滤器只能确定给定条目不存在，但实际上并不存储存在的条目）。

为了允许 Bloom 过滤器“扩展”并容纳比设计容量更多的元素，可以对其进行堆叠。一旦一个 Bloom 过滤器达到容量，则在其之上创建新的过滤器。通常，新过滤器将比前一个过滤器具有更大的容量，以减少需要堆叠其他过滤器的可能性。

在可堆叠（可扩展）Bloom 过滤器中，现在检查成员资格要检查每一层的存在。添加新项现在涉及事先检查其不存在，并将其添加到当前过滤器中。但哈希仍然只需计算一次。

在创建 Bloom 过滤器时，即使是可扩展的，重要的是对它预计要包含的项目数量有一个清楚的概念。一个初始层只能容纳少量元素的过滤器会显著降低性能，因为需要更多的层才能达到更大的容量。

概率过滤器最佳实践

Bloom 过滤器通过对项运行快速哈希函数以及从哈希中抽样位并将其从 0 设置为 1（按位字段中特定间隔）来工作。为了检查 Bloom 过滤器中的存在，将抽样相同的位。许多项可能具有重叠的位，但由于哈希函数产生唯一标识符，因此，如果哈希中的单个位仍然为 0，那么我们知道它以前从未被添加过。

Bloom 过滤器（包括其变体，如计数 Bloom 过滤器、布谷鸟过滤器和带状过滤器）多年来已通过客户端库与 Redis 一起使用，该库利用 GETBIT 和 SETBIT 来处理键处的位域。谢天谢地，自 Redis 4.0 以来，ReBloom 模块已可用，它消除了任何 Bloom 过滤器实现开销。

Bloom 过滤器的良好用例是检查已使用的用户名。在小规模上，这不是问题，但随着服务增长，这可能非常耗费数据库资源。使用 ReBloom 实现这一点非常简单。

首先，让我们添加一些用户名作为测试

> BF.ADD usernames funnyfred
(integer) 1
> BF.ADD usernames fredisfunny
(integer) 1
> BF.ADD usernames fred
(integer) 1
> BF.ADD usernames funfred
(integer) 1

现在，让我们针对 Bloom 过滤器运行一些测试。

> BF.EXISTS usernames fred
(integer) 1
> BF.EXISTS usernames fred_is_funny
(integer) 0

正如预期那样，fred_is_funny 得出 0。零的响应表示我们可以确定该用户名未被使用。1 的响应表示它可能已被使用。我们无法肯定地说，因为它可能是多个项之间重叠位的案例。

通常，假阳性的可能性很低，但并非为零。随着布隆过滤器“填满”，可能性会增加。你可以使用 BF.RESERVE 命令调整错误率和大小。

在此视频中，开发者支持人员 Guy Royse 将解释什么是布隆过滤器、其工作原理，以及如何在 Redis 中使用布隆过滤器。

布隆过滤器在 Redis 中的进一步使用

Redis 功能使用高性能 C 编写，能够公开其自己的命令和数据类型，并定义如何持久化这些数据类型。这使我们能够简单地创建一个非常强大的布隆过滤器模块，并且可以轻松将其添加到 Redis。

获取模块并使用它非常简单

下载并构建

你应首先下载并编译模块

 $ git clone git://github.com/RedisModules/rebloom
 $ cd rebloom
 $ make

你现在应该在 rebloom 目录中拥有一个 rebloom.so。

将 Rebloom 加载到 Redis 中

一旦你构建了过滤器模块，请使用 loadmodule 或 –loadmodule 将你的 redis.conf 或 redis 命令行指向该模块

redis.conf

loadmodule /path/to/rebloom.so

命令行

$ redis-server --loadmodule /path/to/rebloom.so

尝试使用

你可以使用 redis-cli 略微试用一下

 127.0.0.1:6379> BF.ADD bloom mark
 1) (integer) 1
 127.0.0.1:6379> BF.ADD bloom redis
 1) (integer) 1
 127.0.0.1:6379> BF.EXISTS bloom mark
 (integer) 1
 127.0.0.1:6379> BF.EXISTS bloom redis
 (integer) 1
 127.0.0.1:6379> BF.EXISTS bloom nonexist
 (integer) 0
 127.0.0.1:6379> BF.EXISTS bloom que?
 (integer) 0
 127.0.0.1:6379>
 127.0.0.1:6379> BF.MADD bloom elem1 elem2 elem3
 1) (integer) 1
 2) (integer) 1
 3) (integer) 1
 127.0.0.1:6379> BF.MEXISTS bloom elem1 elem2 elem3
 1) (integer) 1
 2) (integer) 1
 3) (integer) 1

你还可以创建一个自定义布隆过滤器。**BF.ADD** 命令创建一个适于较小数量的项目的新布隆过滤器。这会消耗较少的内存，但可能不太适用于大型过滤器

 127.0.0.1:6379> BF.RESERVE largebloom 0.0001 1000000
 OK
 127.0.0.1:6379> BF.ADD largebloom mark
 1) (integer) 1

基准、速度和实现

Rebloom 使用libloom 的修改版本，并进行了其他一些增强

我发现，在测试存在性时，即使检测到未设置的位，libbloom 也会继续针对每一位进行检查。使其仅在找到第一个未设置位时就立即返回，这样可以提高性能。
我从查找 API 中解耦了哈希计算 API。这意味着我只需要计算哈希，然后将其输入到过滤器代码中。
以下是性能基准的摘要。下表显示了一个初始容量为 10,000、错误率为 0.01 且缩放因子为 2 的单个布隆过滤器的基准。测试使用单个客户端线程进行，并使用管道尽量避免网络/调度干扰

实现	添加	检查
redablooms	20k/s	7k/s
lua	29k/s	25k/s
bloomd	250k/s	200k/s
rebloom	400k/s	440k/s

一旦将所有操作完成，我便对其进行了基准测试，并将其与其他一些实现进行了比较。我最初编写的这个过滤器是因为先前的过滤器实现太慢。与产生 30k/sec 的 Lua 实现相比，redablooms 较慢，为 20k/sec。

使用 rebloom 运行等效命令

 mnunberg@mbp15III ~/Source/rebloom $ redis-benchmark -e -r 100000000 -n 1000000 -c 20 bf.add test __rand_int__
 ====== bf.add test __rand_int__ ======
 1000000 requests completed in 8.92 seconds
 20 parallel clients
 3 bytes payload
 keep alive: 1

 99.99% <= 1 milliseconds
 100.00% <= 2 milliseconds
 100.00% <= 3 milliseconds
 100.00% <= 3 milliseconds
 112082.49 requests per second

通过流水线和更改线程数，有可能获得更好的数字，但公平的基准是一个苹果对苹果的比较。

我将 bloomd 自身基准与等效 Rebloom 命令集进行了比较。Bloomd 默认使用 100k 的初始容量和 1/10k 或 0.0001 的误差率。其基准程序简单地设置 1,000,000 个项目，然后读取它们。它在设置项目时使用即发即忘语义，因此在发送命令时网络延迟不会成为一个因素

 mnunberg@mbp15III ~/Source/bloomd $ ./bench
 Thread started.Using filter: foobar1464749818
 Connect: 0 msec
 Create: 1 msec
 Set: 4090 msec. Num: 999987
 Check: 6130 msec. Num: 1000000

因此，我们得到在 4 秒内有 1M 组，或 250K op/s，以及在 6 秒内有 1M 读取，或 166K op/sec.

与 Rebloom 等效

 mnunberg@mbp15III ~/Source/rebloom $ redis-cli del test; redis-cli bf.reserve test 0.0001 100000; redis-benchmark -e -r 1000000 -l -n 1000000 -P 100 -c 1 bf.add test __rand_int__
 (integer) 1
 OK
 ====== bf.add test __rand_int__ ======
 1000000 requests completed in 2.65 seconds
 1 parallel clients
 3 bytes payload
 keep alive: 1

 100.00% <= 0 milliseconds
 376931.75 requests per second

我让这个循环持续了一段时间，因为与使用顺序键的 bloomd 基准不同，redis-bench 使用随机 ID。这意味着发生冲突的可能性更大。

Rebloom 执行速度为 370k/s，比 bloomd 快约 50%。

用于读取

 mnunberg@mbp15III ~/Source/rebloom $ redis-benchmark -e -r 1000000 -n 1000000 -l -P 100 -c 1 bf.exists test __rand_int__
 ====== bf.exists test __rand_int__ ======
 1000000 requests completed in 2.65 seconds
 1 parallel clients
 3 bytes payload
 keep alive: 1

 99.99% <= 1 milliseconds
 100.00% <= 1 milliseconds 377073.91 requests per second

这比 bloomd 快约150%！

调试布隆过滤器

最后，我添加了 BF.DEBUG 命令，以准确查看如何使用过滤器

 127.0.0.1:6379> BF.DEBUG test
 1) "size:987949"
 2) "bytes:239627 bits:1917011 hashes:14 capacity:100000 size:100000 ratio:0.0001"
 3) "bytes:551388 bits:4411101 hashes:16 capacity:200000 size:200000 ratio:2.5e-05"
 4) "bytes:1319180 bits:10553436 hashes:19 capacity:400000 size:400000 ratio:3.125e-06"
 5) "bytes:3215438 bits:25723497 hashes:23 capacity:800000 size:287949 ratio:1.95313e-07"

这将输出元素总数作为第一个结果，然后为链中每个过滤器的详细信息输出一个列表。如您所见，每当添加新过滤器时，它的容量就会呈指数级增长，并且对错误的严格性也会增加。

请注意，此过滤器链还总共使用 5MB。这仍然比替代解决方案更节省空间，因为我们仍然每个元素约为 5 字节，最上层过滤器仅利用约 12%。如果初始容量更大，则可以节省更多空间并且查找会更快。

您可以在 https://github.com/RedisModules/rebloom 自己下载 Rebloom。如果您使用的是 Redis Enterprise，它将与版本 5.0 捆绑在一起。

如果您认为自己的速度可以更快，请告诉我，如果您遇到问题，请提交 github 问题。