Database Systems Internals

这组材料表面上分散：有索引结构、哈希分布、Postgres 队列、以太坊执行客户端、以及 macOS 上的虚拟化。但把它们放在一起看，主题其实很统一：系统性能很少由“功能正确”决定，更多由内部组织方式、状态迁移成本、以及局部优化是否破坏整体平衡决定。

数据库和系统基础设施里，最贵的通常不是“做一件事”，而是“为了把这件事放进已有结构里，要多付多少隐藏成本”。B-tree 变体关注的是写入路径和页分裂；Rendezvous hashing 关注的是节点变化时如何少搬数据；Postgres 队列问题的本质不是能不能 SELECT ... FOR UPDATE SKIP LOCKED，而是高 churn 下 dead tuples 和 vacuum 能不能跟上；Reth 2.0 这种执行层系统，则是在吞吐、模块化和状态访问路径之间重新找平衡。连 “Apple Silicon/macOS 上跑 VM” 这种看似偏平台的话题，本质上也一样：抽象层一多，状态切换和资源隔离的成本就会变成一等公民。

这一组最值得抓住的共识

1. 好系统不是“快”，而是“重组成本低”

很多实现一开始都能跑，但一旦进入高频更新、高并发或节点频繁变动场景，真正决定上限的是重组成本。

• B-tree / Bf-tree 一类结构，核心不是查找复杂度写成 O(log n) 就结束，而是页布局、分裂、合并、缓存命中和写放大。
• Rendezvous hashing 的价值不在于“也能分片”，而在于成员变更时迁移量小，控制平面动作不会把数据面打爆。
• Postgres 队列看起来只是“插入、消费、删除”，但删除并不是真的立刻消失，而是转成 MVCC 下的 dead tuples，最后问题变成清理路径能不能追上生成路径。

一个简单例子：

• 天真的分片算法：hash(key) % N。当节点从 8 台变成 9 台，大量 key 都要重分布。
• Rendezvous hashing：每个 key 只需要选择“得分最高”的节点；新增节点后，理论上只有原本会输给新节点的那部分 key 迁移，扰动显著更小。

这类设计的共同目标不是“理论最优”，而是系统变化时不要全盘重排。

2. 逻辑上的删除，往往意味着物理上的拖尾

“队列在 Postgres 里也能做”这件事没错，但它最容易误导人的地方在于：应用层看到的是 job 被取走、被删除；存储层看到的是元组版本、可见性判断、索引项滞留、vacuum 追赶。

PlanetScale 那篇 Postgres queue 文章把这个问题讲得很清楚：

• 队列表是典型高 churn 工作负载：不断插入、取出、删除。
• 在 MVCC 下，DELETE 先把 tuple 标记为不可见，而不是立即物理清除。
• 如果 vacuum 跟不上，索引扫描会越来越多地命中“已经逻辑删除、但还得走一遍”的条目。
• 于是应用觉得“我明明只要取一条 pending job”，底层却在穿越越来越厚的历史垃圾层。

所以这里真正重要的不是 SQL 技巧，而是生命周期设计：

• worker 事务必须短；
• 长事务会拖住 vacuum；
• mixed workload（比如同库里还跑分析查询）会把问题放大；
• 某个模式在小规模下可接受，不代表它是长期稳定架构。

一个很实际的判断标准是：如果一个表“当前体积不大，但累计吞吐极大”，那就要优先怀疑清理和写放大，而不是先盯着单条查询延迟。

3. 数据结构选择，本质上是在选择失败方式

“Let’s Build a Simple Database” 这种材料的价值，不是教人再造一个玩具数据库，而是把很多工程师平时只在黑盒里使用的东西拆开：页、节点、序列化、游标、分裂、持久化格式。

一旦把数据库实现往下拆，就会发现每个选择都不是“更优雅”，而是“决定你以后会以什么方式痛苦”：

• 顺序追加简单，但读放大可能高；
• 原地更新直观，但并发和崩溃恢复复杂；
• 树结构查询快，但维护成本高；
• 日志结构写入友好，但 compaction 会吞掉后台资源；
• 单体索引容易理解，但热点页和 latch contention 可能早晚出现。

这也是为什么系统内部文章值得成组阅读：它们反复提醒同一件事——抽象接口隐藏了复杂度，但不会消灭复杂度；复杂度只会转移到账本的别处。

4. 高性能客户端和执行引擎，本质上也是“数据库问题”

像 Reth 2.0 这种内容，虽然名义上属于区块链执行客户端，但它面对的约束和数据库没有本质区别：

• 状态访问如何组织；
• 执行路径如何减少不必要复制；
• 模块化后边界是否清晰，还是只是把开销换成跨层通信；
• 数据摄取、索引、执行、持久化能否解耦而不失控。

如果把执行客户端看成“一个持续接收外部输入、维护巨大状态、需要可恢复且可验证的实时数据库”，很多设计就更好理解了。它和传统数据库共享同样的问题：缓存局部性、状态布局、写入节奏、后台整理任务、以及在高吞吐下如何避免某个子系统拖垮全局。

5. 平台/虚拟化问题提醒我们：抽象层本身也有成本模型

“AS VM on macOS” 这类材料放进这一组并不违和。因为它讨论的是另一个版本的同一问题：当你在宿主系统之上再叠一层虚拟化、再叠一层运行时，你获得的是隔离和可移植性，但也引入了新的边界成本。

对数据库或基础设施系统来说，这意味着：

• I/O 路径可能更长；
• 内存语义和页缓存行为可能不同；
• 时钟、调度、fsync、网络虚拟化等细节都可能改变基准表现；
• 你以为在优化应用，实际瓶颈却在宿主/guest 边界。

这提醒我们评估系统实现时不要只看算法，还要看算法落在哪个运行基座上。

具体例子

例子 1：为什么 Postgres 队列会“越用越慢”

假设有一个 jobs 表：

• 每秒插入 500 个任务；
• 8 个 worker 用 FOR UPDATE SKIP LOCKED 抢任务；
• 成功后立即 DELETE；
• 同一个库里还跑一个 20 分钟的报表查询。

应用层看，这只是普通异步任务系统。

存储层看：

• 每个删除都会留下 dead tuple；
• 长事务让 vacuum 无法及时回收；
• 索引叶子节点里还残留大量指向已删除 tuple 的入口；
• worker 每次取“下一条任务”，都要先踩过越来越多无效项。

结果是：业务方以为瓶颈在 worker 数量不够，实际上瓶颈在回收机制被事务可见性规则卡住。

例子 2：为什么 Rendezvous hashing 对动态集群更友好

假设缓存集群从 4 台扩到 5 台。

• 用 hash(key) % N：几乎所有 key 的归属都可能变化，冷启动和回源压力会同时爆发。
• 用 Rendezvous hashing：每个 key 只重新比较一次“新节点是否赢过旧节点”，只有一部分 key 迁移。

这背后体现的是系统设计里的常见优先级：不是让静态状态更完美，而是让变更事件更便宜。

例子 3：为什么“自己写一个简单数据库”仍然值得

很多人第一次实现 pager + leaf/internal node 分裂之后，会立刻理解一件事：数据库不是神秘黑箱，它只是把一串极其具体的取舍封装得很好。

一旦亲手写过：

• 你会更警惕 schema 或索引设计带来的页分裂；
• 你会更理解为什么某些查询“理论上不大”，但实际 I/O 很差；
• 你也会更容易读懂生产系统里关于 compaction、vacuum、checkpoint、buffer pool 的讨论。

这组内容的实用结论

如果最近在读数据库/系统实现，我会把这组材料压缩成三条操作性很强的判断：

1. 先问清理成本，再问功能是否可行。 任何高 churn 设计，只要涉及版本链、索引残留、后台回收，就不能只看前台吞吐。

2. 先问变更扰动，再问稳态性能。 分片、路由、索引、模块边界，都要看系统变化时会不会大面积重排。

3. 先问状态布局，再问抽象是否优雅。 数据怎么落盘、怎么进缓存、怎么跨层传递，往往比 API 看上去是否漂亮更决定真实表现。

Representative links / tickets

• Bf-trees — 围绕 B-tree 变体、页组织与写路径优化的实现思路。
• Rendezvous hashing — 经典分布式放置算法，重点是低扰动重分布。
• Let’s Build a Simple Database — cstack 的数据库实现教程：https://cstack.github.io/db_tutorial/
• Keeping a Postgres queue healthy — PlanetScale，讲 Postgres 队列表在 MVCC / vacuum / dead tuples 下的真实成本：https://planetscale.com/blog/keeping-a-postgres-queue-healthy
• Reth 2.0 — 高性能执行客户端的架构演进，可作为“状态系统工程”来读。
• AS VM on macOS — 从 Apple Silicon / macOS 虚拟化角度理解运行基座对系统行为的影响。