分布式共识

概述

分布式共识是分布式系统中的核心问题，指的是多个地理分散、通信不可靠、可能随时故障的计算节点就某个值或操作序列达成一致决定的过程。

关键内容

1. 问题定义：
2. 在由n个进程组成的异步分布式系统中，其中至多f<n/2个进程可能发生崩溃故障，消息可能丢失、重复或任意延迟，设计一个算法使得这些进程能够就一个值达成共识

3. 必须满足安全性(Safety)和活性(Liveness)要求

4. 安全性要求：

5. 合法性(Validity)：被选定的值必须是某个进程实际提出的值

6. 一致性(Agreement)：一旦某个值被选定，所有进程学习到的值必须相同

7. 活性要求：

8. 终止性(Termination)：系统最终会选定一个值，不会永远停滞

9. 在足够多的进程保持运行，且网络最终连通的前提下，系统一定会终止

10. 历史发展：

11. 20世纪80年代末，计算机系统从单机向分布式过渡，面临节点故障、网络故障等挑战
12. FLP不可能性定理表明在完全异步系统中确定性共识不可能，为该领域带来巨大挑战

13. Paxos算法首次提供了实用的解决方案

14. 实现方法：

15. 基于多数派机制，任意两个多数派必然有交集
16. 通过提案编号和承诺机制协调冲突
17. 使用状态机复制保证一致的状态转换

来源

• 18-lamport-paxos — 详细分析了分布式共识问题
• Paxos算法 — 共识问题的解决方案

相关

• Paxos算法 — solved_by
• Raft算法 — solved_by
• FLP不可能性定理 — relates_to
• 状态机复制 — implemented_by
• 多数派机制 — relates_to
• 拜占庭将军问题 — relates_to