leveldb登山之路——bloom

一、什么是布隆過濾器

        在數學之美中，有一章是關于布隆過濾器的講解，內容如下。

        在字處理軟件中，一個英語單詞是否拼寫正確；在FBI中，一個嫌疑人的名字是否在嫌疑名單上；在網絡爬蟲里，一個網址是否已訪問過，等等。最直接的方法就是將集合中全部的元素存在計算機中，遇到一個新元素時，將它和集合中的元素之間比較。一般來說，計算機中的集合是用哈希表存儲的。好處是快速準確，缺點是耗費存儲空間。當集合很小時，這個問題不明顯，當集合規模巨大時，哈希表存儲效率低的問題就顯現出來了。如果使用哈希表存儲Email地址，每一億個Email地址，就需要1.6GB的內存。為了解決哈希表的這個問題，就需要一種叫布隆過濾器的數學工具。所以，布隆過濾器是個數據工具。他的大小只需要哈希表1/8到1/4的大小就能解決同樣的問題。

        因此，布隆過濾器是一種數學工具。

二、布隆過濾器的原理

        布隆過濾器實際上是一個很長的二進制向量和一系列隨機映射函數。我們通過電子郵件地址的例子來進行說明。

        如果需要存儲一億個電子郵件地址，先建立一個16億二進制(比特)，即2億字節的向量，然后將這16億個二進制位全部清零。再對每一個電子郵件的地址X，用8個不同的隨機數產生器(F1, F2, F3 ..., F8)產生8個信息指紋(f1, f2, f3....., f8)。再用一個隨機數產生器G把這8個位置的二進制全部設置為1。對這一億個電子郵件地址都進行這樣的處理后，就產生了一個針對布隆過濾器。

        當我們需要看一個可疑地址Y是否在黑名單中時，用8個相同的隨機數產生器(F1, F2, F3, ..., F8)對這個地址產生8個信息指紋s1, s2, s3, ... s8，然后將這8個指紋對應到布隆過濾器的8個二進制位，分別是t1, t2, ...., t8。如果Y在黑名單中，那么t1, t2, ...., t8對應的8個二進制數肯定是1。

三、布隆過濾器的優缺點

        優點： 快速，省空間

        缺點： 存在一定的誤識別率

四、leveldb中的布隆過濾器

        因為還沒有實際使用過leveldb，所以，個人在這里覺得，leveldb的布隆過濾器是在數據庫查找時，更快，更省空間。后面具體使用leveldb時，再來理解bloom。下面一起來看代碼分析

        BloomFilterPolicy是繼承自FilterPolicy的，關于FilterPolicy在后面的學習中再詳述，本節僅討論Bloom.cc。

        1. BloomFilterPolicy類

            1.1 BloomFilterPolicy

            構造函數，主要是進行初始化，然后確定需要多少個哈希函數

  explicit BloomFilterPolicy(int bits_per_key)
      : bits_per_key_(bits_per_key) {
    // We intentionally round down to reduce probing cost a little bit
    k_ = static_cast<size_t>(bits_per_key * 0.69);  // 0.69 =~ ln(2)
    if (k_ < 1) k_ = 1;
    if (k_ > 30) k_ = 30;		
  }

            1.2 Name

            返回bloom過濾器名稱

  virtual const char* Name() const {
    return "leveldb.BuiltinBloomFilter2";
  }

            1.3 CreateFilter

            創建BloomFilter，keys是需要存入的key， n是需要存入的個數， dst是BloomFilter的結果

            leveldb在最終的BloomFilter上加了一個k_，表示使用了多少個哈希函數，這樣在查詢時，就可以直接知道用來多少個哈希函數，而不需要重新用一個變量來記錄用來多少個哈希函數。

virtual void CreateFilter(const Slice* keys, int n, std::string* dst) const {
    // Compute bloom filter size (in both bits and bytes)
    size_t bits = n * bits_per_key_;		//所有需要創建的key的總位數

    // For small n, we can see a very high false positive rate.  Fix it
    // by enforcing a minimum bloom filter length.
    if (bits < 64) bits = 64;	//最小需要64位來保存

	//這兩行主要進行字節對齊
    size_t bytes = (bits + 7) / 8;		//對所占的內存進行8字節對齊
    bits = bytes * 8;					//總共需要的位數
	
    const size_t init_size = dst->size();		
    dst->resize(init_size + bytes, 0);		//將所有的位都置為0
    dst->push_back(static_cast<char>(k_));  // Remember # of probes in filter， 將總的哈希函數個數存入最后
    char* array = &(*dst)[init_size];		
    for (int i = 0; i < n; i++) {
      // Use double-hashing to generate a sequence of hash values.
      // See analysis in [Kirsch,Mitzenmacher 2006].
      uint32_t h = BloomHash(keys[i]);
      const uint32_t delta = (h >> 17) | (h << 15);  // Rotate right 17 bits
      for (size_t j = 0; j < k_; j++) {
        const uint32_t bitpos = h % bits;			//獲取第一個數在bits中的位置
		// 將數據存入array中
		 /*
         bitpos/8計算元素在第幾個字節；
         (1 << (bitpos % 8))計算元素在字節的第幾位；
         例如：
         bitpos的值為3， 則元素在第一個字節的第三位上，那么這位上應該賦值為1。
         bitpos的值為11，則元素在第二個字節的第三位上，那么這位上應該賦值為1。
         為什么要用|=運算，因為字節位上的值可能為1，那么新值賦值，還需要保留原來的值。
         */
        array[bitpos/8] |= (1 << (bitpos % 8));	
        h += delta;
      }
    }
  }

            1.4 KeyMayMatch

            查詢是否存在函數， key是需要查詢的， bloom_filter則是需要使用對比的過濾器

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

    const char* array = bloom_filter.data();
    const size_t bits = (len - 1) * 8;

    // Use the encoded k so that we can read filters generated by
    // bloom filters created using different parameters.
    const size_t k = array[len-1];		//這里是使用過濾器尾部保存的哈希函數個數
    if (k > 30) {
		//保留短布隆過濾器
      // Reserved for potentially new encodings for short bloom filters.
      // Consider it a match.
      return true;
    }

    uint32_t h = BloomHash(key);		
    const uint32_t delta = (h >> 17) | (h << 15);  // Rotate right 17 bits
    for (size_t j = 0; j < k; j++) {
      const uint32_t bitpos = h % bits;		//查找
      if ((array[bitpos/8] & (1 << (bitpos % 8))) == 0) return false;		//判斷是否存在布隆過濾器中
      h += delta;
    }
    return true;
  }

            以上就是leveldb中bloom的主要代碼與分析，可以考慮，以后在自己寫代碼時，如果存在有大量數據需要查詢，讀取時，可以先通過布隆過濾器來看是否存在，然后再進行讀取。而且布隆過濾器是一種數學方法，從側面說明了數學與計算機之間的緊密聯系，因此，有時間還是需要對數學進行深入學習。

        更多分享，盡在交流QQ群：199546072