布隆過(guò)濾器 Bloom Filter

布隆過(guò)濾器，用來(lái)判斷一個(gè)元素是否在集合中。
它的特點(diǎn)是節(jié)省空間，但是有誤判。有可能誤判某個(gè)不存在的元素在集合中（false positive），但是不會(huì)誤判存在的元素不再集合中（false negative）。RocksDB可能也正是因?yàn)檫@個(gè)特性，才選擇布隆過(guò)濾器來(lái)作為默認(rèn)filter的數(shù)據(jù)結(jié)構(gòu)。

簡(jiǎn)單地說(shuō)，布隆過(guò)濾器提供了這樣的語(yǔ)義:

• 某個(gè)元素可能在集合中
• 某個(gè)元素一定不在集合中

一個(gè)布隆過(guò)濾器由兩部分組成

• 一個(gè)長(zhǎng)度為m的位數(shù)組，各個(gè)為初始值都是0
• k個(gè)不同的hash函數(shù)

當(dāng)有一個(gè)新的元素x需要插入到集合中，并記錄在布隆過(guò)濾器中時(shí)

• 通過(guò)k個(gè)hash函數(shù)，計(jì)算k個(gè)hash值
• 在位數(shù)組中，將計(jì)算得到的k個(gè)hash值對(duì)應(yīng)的位置為1

查詢時(shí)

• 通過(guò)k個(gè)hash函數(shù)，計(jì)算k各hash值
• 在位數(shù)組中，查看k個(gè)hash值對(duì)應(yīng)的位是否都是1，如果都是1，則說(shuō)明被查詢的數(shù)在集合中

上面所說(shuō)的false negative就是因?yàn)橛幸欢ǖ母怕?，?huì)發(fā)生兩個(gè)不同的元素x和y，通過(guò)k各hash函數(shù)得到的k個(gè)值是相同的。

下圖簡(jiǎn)單說(shuō)明了布隆過(guò)濾器的原理。

Bloom filter原理.png

An example of a Bloom filter, representing the set {x, y, z}. The colored arrows show the positions in the bit array that each set element is mapped to. The element w is not in the set {x, y, z}, because it hashes to one bit-array position containing 0. For this figure, m = 18 and k = 3.

更詳細(xì)的說(shuō)明請(qǐng)參考 Wikipedia article.

RocksDB中Bloom Filter的用法

1. 每一個(gè)SST文件對(duì)應(yīng)一個(gè)Bloom Filter。
2. 當(dāng)SST文件寫入到磁盤中時(shí)，創(chuàng)建一個(gè)Bloom Filter， 并作為SST文件的一部分寫到磁盤上。
3. Bloom Filter只能通過(guò)key集合創(chuàng)建，而沒(méi)有合并的操作。所以，當(dāng)合并兩個(gè)SST文件時(shí)，新文件的Bloom Filter是創(chuàng)建出來(lái)的，而不是合并得到的。
4. 當(dāng)打開(kāi)一個(gè)SST文件時(shí)，會(huì)將對(duì)應(yīng)的Bloom Filter load到內(nèi)存中。當(dāng)關(guān)閉SST文件時(shí)，將對(duì)應(yīng)的Bloom Filter從內(nèi)存中刪除。

Bloom Filter類圖

BloomFilter類圖

職責(zé)說(shuō)明

• BlockBasedTableBuilder
  用于構(gòu)建一個(gè)SST文件的數(shù)據(jù)結(jié)構(gòu), 持有一個(gè)Rep對(duì)象來(lái)保存各種選項(xiàng)和成員變量. 詳見(jiàn)<RocksDB. BlockBasedTable源碼分析>
• Rep
  用于持有各種選項(xiàng)和成員變量, 其中filter_builder成員用于構(gòu)建bloom filter.
• FilterBlockBuilder
  接口類, 定義了構(gòu)建filter的接口, 包括IsBlockBased, StartBlock, Add, Finish等接口.
• BlockBasedFilterBlockBuilder
  實(shí)現(xiàn)了FilterBlockBuilder的接口, 用于構(gòu)造BlockBasedFilterBlock. 持有一個(gè)FilterPolicy* 類型的成員policy_, 用于對(duì)一組key創(chuàng)建filter block.
• FilterPolicy
  接口類, 定義創(chuàng)建filter的接口, 包括CreateFilter, KeyMayMatch等接口.
• BloomFilterPolicy
  實(shí)現(xiàn)了接口類FilterPolicy, 用于對(duì)一組key創(chuàng)建filter block.

Bloom FIlter創(chuàng)建流程分析

filter_policy作為BlockBasedTableOption的一個(gè)選項(xiàng)，在打開(kāi)數(shù)據(jù)庫(kù)對(duì)的時(shí)候指定

      BlockBasedTableOptions table_options;
      table_options.format_version = first_table_version;
      table_options.filter_policy.reset(NewBloomFilterPolicy(10));
      Options options = CurrentOptions();
      options.table_factory.reset(NewBlockBasedTableFactory(table_options));
      options.create_if_missing = true;
      options.compression = comp;
      // DestroyAndReopen(options);

NewBloomFilterPolicy函數(shù)返回Bloom Filter的實(shí)現(xiàn)對(duì)象

const FilterPolicy* NewBloomFilterPolicy(int bits_per_key,
                                         bool use_block_based_builder) {
  return new BloomFilterPolicy(bits_per_key, use_block_based_builder);
}

參數(shù)說(shuō)明

• bits_per_key：位數(shù)組的長(zhǎng)度。推薦的長(zhǎng)度是10，約有%1的誤判率。
• use_block_based_builder ：是否使用block based filter，和block based filter對(duì)應(yīng)的是full filter。默認(rèn)值是true，即使用block based filter。

如第二節(jié)所說(shuō)，Bloom Filter是在生成SST文件的時(shí)候創(chuàng)建的，而SST文件使用的是TableBuilder。以BlockBasedTableBuilder為例，來(lái)看Bloom Filter是如何被創(chuàng)建，并寫入到SST文件中。
BlockBasedTableBuilder并沒(méi)有直接使用filter_policy來(lái)創(chuàng)建filter，而是通過(guò)Rep的成員變量filter_builder。

std::unique_ptr<FilterBlockBuilder> filter_builder;

// 在BlockBasedTableBuilder::Rep的構(gòu)造函數(shù)里，創(chuàng)建一個(gè)filter block builder
    if (skip_filters) {
      filter_builder = nullptr;
    } else {
      filter_builder.reset(
          CreateFilterBlockBuilder(_ioptions, table_options, p_index_builder));
    }

// CreateFilterBlockBuilder的實(shí)現(xiàn)
FilterBlockBuilder* CreateFilterBlockBuilder(
    const ImmutableCFOptions& opt, const BlockBasedTableOptions& table_opt,
    PartitionedIndexBuilder* const p_index_builder) {
  if (table_opt.filter_policy == nullptr) return nullptr;

  FilterBitsBuilder* filter_bits_builder =
      table_opt.filter_policy->GetFilterBitsBuilder();
  if (filter_bits_builder == nullptr) {
    return new BlockBasedFilterBlockBuilder(opt.prefix_extractor, table_opt);
  } else {
      ...
  }
}

創(chuàng)建filter block builder的時(shí)候，將table_options傳了進(jìn)去，讓BlockBasedFilterBlockBuilder可以獲取打開(kāi)數(shù)據(jù)庫(kù)時(shí)創(chuàng)建的filter policy指針。

BlockBasedFilterBlockBuilder::BlockBasedFilterBlockBuilder(
    const SliceTransform* prefix_extractor,
    const BlockBasedTableOptions& table_opt)
    : policy_(table_opt.filter_policy.get()),
      prefix_extractor_(prefix_extractor),
      whole_key_filtering_(table_opt.whole_key_filtering),
      prev_prefix_start_(0),
      prev_prefix_size_(0) {
  assert(policy_);
}

filter builder通過(guò)該指針為一組key集合創(chuàng)建bloom filter。
filter builder的使用分為三個(gè)步驟。

1. StartBlock：為下一個(gè)block創(chuàng)建一個(gè)新的bloom filter。filter builder并不是只為整個(gè)table創(chuàng)建一個(gè)bloom filter。而是創(chuàng)建一組bloom filter，每個(gè)block有一個(gè)bloom filter。實(shí)際上，在計(jì)算filter數(shù)量的時(shí)候，是按照每2KB data創(chuàng)建一個(gè)filter。所以在實(shí)現(xiàn)上，一個(gè)block對(duì)應(yīng)兩個(gè)filter，一個(gè)filter對(duì)應(yīng)4KB data，一個(gè)filter是空的。在后面貼的源碼中可以看到這一點(diǎn)，之所這樣實(shí)現(xiàn)，可能是其它類型的filter對(duì)這樣的行為有依賴。這樣就可以在TableBuilder調(diào)用Flush接口時(shí)觸發(fā)filter builder的創(chuàng)建filter動(dòng)作，而Flush接口是4KB調(diào)用一次。
   創(chuàng)建一個(gè)新的bloom filter前，檢查之前是否有沒(méi)有生成filter的數(shù)據(jù)。判斷標(biāo)準(zhǔn)是比較上一個(gè)block filter的序號(hào)和已有 的filter數(shù)量。

void BlockBasedFilterBlockBuilder::StartBlock(uint64_t block_offset) {
  uint64_t filter_index = (block_offset / kFilterBase);
  assert(filter_index >= filter_offsets_.size());
  while (filter_index > filter_offsets_.size()) {
    GenerateFilter();
  }
}

正常情況下，兩者應(yīng)該相差2。即新來(lái)一個(gè)data block，一個(gè)data block是4KB，除以默認(rèn)的2KB，即新增2個(gè)filter。但是在調(diào)用GenerateFilter接口時(shí)，并沒(méi)有將新的key set分為兩部分，而是在第一次創(chuàng)建filter時(shí)為所有新增的key創(chuàng)建了filter，filter_offsets size + 1，這時(shí)filter_index比f(wàn)ilter_offsets size少1，但是start_和entries_成員已經(jīng)空了，GenerateFilter再被調(diào)用一次，filter_offsets增加一個(gè)和前一個(gè)一樣的offset值，其他什么都不做。

void BlockBasedFilterBlockBuilder::GenerateFilter() {
  const size_t num_entries = start_.size();
  if (num_entries == 0) {
    // Fast path if there are no keys for this filter
    filter_offsets_.push_back(static_cast<uint32_t>(result_.size()));
    return;
  }

  // Make list of keys from flattened key structure
  start_.push_back(entries_.size());  // Simplify length computation
  tmp_entries_.resize(num_entries);
  for (size_t i = 0; i < num_entries; i++) {
    const char* base = entries_.data() + start_[i];
    size_t length = start_[i + 1] - start_[i];
    // 這里只拷貝指針，沒(méi)有做字符串的拷貝
    tmp_entries_[i] = Slice(base, length);
  }

  // Generate filter for current set of keys and append to result_.
  filter_offsets_.push_back(static_cast<uint32_t>(result_.size()));
  policy_->CreateFilter(&tmp_entries_[0], static_cast<int>(num_entries),
                        &result_);

  tmp_entries_.clear();
  entries_.clear();
  start_.clear();
  prev_prefix_start_ = 0;
  prev_prefix_size_ = 0;
}

在后面會(huì)詳細(xì)分析policy_->CreateFilter(&tmp_entries_[0], static_cast<int>(num_entries), &result_);的實(shí)現(xiàn)。

2. Add
   在TableBuilder中，每插入一個(gè)key value對(duì)，就會(huì)將key插入到filter builder中。
   然后在Flush時(shí)為之前插入的所有key創(chuàng)建filter。

void BlockBasedTableBuilder::Add(const Slice& key, const Slice& value) {
    ...
    // Note: PartitionedFilterBlockBuilder requires key being added to filter
    // builder after being added to index builder.
    if (r->filter_builder != nullptr) {
      r->filter_builder->Add(ExtractUserKey(key));
    }
    ...
}

對(duì)于PartitionedFilterBlockBuilder（即我們現(xiàn)在分析的filter builder策略），Add會(huì)調(diào)用AddPrefix接口來(lái)插入key的前綴。
因?yàn)閑ntries_是一個(gè)字符串類型，所有key插入時(shí)都是直接append到字符串末尾，同時(shí)用一個(gè)vector<int>型的成員變量start_來(lái)記錄每個(gè)key在entries_中的offset。所以在取下一個(gè)key時(shí)，要先通過(guò)兩個(gè)成員變量prev_prefix_start_和prev_prefix_size_來(lái)確定下一個(gè)key的偏移量。
只有在key的prefix不存在時(shí)，才會(huì)插入。

inline void BlockBasedFilterBlockBuilder::AddPrefix(const Slice& key) {
  // get slice for most recently added entry
  Slice prev;
  if (prev_prefix_size_ > 0) {
    prev = Slice(entries_.data() + prev_prefix_start_, prev_prefix_size_);
  }

  Slice prefix = prefix_extractor_->Transform(key);
  // insert prefix only when it's different from the previous prefix.
  if (prev.size() == 0 || prefix != prev) {
    start_.push_back(entries_.size());
    prev_prefix_start_ = entries_.size();
    prev_prefix_size_ = prefix.size();
    entries_.append(prefix.data(), prefix.size());
  }
}

3. Finish
   當(dāng)TableBuilder創(chuàng)建完成后，在TableBuilder的Finish接口中會(huì)調(diào)用filter builder的Finish接口來(lái)將offset數(shù)組append到創(chuàng)建的filter結(jié)果所存的result_字符串中，然后調(diào)用WriteRawBlock寫入到SST文件中。

// 調(diào)用的地方
Status BlockBasedTableBuilder::Finish() {
  ...
  // Write filter block
  if (ok() && r->filter_builder != nullptr) {
    Status s = Status::Incomplete();
    while (s.IsIncomplete()) {
      Slice filter_content = r->filter_builder->Finish(filter_block_handle, &s);
      assert(s.ok() || s.IsIncomplete());
      r->props.filter_size += filter_content.size();
      WriteRawBlock(filter_content, kNoCompression, &filter_block_handle);
    }
  }
  ...
}

用于拼接的Finish方法實(shí)現(xiàn)

Slice BlockBasedFilterBlockBuilder::Finish(const BlockHandle& tmp,
                                           Status* status) {
  // In this impl we ignore BlockHandle
  *status = Status::OK();
  if (!start_.empty()) {
    GenerateFilter();
  }

  // Append array of per-filter offsets
  const uint32_t array_offset = static_cast<uint32_t>(result_.size());
  for (size_t i = 0; i < filter_offsets_.size(); i++) {
    PutFixed32(&result_, filter_offsets_[i]);
  }

  PutFixed32(&result_, array_offset);
  result_.push_back(kFilterBaseLg);  // Save encoding parameter in result
  return Slice(result_);
}

到這里我們看到filter block展開(kāi)之后的結(jié)構(gòu)如下

 [filter 0]
 [filter 1]
 [filter 2]
 ...
 [filter N-1]

 [offset of filter 0]                  : 4 bytes
 [offset of filter 1]                  : 4 bytes
 [offset of filter 2]                  : 4 bytes
 ...
 [offset of filter N-1]                : 4 bytes

 [offset of beginning of offset array] : 4 bytes
 lg(base)                              : 1 byte

filter builder通過(guò)調(diào)用BloomFilterPolicy的CreateFilter接口來(lái)創(chuàng)建filter。
CreateFilter的實(shí)現(xiàn)包括一下幾步：

1. 計(jì)算下一個(gè)filter占用的位數(shù)。為了保證準(zhǔn)確率，最小值是64位。
2. 確定下一個(gè)filter在dst中的起始偏移位置。resize之后，起始偏移位置到dst的末尾，就是一個(gè)長(zhǎng)度至少為64bit的bit數(shù)組。
3. 對(duì)每一個(gè)key，計(jì)算得到num_probes_個(gè)hash值，對(duì)bits取余，然后將對(duì)應(yīng)bit位至1.
   這樣就完成了一個(gè)filter的創(chuàng)建。

  virtual void CreateFilter(const Slice* keys, int n,
                            std::string* dst) const override {
    // 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);
    dst->push_back(static_cast<char>(num_probes_));  // Remember # of probes
    char* array = &(*dst)[init_size];
    for (size_t i = 0; i < (size_t)n; i++) {
      // Use double-hashing to generate a sequence of hash values.
      // See analysis in [Kirsch,Mitzenmacher 2006].
      uint32_t h = hash_func_(keys[i]);   // 計(jì)算hash 值
      const uint32_t delta = (h >> 17) | (h << 15);  // Rotate right 17 bits
      for (size_t j = 0; j < num_probes_; j++) {
        const uint32_t bitpos = h % bits;
        array[bitpos/8] |= (1 << (bitpos % 8));  // 將對(duì)應(yīng)bit位標(biāo)1
        h += delta; // 相當(dāng)于更換hash函數(shù)
      }
    }
  }

至此是BloomFilter創(chuàng)建相關(guān)流程分析?？梢杂妙愃频乃悸穪?lái)分析讀流程中，BloomFilter是如何生效的。

小結(jié)

BloomFilter標(biāo)識(shí)了某個(gè)key是否可能存在對(duì)應(yīng)的SST文件中。BloomFilter對(duì)于讀請(qǐng)求的優(yōu)化效果明顯, 不需要掃描整個(gè)SST文件, 因?yàn)樵诖蜷_(kāi)SST文件時(shí), 會(huì)將Bloom Filter加載到內(nèi)存中, 通過(guò)掃描filter即可判斷某個(gè)key是否可能存在該SST文件中。

參考資料
https://github.com/facebook/rocksdb/wiki/RocksDB-Bloom-Filter
https://github.com/facebook/rocksdb/wiki/Rocksdb-BlockBasedTable-Format