“Gilbert 与 Lynch 给出的严格形式如下:在允许网络分区(节点组之间的消息可被全部丢失)的异步系统中,不存在一个读写共享对象的实现同时保证:”
形式陈述
网络分区是通信被隔开,而不一定是机器停止运行。 在消息传递系统中,若进程集合在一段执行期间被分成两个或更多非空部分,部分之间的消息无法交付,便出现了网络分区。各部分内部仍可能正常计算、通信和接收客户端请求。
可以用通信图描述最简单的情形:顶点代表进程,边代表当前可用的通信连接。对无向网络,分区对应图失去连通性;一条链路断开但仍存在替代路径,不一定造成分区。真实故障也可能是单向可达、间歇丢包或随时间变化的隔离,不能一概画成两个内部完全连通的静态小岛。
讨论协议时,还要说明隔离允许持续多久。若所有消息最终都能送达,只是没有已知延迟上界,那是异步延迟;若模型允许某些跨区消息永久丢失,就必须考虑持续分区的执行。一个有限超时只能说明“目前没有收到”,不能把这两种情况可靠地区分开。[1]
直觉
沉默不说明故障,回执却可以提供证据
设五个投票副本的成员列表固定为
但若
崩溃故障约束的是进程此后不再执行;分区约束的是消息不能跨越某些边界。一个被隔离的旧领导者可能仍在运行,甚至仍认为自己是领导者。协议必须约束它能完成哪些操作,而不能只寄希望于它主动察觉隔离。
例子与边界
一次写入为什么会让另一侧的读取陷入两难
五副本最初都保存
| 时刻 | 三副本一侧 | 两副本一侧 |
|---|---|---|
| 分区前 | ||
| 写入完成 | 按协议提交 |
未收到更新 |
| 随后读取 | 可以在满足读协议条件后返回 |
本地仍只有 |
若写入已完成之后,另一客户端才向
少数侧可以等待通信恢复,或拒绝这类需要新鲜状态的读取;也可以通过另一个明确标注为陈旧读取的接口返回缓存。后者改变了接口承诺。一个及时返回的“服务不可用”错误,并不等于完成了 CAP 定义中要求成功响应的读写操作。持续分区下,这个不可区分性正是 CAP 定理的核心。[1]
多数派解决的是协调条件,不是所有故障
任意两个三成员子集必有交点,所以两个隔离部分不能同时各自取得五成员系统的新多数。但“有交点”还不够:交点副本必须遵守投票限制,保存必要状态,并在新领导者产生时传递已提交历史。Raft把这些要求落实为任期、选举限制、日志匹配和提交规则,避免不同多数在不同时刻批准互不兼容的历史。[2]
三副本一侧也不是一恢复内部通信就立即完成所有请求。它仍可能需要选举、日志追赶和一次安全的读取确认;活性还依赖调度、稳定通信与存储进展。两副本一侧则可能继续做不依赖全局协调的本地工作。“能运行”和“有权提交”是两回事。
分区也不必是
成员视图不一致时,稳定评分放置也只能各自按本地候选集合算出赢家:同一键在包含A的视图中可能选A,另一视图排除A后选B。两次计算都符合输入,仍未形成共同独占授权;哈希选择不替代本页要求的成员变更与确认协议。
推论与应用
法定人数系统把操作所需的共同证据明确化。实际设计应逐项说明写入、读取、选举各自需要什么确认,而不是用“支持分区容错”替代接口语义。
租约与 fencing token 处理的是另一层授权。租约要依赖明确的时钟和有效期假设;fencing token 则让资源接收方拒绝落后于已见令牌的旧请求。只有令牌单调生成、随操作传递且由实际资源校验,才形成隔离效果;它不会自动让所有远端机器立刻知道旧领导者已经失去资格。
分区恢复后,通信连通不代表状态已经收敛。日志型系统要追赶并处理未提交的分叉;允许并发写入的系统则需要规定合并、冲突呈现或人工裁决方式。选择什么恢复机制,取决于分区期间到底允许了哪些操作。
参考资料
- [1] Seth Gilbert and Nancy A. Lynch, Perspectives on the CAP Theorem, 2012,§§2–4:分区模型、不可区分性与不同操作的取舍。
- [2] Diego Ongaro and John Ousterhout, In Search of an Understandable Consensus Algorithm (Extended Version), 2014,§§5.2–5.4, 6:多数选举、日志安全与成员变更。