paxos算法之粗浅理解
2021-03-31 09:26
标签：其它 失效 参与者 size 发送 lazy 选择 led details paxos出身 paxos出身名门，它爹是没多久前获得图灵奖的在分布式领域大名鼎鼎的Leslie Lamport。 paxos为何而生 那么Lamport他老人家为什么要搞这个东东呢，不是吃饱了撑的，而是为了解决分布式系统的大难题。分布式系统一 般要求具有高可用性，高可用性一般又是通过冗余也就是多副本来解决，多副本接着又带来了一致性问题，所以分布 式系统要解决的问题可简单归结为多副本的一致性问题。怎么解决一致性问题呢？抢答：用事务。何为事务？抢答： 多个操作序列的原子性。何为原子性？抢答：还需要您自己去多看书吧。实现事务的方案有两阶段提交协议，和在这 个基础上进行了增强的三阶段提交协议。 这两个方案都涉及到两个角色，即协调者(coordinator)和参与者(cohort)，协 调者要保证操作序列的原子性来实现事务，但它们都存在一些 问题，因此一些著名的系统如Google的Chubby和Yahoo 的Apache ZooKeeper都使用了paxos算法。 两阶段提交协议的消息流程： 两阶段提交协议包含投票(Vote)和提交(Commit)两个阶段，它是一个阻塞的协议，如果参与者给协调者发送YES消息后协调者 永久性地挂了，那么参与者将陷入无限等待中，并且会带来数据不一致的问题。 三阶段提交协议的消息流程： 三阶段提交协议在二阶段提交协议的基础上增加了准备提交(Prepared to commit)阶段，解决了协调者挂掉后参与者 无限阻塞和数据可能不一致的问题，但仍然无法解决网络分区的问题。 相对于上面两个协议，由于多数派的特性，paxos可以在节点失效、网络分区、网络延迟等各种异常情况下保证所有 节点都处于同一状态，它的结构图大致如下： Basic paxos architecure. A picutre from:paxos-by-example 一个典型的paxos应用场景 分布式系统中有多个节点，一般每个节点都是参与者，而其中一个节点既是参与者又是协调者。但是这样还会有单点 故障的问题，即如果协调者节点挂了，那么将无法进行任何事务，系统也就停止了正常运转。如何在还存活的其它节 点中选择一个来担当协调者的角色，使系统可以照常运行，达到山不转水转的目标呢？真的好难，但是有了paxos算 法，我们可以解决这个难题。如果还觉得这个问题抽象，那么可以换一种表述方式，即：如何在分布式系统中确定某 一个变量的值。在这个具体的场景中，这个变量的值指定了哪个节点将被选出来担当新协调者的角色。 paxos角色和规则 从上面的结构图中，我们看到paxos主要涉及三个角色，分别为Acceptor、Proposer和Learner，在实践中，往往每个节 点都具备这三个角色，这里为了让我们大脑少些迷糊，暂且以每个节点只具备一种角色来讨论。 paxos算法主要分为两个阶段： 1. Prepare: Proposer 向所有Acceptor发送Prepare申请访问权，并携带一个提案号(epoch)，Acceptor赋予访问权或拒绝，并且返回 该Acceptor 已经接受的值和对应的提案号。如果Proposer获得超过半数Acceptor的访问权，那么会进入第二阶段； 2. Accept: 1) 如果所有的Acceptor返回值都为空，则Proposer将携带自己预设的值v和自己的epoch号向获取到访问权的Acceptor发送请求; 2)如果Proposer第一阶段获得某些Acceptor的返回值不为空，则将epoch号最大的提案号对应的值f作为自己的预设值，和自己的 提案号一起向Acceptor发送请求(如果第一阶段返回f的Acceptor已经超过了半数，则表示已经形成确定性取值，此时直接返回成 功，不需要进行Accept请求了)； 对于Acceptor来说，当它接收到Proposer请求时，需要应用一系列规则来决定如何响应，我们对这些规则可以进行如下概括： 1)喜新厌旧 当Acceptor接收到Prepare请求时，它将当前自己发放了访问权的epoch号和该Prepare请求携带的epoch进行比较，如果前者小 于后者，则将访问权赋予新请求的这个Proposer，否则拒绝发放访问权。这里我们认为epoch值越大的越新。 2) 一视同仁 当Acceptor接收到Accept请求时，它 将当前自己发放了访问权的epoch号和该Prepare请求携带的epoch进行比较，如果前者大于 后者，则拒绝该请求。如果这两个epoch号相等， 并且Acceptor当前接受的取值为空，则接受该Acceptor请求，同时将该Accept 请求的值设置为接受值。如果之后又更大的epoch号申请 到访问权，并发出Accept请求，该值也不会改变，即Acceptor在确定了 值之后不再改变，谁先设置就用谁的值。虽然在发放访问权时是喜新厌旧，但 在取值这个问题上一视同仁，不会因为新epoch号 大而改变取值。这就像某些人，其他女人可以访问他，但老婆只要定了就不会变。 paxos正确性 假 设有N个Acceptor，多数派个数至少为N/2+1。如果有一个以上的Proposer获取到超过半数Acceptor的访问权，那么至少有一个 Acceptor是相同的。具体来说，假设Proposer A在Prepare阶段获取到J个Acceptor的访问权，Proposer B在Prepare阶段获取到K个Acceptor的访问权，J>=N/2+1，K>=N/2+1，那么必然有这样一个Acceptor C，C既属于J又属于K，这种情况就是在C给某个Proposer发放访问权后，接着被另一个Proposer抢占到了访问权时发生。 我们假设Proposer A的取值为V1，Proposer B的取值为V2。在Accept阶段，对于Acceptor C来说，它根据访问权来决定接受谁的Accept请求，如果当前是B获得了访问权，则接受B的取值V2，这样A在Accept阶段将失败，失败之后它可能 会继续生成新的epoch值重新进入Prepare阶段，但是这回它拿到了返回值V2，这样它之后进入Accept阶段时，会将V2作为它的取值向 Acceptor发送申请，最终Proposer A和Proposer B都达成了一致，即V2为最终取值。 以上是本人目前对paxos算法的一点理解，还将继续深入和不断纠正....... 感觉不错的资料，推荐参考： 前百度牛人李海磊的课程： http://www.tudou.com/programs/view/e8zM8dAL6hM/ 这个视频里还讲到了活锁，我看了启发不小： https://www.youtube.com/watch?v=JEpsBg0AO http://angus.nyc/2012/paxos-by-example/ http://blog.csdn.net/chen77716/article/details/6166675 参考：paxos算法之粗浅理解 paxos算法之粗浅理解 标签：其它 失效 参与者 size 发送 lazy 选择 led details 原文地址：https://www.cnblogs.com/aspirant/p/13570471.htmlCoordinator Cohort
QUERY TO COMMIT
-------------------------------->
VOTE YES/NO prepare*/abort*
ACKNOWLEDGMENT commit*/abort*
