leveldb中的SSTable (3)

| 分类 leveldb  | 标签 leveldb 

前言

sstable 文件的foot, data block 和index block都已经介绍过了,看起来好像已经齐备了,根据footer 能够找到index block,而index记录了data block的索引信息,可以根据index block中的索引,快速定位到某个key(可能)位于which data block。

那么meta block和metaindex block到底是干啥的呢,为什么要有它呢?meta block的作用在于快速的确定,是否存在某个key,如果不存在,就没必要去遍历data block查找该key了。

如何快速判断某个key是否存在?

Bloom Filter这种数据结构就是干这个活的。

Bloom Filter

Burton Howard Bloom 在1970年设计的数据结构,用来判断某个key是否属于某个集合。它的原理比较简单,首先定义一个很大的数组,作为位图,初始时,位图中的每个元素都是0。向集合添加某个key的时候,计算一组hash值(多个不同的hash函数),根据结果将位图对应位置的位设为1。如下图所示:

当判断某个key,如上图中的bean是否存在时,将key值通过多个hash函数(如上图中的3个hash函数),判断对应位置是否是1,如果不是1,表示该key并不存在。

如果将key值通过多个hash函数,发现每一个对应位置的bit都是1,说明该key值有很大的概率是存在的。

为什么是很大的概率,而不是绝对?因为Bloom Filter可能会出现虚警,发现每个对应位置都是1,但是去查找确实不存在该key,如下图所示:

上图中lucky并不在集合中,但是hash算出来的三个位置,分别有abc leveldb moon将其设置为1,所以lucky被误判成存在集合中,造成false positive,出现虚警。

即bloom filter 有如下的性质:

  • 如果bloom filter判断不在集合中,那么一定不在集合中 (Never false negative)
  • 如果bloom filter判断在集合中,那么有很大的概率在集合中,但是也有一定的概率不在集合中,即出现虚警 (false positive)

既然会出现false positive,那么虚警概率就很重要了。考虑极端情况,如果位图数组相对于key的个数,太少,势必造成几乎每一个bit都是1,这样虚警的概率是非常高的,整个bloom filter压根就没有存在的价值,因为无论怎么判断,bloom filter总是回答key在集合中。

因此判断集合的大小,选择合适size的bloom filter位图就成了效率的关键。

如果位图中的bit数位为m,集合中的元素为n,hash函数的个数为k,那么虚警概率

如果m 和n 是确定的,那么最优的k为:

m n k 组合下,相关虚警概率的情况如下:

(数据来源于Bloom Filters - the math)

很明显,如果hash 函数的个数太多,就会带来更多的运算,这显然是不合理的,因此,要想降低虚警概率,必须要m/n要尽可能的大,

如果m/n等于20的时候,3个hash函数就可以将虚警概率降低到千分之三左右,4个hash 函数就能将虚警概率控制在千分之一左右。

leveldb中的bloom filter

leveldb搞个全局的Bloom Filter是不现实的,因为无法预知客户到底存放多少key,leveldb可能存放百万千万个key-value pair,也可能存放几百 几千个key-value,因为n不能确定范围,因此位图的大小m,也很难事先确定。

如果设置的m过大,势必造成内存浪费,如果设置的m过小,就会造成很大的虚警。

leveldb的设计,并不是全局的bloom filter,而是根据局部的bloom filter,每一部分的数据,设计出一个bloom filter,多个bloom filter来完成任务。

leveldb中的bloom filter有第二个层面的改进,即采用了下面论文中的算法思想:

Less Hashing, Same Performance: Building a Better Bloom Filter

这个论文有兴趣的筒子可以读一下,我简单summary一下论文的思想,为了尽可能的降低虚概率,最优的hash函数个数可能很高,比如需要10个hash函数,这势必带来很多的计算,而且要设计多个不同的hash函数,论文提供了一个思想,用1个hash函数,多次移位和加法,达到多个hash 的结果。

代码解读

        static uint32_t BloomHash(const Slice& key) // 哈希函数
        {
            return Hash(key.data(), key.size(), 0xbc9f1d34);
        }
        
        class BloomFilterPolicy : public FilterPolicy
        {
        private:
            size_t bits_per_key_; // 一个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;
            }
            
            virtual const char* Name() const
            {
                return "leveldb.BuiltinBloomFilter2";
            }
            
            // n:key的个数;dst:存放过滤器处理的结果
            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_;
                
                // For small n, we can see a very high false positive rate.  Fix it
                // by enforcing a minimum bloom filter length.
                // 位列bits最小64位,8个字节
                if (bits < 64) bits = 64;
                
                // bits位占多少个字节
                size_t bytes = (bits + 7) / 8;
                // 得到真实的位列bits
                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];
                for (size_t 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
                    // 使用k个哈希函数,计算出k位,每位都赋值为1。
                    // 为了减少哈希冲突,减少误判。
                    for (size_t j = 0; j < k_; j++)
                    {
                        // 得到元素在位列bits中的位置
                        const uint32_t bitpos = h % bits;
                        /*
                         bitpos/8计算元素在第几个字节;
                         (1 << (bitpos % 8))计算元素在字节的第几位;
                         例如:
                         bitpos的值为3, 则元素在第一个字节的第三位上,那么这位上应该赋值为1。
                         bitpos的值为11,则元素在第二个字节的第三位上,那么这位上应该赋值为1。
                         为什么要用|=运算,因为字节位上的值可能为1,那么新值赋值,还需要保留原来的值。
                         */
                        array[bitpos/8] |= (1 << (bitpos % 8));
                        h += delta;
                    }
                }
            }
            
            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)
                {
                    // 为短bloom filter保留,当前认为直接match 
                    // 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;
                    // 只要有一位为0,说明元素肯定不在过滤器集合内。
                    if ((array[bitpos/8] & (1 << (bitpos % 8))) == 0) return false;
                    h += delta;
                }
                return true;
            }
        };

我们先来搞定产生Bloom Filter的算法,然后来看调用Bloom Filter的时机。

输入是:

  • keys : 本轮所有的key
  • n : 本轮所有的key的个数

严格意义上讲,Leveldb Bloom Filter创建时只有一个参数即bits_per_key:

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

这个bits_per_key是何意呢? 它即是前文原理部分介绍的 m/n,位图bit数除以key的个数,这个参数是创建BloomFilterPolicy的唯一一个入参,按照我们的表格,bits_per_key越大越好。

有了这个值,就有最优的k值,即:

即我们看到的:

    k_ = static_cast<size_t>(bits_per_key * 0.69);  // 0.69 =~ ln(2)

目前有了m/n的值,根据key的个数n,就可以计算出最优的bit数,即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.
                // 位列bits最小64位,8个字节
                if (bits < 64) bits = 64;
                
                // bits位占多少个字节
                size_t bytes = (bits + 7) / 8;
                // 得到真实的位列bits
                bits = bytes * 8;  /*bits即 位图中bit的个数*/

剩下的事情就水到渠成了,对于每个key,计算k次,将对应位置的bit设置成1:

                外层循环是每一个key值
                for (size_t 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
                    
                    /* 内层循环是对每一个key计算k次hash,当然用的是前面提到的论文中的思想。*/
                    for (size_t j = 0; j < k_; j++)
                    {
                        // 得到元素在位列bits中的位置
                        const uint32_t bitpos = h % bits;

                        array[bitpos/8] |= (1 << (bitpos % 8));
                        h += delta;
                    }
                }
            }

注意,因为sstable中key的个数可能很多,当攒了足够多个key值,就会计算一批位图,再攒一批key,又计算一批位图,那么这么多bloom filter的位图,必需分隔开,否则就混了。

也就说,位图与位图的边界必需清晰,否则就乱了。看下面代码注释:

void FilterBlockBuilder::GenerateFilter() {
  const size_t num_keys = start_.size();
  if (num_keys == 0) {
    // Fast path if there are no keys for this filter
    filter_offsets_.push_back(result_.size());
    return;
  }

  // Make list of keys from flattened key structure
  start_.push_back(keys_.size());  // Simplify length computation
  tmp_keys_.resize(num_keys);
  
  /*得到本轮的所有的keys,放入tmp_keys_数组*/
  for (size_t i = 0; i < num_keys; i++) {
    const char* base = keys_.data() + start_[i];
    size_t length = start_[i+1] - start_[i];
    tmp_keys_[i] = Slice(base, length);
  }

  // Generate filter for current set of keys and append to result_.
  
  /*先记录下上一轮位图截止位置,防止位图的边界混淆*/
  filter_offsets_.push_back(result_.size());
  /*将本轮keys计算得来的位图追加到result_字符串*/
  
  policy_->CreateFilter(&tmp_keys_[0], static_cast<int>(num_keys), &result_);



  tmp_keys_.clear();
  keys_.clear();
  start_.clear();
}

当TableBuilder 每次增加一个元素的时候,就会调用:

void FilterBlockBuilder::AddKey(const Slice& key) {
  Slice k = key;
  start_.push_back(keys_.size());
  keys_.append(k.data(), k.size());
}

我们看下FilterBlockBuilder的定义:

class FilterBlockBuilder {
 public:
  explicit FilterBlockBuilder(const FilterPolicy*);

  void StartBlock(uint64_t block_offset);
  void AddKey(const Slice& key);
  Slice Finish();

 private:
  void GenerateFilter();

  const FilterPolicy* policy_;
  
  /*注意本轮keys产生的位图计算完毕后,会将keys_, start_ ,还有tmp_keys_ 清空*/
  std::string keys_;              // 暂时存放本轮所有keys,追加往后写入
  std::vector<size_t> start_;     // 记录本轮key与key之间的边界的位置,便于分割成多个key
  
  std::string result_;            // 计算出来的位图,多轮计算则往后追加写入
  std::vector<Slice> tmp_keys_;   // 将本轮的所有key,存入该vector,其实并无存在的必要,用临时变量即可
  std::vector<uint32_t> filter_offsets_; //计算出来的多个位图的边界位置,用于分隔多轮keys产生的位图

  // No copying allowed
  FilterBlockBuilder(const FilterBlockBuilder&);
  void operator=(const FilterBlockBuilder&);
};

我们终于提到了多轮了,既然有轮次的概念,那么问题就来了,啥时候发起一轮keys位图的计算?

接下来我们看为一轮多个时机


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

这个函数负责一轮计算Bloom Filter的位图。

触发的时机是Flush函数,而Flush的时机是预测Data Block的size超过options.block_size

void TableBuilder::Add(const Slice& key, const Slice& value) {
  Rep* r = rep_;
  assert(!r->closed);
  if (!ok()) return;
  if (r->num_entries > 0) {
    assert(r->options.comparator->Compare(key, Slice(r->last_key)) > 0);
  }

  if (r->pending_index_entry) {
    assert(r->data_block.empty());
    r->options.comparator->FindShortestSeparator(&r->last_key, key);
    std::string handle_encoding;
    r->pending_handle.EncodeTo(&handle_encoding);
    r->index_block.Add(r->last_key, Slice(handle_encoding));
    r->pending_index_entry = false;
  }

  if (r->filter_block != NULL) {
    r->filter_block->AddKey(key);
  }

  r->last_key.assign(key.data(), key.size());
  r->num_entries++;
  r->data_block.Add(key, value);

  const size_t estimated_block_size = r->data_block.CurrentSizeEstimate();
  if (estimated_block_size >= r->options.block_size) {
    Flush();
  }
}

void TableBuilder::Flush() {
  Rep* r = rep_;
  assert(!r->closed);
  if (!ok()) return;
  if (r->data_block.empty()) return;
  assert(!r->pending_index_entry);
  WriteBlock(&r->data_block, &r->pending_handle);
  if (ok()) {
    r->pending_index_entry = true;
    r->status = r->file->Flush();
  }
  if (r->filter_block != NULL) {
    r->filter_block->StartBlock(r->offset);
  }
}

有一个不容易理解的地方是有一个参数2KB


static const size_t kFilterBaseLg = 11;
static const size_t kFilterBase = 1 << kFilterBaseLg;

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

这个参数的本意应该是,如果多个key-value的总长度超过了2KB,我就应该计算这些key的位图了。但是无奈发起的时机是有Flush决定,因此,并非2KB的数据就会发起一轮 Bloom Filter的计算,比如block_offset等于7KB,可能造成多轮的GenerateFilter函数调用,而除了第一轮的调用会产生位图,其它2轮相当于轮空,只是将result_的size再次放入filter_offsets_。

void FilterBlockBuilder::GenerateFilter() {
  const size_t num_keys = start_.size();
  if (num_keys == 0) {
    // Fast path if there are no keys for this filter
    filter_offsets_.push_back(result_.size());
    return;
  }
  
  ...
}

势必造成如下图的结果:

如果(0~7K-1)是第一个data block的范围,(7K~14K-1)是第二个 data block的范围,(0~6K-1)没啥问题,可是(6K~7K-1)属于第一个data block,但是存放bloom filter的时候,指向的是第二个 bloom filter,将来可能会带来问题。

实际上不会,因为 meta block是data block的辅助,应用层绝不会问 data block offset为6K的block位图在何方。从查找的途径来看,先根据key通过第二篇的index block,找到对应的data block,而data block的offset,只会是0或者7K,绝不会是6K。

当传入data block的offset是7K的时候,根据上表,就会返回第二个bloom filter,而第二个bloom filter会负责整个第二个data block的全部key,即data block的(7K~14K-1)范围内的所有key,都可以利用第二个bloom filter找到。

使用这种方法,当用户输入data block offset的时候,查找对应data block 的bloom filter bitmap非常方便:

bool FilterBlockReader::KeyMayMatch(uint64_t block_offset, const Slice& key) {
  uint64_t index = block_offset >> base_lg_;
  if (index < num_) {
    uint32_t start = DecodeFixed32(offset_ + index*4);
    uint32_t limit = DecodeFixed32(offset_ + index*4 + 4);
    if (start <= limit && limit <= static_cast<size_t>(offset_ - data_)) {
      Slice filter = Slice(data_ + start, limit - start);
      return policy_->KeyMayMatch(key, filter);
    } else if (start == limit) {
      // Empty filters do not match any keys
      return false;
    }
  }
  return true;  // Errors are treated as potential matches
}

按照上面的分析,如果block_offset为6KB的时候,就会找不到对应位图,因为 start和limit指向的都是bitmap 1,函数中的filter最终为空,但是没关系,绝不会传进来6K,因为6K不是两个data block的边界。

meta data的在SSTable File中的布局

TableBuilder::Finish函数中会将Filter Block落盘:

Status TableBuilder::Finish() {
  Rep* r = rep_;
  Flush();
  assert(!r->closed);
  r->closed = true;

  BlockHandle filter_block_handle, metaindex_block_handle, index_block_handle;

  // Write filter block
  if (ok() && r->filter_block != NULL) {
  
  /*将filter block写入磁盘*/
    WriteRawBlock(r->filter_block->Finish(), kNoCompression,
                  &filter_block_handle);
  }
    
  // Write metaindex block
  if (ok()) {
    BlockBuilder meta_index_block(&r->options);
    if (r->filter_block != NULL) {
      // Add mapping from "filter.Name" to location of filter data
      std::string key = "filter.";
      key.append(r->options.filter_policy->Name());
      std::string handle_encoding;
      filter_block_handle.EncodeTo(&handle_encoding);
      meta_index_block.Add(key, handle_encoding);
    }

    // TODO(postrelease): Add stats and other meta blocks
    WriteBlock(&meta_index_block, &metaindex_block_handle);
  }

Slice FilterBlockBuilder::Finish() {
  if (!start_.empty()) {
    GenerateFilter();
  }

  // Append array of per-filter offsets
  const uint32_t array_offset = 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_);
}

布局的方式如下图所示:

最后,metaindex_block 比较简单,格式和data block一模一样,只有一个key-value对,其中key值是filter.leveldb.BuiltinBloomFilter2, 而value,即meta data 所在的 BlockHandler,即位置信息。

也就说,metaindex_block 可以定位到 meta data的位置信息,即上图。


上一篇     下一篇