上一篇结尾，MemTable 积攒了足够多的 key-value 后，按 key 有序遍历、写入磁盘——这个磁盘文件就是 SSTable（Sorted String Table）。
但”写到磁盘”这四个字藏着一连串工程问题：
- 一个 SSTable 可能有几十 MB。不可能读整个文件来找一个 key；需要某种 索引。
- key 是有序的，相邻 key 往往共享很长的前缀（比如
user:10001和user:10002）。直接存很浪费；需要 前缀压缩。 - 即使有索引，每次
Get()仍然要读一次磁盘。如果 key 根本不在这个 SSTable 里，这次 I/O 就白做了；需要一个能在内存中快速判定”一定不存在”的结构——Bloom Filter。
本文是系列第 3 篇。目标：从零实现 Data Block、Bloom Filter、SSTable Builder 和 Reader，给出可编译的 C 代码。
前文回顾： 第 1 篇 建立了 LSM-Tree 的全景地图；第 2 篇 实现了 WAL 和 MemTable。本文接手 MemTable flush 之后的工作。
Data Block：前缀压缩与二分查找
为什么需要 Block
SSTable 是一个几十 MB 的文件，不可能一次读进内存。LevelDB 把文件切成了若干固定大小的 Block（默认 4KB），每个 Block 独立压缩、独立校验。读取时按需加载一个 Block，既省内存又方便缓存。
存放 key-value 数据的叫 Data Block。除此之外还有 Index Block、MetaIndex Block 等辅助 Block，它们与 Data Block 共享相同的 entry + restart array 格式。唯一的例外是 Meta Block（Bloom Filter），它采用自定义格式（bit 数组 + k 值），不使用通用的 entry/restart 结构。
Entry 格式
Data Block 里的每条记录叫一个 Entry。key 是有序的，相邻 key 往往共享前缀，所以每条 Entry 只存与前一条不同的后缀：
+--------------+----------------+-----------+-----------+-------+
| shared_bytes | unshared_bytes | value_len | key_delta | value |
+--------------+----------------+-----------+-----------+-------+
varint32 varint32 varint32 [unshared] [value_len]- shared_bytes：当前 key 与前一个 key 共享的前缀长度。
- unshared_bytes：当前 key 独有的后缀长度。
- key_delta：后缀的原始字节（
unshared_bytes字节）。 - value_len / value：value 的长度和内容。
完整 key = 前一个 key 的前 shared_bytes 字节
+ key_delta。
Restart Point
前缀压缩有个问题：要解码第 N 条 Entry，必须从头链式还原所有前缀。随机访问代价太高。
LevelDB 的解法是 restart point：每隔
restart_interval（默认 16）条 Entry，强制
shared_bytes = 0，把完整 key
存一遍。这些位置就是 restart point，记录在 Block 末尾的
restart array 里：
[Entry 0 ... Entry N-1] [restart[0] ... restart[M-1]] [M]
← 每个 uint32 → uint32查找时：先对 restart array 做 二分查找，定位到最近的 restart point，再从那里线性扫描几条。总比较次数 \(O(\log M + R)\)，其中 \(R\) 是 restart 间隔（16），\(M\) 是 restart 数量。
Block Trailer
每个 Block 写完数据后，紧跟 5 字节 trailer：
| 字段 | 大小 | 含义 |
|---|---|---|
| compression_type | 1 字节 | 压缩类型（0 = 不压缩，1 = Snappy） |
| CRC32 | 4 字节 | 覆盖 block 数据 + compression_type |
本文简化处理：始终不压缩（compression_type = 0）。
Varint 编码
Block 内的长度字段用 varint 编码——小数值只占 1 字节，大数值最多 5 字节（varint32）或 10 字节（varint64）。编码规则：每字节低 7 位存数据，最高位为 1 表示”后面还有字节”：
// 编码 varint32，返回写入的字节数
static int encode_varint32(uint8_t *buf, uint32_t v) {
int n = 0;
while (v >= 0x80) {
buf[n++] = (uint8_t)(v | 0x80);
v >>= 7;
}
buf[n++] = (uint8_t)v;
return n;
}
// 解码 varint32，返回消耗的字节数，value 写入 *out
static int decode_varint32(const uint8_t *buf, size_t limit, uint32_t *out) {
uint32_t result = 0;
int shift = 0;
for (size_t i = 0; i < limit && i < 5; i++) {
uint32_t b = buf[i];
result |= (b & 0x7F) << shift;
if (!(b & 0x80)) {
*out = result;
return (int)(i + 1);
}
shift += 7;
}
return -1; // 编码错误
}
// varint64 版本（用于 BlockHandle 编码）
static int encode_varint64(uint8_t *buf, uint64_t v) {
int n = 0;
while (v >= 0x80) {
buf[n++] = (uint8_t)(v | 0x80);
v >>= 7;
}
buf[n++] = (uint8_t)v;
return n;
}
static int decode_varint64(const uint8_t *buf, size_t limit, uint64_t *out) {
uint64_t result = 0;
int shift = 0;
for (size_t i = 0; i < limit && i < 10; i++) {
uint64_t b = buf[i];
result |= (b & 0x7F) << shift;
if (!(b & 0x80)) {
*out = result;
return (int)(i + 1);
}
shift += 7;
}
return -1;
}BlockBuilder
BlockBuilder 负责把一系列有序 key-value
攒成一个 Block：
#define BLOCK_SIZE 4096 // 目标 block 大小
#define RESTART_INTERVAL 16 // 每 16 条一个 restart point
typedef struct {
uint8_t *data; // 动态 buffer
size_t size; // 当前已写入字节数
size_t cap; // buffer 容量
uint32_t *restarts; // restart 偏移量数组
int num_restarts;
int restart_cap;
char last_key[256]; // 上一个 key（用于计算共享前缀）
int last_key_len;
int entry_count; // 当前 restart 区间内的 entry 计数
} BlockBuilder;
static void block_builder_init(BlockBuilder *bb) {
bb->cap = BLOCK_SIZE * 2;
bb->data = malloc(bb->cap);
bb->size = 0;
bb->restart_cap = 64;
bb->restarts = malloc(bb->restart_cap * sizeof(uint32_t));
bb->num_restarts = 0;
bb->last_key_len = 0;
bb->entry_count = 0;
}
static void block_builder_free(BlockBuilder *bb) {
free(bb->data);
free(bb->restarts);
}
// 确保 buffer 有足够空间
static void bb_ensure(BlockBuilder *bb, size_t need) {
while (bb->size + need > bb->cap) {
bb->cap *= 2;
bb->data = realloc(bb->data, bb->cap);
}
}
static void block_builder_add(BlockBuilder *bb,
const char *key, size_t key_len,
const char *val, size_t val_len) {
int shared = 0;
if (bb->entry_count < RESTART_INTERVAL) {
// 计算共享前缀长度
int min_len = (bb->last_key_len < (int)key_len)
? bb->last_key_len : (int)key_len;
while (shared < min_len && bb->last_key[shared] == key[shared])
shared++;
} else {
// 新的 restart point
if (bb->num_restarts >= bb->restart_cap) {
bb->restart_cap *= 2;
bb->restarts = realloc(bb->restarts,
bb->restart_cap * sizeof(uint32_t));
}
bb->restarts[bb->num_restarts++] = (uint32_t)bb->size;
bb->entry_count = 0;
shared = 0;
}
// 第一条 entry 也是 restart point
if (bb->size == 0 && bb->num_restarts == 0) {
bb->restarts[bb->num_restarts++] = 0;
}
int unshared = (int)key_len - shared;
// 编码 entry
uint8_t hdr[15]; // 3 个 varint32 最多 15 字节
int n = 0;
n += encode_varint32(hdr + n, (uint32_t)shared);
n += encode_varint32(hdr + n, (uint32_t)unshared);
n += encode_varint32(hdr + n, (uint32_t)val_len);
bb_ensure(bb, n + unshared + val_len);
memcpy(bb->data + bb->size, hdr, n); bb->size += n;
memcpy(bb->data + bb->size, key + shared, unshared); bb->size += unshared;
memcpy(bb->data + bb->size, val, val_len); bb->size += val_len;
// 记录 last_key
memcpy(bb->last_key, key, key_len);
bb->last_key_len = (int)key_len;
bb->entry_count++;
}
// 完成 Block：追加 restart array 和 num_restarts
static void block_builder_finish(BlockBuilder *bb) {
bb_ensure(bb, bb->num_restarts * 4 + 4);
for (int i = 0; i < bb->num_restarts; i++) {
uint32_t r = bb->restarts[i];
memcpy(bb->data + bb->size, &r, 4); // little-endian（x86 原生）
bb->size += 4;
}
uint32_t nr = (uint32_t)bb->num_restarts;
memcpy(bb->data + bb->size, &nr, 4);
bb->size += 4;
}block_builder_add 是热路径——SSTable Builder
每写一个 key-value 就调用一次。它只做前缀比较、varint 编码和
memcpy，没有任何 I/O。
Block 内查找
读取时，先定位到某个 Block，然后在 Block 内查找目标 key。流程分两步：
- 二分查找 restart array：把每个 restart offset 解码出完整 key，找到最后一个 ≤ 目标 key 的 restart point。
- 线性扫描：从该 restart point 向后逐条解码 Entry，比对 key。
// 解码一条 Entry，返回消耗的字节数
// 完整 key 写入 key_buf，长度写入 *full_key_len
static int decode_entry(const uint8_t *data, size_t data_size, size_t offset,
const char *prev_key, int prev_key_len,
char *key_buf, int *full_key_len,
const char **val_out, int *val_len_out) {
const uint8_t *p = data + offset;
size_t remain = data_size - offset;
uint32_t shared, unshared, vlen;
int n1 = decode_varint32(p, remain, &shared);
if (n1 < 0) return -1;
int n2 = decode_varint32(p + n1, remain - n1, &unshared);
if (n2 < 0) return -1;
int n3 = decode_varint32(p + n1 + n2, remain - n1 - n2, &vlen);
if (n3 < 0) return -1;
int hdr_len = n1 + n2 + n3;
if (offset + hdr_len + unshared + vlen > data_size) return -1;
// 还原完整 key
memcpy(key_buf, prev_key, shared);
memcpy(key_buf + shared, p + hdr_len, unshared);
*full_key_len = (int)(shared + unshared);
*val_out = (const char *)(p + hdr_len + unshared);
*val_len_out = (int)vlen;
return hdr_len + (int)unshared + (int)vlen;
}
// 在 Block 内查找 target_key
// 找到返回 0 并设置 val_out/val_len_out，未找到返回 -1
static int block_search(const uint8_t *block_data, size_t block_size,
const char *target, size_t target_len,
const char **val_out, int *val_len_out) {
// 读取 restart array
if (block_size < 4) return -1;
uint32_t num_restarts;
memcpy(&num_restarts, block_data + block_size - 4, 4);
size_t restarts_offset = block_size - 4 - num_restarts * 4;
// 二分查找 restart array
int left = 0, right = (int)num_restarts - 1;
int best = 0;
while (left <= right) {
int mid = left + (right - left) / 2;
uint32_t offset;
memcpy(&offset, block_data + restarts_offset + mid * 4, 4);
// restart point 的 shared_bytes = 0，直接解码
char key_buf[256];
int key_len;
const char *v; int vl;
if (decode_entry(block_data, restarts_offset, offset,
"", 0, key_buf, &key_len, &v, &vl) < 0)
return -1;
int cmp = memcmp(key_buf, target,
(size_t)key_len < target_len ? key_len : target_len);
if (cmp == 0)
cmp = key_len - (int)target_len;
if (cmp <= 0) {
best = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
// 从 best restart point 开始线性扫描
uint32_t offset;
memcpy(&offset, block_data + restarts_offset + best * 4, 4);
char prev_key[256] = {0};
int prev_key_len = 0;
while (offset < restarts_offset) {
char key_buf[256];
int key_len;
const char *v; int vl;
int consumed = decode_entry(block_data, restarts_offset, offset,
prev_key, prev_key_len,
key_buf, &key_len, &v, &vl);
if (consumed < 0) return -1;
int cmp = memcmp(key_buf, target,
(size_t)key_len < target_len ? key_len : target_len);
if (cmp == 0)
cmp = key_len - (int)target_len;
if (cmp == 0) {
*val_out = v;
*val_len_out = vl;
return 0;
}
if (cmp > 0) return -1; // 已经超过目标，不存在
memcpy(prev_key, key_buf, key_len);
prev_key_len = key_len;
offset += consumed;
}
return -1;
}整个 Block 查找没有堆分配，key buffer 放在栈上。对一个 4KB Block（约 50-100 条 Entry），二分缩小到 restart 区间（~16 条），再线性扫描十几条即可。
Bloom Filter：用概率换磁盘 I/O
问题：无效 I/O
一次 Get("user:9999")，如果这个 key 不在当前
SSTable 里，我们仍然要读一个 Data Block
才能确认”不存在”——一次无效的磁盘随机读。LSM-Tree
可能有几十个 SSTable（从 Level 0 到 Level
6），最坏情况每层都要读一次。
Bloom Filter 在内存中用一个固定大小的 bit 数组，提供这样的保证：
- 说不在，就一定不在（零假阴性）。
- 说在，有约 1% 的概率是”骗你的”（假阳性）。
一次内存中的位运算就能跳过整个 SSTable 的磁盘读取，性价比极高。
数学基础
设 \(n\) 个 key，bit 数组长 \(m\) bits，使用 \(k\) 个独立哈希函数。误判率（false positive rate）近似为：
\[ f \approx \left(1 - e^{-kn/m}\right)^k \]
给定 bits-per-key \(b = m/n\)，最优 \(k\) 为：
\[ k^* = b \cdot \ln 2 \approx 0.693 \cdot b \]
LevelDB 默认 \(b = 10\)，代入得 \(k = \lfloor 10 \times 0.693 \rfloor = 6\)。源码故意向下取整——减少一次探测可降低计算开销，而对误判率的影响很小（\(k=6\) 时约 0.84%，\(k=7\) 时约 0.82%）。
详细的公式推导可参考这篇文章。
双重哈希技巧
Bloom Filter 需要 \(k\) 个独立哈希函数。LevelDB 没有真的算 \(k\) 次哈希，而是用一次哈希 \(h\) 生成 \(k\) 个探测位置：
\[ h_i = h_1 + i \cdot \delta \pmod{m}, \quad \delta = (h \gg 17) \mid (h \ll 15) \]
这是 Kirsch & Mitzenmacher（2004）的双重哈希方案：只需一次哈希计算，误判率与 \(k\) 个独立哈希相当。
实现
// LevelDB 的 BloomHash（基于 murmurhash 变体）
static uint32_t bloom_hash(const char *data, size_t n) {
uint32_t h = 0;
const uint32_t seed = 0xbc9f1d34;
const uint32_t m = 0xc6a4a793;
h = seed ^ ((uint32_t)n * m);
const uint8_t *p = (const uint8_t *)data;
while (n >= 4) {
uint32_t w;
memcpy(&w, p, 4); // little-endian
h += w;
h *= m;
h ^= (h >> 16);
p += 4;
n -= 4;
}
switch (n) {
case 3: h += (uint32_t)p[2] << 16; // fallthrough
case 2: h += (uint32_t)p[1] << 8; // fallthrough
case 1: h += (uint32_t)p[0]; h *= m; h ^= (h >> 24);
}
return h;
}
typedef struct {
uint8_t *bits; // bit 数组
size_t num_bits; // bit 数量（8 的倍数）
int k; // 哈希函数个数
} BloomFilter;
// 创建 Bloom Filter：给定 key 数组，生成 bit 数组
static void bloom_create(BloomFilter *bf,
const char **keys, const size_t *key_lens, int n,
int bits_per_key) {
// 计算最优 k
int k = (int)(bits_per_key * 0.69); // ln2 ≈ 0.693
if (k < 1) k = 1;
if (k > 30) k = 30;
bf->k = k;
// 分配 bit 数组（向上取整到 8 的倍数，至少 64 bits）
size_t num_bits = (size_t)n * bits_per_key;
if (num_bits < 64) num_bits = 64;
num_bits = (num_bits + 7) & ~(size_t)7; // 对齐到字节
bf->num_bits = num_bits;
size_t num_bytes = num_bits / 8;
bf->bits = calloc(num_bytes, 1);
// 插入每个 key
for (int i = 0; i < n; i++) {
uint32_t h = bloom_hash(keys[i], key_lens[i]);
uint32_t delta = (h >> 17) | (h << 15);
for (int j = 0; j < k; j++) {
uint32_t bit_pos = h % (uint32_t)num_bits;
bf->bits[bit_pos / 8] |= (1 << (bit_pos % 8));
h += delta;
}
}
}
// 查询：返回 1 表示"可能存在"，0 表示"一定不存在"
static int bloom_may_match(const BloomFilter *bf,
const char *key, size_t key_len) {
uint32_t h = bloom_hash(key, key_len);
uint32_t delta = (h >> 17) | (h << 15);
for (int j = 0; j < bf->k; j++) {
uint32_t bit_pos = h % (uint32_t)bf->num_bits;
if (!(bf->bits[bit_pos / 8] & (1 << (bit_pos % 8)))) {
return 0; // 一定不存在
}
h += delta;
}
return 1; // 可能存在
}关键点：bloom_create 的循环里，每个 key
只调用一次 bloom_hash，后续 \(k-1\) 次探测只需
h += delta——一条加法指令。整个 Bloom Filter
的构建和查询都没有分支预测失败的热点。
SSTable 文件格式
整体布局
一个 SSTable 文件从前到后包含以下部分：
| 区域 | 内容 | 说明 |
|---|---|---|
| Data Block 0..N | 有序 key-value | 每个 block 后跟 5 字节 trailer |
| Meta Block | Bloom Filter 数据 | bit 数组 + k 值 |
| MetaIndex Block | "filter.bloom" → BlockHandle |
指向 Meta Block 的位置 |
| Index Block | 每个 Data Block 一条索引 | separator_key → BlockHandle |
| Footer | 48 字节 | 指向 MetaIndex 和 Index Block |
BlockHandle
BlockHandle 是 SSTable 内部的指针，编码为两个 varint64：
typedef struct {
uint64_t offset; // block 在文件中的偏移
uint64_t size; // block 数据部分的大小（不含 5 字节 trailer）
} BlockHandle;
// 编码 BlockHandle，返回写入字节数
static int encode_block_handle(uint8_t *buf, const BlockHandle *h) {
int n = 0;
n += encode_varint64(buf + n, h->offset);
n += encode_varint64(buf + n, h->size);
return n;
}
// 解码 BlockHandle，返回消耗字节数
static int decode_block_handle(const uint8_t *buf, size_t limit,
BlockHandle *h) {
int n1 = decode_varint64(buf, limit, &h->offset);
if (n1 < 0) return -1;
int n2 = decode_varint64(buf + n1, limit - n1, &h->size);
if (n2 < 0) return -1;
return n1 + n2;
}Footer
Footer 是 SSTable 的”目录页”，固定 48 字节，位于文件末尾：
[metaindex_handle] [index_handle] [padding to 40 bytes] [magic 8 bytes]
varint64 × 2 varint64 × 2 zero-fill 0xdb4775248b80fb57读取一个 SSTable 时，首先 seek 到文件末尾
-48 字节，读出 Footer，从中拿到 Index Block 和 MetaIndex
Block 的位置。
#define FOOTER_SIZE 48
#define BLOCK_TRAILER 5 // compression_type(1) + CRC32(4)
static const uint64_t kMagicNumber = 0xdb4775248b80fb57ULL;
// 编码 Footer，buf 至少 48 字节
static void encode_footer(uint8_t *buf,
const BlockHandle *metaindex,
const BlockHandle *index) {
int n = 0;
n += encode_block_handle(buf + n, metaindex);
n += encode_block_handle(buf + n, index);
// 补零到 40 字节
memset(buf + n, 0, 40 - n);
// 写入 magic number（little-endian）
memcpy(buf + 40, &kMagicNumber, 8);
}
// 解码 Footer
static int decode_footer(const uint8_t *buf,
BlockHandle *metaindex, BlockHandle *index) {
uint64_t magic;
memcpy(&magic, buf + 40, 8);
if (magic != kMagicNumber) return -1;
int n = decode_block_handle(buf, 40, metaindex);
if (n < 0) return -1;
n = decode_block_handle(buf + n, 40 - n, index);
if (n < 0) return -1;
return 0;
}Index Block
Index Block 的格式和 Data Block 完全相同——前缀压缩的 entry，restart array，trailer。区别在于它存的内容：
- key = separator key（≥ 当前 Data Block 最大 key，< 下一 Data Block 最小 key）。
- value = BlockHandle，编码为 varint64 × 2。
查找 key 时，先对 Index Block 做二分查找，定位到目标 Data Block 的 BlockHandle，再读那个 Data Block。
为简化实现，我们用每个 Data Block 的最后一个 key 作为
separator（LevelDB 实际上会计算
shortest_separator，更短但意思相同）。
SSTable Builder
TableBuilder 把一系列有序 key-value
写入文件，输出一个完整的 SSTable：
typedef struct {
FILE *fp; // 输出文件
uint64_t offset; // 当前文件偏移
BlockBuilder data_block; // 当前正在构建的 data block
BlockBuilder index_block; // index block
// 记录上一个 data block 的信息（用于写 index entry）
int pending_index; // 是否有待写入的 index entry
char last_key[256]; // 上个 data block 的最后一个 key
int last_key_len;
BlockHandle pending_handle; // 上个 data block 的 handle
// Bloom Filter：收集所有 key
char **all_keys;
size_t *all_key_lens;
int key_count;
int key_cap;
} TableBuilder;
static void table_builder_init(TableBuilder *tb, FILE *fp) {
tb->fp = fp;
tb->offset = 0;
block_builder_init(&tb->data_block);
block_builder_init(&tb->index_block);
tb->pending_index = 0;
tb->last_key_len = 0;
tb->key_cap = 1024;
tb->all_keys = malloc(tb->key_cap * sizeof(char *));
tb->all_key_lens = malloc(tb->key_cap * sizeof(size_t));
tb->key_count = 0;
}核心方法 table_builder_add 每次加入一个
key-value：
// 写入一个 block 到文件，返回 BlockHandle
static BlockHandle write_block(TableBuilder *tb, BlockBuilder *bb) {
block_builder_finish(bb);
BlockHandle handle;
handle.offset = tb->offset;
handle.size = bb->size;
// 写入 block 数据
fwrite(bb->data, 1, bb->size, tb->fp);
tb->offset += bb->size;
// 写入 trailer: compression_type(0) + CRC32
uint8_t trailer[BLOCK_TRAILER];
trailer[0] = 0; // 不压缩
// CRC32 覆盖 block 数据 + compression_type
uint32_t crc = crc32(0, bb->data, bb->size);
crc = crc32(crc, trailer, 1);
memcpy(trailer + 1, &crc, 4);
fwrite(trailer, 1, BLOCK_TRAILER, tb->fp);
tb->offset += BLOCK_TRAILER;
return handle;
}
static void table_builder_add(TableBuilder *tb,
const char *key, size_t key_len,
const char *val, size_t val_len) {
// 如果有 pending 的 index entry，先写入
if (tb->pending_index) {
// 用 last_key 作为 separator
uint8_t handle_buf[20];
int hn = encode_block_handle(handle_buf, &tb->pending_handle);
block_builder_add(&tb->index_block,
tb->last_key, tb->last_key_len,
(const char *)handle_buf, hn);
tb->pending_index = 0;
}
// 收集 key 用于 Bloom Filter
if (tb->key_count >= tb->key_cap) {
tb->key_cap *= 2;
tb->all_keys = realloc(tb->all_keys, tb->key_cap * sizeof(char *));
tb->all_key_lens = realloc(tb->all_key_lens,
tb->key_cap * sizeof(size_t));
}
tb->all_keys[tb->key_count] = malloc(key_len);
memcpy(tb->all_keys[tb->key_count], key, key_len);
tb->all_key_lens[tb->key_count] = key_len;
tb->key_count++;
// 写入 data block
block_builder_add(&tb->data_block, key, key_len, val, val_len);
// 记住当前 key
memcpy(tb->last_key, key, key_len);
tb->last_key_len = (int)key_len;
// data block 达到阈值，flush
if (tb->data_block.size >= BLOCK_SIZE) {
tb->pending_handle = write_block(tb, &tb->data_block);
tb->pending_index = 1;
// 重置 data block
block_builder_free(&tb->data_block);
block_builder_init(&tb->data_block);
}
}最后调用 table_builder_finish
完成整个文件：
static void table_builder_finish(TableBuilder *tb) {
// Flush 最后一个 data block（如果还有数据）
if (tb->data_block.size > 0) {
tb->pending_handle = write_block(tb, &tb->data_block);
tb->pending_index = 1;
}
// 写最后一条 index entry
if (tb->pending_index) {
uint8_t handle_buf[20];
int hn = encode_block_handle(handle_buf, &tb->pending_handle);
block_builder_add(&tb->index_block,
tb->last_key, tb->last_key_len,
(const char *)handle_buf, hn);
}
// === 写 Meta Block（Bloom Filter）===
BloomFilter bf;
bloom_create(&bf,
(const char **)tb->all_keys, tb->all_key_lens,
tb->key_count, 10); // 10 bits/key
// meta block = bloom bits + k(1 byte)
BlockHandle meta_handle;
meta_handle.offset = tb->offset;
size_t bloom_bytes = bf.num_bits / 8;
meta_handle.size = bloom_bytes + 1;
fwrite(bf.bits, 1, bloom_bytes, tb->fp);
uint8_t k_byte = (uint8_t)bf.k;
fwrite(&k_byte, 1, 1, tb->fp);
tb->offset += bloom_bytes + 1;
// meta block trailer
uint8_t mt[BLOCK_TRAILER];
mt[0] = 0;
uint32_t mcrc = crc32(0, bf.bits, bloom_bytes);
mcrc = crc32(mcrc, &k_byte, 1);
mcrc = crc32(mcrc, mt, 1);
memcpy(mt + 1, &mcrc, 4);
fwrite(mt, 1, BLOCK_TRAILER, tb->fp);
tb->offset += BLOCK_TRAILER;
// === 写 MetaIndex Block ===
BlockBuilder metaindex;
block_builder_init(&metaindex);
uint8_t mh_buf[20];
int mhn = encode_block_handle(mh_buf, &meta_handle);
block_builder_add(&metaindex, "filter.bloom", 12,
(const char *)mh_buf, mhn);
BlockHandle metaindex_handle = write_block(tb, &metaindex);
block_builder_free(&metaindex);
// === 写 Index Block ===
BlockHandle index_handle = write_block(tb, &tb->index_block);
// === 写 Footer ===
uint8_t footer[FOOTER_SIZE];
encode_footer(footer, &metaindex_handle, &index_handle);
fwrite(footer, 1, FOOTER_SIZE, tb->fp);
tb->offset += FOOTER_SIZE;
// 清理 Bloom Filter
free(bf.bits);
// 清理 key 收集
for (int i = 0; i < tb->key_count; i++)
free(tb->all_keys[i]);
free(tb->all_keys);
free(tb->all_key_lens);
}构建流程就是 LevelDB TableBuilder::Finish()
的 C 翻译，次序清晰：Data Blocks → Meta Block → MetaIndex
Block → Index Block → Footer。
SSTable Reader
打开 SSTable
读取的入口：先读 Footer，然后根据两个 handle 加载 Index Block 和 Bloom Filter 到内存。
typedef struct {
FILE *fp;
uint64_t file_size;
// 常驻内存
uint8_t *index_data; // Index Block 数据
size_t index_size;
BloomFilter bloom; // Bloom Filter
int has_bloom; // 是否成功加载了 bloom
} TableReader;
// 读取指定 handle 的 block 数据（不含 trailer）
static uint8_t *read_block(FILE *fp, const BlockHandle *h, size_t *out_size) {
uint8_t *buf = malloc(h->size);
fseek(fp, (long)h->offset, SEEK_SET);
fread(buf, 1, h->size, fp);
*out_size = h->size;
// 读取 trailer 并验证 CRC32
uint8_t trailer[BLOCK_TRAILER];
fread(trailer, 1, BLOCK_TRAILER, fp); // 紧跟 block 数据之后
uint32_t stored_crc;
memcpy(&stored_crc, trailer + 1, 4);
uint32_t actual_crc = crc32(0, buf, h->size);
actual_crc = crc32(actual_crc, trailer, 1); // 覆盖 compression_type
if (actual_crc != stored_crc) {
free(buf);
*out_size = 0;
return NULL;
}
return buf;
}
static int table_reader_open(TableReader *tr, const char *filename) {
tr->fp = fopen(filename, "rb");
if (!tr->fp) return -1;
// 获取文件大小
fseek(tr->fp, 0, SEEK_END);
tr->file_size = ftell(tr->fp);
if (tr->file_size < FOOTER_SIZE) {
fclose(tr->fp);
return -1;
}
// 读 Footer
uint8_t footer_buf[FOOTER_SIZE];
fseek(tr->fp, (long)(tr->file_size - FOOTER_SIZE), SEEK_SET);
fread(footer_buf, 1, FOOTER_SIZE, tr->fp);
BlockHandle metaindex_handle, index_handle;
if (decode_footer(footer_buf, &metaindex_handle, &index_handle) < 0) {
fclose(tr->fp);
return -1;
}
// 加载 Index Block
tr->index_data = read_block(tr->fp, &index_handle, &tr->index_size);
if (!tr->index_data) { fclose(tr->fp); return -1; }
// 加载 Bloom Filter（通过 MetaIndex 找到 Meta Block）
tr->has_bloom = 0;
size_t mi_size;
uint8_t *mi_data = read_block(tr->fp, &metaindex_handle, &mi_size);
if (!mi_data) { free(tr->index_data); fclose(tr->fp); return -1; }
const char *bloom_handle_raw;
int bloom_handle_len;
if (block_search(mi_data, mi_size, "filter.bloom", 12,
&bloom_handle_raw, &bloom_handle_len) == 0) {
BlockHandle bloom_bh;
if (decode_block_handle((const uint8_t *)bloom_handle_raw,
bloom_handle_len, &bloom_bh) >= 0) {
// 读取 bloom block
size_t bloom_raw_size;
uint8_t *bloom_raw = read_block(tr->fp, &bloom_bh,
&bloom_raw_size);
if (bloom_raw_size > 1) {
tr->bloom.k = bloom_raw[bloom_raw_size - 1];
tr->bloom.num_bits = (bloom_raw_size - 1) * 8;
tr->bloom.bits = malloc(bloom_raw_size - 1);
memcpy(tr->bloom.bits, bloom_raw, bloom_raw_size - 1);
tr->has_bloom = 1;
}
free(bloom_raw);
}
}
free(mi_data);
return 0;
}Get 操作
完整的读取流程如下图所示：
// 在 SSTable 中查找 key
// 找到返回 0 并设置 val_out（调用者负责 free），未找到返回 -1
static int table_reader_get(TableReader *tr,
const char *key, size_t key_len,
char **val_out, int *val_len_out) {
// Step 1: Bloom Filter 快速排除
if (tr->has_bloom) {
if (!bloom_may_match(&tr->bloom, key, key_len)) {
return -1; // 一定不存在
}
}
// Step 2: 在 Index Block 中查找，定位 Data Block
// Index Block 的 value 是 BlockHandle
// 我们需要找到第一个 separator_key >= key 的 entry
// 教学简化：此处线性扫描；生产实现应对 restart array 做二分查找
// 遍历 index block
uint32_t num_restarts;
memcpy(&num_restarts, tr->index_data + tr->index_size - 4, 4);
size_t restarts_off = tr->index_size - 4 - num_restarts * 4;
size_t offset = 0;
char prev_key[256] = {0};
int prev_key_len = 0;
while (offset < restarts_off) {
char sep_key[256];
int sep_len;
const char *handle_raw;
int handle_len;
int consumed = decode_entry(tr->index_data, restarts_off, offset,
prev_key, prev_key_len,
sep_key, &sep_len,
&handle_raw, &handle_len);
if (consumed < 0) return -1;
int cmp = memcmp(sep_key, key,
(size_t)sep_len < key_len ? sep_len : key_len);
if (cmp == 0) cmp = sep_len - (int)key_len;
if (cmp >= 0) {
// 这个 data block 可能包含目标 key
BlockHandle data_bh;
if (decode_block_handle((const uint8_t *)handle_raw,
handle_len, &data_bh) < 0)
return -1;
// Step 3: 读取 Data Block 并查找
size_t block_sz;
uint8_t *block_data = read_block(tr->fp, &data_bh, &block_sz);
if (!block_data) return -1;
const char *v;
int vl;
int found = block_search(block_data, block_sz,
key, key_len, &v, &vl);
if (found == 0) {
*val_out = malloc(vl);
memcpy(*val_out, v, vl);
*val_len_out = vl;
}
free(block_data);
return found;
}
memcpy(prev_key, sep_key, sep_len);
prev_key_len = sep_len;
offset += consumed;
}
return -1;
}
static void table_reader_close(TableReader *tr) {
fclose(tr->fp);
free(tr->index_data);
if (tr->has_bloom) free(tr->bloom.bits);
}整个读路径：
- Bloom Filter（内存）→ 排除约 99% 的无效查找。
- Index Block（常驻内存）→ 定位 Data Block。
- Data Block（一次磁盘读）→ restart 二分 + 线性扫描。
生产级实现还会加入 Table Cache 和 Block Cache，避免重复打开文件和重复读取热点 Block。我们在示意图中标出了缓存层，但代码中暂不实现——这属于第 5 篇的完整引擎组装。
完整 Demo
把所有部件串起来——构建一个包含 100 个 key-value 的 SSTable，然后读取验证：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <zlib.h> // crc32
// [上面所有函数定义省略，依次拼接即可编译]
int main(void) {
const char *filename = "/tmp/test.sst";
// === 构建 SSTable ===
FILE *wfp = fopen(filename, "wb");
TableBuilder tb;
table_builder_init(&tb, wfp);
for (int i = 0; i < 100; i++) {
char key[32], val[32];
snprintf(key, sizeof(key), "key:%06d", i);
snprintf(val, sizeof(val), "value:%d", i);
table_builder_add(&tb, key, strlen(key), val, strlen(val));
}
table_builder_finish(&tb);
block_builder_free(&tb.data_block);
block_builder_free(&tb.index_block);
fclose(wfp);
printf("SSTable built: %s (%lu bytes)\n", filename, tb.offset);
// === 读取 SSTable ===
TableReader tr;
if (table_reader_open(&tr, filename) < 0) {
fprintf(stderr, "Failed to open SSTable\n");
return 1;
}
printf("SSTable opened. has_bloom=%d\n", tr.has_bloom);
// 测试存在的 key
const char *test_keys[] = {"key:000000", "key:000050", "key:000099"};
for (int i = 0; i < 3; i++) {
char *val = NULL;
int vlen = 0;
int ret = table_reader_get(&tr, test_keys[i], strlen(test_keys[i]),
&val, &vlen);
if (ret == 0) {
printf("GET %-12s => %.*s\n", test_keys[i], vlen, val);
free(val);
} else {
printf("GET %-12s => NOT FOUND\n", test_keys[i]);
}
}
// 测试不存在的 key（Bloom Filter 应拦截大部分）
const char *missing[] = {"key:999999", "nonexist", "zzzzz"};
for (int i = 0; i < 3; i++) {
char *val = NULL;
int vlen = 0;
int ret = table_reader_get(&tr, missing[i], strlen(missing[i]),
&val, &vlen);
printf("GET %-12s => %s\n", missing[i],
ret == 0 ? "FOUND (false positive?)" : "NOT FOUND");
if (ret == 0) free(val);
}
table_reader_close(&tr);
return 0;
}预期输出：
SSTable built: /tmp/test.sst (XXXX bytes)
SSTable opened. has_bloom=1
GET key:000000 => value:0
GET key:000050 => value:50
GET key:000099 => value:99
GET key:999999 => NOT FOUND
GET nonexist => NOT FOUND
GET zzzzz => NOT FOUND三个存在的 key 正确返回 value，三个不存在的 key 被 Bloom Filter 或 Data Block 查找排除。
系列路线图
| 篇目 | 标题 | 核心产出 |
|---|---|---|
| 第 1 篇 | LSM-Tree 全景 | 架构心智模型 + 三种放大的数学推导 |
| 第 2 篇 | WAL + MemTable | WAL 分片策略 + 跳表实现 + 崩溃恢复证明 |
| 第 3 篇 | SSTable + Bloom Filter（本文） | Data Block 前缀压缩 + Bloom Filter 双重哈希 + Builder/Reader |
| 第 4 篇 | Compaction | 多路归并迭代器 + Version/MANIFEST + 策略对比 |
| 第 5 篇 | 完整引擎 + Rust 重写对比 | DB API + 并发 + Snapshot + Iterator + Rust 重写 + benchmark |
→ 第 4 篇我们实现 Compaction：多路归并让 Level 间的数据有序流动，以及 Version/VersionEdit 如何记录每次 Compaction 的增量变化。
参考
- Patrick O’Neil, Edward Cheng, Dieter Gawlick, Elizabeth O’Neil. The Log-Structured Merge-Tree (LSM-Tree). Acta Informatica, 1996.
- LevelDB 源码: table_builder.cc — SSTable 构建实现。
- LevelDB 源码: block_builder.cc — Block 构建与前缀压缩。
- LevelDB 源码: block.cc — Block 读取与二分查找。
- LevelDB 源码: filter_block.cc — Bloom Filter 的构建与查询。
- LevelDB 源码: bloom.cc — BloomHash 与双重哈希实现。
- LevelDB 源码: format.cc — BlockHandle、Footer 编解码。
- Adam Kirsch, Michael Mitzenmacher. Less Hashing, Same Performance: Building a Better Bloom Filter. ESA 2006.
- Burton H. Bloom. Space/Time Trade-offs in Hash Coding with Allowable Errors. Communications of the ACM, 1970.
- 本站相关文章：leveldb 的缓存结构 — Table Cache 与 Block Cache 的 LRU 实现。
- 本站相关文章：LevelDB 日常使用 — Bloom Filter 参数配置与误判率公式推导。