实现

leveldb中的布隆过滤器实现较为简单，以goleveldb为例，有关的代码在filter/bloom.go中。

定义如下，bloom过滤器只是一个int数字。

  1. type bloomFilter int

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

  1. func NewBloomFilter(bitsPerKey int) Filter {
  2.     return bloomFilter(bitsPerKey)
  3. }

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

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

  1. func (f bloomFilter) NewGenerator() FilterGenerator {
  2.     // Round down to reduce probing cost a little bit.
  3.     k := uint8(f * 69 / 100) // 0.69 =~ ln(2)
  4.     if k < 1 {
  5.         k = 1
  6.     } else if k > 30 {
  7.         k = 30
  8.     }
  9.     return &bloomFilterGenerator{
  10.         n: int(f),
  11.         k: k,
  12.     }
  13. }

generator主要有两个函数：

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

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

位数组的大小为用户指定的每个key所分配的位数 乘以 key的个数。

位数组的最末尾用来存储k的大小。

  1. func (g *bloomFilterGenerator) Generate(b Buffer) {
  2.     // Compute bloom filter size (in both bits and bytes)
  3.     // len(g.keyHashes) 可以理解为n， g.n可以理解为m/n
  4.     // nBits可以理解为m
  5.     nBits := uint32(len(g.keyHashes) * g.n)
  6.     // For small n, we can see a very high false positive rate.  Fix it
  7.     // by enforcing a minimum bloom filter length.
  8.     if nBits < 64 {
  9.         nBits = 64
  10.     }
  11.     nBytes := (nBits + 7) / 8
  12.     nBits = nBytes * 8
  13.  
  14.     dest := b.Alloc(int(nBytes) + 1)
  15.     dest[nBytes] = g.k
  16.  
  17.     for _, kh := range g.keyHashes {
  18.         // Double Hashing
  19.         delta := (kh >> 17) | (kh << 15) // Rotate right 17 bits
  20.         for j := uint8(0); j < g.k; j++ {
  21.             bitpos := kh % nBits
  22.             dest[bitpos/8] |= (1 << (bitpos % 8))
  23.             kh += delta
  24.         }
  25.     }
  26.  
  27.     g.keyHashes = g.keyHashes[:0]
  28. }

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

  1. func (f bloomFilter) Contains(filter, key []byte) bool {
  2.     nBytes := len(filter) - 1
  3.     if nBytes < 1 {
  4.         return false
  5.     }
  6.     nBits := uint32(nBytes * 8)
  7.  
  8.     // Use the encoded k so that we can read filters generated by
  9.     // bloom filters created using different parameters.
  10.     k := filter[nBytes]
  11.     if k > 30 {
  12.         // Reserved for potentially new encodings for short bloom filters.
  13.         // Consider it a match.
  14.         return true
  15.     }
  16.  
  17.     kh := bloomHash(key)
  18.     delta := (kh >> 17) | (kh << 15) // Rotate right 17 bits
  19.     for j := uint8(0); j < k; j++ {
  20.         bitpos := kh % nBits
  21.         if (uint32(filter[bitpos/8]) & (1 << (bitpos % 8))) == 0 {
  22.             return false
  23.         }
  24.         kh += delta
  25.     }
  26.     return true
  27. }