数据库存储 入门

Row 42 不是存储引擎能寻址的东西。它能寻址的是heap 文件里的一页，以及页里的一个 slot —— 这两样合起来就是一个 tuple 的全部身份。走一遍这个文件：

注意这个地址是算出来的，不是查出来的：第 12 页从第 98,304 字节开始，因为每一页都一样大。本节其余部分都活在这条约束下 —— 变长的行必须塞进定长的盒子，而所有引擎的解法都一样，slotted page。

按真实比例画出来，一个 8 KB 的 Postgres 页是 24 字节页头、从页头往下长的 slot 数组、以及从另一头往上长的 tuple 数据。拖滑块往里装 104 字节的 tuple，看这两头怎么合拢：

注意页头存在的理由就是这条不变式：pd_lower ≤ pd_upper, 空闲空间正好是两者之差。每个 tuple 花 108 字节 —— 自己 104,slot 4 —— 所以装得下 75 个，还剩68 字节卡在那儿用不掉。推过 75，插入不会失败，它去另一页 —— 这就是表为什么是页数组，而不是一个装行的文件。

这页上的东西也从来不会被就地改。在 MVCC 下，一次 UPDATE 写一个全新的版本，把旧的标成死的; 新版本能不能留在这一页，由 fillfactor 决定。先定它，再更新这一行：

默认 fillfactor 是 100，页里没有余地，所以每次更新都落到别的页上，还要往表上每一个索引写一条。把 fillfactor 降到 90, 同样 8 次更新全变成 HOT —— 索引仍然指着旧的 line pointer, 由它转发，一个索引页都不用碰。

为什么是 8 KB？因为页是 I/O 的单位、缓存的单位、多数锁的单位、日志记录的单位，所以页大小一动，这四样一起动。把滑块走过这些引擎真正发布的 5 种大小，看点读和扫描怎么往相反方向拉：

因为点读为了一行 104 字节要搬整整一页， 4 KB 页把它放大 39 倍，64 KB 页放大 630 倍。扫描往另一边拉：同样 1 万行，4 KB 下是 271 次取页，64 KB 下是 17 次。 8 KB 和 16 KB 是两条曲线都还能忍的地方 —— 滑块上的引擎全住在那儿。

一个 tuple 必须装进一页，而 64 KB 的 JSON 文档装不进。Postgres 的答案是 TOAST: 超过阈值，值就离开这一页，留在原地的是一个 18 字节指针，指向兄弟表里的分片。把这个字段撑大，看它怎么走：

注意那条虚线阈值落在哪儿 —— 2032 字节，页的四分之一，不是页大小。过了它，值先压缩，再切成 1,996 字节的分片；64 KB 变成33 行分片。读是透明的。对 TOAST 过的列做 UPDATE 就不是：MVCC 要写一个新行版本，所以改一个字节要重写全部 33 个分片。

以上是磁盘。数据库之所以还能用，靠的是 buffer pool: 一张按 (relation, page) 索引、把页留在 RAM 里的哈希表。动一动命中率，看平均读里有多少是未命中、而不是命中:

注意到 99% 的时候柱子几乎全是玫红。命中 0.1 µs,NVMe 未命中 100 µs, 所以百里挑一的未命中已经把平均值顶到 1.10 µs —— 全缓存路径的 11 倍。 95% 「听着挺高」，量出来 5.10 µs：差 4 个百分点，却比 99% 差 4.6 倍。命中率不是一个线性旋钮。

池子是有限的，进来一页就得赶走一页。Postgres 用 clock sweep:一根指针绕着 buffer 走，一路把使用计数减一，碰到第一个已经是 0 的就拿走。走一圈看看：

注意它要走多久。第一圈一个都淘汰不掉，因为每个 buffer 至少被碰过一次；指针得整整绕一圈，牺牲者才存在。这正是要点 —— 这套扫描在不维护 LRU 链表的前提下近似了 LRU, 而维护那条链表意味着每次访问 buffer 都要加锁。

近似 LRU 有个著名的翻车。一次性的顺序扫描把读到的每页恰好碰一次，在朴素 LRU 下，每个被扫的页都挤掉一个热页。把扫描拉长，看热集合怎么死：

头部插入下，一次 16 页的扫描让 16 个热页一个不剩，而且这个故障是无声的：写没受影响，扫描本身还挺快，伤害要几分钟后在别的查询上表现成一级延迟台阶。换成 InnoDB 的中点插入，同一次扫描最多只能碰到链表末尾那 37% ——11 页无论扫多长都活着。

写不是发生时就落盘的。被改的页标成脏，留在池子里；真正把它们全赶出去的是检查点。checkpoint_completion_target 决定这次刷写能占掉多少个区间。把它拖下来，看刷写速率怎么把设备预算甩在身后：

4 GB 脏 buffer 摊在 5 分钟区间的默认 0.9 上是 15 MB/s —— 在预算内，看不见。同样 4 GB 摊在 0.05 上是 273 MB/s，而设备给不出来：内核卡在 fsync 里，所有前台查询排在它后面一起卡住。这就是那个经典的 Postgres 检查点停顿，它是配置 bug，不是硬件 bug。

B+ 树不是「多绕几步的二叉树」。它是节点即页的树，一个节点能带多少孩子，取决于一页装得下多少。这一点要紧，因为一次查找的代价是碰过多少页，不是做过多少次比较 —— 而这正是二叉索引当场输给 B+ 树的地方：

看着表变大，差距怎么拉开。到十亿行，二叉索引深 30 层，B+ 树深 4 层 —— 同一个答案要读 7.5 倍的页，因为二叉的每一层只买到 1 个比特，B+ 树的每一层买到 9 个。

所以扇出是算出来的，不是设计出来的。一个 key 加一个 8 字节下行指针再加 4 字节 slot 是一条；节点能装的条数就是可用页除出来的数。两个滑块都动一动，看扇出跟着走：

16 KB 的 InnoDB 页配 16 字节 key，每节点 584 条。注意key 宽度砸得多狠：64 字节 key —— 比方说拿 VARCHAR 当主键 —— 同样一页掉到 215 条。同样的索引字节数，扇出只剩三分之一，而这正是一个宽自然键长出额外一层树的地方。

因为每一层都乘一次扇出，深度按以 584 为底的行数对数增长。把行数抬过 12 个数量级，数数新的一层多久加一次：

4 层能寻址 1,160 亿行。这就是「它到底能多深」在生产里的答案：不深。十亿行的表从根到叶是 4 次读页，而根加它下面一层总共 585 页、9 MB，永远不出 buffer pool —— 所以实际上一次查找是 3 次缓存命中的探测，加一次可能 miss 的。

这正是 planner 选 users_pkey 时买到的东西。一步步走下行：已经跨过的层、正在搜的那一页, 以及最后那次彻底离开索引的取 heap:

注意最后一步读数怎么跳。4 次缓存探测是 0.60 µs;取 heap 如果 miss，是 100 µs —— 前面整段下行的 167 倍。这就是为什么两份看起来一模一样的 EXPLAIN 输出在运行时能差两个数量级，也是覆盖索引(答案就在叶子上)值这么多钱的原因。

而索引可以把这笔钱买回来：让自己的叶子顺便带上查询要的那几列 —— 一个 INCLUDE 列表。加几列，看索引怎么付账：

3 列全带上，100.6 µs 的查找就变成 0.60 µs 的 index-only scan —— 代价是索引从 18.7 GB 涨到 86.2 GB，因为每个叶子从装 818 条变成装 177 条。内部节点纹丝不动：INCLUDE 只加宽底部，所以树不会变深，只会变胖。

B+ 树里的加号是叶子被链起来了。范围查询下行一次，然后横着走。抬高上界，把一次下行加一段横走和hash 索引不得不做的事比一比：

2,000 行的时候，B+ 树读 15 页，hash 索引做 2,001 次独立查找，因为 hash 索引根本没有「下一个 key」这个概念。这就是有序索引的全部论据，也是 ORDER BY、MIN、MAX 和所有 keyset 分页在 B+ 树上白送、在 hash 上做不到的原因。

代价出在插入上。一条进一个还有空位的叶子 —— 直到没空位。往一个能放 8 条的叶子里推key, 看第 9 条怎么逼出一次分裂:

因为断页没法用增量修好，Postgres 对检查点之后第一次碰到的每一页，都会把整整 8 KB 的页镜像记进日志。普通插入大约 100 字节 WAL; 触发分裂的那次插入重写两个叶子加父节点，花16 KB —— 同样一行，贵 165 倍。

于是 key 顺序变成了一个吞吐决策。顺序 key 一次次落在最右边那个叶子上；随机 key 到处落。抬高插入条数，在顺序和随机 UUID之间来回切：

2,000 次顺序插入弄脏 10 个叶子页，吐出 275 KB WAL。同样 2,000 次换成随机 UUID，弄脏 1,648 个 —— 5,000 叶子索引上的 coupon-collector 期望值 —— 吐出 13 MB。日志量 49 倍，复制带宽 49 倍，外加一整个装满「只碰过一次的页」的 buffer pool。用 v7 UUID，或者 bigint，或者认账。

还有一件事必须成立：一个读者正在下行，写者却把它脚下的节点分裂了。普通 latch coupling 在锁住孩子之前一直握着父节点；安全，但把整条路径串行化了。把读者走下去，再换一种树：

因为 Lehman 和 Yao 的 B-link 树给每个节点加了一个右链, 分裂之后才到的读者顺着一个指针横着走一步就行，不用从根重来。Postgres 的 nbtree 就是为这个才做成 B-link 树：分裂过程完全不需要握父节点的 latch, 于是写者不再在下行路上挡住读者。

两种结构回答的是同一个问题 —— 这个 key 住哪儿 —— 只是政策相反。B+ 树维护一个有序结构，原地改它；LSM 维护很多个，一个都不改，过后再合并。给两边发同样 12 次写：

注意这些写落在哪儿。原地改的话，12 次写散到 9 个不同的页上，每一个都是一次寻道加一次页重写。追加的话， 12 条在同一个文件里连着 —— 同样 12 个事实，只是按到达顺序记的，不是按 key 顺序。

于是写永远不寻道。它往日志追加、插进内存里的 memtable、返回；只有 memtable 满了，才有东西进到树里。把写入量拖上去，看SSTable怎么冒出来：

注意这条路上没有一步是随机的。RocksDB 默认 64 MB 的memtable 意味着每写 64 MB 刷一次，而一次刷写就是把一个已经有序的结构顺序写成一个文件。写的天花板是设备的顺序带宽，不是它的随机写 IOPS —— 在同一块 NVMe 上，这两者差大约一个数量级。

SSTable 不只是一堆有序字节。它自带一个索引块 —— 每 4 KB 数据块一条 —— 和一个filter 块, 两者都随文件一起长。把它撑大：

注意这些元数据有多便宜：64 MB 的表上，索引加filter 一共是文件的 1.8%, 而正是它们让一次查找能一次读中 16,384 个 4 KB 块里的那一个 —— 或者干脆一个字节都不读就跳过整个文件。

这些文件不能无限堆着，所以它们被组织成层，每层装上一层的 10 倍。抬高数据集大小，数数这要多少层 —— 少得出奇：

1 TB 是 L0 之下 5 层。这就是 B+ 树给过我们的同一个对数，只是底从 584 变成了 10 —— 这也正好解释了 LSM 的读为什么比 B+ 树贵，以及贵多少。 LSM 得多找几个地方，因为它有更多地方。

所以读要一路往下走。memtable，然后每个 L0 文件，然后每层一个文件 —— 每一站上，bloom filter要么白送你一次跳过，要么害你付一次真读盘。把这次查找走下去：

注意哪些站是白送的。bloom filter 不会产生假阴性，所以「不在」是终局，除了几次哈希什么都不花；只有「可能在」才碰盘。没有这些 filter, 每次读都得从每一层取一个块 —— 这个结构在任何深度上都没法用。

filter 也不白来：它们是 RAM，按每 key 多少位来算。饿着它们，把假阳性率抬上去，看白送的跳过怎么不再白送：

在 RocksDB 默认的每 key 10 位上，这个率是 0.82%, 横跨 6 层就是每千次查找白读 49 次盘，10 亿个 key 要 1.16 GB内存。降到 5 位，内存减半，率变成 9.1% —— 每千次白读 543 次。指数形式是 0.6185 的「每 key 位数」次方，所以每多一位，错误率就除以 1.6。

压缩就是赊账到期的地方。把一层并进下一层，大约要把下层重写 T 遍，所以写放大是 T 乘层数 —— 而读放大往另一边走。动一动倍数，再换个策略：

注意两根柱子往相反方向走，而且没有哪个设定能让它们都小。 leveled 在默认倍数 10 上是52 倍写放大、10 个文件要探;tiered 是 7 倍、55 个文件。真实的 RocksDB 量出来是 10–30 倍而不是 52, 因为动态层大小让中间那些层远低于名义容量 —— 但这笔交易的形状就是这样。

这给写入定了一条硬天花板，而越过它之后的故障就是 LSM 的生产事故。把写速率推过压缩能排掉的量，看L0怎么涨起来：

因为一块 600 MB/s 的设备在 52 倍放大下只能吸收11.5 MB/s 的用户写，高过这个数就开始积。到 50 MB/s,L0 在 60 秒内摸到 level0_stop_writes_trigger，写直接被堵死。而在触发线以下，故障是无声的、也更糟：写吞吐看着还很健康，每次点查却在悄悄探 40 个文件，而不是 10 个。

最后一条不对称。因为文件不可变，删除删不掉任何东西 —— 它写一个墓碑，说这个 key 没了。删几行，看数据库怎么变大：

空间只有等某次压缩把墓碑一路带到最底层才还回来，对冷数据而言这可能永远不发生。更糟的是范围扫描必须把范围里的每个墓碑都读一遍： Cassandra 在 tombstone_failure_threshold(默认 10 万)上直接中止查询，「我们删了些老数据」就是这样变成「那个 partition 现在一读就抛异常」的。

规则只有一句，没有例外：数据页的任何修改，在描述它的日志记录已经在持久存储上之前，不许到达持久存储。页之后可以晚刷、乱序刷、或者根本不刷 ——日志才是规范真相。

这条规则划算，前提是恢复能分辨一页里已经有什么。每一页都带着最后一条应用到它身上的记录的 LSN，重做会跳过所有小于等于它的记录。把恢复往前拖：

因为页里已经带着的那 4 条是被跳过而不是重新应用，把日志重放两遍和重放一遍得到的是同一页。正是这份幂等，让恢复自己崩了也能干脆重来一次 —— 否则一台在启动过程中挂掉的机器就再也起不来了。

值得亲手破坏这条规则一次，才看得出它为什么存在。选日志记录和脏页谁先落盘，再把崩溃挪到它们中间：

注意「页先」并不会大声失败。恢复启动，在日志里找不到关于那一页的任何东西，于是断定这页已经是对的 —— 一次改了一半的修改就成了数据库眼里的真相，而校验和失败是你唯一可能听说这件事的机会。「日志先」的崩溃很无聊，这正是重点。

有了这条规则，一次提交就是 4 步便宜的加 1 步贵的 —— 先是干活，然后是刷盘。走一遍，看时间花在哪儿：

注意柱子里 fsync 占了多少。改页、构造记录、追加提交记录，加起来 0.6 µs;fdatasync在本文最好的硬件上是 30 µs。数据库为了写得更快做的一切，都是在攻击那一段。

而那一段不是软件数字，它是日志底下那块设备的属性 —— 而且能差两个半数量级。走过 4 种设备，读出每一种定下的天花板:

因为一个会话提交不可能快过一次 fsync,天花板就是 1 ÷ fsync: 带掉电保护的 NVMe 上每秒 33,333 次，7,200 转磁盘上 120 次 —— 那是盘片转一圈，8.33 毫秒，再怎么调也钻不到它下面。不带掉电保护的消费级 NVMe 落在 1,000，因为它的 flush 得排空板载 DRAM 缓存，而企业盘可以安全地忽略这一步。

一秒 120 次提交没法用，所以没有引擎接受它。一次 fsync 还在飞的时候到达的提交，搭下一班车。抬高会话数, 看fsync 速率怎么纹丝不动：

因为刷是共享的、等是各等各的，同一块盘上 64 个会话用 120 次 fsync 退役了每秒 7,680 次提交 —— 而且每一次都真的等到了自己的数据持久化。组提交在不动语义的前提下买到吞吐，所以它默认开着，也所以 synchronous_commit = off 几乎从来不是写瓶颈的正确答案。

日志的另一个消费者是备库，而 synchronous_commit 决定一次提交要在这条管子上等到多远。把备库挪远，再换档位：

注意 local 完全不动：它根本不出这台机器。同区域的 remote_apply 是 5.06 毫秒 —— local 的 165 倍 —— 因为提交现在既要等一个往返，还要等备库把那条记录重放完。这就是备库上「读到自己刚写的」这个保证的来源，也是它的全部价钱。

日志还有第二份工作：崩溃是靠它修的。ARIES 用 3 遍扫过上一个检查点之后的记录 —— 只有最后一遍碰从没提交的东西。跑一遍：

注意重做把所有东西都重放一遍，不管提没提交。它必须这样：这一遍要把数据库还原到崩溃那一刻的精确状态，之后回滚才能把从没提交的撤掉。想一遍搞定，就得在读到那条决定命运的记录之前就知道每个事务的命运。

所以恢复时间由日志有多少决定，不由数据库有多大决定。max_wal_size 就是那个旋钮。抬高它，看重做怎么变长，而检查点怎么变稀：

在默认的 1 GB 上，重做在 Postgres 给它的那一个核上按 80 MB/s 算是 13 秒。到 16 GB 是 205 秒 —— 三分半钟的停机，换来的是检查点数量的十六分之一，因而全页镜像也只剩十六分之一。这才是这个旋钮背后真正的交易，而它是一个恢复目标决策，不是性能决策。

这就说到了大家真正会去拧的那个旋钮。synchronous_commit = off 不再等 fsync，照样返回成功。动一动 wal_writer_delay, 读出一次崩溃会带走什么:

在默认的 200 毫秒上，暴露窗口最多是 3 个延迟 —— 600 毫秒 —— 按我们刚量出来的每秒 7,680 次提交算，那是 4,608 个已经告诉客户端提交成功的事务。没有任何东西损坏：数据库回来时是一致的，只是干脆忘了它们。这个设置是在「丢掉最后半秒真的没关系」的时候用的，绝不是因为某张图看着更好看。

值得背下来的是第三级到第五级那一跳：读一页是微秒，磁盘转一圈是毫秒。这道坎之上你用内存预算来调；坎之下你是在挑硬件，任何配置文件都帮不上忙。

注意B+ 树只在最上面那根柱子上赢。按 key 顺序写，它每写 1 字节搬 1.8 字节，没有对手；换成随机 UUID，它搬 105 字节，比 leveled LSM 还差。决定权不在结构上 —— 在 key 顺序上，再往后才是「你养不养得起一个永不停的后台压缩器」。

最后一个危险信号长得最像「调优」。Postgres 的池子是穿过内核读的，所以它缓存的页通常也在OS page cache 里。多要一点机器，看同一份字节怎么被缓存两遍:

25% 上，双份缓存的重叠是 16 GB,内核那边还有 42 GB。推过 90%，排序和连接一点不剩，机器开始换页。InnoDB 那条 70–80% 搬不过来，是因为它用O_DIRECT，没有第二份拷贝要付钱。

• 为了「性能」把 synchronous_commit 设成 off。 组提交不丢持久性就能给你大部分。
• 随机 UUID 当主键。WAL 49 倍。UUIDv7 按时间有序。
• 对 LSM 写吞吐报警。该报的是 L0 文件数。
• 对 fsync 撒谎的盘缓存。 用真拔电测，别信 benchmark。