数据库存储 入门

我们 SELECT * FROM users WHERE id = 42 的 planner 已经决定用主键索引。 从这里开始,存储引擎的活儿是机械的:沿索引下行,找到装 row 42 的 heap 页, 读页,解码 tuple,交给 executor。要理解这步,得先理解页和 buffer pool。

页是一切的单位

数据库文件不是随机字节流,而是定大小页数组, 挑成磁盘扇区大小和文件系统块大小的小倍数:

• Postgres:8 KB 默认(编译期设定)。
• MySQL InnoDB:16 KB 默认(可配 4 / 8 / 16 / 32 / 64 KB)。
• SQL Server:8 KB 固定。
• Oracle:8 KB 默认,可配 2–32 KB。
• SQLite:4 KB 默认(可配 512 B – 64 KB)。

页是一切的单位:I/O 单位(一次读 / 写一页,不是一行)、 buffer pool 单位(一个条目缓存一页)、很多引擎上的锁单位、 WAL 日志记录单位(「页 X 的 100–116 字节改成 …」)。 页大小挑错了,整个引擎的性能都会偏。

Slotted page 布局

行是变长的,页是定长的。标准方案 —— Postgres、MySQL InnoDB、SQL Server、SQLite, 基本所有人都用 —— 是 slotted page:

+--------------------------------------------------------+ offset 0
| 页头                                                   |   24 bytes
|   pd_lsn  (WAL 位置)                                   |
|   pd_checksum                                          |
|   pd_lower (slot 数组末端)                             |
|   pd_upper (tuple 数据起点)                            |
|   pd_special、flags 等                                 |
+--------------------------------------------------------+
| Slot 0  →  offset 7900 (16 字节)                       |  slot
| Slot 1  →  offset 7820 (32 字节)                       |  数组
| Slot 2  →  offset 7760 (52 字节)                       |  向下
| ...                                                    |  生长 ↓
+----------------+---------------------------------------+ pd_lower
|                                                        |
|        自由空间  (pd_upper - pd_lower 字节)            |
|                                                        |
+----------------+---------------------------------------+ pd_upper
| ...                                                    |  tuple
| Tuple 2 (52 B): xmin xmax | id=42 | name='alice' |...  |  数据
| Tuple 1 (32 B): xmin xmax | id=41 | name='bob'   |...  |  向上
| Tuple 0 (16 B): xmin xmax | id=40 | ...                |  生长 ↑
+--------------------------------------------------------+ offset 8191

Slot 数组从头部往下长;tuple 数据从底部往上长;自由空间夹中间。 要找 row 42,引擎读 slot N(常数时间,因为 slot 条目 4 字节), 拿到 offset 7900 长度 16,解码那 16 字节。Insert 把新 tuple 塞进自由区顶部、加一个 slot。 Delete 把 slot 标死 —— 空间留给后面 VACUUM / 压缩回收。

每个 tuple 自带行头:Postgres 里是 xmin(插入它的事务)、xmax(删它的事务)。MVCC 可见性检查在解码时做 —— 所以同一页上能同时有 row 42 的多个版本。

大行:TOAST 和溢出页

Tuple 必须装在一页里。那 5 MB 文本列怎么办?每个引擎都有溢出方案:

• Postgres TOAST(The Oversized-Attribute Storage Technique): tuple 超过 ~2 KB,大属性先压缩,再切成 ~2 KB 块存到旁边的 pg_toast_* 表。主 tuple 留个指针。读时透明, UPDATE TOAST 列时痛苦(整个新版本被重写)。
• MySQL InnoDB:变长列超阈值就存到溢出页(一个或多个), 内联留 20 字节指针。

Buffer pool

从 NVMe 读 8 KB 大约 100 μs。从 RAM 读 8 KB 大约 50 ns。三个数量级。 所以每个数据库都维护一个内存里的页缓存 —— buffer pool —— 按 (relation_oid, page_number) 哈希:

Postgres:  shared_buffers       = RAM 的 25%(推荐起点)
           effective_cache_size = RAM 的 ~50-75%(planner 提示,不是分配)
MySQL:     innodb_buffer_pool_size = 专用机上 RAM 的 70-80%
SQL Svr:   max server memory       = 总 RAM - (~4 GB 留给 OS)
Oracle:    db_cache_size + sga_target / memory_target

OLTP 上 buffer pool 命中率目标:≥ 99%。
95% 听起来高,但意思是每 20 次读 1 次落盘 —— 比缓存路径 20× 延迟。

Postgres 比较特别:故意把 shared_buffers 留小,靠 OS page cache 兜底, 因为 Postgres 页住在普通文件里,OS 反正会缓存。MySQL InnoDB 反着来 —— 用 O_DIRECT + 巨大 buffer pool,这样 OS page cache 不会变成第二份拷贝。

页替换与 pin 计数

Buffer pool 有限,新页进来就得淘汰东西:

• Postgres:clock sweep。每个 buffer 有使用计数器(0–5); 一只旋转的「时钟指针」边走边减,遇到计数为 0 的就淘汰。便宜,近似 LRU。
• MySQL InnoDB:带中点插入的 LRU 变种 —— 新读进来的页插到 LRU 链表中点,不是表头。一次大顺扫不会把缓存「热」半边的 常用页冲掉。
• 正在用的页被 pin —— 引用计数, 查询读这页或后台 writer 刷它时不让淘汰。

脏页、checkpoint、后台 writer

UPDATE 改了页,该页在 buffer pool 里被标dirty。 每次 commit 都把所有 dirty 页刷回磁盘会很惨;实际:

1. 改动记到 WAL(Section 04 讲)。这才是让 commit 持久的东西。
2. 脏页本身留在 buffer pool 里,由后台 writer 匀速懒刷, 或在 checkpoint 时大批刷。
3. Checkpoint 刷所有当前脏页,这样 checkpoint 之前的 WAL 能回收。 触发条件:每隔 checkpoint_timeout(Postgres 默认 5 分钟) 或 WAL 装满 max_wal_size。

没调好的 checkpoint 会让内核 fsync 几 GB 脏页时把写阻塞几秒 —— 经典 Postgres 生产事故。Postgres 的 checkpoint_completion_target(默认 0.9)把写摊到大部分间隔上,平滑尖峰。

结构:宽、浅、全排序

B+ 树是一棵平衡 n 叉树:

• 内部节点装分隔 key 和指向子节点的指针。 它们做路由 —— 从不装行数据。
• 叶节点要么装行本身(聚簇索引,例如 MySQL InnoDB 主键), 要么装指向 heap 里行的指针(非聚簇,例如 Postgres)。
• 叶按 key 序连成双向链表。这就是 B+ 树里那个加号, 也是 WHERE id BETWEEN 40 AND 50 便宜的原因。

分支因子巨大:16 KB 页减去 header,除以(key 大小 + 指针大小)。 16 字节分隔 key + 8 字节子指针,在 16 KB 页里,fan-out 大约~600。这个 fan-out 下:

fanout = 600

深度    最大行数
  1       600              (根 + 600 叶)
  2       360,000
  3       216,000,000
  4       129,600,000,000  (1300 亿)

深度 4 的 B+ 树覆盖 10 亿行表。
Postgres 在 CREATE INDEX VERBOSE / EXPLAIN 时记录索引深度。
你基本不会在生产看到 depth > 5。

下行 —— SELECT id = 42 实际干了什么

1. 查索引的根页(总是已知 —— 存在系统目录里、pin 在 buffer pool 中)。
2. 在根的分隔 key 里二分查 42。沿指针走到下一层子节点。
3. 每个内部层重复。每步一次页查找 —— 几乎总是缓存命中,~150 ns。
4. 到叶。再二分查,找 key 42 的条目。聚簇索引:行就在那。 堆组织(Postgres):叶装一个 (page, slot) tuple ID; fetch 那个 heap 页,解码 tuple。

深度 4 + 全缓存:4 次页读 ≈ 600 ns。NVMe 上 heap 有一次落盘:≈ 200 μs。 完全冷缓存:≈ 1 ms。这三个数都可预测 —— 这就是 B+ 树赢的原因。

范围扫描 —— 双向链表叶

SELECT * FROM users WHERE id BETWEEN 40 AND 50: 下行一次找 40,然后沿叶链表往右走,直到 key 超过 50。 每行不重新下行。这就是 B+ 树在范围查询上吊打 hash 索引的原因 —— 也是 B+ 树索引上 WHERE created_at > ... 变成扫几个叶的原因。

分裂与合并

插入落到满叶时,引擎分裂它:分配新页、把一半条目搬过去、 把新分隔 key 推上去给父节点。如果父也满,父也分裂 —— 级联理论上能到根, 让树长一层。对称地,删除可能让叶下溢、和兄弟合并(有的引擎,比如 Postgres,这里偷懒,让页半空直到 VACUUM)。

分裂贵:重写两页、改第三页(父)、给所有三页都发 WAL 记录。 往乱序 key 大批插入,会得到稳定的分裂流;顺序插入打到最右叶,分一次再继续 (便宜得多)。这就是单调递增主键(时间戳、BIGSERIAL) 对 B+ 树比随机 UUID 友好得多的原因 —— UUID 把插入散到每片叶上、糟蹋 buffer pool。

并发:lock coupling 和 B-link 树

多个查询同时下行;一个可能在分裂,另一个在读。朴素加锁 —— 从根到叶每节点都拿写 latch —— 会让整棵树在每次修改时串行化。真实引擎用:

• Lock coupling / latch crabbing:先 latch 父、再 latch 子、 再放父。读用共享 latch;写用独占 latch。并发读互不阻塞;只锁正在分裂的路径。
• B-link 树(Lehman & Yao,1981;Postgres nbtree 用): 每个内部节点多一个 right-link 指针。一个读者到了一个正在分裂的节点, 能沿 right-link 找到缺失的 key,而不用从根重启。这样分裂时不用持父 latch —— 分裂对并发更友好。

Planner 挑别的的时候

B+ 树不是唯一的索引选项:

• Hash:O(1) lookup,但没范围、没序。 Postgres 有 hash 索引;极少是对的选择,因为 B+ 树点查实践中 n=4 已经 O(log n)。
• GIN(Generalized Inverted Index):给数组、JSONB、全文。 倒排:每个 token 映射到一组 row ID。
• GiST / SP-GiST:给几何 / 范围 / 自定义索引的框架 (PostGIS、exclusion constraint)。
• BRIN(Block Range INdex):给巨大、已排序表的小索引 (时序、append-only)。每个 block 范围只存 min/max —— 比 B+ 树小几个数量级,planner 只需要 skip block 时有用。
• LSM:不算纯索引,更像存储布局 —— Section 03 讲。

起源:O'Neil 等,1996(《Log-Structured Merge-Tree》)。 被 Google Bigtable(2006)、LevelDB(2011 开源)、再到 RocksDB(Facebook fork LevelDB,2012) 发扬光大并重塑。今天 LSM 是 RocksDB、Cassandra、ScyllaDB、HBase、InfluxDB、CockroachDB(基于 Pebble,LSM 重写)、以及大多数现代 KV 存储的底层布局。

基本形状

            ┌─────────────────────────┐
write ───►  │  WAL  (顺序文件)        │   持久性
            └─────────────────────────┘
            ┌─────────────────────────┐
            │  Memtable (skiplist)    │   最近写、在 RAM 里
            │  ~64 MB                 │   按 key 排序
            └────────────┬────────────┘
                         │ 满了 → flush
                         ▼
            ┌─────────────────────────┐
            │  L0:  SSTable SSTable … │   最近 flush(可能重叠)
            ├─────────────────────────┤
            │  L1:  SSTable           │   ~10× L0 大小、无重叠
            ├─────────────────────────┤
            │  L2:  SSTable           │   ~10× L1
            ├─────────────────────────┤
            │  L3:  SSTable           │   ~10× L2
            ├─────────────────────────┤
            │  ...                    │
            └─────────────────────────┘

写永远从上往下流。读检查每一层直到找到 key(或者层数用光)。 所有磁盘层都是不可变的 —— SSTable 文件一旦写下,绝不修改。 改动只能通过写新文件、最终把它们压缩到一起来发生。

写路径 —— 纯顺序

1. Append 一条记录到 WAL(顺序磁盘写)。
2. 插入 RAM 里的 memtable(skiplist 或红黑树,都 O(log n))。
3. 返回。写已持久(WAL)且可见(memtable)。

没 B+ 树下行、没页分裂、没随机写。NVMe + group commit 下,每写 ~10–50 μs —— 吞吐天花板是设备的顺序写速度,不是随机写速度。所以 LSM 在 benchmark 上能上 100K writes/sec/core,而 B+ 树在同硬件上很早就到顶。

Memtable flush → SSTable

Memtable 到了大小上限(RocksDB 默认 64 MB),被冻结,后台线程把它写成 L0 里一个不可变、已排序的 SSTable(Sorted String Table)文件。 新空 memtable 接班。SSTable 文件格式大致:

SSTable 文件布局
┌──────────────────────────────────┐
│ Data blocks (每个 ~4 KB)         │   key/value 对,已排序
│   block 0: keys aaa…abc          │
│   block 1: keys abc…ade          │
│   …                              │
├──────────────────────────────────┤
│ Index block                      │   每个 data block 一条
│   (last key, block offset)       │
├──────────────────────────────────┤
│ Bloom filter (~10 bits/key)      │   「可能有 / 绝对没有」
├──────────────────────────────────┤
│ Footer (offsets, magic, version) │
└──────────────────────────────────┘

Bloom filter 关键:每个 SSTable 一个,误判率调到 ~1%。点查先问 bloom —— 几次 hash、零磁盘 I/O —— 答「这文件绝对没有」就跳过整个 SSTable。 没 bloom filter 的话,每次读都要碰每个 SSTable。

Compaction —— 该交钱了

SSTable 会堆积。不清理:每次读都要碰几百个;删的 key 也永远不消失 (LSM 里删其实是墓碑 —— 一条「这 key 现在没了」的记录)。Compaction 是把 SSTable 合并、丢掉被覆盖和墓碑条目的后台进程:

• Size-tiered compaction(Cassandra 历史默认): L0 攒了 N 个大小相近的表就全合成一个大表。简单,但瞬时突增时读放大可能高。
• Leveled compaction(LevelDB / RocksDB 默认): 每层比上一层 ~10× 大;一层之内(L0 除外),key 范围不重叠。 一次合一块 L_i 进 L_(i+1)。读放大低(L0 之外每层 ≤ 1 SSTable),写放大高。
• Universal compaction、FIFO compaction: 调参变种。RocksDB 都暴露。

三种放大

LSM 性能用三个数描述,它们互相取舍:

读放大     = 每次逻辑读读的页数
              (LSM leveled: ~ L + 1)
              (B 树:        ~ 深度,≤ 4-5)

写放大     = 每字节用户写产生的实际磁盘写字节
              (LSM leveled: 典型 10-30×)
              (LSM tiered:  典型 5-15×)
              (B 树:        典型 1-2×)

空间放大   = 磁盘大小 / 逻辑数据大小
              (LSM leveled: ~ 1.1×)
              (LSM tiered:  ~ 2×)
              (B 树:        ~ 1.3-2×,碎片)

三个不可能同时最小。Leveled 压缩用写放大换空间和读放大最小;tiered 用空间和读放大换写放大最小; 按负载选。RocksDB 的旋钮(level0_file_num_compaction_trigger、max_bytes_for_level_multiplier、compaction_pri、rate_limiter_bytes_per_sec)都是在三个数之间移动。

读路径 —— 以及它怎么 stall

1. 查 memtable(RAM,微秒)。
2. 查每个 L0 SSTable(可能重叠)。先 bloom filter;正就读 SSTable 索引,再读数据块。
3. 每个下层:bloom filter 查 key 范围覆盖的那一个 SSTable;正就读索引、再读数据块。
4. 找到最新版本(或墓碑)就返回。

最差:每层 bloom filter 都误判 → 读放大 = 层数。生产里常见的失败模式: compaction 队列涨得比 compactor 排得快、L0 攒了几十个 SSTable, 点查现在要查 30+ 文件而不是 4–5。延迟尖峰 —— 但写吞吐看起来还健康。经典 LSM 调试故事。

什么时候选哪个

• B+ 树:关系 OLTP,读写混合,点查 + 范围都频繁, 写放大容忍度低。Postgres、MySQL —— 你的事务系统记录。
• LSM:写多的摄入(指标、事件、日志)、有 bloom filter 的 KV 查、 容忍压缩 CPU。嵌入式 RocksDB、时序的 Cassandra/Scylla、分析的 ClickHouse。
• 都用:越来越多混合设计。Postgres 有 zheap、 MySQL 实验过 LSM 列存、CockroachDB 选了 LSM(Pebble)因为分布式写重。 按表或按引擎选,不按语言选。

一句话规则

预写日志(WAL)意思是:数据页的任何修改在能到持久存储之前, 描述该修改的日志记录必须已经在持久存储上。 页修改可以晚刷、永不刷、或乱序刷 —— WAL 是规范真相。

为啥要这条规则、不是更简单的「直接写页」?因为页大(8–16 KB)、 在磁盘上随机、修改是小补丁(这 16 字节、那 4 字节)。 WAL append 是顺序的、跨多个事务批量、大小贴合修改本身。 WAL 上一次 fsync 提交几千个补丁;每个脏页一次 fsync 会压垮你。

一次 commit,一步步看

请求的 UPDATE 形式(UPDATE users SET email = ... WHERE id = 42),COMMIT 到响应回去之间实际发生:

1. Executor 在 buffer pool 里定位并改 heap 页。页现在在 RAM 里是 dirty。 磁盘上还没变。
2. 内存里 append 一条 WAL 记录描述改动:页 X、slot S、设字节 32-79 = ...。 每条记录带它修改的页的 LSN(Log Sequence Number)。
3. COMMIT 时 append 一条 commit 记录。WAL writer 把内存 WAL bufferwrite() 到磁盘,对 WAL 文件 fsync()。 fsync 返回了 COMMIT 才返回成功。
4. 脏数据页留在 buffer pool。几分钟后由后台 writer 或下次 checkpoint 刷。 按 WAL 规则这安全:崩了的话,WAL 回放会重建修改。

WAL 上的 fsync 是持久性瓶颈。带电池后备缓存的 NVMe:~50–500 μs。 没掉电保护的消费级 NVMe:5–15 ms。转盘:5–50 ms。 慢盘上每 commit 两次 fsync(Postgres 在 checkpoint 时还要 fsync 数据文件) 会把每连接的最大 commit 速率钉到约 100 TPS。

崩溃恢复:三个字母的 ARIES

Mohan 等,1992(ARIES paper)定义了每个现代关系数据库都实现某种变体的恢复算法。 在 WAL 上跑的三个阶段:

• Analysis。从上次 checkpoint 往后扫。 决定崩溃时哪些事务在飞(活跃事务列表)、哪些页 dirty(dirty page 表)。
• Redo。从 dirty page 表的最小 LSN 往后,回放每条 WAL 记录, 不管原事务有没 commit。把每页带到它最后记录的状态 —— 数据库现在就在崩溃时的位置,只是所有改动真的在磁盘上了。
• Undo。给崩溃时每个在飞(未提交)的事务,反着走它的 WAL 记录、 应用逆操作。Undo 之后,只有 commit 过的事务可见。

恢复时间和 checkpoint 之间的 WAL 成正比,不是数据库大小。 这就是 checkpoint 存在的原因,也是你调 max_wal_size /innodb_log_file_size 的原因 —— 它们界定恢复要多久。

Group commit —— 跟 fsync 悬崖搏斗

每次 commit 都需要 fsync。1000 连接每个 200 TPS,那就是 20 万 fsync/秒 —— 不可能。 解法是 group commit:把一次 commit 稍微 hold 一下, 让接下来几微秒里排队的其他 commit 搭同一次 fsync 的车。一次 fsync、多次 commit。 语义不变(每次 commit 还是等自己的数据持久)、吞吐陡涨。

Postgres 旋钮:commit_delay(fsync 前等多少微秒,默认 0)和commit_siblings(延迟生效前至少几个其他活跃事务,默认 5)。 MySQL InnoDB:flush 模式允许批量时的 innodb_flush_log_at_timeout。

你真能调的持久性旋钮

POSTGRES — synchronous_commit
  on            (默认)每次 commit fsync WAL。ACID 安全。
                代价:每次 commit 一次 fsync(NVMe 5-15 ms)。
  local         本地 fsync,但不等同步副本。
                副本延迟比持久余量更重要时用。
  remote_write  等副本写 WAL(不 fsync)—— 扛主库故障但扛不住主 + 副本同时崩。
  remote_apply  等副本 redo WAL —— 最强、最慢。
  off           批到 wal_writer_delay(默认 200 ms)。
                崩溃时可能丢 ~600 ms 已提交事务。
                别在生产用,除非你完全知道丢什么数据没事。

MYSQL InnoDB — innodb_flush_log_at_trx_commit
  1   (默认)每次 commit write + fsync log。ACID 合规。
  2             每次 commit write log、每秒一次 fsync。
                扛 MySQL 崩,不扛 OS / 硬件在 ~1 秒内崩。
  0             每秒一次 write + fsync。
                崩溃时可丢 ~1 秒已提交事务。

每个引擎 —— 盘的写缓存
  写完成上撒谎的盘缓存(便宜消费 SSD)会无形破坏持久性。
  用 diskchecker.pl / 带 fsync 验证的 fio 测,或用带掉电保护的企业盘。

复制和 CDC 都骑 WAL

WAL 不只是给恢复用。它是数据库状态变更的规范流,所以是自然的 feed,给:

• 物理复制:把原始 WAL 记录流到 standby;standby 按字节回放。 主版本要一致。Postgres 流复制、MySQL binlog + 位置式副本。 快,但 standby 是完美克隆 —— 没有按表过滤。
• 逻辑复制:把 WAL 记录解成行级事件(INSERT id=42、值是 {..})、发出去。 按表、跨版本,能跨主版本。Postgres 逻辑复制、MySQL 行式 binlog。 发布端 CPU 稍多。
• CDC / Change Data Capture 工具:Debezium、Maxwell、 Postgres 的逻辑解码插件。它们读 WAL、发 Kafka / Kinesis 事件。 每个 OLTP 数据库下游的「事件驱动」架构其实就是这么工作的。
• Point-in-time recovery:做一次 base backup,之后 archive 每个 WAL segment, 回放 WAL 到选定的 LSN 或时间戳。粒度是一条 WAL 记录 —— 实际就是按事务。

WAL 实际上是数据库对外的变更 API。把这点想通,「WAL 是 mutation 流、表是它的 accumulator」 —— LSM 和 stream-table 对偶都更说得通了。

Code review 红旗

• 生产环境为「性能」开 synchronous_commit = off /innodb_flush_log_at_trx_commit = 2。你拿 ACID 持久换了 ~10% 吞吐。Group commit 能把大部分换回来且不丢持久。 要是你真的不在乎丢最近一秒的写(分析摄入、尽力日志),明着说 —— 别把权衡藏在 config 里。
• shared_buffers 设成总 RAM(或 Postgres 上 90%+)。 没给 OS page cache、query sort 的 work_mem、连接内存、其它进程留东西。 Postgres 25% 是起点;MySQL InnoDB 70–80% 适用,因为 InnoDB 用 O_DIRECT、 跳过 OS page cache。
• LSM compaction 队列无限涨。写看着没事; 读悄悄退化,因为 L0 里塞了几十个 SSTable、每次点查都得过一遍。 监控 num-files-at-level0(RocksDB),设告警, 压缩崩盘前限流摄入。
• 低基数列上建 B+ 树索引(布尔、deleted_at、status_id 只有 4 个不同值)。 索引最后比它「帮」的表扫还大,planner 直接忽略它。 用部分索引(WHERE status = 'active')或干脆不建、让 seq scan 赢。
• 热行每秒被改几千次。计数器行、session token 行、「最后在线」时间戳。 每次 update 都发一条 WAL、把同一页弄脏;WAL 变瓶颈,锁争用勒死你。 换成按分区行加和的计数表(读时求和),或挪到 Redis、周期性回刷。