首页 > BigData > 我所理解的Paxos

我所理解的Paxos

Paxos是前段时间刚获得图灵奖的大神Leslie Lamport所提出的,是用来解决分布式系统中的一致性问题的算法。该算法对于分布式系统的重要性,在这里不再赘言。了解过Paxos的朋友应该都知道,要完全理解Paxos不是一件容易的事。本文是笔者在学习Paxos时,用来帮助自己更好的理解Paxos所梳理的一遍文章,希望能够通过通俗易懂的方式,把Paxos理解清楚。

Paxos要解决的问题

我们知道,Paxos要解决的问题,是分布式系统中的一致性问题。到底什么是“分布式系统中的一致性问题”呢?在分布式系统中,为了保证数据的高可用,通常,我们会将数据保留多个副本(replica),这些副本会放置在不同的物理的机器上。为了对用户提供正确的读/写/删/改等语义,我们需要保证这些放置在不同物理机器上的副本是一致,这就是Paxos所要解决的问题。
Paxos-Scenario
如上图所示,Client会将数据写到三个不同的Server上,如何保证写在这三个不同Server上的数据是一致的,这便是Paxos要解决的问题。
对上述问题进一步抽象,我们假设Replica A的初始状态是S0, 然后用户一次操作称为一个OP, 那么任意时刻,Replica A的状态Sn,都是在S0的基础,执行一系列操作{OP1, OP2, …, OPn}的结果,即:

Sn = S0 + {OP1, OP2, ..., OPn}

在此基础上,要保证多个Replica A/B/C一致,我们需要A/B/C有相同的初始状态S0, 然后{OP1, OP2, …, OPn}按相同的顺序执行,那么最终得到的A/B/C的状态Sn就都是一致的。在这里S0一致是比较好做的,重点是保证{OP1, OP2, …, OPn}按相同的顺序执行,这正是Paxos所要解决的问题。具体到把Paxos应用到实际的系统中,我们需要在系统中执行多轮的Paxos算法,每一轮Paxos用来保证每个OP在每个Replica上被正确执行,多轮Paxos执行的顺序保证多个OP执行的顺序。

Paxos算法模型

Paxos-Model
上图是Paxos所抽象出的模型,为了简化说明,省略了Server1和Server3中的一些细节,这里拿Server2为例来进行说明。如上图中所示,每个Server中都抽象出了Proposer, Acceptor和Learner三个角色。对应到第一部分中Paxos要解决的问题,每个OP被抽象成一个Proposal,Proposer用来发起Proposal, Acceptor用来决策是否接受Proposal, Learner用来获取各Acceptor决策的结果。与之对应,Paxos算法也分为三个过程:Prepare(准备发起Proposal, 图中绿线), Accept(发起Proposal并协商接受, 图中绿线), Learn(学习获取接受的Proposal, 图中蓝线)。

Paxos算法

结合上面的图,我们先来看一下Paxos算法,先对算法本身有一个直观的认识,然后再结合后文来进一步理解,Paxos算法分为下面三个阶段:
1. Prepare阶段:

  • Proposer向大多数Acceptor发起自己要发起Proposal(epochNo, value)的Prepare请求
  • Acceptor收到Prepare请求,如果epochNo比已经接受的小的,直接拒绝; 如果epochNo比已经接受的大,保证不再接受比该epochNo小的请求,且将已经接受的epochNo最大的Proposal返回给Proposer

2. Accept阶段:

  • Proposer收到大多数Acceptor的Prepare应答后,如果已经有被接受的Proposal,就从中选出epochNo最大的Proposal, 发起对该Proposal的Accept请求。如果没有已经接受的Proposal, 就自己提出一个Proposal, 发起Accept请求。
  • Acceptor收到Accept请求后,如果该Proposal的epochNo比它最后一次应答的Prepare请求的epochNo要小,那么要拒绝该请求;否则接受该请求。

3. Learn阶段:

  • 当各个Acceptor达到一致之后,需要将达到一致的结果通知给所有的Learner.

简化模型1

Paxos-Simple-Model1
在Paxos算法中,每个Proposer都会发向所有的Acceptor发起Proposal, 上图是一个Proposer向所有Acceptor发起Proposal的过程。我们知道,在分布式系统的环境中,经常会有各种故障,比如网络异常,物理机器故障等。如果Paxos要求所有的Acceptor都时时刻刻都一致,那么只要有一个Accepor故障的话,整个系统将无法正常运转。因此,Paxos这里弱化了一致的语义,这里的一致是指大多数(majority)机器一致,也就是说,一个Proposal如果被半数以上的Acceptor接受,我们就认为该Proposal被接受了

简化模型2

Paxos-Simple-Model2
上图是Paxos中,各Proposer向各Acceptor发起proposal的过程。可以看出,每个Proposer都会向指定的某个Acceptor发起Proposal, 也就是说,每个Acceptor都会被收到多个Proposal。如何保证每个Acceptor最终接受的值是确定的,且保证大多数Acceptor的接受的值是一样的,这是我们面临的问题。

先看这样一个场景,Proposer1/2/3同时向Acceptor1发起Proposal, 多个Proposal在同一个Acceptor不能并行处理,因此要保证这些Proposal在Acceptor1上能被正确处理,需要一把”锁”, 用它来保证每次只处理一个Proposal。在Paxos算法中,采用了一个单独调增的整数epochNo来充当”锁”的角色。每个Proposal都会有一个epochNo,也就是说每个Proposal是(epochNo, value)这样一个元组。

对于如何保证每个Acceptor最终的值是确定的,Paxos是这么做的: 对于某个指定的Acceptor, 如果它之前没接受任何Proposal, 那么它将接受它所收到的第一个Proposal; 如果它之前已经接受了某个Proposal, 后续将会把自己已经接受的Proposal告知给发起Proposal的其它Proposer,请它们帮忙用该值跟其它Acceptor达到一致。

对于如何保证大多接受的值是一样的,我们来看这样几个场景:
1. Proposer1发起的Proposal收到了一半以上的Acceptor接受的应答: 假设Acceptor1/2接受了Proposer1的Proposal, 如果后续其它Proposer发起的Proposal要保证被一半以上的Acceptor接受,那么这些Acceptor里至少包含Accetor1或2中的一个,它们会协助完成让其它Acceptor接受该Proposal的任务。
2. Proposer1发起的Proposal没收到一半以上的Acceptor接受的应答: 假设只有Acceptor1接受了请求,这时候如果Acceptor1在其它Proposer要达成一致的大多数中, 那么它的值也将会在别的Proposer的协助下,让这大多数达到一致;如果Acceptor1不在其它Proposer要达成一致的大多数中,那么其它大多数会自己达成一致。

总结

关于Paxos,有几个比较重要的核心点,需要进一步强调:

  • 1. epochNo, 在Paxos中充当了“抢占式锁”的角色,非常重要
  • 2. 新(大)的epochNo到了之后,旧(小)的就不再生效,它所有的请求都会被拒绝
  • 3. 新(epochNo大)的Proposal, 要认可旧值,帮助促成旧值达到一致

另外,Paxos因为会有多个Proposer发起Proposal, 新的epochNo能抢占旧的,这样就会有活锁(Liveness)问题,通常的解决方案是选Leader, 由Leader来发起Proposal,Leader会维护一个Lease, Lease过期的话,需要选举新的Leader。Leader是保证和加速Paxos进度的重要手段,通常在具体的工程实践中,都会选Leader。

参考资料

1. Paxos Made Simple
2. Paxos Made Live

  1. 本文目前尚无任何评论.
  1. 本文目前尚无任何 trackbacks 和 pingbacks.
您必须在 登录 后才能发布评论.