Paxos问题是指分布式系统中存在故障,但不存在恶意节点的场景(即消息可能丢失或重复,但无错误消息)下的共识达成问题,这也是分布式共识领域最为常见的问题。解决Paxos问题的算法主要有Paxos算法和Raft算法。
Paxos算法是分布式一致性算法,用来解决一个分布式系统如何就某个值(决议)达成一致的问题。但需要注意的是,Paxos经常被误称为“一致性算法”,但“一致性”和“共识”并不是同一个概念。Paxos是一种共识算法。
1990年,Leslie Lamport在其论文“The Part-time Parliament”中提出的Paxos共识算法,在工程角度实现了一种最大化保障分布式系统一致性的机制。Paxos算法被广泛应用于Chubby、ZooKeeper等分布式系统中。Leslie Lamport在论文中通过一个故事描述了Paxos算法问题:古代爱琴海的Paxos岛通过议会的形式修订法律,执法者在议会大厅中表决通过法律,并通过服务员传递纸条的方式交流信息,每个执法者会将通过的法律记录在自己的账目上,问题在于执法者和服务员都不可靠,他们随时会因为各种事情离开议会大厅,服务员也有可能重复传递消息,并随时可能有新的执法者(或者是暂时离开的)回到议会大厅进行法律表决,因此,议会协议要求保证在上述情况下能够正确地修订法律并且不会产生冲突。
Paxos是首个得到证明并被广泛应用的共识算法,通过消息传递来逐步消除系统中的不确定状态。其基本思路类似于两阶段提交:多个提案者先要争取到提案的权利(得到大多数接受者的支持);成功的提案者发送提案给所有人进行确认,得到大部分人确认的提案成为批准的结案。
Paxos算法有时也被称为Paxos协议,它是少数在工程实践中被证实的强一致性、高可用的去中心化分布式协议。Paxos协议的流程较为复杂,但其基本思想却不难理解,类似于人类社会的投票过程。在Paxos协议中,有一组完全对等的参与节点,这组节点各自就某事件做出决议,如果某个决议获得了超过半数节点的同意则生效。Paxos协议中只要有超过一半的节点正常,就可以很好地对抗停机、网络分化等异常情况。