存储引擎与查询
0. 引言
分布式数据库的复制、事务、恢复等机制，最终都依赖单机存储引擎的能力：WAL 既是恢复的基础，也是逻辑复制的数据源；索引结构决定了查询路径。理解存储引擎，是理解数据库性能与可靠性的前提。本文先给出"最小分布式数据库"的整体设计，再深入存储引擎类型、日志型存储的代价、分布式索引，最后展望计算存储分离与 HTAP 趋势。
1. 最小分布式数据库：三层架构
设计一个支持基本 CRUD、可水平扩展、节点故障不丢数据的分布式 KV 数据库，约束为：数据按 Key 哈希分片、每个分片 3 个副本、写入需多数派（Quorum）确认。其架构包含三层：
- 接入层（Proxy）：接收客户端请求，按 Key 定位分片；
- 协调节点：负责分片路由、事务协调，作为 Leader 将写入同步给副本；
- 存储节点：实际持有分片副本，由存储引擎落盘。
1.1 读写流程
写入流程（Put(key, value)）：
- 客户端向 Proxy 发起写入；
- Proxy 计算
hash(key)定位目标分片及其 3 个副本节点； - 协调节点作为 Leader 将写入同步给 3 个副本，等待多数派（≥2）确认；
- 多数派确认后，写入对客户端返回成功。
读取流程：同样定位分片，向多数派副本读取并取最新版本（基于时间戳或版本号）；读多写少时也可读单个副本以降低延迟。
该流程结合了分片与复制（详见《数据分布：分片与复制》）的思想，并通过 Quorum 在可用性与一致性间折中；副本故障时将其移出可用集合，剩余副本仍满足 Quorum，Leader 故障则触发选举接管分片（详见《分布式协调》章）。
2. 存储引擎的职责与三大类型
存储引擎是数据库负责数据落盘、读取与组织的底层组件，核心职责包括：
- 数据的物理组织（页、行、列）；
- 索引的维护；
- 写入缓冲与刷盘策略；
- 崩溃后的恢复。
主流存储引擎可按组织方式分为三类：
| 引擎类型 | 组织方式 | 优点 | 缺点 | 典型负载/代表 |
|---|---|---|---|---|
| B+ 树 | 叶子节点有序链表，支持高效范围查询与点查 | 读友好、范围查询强 | 随机写产生大量随机 I/O | 事务型、读多写少（MySQL InnoDB、PostgreSQL） |
| LSM-Tree | 写先入 MemTable，刷成有序 SSTable，读取合并多层 | 顺序写、写入吞吐高 | 读需合并多层（读放大），需后台 Compaction | 写密集、高吞吐（Cassandra、RocksDB） |
| 列式 | 按列存储，同列数据连续 | 高压缩比、聚合查询快 | 点查与单行写入效率低 | 分析型 OLAP（ClickHouse、HBase 列族） |
3. 日志型存储：LSM-Tree 的代价与收益
传统原地更新（In-Place Update）的 B+ 树存在随机写问题：一次更新可能涉及多次随机磁盘 I/O。日志型存储（Log-Structured Storage）将所有写都转化为顺序追加，充分利用磁盘的顺序写带宽，是 LSM-Tree 等现代引擎的基础。
3.1 核心思想
- 写入先进入内存的 MemTable（有序结构）；
- MemTable 达到阈值后，整体刷盘为不可变的 SSTable 文件；
- 读取时从 MemTable 与各层 SSTable 合并出最新值；
- 后台通过 Compaction 合并多层 SSTable，回收过期数据。
3.2 三类放大
日志型存储引入三类代价，工程优化围绕降低它们展开：
| 放大类型 | 定义 | 缓解策略 |
|---|---|---|
| 写放大（Write Amplification） | Compaction 时同一份数据被反复读写 | 调整分层大小比、合并阈值 |
| 读放大（Read Amplification） | 一次读可能要查多层 SSTable | 布隆过滤器、缓存、层级合并 |
| 空间放大（Space Amplification） | 过期数据在 Compaction 前仍占空间 | 及时 Compaction、分层策略（Leveled / Size-Tiered） |
3.3 与 WAL 的关系
日志型存储的"日志"思想与预写日志（WAL）一致：先写日志再改内存，保证崩溃后可重放恢复。WAL 是事务处理与恢复的基础（详见《事务与恢复》章），也是物理复制的数据源。
4. 分布式索引
数据被分片到多个节点后，分布式索引解决的是：如何快速定位目标数据，避免全节点扫描。无索引时，一次查询需广播到所有分片（Scatter-Gather），延迟与开销随节点数线性上升。
4.1 本地索引 vs 全局索引
| 维度 | 本地索引 | 全局索引 |
|---|---|---|
| 覆盖范围 | 仅覆盖本分片数据 | 记录每个索引键到分片的映射，覆盖全量数据 |
| 优点 | 构建与维护成本低，与分片生命周期一致 | 点查可一次定位目标分片 |
| 缺点 | 跨分片查询仍需访问多个分片，全局有序性需额外处理 | 写入需额外维护，存在索引与数据的一致性问题；索引本身可能成为热点，需再次分片 |
全局索引本身也需分片：按索引键哈希分片分布均匀但范围查询需访问多分片；按索引键范围分片范围查询友好但易热点。
4.2 二级索引的一致性与范围查询
在分布式数据库中，二级索引的更新与数据写入通常不在一个原子操作中，可能出现索引与数据短暂不一致。常见方案：
- 将索引作为本地索引，查询时各分片并行查再合并；
- 通过异步补偿（数据可靠传播与反熵）修复不一致。
范围查询在分片环境下需处理跨分片合并：若数据按索引键有序分片，可缩小扫描分片集合；否则需对所有分片执行查询并归并。
5. 主流引擎分类与演进趋势
5.1 三大系代表
- LSM-Tree 系：RocksDB（嵌入式 LSM 引擎，被 TiDB、CockroachDB 用作单机存储底座）、Bigtable / HBase（分布式列族）、Cassandra（去中心化 LSM，无主架构）；
- B+ 树系：InnoDB（MySQL 默认引擎，聚簇索引 + WAL）、PostgreSQL（堆表 + 索引，MVCC 实现）；
- 列式系：ClickHouse（MPP 列式）、Parquet / ORC（列存文件格式，常见于数据湖）。
5.2 计算存储分离与 HTAP
现代分布式数据库普遍采用计算与存储分离：计算节点无状态、弹性扩缩，存储层独立扩展、基于对象存储或分布式文件系统——代表如 TiDB（TiKV + 计算节点）、Snowflake、Amazon Aurora。
融合趋势：
- HTAP：同一引擎同时服务 OLTP 与 OLAP（如 TiDB 的行存 + 列存）；
- 内存 + 持久化：内存表加速，WAL 保证持久。
6. 小结
- 最小分布式数据库 = Proxy 接入层 + 协调节点 + 存储节点三层，Quorum 多数派确认保证不丢已提交数据；
- 存储引擎选型看负载：B+ 树（读多/事务）、LSM-Tree（写密集）、列式（分析型）；
- 日志型存储以顺序追加换写吞吐，代价是写/读/空间三类放大，WAL 是其与恢复、复制的连接点；
- 分布式索引：本地索引简单但跨分片慢，全局索引定位快但需解决一致性与热点；
- 演进方向：计算存储分离 + HTAP，让一套引擎同时服务事务与分析。
下一章讲解事务与恢复：分布式事务协议与崩溃恢复机制。