由于最近需要在组内做一个分享，而且Spring那块我还没搞完，就打算选paxos的一些问题来梳理理解一下，这也就是技术分享的最大好处，需要你去好好准备。下面是分享的内容文字版。这篇文章的内容大部分参考 自知行学社的视频(B站可以搜索分布式系统与Paxos算法视频课程)。

paxos究竟在解决什么问题？ paxos用来确定一个不可变变量的取值，取值可以是任意的二进制，一旦确定后将不可更改，并且能被再次获取到。

paxos如何在分布式存储系统中应用的？

我们需要转换一下切入点，也许我们需要paxos确定的值，并不一定是我们真正看到的数据。

  • 数据本身通过多副本进行存储
  • 需要保证多个副本的更新操作序列[op1, op2, … opn]是相同的，不变的
  • 用paxos一次来确定不可变变量opi的取值，每次确定完opi之后，就让各个数据副本执行opi

我们观察大部分存储系统，如LevelDB，都是以AppendLog的形式，确定一个操作系列，而后需要恢复存储的时候 都可以通过这个操作系列来恢复，而这个操作系列，正是确定之后就永远不会被修改的。因此这就是paxos在分布式存储系统中的应用。ocean base是基于paxos协议来保证一致性的，微信也实现了一个。

**paxos希望解决的一致性问题

现在我们需要设计一个系统，来存储名为var的一个变量。系统内部有多个acceptor组成，负责存储和管理var变量；系统外部有多个proposer机器任意并发的调用系统API，向系统提交不同的var的取值(任意 二进制数据)。这个系统需要保证var取值满足下面的一致性：

  • 如果var的取值还没有确定，则var的取值为null
  • 一旦var的取值被确定，则不可以更改，且可以一直获取到这个值

系统需要满足的容错特性：

  • 可以容忍任意数量的proposer机器故障
  • 可以容忍半数以下的acceptor机器故障

视频里面提到，确定一个不可变变量的难点在于：

  • 管理多个proposer机器的并发执行
  • 保证var变量不可变性
  • 容忍两种机器的故障

为此，视频里采用了一种循序渐进的方式引入paxos。为此，我们来看设计这个系统的方案一

方案一

  • 先考虑系统内部只有一个acceptor，通过类似互斥锁的机制来管理proposer的并发执行
  • proposer首先向acceptor申请互斥访问权，获得访问权后再请求acceptor接受自己的取值
  • acceptor会向proposer发放互斥访问权，哪个proposer申请到互斥访问权，就接受这个proposer的取值
  • 让proposer按照获取互斥访问权的顺序来依次访问acceptor，一旦acceptor接受了某个proposer的取值，则认为var变量的取值已经确定，其他proposer不能再进行更改

acceptor的实现：

  • 内部保存变量var和一个互斥锁lock
  • prepare(): 加互斥锁，给予var变量的互斥访问权，并返回var当前的取值
  • release(): 释放互斥锁，收回var变量的互斥访问权
  • accept(var, V): 如果已经加锁，并且var此时的取值为null，则设置var的值为V，并释放锁

proposer通过两个阶段来实现：

  • 第一阶段：通过Accept::prepare()接口获取互斥访问权，以及var当前的取值。如果不能，则返回error表示互斥锁已经发给了其他的proposer
  • 第二阶段：根据第一阶段获取到的var值：如果值为null，则通过Accept::accept(var, V)提交自己的取值V；如果不为null，则表示var已经有了确定值，通过Accept::release()释放访问权

我们现在不考虑任何性能问题，思考一下就发现，但是方案一并不能满足刚刚提到的一致性和容错性里的一条，即如果一个proposer申请到了锁之后，在释放锁之前出现了故障，则会导致死锁。我个人的思考是， 在这里给锁加一个过期时间可不可行？。如何解决这种死锁问题呢？

方案二 引入抢占式访问权

  • acceptor可以让某个proposer获取到的访问权失效，不再接受它的访问
  • 可以将访问权发放给其他proposer：proposer向acceptor申请访问权的时候需要指定一个编号 epoch，epoch越大表示越新，还是只有获取到访问权的proposer才能向acceptor提交取值
  • acceptor采用喜新厌旧的原则：一旦接收到更大的epoch的申请，马上让旧的epoch的访问权失效，不再接受这些proposer提交的取值，然后给新的epoch访问权，只接受新的epoch提交的取值
  • 新的epoch可以抢占旧的epoch的访问权，让旧的epoch的访问权失效，为了保证数据的一致性，不同epoch的proposer之间采用"后者认同前者"的原则：在旧的epoch无法形成确定的取值的时候，新的epoch才会 提交自己的取值；而一旦旧的epoch形成了确定的取值，新的epoch肯定会获取到此值，并且认同这个值，不会进行破坏。这儿有一个思考，什么叫认同？怎么认同的。

acceptor的实现：

  • acceptor保存的状态：

    • 当前var的取值以及这个值是哪一个epoch提交的<accepted_epoch, accepted_value>
    • 最新发放的访问权的epoch (latest_prepared_epoch)

  • Accept::prepare(epoch)：

    • 只接受比latest_prepared_epoch大的epoch，并给予访问权
    • 本地记录latest_prepared_epoch = epoch，并返回当前var的值

  • Accept::accept(var, prepared_epoch, V)：

    • 验证prepared_epoch == latest_prepared_epoch，如果不相等则返回错误，表示访问权已经被更大的epoch拿到
    • 设置<accepted_epoch, accepted_value> = <prepared_epoch, V>

proposer的两阶段实现：

  • 第一阶段：简单选取当前时间戳为epoch，通过prepare(epoch)接口获取epoch的访问权以及var变量的取值。如果不能，则返回error，表示互斥锁已经发给了更大epoch
  • 第二阶段：如果获取到了访问权，采用"后者认同前者"的原则执行：如果上一阶段获取的var值为null，则肯定旧的epoch不能形成旧的取值，通过accept(var, prepared_epoch, V)提交数据V，成功后返回 <ok, V>，如果失败则返回error(意味着访问权被更大的epoch抢占到，或者acceptor故障)；如果上一阶段获取的var值不为空，则这个值已经是确定的，不能再进行修改，返回<ok, accepted_value>

基于抢占式访问权的核心思想：

  • 让proposer将按照epoch递增的顺序抢占式的依次运行，后者会认同前者
  • 可以避免proposer机器故障带来的死锁问题，并且仍可以保证var取值的一致性
  • 仍需要引入多acceptor： 单机模块Acceptor故障容易导致整个系统宕机，无法提供服务

paxos—引入多个acceptor的方案二

paxos在方案二的基础上引入多个acceptor，解决了单点问题，acceptor的实现保持不变，仍然采用"喜新厌旧"的原则。paxos采用少数服从多数的思路，一旦某个epoch的取值被半数以上的acceptor接受， 则认为此值被确定，不再变化。

proposer的两阶段实现：

  • 第一阶段：选定一个epoch，获取epoch访问权和对应的var取值，获取半数以上的acceptor的访问权和对应的一组var取值。

  • 第二阶段：仍然采用"后者认同前者"的原则执行：

    • 如果获取的var值都为空，则旧的epoch无法形成确定性取值，此时向epoch对应的所有acceptor(我认为是获取到了访问权的acceptor，不是系统的所有acceptor；此处微信文章认为不一定要向所有应答了 的acceptor，只要是多数派就可以，也就是漏掉几个满足多数也没有关系)提交取值accept(var, prepared_epoch, V)， 如果收到半数(所有acceptor)以上的成功，则返回<ok, V>，否则返回error，表示被新的epoch抢占或者acceptor出现了故障。
    • 如果var的取值存在，认同最大的accepted_epoch对应的取值f，如果f出现了半数以上，则说明f已经是确定性取值，直接返回<ok, f>；否则向epoch对应的所有acceptor提交取值accept(var, epoch, f)

注意

这里讲了一下paxos的实现方案，按照上述推导，其实任意情况都能保证数据的一致性。但是常说的leader和learner并不是paxos保证一致性的必要角色，它们是用来提升性能的。

分析 假设在一个系统中有两个 proposer三个acceptor，暂时不提learner，该系统发生了如下时间线的事情：

1、proposer1 拿到了3个acceptor对 prepare 请求的确认回复，开始向3个acceptor发送accept请求
2、proposer1 的accpet 请求顺利到达acceptor1，acceptor1 accept 了 value1
3、因为延时等问题proposer1发出的accept请求没能及时到达acceptor2与acceptor3
4、proposer2 更新了acceptor2与acceptor3的 prepare number
5、proposer2 向三个acceptor都发送accept请求，acceptor2与acceptor3 accept了value2，acceptor1则拒绝了value2

也就是说，在上面的例子中value真正被chosen是在acceptor2与acceptor3 accept 了value2 那一刻，而不是 acceptor1 accept 了 value1 那一刻。

Q1：有人要问了，那acceptor1 accept了 value1，acceptor2与acceptor3 accept 了value2 ，那岂不是没有实现状态一致吗？出现这个问题除了之前说的，混淆了accept与chosen以外，也和网络上 很多关于Paxos 算法的文章省略了对learner的讨论有关系。 A1：首先我们应该明确，一个value是否被chosen与acceptor是无关的，acceptor在accept一个value之后，它的使命就完成了，至于这个value最后是否能够被chosen不是它考虑的问题。

Q2：有人又要问了，那acceptor怎么知道自己accept的value 有没有被chosen呢？答案是：其实它没有知道的必要，如果它想知道的话，通过learner。 A2：如果acceptor想知道哪个value被chosen的话，可以通过询问learner（learner可以有一个也可以有多个），如果此时已经有value被chosen了，learner可以告诉该acceptor被chosen的value2， 然后该acceptor记录下被chosen的value（如果它有必要记录的话）

其实我们在上面的例子中，如果开上帝视角的话，在acceptor2与acceptor3 accept 了value2 的那一刻，value2的值已经被chosen了，但是此时learner节点们还不知道，所有就需要learner去 learn哪个value被chosen了（To learn that a value has been chosen）

关于learner 如何learn 到哪个value被chosen，在 Paxos make simple 的论文中有讨论，也比较简单（其实就是通过消息去询问或者被告知是否有一个value被大多数（超过一半）acceptor accept）。

basic paxos是由client发起的同步过程，在两阶段返回前，client不能得到成功的返回。

第一阶段a（发送prepare），proposer向acceptor提出一个协议，这里的协议可以理解为client发送过来期望多节点一起保存的一致性内容，举例：一句日志，某个配置等 第一阶段b（计算协议vn），根据半数以上acceptor的返回，选择 max{va,vb,vc} = vn，这里的vx理解为这个acceptor已知的最大协议号，acceptor一旦返回了vx后，则表明： acceptor在接下来的prepare请求中，会返回的vx自增1 acceptor不会accept任何小于vx的协议请求，只会accept大于vx的协议请求 第二阶段a（发送决议好的vn），把vn发送给acceptor 第二阶段b，在半数acceptor返回了成功后，再返回client成功通过协议

引用wiki上的流程图：

Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  |
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Prepare(1)
   |         |<---------X--X--X       |  |  Promise(1,{Va,Vb,Vc})
   |         X--------->|->|->|       |  |  Accept!(1,Vn)
   |         |<---------X--X--X------>|->|  Accepted(1,Vn)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |

刚才我讲了，Paxos还过于理论，无法直接用到复制状态机中，总的来说，有以下几个原因 Paxos只能确定一个值，无法用做Log的连续复制 由于有多个Proposer，可能会出现活锁，如我在上面举的例子中，Server2的一共提了两次Propose才最终让提案通过，极端情况下，次数可能会更多 提案的最终结果可能只有部分Acceptor知晓，没法达到复制状态机每个instance都必须有完全一致log的需求。 那么其实Multi-Paxos，其实就是为了解决上述三个问题，使Paxos协议能够实际使用在状态机中。解决第一个问题其实很简单。为Log Entry每个index的值都是用一个独立的Paxos instance。解决第二个问题也很简答， 让一个Paxos group中不要有多个Proposer，在写入时先用Paxos协议选出一个leader（如我上面的例子），然后之后只由这个leader做写入，就可以避免活锁问题。并且，有了单一的leader之后，我们还可以省略掉大部 分的prepare过程。只需要在leader当选后做一次prepare，所有Acceptor都没有接受过其他Leader的prepare请求，那每次写入，都可以直接进行Accept，除非有Acceptor拒绝，这说明有新的leader在写入。为了解 决第三个问题，Multi-Paxos给每个Server引入了一个firstUnchosenIndex，让leader能够向向每个Acceptor同步被选中的值。解决这些问题之后Paxos就可以用于实际工程了。 Paxos到目前已经有了很多的补充和变种，实际上，之后我要讨论的ZAB也好，Raft也好，都可以看做是对Paxos的修改和变种，另外还有一句流传甚广的话，“世上只有一种一致性算法，那就是Paxos”。