3. LevelDB源碼剖析之基礎部件-Bloom Filter、Murmur Hash、CRC32

3.1 Bloom Filter

3.1.1 基本概念

布隆過濾器（英語：Bloom Filter）是1970年由布隆提出的。當一個元素被加入集合時，通過K個散列函數(shù)將這個元素映射成一個位數(shù)組中的K個點，把它們置為1。檢索時，我們只要看看這些點是不是都是1就（大約）知道集合中有沒有它了：如果這些點有任何一個0，則被檢元素一定不在；如果都是1，則被檢元素很可能在。

相比于其它的數(shù)據(jù)結構，布隆過濾器在空間和時間方面都有巨大的優(yōu)勢。布隆過濾器存儲空間和插入/查詢時間都是常數(shù)O(k)。

但是布隆過濾器的缺點和優(yōu)點一樣明顯，誤算率是其中之一。隨著存入的元素數(shù)量增加，誤算率隨之增加。但是如果元素數(shù)量太少，則使用散列表足矣。另外，一般情況下不能從布隆過濾器中刪除元素，因為我們無法得知指定position上被那些key映射。

假設 Hash 函數(shù)以等概率條件選擇并設置 Bit Array 中的某一位，m 是該位數(shù)組的大小，n是數(shù)據(jù)個數(shù)，k 是 Hash 函數(shù)的個數(shù)，對于給定的m，n，如何選擇Hash函數(shù)個數(shù) k 由以下公式確定：k = ln2 * m/n = 0.7 * m/n。此時誤報率為：2^-k = 0.6185^m/n。當m/n=10時，誤報率約為0.8%。
關于詳細證明請參見布隆過濾器 (Bloom Filter) 詳解。

3.1.2 LevelDB版本實現(xiàn)

LevelDB將bloom filter做為內置過濾器，供用戶選擇使用，其核心算法代碼在bloom.cc中。

3.1.2.1 K值選擇

根據(jù)前面的描述，最佳k值為0.7m/n，leveldb中實現(xiàn)基本一致：

class BloomFilterPolicy : public FilterPolicy
{
private:
  size_t bits_per_key_;
  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
    k_ = static_cast<size_t>(bits_per_key * 0.69); // 0.69 =~ ln(2)
    if (k_ < 1)
      k_ = 1;
    if (k_ > 30)
      k_ = 30;
  }
  ......
};

LevelDB將m/n命名為bits_per_key，稍有點不同的是leveldb中的k值是向下取整的。作者的解釋是為了減少檢測碰撞所需的時間，但這樣增大了誤報率，整體性能上應該是要比非向下取整后要差的。

K值得取值范圍為1-30，作者推薦值為10(參見測試程序)，此時的誤報率小于1%(約為0.8%)。

3.1.2.2 布隆插入

布隆位組構建邏輯如下：

class BloomFilterPolicy : public FilterPolicy
{
  ......
  virtual void CreateFilter(const Slice *keys, int n, std::string *dst) const
  {
    //動態(tài)計算布隆過濾器的位組大小(n * m /n = m)
    // Compute bloom filter size (in both bits and bytes)
    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 < 64)
      bits = 64;

    size_t bytes = (bits + 7) / 8;
    bits = bytes * 8;
    
    //分配布隆位組
    const size_t init_size = dst->size();
    dst->resize(init_size + bytes, 0);
    //保存本次生成布隆位組時的K值
    dst->push_back(static_cast<char>(k_)); // Remember # of probes in filter
    char *array = &(*dst)[init_size];
    //為每個key值hash出key個位置并置1
    for (int i = 0; i < n; i++)
    {
      //使用double hashing計算出K個position而非采用K中hash算法
      // 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;
        array[bitpos / 8] |= (1 << (bitpos % 8));
        h += delta;
      }
    }
  }
  ......
}

LevelDB中的布隆位組不是預先設定好，而是動態(tài)生成的。對一批key值設置一個布隆位組，由此保證誤報率一直處于預期之內。另外，位組借用了std::string實現(xiàn)，并在位組最后額外保存了生成該布隆位組時采用的K值。

但有一點很奇怪，程序在resize之后緊接著做了一次push_back，這可能導致額外的一次內存分配、拷貝動作，對于leveldb這種對性能追求極致的程序并不應該，來看測試程序:

#include <iostream>
#include <string>

int main()
{
  std::string name;
  name = "hello";
  name.resize(63,100);
  std::cout << name.capacity() << std::endl; 

  name.push_back((char)97);
  std::cout << name.capacity() << std::endl; 
  std::cout << "Hello, " << name << "!\n";
}

采用g++ -O2命令編譯并運行該程序結果

desmondwangdeMacBook-Pro:demo desmondwang$ g++ -O2 a.cpp 
desmondwangdeMacBook-Pro:demo desmondwang$ ./a.out 
63
127
Hello, hellodddddddddddddddddddddddddddddddddddddddddddddddddddddddddda!

最后，LevelDB并沒有真正的使用K個hash算法計算position，而是采用double hashing，公式如下：h(i,k)=(h1(k)+i?h2(k))mod|T|。LevelDB中，h1(k)為根據(jù)hash算法計算出來的結果，而h2(k)為delta = (h >> 17) | (h << 15)。

3.1.2.3 布隆過濾

布隆過濾計算邏輯如下：

class BloomFilterPolicy : public FilterPolicy
{
  ......
  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;

    //獲取K值
    // 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;
  }
  ......
};

實現(xiàn)邏輯非常簡單，首先取出K值，隨后采用和構建布隆位組相同的方式判斷指定位組是否為1，如全部為1則認定存在該值，否則判斷不存在。

3.2 Murmur Hash

布隆過濾中使用的Hash算法(BloomHash)最終調用的是hash.cc中的Hash函數(shù)，按作者說法它是Murmur hash的一個變種。關于Murmur hash簡介如下:

MurmurHash 是一種非加密型哈希函數(shù)，適用于一般的哈希檢索操作。

由Austin Appleby在2008年發(fā)明，并出現(xiàn)了多個變種，都已經發(fā)布到了公有領域(public domain)。與其它流行的哈希函數(shù)相比，對于規(guī)律性較強的key，MurmurHash的隨機分布特征表現(xiàn)更良好。

代碼實現(xiàn)如下：

uint32_t Hash(const char *data, size_t n, uint32_t seed)
{
  // Similar to murmur hash
  const uint32_t m = 0xc6a4a793;
  const uint32_t r = 24;
  const char *limit = data + n;
  uint32_t h = seed ^ (n * m);

  // Pick up four bytes at a time
  while (data + 4 <= limit)
  {
    uint32_t w = DecodeFixed32(data);
    data += 4;
    h += w;
    h *= m;
    h ^= (h >> 16);
  }

  // Pick up remaining bytes
  switch (limit - data)
  {
  case 3:
    h += static_cast<unsigned char>(data[2]) << 16;
    FALLTHROUGH_INTENDED;
  case 2:
    h += static_cast<unsigned char>(data[1]) << 8;
    FALLTHROUGH_INTENDED;
  case 1:
    h += static_cast<unsigned char>(data[0]);
    h *= m;
    h ^= (h >> r);
    break;
  }
  return h;
}

直觀上看代碼比Murmur hash更為簡潔，本人對hash算法并沒有深入研究，此處的各種優(yōu)劣只能暫略。

3.3 CRC32

CRC（Cyclic Redundancy Check）中文名是循環(huán)冗余校驗，在數(shù)據(jù)存儲和數(shù)據(jù)通訊領域，為了保證數(shù)據(jù)的正確，采用檢錯的手段。
LevelDB自己實現(xiàn)了CRC32算法，核心代碼如下:

uint32_t Extend(uint32_t crc, const char *buf, size_t size)
{
  static bool accelerate = CanAccelerateCRC32C();
  if (accelerate)
  {
    return port::AcceleratedCRC32C(crc, buf, size);
  }

  const uint8_t *p = reinterpret_cast<const uint8_t *>(buf);
  const uint8_t *e = p + size;
  uint32_t l = crc ^ 0xffffffffu;

#define STEP1                  \
  do                           \
  {                            \
    int c = (l & 0xff) ^ *p++; \
    l = table0_[c] ^ (l >> 8); \
  } while (0)
#define STEP4                       \
  do                                \
  {                                 \
    uint32_t c = l ^ LE_LOAD32(p);  \
    p += 4;                         \
    l = table3_[c & 0xff] ^         \
        table2_[(c >> 8) & 0xff] ^  \
        table1_[(c >> 16) & 0xff] ^ \
        table0_[c >> 24];           \
  } while (0)

  // Point x at first 4-byte aligned byte in string.  This might be
  // just past the end of the string.
  const uintptr_t pval = reinterpret_cast<uintptr_t>(p);
  const uint8_t *x = reinterpret_cast<const uint8_t *>(((pval + 3) >> 2) << 2);
  if (x <= e)
  {
    // Process bytes until finished or p is 4-byte aligned
    while (p != x)
    {
      STEP1;
    }
  }
  // Process bytes 16 at a time
  while ((e - p) >= 16)
  {
    STEP4;
    STEP4;
    STEP4;
    STEP4;
  }
  // Process bytes 4 at a time
  while ((e - p) >= 4)
  {
    STEP4;
  }
  // Process the last few bytes
  while (p != e)
  {
    STEP1;
  }
#undef STEP4
#undef STEP1
  return l ^ 0xffffffffu;
}

關于CRC32網上有完整的算法說明，本文說明如下幾點：

  1. 優(yōu)先判斷運行環(huán)境的CPU是否自身有計算CRC32的能力，如果有則使用CPU自身的能力計算CRC32。
  2. 絕大多數(shù)人定義宏的時候，將宏放到.h文件或者.c文件的最開始處。這其實違反了生命周期最小化原則。示例中STEP1、STEP2宏在函數(shù)內定義，并在函數(shù)結尾處解除宏定義，由此保證該宏僅在該函數(shù)內生效。
  3. 宏定義采用良好的do {} while(0)方式實現(xiàn)，這樣做有兩個好處：避免出現(xiàn)變量重復定義，以及避免誤用。

3.4 總結

布隆過濾器是LevelDB1.2版本新增的特性，其目的在于進一步提升LevelDB的性能。

轉載請注明：【隨安居士】http://www.itdecent.cn/p/366d6563fba8

最后編輯于 ：
?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
【社區(qū)內容提示】社區(qū)部分內容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內容（如有圖片或視頻亦包括在內）由作者上傳并發(fā)布，文章內容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內容

友情鏈接更多精彩內容