LevelDB源碼解析19. FilterBlockBuilder
FilterBlock
這裡主要介紹的代碼，位於table/filter_block.h和table/filter_block.cc。
在本文中將不再區分filter block和meta block。
接下來將要介紹的是FilterBlock，實質上就是SST文件裡面的meta block，由於目前只有這麼一種meta block並用是用來做為filter。所以也經常被稱之為filter block。
使用方式
在查看類的內部定義之前，可以先看一下這個類是如何使用的。這將有助於理解後面FilterBlockBuilder類的含義。
TEST(FilterBlockTest, SingleChunk) {
FilterBlockBuilder builder(&policy_);
builder.StartBlock(100);
builder.AddKey("foo");
builder.AddKey("bar");
builder.AddKey("box");
builder.StartBlock(200);
builder.AddKey("box");
builder.StartBlock(300);
builder.AddKey("hello");
Slice block = builder.Finish();
FilterBlockReader reader(&policy_, block);
ASSERT_TRUE(reader.KeyMayMatch(100, "foo"));
ASSERT_TRUE(reader.KeyMayMatch(100, "bar"));
ASSERT_TRUE(reader.KeyMayMatch(100, "box"));
ASSERT_TRUE(reader.KeyMayMatch(100, "hello"));
ASSERT_TRUE(reader.KeyMayMatch(100, "foo"));
ASSERT_TRUE(! reader.KeyMayMatch(100, "missing"));
ASSERT_TRUE(! reader.KeyMayMatch(100, "other"));
}
類的定義
// A FilterBlockBuilder is used to construct all of the filters for a
// particular Table. It generates a single string which is stored as
// a special block in the Table.
//
// The sequence of calls to FilterBlockBuilder must match the regexp:
// (StartBlock AddKey*)* Finish
class FilterBlockBuilder {
const FilterPolicy* policy_;
std::string keys_; // Flattened key contents
std::vector<size_t> start_; // Starting index in keys_ of each key
std::string result_; // Filter data computed so far
std::vector<Slice> tmp_keys_; // policy_->CreateFilter() argument
std::vector<uint32_t> filter_offsets_;
};
在LevelDB源碼裡面有很多的Builder，這些Builder的主要功能就是實現一個構建器。類似於寫者。
為什麼說是構建器，類似於寫者，而不是寫者呢？主要原因是： - 構建器操作的對象是內存。也就是把要輸出的結果按照想要的格式整理好。在內存中放置好。 - 而Writer主要是把內存裡面的內容寫入到文件裡面。
所以在看代碼的時候，需要注意：BlockBuilder也好，FilterBlockBuilder也好，或者是TableBuilder也好，實際上都是要按內存裡面指定的格式整理在內存裡面。
log_writer才是真正的把內存裡面的內容寫入到文件裡面。
keys
這裡面有很多內存變數，簡要介紹一下各個變數的作用。
policy_這裡是指向一個具體的filter_policy。keys_裡面包含了所有展開的keys。並且這些所有的keys都是存放在一起的。這個可以通過如下代碼推斷出來。
void FilterBlockBuilder::AddKey(const Slice& key) {
Slice k = key;
start_.push_back(keys_.size());
keys_.append(k.data(), k.size());
}
當添加一個key的時候，start_裡面會記錄當前這個key在keys_裡面的offset，當然，代碼處理起來比較簡單，只需要start_.push_Back(keys_.size())就可以了。
而key真正的內容只需要append在keys_裡面就可以了。所以，所有的key都是存放到keys_裡面了。
不過需要注意的是：filter block雖然只有一個，但是實際上filter block裡面卻是有很多的filter。每個filter都會利用一系列keys來生成相應的filter_的輸入。這裡filter_的輸入用的是result_來記錄所有的輸入。而filter_offsets_則是將這些隔開，並且更加容易拆分。
filter offset
除此之外，還有兩個變數，
std::vector<Slice> tmp_keys_; // policy_->CreateFilter() argument
std::vector<uint32_t> filter_offsets_;
接下來看一下這兩個變數的含義。這裡需要再次回顧一下SST文件的格式。
<beginning_of_file>
[data block 1]
[data block 2]
...
[data block N]
[meta block 1]
[meta block index]
[data block index]
[Footer]
<end_of_file>
一般而言，雖然SST文件裡面聲稱是支持多個meta block的，但是實際上，也只有一個meta block。此外，會在每當data block的大小2K的時候，開始創建一個filter。
// See doc/table_format.md for an explanation of the filter block format.
// Generate new filter every 2KB of data
static const size_t kFilterBaseLg = 11;
static const size_t kFilterBase = 1 << kFilterBaseLg;
這裡kFilterBaseLg表示的意思是對2K取2的對數，也就是得到11。那麼真正的大小kFilterBase這裡也就是2K。
那麼基於以上原因：
- 只有一個meta block
- 每
2K創建一個filter。
所以，當給定block_offset的時候。需要創建的filter的數目也就確定了。
// 注意：block_offset指的是 filter block的offset.
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();
}
}
在上面的代碼中，首先第一步是計算出所有的filter的總數。filter_index這個變數命名感覺怪怪的。我覺得應該使用filters_number更加合適。也就是說filters_number = block_offset / kFilterBase。
而filter_offsets_裡面則是記錄了當前已經生成的所有的filter的offset信息。
所以
while (filter_index > filter_offsets_.size()) {
GenerateFilter();
}
也就容易理解了。當已經生成的filter的數目小於需要生成的filter的總數時，那麼就繼續創建filter。
創建Filter
那麼GenerateFilter是如何操作的呢？這段代碼相對比較長一些。首先需要看一下result_變數。result_變數就是表示的是一個filter計算之後的輸出。比如boomfilter經過各種key計算之後，可能會得到一個filter_Str。這個filter_str就是放到result裡面。
filter_offsets_裡面的每個元素就是用來記錄每個filter內容的offset。
所以result_與filter_offsets_的關係，與keys_和start_的關係一模一樣。都是表示一段內存區域。然後用vector來記錄offset的位置。
void FilterBlockBuilder::GenerateFilter() {
// 拿到key的數目
const size_t num_keys = start_.size();
// 如果當前key數目還是0
if (num_keys == 0) {
// 如果key數目為0，這裡應該是表示要新生成一個filter
// 這時應該是重新記錄下offset了。
// 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_裡面記錄下offset
start_.push_back(keys_.size()); // Simplify length computation
// 需要多少個key呢？
tmp_keys_.resize(num_keys);
// 依次拿到每個key
for (size_t i = 0; i < num_keys; i++) {
// 這裡拿到每個key的base address.
const char* base = keys_.data() + start_[i];
// 拿到key的長度
size_t length = start_[i+1] - start_[i];
// 生成相應的key，並且放到tmp_keys裡面
tmp_keys_[i] = Slice(base, length);
}
// Generate filter for current set of keys and append to result_.
// 記錄下offset
filter_offsets_.push_back(result_.size());
// 利用tmp_keys生成輸出，並且放到result裡面。
policy_->CreateFilter(&tmp_keys_[0], static_cast<int>(num_keys), &result_);
// 清空keys/start變數
tmp_keys_.clear();
keys_.clear();
start_.clear();
}
Finish
在看Finish函數之前，需要再看一下Filter block的結構：
Slice FilterBlockBuilder::Finish() {
// 如果還有key，那麼把剩下的key用來生成filter
if (!start_.empty()) {
GenerateFilter();
}
// Append array of per-filter offsets
// 處理所有的filter
// 將offset進行編碼
const uint32_t array_offset = result_.size();
for (size_t i = 0; i < filter_offsets_.size(); i++) {
PutFixed32(&result_, filter_offsets_[i]);
}
// 將filter的總數也進行編碼
PutFixed32(&result_, array_offset);
// 把lg參數也進行編碼
result_.push_back(kFilterBaseLg); // Save encoding parameter in result
// 返回整個result_內存結果
return Slice(result_);
}
FilterReader
有了前面代碼，那麼再看一下FilterReader的代碼就特別容易看懂了。這裡放上函數的注釋。
FilterBlockReader::FilterBlockReader(const FilterPolicy* policy,
const Slice& contents)
: policy_(policy),
data_(nullptr),
offset_(nullptr),
num_(0),
base_lg_(0) {
// 注意這裡的contents只是用於filter block的內容。
// 並不包含其他block的內容。
size_t n = contents.size();
if (n < 5) return; // 1 byte for base_lg_ and 4 for start of offset array
base_lg_ = contents[n-1];
// 這裡實際上取出了filter的offset
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;
}
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);
// 當前這個filter的limit肯定是下一個filter的開頭位置
uint32_t limit = DecodeFixed32(offset_ + index*4 + 4);
// 必須要保證limit也是合法的
if (start <= limit && limit <= static_cast<size_t>(offset_ - data_)) {
// 在合法的情況下，取出filter
Slice filter = Slice(data_ + start, limit - start);
// Slice filter實際上可以看成是數據的輸入部分
return policy_->KeyMayMatch(key, filter);
} else if (start == limit) {
// 如果這個filter是空的，那麼直接返回不存在
// 多半的原因是這段內存裡面沒有key
// Empty filters do not match any keys
return false;
}
}
// 出錯的時候，返回有可能存在
return true; // Errors are treated as potential matches
}
推薦閱讀：
