企业官网建设流程全解析

项目地址：Remedios11/Mini-HDFS-Ceph: 分布式存储系统

技术栈：C++17、SkipList、SSTable、WAL、Bloom Filter、LRU Cache

系列：Mini Distributed Storage System（第一阶段：单机存储引擎）

一、为什么要造这个轮子？

面向实习而造…

我的引擎可以做到这些：

`

options.db_path = "./my_db"; auto* db = mini_storage::DB::Open(options); db->Put("user:1001", "Alice"); db->Put("user:1002", "Bob"); std::string value; db->Get("user:1001", &value); // "Alice" db->Delete("user:1002"); // 关闭程序，重启，数据还在 delete db;

这篇文章记录整个实现过程：设计思路、关键取舍、踩过的坑，以及每个模块背后的"为什么"。

二、架构总览：为什么是LSM-Tree?

在动手之前，需要先想清楚要构建什么。

核心问题：随机写太慢了…

传统数据库用B-Tree,MYSQL的InnoDB存储引擎用的是B+树（当然MYSQL是以读为主，用B+树很恰当，在此只是拿出来对比一下），首先B+树相比于B树，在数据库场景下有明显优势：磁盘读写代价更低，范围查询极快，但是每次写入都要在磁盘找到对应位置然后原地修改——这意味着是随机写。机械硬盘的随机写平均延迟4~8ms，SSD也要0.1ms级别。这对于大规模写入场景（日志系统、时序数据库、消息队列），这是非常大的问题。

LSM-Tree的核心思想：把所有随机写变成顺序写。

具体做法：不直接修改磁盘上的数据，而是先写到内存，积累到一定量再批量顺序刷到磁盘，这样磁盘永远只做顺序I/O，写性能大幅提升，代价是读取时要查多个地方，但可以通过各种索引结构来优化。

但是LSM有放大问题，读放大，写放大，空间放大

读放大：一次 Put 操作实际写了两次——先写 WAL（fsync 落盘），再写 MemTable，MemTable 刷盘时再写 SSTable，Compaction 时还会重写。实际写放大因子 ≈ Compaction 层数 × 每层大小比例。

写放大：最坏情况需要查 活跃MemTable → 只读MemTable → 每个 SSTable（先 Bloom Filter，再 Index Block，再 Data Block），层数越多读放大越大。

空间放大：同一个 Key 在不同 SSTable 中存在多个历史版本，删除操作只写 Tombstone 不立即清理，Compaction 前磁盘占用可达实际数据量的数倍。

但是我这边用布隆过滤器缓解读放大，Compaction缓解空间放大

LSM树适合的是写的快的环境，B+树适合的是读的快的环境

完整I/O路径

【写路径 Write Path】

Client 写入

→ 追加写入 WAL 文件（顺序写，fsync 落盘）

→ 写入内存 MemTable

→ 返回成功

（MemTable 达到阈值，如 4MB）

→ 冻结 MemTable，转为只读

→ 异步刷盘，生成 SSTable 文件

→ 更新 Checkpoint，删除旧 WAL

【读路径 Read Path】

Client 读取 key

→ 查活跃 MemTable（最新数据）

→ 查只读 MemTable（正在刷盘的）

→ 查 LRU Block Cache（热点缓存）

→ 查各层 SSTable：布隆过滤器拦截 → 读索引 → 加载 Block → 二分查找

→ 返回结果

整个系统由四个核心模块组成

| 模块 | 核心能力 |

| MemTable（跳表） | 内存有序存储，O(log N) 增删查 |

| SSTable | 数据持久化，磁盘高效检索 |

| WAL + 崩溃恢复 | 写入持久性，进程崩溃不丢数据 |

| Bloom Filter + LRU Cache + Compaction | 读取加速，磁盘空间控制 |

三、MemTable——内存中的有序世界

为什么选跳表而不是红黑树？

MemTable的核心需求：有序、高效、支持并发

std::map底层是红黑树，O(log N)的增删查满足要求，但是为什么我选跳表呢：

1. 并发控制更友好：红黑树的旋转操作需要锁住树的大范围节点；跳表的插入只影响局部指针，更容易实现细粒度锁，甚至 lock-free 版本（RocksDB 就是这么做的）。
2. 实现更简单直观：跳表的核心逻辑，调试和验证都更容易

跳表的结构是多层有序链表，上层是下层的稀疏索引

Level 3: 1 ──────────────────────────── 9

Level 2: 1 ──────── 4 ──────── 7 ───── 9

Level 1: 1 ──── 3 ── 4 ──── 6 ─ 7 ─── 9

Level 0: 1 ─ 2 ─ 3 ─ 4 ─ 5 ─ 6 ─ 7 ─ 8 ─ 9

查找时从最高层开始，每层快速跳过不可能的区间，平均O(log N)，节点的层数由随机函数决定(1/2的概率晋升)所以叫概率分层

墓碑删除

MemTable的删除不是真的删除数据，而是插入一条特殊的标记记录：

db->Delete("user:1002"); // 内部实际执行的是： memtable.Put("user:1002", "", kTypeDeletion); // 插入墓碑标记

因为磁盘上的SSTable是不可变文件，没法原地删除。墓碑标记会在读取时屏蔽老版本数据，在Compaction时真正删除，其实把删除变成写入墓碑标记，简化了整个写路径的逻辑

迭代器模式

MemTable暴露迭代器接口

for (iter->SeekToFirst(); iter->Valid(); iter->Next()) { // key 按字典序有序遍历 process(iter->Key(), iter->Value()); }

MemTable刷盘、Compaction合并、范围查询，全部都是通过迭代器完成，统一的接口可以让各个模块之间解耦

四、SSTable——让数据落地磁盘

文件格式设计：三段式结构

SSTable(Sorted String Table)是数据在磁盘上的存储形式，文件格式参考LevelDB，分为三段

Data Block存储实际的键值对，每个Block大小约4KB（对齐磁盘扇区）

Index Block是稀疏索引，只记录每个Block的起始key和偏移量（如果给每个key都建索引，内存占用会很大，稀疏索引只需要O(Block数量)的内存，却只会让查找多一次Block内的二分搜索——内存占用降低10~100倍）

查找一个key的过程：

1. 加载Index Block（从 Footer 得知偏移量）
2. 在 Index Block 里二分查找，定位 key 在哪个 Data Block
3. 加载对应 Data Block
4. 在 Data Block 内部二分查找
5. 返回结果（或不存在）

Varint编码：省空间

数字序列化用了 Varint（变长编码）而不是固定 4 字节：

Fixed32（固定 4 字节）:

100 → [100][0][0][0] (4字节)

100000 → [160][134][1][0] (4字节)

Varint（变长编码）:

100 → [100] (1字节，节省 75%!)

100000 → [160][141][6] (3字节，节省 25%)

对于大量小整数（key/value长度、偏移量等），Varint平均能节省50~75%的空间，但是代价是编码/解码多一点计算量，但是因为该项目是存储引擎，所以值得

CRC32：数据的指纹

每个Data Block写入磁盘时，附加一个CRC32校验码：

uint32_t checksum = CalculateCRC32(block_data, block_size); file.write(block_data, block_size); EncodeFixed32(footer, checksum); file.write(footer, 4); // 读取时 uint32_t stored_checksum = DecodeFixed32(footer); uint32_t actual_checksum = CalculateCRC32(block_data, block_size); if (stored_checksum != actual_checksum) { return Status::Corruption("block checksum mismatch"); }

因为某些原因，数据可能损坏，CRC32用32位哈希值检测这类损坏，防止把错误数据当成正确数据返回给用户

五：WAL——崩溃恢复的最后防线

前面的任务做完之后会有一个缺陷：MemTable在内存里，一旦进程崩溃，数据就没了，所以我们要用WAL解决

WAL：先写日志，再写数据

WAL（Write-Ahead Log，写前日志）：在修改数据之前，先把要做什么记到日志文件里

没有 WAL 的写流程（有缺陷）：

Client → Put(“key”, “val”) → 写 MemTable → [进程崩溃] → 数据消失

有 WAL 的写流程（正确）：

Client → Put(“key”, “val”) → 先追加写 WAL 文件（崩溃后可以从这里恢复） → 再写 MemTable → 返回成功

WAL文件只做追加写，不修改已经写入的内容，保证速度，顺序追加写的延迟约0.1ms，比B树的随机写快特别多

每条WAL Record的格式：

CRC32覆盖Type+Data，确保WAL记录本身也不会损坏

WriteBatch：原子性的保证

多个操作打包成一个WriteBatch，对外表现为原子操作：

batch.Put("account:A", "balance:900"); // A 扣款 100 batch.Put("account:B", "balance:1100"); // B 收款 100 db->Write(batch); // 要么两条都成功，要么两条都失败，不会出现中间状态

整个WriteBatch序列化成一条WAL Record写入，回放时也是整批回放，保证原子性

崩溃恢复：从日志重建

程序重启时，DB::Open()会自动触发恢复流程

// 1. 找到 Checkpoint（上次安全点） CheckpointData checkpoint; ReadCheckpoint(&checkpoint); // 2. 打开 WAL 文件，跳到 Checkpoint 位置 LogReader reader(wal_file_); reader.SkipToOffset(checkpoint.log_offset); // 3. 逐条回放 Checkpoint 之后的日志 std::string record; while (reader.ReadRecord(&record)) { WriteBatch batch; batch.SetData(record); batch.Iterate(&MemTableHandler(mem_table_)); // 写回 MemTable } return Status::OK(); }

Checkpoint 之前的数据已经刷到 SSTable 了，是安全的；Checkpoint 之后、崩溃之前的数据在 WAL 里，回放一遍就能恢复。

六、优化模块————让引擎跑起来更快

布隆过滤器：拦截无效的磁盘I/O

在没有布隆过滤器的情况下，查询一个不存在的 key，需要遍历所有的 SSTable 文件。每次读 SSTable 至少需要一次磁盘 I/O（读 Index Block）

布隆过滤器能在查磁盘之前快速判断：这个 key一定不在这个 SSTable 里。

原理时用多个哈希函数映射到一个数组：

h1("Alice") = 42 → bit[42] = 1 h2("Alice") = 137 → bit[137] = 1 h3("Alice") = 890 → bit[890] = 1 查询 "Bob" 时： h1("Bob") = 42 → bit[42] = 1 (可能是 Alice 的哈希冲突) h2("Bob") = 512 → bit[512] = 0 ← 有一个 0，Bob 一定不存在！ → 直接返回 Not Found，不读磁盘

布隆过滤器有两种判断结果：

不存在：一定不存在（100%准确）

存在：可能存在（有极小概率误判）

误判率约在 1% 以内，但它能拦截大多数无效的磁盘读取——在实际负载中，大量查询的 key 并不存在，布隆过滤器在这种场景下效果显著。

哈希函数用的是 MurmurHash3，分布均匀、速度快，是存储引擎领域的标准选择。

LRU Cache：热点数据的加速器

频繁访问的 Data Block 缓存在内存里，避免反复读盘：

第一次读 “user:1001”：

布隆过滤器 → 读 Index Block → 读 Data Block → 写入 LRU Cache → 返回

第二次读 “user:1001”：

布隆过滤器 → LRU Cache 命中 → 直接返回（不读磁盘）

LRU（Least Recently Used）实现用的是经典的哈希表 + 双向链表组合：哈希表保证 O(1) 查找，双向链表维护访问顺序，每次访问把节点移到链表头，容量满时淘汰链表尾。

Compaction：控制磁盘空间膨胀

随着数据不断写入，SSTable文件越来越多，两个问题就会出现：

1. 读放大：查询一个 key 可能需要查 10 个 SSTable 文件（虽然布隆过滤器能过滤大部分，但还是有开销）。
2. 空间放大：同一个 key 的多次更新会在不同 SSTable 里留下多个版本；被删除的 key 的墓碑标记也一直占用空间。
3. 写放大：一次 Put 操作实际写了两次——先写 WAL（fsync 落盘），再写 MemTable，MemTable 刷盘时再写 SSTable，Compaction 时还会重写。实际写放大因子 ≈ Compaction 层数 × 每层大小比例。

Compaction是后台任务，定期把多个SSTable文件合并成一个更大的文件：

合并前：

SSTable-1: [a:1][b:2][c:old]

SSTable-2: [c:new][d:4]

SSTable-3: [b:DELETED][e:5]

Compaction（多路归并排序）：

合并后：

SSTable-merged: [a:1][c:new][d:4][e:5]

// b 已删除，c 只保留最新版本，空间和读取路径都变干净了

核心算法是多路归并：对每个SSTable创建一个迭代器，用优先队列（小顶堆）每次取出当前最小的key，遇到重复的key保留最新版本，遇到墓碑标记直接丢弃，时间复杂度O(N log K)，N是总记录数，K是参与合并的文件数

七、一次Put的完整过程

一次读取db->Put(“user:1001”,“Alice”)的流程：

① Client 调用 db->Put(“user:1001”, “Alice”)

② DB 层加锁，构造 WriteBatch

③ 序列化 WriteBatch，追加写入 WAL 文件
[WAL 文件]：… [CRC32|Len|Type|key_len|key|val_len|val] ← 新记录追加到这里

④ 调用 fsync（可选，强持久化模式下开启）
确保数据真正落盘，不在 OS 缓冲区里

⑤ 写入活跃 MemTable（跳表插入）
MemTable: {user:1000 → …, user:1001 → “Alice”, user:1002 → …}

⑥ 返回成功给 Client
↑ 到这里，整个写入流程结束，总延迟约 0.1~0.5ms

─────────────── 异步刷盘（MemTable 达到 4MB 阈值）──────────────

⑦ 活跃 MemTable 冻结，变为只读 Immutable MemTable
同时创建新的活跃 MemTable

⑧ 后台线程：遍历 Immutable MemTable（有序），写入新 SSTable 文件
SSTable: [Data Block…][Index Block][Footer]

⑨ 更新 Checkpoint，记录当前 WAL 位置

删除 Checkpoint 之前的旧 WAL 文件

⑩ Immutable MemTable 释放内存

一次读取db->Get(“user:1001”)的流程：

① 查活跃 MemTable → 未命中

② 查 Immutable MemTable（如有）→ 未命中

③ 查 LRU Block Cache → 未命中（冷数据）

④ 遍历各 SSTable：

• 布隆过滤器：可能存在 → 继续
• 读 Index Block：user:1001 在 Block #3
• 从磁盘加载 Block #3 → 写入 LRU Cache
• Block #3 内二分查找 → 找到 “Alice”

⑤ 返回 “Alice”

八、性能分析

我不会分析…

其实会，但是具体数值我并不会算…

九、复盘

其实MemTable也可以选map啊，但是我只是想学习跳表的结构啥的，理解为什么RocksDB选它，实际写生产代码还是会写map，遇到性能瓶颈再换，然后为什么WAL要fsync，因为如果不搞的话，数据在 OS 的 Page Cache 里，进程崩溃没问题，但机器断电就丢了。fsync 把 Page Cache 强制刷到磁盘，代价是每次 fsync 约 1~10ms 延迟。工程上的折中是Group Commit：多个写入共享一次 fsync，批量落盘。MySQL 的sync_binlog参数就是控制这个的。然后布隆过滤器经验公式：每个 key 分配 10 个 bit，使用 3 个哈希函数，误判率约 0.8%。bit 数越大，误判率越低，但内存占用越高。实际上布隆过滤器的内存非常小——100 万个 key，10 bit/key，才 1.25 MB，远小于 key-value 本身。

十、学到了啥

对LSM树的了解更深刻了

技术层面：

顺序写为什么比随机写快：磁盘物理寻道和直接追加的区别

布隆过滤器的误判特性

Checkpoint为什么用rename

Compaction的本质：用写放大换读放大，这是trade-off

还学到一个RUM定律，就是读性能，写性能，空间利用率，这三个只能选两个，所以这其实也是一种trade-off，主要看适合的场景再进行随机应变

十一、下一阶段

下一阶段接入基础网络层

然后我这博客就写完了，第一次写有写的不好的地方多多包涵哈谢谢，我也很喜欢大家来讨论问题啊，如果我文章里有讲错的地方欢迎大家指出！

项目在GitHub，点第一行链接就可以看到了，感谢各位大佬阅读!