布隆过滤器

BloomFilter是一种空间效率很高的随机数据结构,它利用位数组很简洁地表示一个集合,并能判断一个元素是否属于这个集合。BloomFilter的这种高效是有一定代价的:在判断一个元素是否属于某个集合时,有可能会把不属于这个集合的元素误认为属于这个集合(falsepositive)。因此,BloomFilter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下,BloomFilter通过极少的错误换取了存储空间的极大节省。

leveldb中利用布隆过滤器判断指定的key值是否存在于sstable中,若过滤器表示不存在,则该key一定不存在,由此加快了查找的效率。

结构

bloom过滤器底层是一个位数组,初始时每一位都是0

结构 - 图1

当插入值x后,分别利用k个哈希函数(图中为3)利用x的值进行散列,并将散列得到的值与bloom过滤器的容量进行取余,将取余结果所代表的那一位值置为1。

结构 - 图2

一次查找过程与一次插入过程类似,同样利用k个哈希函数对所需要查找的值进行散列,只有散列得到的每一个位的值均为1,才表示该值“有可能 ”真正存在;反之若有任意一位的值为0,则表示该值一定不存在。例如y1一定不存在;而y2可能存在。

结构 - 图3

数学结论

http://blog.csdn.net/jiaomeng/article/details/1495500 该文中从数学的角度阐述了布隆过滤器的原理,以及一系列的数学结论。

首先,与布隆过滤器准确率有关的参数有:

  • 哈希函数的个数k;
  • 布隆过滤器位数组的容量m;
  • 布隆过滤器插入的数据数量n;

主要的数学结论有:

  • 为了获得最优的准确率,当k = ln2 *(m/n)时,布隆过滤器获得最优的准确性;
  • 在哈希函数的个数取到最优时,要让错误率不超过є,m至少需要取到最小值的1.44倍;

实现

leveldb中的布隆过滤器实现较为简单,以goleveldb为例,有关的代码在filter/bloom.go中。定义如下,bloom过滤器只是一个int数字。

type bloomFilter int

创建一个布隆过滤器时,只需要指定为每个key分配的位数即可,如结论2所示,只要该值(m/n)大于1.44即可,一般可以取10。

func NewBloomFilter(bitsPerKey int) Filter {
    return bloomFilter(bitsPerKey)
}

创建一个generator, 这一步中需要指定哈希函数的个数k,可以看到k = f *ln2,而f = m/n,即数学结论1。

返回的generator中可以添加新的key信息,调用generate函数时,将所有的key构建成一个位数组写在指定的位置。

func (f bloomFilter) NewGenerator() FilterGenerator {
    // Round down to reduce probing cost a little bit.
    k := uint8(f * 69 / 100) // 0.69 =~ ln(2)
    if k < 1 {
        k = 1
    } else if k > 30 {
        k = 30
    }
    return &bloomFilterGenerator{
        n: int(f),
        k: k,
    }
}

generator主要有两个函数:

  • Add
  • GenerateAdd函数中,只是简单地将key的哈希散列值存储在一个整型数组中
func (g *bloomFilterGenerator) Add(key []byte) {
    // Use double-hashing to generate a sequence of hash values.
    // See analysis in [Kirsch,Mitzenmacher 2006].
    g.keyHashes = append(g.keyHashes, bloomHash(key))
}

Generate函数中,将之前一段时间内所有添加的key信息用来构建一个位数组,该位数组中包含了所有key的存在信息。

位数组的大小为用户指定的每个key所分配的位数 乘以 key的个数。位数组的最末尾用来存储k的大小。

func (g *bloomFilterGenerator) Generate(b Buffer) {
    // Compute bloom filter size (in both bits and bytes)
    // len(g.keyHashes) 可以理解为n, g.n可以理解为m/n
    // nBits可以理解为m
    nBits := uint32(len(g.keyHashes) * g.n)
    // For small n, we can see a very high false positive rate.  Fix it
    // by enforcing a minimum bloom filter length.
    if nBits < 64 {
        nBits = 64
    }
    nBytes := (nBits + 7) / 8
    nBits = nBytes * 8
 
    dest := b.Alloc(int(nBytes) + 1)
    dest[nBytes] = g.k
 
    for _, kh := range g.keyHashes {
        // Double Hashing
        delta := (kh >> 17) | (kh << 15) // Rotate right 17 bits
        for j := uint8(0); j < g.k; j++ {
            bitpos := kh % nBits
            dest[bitpos/8] |= (1 << (bitpos % 8))
            kh += delta
        }
    }
 
    g.keyHashes = g.keyHashes[:0]
}

Contain函数用来判断指定的key是否存在。

func (f bloomFilter) Contains(filter, key []byte) bool {
    nBytes := len(filter) - 1
    if nBytes < 1 {
        return false
    }
    nBits := uint32(nBytes * 8)
 
    // Use the encoded k so that we can read filters generated by
    // bloom filters created using different parameters.
    k := filter[nBytes]
    if k > 30 {
        // Reserved for potentially new encodings for short bloom filters.
        // Consider it a match.
        return true
    }
 
    kh := bloomHash(key)
    delta := (kh >> 17) | (kh << 15) // Rotate right 17 bits
    for j := uint8(0); j < k; j++ {
        bitpos := kh % nBits
        if (uint32(filter[bitpos/8]) & (1 << (bitpos % 8))) == 0 {
            return false
        }
        kh += delta
    }
    return true
}
下一节:Compaction是leveldb最为复杂的过程之一,同样也是leveldb的性能瓶颈之一。其本质是一种内部数据重合整合的机制,同样也是一种平衡读写速率的有效手段,因此在下文中,首先介绍下leveldb中设计compaction的原由,再来介绍下compaction的具体过程。