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

Redis大数据计数器HyperLogLog

NoSQL专题

大数据专题

 

猜你喜欢