LevelDB 的 table 文件以 .ldb 作為文件擴(kuò)展名颜说，包括若干個 block，data block 存儲按照 key 的字母表順序排序的 KV 對數(shù)據(jù)俗孝，meta block 存儲 filter 數(shù)據(jù)晃危，metaindex block 存儲 每個 meta block 的 offset 信息，index block 存儲每個 data block 的 offset 信息奕锌。對于 data block，引入了前綴壓縮技術(shù)減少磁盤空間占用村生。本文結(jié)合 LevelDB 代碼，探討 .ldb 文件的 data block key 前綴壓縮方法饼丘。
<beginning_of_file>
[data block 1]
[data block 2]
...
[data block N]
[meta block 1]
...
[meta block K]
[metaindex block]
[index block]
[Footer] (fixed size; starts at file_size - sizeof(Footer))
<end_of_file>
對于排序后的 KV 對趁桃，相鄰的 key 通常會具有相似的前綴。LevelDB 基于相鄰 key 的共享前綴對 key 進(jìn)行了壓縮肄鸽。更小的 data block 可以實現(xiàn)更快的讀取卫病，也對 page cache 更為友好。
Layout
[k1, v1] -- offset1
[k2', v2]
[k3', v3]
...
[k14', v14]
[k15', v15]
[k16, v16] -- offset2
[k17', v17]
...
[offset1, offset2, offset3, ...]
[num of restart points]
key 壓縮后的 data block 如上所示典徘，由 KV 對和 restart point 構(gòu)成蟀苛。采用類似于稀疏索引的方式，部分 KV 對記錄完整的 key逮诲，作為 restart point帜平。restart point 之間的 key 則通過共同前綴進(jìn)行壓縮幽告。在 data block 的最后，保存了各個 restart point 的 offset 以及 restart point 的數(shù)量裆甩。
Writing Flow
void BlockBuilder::Add(const Slice& key, const Slice& value) {
size_t shared = 0;
// 每16個 key 為一個 restart point冗锁，restart point 保存完整的 key
if (counter_ < options_->block_restart_interval) {
// 計算共同前綴長度
const size_t min_length = std::min(last_key_piece.size(), key.size());
while ((shared < min_length) && (last_key_piece[shared] == key[shared])) {
shared++;
}
} else {
// 記錄 restart point
restarts_.push_back(buffer_.size());
counter_ = 0;
}
const size_t non_shared = key.size() - shared;
// 寫入 KV 對
buffer_.append(key.data() + shared, non_shared);
buffer_.append(value.data(), value.size());
// 記錄 last key
last_key_.resize(shared);
last_key_.append(key.data() + shared, non_shared);
counter_++;
}
Slice BlockBuilder::Finish() {
// Append restart array
for (size_t i = 0; i < restarts_.size(); i++) {
PutFixed32(&buffer_, restarts_[i]);
}
PutFixed32(&buffer_, restarts_.size());
finished_ = true;
return Slice(buffer_);
}
data block 的生成流程如上所示，以第每16個 key 作為 restart point嗤栓，記錄完整的 key冻河。restart point 間的 key 則只在前一個 key 的基礎(chǔ)之上，記錄不同的后綴茉帅。當(dāng) block 寫入完成時叨叙，在 block 的最后追加寫入 restart point。
Reading Flow
virtual void Seek(const Slice& target) {
// 二分查找最大的 restart point堪澎，滿足 restart point key < target
uint32_t left = 0;
uint32_t right = num_restarts_ - 1;
while (left < right) {
uint32_t mid = (left + right + 1) / 2;
uint32_t region_offset = GetRestartPoint(mid);
uint32_t shared, non_shared, value_length;
const char* key_ptr =
DecodeEntry(data_ + region_offset, data_ + restarts_, &shared,
&non_shared, &value_length);
if (key_ptr == nullptr || (shared != 0)) {
CorruptionError();
return;
}
Slice mid_key(key_ptr, non_shared);
if (Compare(mid_key, target) < 0) {
left = mid;
} else {
right = mid - 1;
}
}
// 從 restart point 后的 key 開始線性搜索
SeekToRestartPoint(left);
while (true) {
if (!ParseNextKey()) {
return;
}
if (Compare(key_, target) >= 0) {
return;
}
}
}
數(shù)據(jù)的讀取摔敛，是一定需要完整的 key 進(jìn)行比較的。數(shù)據(jù)讀取流程為了避免不必要的 decode全封，先通過 restart point 進(jìn)行二分查找马昙，找到最大的 key，再進(jìn)行線性搜索刹悴。最差情況下的搜索次數(shù)為 Log(n) + 15行楞，其中 n 為 data block 中 key 的數(shù)量。
