cpp

用 C++ 实现存储引擎：B+ 树与 LSM-Tree

存储引擎是数据库的心脏。本文从页缓存与磁盘布局讲起，剖析 B+ 树的页格式、节点分裂与范围扫描，拆解 LSM-Tree 的 MemTable、SSTable、跳表与 compaction，讨论 WAL 崩溃恢复与三种读写放大，并给出一个 C++20 最小 KV 引擎骨架。

Leeting Yan 10 分钟阅读 4530 字

数据库、消息队列、时序系统、搜索索引，底层都站着一个存储引擎。它要解决的核心问题只有一个：如何在持久化介质上组织键值数据，使得读、写、范围扫描三类操作都在可接受的代价内完成。用 C++ 实现存储引擎是理解数据库内幕的最短路径，因为这里没有语言运行时的抽象泄漏，每一次内存拷贝、每一次系统调用都直接对应到性能数字。

一、两条技术路线

所有存储引擎都可以归入两种组织方式，它们的取舍贯穿整个设计。

路线代表写放大读放大适用场景
页式（B+ 树）InnoDB、SQLite、PostgreSQL高（原地更新要写整页 + WAL）低（树高约 3 到 4 层）读多写少、事务型负载
日志结构（LSM-Tree）LevelDB、RocksDB、Cassandra低（顺序追加）高（要查多层）写密集、追加型负载

页式的本质是原地更新：数据按固定大小的页（通常 4 KB 到 16 KB）组织成一棵平衡树，修改一个键就要读入整页、改内存、再写回。它把随机写变成了「读 - 改 - 写」，因此必须靠 WAL 先把变更日志顺序落盘来保证崩溃一致性。

LSM-Tree 的本质是顺序追加：所有写入先进内存表，攒够了一次性顺序刷成不可变的有序文件，后台再不断合并。它把随机写彻底转成顺序写，代价是读一个键可能要穿透多层文件。

选型时先问一句：这个负载是「一次写入、多次读取」，还是「持续高频写入」。前者用 B+ 树，后者用 LSM-Tree。

二、页布局与页缓存

2.1 页格式

存储引擎与文件系统之间隔着一层页管理器。页是 I/O 的最小单位，也是缓存的最小单位。

// page.h
#pragma once
#include <cstdint>
#include <cstddef>
#include <array>

constexpr std::size_t kPageSize = 4096;

// 页头：12 字节，控制信息与校验和分离，便于只更新校验字段
struct PageHeader {
    std::uint16_t slot_count;   // 槽位数量
    std::uint16_t free_offset;  // 空闲区起始偏移
    std::uint16_t free_size;    // 空闲区大小
    std::uint16_t flags;        // 页类型与状态位
    std::uint32_t lsn;          // 最后修改该页的日志序号
};

static_assert(sizeof(PageHeader) == 12, "页头必须是紧凑的 12 字节");

struct Page {
    PageHeader header;
    std::array<std::byte, kPageSize - sizeof(PageHeader)> data;
    std::uint32_t checksum() const;   // 通常用 CRC32C
};

页头里的 lsn 是 WAL 与页式引擎的接缝：恢复时用页的 lsn 与日志的 lsn 比较，决定这一页是否需要重放。

2.2 页缓存

页缓存（buffer pool）是内存中的哈希表加淘汰链表，fetch() 返回一个持有页锁的句柄，析构时自动归还并可能触发淘汰，mark_dirty() 记录脏页与对应的 lsn。

class BufferPool {
public:
    explicit BufferPool(std::size_t capacity) : capacity_(capacity) {}
    PageHandle fetch(PageId pid);
    void mark_dirty(PageId pid, std::uint32_t lsn);

private:
    std::size_t capacity_;
    std::unordered_map<std::uint32_t, Frame> frames_;
    std::list<std::uint32_t> lru_;   // 淘汰顺序
    std::mutex latch_;
};

命中率决定一切，因为一次缺页就是一次随机 I/O。经典做法是 CLOCK 或 LRU-K 淘汰，并对脏页做后台刷盘。页缓存不能无限增长：内存越大，checkpoint 时的刷盘尖峰越明显，恢复时间也越长。

三、B+ 树实现要点

3.1 节点格式

B+ 树与二叉搜索树的关键差异在两点：节点是页大小的多路分支，且只有叶子节点存数据，内部节点只存分隔键。

// btree_node.h
#pragma once
#include <cstdint>
#include <string_view>

// 叶子节点：按键有序排列的槽位数组
//  [header][key0][val0][key1][val1] ... [slot_offsets]
struct LeafNode {
    std::uint16_t count;
    std::uint16_t next_leaf;    // 叶子链表，用于范围扫描
    std::uint16_t prev_leaf;
    std::uint16_t slot[1];      // 柔性数组，存每项的偏移
};

// 内部节点：N 个键 + N+1 个子页号，布局为
//  [header][child0][key0][child1][key1] ... [childN]
struct InternalNode {
    std::uint16_t count;
    std::uint16_t reserved;
    std::uint32_t child[1];
};

键用 std::string_view 传递而不拷贝，比较时用 memcmp 而非 std::string，这一条在热路径上能省下可观的分配开销。

3.2 查找与分裂

查找是自上而下的二分：每个内部节点对分隔键做 std::upper_bound，决定走向哪个子页。真正的难点在插入导致的分裂。

// 分裂的通用逻辑：把一个满节点一分为二，返回提升到父节点的分隔键
struct SplitResult {
    PageId right;
    std::vector<std::byte> separator;
};
SplitResult split_leaf(LeafNode* leaf, std::size_t slot_bytes);

分裂策略直接影响空间利用率。「对半分裂」在插入有序键时会产生 50% 的空间浪费；「按字节均分」让两侧字节数尽量相等，更好。批量装载（bulk load）时可以预先把叶子填到接近满，再自底向上建内部节点，空间利用率能到 90% 以上。删除时不能立即合并节点，否则会出现「抖动」——删除一个键触发合并，插入一个键又触发分裂。工程上普遍采用延迟合并：节点下溢时先标记，只有当同一父节点的兄弟也欠载时才真正合并，其余情况靠再平衡解决。

3.3 范围扫描

B+ 树最不可替代的能力是有序遍历。叶子节点之间用双向链表连接，找到起点后顺序往后走即可，无需回到根节点。

class BTreeCursor {
public:
    void seek(std::string_view key);   // 定位到第一个 >= key 的位置
    bool valid() const;
    void next();
    std::string_view key() const;
    std::string_view value() const;

private:
    std::vector<PageHandle> path_;   // 从根到叶的路径，用于向上回溯
    std::size_t slot_ = 0;
};

游标持有从根到叶的整条路径，这样 next() 跨页时可以沿着路径向上找到后继，而不必每次从根重新下降。

四、WAL 与崩溃恢复

页式引擎不能直接改磁盘上的页，否则写到一半断电就会留下半个页。WAL（Write-Ahead Logging）的原则是：任何页的修改，其日志必须先落盘。

// wal.h
#pragma once
#include <cstdint>
#include <span>

enum class WalRecordType : std::uint8_t {
    kInsert = 1, kDelete = 2, kCommit = 3, kCheckpoint = 4,
};

struct WalRecordHeader {
    std::uint32_t lsn;
    std::uint32_t txn_id;
    std::uint8_t  type;
    std::uint32_t page_id;    // 受影响页
    std::uint32_t length;     // 负载长度
    std::uint32_t crc32c;     // 覆盖头部与负载
};

class WalWriter {
public:
    std::uint32_t append(const WalRecordHeader& hdr, std::span<const std::byte> payload);
    // 组提交：多个事务共用一次 fsync，是 WAL 吞吐的关键
    void flush(bool sync);
};

flush(false) 只写进内核页缓存，flush(true) 才调用 fsync。这里的核心优化是组提交（group commit）：把短时间内多个事务的日志攒在一起，用一次 fsync 落盘。单条日志一次 fsync 时吞吐被磁盘延迟锁死在几百 TPS，组提交能把它拉到几万 TPS。

恢复流程分三个阶段：

  1. 分析：从最近一次 checkpoint 的 LSN 开始扫描日志，重建脏页表与活动事务表。
  2. 重做：对每条日志，若目标页的 lsn 小于日志 lsn，则重放该修改（幂等）。
  3. 撤销：对未提交事务的日志做反向撤销，回滚它们已写下的修改。

判断一条日志是否已经反映到页上，靠的正是页头里的 lsn 字段——这也是为什么它必须和页一起原子落盘。

五、LSM-Tree 实现要点

5.1 MemTable 与跳表

LSM-Tree 的写入路径是：先写 WAL，再写内存表。内存表必须支持有序遍历与并发插入，跳表是标准答案。

// memtable.h
#pragma once
#include <atomic>
#include <optional>
#include <string>
#include <string_view>

// 跳表节点：层高随机，最高 12 层足以支撑千万级元素
struct SkipNode {
    std::string key;
    std::string value;
    std::atomic<SkipNode*> next[12];
};

// MemTable 对外暴露 put / remove / get / approximate_size
// remove 写入墓碑标记，get 命中墓碑即返回空

删除不真的删数据，而是写入一个**墓碑（tombstone）**标记。因为旧值可能还躺在更底层的 SSTable 里，只有墓碑才能保证它不会在读取时「复活」。

5.2 SSTable 与布隆过滤器

内存表写满后整体刷成一个 SSTable（Sorted String Table）。它的结构是：数据块 + 索引块 + 布隆过滤器 + 尾部的元信息。数据块内按键有序，块之间用索引定位。

// sstable.h
#pragma once
#include <cstdint>

// 尾部元信息：指向索引块与布隆过滤器，magic 为 "SBT1"
struct SstFooter {
    std::uint64_t index_offset;
    std::uint64_t bloom_offset;
    std::uint64_t data_size;
    std::uint32_t magic;
};

布隆过滤器提供 add(key) 与 may_contain(key)，内部是一排 std::uint64_t 位图加 k = bits_per_key * ln2 个哈希函数。它的价值在于把「确定不存在」的查询挡在磁盘 I/O 之前：10 bits/key 时误判率约 1%，能把点查的读放大降低一个数量级。每个键用双哈希技巧生成 k 个位置：h_i = h1 + i * h2。

5.3 Compaction

合并策略决定 LSM-Tree 的三种放大之间的平衡。主流有三代方案：

  • Leveled（LevelDB/RocksDB 默认）：每层容量按 10 倍递增，层内按键范围切分成多个文件，合并时只挑有重叠的文件。空间放大最小（约 1.1 倍），但写放大最大（总写放大可达 20 到 30 倍）。
  • Tiered（Cassandra）：同层允许多个文件有重叠，合并时一次归并整层。写放大最小，读放大与空间放大最大。
  • Hybrid（RocksDB Universal）：小层用 tiered，大层用 leveled，是当前的主流折中。

写放大是 LSM-Tree 最昂贵的代价。一个经验法则是：如果写入带宽的 80% 以上都被 compaction 吃掉，就该调大每层容量倍数，或者切换到 tiered 策略。工程实现上，一次 compaction 是一个 CompactionTask：记录层号、参与合并的输入文件号、输出文件号，以及是否为整层合并（major）。

六、三种放大的权衡

任何存储引擎都在读放大、写放大、空间放大之间做三角权衡，没有例外。

放大类型定义B+ 树LSM-Tree
读放大一次逻辑读触发的物理读次数约 1（树高 3 到 4 层，顶层常驻内存）3 到 10（逐层查找）
写放大一次逻辑写导致的物理写字节数10 到 30（页 + WAL + 双写缓冲）10 到 30（compaction）
空间放大实际占用与逻辑数据量之比约 1.3（页内碎片）1.1 到 2（多版本残留）

调优的基本手法：

  • 降读放大：加大布隆过滤器位数、把索引常驻内存、用 posix_fadvise 预读。
  • 降写放大：组提交、调整 compaction 触发阈值、SSD 上关掉双写缓冲（有风险）。
  • 降空间放大：更激进的 compaction、定期做 full compaction、开启前缀压缩。

七、持久化原语

7.1 fsync 与 O_DIRECT

write() 返回成功只代表数据进了内核页缓存，fsync() 返回才代表数据落到介质。SSD 上单次 fsync 的延迟在 100 微秒到 1 毫秒之间，这是所有持久化系统的性能基线。

#include <fcntl.h>
#include <unistd.h>

// O_DIRECT 绕过页缓存，避免「写一次、缓存一次、再刷一次」的双重开销
int fd = ::open("data.sst", O_RDWR | O_CREAT | O_DIRECT, 0644);

// 约束：缓冲区地址、长度、偏移都要按块大小对齐，故需 posix_memalign 配对齐分配
void* p = nullptr;
::posix_memalign(&p, kPageSize, bytes);

多数引擎的选择是折中：写 WAL 用 O_DIRECT 保证顺序写的确定性，读数据走页缓存以利用局部性。

7.2 mmap 与 posix_fadvise

mmap 把文件映射进地址空间，读写就像访问内存，由内核负责缺页加载与回写，省掉了显式的 read/write 调用与一次拷贝；代价是缺页延迟不可控（SIGBUS 风险），且 OS 的淘汰策略不感知你的访问模式。用 ::madvise(base, size, MADV_RANDOM) 告诉内核这是随机访问，用 posix_fadvise(fd, 0, 0, POSIX_FADV_WILLNEED) 主动预读、POSIX_FADV_DONTNEED 提示内核丢弃不再需要的缓存——在扫描大表后立刻释放缓存能显著降低对其他查询的干扰。

八、并发控制

8.1 Latch Crabbing

B+ 树的并发插入需要同时持有多个页的锁。朴素做法是全程持有根节点的锁，把整棵树串行化。Latch Crabbing（螃蟹式加锁） 的做法是：先锁父节点，再锁子节点，确认子节点安全（不会分裂）后立刻释放父节点锁。

// 悲观插入：只在可能分裂时才继续持有祖先锁
void BTree::insert(std::string_view key, std::string_view value) {
    auto* node = root_;
    node->latch.lock();
    while (!node->is_leaf()) {
        auto* child = descend(node, key);
        child->latch.lock();
        if (child->is_safe_for_insert()) node->latch.unlock();   // 不满则放掉祖先
        node = child;
    }
    insert_into_leaf(node, key, value);
    node->latch.unlock();
}

优化的关键是乐观插入：绝大多数插入不会引发分裂，所以先用读锁走一遍，确认所有节点都安全后再拿写锁重做一遍。分裂是小概率事件，乐观路径覆盖了 99% 以上的情况。

并发读与 compaction 也会打架：读线程正在遍历一个 SSTable，后台却想把它合并删掉。解法是引用计数加延迟删除——文件在被打开时计数加一，compaction 只标记删除，等计数归零才真正 unlink。这正是 shared_ptr 在存储引擎里的经典用途。

相关阅读

  • https://plumephp.com/cpp-performance-optimization/ — 缓存友好布局与分支预测的通用手法
  • https://plumephp.com/cpp-memory-pool-allocators/ — 页缓存与对齐分配器的实现基础
  • https://plumephp.com/cpp-concurrency-patterns/ — latch crabbing 背后的并发模式

延伸阅读

  • https://plumephp.com/cpp-compilation-linking/ — 编译、链接与目标文件格式的基础
  • https://plumephp.com/cpp-atomic-memory-order/ — 无锁跳表所需的内存序知识
  • https://plumephp.com/cpp-serialization-libraries/ — SSTable 与 WAL 的序列化选型

文末完整示例

// 最小 KV 引擎骨架：WAL + MemTable + SSTable，可直接编译
// 编译：g++ -std=c++20 -O2 -o kvstore kvstore.cpp
#include <cassert>
#include <cstdint>
#include <cstdio>
#include <filesystem>
#include <fstream>
#include <map>
#include <optional>
#include <string>
#include <string_view>

namespace kv {

constexpr std::size_t kMemFlushBytes = 4096 * 256;

// ---------- 1. MemTable：std::map 简化版（生产用跳表） ----------
struct Entry { std::string value; bool deleted = false; };
class MemTable {
public:
    void put(std::string_view key, std::string_view value) {
        table_[std::string(key)] = Entry{std::string(value), false};
        bytes_ += key.size() + value.size();
    }
    void remove(std::string_view key) { table_[std::string(key)] = Entry{"", true}; }
    std::optional<std::string> get(std::string_view key) const {
        auto it = table_.find(std::string(key));   // 墓碑即视为不存在
        if (it == table_.end() || it->second.deleted) return std::nullopt;
        return it->second.value;
    }
    std::size_t size_bytes() const { return bytes_; }
    const std::map<std::string, Entry>& table() const { return table_; }
private:
    std::map<std::string, Entry> table_;   // 有序，便于刷成 SSTable
    std::size_t bytes_ = 0;
};
// ---------- 2. 引擎：写走 WAL -> MemTable，满则刷 SSTable ----------
class Engine {
public:
    explicit Engine(std::filesystem::path dir)
        : dir_(std::move(dir)), wal_(dir_ / "wal.log", std::ios::binary | std::ios::app) {
        std::filesystem::create_directories(dir_);
    }
    void put(std::string_view key, std::string_view value) {
        append_wal(key, value, false);
        mem_.put(key, value);
        if (mem_.size_bytes() > kMemFlushBytes) flush();
    }
    void remove(std::string_view key) {
        append_wal(key, "", true);
        mem_.remove(key);
    }
    std::optional<std::string> get(std::string_view key) const { return mem_.get(key); }
private:
    void append_wal(std::string_view key, std::string_view value, bool deleted) {
        auto klen = static_cast<std::uint32_t>(key.size());
        auto vlen = static_cast<std::uint32_t>(value.size());
        std::uint8_t flag = deleted ? 1 : 0;
        wal_.write(reinterpret_cast<const char*>(&klen), sizeof(klen));
        wal_.write(reinterpret_cast<const char*>(&vlen), sizeof(vlen));
        wal_.write(reinterpret_cast<const char*>(&flag), sizeof(flag));
        wal_.write(key.data(), static_cast<std::streamsize>(key.size()));
        wal_.write(value.data(), static_cast<std::streamsize>(value.size()));
    }
    void flush() {   // 整体顺序写出，键已有序
        std::ofstream out(dir_ / ("sst_" + std::to_string(++sst_id_) + ".dat"),
                          std::ios::binary | std::ios::trunc);
        for (const auto& [key, entry] : mem_.table()) {
            auto klen = static_cast<std::uint32_t>(key.size());
            auto vlen = static_cast<std::uint32_t>(entry.value.size());
            out.write(reinterpret_cast<const char*>(&klen), sizeof(klen));
            out.write(reinterpret_cast<const char*>(&vlen), sizeof(vlen));
            out.write(key.data(), static_cast<std::streamsize>(key.size()));
            out.write(entry.value.data(), static_cast<std::streamsize>(entry.value.size()));
        }
        wal_.flush();   // 组提交点：一次 flush 覆盖整批写入
        mem_ = MemTable{};
    }
    std::filesystem::path dir_;
    std::ofstream wal_;
    MemTable mem_;
    std::uint64_t sst_id_ = 0;
};

}  // namespace kv
int main() {
    kv::Engine engine("/tmp/kvstore_demo");
    engine.put("user:1", "alice");
    engine.put("user:2", "bob");
    engine.remove("user:1");
    assert(!engine.get("user:1"));
    assert(engine.get("user:2").value() == "bob");
    std::puts("kvstore demo ok");
    return 0;
}

继续阅读

探索更多技术文章

浏览归档，发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「cpp」更多文章

  1. C++ Unicode 与文本处理：编码转换与高性能字符串
  2. C++ 数值计算与线性代数：Eigen 与表达式模板
  3. C++ 静态分析与代码质量工具链：clang-tidy 与 Clang Static Analyzer