Redis布隆Bloom过滤器

　　Redis提供了三种强大数据结构：HyperLogLog，布隆过滤器和布谷鸟过滤器。本文讨论布隆过滤器：

布隆过滤器是最具代表性的概率数据结构，可用于各种应用，数据库，网络设备甚至加密货币都广泛使用布隆过滤器来加速内部操作。

客户端可以向服务查询某个数据是否已经被缓存了，Redis以名为ReBloom的模块方式提供，此数据结构允许你测试某个数据项是否属于一个大型集合的一分子，但无需将整个集合保存在内存中。

值得注意的是，你可以指定0％到100％之间的误报概率（不包括极值），并避免误报，关于布隆过滤器最重要的一点是布隆过滤器总是回复“可能是”或“绝对没有”。

使用ReBloom时，空间使用与目标错误率成反比。

此外，ReBloom支持增长过滤器，让你为每个过滤器动态分配内存，这对于没有“一条裤子适合所有人”的解决方案的情况非常有用（例如跟踪社会网络中的关系，这遵循幂律分布），虽然过滤器会自动增长，但为了确保最佳的空间和CPU效率，当你已经知道集合近似大小时，尽可能准确地分配过滤器空间非常重要。

适用情况：

1. 检查用户名可用性 2. 欺诈检测和缓解某些类型的网络攻击 3. 跟踪已知URL的Web爬虫

基本用法

加载ReBloom模块后，添加数据项时，redis将为你无缝创建到key：

BF.ADD <key> <item>

如果要指定更多选项，可以使用：

BF.RESERVE <key> <error_rate> <size>

这将创建一个名为<key>的过滤器，该过滤器最多可容纳<size>项，目标错误率为<error_rate>。一旦溢出原始<size>估计值，过滤器将自动增长。

不会重复抓取网址

假设你正在运行网络抓取工具，并且希望确保它每次都不会无限制地抓取已经抓取过的网址。

当你抓取一个域名网站，保存所有已知URL的列表可能不是问题，但是，如果该范围大小在接近Google规模之间的某种程度，你可能会浪费太多资源来更新和阅读这个列表（甚至可能不再适合放入内存）。

使用布隆过滤器可以解决同样的问题，例如：

BF.ADD crawled "redis.io/documentation"

要测试URL是否已被抓取，你可以使用：

BF.EXISTS crawled "redis.io/maybe-new-url"

回答将是：

0（绝对没有）：这是一个新的URL，你可以抓取它; 要么 1（可能是）：这很可能是一个已知的URL。

在积极的情况下，由你决定是否接受跳过某些URL并继续前进的可能性很小，或者在磁盘中中跟踪这些URL，这样你可以查询这些URL以获得精确的、尽管速度较慢的结果。

Bloom过滤器需要多少空间？

一个大小为100MB的过滤器可以容纳多达1亿个单独数据项，错误率为2％。

比特币还使用布隆过滤器优化客户端通信。

布隆不够时：布谷鸟Cuckoo过滤器

布隆过滤器是一种经过时间考验的惊人数据结构，可满足大多数需求，但它们并不完美，他们最大的缺点是无法删除项目，由于是一种数据存储在过滤器内的方式，一旦添加了项目，就无法将其与其他数据项完全分开，在不引入新的错误的前提下几乎无法删除。

Cuckoo过滤器提供更新的概率数据结构，它以不同方式存储信息，导致性能特征略有不同，并且能够在需要时删除项目。

布谷鸟过滤器在下面情况比布隆过滤器更好：

1. 删除项目 2. 更快的查找（因为更好的内存位置） 3. 空间效率（当目标错误率低于3％时） 4. 更快的插入（当过滤器的填充率低于80％时）

在以下情况下，布谷鸟过滤器比布隆过滤器更糟糕：

1. 你的填充率超过80％;在这种情况下，布谷鸟过滤器的插入速度很快就会低于布隆。

2. 你有更宽松的目标错误率（大于3％），使布谷鸟过滤器的空间效率降低

3. 你需要高度可预测的行为（因为布谷鸟过滤器在插入过程中使用随机源来提供性能改进）

基本用法：

Cuckoo过滤器也存在于Redis的ReBloom中，可以像使用Bloom一样使用，唯一的区别是命令前缀是CF而不是BF，并且你有一个新的删除命令：

CF.DEL <key> <item>

其他所有内容都可以使用与布隆过滤器相同的方式建模。

结论 概率数据结构优雅地解决了许多类型的问题，否则，这些问题需要更多的计算能力、成本和开发工作，在本文中，我们介绍了三种有用的概率数据结构：

1. HyperLogLog（包含在Redis中）来计算集合中的元素。

2. 布隆过滤器（在ReBloom中可用），用于跟踪集合中存在或缺失的元素。

3. Cuckoo过滤器（ReBloom中提供）可以像布隆一样跟踪元素，但具有从集合中删除元素的附加功能。