leveldb 源码分析 13¶

本系列《leveldb 源码分析》共有 22 篇文章，这是第十三篇

8.FilterPolicy&Bloom 之二¶

8.5.1 FilterBlockBuilder¶

了解了 filter 机制，现在来看看 filter block 的构建，这就是类 FilterBlockBuilder。它为指定的 table 构建所有的 filter，结果是一个 string 字符串，并作为一个 block 存放在 table 中。它有三个函数接口：

// 开始构建新的filter block，TableBuilder在构造函数和Flush中调用  

void StartBlock(uint64_tblock_offset);  

// 添加key，TableBuilder每次向data block中加入key时调用  

void AddKey(const Slice&key);  

// 结束构建，TableBuilder在结束对table的构建时调用  

Slice Finish();

FilterBlockBuilder 的构建顺序 必须满足如下范式：(StartBlock AddKey*)* Finish，显然这和前面讲过的 BlockBuilder 有所不同。其成员变量有：

const FilterPolicy* policy_; // filter类型，构造函数参数指定  

std::string keys_;          //Flattened key contents  

std::vector<size_t> start_; // 各key在keys_中的位置  

std::string result_;        // 当前计算出的filter data  

std::vector<uint32_t>filter_offsets_; // 各个filter在result_中的位置  

std::vector<Slice> tmp_keys_;// policy_->CreateFilter()参数

前面说过 base 是 2KB，这对应两个常量 kFilterBase =11, kFilterBase =(1<<kFilterBaseLg)； 其实从后面的实现来看 tmp_keys_ 完全不必作为成员变量，直接作为函数 GenerateFilter() 的栈变量就可以。下面就分别分析三个函数接口。

8.5.2 FilterBlockBuilder::StartBlock()¶

它根据参数 block_offset 计算出 filter index，然后循环调用 GenerateFilter 生产新的 Filter。

uint64_t filter_index =(block_offset / kFilterBase);  

assert(filter_index >=filter_offsets_.size());  

while (filter_index >filter_offsets_.size()) GenerateFilter();

我们来到 GenerateFilter 这个函数，看看它的逻辑。

//S1 如果filter中key个数为0，则直接压入result_.size()并返回  

  const size_t num_keys =start_.size();  

  if (num_keys == 0) { // there are no keys for this filter  

    filter_offsets_.push_back(result_.size()); //result_.size()应该是0  

    return;  

  }  

//S2 从key创建临时key list，根据key的序列字符串kyes_和各key在keys_
//中的开始位置start_依次提取出key。  

  start_.push_back(keys_.size());  // Simplify lengthcomputation  

  tmp_keys_.resize(num_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);  

  }  

//S3 为当前的key集合生产filter，并append到result_  

filter_offsets_.push_back(result_.size());  

policy_->CreateFilter(&tmp_keys_[0], num_keys, &result_);  

//S4 清空，重置状态  

tmp_keys_.clear();  

keys_.clear();  

start_.clear();

8.5.3 FilterBlockBuilder::AddKey()¶

这个接口很简单，就是把 key 添加到 key_ 中，并在 start_ 中记录位置。

Slice k = key;  

start_.push_back(keys_.size());  

keys_.append(k.data(),k.size());

8.5.4 FilterBlockBuilder::Finish()¶

调用这个函数说明整个 table 的 data block 已经构建完了，可以生产最终的 filter block 了，在 TableBuilder::Finish 函数中被调用，向 sstable 写入 meta block。函数逻辑为：

//S1 如果start_数字不空，把为的key列表生产filter  

  if (!start_.empty()) GenerateFilter();  

//S2 从0开始顺序存储各filter的偏移值，见filter block data的数据格式。  

  const uint32_t array_offset =result_.size();  

  for (size_t i = 0; i < filter_offsets_.size();i++) {  

    PutFixed32(&result_,filter_offsets_[i]);  

  }  

//S3 最后是filter个数，和shift常量（11），并返回结果  

  PutFixed32(&result_,array_offset);  

  result_.push_back(kFilterBaseLg);  // Save encoding parameter in result  

  return Slice(result_);

8.5.5 简单示例¶

让我们根据 TableBuilder 对 FilterBlockBuilder 接口的调用范式： (StartBlock AddKey) Finish 以及上面的函数实现，结合一个简单例子看看 leveldb 是如何为 data block 创建 filter block（也就是 meta block）的。 考虑两个 datablock，在 sstable 的范围分别是：Block 1 [0, 7KB-1], Block 2 [7KB, 14.1KB]

S1 首先 TableBuilder 为 Block 1 调用 FilterBlockBuilder::StartBlock(0)，该函数直接返回；
S2 然后依次向 Block 1 加入 k/v，其中会调用 FilterBlockBuilder::AddKey，FilterBlockBuilder 记录这些 key。
S3 下一次 TableBuilder 添加 k/v 时，例行检查发现 Block 1 的大小超过设置，则执行 Flush 操作，Flush 操作在写入 Block 1 后，开始准备 Block 2 并更新 block offset=7KB，最后调用 FilterBlockBuilder::StartBlock(7KB)，开始为 Block 2 构建 Filter。
S4 在 FilterBlockBuilder::StartBlock(7KB) 中，计算出 filter index = 3，触发 3 次 GenerateFilter 函数，为 Block 1 添加的那些 key 列表创建 filter，其中第 2、3 次循环创建的是空 filter。此时 filter 的结构如图 8.5-1 所示。

图 8.5-1

在 StartBlock(7KB) 时会向 filter 的偏移数组 filter_offsets_ 压入两个包含空 key set 的元素，filter_offsets_[1] 和 filter_offsets_[2]，它们的值都等于 7KB-1。
S5Block 2 构建结束，TableBuilder 调用 Finish 结束 table 的构建，这会再次触发 Flush 操作，在写入 Block 2 后，为 Block 2 的 key 创建 filter。最终的 filter 如图 8.5-2 所示。

图 8.5-2
这里如果 Block 1 的范围是 [0, 1.8KB-1]，Block 2 从 1.8KB 开始，那么 Block 2 将会和 Block 1 共用一个 filter，它们的 filter 都被生成到 filter 0 中。当然在 TableBuilder 构建表时，Block 的大小是根据参数配置的，也是基本均匀的。

8.6.1 FilterBlockReader¶

FilterBlock 的读取操作在 FilterBlockReader 类中，它的主要功能是根据传入的 FilterPolicy 和 filter，进行 key 的匹配查找。它有如下的几个成员变量：

const FilterPolicy* policy_; // filter策略  

const char* data_;           // filter data指针 (at block-start)  

const char* offset_;        // offset array的开始地址 (at block-end)  

size_t num_;                // offsetarray元素个数  

size_t base_lg_;            // 还记得kFilterBaseLg吗

Filter 策略和 filter block 内容都由构造函数传入。一个接口函数，就是 key 的批判查找：

bool KeyMayMatch(uint64_t block_offset, const Slice& key);

8.6.2 构造¶

在构造函数中，根据存储格式解析出偏移数组开始指针、个数等信息。

FilterBlockReader::FilterBlockReader(const FilterPolicy* policy, 
                                     constSlice& contents)  

    : policy_(policy),data_(NULL), offset_(NULL), num_(0), base_lg_(0) {  

  size_t n = contents.size();  

  if (n < 5) return;  // 1 byte forbase_lg_ and 4 for start of offset array  

  base_lg_ = contents[n-1]; // 最后1byte存的是base  

  uint32_t last_word =DecodeFixed32(contents.data() + n - 5); //偏移数组的位置  

  if (last_word > n - 5)return;  

  data_ = contents.data();  

  offset_ = data_ + last_word; // 偏移数组开始指针  

  num_ = (n - 5 - last_word) / 4; // 计算出filter个数

8.6.3 查找¶

查找函数传入两个参数

@block_offset 是查找 data block 在 sstable 中的偏移，Filter 根据此偏移计算 filter 的编号；
@key 是查找的 key。声明如下： bool FilterBlockReader::KeyMayMatch(uint64_t block_offset, constSlice& key) 它首先计算出 filterindex，根据index 解析出 filter 的 range，如果是合法的 range，就从 data_ 中取出 filter，调用 policy_ 做 key 的匹配查询。函数实现：

uint64_t index = block_offset>> base_lg_; // 计算出filter index  

if (index < num_) {  
  // 解析出filter的range  
  uint32_t start =DecodeFixed32(offset_ + index*4);

  uint32_t limit =DecodeFixed32(offset_ + index*4 + 4);  

  if (start <= limit&& limit <= (offset_ - data_)) {  

    Slice filter = Slice(data_ +start, limit - start); // 根据range得到filter  

    returnpolicy_->KeyMayMatch(key, filter);  

  } else if (start == limit) {  

    return false;  // 空filter不匹配任何key  

  }  

}  

return true; // 当匹配处理

至此，FilterPolicy 和 Bloom 就分析完了。