本文共 4215 字，大约阅读时间需要 14 分钟。
前面我们分析了leveldb中的index block和data block。这里主要是分析filter block。filter block属于一种metadata block，它的构造主要由FilterBlockBuilder完成。filter block的作用就是提供快速判断一个key是否存在于某个datablock中，以加速查找的过滤器。
回忆在分析TableBuilder的Add函数时，每次向sstable中添加一个key-value，都会执行
if (r->filter_block != NULL) { r->filter_block->AddKey(key); } 以将key加入到filter block中。从判断语句我们也可以看到，filter block是可选项，不是必须要有的。
而且每写完一个data block，并在TableBuilder中的Flush函数中将data block写盘时，都会执行
if (r->filter_block != NULL) { r->filter_block->StartBlock(r->offset); } 而且在写完整个sstable时，还会在TableBuilder.Finish函数中执行以下代码
if (ok() && r->filter_block != NULL) { WriteRawBlock(r->filter_block->Finish(), kNoCompression, &filter_block_handle); } 当然，这里的Finish函数，根据前面的分析可以知道，它返回一个字符串，供TableBuilder写盘。本文的主要重点就是这个字符串是怎么生成的，它具有什么样的格式。
所以我们可以看出构建filter block的核心函数是Addkey，Startblock，Finish。下面我们将逐个分析这些函数的源代码
FilterBlockBuilder.AddKey函数
void FilterBlockBuilder::AddKey(const Slice& key) { Slice k = key; start_.push_back(keys_.size()); keys_.append(k.data(), k.size());} 这里面的keys就是一个字符串，start_是一个整形数组。所以加入一个key就是把这个key append到keys字符串中，在此之前记录该字符串未加入key时的长度。这里的keys和start_都是类成员数据。
FilterBlockBuilder::StartBlock函数
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(); }} 其中kFilterBase是2的11次方，表示2kb。
block_offset是data block在sstable中的偏移位置。这个看TableBuilder.Flush函数就可以清楚知道。所以从计算filter index我们可以看到：
并不是每个data block严格对应filter block中的一项。我们可以理解为对于filter i，它对应block offset在[i*2kb ~ (i+1)*2kb]中的所有block的key，所以可能有多个block下面我们看一下GenerateFilter函数：
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; } 前面我们讲过start_中存储的是keys的长度，每次向keys字符串中新加入一个key就更新以下start_中当前keys的长度，我们可以用下图形象表示：
start_.push_back(keys_.size()); // Simplify length computation 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); } 理解了上面的keys和start_，我们就可以很好理解这部分的代码了。无非就是将keys中的key分别放入tmp_keys_数组中。我们的filter就是根据这些key生成的。
filter_offsets_.push_back(result_.size()); policy_->CreateFilter(&tmp_keys_[0], static_cast (num_keys), &result_);
这就是生成过滤器的算法了。leveldb中提供了几种生成过滤器的算法，我们这里不深究。只需要看到，CreateFilter函数根据tmp_keys_生成一个过滤器，过滤器就是一个字符串，并将过滤器append到result中。所以result具有如下形式：
tmp_keys_.clear(); keys_.clear(); start_.clear();
最后面就是收尾了，从start_clear()和keys.clear()我们可以看到，每个filter所用的key都不会有重叠。
综上，start_block函数本质上就是根据keys_中的key生成一个filter，filter是一个字符串，并将这个filter拼接到result中。所以，所有的filter都会在result中，filter_offsets_数组则是记录各个filter在result中的偏移量。比如filter[i]在result中的偏移量为filter_offsets_[i]，它对应的是所有block offset在[i*2kb ~ (i+1)*2kb]中的block包含的key。
FilterBlockBuilder::Finish
Finish函数和其他block一样，将会返回一个string给上层的TableBuilder，供TableBuilder写入磁盘。这里看一下filter block所代表的字符串是什么样子的
Slice FilterBlockBuilder::Finish() { if (!start_.empty()) { GenerateFilter(); } 如果start_不是空，则再为结尾这些残余key生成一个filter。
const uint32_t array_offset = result_.size(); for (size_t i = 0; i < filter_offsets_.size(); i++) { PutFixed32(&result_, filter_offsets_[i]); } 这里将filter_offsets_数组中的每一项拼接到filter数组result_中。
PutFixed32(&result_, array_offset); result_.push_back(kFilterBaseLg); // Save encoding parameter in result, void push_back (char c); return Slice(result_);
这里将这个filter block包含的所有filter的总字节数(array_offset)拼接到result中，通过它可以找到offset数组在filter block中的偏移位置。最后把kFilterBaseLg参数拼接进去，前面我们经常看到的2kb就是通过这个参数计算来的，我们可以通过改变这个参数来调节每个filter 对应的block offset区间。
最后即使返回result字符串供TableBuilder写盘了。
综上我们可以看到filter block的空间布局如下所示：
总结
filter block中的filter i对应block offset在｛i*2kb ~ (i+1)*2kb｝中的所有block包含的key。通过这个filter我们可以快速判断给定的一个key是否在这些block中。从filter block的组织中，可以知道，我们可以通过offset of filter array找到filter的偏移数组，通过这些偏移数组，我们可以找到具体的filter。本文没有介绍具体的filter生成算法，我们只简单地认为一个生成过滤器的算法将为一组key生成一个字符串。后面有机会再介绍，比如布隆过滤器等，还是挺有趣的。