Bloom Filter和Cuckoo Filter对比解析

一、Bloom Filter

Bloom Filter(布隆过滤器)是1970年由布隆提出的,它由一个二进制向量数组和一系列随机映射函数组成。它可以用于检索一个元素是否一定在一个集合中或者可能存在一个集合中

1.1、实现原理

  • 初始化内存区域:在内存中开辟一块储存空间,并将里面的比特位全部初始化为0
  • 设置k个hash函数:初始化khash函数,用于元素的数据映射;
  • 比特位映射:通过khash函数,将元素映射到存储空间对应的比特位,并将对应的比特位设置为1

原理图

1.2、优缺点

  • 优点
    • 散列函数相互之间没有关系,方便由硬件并行实现;
    • 不需要存储元素本身,在某些对保密要求非常严格的场合有优势;
  • 缺点
    • 布隆过滤器存储空间和插入/查询时间都是O(k),导致查询性能较弱;
    • 误算率随着存入的元素数量增多而不断增加;
    • 由于不能确定某个元素是否一定存在,因此无法删除元素;
    • 空间利用效率低;

二、Cuckoo Filter

Cuckoo Filter(布谷鸟过滤器)使用一维数组存储元素的指纹信息(会存在误判率),同时使用两个 hash 函数获得指纹的位置id,在每个位置可以放置多个座位。这两个 hash 函数选择的比较特殊,因为过滤器中只能存储指纹信息。当这个位置上的指纹被挤兑之后,它需要计算出另一个对偶位置,下面会单独对这两个hash函数进行解析。

2.1、实现原理

  • 初始化内存:初始化一块内存给一维数组Buckets,其中每个Bucketn个位置可供使用,每个位置存储对应元素的指纹信息,即每个Bucket中可供存储n个元素的指纹信息;
  • Bucket映射:通过两个Hash函数得到两个对应的位置点(p1p2)信息,尝试将对应元素的指纹信息存入指定的Bucket中,如果p1对应的Bucket已经填充满了,则尝试填充到p2对应的Bucket中;
  • 元素指纹挤兑:当两个位置点(p1p2)对应的Bucket都已经填充满了就会触发填充挤兑,从p1p2对应的Bucket中随机选择一个进行挤兑操作,将Bucket中的已经存在的指纹信息踢除(被踢除的指纹信息会存储到它可存储的另一个Bucket中,如果另一个Bucket中也没有了位置,则又会触发挤兑操作,直到达到挤兑操作的上限),然后将该指纹信息存储到当前的Bucket中;

2.1.1、一维数组的特性

布谷鸟过滤器强制一维数组的长度必须是 2 的指数,所以对数组的长度取模等价于取 hash 值的最后 n 位。在进行异或运算时,忽略掉低 n 位 之外的其它位就行。将计算出来的位置 p 保留低 n 位就是最终的对偶位置。

2.1.2、两个hash函数的特性

因为布谷鸟过滤器中只存储指纹信息,当这个位置上的指纹被挤兑之后,它需要计算出另一个对偶位置,而计算这个对偶位置是需要元素本身的,但是布谷鸟过滤器巧妙的设计了一个独特的 hash函数,使得可以根据 p1元素指纹 直接计算出 p2,而不需要完整的 x 元素

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

原理图

2.2、优缺点

  • 优点
    • 查询性能较高;
    • 空间利用率较高;
    • 保证了一个比特只被一个元素映射,所以允许删除操作;
  • 缺点
    • 不能完美的支持删除,存在误删的情况;
    • 存储空间的大小必须为2的指数的限制让空间效率打了折扣;

2.3、场景分析

2.3.1、相同元素多次连续插入

假设每个Bucket的可供存储的座位为4,那么当相同的元素多次连续插入之后,Cuckoo Filter会对同一个元素进行了挤兑循环操作,导致同一个元素的指纹会占用两个位置上的所有的8个座位,导致空间利用率较低。

2.3.2、误删情况

由于存在不同元素被hash到同一个位置的情况,以及不同元素指纹相同的情况,所以会存在一定的误判率。

参考链接:https://juejin.im/post/5cfb9c74e51d455d6d5357db

Author: bugwz
Link: https://bugwz.com/2019/08/12/bloom-and-cuckoo-filter/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.