Leveldb BloomFliter 解析

BloomFilter 原理

布隆過濾器由巴頓布隆于1970年提出，由一個很長的bit數組以及一系列hash函數組成。bloomfilter可以用于檢索一個元素是否出現在一個集合中，bloomfilter的優點是相比hash表擁有極大的空間效率，缺點是會出現一定的錯誤機率(False positive,一個不在集合中的元素被誤認為處于集合中）。

bloomfilter 的原理是，當一個元素在加入集合時，通過k個hash 函數映射到bit數組的k個位置，并将相應的位置置1。在查找一個元素是否存在于集合中時，使用相同的k個hash 函數檢視bit數組中的位置是否為全為1，如果出現一個0，則該key 一定不存在集合中，否則有可能出現在集合中。

優點

Bloomfilter 可以使用較少的空間存儲大量資料的全集，并且存儲的不是每個元素的原本的數值，隻是設定對應的bit位，一定程度上實作了加密的效果。除空間效率之外，bloomfilter的時間效率都是常數級别O(k),其中k 代表使用的hash 函數個數，由于k個hash 函數式互相獨立的性質，在進行k個hash 計算時可以并行計算進一步加速插入查找。

缺點

Bloomfilter 的缺點是會出現False positive 的誤判率，而且随着元素的增加，誤算率也随之增加。是以盡可能降低誤判率需要一些額外工作。

BloomFilter參數選擇

以下均參考wikipedia bloomfilter 中關于誤差率的計算章節。直接說結論，當k(hash 函數個數)，m(bit數組大小)，n(插入元素個數)滿足下式的時候，可以保證最低的誤差率。

k=mnln2 k = m n l n 2

下圖(摘自wikipedia) 表示在最優hash函數個數的情況下，不同m,n之間誤差率關系。

從上圖可以看到當存儲10億個元素時使用4GB的存儲空間可以保證不到1e-06的錯誤率。可以看到bloomfilter在實作高空間使用率的同時可以保證較低誤差率。

Leveldb 實作

leveldb bloomfilter 實作在util/bloom.cc

成員變量以及構造函數

class BloomFilterPolicy : public FilterPolicy {
 private:
  // 平均每個key擁有的bit 數目
  size_t bits_per_key_;
  // hash function 的個數
  size_t k_;

 public:
  explicit BloomFilterPolicy(int bits_per_key)
      : bits_per_key_(bits_per_key) {
    // We intentionally round down to reduce probing cost a little bit
    // 按照上面的公式設定hash函數的個數
    k_ = static_cast<size_t>(bits_per_key * );  // 0.69 =~ ln(2)
    if (k_ < ) k_ = ;
    if (k_ > ) k_ = ;
  }
 };
           

CreateFilter

将傳入的n個key 存儲到bloomfilter 中，bloomfilter結果使用string存儲。

virtual void CreateFilter(const Slice* keys, int n, std::string* dst) const {
    // Compute bloom filter size (in both bits and bytes)
    // bloomfilter 需要多少bit
    size_t bits = n * bits_per_key_;

    // For small n, we can see a very high false positive rate.  Fix it
    // by enforcing a minimum bloom filter length.
    if (bits < ) bits = ;
    // 對齊,友善記憶體讀寫以及後續位置索引
    size_t bytes = (bits + ) / ;
    bits = bytes * ;
    // 在string 中配置設定空間
    const size_t init_size = dst->size();
    dst->resize(init_size + bytes, );
    // string 的最後一個byte存儲使用的hash 函數的個數
    dst->push_back(static_cast<char>(k_));  // Remember # of probes in filter
    // 獲得string内部的char 型數組
    char* array = &(*dst)[init_size];
    // 逐個将每個key 寫入bloom fliter
    for (int i = ; i < n; i++) {
      // Use double-hashing to generate a sequence of hash values.
      // See analysis in [Kirsch,Mitzenmacher 2006].
      // leveldb 使用一個hash 函數，每次對hash值向右循環移位17個bit來模拟實作多個hash 函數的效果
      uint32_t h = BloomHash(keys[i]);
      // 每次向右循環移位17個bit
      const uint32_t delta = (h >> ) | (h << );  // Rotate right 17 bits
      for (size_t j = ; j < k_; j++) {
        // 在整個bit 數組的位置
        const uint32_t bitpos = h % bits;
        // 在char型數組的位置
        array[bitpos/] |= ( << (bitpos % ));
        // 更新獲得一個新的hash 數值
        h += delta;
      }
    }
  }
           

KeyMayMatch

判斷一個 key 在bloomfilter中是否存在。

virtual bool KeyMayMatch(const Slice& key, const Slice& bloom_filter) const {
    const size_t len = bloom_filter.size();
    if (len < ) return false;

    const char* array = bloom_filter.data();
    // 最後一個byte數值代表使用了多少hash函數
    // 除最後一個byte之外代表bit數組
    const size_t bits = (len - ) * ;

    // Use the encoded k so that we can read filters generated by
    // bloom filters created using different parameters.
    const size_t k = array[len-];
    if (k > ) {
      // Reserved for potentially new encodings for short bloom filters.
      // Consider it a match.
      return true;
    }
    // 使用相同的方法模拟多個hash函數計算的hash值
    uint32_t h = BloomHash(key);
    const uint32_t delta = (h >> ) | (h << );  // Rotate right 17 bits
    for (size_t j = ; j < k; j++) {
      const uint32_t bitpos = h % bits;
      // 找到一個bit位置不比對，提前傳回false
      // 在bit數組中位置的索引和設定時的方法一緻
      if ((array[bitpos/] & ( << (bitpos % ))) == ) return false;
      // 更新獲得下一個hash value
      h += delta;
    }
    // 全部比對return true
    return true;
  }
           

BloomFilter 應用場景

由于其高效的空間效率，bloomfilter 可以應用于以下場景：

• 爬蟲系統記錄以經爬取過的url
• 垃圾郵件過濾
• p2p 網絡中查找資源操作: 使用一個bloomfilter 儲存擁有此資源的網絡通路
• 廣播資訊時檢查某個ip是否發包
• 字典糾錯：将所有單詞存儲到bloomfilter中，如果不存在則認為是一個錯誤拼寫
• CDN 代理緩存: 每個cache 伺服器上使用bloomfilter 存儲兄弟cache 伺服器上是否有緩存關鍵字，如果沒有則可以避免一次查找

總結

Bloomfilter 是一種設計巧妙的資料結構，由于其良好的空間效率，可以用于判斷一個元素是否包含于海量元素集合的場景。

Leveldb 的實作的bloomfilter 可以靈活配置hash 函數的個數，使用一個hash 函數模拟任意多個hash 函數的場景，并将使用hash函數的個數存儲到bloomfilter編碼結果中。除此之外，leveldb bloomfilter 實作bit數組個數，hash函數個數以及存儲元素個數的最優配置，保證最低的誤差率。