Paxos算法处理的问题.DOC

Paxos算法深入分析 夏超伦，盛浩，刘森 一 算法背景问题分析 2 1.1 Paxos算法处理的问题 2 1.2 不一致性问题的产生 2 1.3 算法的一些前提 3 二 算法介绍与分析 3 2.1 算法详细描述 3 2.1.1 角色分类 3 2.1.2 核心思想 4 2.1.3 Proposer行为分析 5 2.1.4 Acceptor行为描述 5 2.1.5 Learner行为描述 5 2.1.6 整体描述 6 2.1.7 算法总结 6 2.2 算法伪代码描述 6 2.3 算法运行实例 9 2.3.1 结点全部正常 9 2.3.2 一个Acceptor出现故障 9 2.3.3 一个Proposer成为Leader后发生故障 9 2.3.4 两个Proposer进入无限循环竞争 10 三 算法的思考及优化 11 3.1 体系结构优化 11 3.2 Reconfiguration优化 12 3.3 算法细节优化 12 参考文献 13 一 算法背景问题分析 1.1 Paxos算法处理的问题 Paxos算法解决的问题是一个分布式系统如何就某个值(决议)达成一致[1]。一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。一个通用的一致性算法可以应用在许多场景中，是分布式计算中的重要问题。 节点通信存在两种模型：共享内存(Shared memory)和消息传递(Messages passing)。Paxos算法就是一种基于消息传递模型的一致性算法。 BigTable使用一个分布式数据锁服务Chubby，而Chubby使用Paxos算法来保证备份的一致性[2]。 1.2 不一致性问题的产生 如图1.1所示，一般银行ATM系统的体系结构：C={c1,c2,…,cn}代表n个客户端（ci一个实例是取款机），S={ s1,s2,…,sm }代表m个服务端（si响应每个与之相连的客户端的命令请求；Paxos算法运行的实体）。 图1.1 银行ATM结构图 采用这样的体系结构的目的就是保证在若干个服务端出现故障的情况下，所有的客户端仍能不受影响地进行工作。从而，本文讨论的一致性问题始终是在保证系统可靠性的前提下------因为解决一致性问题最简单而又最不明智的办法就是只设置一个数据处理端（在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)。 1.3 算法的一些前提 前提1：为了保证不出现一些不合法的命令序列，首先Paxos算法执行的环境应当处在一个可靠的通信环境中。即在异步通信过程中，发送的数据可能会被丢失(lost)、延长(delayed)、重复(duplicated)[4]，但不会出现被篡改。 前提2：任意一个算法运行的实体（例如ATM系统中的S）不会出现拜占庭将军问题（Byzantine failure）[5]，可以简单地理解为结点群在决定命令序列的过程中没有结点受病毒、黑客影响。 二 算法介绍与分析 2.1 算法详细描述 2.1.1 角色分类 便于理解，在这里把一个结点的所有行为概括成3种角色：Proposer, Acceptor, Learner。可以认为在一个结点中Paxos算法的行为可以被独立地分成3种对象来执行，对象之间的交互是统一的。其中： Proposer向Acceptor提交提案（proposal），提案中含有决议（value）。 Acceptor审批提案。 Learner执行通过审批的提案中含有的决议。 2.1.2 核心思想 一个Paxos算法执行的实例中只确定一个决议。我们使用数