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中提供）可以像布隆一样跟踪元素，但具有从集合中删除元素的附加功能。