Bloom Filter

23rd January 2021 at 11:44pm
Data Structure

Bloom Filter(布隆过滤器)是一种概率数据结构(probabilistic data structure)。它被用来判断一个元素是否存在一个集合中但它可能会有 false positive,即元素不存在、但仍然报存在。False positive 的概率可以调校得很小。应用时需要考虑场景能否容忍 false positives。

一些使用场景

  • 注册新用户时判断用户名是否已被占用(能容忍一定程度的误报)
  • Medium 在做推荐时,用它来判断用户是否看过文章
  • Chrome 用它来判断是否恶意 URL

它仅支持两个操作

  • insert(x):插入一个数据到 bloom filter 中
  • lookup(x):查找一个数据是否在 bloom filter 中,但是有一定概率报 false positive

原理

开一个长度为 n 的 bit vector。选几个 hash function。每当有新数据被添加进来时,将其 hash 值运算出来再对 n 取余。将 bit vector 中相应的 bit 置为 1。比如:

表示:

  • hash1("geeks") % 10 == 1
  • hash2("geeks") % 10 == 4
  • hash3("geeks") % 10 == 7

同样的,"nerd" 加进来后:

进行搜索时,也对搜索的 key 做如上相应的几次 hash 运算。比如查 "cats",如果得出的结果分别是 (3, 5, 7),bit vector 中这几个位置都是 1,因此 bloom filter 会认为 "cats" 存在,引起 false positive;如果得出的结果是 (3, 5, 6),由于 bit vector 中 6 的位置为 0,那么 "cats" 一定没有被加入进来过。

避免 false positive 的方法在于增大 bit vector 的位数。

因为可能存在不同的元素 hash 出来的三元组一致,因此 bloom filter 无法支持删除元素。

如何选择哈希函数

几个哈希函数间应该是 互相独立的,且哈希结果应该是 离散型均匀分布的(discrete uniform distribution)。而且它应该足够快,因此 密码学中的哈希算法并不是很合适(性能差一些)。

常用的有 murmur、fnv 及 HashMix 等。没有深入。

Scalable Bloom Filter

Redis 实现了 scalable bloom filter

Redis 在初始化 bloom filter 时可以指定容纳元素的 capacity 以及 expansion rate:

BF.RESERVE {key} {error_rate} {capacity} [EXPANSION {expansion}] [NONSCALING]

比如 capacity 设为 1000,EXPANSION 保持默认的 2,那么:

  1. 假设初始的 bit array 长度为 n(不可在命令中设置,暂时没有了解它的值是什么)
  2. 不停添加元素,当添加到 1000 个(capacity)时,
  3. Redis 自动扩容,会新建一个 2n 长(视 expansion)的 bit array;老的 bit array 仍然保留

由于 bloom filter 没有保留元素的初始值,因此扩容过程并没有类似 hash table 的 rehashing 过程。扩容之后会有多个 bit array,因此:

  • 新增元素时,只会插入最新的 bit array,避免老的 bit array 过于饱和而增加 false positive 的概率
  • 搜索元素时,会搜索全部的 bit array,如果有任一匹配,则返回存在

参考