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以获得精确的、尽管速度较慢的结果。
一个大小为100MB的过滤器可以容纳多达1亿个单独数据项,错误率为2%。
比特币还使用布隆过滤器优化客户端通信。
布隆过滤器是一种经过时间考验的惊人数据结构,可满足大多数需求,但它们并不完美,他们最大的缺点是无法删除项目,由于是一种数据存储在过滤器内的方式,一旦添加了项目,就无法将其与其他数据项完全分开,在不引入新的错误的前提下几乎无法删除。
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中提供)可以像布隆一样跟踪元素,但具有从集合中删除元素的附加功能。