专栏首页码洞布隆过滤器过时了,未来属于布谷鸟过滤器?

布隆过滤器过时了,未来属于布谷鸟过滤器?

为了解决布隆过滤器不能删除元素的问题,布谷鸟过滤器横空出世。论文《Cuckoo Filter:Better Than Bloom》作者将布谷鸟过滤器和布隆过滤器进行了深入的对比。相比布谷鸟过滤器而言布隆过滤器有以下不足:查询性能弱、空间利用效率低、不支持反向操作(删除)以及不支持计数。

查询性能弱是因为布隆过滤器需要使用多个 hash 函数探测位图中多个不同的位点,这些位点在内存上跨度很大,会导致 CPU 缓存行命中率低。

空间效率低是因为在相同的误判率下,布谷鸟过滤器的空间利用率要明显高于布隆,空间上大概能节省 40% 多。不过布隆过滤器并没有要求位图的长度必须是 2 的指数,而布谷鸟过滤器必须有这个要求。从这一点出发,似乎布隆过滤器的空间伸缩性更强一些。

不支持反向删除操作这个问题着实是击中了布隆过滤器的软肋。在一个动态的系统里面元素总是不断的来也是不断的走。布隆过滤器就好比是印迹,来过来就会有痕迹,就算走了也无法清理干净。比如你的系统里本来只留下 1kw 个元素,但是整体上来过了上亿的流水元素,布隆过滤器很无奈,它会将这些流失的元素的印迹也会永远存放在那里。随着时间的流失,这个过滤器会越来越拥挤,直到有一天你发现它的误判率太高了,不得不进行重建。

布谷鸟过滤器在论文里声称自己解决了这个问题,它可以有效支持反向删除操作。而且将它作为一个重要的卖点,诱惑你们放弃布隆过滤器改用布谷鸟过滤器。

但是经过我一段时间的调查研究发现,布谷鸟过滤器并没有它声称的那么美好。它支持的反向删除操作非常鸡肋,以至于你根本没办法使用这个功能。在向读者具体说明这个问题之前,还是先给读者仔细讲解一下布谷鸟过滤器的原理。

布谷鸟哈希

布谷鸟过滤器源于布谷鸟哈希算法,布谷鸟哈希算法源于生活 —— 那个热爱「鸠占鹊巢」的布谷鸟。布谷鸟喜欢滥交(自由),从来不自己筑巢。它将自己的蛋产在别人的巢里,让别人来帮忙孵化。待小布谷鸟破壳而出之后,因为布谷鸟的体型相对较大,它又将养母的其它孩子(还是蛋)从巢里挤走 —— 从高空摔下夭折了。

最简单的布谷鸟哈希结构是一维数组结构,会有两个 hash 算法将新来的元素映射到数组的两个位置。如果两个位置中有一个位置为空,那么就可以将元素直接放进去。但是如果这两个位置都满了,它就不得不「鸠占鹊巢」,随机踢走一个,然后自己霸占了这个位置。

p1 = hash1(x) % l
p2 = hash2(x) % l

不同于布谷鸟的是,布谷鸟哈希算法会帮这些受害者(被挤走的蛋)寻找其它的窝。因为每一个元素都可以放在两个位置,只要任意一个有空位置,就可以塞进去。所以这个伤心的被挤走的蛋会看看自己的另一个位置有没有空,如果空了,自己挪过去也就皆大欢喜了。但是如果这个位置也被别人占了呢?好,那么它会再来一次「鸠占鹊巢」,将受害者的角色转嫁给别人。然后这个新的受害者还会重复这个过程直到所有的蛋都找到了自己的巢为止。

正如鲁迅的那句名言「占自己的巢,让别人滚蛋去吧!」

但是会遇到一个问题,那就是如果数组太拥挤了,连续踢来踢去几百次还没有停下来,这时候会严重影响插入效率。这时候布谷鸟哈希会设置一个阈值,当连续占巢行为超出了某个阈值,就认为这个数组已经几乎满了。这时候就需要对它进行扩容,重新放置所有元素。

还会有另一个问题,那就是可能会存在挤兑循环。比如两个不同的元素,hash 之后的两个位置正好相同,这时候它们一人一个位置没有问题。但是这时候来了第三个元素,它 hash 之后的位置也和它们一样,很明显,这时候会出现挤兑的循环。不过让三个不同的元素经过两次 hash 后位置还一样,这样的概率并不是很高,除非你的 hash 算法太挫了。

布谷鸟哈希算法对待这种挤兑循环的态度就是认为数组太拥挤了,需要扩容(实际上并不是这样)。

优化

上面的布谷鸟哈希算法的平均空间利用率并不高,大概只有 50%。到了这个百分比,就会很快出现连续挤兑次数超出阈值。这样的哈希算法价值并不明显,所以需要对它进行改良。

改良的方案之一是增加 hash 函数,让每个元素不止有两个巢,而是三个巢、四个巢。这样可以大大降低碰撞的概率,将空间利用率提高到 95%左右。

另一个改良方案是在数组的每个位置上挂上多个座位,这样即使两个元素被 hash 在了同一个位置,也不必立即「鸠占鹊巢」,因为这里有多个座位,你可以随意坐一个。除非这多个座位都被占了,才需要进行挤兑。很明显这也会显著降低挤兑次数。这种方案的空间利用率只有 85%左右,但是查询效率会很高,同一个位置上的多个座位在内存空间上是连续的,可以有效利用 CPU 高速缓存。

所以更加高效的方案是将上面的两个改良方案融合起来,比如使用 4 个 hash 函数,每个位置上放 2 个座位。这样既可以得到时间效率,又可以得到空间效率。这样的组合甚至可以将空间利用率提到高 99%,这是非常了不起的空间效率。

布谷鸟过滤器

布谷鸟过滤器和布谷鸟哈希结构一样,它也是一维数组,但是不同于布谷鸟哈希的是,布谷鸟哈希会存储整个元素,而布谷鸟过滤器中只会存储元素的指纹信息(几个bit,类似于布隆过滤器)。这里过滤器牺牲了数据的精确性换取了空间效率。正是因为存储的是元素的指纹信息,所以会存在误判率,这点和布隆过滤器如出一辙。

首先布谷鸟过滤器还是只会选用两个 hash 函数,但是每个位置可以放置多个座位。这两个 hash 函数选择的比较特殊,因为过滤器中只能存储指纹信息。当这个位置上的指纹被挤兑之后,它需要计算出另一个对偶位置。而计算这个对偶位置是需要元素本身的,我们来回忆一下前面的哈希位置计算公式。

fp = fingerprint(x)
p1 = hash1(x) % l
p2 = hash2(x) % l

我们知道了 p1 和 x 的指纹,是没办法直接计算出 p2 的。

特殊的 hash 函数

布谷鸟过滤器巧妙的地方就在于设计了一个独特的 hash 函数,使得可以根据 p1 和 元素指纹 直接计算出 p2,而不需要完整的 x 元素。

fp = fingerprint(x)
p1 = hash(x)
p2 = p1 ^ hash(fp)  // 异或

从上面的公式中可以看出,当我们知道 fp 和 p1,就可以直接算出 p2。同样如果我们知道 p2 和 fp,也可以直接算出 p1 —— 对偶性。

p1 = p2 ^ hash(fp)

所以我们根本不需要知道当前的位置是 p1 还是 p2,只需要将当前的位置和 hash(fp) 进行异或计算就可以得到对偶位置。而且只需要确保 hash(fp) != 0 就可以确保 p1 != p2,如此就不会出现自己踢自己导致死循环的问题。

也许你会问为什么这里的 hash 函数不需要对数组的长度取模呢?实际上是需要的,但是布谷鸟过滤器强制数组的长度必须是 2 的指数,所以对数组的长度取模等价于取 hash 值的最后 n 位。在进行异或运算时,忽略掉低 n 位 之外的其它位就行。将计算出来的位置 p 保留低 n 位就是最终的对偶位置。

// l = power(2, 8)
p_ = p & 0xff

数据结构

简单起见,我们假定指纹占用一个字节,每个位置有 4 个 座位。

type bucket [4]byte  // 一个桶,4个座位
type cuckoo_filter struct {
  buckets [size]bucket // 一维数组
  nums int  // 容纳的元素的个数
  kick_max  // 最大挤兑次数
}

插入算法

插入需要考虑到最坏的情况,那就是挤兑循环。所以需要设置一个最大的挤兑上限

def insert(x):
  fp = fingerprint(x)
  p1 = hash(x)
  p2 = p1 ^ hash(fp)
  // 尝试加入第一个位置
  if !buckets[p1].full():
    buckets[p1].add(fp)
    nums++
    return true
  // 尝试加入第二个位置
  if !buckets[p2].full():
    buckets[p2].add(fp)
    nums++
    return true
  // 随机挤兑一个位置
  p = rand(p1, p2)
  c = 0
  while c < kick_max:
    // 挤兑
    old_fp = buckets[p].replace_with(fp)
    fp = old_fp
    // 计算对偶位置
    p = p ^ hash(fp)
    // 尝试加入对偶位置
    if !buckets[p].full():
      buckets[p].add(fp)
      nums++
      return true
    c++
  return false

查找算法

查找非常简单,在两个 hash 位置的桶里找一找有没有自己的指纹就 ok 了。

def contains(x):
  fp = fingerprint(x)
  p1 = hash(x)
  p2 = p1 ^ hash(fp)
  return buckets[p1].contains(fp) || buckets[p2].contains(fp)

删除算法

删除算法和查找算法差不多,也很简单,在两个桶里把自己的指纹抹去就 ok 了。

def delete(x):
  fp = fingerprint(x)
  p1 = hash(x)
  p2 = p1 ^ hash(fp)
  ok = buckets[p1].delete(fp) || buckets[p2].delete(fp)
  if ok:
    nums--
  return ok

一个明显的弱点

so far so good!布谷鸟过滤器看起来很完美啊!删除功能和获取元素个数的功能都具备,比布隆过滤器强大多了,而且似乎逻辑也非常简单,上面寥寥数行代码就完事了。如果插入操作返回了 false,那就意味着需要扩容了,这也非常显而易见。

but! 考虑一下,如果布谷鸟过滤器对同一个元素进行多次连续的插入会怎样?

根据上面的逻辑,毫无疑问,这个元素的指纹会霸占两个位置上的所有座位 —— 8个座位。这 8 个座位上的值都是一样的,都是这个元素的指纹。如果继续插入,则会立即出现挤兑循环。从 p1 槽挤向 p2 槽,又从 p2 槽挤向 p1 槽。

也许你会想到,能不能在插入之前做一次检查,询问一下过滤器中是否已经存在这个元素了?这样确实可以解决问题,插入同样的元素也不会出现挤兑循环了。但是删除的时候会出现高概率的误删。因为不同的元素被 hash 到同一个位置的可能性还是很大的,而且指纹只有一个字节,256 种可能,同一个位置出现相同的指纹可能性也很大。如果两个元素的 hash 位置相同,指纹相同,那么这个插入检查会认为它们是相等的。

插入 x,检查时会认为包含 y。因为这个检查机制会导致只会存储一份指纹(x 的指纹)。那么删除 y 也等价于删除 x。这就会导致较高的误判率。

论文没有欺骗我们,它也提到了这个问题。(读者不必理解后半句)

图片

这句话明确告诉我们如果想要让布谷鸟过滤器支持删除操作,那么就必须不能允许插入操作多次插入同一个元素,确保每一个元素不会被插入多次(kb+1)。这里的 k 是指 hash 函数的个数 2,b 是指单个位置上的座位数,这里我们是 4。

在现实世界的应用中,确保一个元素不被插入指定的次数那几乎是不可能做到的。如果你觉得可以做到,请思考一下要如何做!你是不是还得维护一个外部的字典来记录每个元素的插入次数呢?这个外部字典的存储空间怎么办?

因为不能完美的支持删除操作,所以也就无法较为准确地估计内部的元素数量。

证明

下面我们使用开源的布谷鸟过滤器库来证明一下上面的推论

go get github.com/seiflotfy/cuckoofilter

这个布谷鸟过滤器对每个元素存储的指纹信息为一个字节,同一个位置会有 4 个座位。我们尝试向里面插入 15 次同一个元素。

package main

import (
    "fmt"
    "github.com/seiflotfy/cuckoofilter"
)

func main() {
    cf := cuckoo.NewFilter(100000)
    for i := 0; i < 15; i++ {
        var ok = cf.Insert([]byte("geeky ogre"))
        fmt.Println(ok)
    }
}

-------
true
true
true
true
true
true
true
true
false
false
false
false
false
false
false

我们发现插入它最多只能插入 8 次同一个元素。后面每一次返回 false 都会经过上百次的挤兑循环直到触碰了最大挤兑次数。

如果两个位置的 8 个座位 都存储了同一个元素,那么空间浪费也是很严重的,空间效率直接被砍得只剩下 1/8,这样的空间效率根本无法与布隆过滤器抗衡了。

如果不支持删除操作,那么布谷鸟过滤器单纯从空间效率上来说还是有一定的可比性的。这确实比布隆过滤器做的要好一点,但是布谷鸟过滤器这必须的 2 的指数的空间需求又再次让空间效率打了个折扣。

补充:来自CuckooFilter4j 的特别说明

相关项目

布谷鸟过滤器论文:Cuckoo Filter: Practically Better Than Bloom

Redis 布谷鸟过滤器模块: https://github.com/kristoff-it/redis-cuckoofilter

最有影响力的布谷鸟过滤器 C 库:https://github.com/efficient/cuckoofilter

Java 版布谷鸟过滤器:https://github.com/efficient/cuckoofilter

本文分享自微信公众号 - 码洞(codehole),作者:佬钱

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-06-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Redis 之布隆过滤器与布谷鸟过滤器

    大家都知道,在计算机中,IO一直是一个瓶颈,很多框架以及技术甚至硬件都是为了降低IO操作而生,今天聊一聊过滤器,先说一个场景:

    孙玄@奈学教育
  • 由布隆过滤器和布谷鸟过滤器引发得感想

    用户5927264
  • 高级算法篇:布隆过滤器?非也,布谷鸟过滤器是也

    过滤器在数据科学中的应用十分广泛,包括数据库查询、数据快速检索,数据去重等等。过滤器的出现是为了解决在大量数据的环境下,能够更好更快的(节省计算资源或者存储资源...

    IT大咖说
  • 布隆过滤器

    之前读吴军《数学之美》的时候提到布隆过滤器,觉得蛮有意思的,所以总结一下。 在计算机中,判断一个元素是不是在一个集合中,通常是用hash来解决,这在数据量不大的...

    Leetcode名企之路
  • 布隆过滤器

    本质上布隆过滤器是一种数据结构,比较巧妙的概率型数据结构(probabilistic data structure),特点是高效地插入和查询,可以用来告诉你 “...

    兜兜毛毛
  • 布隆过滤器

      布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个...

    OPice
  • 布隆过滤器

    布隆过滤器 (Bloom Filter)是由Burton Howard Bloom于1970年提出,它是一种space efficient的概率型数据结构,用于...

    大学里的混子
  • 布隆过滤器

    前两天, 一个大学同学问我布隆过滤器, 我本想反手甩他一篇我写的文章, 尴尬的是我找了找发现没有写过....

    烟草的香味
  • 布隆过滤器

    布隆过滤器本质上是一种概率型的数据结构,用于检索一个元素是否在集合中,它将告诉你一个数据“一定不存在或可能存在。

    不作声
  • 布隆过滤器

    项目中的热点数据我们一般会放在 redis 中,在数据库前面加了一层缓存,减少数据库的访问,提升性能。但如果,请求的 key 在 redis 中并不存在,那请求...

    贪挽懒月
  • Redis布隆过滤器

    比如我们在使用新闻客户端看新闻时,它会给我们不停地推荐新的内容,它每次推荐时要去重,去掉那些已经看过的内容。问题来了,新闻客户端推荐系统如何实现推送去重的?

    程序员酷森
  • 2020-11-09:谈谈布隆过滤器和布谷鸟过滤器的相同点和不同点?

    查询性能:布隆过滤器查询性能弱,原因是使用了多个hash函数,内存跨度大,缓存行命中率低。布谷鸟过滤器访问内存次数低,效率相对高。

    福大大架构师每日一题
  • Guava的布隆过滤器

    程序世界的算法都要在时间,资源占用甚至正确率等多种因素间进行平衡。同样的问题,所属的量级或场景不同,所用算法也会不同,其中也会涉及很多的trade-off。

    程序员历小冰
  • Bloom Filter布隆过滤器

    Bloom Filter是1970年由Bloom提出的,最初广泛用于拼写检查和数据库系统中。近年来,随着计算机和互联网技术的发展,数据集的不断扩张使得 Bloo...

    海天一树
  • Redis布隆Bloom过滤器

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

    物流IT圈
  • Guava的布隆过滤器

     程序世界的算法都要在时间,资源占用甚至正确率等多种因素间进行平衡。同样的问题,所属的量级或场景不同,所用算法也会不同,其中也会涉及很多的trade-off。

    程序员历小冰
  • 布隆过滤器原理

    如图所示,当字符串存储要加入到布隆过滤器中时,该字符串首先由多个哈希函数生成不同的哈希值,然后在对应的位数组的下表的元素设置为 1(当位数组初始化时 ,所有位置...

    happyJared
  • 布隆过滤器之 Redis

    Redis v4.0 之后有了 Module(模块/插件) 功能,Redis Modules 让 Redis 可以使用外部模块扩展其功能,布隆过滤器就是其中的 ...

    happyJared
  • 布隆过滤器介绍

    我们知道检查一个元素是否在某一个集合中,使用HashSet是比较好的选择,因为在不发生Hash碰撞的情况下它的时间复杂度为常数级别,但是在数据量比较大的情况下,...

    夹胡碰

扫码关注云+社区

领取腾讯云代金券