1.Paxos算法 Paxos算法是Leslie Lanmport(2013年获图灵奖)在1990年提出的一种基于消息传递的共识算法(也称为,一致性算法),由于算法难以理解并没有被ACM TOCS发表。直到1998年,才引起人们的注意,Lanmport重新发表文章。为了便于人们通俗地理解Paxos算法,Lanmport于2001年简化原来的文章,发表了Paxos Made Simple,文章循序渐进地推导出了Paxos算法,并用数学归纳法进行了证明。在此基础上,本文结合Paxos Made Simple,与其他优秀的Paxos算法解读,重新描述Paxos协议,希望可以深入理解基本的Paxos算法理论。 Paxos算法解决的问题是一个分布式系统中如何就某个值(或协议)达成一致。在一个分布式系统中,如果各节点的初始状态一致,每个节点都执行相同的操作,那么他们最后的得到的也是一个一致的状态。一个分布式系统中,通常包含一个主节点和多个备节点。为了保证每个节点执行相同的操作指令,需要每一条执行执行一个“一致性算法”来选举出主节点,进而保证每个节点得到的指令一致。这是一个分布式系统中的重要问题。 2.基本概念 Paxos算法中有三种角色:Proposer, Acceptor, Learner。每个节点需要同时扮演 两种或两种以上的角色。 Proposal Value: 提议的值 Proposal Number: 提议编号,并且要求提议编号不能冲突 Proposal: 提议 = 提议编号 + 提议的值 Proposer: 提议发起者 Acceptors: 提议接受者 Learners: 提议学习者 需要说明的是,Proposer有两种行为,一个是向Acceptors发起Prepare请求,另一个是向Acceptors发起Accept请求。Acceptors则根据协议规则或(自身状态)对Proposers的请求做出应答。Learners根据Acceptors的状态,学习最终被确定的值。……

阅读全文