“Gilbert 与 Lynch 给出的严格形式如下:在允许网络分区(节点组之间的消息可被全部丢失)的异步系统中,不存在一个读写共享对象的实现同时保证:”
形式陈述 ​
网络分区是通信故障使进程集合在一段时间内分成无法相互传递消息的部分。对异步系统,有限但未知的长延迟与分区在观察上可能不可区分;分区是否最终愈合、是否单向、是否丢包由模型决定。进程本身可能仍运行,因此分区不同于节点崩溃。
直觉
分区把通信图暂时切成多个彼此不可达的子图,每一侧仍可能拥有活跃节点与过期副本。任何一侧都无法仅凭本地超时判断自己是多数、少数还是另一侧已经全部失效,因此允许各侧独立写入会产生冲突主权。协议通常通过多数交叠、租约或外部 fencing 把“能通信的岛”与“有权提交的岛”区分开。
例子与边界
跨机房链路中断时两侧节点均可服务本地请求,却不能同步。单个消息超时不能证明永久分区。脑裂是多个分区同时认为自己拥有主权的协议后果,不是分区定义本身。
五副本集群被切成三节点与两节点两侧,三节点侧可形成多数提交,二节点侧只能读取旧值或拒绝写入。若旧 leader 在二节点侧仍向外部存储发送命令,存储必须检查更高任期 token,否则网络恢复后会出现旧主写穿。单链路丢包可能绕其他路径恢复连通,并不构成图意义上的分区;实际系统也常是非对称可达,而非整齐的双向切割。
推论与应用
消息系统的通信连通性失效形成分区,quorum交集让至多一侧获得提交证书。CAP 定理讨论分区期间线性一致与每请求可用之间的取舍,Raft 和其他共识协议则选择少数侧停止进展以保存日志安全。冲突可合并数据类型采用的是另一种语义路线。
参考资料
- Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann, 1996,Chs. 1–25。
- Tushar D. Chandra and Sam Toueg, “Unreliable Failure Detectors for Reliable Distributed Systems,” Journal of the ACM 43(2), 1996,Full paper。