RocksDB. Bloom Filter源码分析

2017-04-24 本文已影响1203人周肃

布隆过滤器 Bloom Filter

布隆过滤器，用来判断一个元素是否在集合中。
它的特点是节省空间，但是有误判。有可能误判某个不存在的元素在集合中（false positive），但是不会误判存在的元素不再集合中（false negative）。RocksDB可能也正是因为这个特性，才选择布隆过滤器来作为默认filter的数据结构。

简单地说，布隆过滤器提供了这样的语义:

某个元素可能在集合中
某个元素一定不在集合中

一个布隆过滤器由两部分组成

一个长度为m的位数组，各个为初始值都是0
k个不同的hash函数

当有一个新的元素x需要插入到集合中，并记录在布隆过滤器中时

通过k个hash函数，计算k个hash值
在位数组中，将计算得到的k个hash值对应的位置为1

查询时

通过k个hash函数，计算k各hash值
在位数组中，查看k个hash值对应的位是否都是1，如果都是1，则说明被查询的数在集合中

上面所说的false negative就是因为有一定的概率，会发生两个不同的元素x和y，通过k各hash函数得到的k个值是相同的。

下图简单说明了布隆过滤器的原理。

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.

更详细的说明请参考 Wikipedia article.

RocksDB中Bloom Filter的用法

每一个SST文件对应一个Bloom Filter。
当SST文件写入到磁盘中时，创建一个Bloom Filter，并作为SST文件的一部分写到磁盘上。
Bloom Filter只能通过key集合创建，而没有合并的操作。所以，当合并两个SST文件时，新文件的Bloom Filter是创建出来的，而不是合并得到的。
当打开一个SST文件时，会将对应的Bloom Filter load到内存中。当关闭SST文件时，将对应的Bloom Filter从内存中删除。

Bloom Filter类图

BloomFilter类图

职责说明

BlockBasedTableBuilder
用于构建一个SST文件的数据结构, 持有一个Rep对象来保存各种选项和成员变量. 详见<RocksDB. BlockBasedTable源码分析>
Rep
用于持有各种选项和成员变量, 其中filter_builder成员用于构建bloom filter.
FilterBlockBuilder
接口类, 定义了构建filter的接口, 包括IsBlockBased, StartBlock, Add, Finish等接口.
BlockBasedFilterBlockBuilder
实现了FilterBlockBuilder的接口, 用于构造BlockBasedFilterBlock. 持有一个FilterPolicy* 类型的成员policy_, 用于对一组key创建filter block.
FilterPolicy
接口类, 定义创建filter的接口, 包括CreateFilter, KeyMayMatch等接口.
BloomFilterPolicy
实现了接口类FilterPolicy, 用于对一组key创建filter block.

Bloom FIlter创建流程分析

filter_policy作为BlockBasedTableOption的一个选项，在打开数据库对的时候指定

      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函数返回Bloom Filter的实现对象

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

参数说明

bits_per_key：位数组的长度。推荐的长度是10，约有%1的误判率。
use_block_based_builder ：是否使用block based filter，和block based filter对应的是full filter。默认值是true，即使用block based filter。

如第二节所说，Bloom Filter是在生成SST文件的时候创建的，而SST文件使用的是TableBuilder。以BlockBasedTableBuilder为例，来看Bloom Filter是如何被创建，并写入到SST文件中。
BlockBasedTableBuilder并没有直接使用filter_policy来创建filter，而是通过Rep的成员变量filter_builder。

std::unique_ptr<FilterBlockBuilder> filter_builder;

// 在BlockBasedTableBuilder::Rep的构造函数里，创建一个filter block builder
    if (skip_filters) {
      filter_builder = nullptr;
    } else {
      filter_builder.reset(
          CreateFilterBlockBuilder(_ioptions, table_options, p_index_builder));
    }

// CreateFilterBlockBuilder的实现
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 {
      ...
  }
}

创建filter block builder的时候，将table_options传了进去，让BlockBasedFilterBlockBuilder可以获取打开数据库时创建的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通过该指针为一组key集合创建bloom filter。
filter builder的使用分为三个步骤。

StartBlock：为下一个block创建一个新的bloom filter。filter builder并不是只为整个table创建一个bloom filter。而是创建一组bloom filter，每个block有一个bloom filter。实际上，在计算filter数量的时候，是按照每2KB data创建一个filter。所以在实现上，一个block对应两个filter，一个filter对应4KB data，一个filter是空的。在后面贴的源码中可以看到这一点，之所这样实现，可能是其它类型的filter对这样的行为有依赖。这样就可以在TableBuilder调用Flush接口时触发filter builder的创建filter动作，而Flush接口是4KB调用一次。
创建一个新的bloom filter前，检查之前是否有没有生成filter的数据。判断标准是比较上一个block filter的序号和已有的filter数量。

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();
  }
}

正常情况下，两者应该相差2。即新来一个data block，一个data block是4KB，除以默认的2KB，即新增2个filter。但是在调用GenerateFilter接口时，并没有将新的key set分为两部分，而是在第一次创建filter时为所有新增的key创建了filter，filter_offsets size + 1，这时filter_index比filter_offsets size少1，但是start_和entries_成员已经空了，GenerateFilter再被调用一次，filter_offsets增加一个和前一个一样的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];
    // 这里只拷贝指针，没有做字符串的拷贝
    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;
}

在后面会详细分析policy_->CreateFilter(&tmp_entries_[0], static_cast<int>(num_entries), &result_);的实现。

Add
在TableBuilder中，每插入一个key value对，就会将key插入到filter builder中。
然后在Flush时为之前插入的所有key创建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));
    }
    ...
}

对于PartitionedFilterBlockBuilder（即我们现在分析的filter builder策略），Add会调用AddPrefix接口来插入key的前缀。
因为entries_是一个字符串类型，所有key插入时都是直接append到字符串末尾，同时用一个vector<int>型的成员变量start_来记录每个key在entries_中的offset。所以在取下一个key时，要先通过两个成员变量prev_prefix_start_和prev_prefix_size_来确定下一个key的偏移量。
只有在key的prefix不存在时，才会插入。

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());
  }
}

Finish
当TableBuilder创建完成后，在TableBuilder的Finish接口中会调用filter builder的Finish接口来将offset数组append到创建的filter结果所存的result_字符串中，然后调用WriteRawBlock写入到SST文件中。

// 调用的地方
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方法实现

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展开之后的结构如下

 [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通过调用BloomFilterPolicy的CreateFilter接口来创建filter。
CreateFilter的实现包括一下几步：

计算下一个filter占用的位数。为了保证准确率，最小值是64位。
确定下一个filter在dst中的起始偏移位置。resize之后，起始偏移位置到dst的末尾，就是一个长度至少为64bit的bit数组。
对每一个key，计算得到num_probes_个hash值，对bits取余，然后将对应bit位至1.
这样就完成了一个filter的创建。

  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]);   // 计算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));  // 将对应bit位标1
        h += delta; // 相当于更换hash函数
      }
    }
  }

至此是BloomFilter创建相关流程分析。可以用类似的思路来分析读流程中，BloomFilter是如何生效的。

小结

BloomFilter标识了某个key是否可能存在对应的SST文件中。BloomFilter对于读请求的优化效果明显, 不需要扫描整个SST文件, 因为在打开SST文件时, 会将Bloom Filter加载到内存中, 通过扫描filter即可判断某个key是否可能存在该SST文件中。

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

RocksDB. Bloom Filter源码分析

布隆过滤器 Bloom Filter

RocksDB中Bloom Filter的用法

Bloom Filter类图

Bloom FIlter创建流程分析

小结

猜你喜欢

热点阅读