深入理解Paxos算法协议

发表于   |   分类于   |  

前言

这篇文章是来自于网络上有关Paxos算法协议的分析文章的整理，我觉得看完网上的分析文章之后还是能帮助自己理解这个协议，当然工程实践还是有些迷惑，因此在此记录。首先抛出几个问题，然后带着问题再看此文章更好：

  1. Paxos算法协议要解决什么问题？
  2. Paxos算法协议为什么要有两个阶段？
  3. Paxos算法协议为什么要求每次提议的编号都要是最大的？
  4. 如果Prepare阶段成功，但是Accept阶段失败，系统如何表现？

背景

Paxos算法是Lamport于1990年提出的一种基于消息传递的一致性算法。由于算法难以理解起初并没有引起人们的重视，使Lamport在八年后重新发表到TOCS上。即便如此paxos算法还是没有得到重视，2001年Lamport用可读性比较强的叙述性语言给出算法描述Paxos Made Simple。可见Lamport对paxos算法情有独钟。近几年paxos算法的普遍使用也证明它在分布式一致性算法中的重要地位。06年google的三篇论文初现“云”的端倪，其中的chubby锁服务使用paxos作为chubby cell中的一致性算法，paxos的人气从此一路狂飙。

Paxos算法是什么

在分布式系统中一个最重要的问题就是如何确保数据的一致性，最终一致性可以通过异步复制的机制来实现，而强一致性就需要用诸如分布式共识算法等技术手段来实现了。
Paxos 算法解决的问题就是一个分布式系统如何就某个值（决议）达成一致。一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致，这样就能达到强一致性。一个通用的一致性算法可以应用在许多场景中，是分布式计算中的重要问题。从20世纪80年代起对于一致性算法的研究就没有停止过。节点通信存在两种模型：共享内存（Shared memory）和消息传递（Messages passing）。Paxos 算法就是一种基于消息传递模型的一致性算法。

Paxos的基本概念

Paxos算法协议中涉及到了如下几个概念，这对于理解整个协议是有很大的帮做的。

  • Proposal Value：提议的值
  • Proposal Number：提议编号，要求提议编号不能冲突
  • Proposal：提议 = 提议的值 + 提议编号
  • Proposer：提议发起者，处理客户端请求，将客户端的请求发送到集群中，以便决定这个值是否可以被批准
  • Acceptor：提议接受者，负责处理接收到的提议，他们的回复就是一次投票。会存储一些状态来决定是否接收一个值
  • Learner：提议学习者

Paxos的两个原则

Paxos 协议需要依赖一个基本假设，主备之间有多数派机器（N / 2 + 1）存活并且他们之间的网络通信正常，如果不满足这个条件，则无法启动服务，数据也无法写入和读取。同时还拥有如下两个原则：

安全原则，保证不能做错的事：

  1. 只能有一个值被批准，不能出现第二个值把第一个覆盖的情况
  2. 每个节点只能学习到已经被批准的值，不能学习没有被批准的值

存活原则，只要有多数服务器存活并且彼此间可以通信最终都要做到的事：

  1. 最终会批准某个被提议的值
  2. 一个值被批准了，其他服务器最终会学习到这个值

Paxos提议过程解析

为了从本质上来理解Paxos算法协议，我们可以假设每一台服务器都是一个Proposer，也是一个Acceptor，（更直白的理解就是，在一个分布式数据库系统中，每一台数据库服务器都可以处理读写请求，他们构成了一个分布式的环境，此时就是多个Proposer，多个Acceptor，而他们自身又是基于主从架构的，此时就分成了一个Proposer，多个Acceptor）。而且分如下两种情况：

一个Acceptor

首先从最简单的方式开始，假设只有一个Acceptor，让它做决定是否批准一个值

如上图，每一个Proposer提议一个值给Acceptor来批准，然后Acceptor批准一个值作为最终的值。但是这种简单的方式，没有办法解决Acceptor crash的问题，如果唯一的Acceptor crash了，就没有办法知道哪个值被选择了，就需要等待它重启，这一条违反了存活原则，这个时候有4台服务器存活，但已经没有办法工作了。

多个Acceptor

为了解决这个问题，就必须要用到一种多数选择的方法。使用一个Acceptor的集合。然后只有其中的多数批准了一个值，这个值才可以确实是被最终被批准的。当然，为了达到目的也需要一些技巧，同时也会遇到新的问题。

批准第一个达到的值：首先规定每个Acceptor必须批准第一个到达的值。哪个值达到多数批准就是最终批准的值。

但是有一个问题，比如上图，因为没有值被多数批准，无法批准一个最终的值出来，而且本身还是需要能够批准多个值的。这就需要Acceptor批准了一个值之后还要根据某种规则批准不同的值。

批准每个提议的值：接下来规定Acceptor批准每个提议的值，但是这也会带来一个问题，可能会批准出多个值。

如图，S1发出提议，S1，S2，S3批准 red为最终批准的值。S5随后发出提议，s3，S4，S5批准，blue又为最终批准的值。此时S1，S2，S3最终批准red，S3，S4，S5最终批准blue，这就违背了我们的一致性原则，最终只有一个值被选择。

二段提交原则

要解决上面的问题，就要S5在发送自己的提议之前，优先检查有没有已经被批准的值，如果有应该提议已经被批准的值而放弃自己的值，也就是放弃自己的blue改为提议red，这样最终只有一个值被批准就是red。这个就是经典的二段提交原则。不幸的是，二段提交还是存在另一个问题。

如图，S1在发送提议之前，检查没有值被批准，因此提议red。但同时在所有Acceptor批准之前，S5也要进行提议，这个时候也检查出没有值被批准，所以它也把自己的blue作为提议发送给acceptor。接下来S5的提议优先到达S3，S4，S5，这些Acceptor先批准了blue，达到多数所以blue最终被批准了。但是随后S1，S2，S3接收到了red进行批准。所以又出现了批准出多个值的问题。

提议排序

要解决上面二段提交原则中的问题，就需要一旦Acceptor批准了某个值，其他有冲突的值都应该被拒绝。也就是说S3随后到达的red应该被拒绝，为了做到这一点。需要对Proposer进行排序，将排序在前的赋予高优先级，Acceptor批准优先级高的值，拒绝排序在后的值。为了将提议进行排序，可以为每个提议赋予一个唯一的ID，规定这个ID越大，优先级越高，在提议者发送提议之前，就需要生成一个唯一的ID，而且需要比之前使用的或者生成的都要大。

Paxos提议完整过程

有了上面的分析之后，再综合起来看一下提议的两个阶段的完整过程，在此，记{n，v}为提议编号为n，提议的值为v的提议，记(m，{n，v})为承诺了Prepare（m）请求，并接受了提议{n，v}。

第一阶段A

Proposer选择一个提议编号n，向所有的Acceptor广播Prepare（n）请求。此时的提议编号n，由当前Proposer保证自己发起的后一轮提议编号（n）一定大于前一轮提议编号。（而各个Proposer不必保证自己的投票轮次是全局最大的，当然为了减少在第一阶段的授权冲突，也可以保证新的投票轮次全局最大）

Proposer向所有Acceptor发出关于发起提议n的新一轮提议的申请，并等待第一阶段B各个Acceptor进行响应。当然会有一个超时时间，如果超过这个时间还没有得到Acceptor的响应，则认为已经被拒绝。如果有超过N/2 + 1个节点在规定的时间内没有回复响应，那就说明整个选举系统发现了问题，则终止操作抛出错误，向客户端反馈异常信息。

第一阶段B

Acceptor接收到Prepare（n）请求，若提议编号n比之前接收的Prepare请求都要大，则承诺将不会接收提议编号比n小的提议，并且带上之前Accept的提议中编号小于n的最大的提议，否则不予理会。

Proposer将负责汇总所有Acceptor的响应情况，并根据汇总的情况判断下一步的操作：

  1. 超过（包括）N/2 + 1个Acceptor节点在规定的时间内没有反馈结果，这种情况直接判定Paxos系统崩溃。
  2. 只要至少N/2 + 1个Acceptor节点的AcceptedValue（v）为同一个值，就认为提议n的结果达到了最终一致，整个Paxos算法过程也结束。
  3. 至少N/2 + 1个Acceptor允许这轮投票。这些Acceptor就形成了一个集合Q，这个集合Q将继续下一步骤的操作。这时集合Q中的Acceptor是否已有AcceptedValue就很重要了：如果集合Q中没有任何一个Acceptor的AcceptedValue属性有值，则当前Proposer会在下一步提议自己的值为集合Q中每一个Acceptor的赋值目标；如果集合Q中至少存在一个Acceptor的AcceptedValue属性有值，则Proposer会选择一个AcceptedVote最大的AcceptedValue属性值，作为当前Proposer会在下一步进行Acceptor赋值的目标。

第二阶段A

Proposer得到了多数Acceptor的承诺后，如果没有发现有一个Acceptor接受过一个值，那么向所有的Acceptor发起自己的值和提议编号n，否则，从所有接受过的值中选择对应的提议编号最大的，作为提议的值，提议编号仍然为n。（第二阶段一般将以上一阶段形成的多数派集合Q作为操作目标）

Proposer将负责汇总所有第二阶段B Acceptor的响应情况，并根据汇总的情况判断下一步的操作：

  1. 超过（包括）N/2 + 1个Acceptor节点在规定的时间内没有反馈结果，这种情况直接判定Paxos系统崩溃
  2. 只要至少N/2 + 1个Acceptor节点的AcceptedValue（v）为同一个值，就认为提议n的结果达到了最终一致，整个Paxos算法过程也结束。
  3. 发现任何一个赋值结果不一致，则认为赋值操作失败。这时Proposer会将自己的提议编号n进行增加后，再回到第一阶段重新发起投票（最大Commit原则）。

第二阶段B

Acceptor接收到提议后，如果该提议编号不违反自己做过的承诺，则接受该提议，并修改自己的对应的值为n,v。

赋值操作完成后，Acceptor将向Proposer返回赋值操作后的AcceptedValue属性(v)和AcceptedVote属性(n)。换句话说就是，即使Acceptor拒绝了第二阶段的赋值操作，也要向Proposer返回AcceptedValue属性值。

小结

上面的图例中，P1广播了Prepare请求，但是给A3的丢失，不过A1、A2成功返回了，即该Prepare请求得到多数派的应答，然后它可以广播Accept请求，但是给A1的丢了，不过A2，A3成功接受了这个提议。因为这个提议被多数派（A2，A3形成多数派）接受，我们称被多数派接受的提议对应的值被Chosen。（这里也可以说是针对网络分区或者延迟的一个处理措施）

Paxos协议最终解决什么问题？

当一个提议被多数派接受后，这个提议对应的值被Chosen（选定），一旦有一个值被Chosen，那么只要按照协议的规则继续交互，后续被Chosen的值都是同一个值，也就是这个Chosen值的一致性问题。整个完整的过程如下图所示：

总结

整个协议的过程，理解起来还是比较容易懂，也可以看出Paxos算法协议满足了分布式系统中的数据一致性，服务的持续可用，同时也能满足主备自动切换。而且在分布式情况下，出现的网络分区，或者是网络抖动导致的延迟都能比较好的应对。如果想要看具体的算法证明可以看下这篇文章微信PaxosStore：深入浅出Paxos算法协议，具体的工程实践可以看这篇文章架构师需要了解的Paxos原理、历程及实战

参考

一步一步理解Paxos算法
最终一致性Basic-Paxos算法
微信PaxosStore：深入浅出Paxos算法协议
架构师需要了解的Paxos原理、历程及实战