数据库系统内幕

一、全书概览

《Database Internals》（数据库系统内幕）是 Alex Petrov 写的一本硬核技术书，2020 年由 O'Reilly 出版。Petrov 本人是 Apache Cassandra 的 committer，也在 DataStax 做过架构师，所以这本书不是从零讲理论的教科书，而是一个实打实从工程实践出发、拆解数据库底层实现的书。

全书分两部分：存储引擎和分布式系统，共 13 章。前半部分讲 B-Tree、LSM-Tree、事务、并发控制这些单机数据库的核心机制；后半部分讲复制、分区、分布式事务、共识算法这些分布式数据库的关键问题。覆盖了从 MySQL、PostgreSQL 到 Cassandra、Riak 等多种数据库的实际实现细节。

这本书的价值在于：它不是泛泛而谈"数据库是什么"，而是具体告诉你"数据库怎么做到的"。每个概念都有源码级别的实现引用，每个设计选择都有具体的性能数据支撑。如果你想理解数据库底层到底在干什么，或者你自己要造一个存储引擎，这本书是目前市面上最好的参考之一。

适合人群：后端工程师、数据库内核开发者、架构师、对系统底层有好奇心的人。不适合完全没接触过数据库的新手——你需要至少用过几种数据库，才能读出味道。

| 维度 | 信息 | |------|------| | 原版书名 | Database Internals: A Deep Dive into How Distributed Data Systems Work | | 作者 | Alex Petrov | | 出版 | O'Reilly, 2019 | | 页数 | 约 380 页 | | 难度 | ⭐⭐⭐⭐（中高） | | 领域 | 数据库内核、分布式系统 | | 核心价值 | 工程级拆解，不是理论堆砌 |

二、逐章要点

第1章：引言与概述

这章很短，但立了一个很好的框架。Petrov 把数据库分成了两个维度来理解：数据模型（关系型 vs 文档型 vs 图数据库等）和存储/分发架构（单机 vs 分布式）。他强调，很多关于数据库的争论（比如 SQL vs NoSQL）本质上混淆了这两个维度。

"数据库系统的复杂性来自两个独立的维度：数据在逻辑上如何组织（数据模型），以及数据在物理上如何存储和分发（存储引擎与分布式架构）。"

一个关键观点：你选择数据库时，不应该只看它是"SQL"还是"NoSQL"，而应该分别评估它的存储引擎适合什么工作负载，它的分布式架构能提供什么样的一致性和可用性保证。比如 PostgreSQL 用 B-Tree 做存储引擎，适合点查询和范围查询；Cassandra 用 LSM-Tree，适合高写入吞吐。

| 数据模型类型 | 代表数据库 | 典型场景 | |-------------|-----------|---------| | 关系型 | PostgreSQL, MySQL | 事务性业务系统 | | 文档型 | MongoDB, CouchDB | 灵活 schema 的内容管理 | | 键值型 | Redis, Riak | 缓存、会话存储 | | 列族型 | Cassandra, HBase | 高写入、时序数据 | | 图数据库 | Neo4j | 关系密集的社交网络 |

第2章：底层数据结构

这是全书技术密度最高的一章。Petrov 详细拆解了数据库使用的两种核心存储结构：B-Tree 和 LSM-Tree（Log-Structured Merge-Tree）。

B-Tree 是大多数关系型数据库的选择。它把数据组织成平衡的多叉树，查找时间复杂度 O(log n)。但 B-Tree 有个根本性的问题：写放大。每次更新都要找到对应页，修改后写回磁盘，还可能触发页分裂。一个 4KB 的修改可能导致 4 次 4KB 的写（读旧页 + 写 WAL + 写新页 + 写父页）。

LSM-Tree 换了个思路：所有写入先追加到内存中的 MemTable，满了之后刷盘变成 SSTable（Sorted String Table），后台定期合并。读的时候要从 MemTable 到各级 SSTable 逐层查找。这把随机写变成了顺序写，写入吞吐大幅提升，但读取变慢了（读放大），而且后台合并会消耗 I/O（空间放大）。

"在 B-Tree 和 LSM-Tree 之间做选择，本质上是在读放大、写放大和空间放大之间做权衡。没有免费的午餐。"

| 特性 | B-Tree | LSM-Tree | |------|--------|----------| | 写入方式 | 原地更新 | 追加写入 | | 写放大 | 较高（2-3x） | 较低（1x，但合并时高） | | 读放大 | 低（1次磁盘查找） | 高（需查多层 SSTable） | | 空间放大 | 低 | 较高（旧版本需合并清理） | | 范围查询 | 天然支持 | 需合并多个 SSTable | | 代表数据库 | MySQL InnoDB, PostgreSQL | Cassandra, RocksDB, LevelDB |

[ ] 理解 B-Tree 的页分裂机制和填充因子的影响
[ ] 动手写一个简化的 LSM-Tree（MemTable + SSTable + 合并）
[ ] 用 iostat 观察数据库在不同负载下的读写模式

第3章：存储引擎

这一章把底层数据结构组装成完整的存储引擎。讨论了缓冲池管理、文件格式、页面布局等工程细节。

Petrov 以 PostgreSQL 的堆文件和 MySQL InnoDB 的表空间为例，展示了不同的页面组织方式。PostgreSQL 把元组（tuple）直接存在堆文件里，通过 TID（tuple identifier）定位；InnoDB 则把数据和索引都组织在 B+Tree 里，数据就是聚簇索引的叶子节点。

缓冲池（Buffer Pool）是存储引擎性能的关键。它缓存经常访问的页面，避免每次查询都走磁盘。替换策略通常用改进的 LRU（比如 InnoDB 的 LRU 分冷热区，避免全表扫描污染缓存）。Petrov 特别提到了 预读（prefetching） 的重要性：顺序扫描时提前把后续页面拉进缓冲池，可以显著减少 I/O 等待。

"数据库的很多性能优化，本质上都是在和磁盘的物理特性作斗争。磁盘喜欢顺序读写、讨厌随机访问；缓存喜欢局部性好、讨厌全表扫描。"

第4章：B-Tree 的实现细节

这章深入 B-Tree 的工程实现。包括：

页面布局：InnoDB 的页面结构（File Header + Page Header + Infimum + Supremum + Records + Free Space + Page Directory），一个 16KB 的页面里塞了多少元数据
二分查找在页面内的实现：Page Directory 用槽（slot）记录每 4-8 条记录的位置，先在目录里二分定位，再在记录组内线性扫描
写时复制 vs 原地更新：LMDB 用写时复制实现 MVCC，InnoDB 用 undo log 实现可回滚的原地更新
分裂与合并策略：页面满时的分裂（从中间分裂、向右兄弟借记录、合并相邻页面）

一个让我印象深刻的细节：InnoDB 的 B+Tree 叶子节点之间用双向链表连接，这意味着范围查询在找到起始点后可以顺序扫描，不需要反复从根节点查找。但这也意味着并发修改时需要锁住兄弟节点，增加了锁的复杂度。

[ ] 阅读 InnoDB 源码中 btr_cur_search_to_nth_level 函数
[ ] 用 innodb_space 工具可视化 B-Tree 的页面结构
[ ] 理解写时复制（Copy-on-Write）和 undo log 两种 MVCC 实现的差异

第5章：事务与并发控制

事务是关系型数据库区别于简单 KV 存储的核心能力。Petrov 从 ACID 出发，但不是简单复述定义，而是从实现角度拆解每个字母背后的代价。

隔离级别是这一章的重点。从 Read Uncommitted 到 Serializable，每个级别允许什么异常现象（脏读、不可重复读、幻读），以及数据库用什么机制来防止这些异常：

| 隔离级别 | 脏读 | 不可重复读 | 幻读 | 典型实现 | |---------|------|-----------|------|---------| | Read Uncommitted | ✗ 可能 | ✗ 可能 | ✗ 可能 | 无锁 | | Read Committed | ✓ 防止 | ✗ 可能 | ✗ 可能 | 短期读锁 | | Repeatable Read | ✓ 防止 | ✓ 防止 | ✗ 可能（MySQL例外） | MVCC / 两阶段锁 | | Serializable | ✓ 防止 | ✓ 防止 | ✓ 防止 | 范围锁 / 快照隔离 + 检测 |

MySQL InnoDB 在 Repeatable Read 级别通过 next-key lock 防止了幻读，这是一个超越 SQL 标准的实现。

"并发控制不是免费的午餐。更高的隔离级别意味着更多的锁争用和更低的吞吐。选择隔离级别是在数据一致性和系统性能之间做权衡。"

MVCC（Multi-Version Concurrency Control）是现代数据库实现高并发读写的核心技术。它的思路是：不阻塞读，而是给每个事务看到数据的一个"快照"。写操作创建新版本，读操作读取旧版本。PostgreSQL 和 InnoDB 都实现了 MVCC，但方式不同：PostgreSQL 把旧版本存在堆文件里（需要 VACUUM 清理），InnoDB 把旧版本存在 undo log 里。

第6章：LSM-Tree 的实现细节

这一章和第4章对称，深入 LSM-Tree 的工程实现。

SSTable 的文件格式：通常包含 Data Block、Index Block、Filter Block 和 Footer。Data Block 里存排序好的键值对，Index Block 记录每个 Data Block 的起始键和偏移量，Filter Block 存布隆过滤器数据。查找时先查布隆过滤器（判断键是否存在），再在 Index Block 里二分查找定位 Data Block，最后在 Data Block 里查找。

合并策略是 LSM-Tree 性能的关键。Petrov 对比了几种策略：

Size-Tiered Compaction（Cassandra 默认）：类似大小的 SSTable 合并，写入吞吐高但读放大大
Leveled Compaction（RocksDB/LevelDB）：每层大小固定比例（通常 L1 是 L0 的 10 倍），读放大小但写放大大
FIFO Compaction：适合时间序列数据，只按时间淘汰，不做真正合并

一个很实用的观点：布隆过滤器可以显著减少 LSM-Tree 的读放大。布隆过滤器用少量内存就能判断一个键"肯定不在"或"可能在"某个 SSTable 里。LevelDB 的实现中，每 2KB 数据对应 8 字节的布隆过滤器，误判率约 1%。

[ ] 用 RocksDB 的 rocksdb.db_bench 跑不同合并策略的性能对比
[ ] 理解布隆过滤器的参数选择（哈希函数数量、位数组大小）对误判率的影响
[ ] 在实际项目中评估 B-Tree 和 LSM-Tree 的适用场景

第7章：日志与恢复

数据库崩溃后如何恢复到一致状态？靠的就是日志。Petrov 讨论了两种日志策略：

ARIES（Algorithm for Recovery and Isolation Exploiting Semantics） 是 InnoDB 和大多数关系型数据库使用的恢复算法。它的核心思想是 WAL（Write-Ahead Logging）：先写日志，再写数据页。崩溃恢复时，先用日志重做（redo）已提交但未落盘的事务，再回滚（undo）未提交的事务。

Redo 和 Undo 的配合：

Redo 恢复已提交事务的修改（保证持久性）
Undo 回滚未完成事务的修改（保证原子性）
Checkpoint 减少恢复时间（记录哪些页面已安全落盘）

Petrov 提到了一个工程上的细节：日志的写入必须是顺序的、同步的（fsync），因为这是数据库在崩溃时唯一能信赖的东西。InnoDB 的 innodb_flush_log_at_trx_commit=1 就是每事务提交都 fsync，这保证了持久性但牺牲了性能。很多"数据库性能优化"文章建议改成 2（每秒 fsync 一次），但这意味着最多丢 1 秒的数据——你是否能接受这个代价？

"WAL 是数据库持久性的最后防线。如果你不 fsync 日志，那你所有的持久性保证都是空中楼阁。"

第8章：分布式系统概述

从这一章开始进入第二部分。Petrov 讨论了分布式系统的基本问题：网络分区、时钟、一致性模型。

一个核心概念是 CAP 定理：在网络分区发生时，你只能在一致性和可用性之间选一个。但 Petrov 指出，CAP 定理经常被误读。实际上，大多数现代数据库在分区发生时选择了可用性（Cassandra），但提供了可调的一致性级别（QUORUM 读写的 R + W > N 策略），让用户自己决定每次操作的一致性保证。

一致性模型的谱系很长，从最弱的最终一致性到最强的线性一致性（Linearizability）。中间有因果一致性、读己之所写、单调读等。Petrov 用一个很直观的例子说明了不同一致性级别的区别：如果你发了条朋友圈，最终一致性下你的朋友可能过几秒才看到；线性一致性下，一旦返回成功，所有后续请求都能看到。

第9章：复制

复制是分布式数据库的基本操作。Petrov 对比了两种复制方式：

主从复制（Leader-Follower）：所有写操作发到主节点，主节点把变更同步到从节点。简单直观，但主节点是单点。MySQL 主从复制、Kafka 的分区复制都是这个模式。

无主复制（Leaderless / Quorum-based）：客户端同时写入多个副本，用仲裁（QUORUM）保证一致性。Cassandra、DynamoDB 采用这种方式。

| 复制方式 | 延迟 | 可用性 | 复杂度 | 代表 | |---------|------|--------|--------|------| | 主从同步 | 高（等所有从节点确认） | 低（主挂了从不能接管） | 低 | 传统 MySQL | | 主从半同步 | 中 | 中 | 中 | MySQL 5.7+ | | 主从异步 | 低 | 中（可能丢数据） | 中 | MySQL 默认 | | 无主 Quorum | 可调 | 高 | 高 | Cassandra |

反熵（Anti-Entropy） 机制用于修复副本间的数据不一致。读修复（Read Repair）在读请求时顺便修复差异；Merkle Tree 用于高效地发现不一致的范围，再精确同步。

"复制的核心矛盾是：你想要强一致性，就必须忍受高延迟和低可用；你想要高可用，就必须接受最终一致性下数据暂时不一致。"

第10章：分区

当数据量超过单机容量时，就需要分区（也叫分片）。Petrov 讨论了几种分区策略：

哈希分区：用键的哈希值决定分区。数据分布均匀，但范围查询困难
范围分区：按键的范围分配。支持范围查询，但可能出现热点（比如按时间分区时最近的分区负载最高）
目录分区：用一个独立的分区服务来记录每个键在哪个分区。灵活但多了一跳

再平衡（Rebalancing）是分区的难点。加机器或减机器时，如何尽量少地移动数据？一致性哈希（Consistent Hashing）和虚拟节点（Virtual Nodes）是常用方案。Cassandra 每个物理节点对应 256 个虚拟节点，这样加一个节点只需要迁移约 1/N 的数据。

第11章：分布式事务

分布式事务横跨多个节点，要保证原子性和隔离性。这是分布式系统里最难的问题之一。

两阶段提交（2PC） 是最经典的方案。第一阶段（Prepare）：协调者问所有参与者"你能提交吗？"。第二阶段（Commit）：如果所有人都说能，协调者发送 Commit；否则发送 Abort。2PC 的问题在于它是阻塞协议：如果协调者在发送 Commit 之前挂了，参与者不知道该提交还是回滚，只能等协调者恢复。MySQL 的 XA 事务就是 2PC 的实现。

"2PC 是分布式事务的最低限度保证。它能防止不一致，但代价是阻塞和低可用。如果你的系统对可用性要求很高，2PC 可能不是好选择。"

Petrov 还讨论了Saga 模式：把一个大事务拆成多个本地事务，每个本地事务有对应的补偿操作。如果某一步失败了，执行已完成步骤的补偿操作来回滚。Saga 不提供隔离性，但可用性更好，适合最终一致性场景。

第12章：一致性与共识

这是全书理论密度最高的一章。Petrov 从FLP 不可能定理（异步系统中即使只有一个节点可能崩溃，也无法达成确定性共识）和 CAP 定理出发，讨论了共识问题的理论边界。

Paxos 是共识算法的鼻祖，但以难懂著称。Petrov 用了比较简洁的方式解释了 Paxos 的核心：通过 Proposer、Acceptor、Learner 三个角色，用多数派投票来保证一致性。Multi-Paxos 通过选出一个稳定的 Leader 来减少共识轮次。

Raft 是为了解决 Paxos 难懂的问题而设计的。它把共识拆成了三个子问题：Leader 选举、日志复制、安全性。Raft 的状态机清晰（Follower → Candidate → Leader），日志复制逻辑直观，因此被 etcd、Consul、TiKV 等项目广泛采用。

| 共识算法 | 理解难度 | 性能 | 应用场景 | |---------|---------|------|---------| | Paxos | ⭐⭐⭐⭐⭐ | 高 | Google Chubby, ZooKeeper (ZAB) | | Raft | ⭐⭐⭐ | 中高 | etcd, Consul, CockroachDB | | Viewstamped Replication | ⭐⭐⭐ | 中 | 理论原型 | | Gossip | ⭐⭐ | 低 | Cassandra, Riak |

第13章：总结与展望

最后一章回顾了全书的关键结论，并展望了数据库的未来方向。Petrov 提到了几个趋势：HTAP（Hybrid Transactional/Analytical Processing）混合负载处理、云原生数据库、新型硬件（NVM、RDMA）对存储引擎设计的影响。

三、关键概念速查

1. B-Tree vs LSM-Tree

两种主流存储结构的权衡。B-Tree 读快写慢，LSM-Tree 写快读慢。选择取决于你的工作负载：读多选 B-Tree，写多选 LSM-Tree。

2. MVCC（多版本并发控制）

通过维护数据的多个版本，让读写操作不互相阻塞。PostgreSQL 在堆文件里存旧版本，InnoDB 在 undo log 里存。这是现代数据库高并发的基础。

3. WAL（Write-Ahead Logging）

先写日志再写数据。数据库崩溃恢复的基石。没有正确实现 WAL 的数据库，在断电时一定会丢数据。

4. CAP 定理与一致性模型

网络分区下，一致性和可用性不可兼得。但现实中的选择不是二元的——通过可调的一致性级别（QUORUM、因果一致性等），可以在两个极端之间找到平衡点。

5. Raft 共识算法

把 Paxos 的复杂逻辑拆解为 Leader 选举、日志复制、安全性三个清晰的部分。是目前工程实践中最流行的共识算法。

6. 读放大 / 写放大 / 空间放大

评价存储引擎效率的三个维度。B-Tree 写放大高（每次更新写多个页面），LSM-Tree 读放大高（查多个层级）和空间放大高（合并前旧版本占空间）。

7. ARIES 恢复算法

先 Redo 再 Undo 的崩溃恢复流程。几乎所有关系型数据库都基于 ARIES 或其变体实现崩溃恢复。

四、核心框架/模型

数据库存储引擎选型框架

                    你的工作负载是什么？
                          │
              ┌───────────┼───────────┐
              ▼           ▼           ▼
          读多写少      读写均衡      写多读少
              │           │           │
              ▼           ▼           ▼
          B-Tree      看具体比例    LSM-Tree
          (MySQL,     和数据量      (RocksDB,
           PostgreSQL)              Cassandra)
              │           │           │
              │           ▼           │
              │      数据量大吗？      │
              │       │      │       │
              │      是      否      │
              │       │      │       │
              │       ▼      ▼       │
              │    分区    单机      │
              │       │      │       │
              └───────┴──────┴───────┘
                       │
                       ▼
              需要强一致性吗？
              │           │
             是           否
              │           │
              ▼           ▼
         主从复制 +    无主复制 +
         Raft/ZAB      最终一致性

事务隔离级别决策模型

你的业务容忍脏数据吗？ ─── 是 ──→ Read Uncommitted（几乎没人用）
              │
              否
              │
你的业务容忍读到不同版本吗？ ─── 是 ──→ Read Committed（PostgreSQL 默认）
              │
              否
              │
你的业务容忍幻读吗？ ─── 是 ──→ Repeatable Read（MySQL 默认，InnoDB 防幻读）
              │
              否
              │
你能接受性能下降吗？ ─── 是 ──→ Serializable
              │
              否
              │
         考虑乐观并发控制或业务层面加锁

分布式系统权衡三角

           一致性 (Consistency)
              /\
             /  \
            /    \
           /      \
          /        \
         /          \
        /____________\
可用性 ←──────────→ 分区容忍性
(Availability)      (Partition Tolerance)

CAP 定理说三条边不可能同时满足。但实际工程中，分区容忍性是必须的（网络一定会出问题），所以选择其实是 C vs A。而现代数据库通过可调一致性级别，让这个选择变成了一个滑块，不再是非黑即白的开关。

五、金句摘录

"数据库系统的复杂性来自两个独立的维度：数据在逻辑上如何组织，以及数据在物理上如何存储和分发。"

"在 B-Tree 和 LSM-Tree 之间做选择，本质上是在读放大、写放大和空间放大之间做权衡。没有免费的午餐。"

"WAL 是数据库持久性的最后防线。如果你不 fsync 日志，那你所有的持久性保证都是空中楼阁。"

"并发控制不是免费的午餐。更高的隔离级别意味着更多的锁争用和更低的吞吐。"

"2PC 是分布式事务的最低限度保证。它能防止不一致，但代价是阻塞和低可用。"

"复制的核心矛盾是：你想要强一致性，就必须忍受高延迟和低可用；你想要高可用，就必须接受数据暂时不一致。"

"FLP 不可能定理告诉我们：在完全异步的系统中，即使只有一个节点可能崩溃，也无法在有限时间内达成确定性共识。这不是工程问题，这是数学事实。"

六、行动清单

每天

[ ] 写代码时想想你正在用的数据库，这次操作是读多还是写多？B-Tree 还是 LSM-Tree 更合适？
[ ] 看到 SELECT * 时提醒自己：范围扫描会扫到 B-Tree 的多个页面，想想缓冲池命中率
[ ] 代码里用到事务时，问自己：这个事务真的需要 Repeatable Read 吗？Read Committed 够不够？

每周

[ ] 用 EXPLAIN ANALYZE 分析一次慢查询，对照 B-Tree 索引结构理解为什么慢
[ ] 读一篇数据库内核相关的博客或论文（RocksDB 官方博客、CMU 15-445 课程笔记都是好来源）
[ ] 审查项目中的数据库配置：innodb_flush_log_at_trx_commit 设的是什么？能接受它的数据丢失风险吗？

每月

[ ] 跑一次数据库基准测试（sysbench 或 YCSB），对比不同参数下的吞吐和延迟
[ ] 读一个开源数据库的一个模块源码（比如 RocksDB 的 compaction 或 etcd 的 Raft 实现）
[ ] 复盘一次线上数据库问题，从存储引擎层面分析根因，而不是只看慢查询日志

七、一句话总结

这本书告诉你数据库不是魔法，而是一堆精心设计的工程取舍——理解了 B-Tree 和 LSM-Tree 的权衡、MVCC 的代价、WAL 的必要性、Raft 的简洁，你就具备了看穿数据库选型争论的技术底气。

八、读者热议

1. "这本书应该叫《为什么 MySQL 不是万能的》"

很多读者表示，读完这本书最大的收获不是学会了什么新技术，而是打破了对关系型数据库的盲目信任。B-Tree 不是唯一的存储结构，SQL 不是唯一的查询方式，强一致性不是唯一正确的一致性级别。当你理解了底层机制，选型就变成了理性的工程决策，而不是"我们团队一直用 MySQL"的惯性。

2. "LSM-Tree 那几章值回票价"

不少做后端的工程师反馈，他们公司用 Cassandra 或 RocksDB，但之前根本不理解 LSM-Tree 的合并机制。读完第6章之后，终于明白为什么写吞吐高但偶尔会出"合并风暴"（compaction storm），也知道了怎么通过调整合并策略和布隆过滤器来缓解问题。这部分内容直接转化成了生产环境的性能调优方案。

3. "Raft 比 Paxos 好懂一万倍，但这章可以更详细"

Raft 章节受到好评，因为 Petrov 把 Leader 选举、日志复制、安全性拆解得很清楚。但也有读者觉得这章偏短，建议配合 Raft 论文和 etcd 源码一起读。一个普遍的建议是：先读 Raft 论文（14页，很简洁），再读这章作为补充，然后去看 etcd 的 raft 包实现，效果最好。

笔记生成：2026-04-28 by 喵喵 🐈

📚 喵喵的笔记库

探索