Paxos算法深入分析.doc

Paxos算法深入分析夏超伦,盛浩,刘森一算法背景问题分析 3二算法介绍与分析 10三算法的思考及优化 12参考文献 (决议)达成一致[1]。一个典型的场景是,在一个分布式数据库系统中,如果各节点的初始状态一致,每个节点都执行相同的操作序列,那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列,需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。一个通用的一致性算法可以应用在许多场景中,是分布式计算中的重要问题。节点通信存在两种模型:共享内存(Sharedmemory)和消息传递(Messagespassing)。Paxos算法就是一种基于消息传递模型的一致性算法。BigTable使用一个分布式数据锁服务Chubby,而Chubby使用Paxos算法来保证备份的一致性[2]。,一般银行ATM系统的体系结构:C={c1,c2,…,cn}代表n个客户端(ci一个实例是取款机),S={s1,s2,…,sm}代表m个服务端(si响应每个与之相连的客户端的命令请求;Paxos算法运行的实体)。,所有的客户端仍能不受影响地进行工作。从而,本文讨论的一致性问题始终是在保证系统可靠性的前提下------因为解决一致性问题最简单而又最不明智的办法就是只设置一个数据处理端(在ATM模型中只存在一个S),这样永远都不会出现不一致的问题。由于C与S之间的通信是异步的,那么如果c1,c2,c3分别发出如下命令a,b,c,即operation(c1)=a,operation(c2)=b,operation(c3)=c,那么总共可能会产生=3!=6种合法命令序列,即(a,b,c),(a,c,b),…,(c,b,a)。本文不讨论不合法的命令序列,譬如(a,a,c),这在下文会给假设与解释(此外,如果a任务一定要在b之间执行,那么(b,a,c)此类序列也变得不合法。在本文中假设a,b任务之间是没有顺序制约的,可以想象成a任务为某一个用户在帐户A上进行一个取款操作,b任务为另一个用户在帐户B上进行一个存款操作,由于A,B是两个不相同的帐户,所以a任务的执行与b任务的执行不相关)。如果S中的每一个服务端执行了不同的合法命令序列,将会导致整个系统的不一致性问题,所以Paxos的任务是保证S中每一个处于正常工作的服务端都将执行一个相同的命令序列,例如(a,b,c)。:为了保证不出现一些不合法的命令序列,首先Paxos算法执行的环境应当处在一个可靠的通信环境中。即在异步通信过程中,发送的数据可能会被丢失(lost)、延长(delayed)、重复(duplicated)[4],但不会出现被篡改。前提2:任意一个算法运行的实体(例如ATM系统中的S)不会出现拜占庭将军问题(Byzantinefailure)[5],可以简单地理解为结点群在决定命令序列的过程中没有结点受病毒、黑客影响。,在这里把一个结点的所有行为概括成3种角色:Proposer,Acceptor,Learner。可以认为在一个结点中Paxos算法的行为可以被独立地分成3种对象来执行,对象之间的交互是统一的。其中:eptor提交提案(proposal),提案中含有决议(value)。Acceptor审批提案。Learner执行通过审批的提案中含有的决议。。我们使用数学归纳法的思想来保证如何只确定一个决议被批准::一个决议(value)被“批准”,当且仅当含有该决议的提案(proposal)被大多数(majority)eptors所“接受”:某个决议v被批准后,接下来(a)没有任何提案被接受;或者(b)只有包含决议v的