Redis 8 发布了——它是开源的
了解更多
点击此处下载概率模块，该模块支持可扩展布隆过滤器和布谷鸟过滤器。
布隆过滤器是伯顿·霍华德在 1970 年提出的一种概率型数据结构，它提供了一种高效的方式来验证一个条目是否肯定不在集合中。这使得它在尝试搜索访问成本高昂的资源（例如通过网络或磁盘）上的项目时特别理想：如果我有一个大型的磁盘数据库，并且想知道键 foo 是否存在其中，我可以首先查询布隆过滤器，它会确定地告诉我它是否可能存在（然后可以继续进行磁盘查找），或者它是否不存在，在这种情况下，我就可以放弃昂贵的磁盘查找，直接向上层发送一个否定回复。
虽然可以使用其他数据结构（例如哈希表）来执行此操作，但布隆过滤器也非常有用，因为每个元素占用的空间非常小，通常以位为单位计算（而不是字节！）。会存在一定比例的误报（这是可控的），但对于初步测试键是否存在于集合中，它们提供了极佳的速度，最重要的是极佳的空间效率。
布隆过滤器广泛应用于各种场景，例如广告投放——确保用户不会太频繁地看到同一个广告；内容推荐系统——确保推荐内容不会太频繁出现；数据库——在访问磁盘上的表之前快速检查条目是否存在，等等。
布隆过滤器的工作原理是：将一个项目通过一个快速哈希函数处理，并从该哈希值中抽取位，然后在位域的特定位置将它们从 0 设置为 1。要检查布隆过滤器中是否存在某个项目，会采样相同的位。许多项目可能具有重叠的位，但由于关系哈希函数会产生唯一标识符，如果哈希中的一个位仍然是 0，那么我们就知道它之前没有被添加过。k 个哈希函数是此过程中的关键组成部分，它们决定了位数组中应为每个项目检查或设置的位置。
关于布隆过滤器的大多数文献都使用高度符号化和/或数学化的描述来解释它。如果你像我一样对数学感到苦手，你可能会发现我的解释更有用。
布隆过滤器是一个由许多位组成的数组。当一个元素被“添加”到布隆过滤器时，该元素会被哈希。然后将 bit[hashval % nbits] 设置为 1。这与哈希表中桶的映射方式非常相似，都利用了关系哈希函数。要检查项目是否存在，会计算哈希值，然后过滤器查看对应的位是否已设置。
当然，这会受到哈希冲突的影响。如果发生冲突，过滤器会返回误报——表示该条目确实找到了（注意，布隆过滤器永远不会返回误否定，也就是说，它不会声称某个事物不存在而实际上它存在）。
为了降低哈希冲突的风险，一个条目可以使用不止一位：该条目会被哈希 bits_per_element (bpe) 次，每次迭代使用不同的种子，从而产生不同的哈希值，并且对于每个哈希值，都会设置相应的 hash % nbits 位。要检查条目是否存在，候选键也会被哈希 bpe 次，如果任何相应的位是未设置的，则可以确定该项目不存在。
bpe 的实际值在创建过滤器时确定。一般来说，每个元素的位数越多，误报的可能性就越低。
在上面的示例中，所有三个位都需要被设置，过滤器才会返回肯定的结果。
影响布隆过滤器准确性的另一个值是其填充率，即过滤器中实际设置的位数。如果过滤器的大多数位都已设置，则任何特定查找返回否定的可能性会降低，从而过滤器返回误报的可能性会增加。
计数布隆过滤器和布谷鸟过滤器是传统布隆过滤器的进阶变体，提供附加功能。计数布隆过滤器允许通过维护一位被设置的次数来删除元素，而不仅仅是将其设置为 1。这在需要随时间添加和删除元素的动态数据集中特别有用。
另一方面，布谷鸟过滤器提供了一种比布隆过滤器更节省空间的替代方案，并允许删除项目而不会显著增加误报率。它们的工作原理是使用不同类型的哈希函数和桶系统，该系统可以重新定位项目以解决哈希冲突。
另一个近期发展是Ribbon 过滤器，它在提供快速查找时间的同时，设计得比布隆过滤器和布谷鸟过滤器都更节省空间。Ribbon 过滤器以新颖的方式使用一系列哈希函数来创建紧凑高效的数据结构。
通常，布隆过滤器在创建时必须预知将包含多少条目。bpe 的值需要固定，同样，位数组的宽度也是固定的。
与哈希表不同，布隆过滤器无法“重新平衡”，因为无法知道哪些条目是过滤器的一部分（过滤器只能确定给定条目是否不存在，但实际上不存储已存在的条目）。
为了让布隆过滤器能够“扩展”并容纳比其设计容量更多的元素，它们可以被堆叠起来。一旦一个布隆过滤器达到容量，就会在其上创建一个新的过滤器。通常，新的过滤器将比前一个具有更大的容量，以减少需要再次堆叠过滤器的可能性。
在可堆叠（可扩展）的布隆过滤器中，检查成员资格现在需要检查每一层是否存在。添加新项目现在需要预先检查它是否不存在，然后将其添加到当前过滤器中。然而，哈希值仍然只需要计算一次。
在创建布隆过滤器——即使是可扩展的——时，了解它预计包含多少项目非常重要。一个初始层只能包含少量元素的过滤器将显著降低性能，因为它需要更多的层才能达到更大的容量。
布隆过滤器的工作原理是：将一个项目通过一个快速哈希函数处理，并从该哈希值中抽取位，然后在位域的特定位置将它们从 0 设置为 1。要检查布隆过滤器中是否存在某个项目，会采样相同的位。许多项目可能具有重叠的位，但由于哈希函数会产生唯一标识符，如果哈希中的一个位仍然是 0，那么我们就知道它之前没有被添加过。
布隆过滤器，包括其变体如计数布隆过滤器、布谷鸟过滤器和 Ribbon 过滤器，多年来一直通过利用 GETBIT 和 SETBIT 在键上使用位域的客户端库与 Redis 一起使用。值得庆幸的是，自 Redis 4.0 以来， ReBloom 模块已可用，它消除了布隆过滤器的任何实现开销。
布隆过滤器的一个很好的用例是检查用户名是否已被使用。在小规模情况下这不是问题，但随着服务增长，这可能对数据库造成很大负担。使用 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
现在，让我们对布隆过滤器进行一些测试。
> BF.EXISTS usernames fred (integer) 1 > BF.EXISTS usernames fred_is_funny (integer) 0
正如预期， fred_is_funny 的结果是 0。响应为 0 意味着我们可以确定此用户名尚未使用。响应为 1 意味着它 可能 已被使用。我们无法确定，因为它可能是多个项目之间位重叠的情况。
一般来说，误报的几率较低，但非零。随着布隆过滤器“填满”，几率会增加。你可以使用 BF.RESERVE 命令调整错误率和大小。
在此视频中，开发者布道师 Guy Royse 将解释什么是布隆过滤器、它们如何工作以及如何在 Redis 中使用它们。
Redis 的功能是用高性能 C 语言编写的，能够暴露自己的命令和数据类型，并定义这些数据类型如何持久化。这使我们能够简单地创建一个非常强大的布隆过滤器模块，并轻松将其添加到 Redis 中。
获取并使用该模块非常简单
您应该首先下载并编译该模块
$ git clone git://github.com/RedisModules/rebloom $ cd rebloom $ make
现在您应该在 rebloom 目录中有一个 rebloom.so 文件。
构建过滤器模块后，使用 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 的修改版本，并进行了一些额外的增强
|
实现 |
添加 |
检查 |
|
redablooms |
20k/秒 |
7k/秒 |
|
lua |
29k/秒 |
25k/秒 |
|
bloomd |
250k/秒 |
200k/秒 |
|
rebloom |
400k/秒 |
440k/秒 |
完成后，我对其进行了基准测试，并与其他一些实现进行了比较。我最初编写这个过滤器是因为之前的过滤器实现太慢了。与产生 30k/秒 的 Lua 实现相比，redablooms 更慢，为 20k/秒。
使用 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 默认使用 10 万的初始容量和 1/10 万的错误率，即 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 秒内设置 100 万次，即 25 万操作/秒；6 秒内读取 100 万次，即 16.6 万操作/秒。
使用 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 的性能达到 37 万/秒，比 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 issue。
