paxos算法是一种基于消息传递的且具有高度容错性的一种算法，解决的问题是一个分布式系统如何就某个值达成一致。该算法的前提是假设不存在拜占庭将军问题。在该算法中一共有三种角色：proposer、acceptor、learner。proposer负责提出提案，acceptor负责对提案作出裁决，learner负责学习得到的提案。为了避免单点故障，会有一个acceptor集合，proposer向该集合发送提案，acceptor集合中的每个成员都有可能同意该提案且每个acceptor只能批准一个提案，当有一半以上的成员同意，则同意该提案。
主要过程如下：分为两部分，prepare阶段，accept阶段
prepare阶段：Proposer提出编号为Mn的提案，向acceptor集合发送prepare请求。acceptor做出反馈：保证不会再接收编号比Mn小的提案；如果acceptor已经批准过某提案，会向proposer返回已经批准的编号最大的提案的value值。
如果acceptor收到一个编号为Mn的请求且编号大于acceptor已经响应的所有prepare请求的编号，则它会将自己已经批准过的编号最大的提案值反馈给proposer，同时acceptor承诺不会再接收编号比Mn小的提案。（优化：忽略编号小于已批准的提案的请求）
如果proposer收到了集合至少一半的响应，则会发送一个针对Mn的Vn的accept请求给acceptor。Vn为收到的所有响应中编号最大的提案的值。如果响应不包括值，则可以由proposer选择任意值。
accept阶段：acceptor收到accept请求后，只要未收到任何编号大于Mn的prepare请求，则通过该提案。（accept阶段接受提案的要求）
Learn学习策略三种：
优化：为了避免死循环，比如两个proposer一次提出一系列编号递增的提案，可以产生一个主proposer，提案只能由主proposer负责提出。
关于paxos算法的应用：chubby（分布式锁服务、GFS中master选举）
网友评论