乐趣区

关于算法:bloom-filter浅析基本概念概率分析源码分析

jiezi

基本概念

Bloom filter 是一个空间高效（space- efficient）概率算法，被用于测试一个元素是否存在于一个汇合中。
存在假阳性（false positive，示意理论是假但误辨为真的状况）匹配的可能，但不存在假阴性（false negatives）的可能。也就是说，一次查问返回的后果是 可能在汇合里 或者 相对不在汇合里 。
最罕用的操作是校验元素是否存在于汇合中，也能够增加元素，但不能够删除元素。
同时，越多元素被退出到汇合中，假阳性的概率就会越高。
Bloom filter 个别利用在内存无限的索引场景，在可容忍的低误判的状况下，以极低的存储代价，实现去除绝大部分不必要的查问的便当。

定义

一个空的 bloom filter 是一个有 m 位的位数组，同时也定义 k 个哈希函数，每一个哈希函数映射元素到位数组的其中一个位。

增加 ：设置每一个哈希函数映射到的位为 1。
查问 ：查问每一个哈希函数映射到的位是否都为 1。只有有任意一个位不为 1，则表明该元素相对不存在。如果都为 1，但也只能表明该元素可能存在（对于个别的 bloom filter 实现）。
删除：不反对。

补充：
要枚举所有在 bloom filter 中的元素是很艰难的（譬如，须要许多的硬盘读取）

假阳性比例过高时，能够从新生成一个过滤器（以使得过滤器的假阳性低于某一个规范），只是这是一种绝对十分少见的状况。

利用

  • Google Bigtable、Apache Hbase、Apache Cassandra、PostgreSQL 应用 bloom filter 来缩小在磁盘上对不存在的行或列的查找。防止代价昂扬的磁盘查问能够无效地进步数据库的查问性能。
  • Google Chrome 应用 bloom filter 来辨认无害 url。
  • Microsoft Bing 应用多层级的 bloom filter 来作为搜寻的索引（BitFunnel，github 上有对应的 repo）。
  • Bitcoin 曾应用 bloom filter 来减速同步数字钱包。
  • Medium 应用 bloom filter 以防止对同一用户反复举荐雷同的文章。
  • Ethereum 应用 bloom filter 在区块链上疾速搜寻 logs。

概率分析

假阳性的概率（probability of false positive）

一个重要的前提条件，哈希函数映射到数组的每一个不同地位的概率是相等的，即简略平均散列（simple uniform hashing）。

假如 m 为数组的位数，在对布隆过滤器插入一个元素时，某一位未被某一哈希函数（映射到）设置为 1 的概率是 $1 – \frac{1}{m}$。
因为数组长度为 m，任意某一位被任意某一哈希函数设置为 1 的概率是 $\frac{1}{m}$，那么未被设置为 1 即可得。

假如 k 为哈希函数的数量，每一个都是相互独立的（任意一个哈希的后果不依赖于任意其余的哈希后果），那么数组中的某一位未被散列函数设置为 1 的概率是 $(1 – \frac{1}{m})^k$。

依据微积分的常识，咱们晓得一个非凡的极限（也是自然对数 e 的定义）
$lim_{x \to -\infty}{(1 – \frac{1}{m})^k} = \frac{1}{e}$
又因为
$(1-\frac{1}{m})^k = ((1-\frac{1}{m})^m)^\frac{k}{m} \approx e^{-\frac{k}{m}}$
所以咱们能够失去，插入 n 个元素后，数组中任意某一位依然为 0 的概率为
$(1-\frac{1}{m})^{kn} \approx e^{-\frac{kn}{m}}$
未被置 1 的概率为
$1 – (1-\frac{1}{m})^{kn} \approx 1 – e^{-\frac{kn}{m}}$

当初，如果须要测验一个实际上元素不在汇合中，但 k 个哈希函数映射的地位却都置为了 1 的状况，也就是假阳性的状况的概率：
$(1 – [1-\frac{1}{m}]^{kn})^k \approx (1 – e^{-\frac{kn}{m}})^k$

另有一个分析方法能够不依赖独立性的假如，证得与后面的后果统一。

进一步推断可得，当数组的位数 m 减少时，假阳性的概率会升高；当插入元素的次数 n 减少时，假阳性的概率会减少。

源码剖析

以太坊源码中应用到的 bloom filter 的实现：github.com/steakknife/bloomfilter

计算假阳性概率，与数学分析的公式类似

$(1 – e^{-\frac{k(n + 0.5)}{m – 1}})^k$

func (f *Filter) FalsePosititveProbability() float64 {k := float64(f.K()) 
    n := float64(f.N()) 
    m := float64(f.M()) 
    return math.Pow(1.0-math.Exp(-k)*(n+0.5)/(m-1), k) 
}

依据数列位数 m 和 预计退出元素的最大数量 maxN 来预估最佳的映射函数个数 K

$K = ceil(\frac{m * \log_e 2}{maxN})$
ceil 即便取下界。

func OptimalK(m, maxN uint64) uint64 {return uint64(math.Ceil(float64(m) * math.Ln2 / float64(maxN))) 
}

依据预计退出元素的最大数量 maxN 和 可承受最大假阳性概率 p 来预估最佳的数列位数 m

$m = ceil(\frac{-maxN * log_2 p}{(log_e 2)^2})$

func OptimalM(maxN uint64, p float64) uint64 {return uint64(math.Ceil(-float64(maxN) * math.Log(p) / (math.Ln2 * math.Ln2))) 
}

bloom filter 内部结构

type Filter struct { 
    lock sync.RWMutex // 应用读写锁保障线程平安
    bits []uint64 // 数列，采纳位向量 bitvector 的形式存储
    keys []uint64 // 散列函数 keys，此处存储散列算法用到的随机数
    m    uint64 // 数列的位数
    n    uint64 // 曾经插入的元素数 
}

哈希函数

先取待哈希的值的 Sum64 值到 rawHash。
Filter.keys 是寄存着 n 个随机数。取每一个其中的数与 rawHash 进行异或 XOR 操作，失去的后果放到 hashes 的切片中。

func (f *Filter) hash(v hash.Hash64) []uint64 {rawHash := v.Sum64() 
    n := len(f.keys) 
    hashes := make([]uint64, n) 
    for i := 0; i < n; i++ {hashes[i] = rawHash ^ f.keys[i] 
    } 
    return hashes 
}

增加元素

0x3f（16 进制）= 0011 1111（二进制）= 63（十进制）
F.bits[i>>6] |= 1 << uint(i&0x3f) 位向量（bit vector）的 set 操作。
整个增加的流程即有 n 个随机数，进行异或失去 n 个两头值，而后再求余（一种散列映射的形式），依据位向量 set 到 filter 的数列里。

func (f *Filter) Add(v hash.Hash64) {f.lock.Lock()
    defer f.lock.Unlock() 

    for _, i := range f.hash(v) {// f.setBit(i)
        i %= f.m
        f.bits[i>>6] |= 1 << uint(i&0x3f)
    }

    f.n++ 
}

验证元素是否存在

相似，迭代「哈希，求余，位向量 test 操作」。

// false: f definitely does not contain value v 
// true:  f maybe contains value v 
func (f *Filter) Contains(v hash.Hash64) bool {f.lock.RLock() 
    defer f.lock.RUnlock() 
    r := uint64(1) 
    for _, i := range f.hash(v) {// r |= f.getBit(k) 
        i %= f.m
        
        // &=，若有 0，即示意元素存在的任意一位为 0，r 都会是 0
        r &= (f.bits[i>>6] >> uint(i&0x3f)) & 1
    } 
    
    return uint64ToBool(r) 
}
退出移动版