-
Notifications
You must be signed in to change notification settings - Fork 8
Wait Free Reads and Crash Safe
进程崩溃是进程在非预期的执行位置终止，包括软件故障以及 kill -9 / abort 这样的人为终止，操作系统仍在运行。硬件断电则会丢失内存及 PageCache（操作系统的文件页缓存）中尚未持久化的内容。这里讨论前一种情形下的结构可读性。
一个数据结构的写操作通常不是一条机器指令。插入一个 key，可能要分配节点、填写字段、修改父节点，再更新入口。若这些步骤直接改写读者正在访问的结构，任意两个步骤之间都可能出现只完成一半的中间状态。传统做法是用锁挡住读者，等写者恢复结构的一致性后再放行。
但读者等待写者会把写路径的延迟传到读路径：写者被抢占、缺页或者长期停顿，读者也随之停顿。提高并发读写性能，首先要回答一个问题：怎样让读者不接触中间状态，又不必等待写者完成？
一种答案是把“修改结构”和“让修改可见”分开。对于需要替换的局部结构，写者先在副本上完成修改，再用一次原子操作替换指向它的入口。这就是写时复制（Copy-on-Write，COW）与原子发布相配合的方式。这里的入口可以是父节点指向子节点的链接，不必是整个数据结构的根。
读者通过这个入口访问的，要么是修改前的完整结构，要么是修改后的完整结构。发布后，旧结构仍须保留到原有读者不再访问它，才能回收。先构造、再发布、后回收，让读者在任意时刻读到的结构都是完整的一致的。
flowchart TB
accTitle: 写时复制与原子发布
accDescr: 上下两幅对照：发布前，入口指向旧结构，新结构在旁构造；新结构完整后原子替换入口，发布后的新读者访问新结构，既有读者仍可访问旧结构。
subgraph before["① 发布前"]
direction LR
old["入口 → 完整的旧结构<br/>读者正常查找"]
building["新结构<br/>写者构造，尚未发布"]
old -.复制并修改.-> building
end
subgraph after["② 发布后"]
direction LR
current["入口 → 完整的新结构<br/>新读者正常查找"]
retained["旧结构继续保留<br/>供既有读者访问"]
current ~~~ retained
end
before -->|新结构完整后<br/>原子替换入口| after
保持结构一致，解决了读者能否访问有效数据的问题；读者能否独立完成查找，还取决于查找路径是否需要等待或重试。如果读者沿已发布的结构前进，不等待写者释放节点锁，也不因写者正在更新而重试，并能在有限的自身步骤内完成，那么即使写者停止，读取也能继续完成。这种性质称为读侧无等待（wait-free reads），符合 Herlihy 对 wait-free 的定义，但这里的保证限定在读侧查找。
允许并发写者在冲突时互相等待，就可以用锁协调相互关联的多步更新，无需保证每个写操作都能独立于其他写者完成。这大大简化了数据结构的设计，使读侧无等待能够应用于更广泛的数据结构。关键是将等待限制在写者之间，读者仍只访问完整的已发布结构。这是务实的工程哲学。
先明确局部替换必须满足的条件：新结构在发布前初始化完成；入口发布是具有正确内存顺序的原子操作；旧结构在读者不再访问后才被回收。
以一次局部结构替换为例，设旧结构为 S0，准备发布的新结构为 S1，指向它们的入口为 R。写操作可以停在任意指令之后，但入口只有两种可观察的状态：
- 写者尚未发布，
R仍指向完整的S0；新空间即使只写了一部分，也无法从R到达。 - 发布已经完成，
R指向初始化完成的S1；旧结构继续保留到既有读者结束。
原子发布是这两个状态之间的一次转换，不存在可被读者观察的半个入口。因此，无论写者停在哪一步，从 R 出发都只能读到已经发布的完整结构。
要将这一结论推广到整个数据结构，更新设计还必须保证每次局部发布都保持已发布结构的完整一致。在初始结构完整一致的前提下，经过任意次这样的发布，这个性质仍然成立。结合读侧无等待的查找路径，读者便能在写者停在任意一步时，独立完成对有效结构的读取。
现在让写线程停在某一步，永远不再执行。结构仍然可读，并发读者也不需要等待它恢复。若停止的不只是写线程，而是整个进程，原来的读者也随之消失：换一个进程来读取，前面的论证还能否成立？
新进程首先需要找到旧结构的字节。普通堆内存在进程退出后不再可供新进程访问；共享文件映射（file mmap，使用 MAP_SHARED）把结构放在操作系统 PageCache 管理的文件页中，进程退出后，数据仍可通过操作系统访问。它也不等于数据已经持久落盘。共享映射与私有映射的区别见 Linux mmap 文档。
字节保留下来，还要能重新定位节点。新进程重新映射同一个文件时，映射基址可能改变，原来的绝对指针因而不能直接使用。将节点引用保存为相对于映射基址的偏移，新进程就可以用新的基址加偏移重新定位。文件还需记录可识别的入口和有效范围，让新进程知道从哪里开始读取。
这样，字节保留与重新寻址两个问题都有了答案，才能把前面对并发读取的论证用于新的进程。
在上述条件下，两个场景可以逐项对应：
| 并发读写 | 进程崩溃后的读取 |
|---|---|
| 写线程停在任意指令 | 原进程停在同一条指令 |
| 共享内存中的已发布入口 | 文件中保存的入口偏移 |
| 同一进程的并发读者 | 重新映射文件的恢复进程 |
| 未发布、不可达的新节点 | 文件中未发布、不可达的字节 |
| 读者不等待写线程 | 恢复不等待已经消失的进程 |
重新映射改变了基址，但不改变偏移所表示的节点连接关系。恢复读者因而能够从保存的入口出发，沿同一份已发布结构读取。第四章已经说明，这份结构在写者停止时仍完整一致，而读侧无等待又保证读取不依赖原写者继续执行。因此，并发读者在写者停顿后仍能完成的读取，恢复读者在进程崩溃后同样能够完成。这就是读侧无等待与 crash-safe 在结构可读性上的同构。
这里的恢复只读取旧进程留下的结构，不在原结构上继续写入。原来的写侧锁即使未被释放，也不妨碍沿已发布入口读取：这与并发读者不等待写者解锁是同一个要求。
上述推导可以在两种不同的数据结构中找到具体实现。
基于 Patricia Trie（压缩前缀树）的 Crash-Safe Parallel Patricia（CSPP），最初的设计目标是高性能并发读写。它对需要替换的局部节点先完成副本，再原子发布新的节点引用；读者沿已发布关系查找。OffsetSkipList（OSL）则基于 SkipList（跳表），需要替换的版本数组同样先在新空间中构造，再以原子操作发布。两者的查找路径都不等待写侧锁，也不因写者尚未完成更新而重试。
两者都使用相对偏移表示节点引用，并支持 file mmap。先为高性能并发读取建立结构约束，再通过 file mmap 保留字节、通过相对偏移重新寻址，同一套约束便能用于进程崩溃后的读取，无需先修复写者尚未完成的局部修改。