上午写的设计，下午被自己的基准推翻
存储引擎里，段表记录每个段（数据文件）的状态、边界和区间占用，架着三条水位线（最小地址 / 已提交尾 / 已分配尾）。所有地址分配、租约、恢复都要经过它。
它是整个项目最朴素的一个数据结构：一个紧凑的段数组 + 一个 segId → 下标 的索引数组。查询就是两次 volatile 读加一次数组索引：
var index = Volatile.Read(ref _segIndex);
var idx = (uint)segId < (uint)index.Length ? Volatile.Read(ref index[segId]) : -1;
return idx >= 0 ? Volatile.Read(ref _segments)[idx] : Segment.Hollow;但它不是一开始就这么简单的。它变成这样，是被实测反复打出来的。这篇讲两件事：段表数据结构经历的几次反复，以及”最简单的算法为什么快”——以及为什么这件事总被低估。
反复一：全局红黑树，只活了一天
段表的设计一度走到”全局统一”的方向：用一个全局红黑树 + 序列锁取代每段独立的结构——为这条路线重写了一份设计文档，光是”完整不变量清单”就列了 37 条。理由听起来很正当：区间是全局的，跨段协调成本随段数增长，应该用一个全局有序结构统一管理。
当天下午，这个方向被基准数据推翻了：
| 区间数 N | 每段独立表（插入） | 全局红黑树（插入） |
|---|---|---|
| 100 | 82.8 ns | 135.1 ns |
| 1,000 | 70.3 ns | 208.4 ns |
| 10,000 | 75.8 ns | 335.9 ns |
并发下差距更大：4 线程时全局树的每次操作 1,315 ns——1 线程到 4 线程不升反降（全局锁把所有写串行化了）。内存 82 B/节点对 148 B/节点。
而推翻它的那句话，比数字更值钱：
全局树假设”跨段协调成本 O(段数)“是瓶颈。但原型基准证明每段 List 仅 1-5 项。
全局树的立论前提是对数据分布的想象，不是实测。真实负载里每个段的区间表只有 1-5 个区间——“跨段协调是瓶颈”根本不成立。于是每段一个独立的小结构（List + 二分 + 段锁）全面胜出，而且段间天然并发（不同段 = 不同锁）。
反复二：三层分层，实现时反向合并
第二次反复更微妙。设计稿把地址空间切成三层：段表是地基，水位线、租约、生命周期建在它上面。
第二天实现时走了反方向：水位线被并回段表。理由很干脆——“双尾水位线本质是段表内部状态（使用进度），必须和段表边界一起原子推进/回退”。
设计的三个组件，最后只有一个活了下来。这不是设计错了，而是”分层”这条抽象原则撞上了”原子性”这条更硬的需求：必须一起原子推进的东西，不能分在两个组件里。
反复三：密集数组，被 20GB 内存爆炸炸掉
一次测试死机暴露了内存问题：恢复时扫到一个稀疏的段文件——段号跨度 6000 万，实际只有 711 个有效段。当时的实现是密集数组（下标 = 段号偏移），于是给每个不存在的段都建了一个对象：20GB 内存爆炸。
修法是双数组：一个紧凑追加的段数组，加一个”段号 → 下标”的索引数组（只增不删，写一次后永不变）。索引每槽 4 字节，最坏情况约 157MB——比 20GB 好三个数量级。而且”写一次后永不变”这个性质顺手消掉了”索引失效”这一整类并发问题。
这次简化是对的。但它也埋了一根刺——见后面”代价”一节。
反复四：边界的两种写法
“恰好填满一段”的边界位置，曾经有两种线性等价但表示不同的形态并存：“段末之后第一个字节”和”段末”。
两种形态并存咬过人：重开时崩溃（元组比较越界，靠恢复补丁兜底）；更糟的是哨兵被当状态误读，逼出上层一堆”+1 页余量”的绕行代码。最后是这句反馈定的案：
“我的数据明明写的刚满，但是你给我的是下一段地址了。不应该是统一用段末这个表示吗？”
统一停驻”段末”，新算术永不产出下一段头。这次的教训在实施侧：设计稿里写着”不改”的形态敏感点，被全量测试又揪出 4 处——形态的消费面必须靠全量测试收口，不能只靠静态推演。
番外：一个自研锁原语的九天
段表的故事里还有一段支线：一个自研的复合锁字原语（CAS 互斥 + 读写锁 + 等待三职责合一）。
- 引入第二天：
Wait()里先释放排他锁再挂起，唤醒后重获——顺序错了，死锁； - 第三天：找到古老全进程死锁的真根因——共享读的计数用 OR 置位而不是 ADD，第二个读者释放时计数下溢，借位污染出假的”写者位”，所有读者和清理逻辑永久自旋楔死。这个 bug 是”压测长期不稳定”的真凶；
- 同天又一个：唤醒的脉冲打进空等待集，写者永久挂起（丢失唤醒窗口）；
- 第九天：整体删除。三职责交给现成的：读写锁用一个成熟的自旋读写锁，等待用
Monitor。
删除时的记录还带着一条方法论教训：之前有人”预感这个死锁与内存回收窗口同族”——证伪。跨系统归因之前，先抓现场。
最简单的算法为什么最快
段表最终形态的复杂度是单调下降的：每一次”变复杂”的尝试（全局红黑树、序列锁、单块紧凑布局）都被实测打回。为什么简单版本反而快？四条实证：
一、纳秒级的开销，淹没在微秒级的 IO 里
段表维护开销的专项基准：写入路径上段表的开销不可测——含段表维护的写 7,433 ns，不含的对照 7,698 ns，比值 1.04（在误差内），两者分配量相同。因为稳态开销 ≈ 一次字典读 + 一次 volatile 读 + 一次比较 ≈ 15 ns，是 7.4 µs IO 的 0.2%。
查询路径更明显：纯段表查询 2.16 ns / 1.06 ns（零分配），比原来”扫盘探针”的写法（查文件是否存在、取文件大小，两次系统调用）快 ~1000 倍。
当一个操作的耗时多两个数量级时，包在它外层的簿记工作根本不值一提。
二、紧凑 ≠ 快
水位线的内存布局，第一直觉是”三个 16B 拼成一个块，紧凑、局部性好”。实测（20 万次操作/线程）：
| 线程 | 共享缓存行 | 三个独立 | 独立快 |
|---|---|---|---|
| 1 | 7.48 ms | 5.18 ms | 31% |
| 2 | 8.03 ms | 4.50 ms | 44% |
| 4 | 47.18 ms | 29.01 ms | 39% |
| 8 | 111.09 ms | 66.61 ms | 40% |
后来又一次”合并成单个 128B 块”的尝试，同样被实测打回：2 线程吞吐 2.19M vs 1.35M ops/s。原因是 CPU 的空间预取器会绑定相邻缓存行——改一个水位线时，另一个被踢出缓存。
那句总结很到位：“紧凑 = 局部性好 = 快”对读多场景成立，但水位线是写多场景。
三、二分全废，裸枚举胜出
恢复时要找”最小/最大的段号”。听起来是经典的二分问题，但四个二分变体全废了，因为它依赖一个隐含假设：存在性单调——某个段号不存在，则比它大的都不存在。
反例：段号 100, 200, 500——500 是孤岛，不是任何区间的中点，二分永远踩不到它。不是写法问题，是二分对非单调存在性的根本局限。
最终方案是最笨的：枚举目录里的段文件，只记最小/最大两个标量。O(1) 内存、100% 正确（不假设单调性）。实测：
| 场景 | 实际段数 | 耗时 |
|---|---|---|
| 孤岛（段号 0 和 999999） | 2 | 0 ms |
| 稀疏（999 个删掉 90%） | 96 | 1 ms |
| 1000 段 | 1000 | 9 ms |
| 10000 段 | 10000 | 86 ms |
性能与实际段数成正比、与段号范围无关——稀疏场景（恰恰是最需要它的场景）极快。文档里留了一句话：“正确性 > 速度——恢复是关键路径，漏段比慢更严重。”
四、把”优化”移除，性能没变
高并发追加的扩展率探针测出来是反扩展的：1 线程 2.65M ops/s，4 线程 1.90M（0.72×），8 线程 1.67M（0.63×）。
于是做了个”优化”：把分配快路径里一次看似多余的原子操作换成稳定双读。结果实测零收益（0.70× / 0.62×，与基线持平）。归因很清醒：
扩展率上限 = 水位推进的那次 CAS——每笔必有、不可消除；被换掉的那个操作是叠加竞争，移除后主竞争仍在。
也就是说，那个”瓶颈”不是可优化项，而是这个数据结构的物理形态——除非改成分片分配器（架构级重构）。这条记为”证伪”，改动回滚。
反面：简单也有失效边界
“简单”不等于”能跑就行”。同一条线上有一次相反方向的裁定：区间检查曾想用 O(n) 全扫换取正确性——被否决，因为十万级空洞下每次检查线性退化到 200 µs+（把另一个方案 10-13 ns 的成绩拉低三个数量级）。裁定原话是”底层组件零性能税”。
段表最终选的双数组，妙处在于它同时满足两个条件：实现最简单 + 查询 O(1)。“简单胜出”的前提是简单的那条路径本身不引入渐进复杂度——一个 O(n) 的简单算法，在 10⁵ 量级就是税。
代价：简单的是算法，不简单的是发布顺序
最后是这段历史里最贵的一课。
稀疏双数组是一次成功的简化——内存模型简单了、并发复杂度低了。但它在 16 天后引爆了一次数据丢失事故：
索引扩容用的
Array.Resize——零初始化的新数组先可见、填充后可见。无锁读者在这个窗口里读到0（= 下标 0 的合法段）→ 判定”段存在”→ 跳过注册 → 尾水位穿过未注册的段 → 永久空洞 → 重开时在第一个空洞处截断，数据不可达（复现：1.2MB 丢 ~1.1MB）。
修复是教科书式的 build-then-publish：
// 新建 + 拷贝 + 先填充 -1，最后单点发布（Volatile.Write）
var grown = new int[newSize];
Array.Copy(_segIndex, grown, oldLen);
Array.Fill(grown, -1, oldLen, newSize - oldLen);
Volatile.Write(ref _segIndex, grown);当时的复盘留了两条，值得原样抄下来：
x64 处理器”按序可见”也救不了：读者见到字段 = 新数组时，其后的填充写入尚不可见。 教训：锁内代码的逻辑正确证明不了无锁读者看到的中间态；共享数组扩容必须 build-then-publish。
所以”简单”买到的是算法层面的简单。并发下的发布顺序、可见性、内存序——该付的账一分不少。段表现有的三条铁律（读者先想清楚能看到什么、共享数组 build-then-publish、16 字节裸读不得用于判定）全部是从这类事故里长出来的。
小结
段表的演进浓缩成三句话：
- 数据结构选型要看真实数据分布，不是复杂度想象。 全局红黑树输给了一个朴素事实：“每段只有 1-5 个区间”。
- 简单算法的性能常被低估，因为人们把”复杂”误当成”快”。 纳秒级簿记在微秒级 IO 面前是噪声；紧凑布局在写多场景反而更慢；枚举在稀疏场景完胜二分；移除”优化”性能不变。
- 但简单 ≠ 省事。 简单换来的是算法清晰，并发正确性的复杂度一分没少——它只是从”数据结构设计”转移到了”发布顺序纪律”上。
本文事实来自 TC.Tier 的地址空间设计文档、段表开销与布局基准、恢复算法专项基准，以及问题台账与提交历史。
评论