paxos 科普

分布式算法，不得不提paxos。它是目前公认的解决分布式共识问题最有效的算法之一，甚至可以说过去几十年里一切分布式一致性算法都来源于它。
那么要学习paxos，我们首先得认识它。一般描述它，都会包含两个词：分布式容错、分布式共识算法。那么它们是指什么呢？paxos又解决了什么样的问题呢？

  1. 分布式容错
    分布式容错，是指在分布式环境下，能够容忍一部分节点宕机，还能向外提供稳定的服务。
  2. 分布式共识算法
    分布式共识算法，是指在分布式环境下，各个节点能就某个值达成共识，即所有节点都认同某个值。

理解共识可能要难一点，那么我举个例子。假如有A、B两个客户端，他们都对同一个X进行赋值。A需要设置X=1，B需要设置X=2。那么让A和B都认同值X=1或者X=2的过程，就是达成共识。

带着这个问题，来聊聊如何达成共识呢?

初探paxos

paxos为了帮我们理解，抽象出三个角色和两个阶段

  • 角色：提案者（proposer）、接受者（acceptor）、学习者（learner）
  • 阶段：prepare阶段、accept阶段、learn阶段

提案（proposal）

在描述这些角色之前，我们需要先了解什么提案。在paxos算法中提案是指需要达成共识的某一个值，或者某一个操作。paxos对其封装成一个提案，并为其生成唯一的提案编号。本文中使用[M, V]表示一个提案，其M表示提案编号，V表示需要达成共识的值。

提案者（proposer）

proposer的工作在于接收客户端请求，将其封装成提案（proposal）。并将提案（proposal）发给所有的接受者（acceptor）。根据接受者（acceptor）返回情况，控制是否需要提交该提案（proposal）即保存该提案（proposal）。

接受者（acceptor）

acceptor的工作在于参与对提案（proposal）的投票，接收和处理paxos的两个阶段的请求。

学习者（learner）

learner不参与提案和投票，只被动接收提案结果。他的存在可用于扩展读性能，或者跨区域之间读操作。

因为他们不投票，所以他们不是paxos集群的重要组成部分。因此，它们可以失败，或者与集群断开连接，而不会损害paxos服务的可用性。对用户的好处是learner相比acceptor来说更能通过不太可靠的网络链接进行连接。实际上，learner可用于与另一个数据中心的paxos服务器通信，并且写入消耗最小的网络流量，因为在没有投票协议的情况下所需的消息数量较少。

prepare阶段

prepare阶段，由proposer向acceptor发送prepare请求，acceptor根据约定决定是否需要响应该请求。如果acceptor通过提案[M, ]的prepare请求，则向proposer保证以下承诺

  1. acceptor承诺不再通过编号小于等于M的提案的prepare请求
  2. acceptor承诺不再通过编号小于M的提案的accept请求，也就是不再通过编号小于M的提案
  3. 如果acceptor已经通过某一提案，则承诺在prepare请求的响应中返回已经通过的最大编号的提案内容。如果没有通过任何提案，则在prepare请求的响应中返回空值

其中prepare阶段还得注意，在prepare请求中，proposer只会发提案编号，也就是[M, ]。

accept阶段

accept阶段，在proposer在prepare阶段收到大多数响应后，由proposer向acceptor发送accept请求。例如此时进行决策的提案是[M, V]，根据acceptor在prepare阶段对proposer的承诺。

  • 如果此时acceptor没有通过编号大于M的prepare请求，则会批准提案[M, V]，并返回已通过的编号最大的提案（也就是[M, ]）。
  • 如果此时acceptor已经通过编号大于M的prepare请求，则会拒绝提案[M, V]，并返回已通过的编号最大的提案（大于M的编号）。

proposer会统计收到的accept请求的响应，如果响应中的编号等于自己发出的编号，则认为该acceptor批准过了该提案。如果存在大多数acceptor批准了该提案，则记作该提案已达成共识，或者记作提案已被批准。如果没有大多数acceptor批准该提案，则重新回到prepare阶段进行协商。

其中accept阶段也有注意的地方，在prepare请求中，proposer只会发提案[M, ]。而accept请求，proposer会发送提案编号和提案值，也就是[M, V]。这里要注意的是V的值，如果在prepare请求的响应中，部分acceptor已经批准过的提案值，则V为prepare请求的响应中编号最大的提案值，否则可以由proposer任意指定。

learn阶段

learn阶段，在某一个提案通过paxos达成共识之后，由acceptor通知learner学习提案结果。

算法陈述

该小节分为两部描述：提案选定、提案获取。

  • 提案选定，是描述paxos从一个提案的产生到如何达成共识的过程。也就是prepare阶段、accept阶段
  • 提案获取，是描述learner如何获取保存提案，也就是learn阶段

提案选定

先来看一张非常流行的图，它用伪代码描述了paxos的过程。我预先描述下几个变量。

  • minProposal：当前acceptor在prepare请求中通过的最大提案编号
  • acceptedProposal：当前acceptor在accept请求中通过的最大提案编号
  • acceptedValue：当前acceptor在accept请求中通过的最大提案编号的提案值

paxos伪代码描述

  1. 先为proposal生成一个编号n，这里需要保证编号全局唯一，并且全局递增，具体实现全局编号，这里不予讨论。
  2. proposer向所有acceptors广播prepare(n)请求
  3. acceptor比较n和minProposal，如果n>minProposal则执行minProposal=n，并且将 acceptedProposal 和 acceptedValue 返回给proposer。
  4. proposer接收到过半数回复后，如果发现有acceptedValue返回，将所有回复中acceptedProposal最大的acceptedValue作为本次提案的value，否则可以任意决定本次提案的value。
  5. 到这里可以进入第二阶段，广播accept (n,value) 到所有节点。
  6. acceptor比较n和minProposal，如果n>=minProposal，则acceptedProposal=minProposal=n，acceptedValue=value，本地持久化后，返回；否则，返回minProposal。
  7. proposer接收到过半数请求后，如果发现有返回值result（minProposal） > n，表示有更新的提议，跳转到1；否则value达成一致。

当然，实际运行过程中，没有以上陈述的那么理想。真实情况下，每一个proposer都有可能产生多个提案，但只要每个proposal遵循如上算法运行，就一定能保证执行正确性。文章后续我们会对多提案提出的情况进行模拟，并详细讲解。

提案获取

在一个提案达成共识后，如何让learner获取该提案也是一个值得细究的问题。一般有以下几种方案。

  • 方案一
    最简单的方法就是一旦acceptor批准了一个提案，就将该提案发给所有的learner。这种做法虽然可以让learner尽快的获得被选中的提案，但是却需要每个acceptor与所有learner逐一进行通信，通信次数为二者乘积，所以效率较低。
  • 方案二
    选定一个主learner，如有某一个提案批准后，由acceptor通知主learner，当主learner被通知后，由它通知其他的learner。这个方案虽然多了一个步骤，但是通信次数大大降低，通信次数为learner的数量。该方案同时引出另一个问题：主learner随时可能出现故障。
  • 方案三
    在基于方案二的基础上，由单个主learner扩展成一个主learner集合。集合中learner数量越高，可靠性也越好。

算法模拟

为了更好的熟悉paxos，我们举例描述paxos中提案选定过程。假设存在3节点的paxos集群，这里需要注意每一个节点可以同时扮演proposer和acceptor。情况如下

proposerA收到请求将X设置成3，proposerB收到请求将X设置成5。proposerA和proposerB分别为此生成提案，其proposerA的提案编号为1，proposerB提案编号为2。在prepare阶段它们交互结果如下

paxos prepare请求

  1. proposerA和proposerB分别进入prepare阶段，将提案编号发给各个acceptor。
  2. acceptorA和acceptorB在收到proposerA的prepare请求后，由于没有通过过任何prepare请求，也没有批准过任何的accept请求。则给proposerA返回尚无提案。
  3. acceptorC由于在收到proposerB的prepare请求之后再收到proposerA的prepare请求，且proposerB的提案编号大于proposerA的提案编号，故不给proposerA返回prepare响应。
  4. acceptorA和acceptorB在收到proposerB的prepare请求后，由于之前收到proposerA的prepare请求，则比较各自的提案编号，由于proposerB的提案编号大于proposerA的提案编号，但是又没有通过任何的accept请求，则给proposerB返回尚无提案，并向proposerB保证前文所说的三个承诺。

至此，proposerA获得2个prepare响应，proposerB获得三个prepare
响应。即他们都获得了大多数节点的prepare响应，于是各自开始accept阶段提交。

paxos accept请求

  1. proposerA由于收到的prepare响应中没有任何提案值，则自己任意设置提案值，也就是[1, 3]。并向各个acceptor发起accept请求。
  2. acceptorA、acceptorB、acceptorC收到proposerA的accept请求后，由于在prepare阶段，他们都向proposerB保证了上文所说的三个承诺，则他们不会该accept请求，并将prepare阶段通过最大的提案编号返回给proposerA，也就是[2, ]。
  3. proposerA收到[2, ]后，发现响应中的提案编号2比自己的提案编号1大，则认为没有accept通过该提案。proposerA需要重新回到prepare阶段进行协商。
  4. proposerB由于收到的prepare响应中没有任何提案值，则自己任意设置提案值，也就是[2, 5]。并向各个acceptor发起accept请求。
  5. acceptorA、acceptorB、acceptorC，在此期间没有通过任何的prepare请求也没有通过任何的accept请求，即同意批准该提案，返回[2, ]给proposerB。
  6. proposerB收到accept响应后，比对提案编号发现有大多数的提案编号是自己的编号，则认为该提案达成共识，完成协商过程。

以上过程的主要描述了accept对proposer的两个承诺，即如果acceptor通过提案[M, ]的准备请求

  • acceptor承诺不再通过编号小于等于M的提案的prepare请求
  • acceptor承诺不再通过编号小于M的提案的accept请求，也就是不再通过编号小于M的提案

那么还有一个承诺是

  • 如果acceptor已经通过某一提案，则承诺在prepare请求的响应中返回已经通过的最大编号的提案内容。如果没有通过任何提案，则在prepare请求的响应中返回空值

为了描述该承诺，我们想象出这样一个场景。proposeB完成prepare请求后，发起accept请求，且提案为[3, 6]。在此过程中，proposeA发起prepare请求，提案编号为[4, ]，并且acceptor先收到proposeA发起prepare请求，也就是说acceptor会拒绝proposeB的accept请求。情况如下

paxos 两个提案提出

  1. proposerB发起accept请求，提案为[3, 6]。
  2. acceptorA收到proposerB的accept请求后，批准了该请求。
  3. proposerA发起prepare请求，提案为[4, ]。
  4. acceptorB、acceptorC先收到proposerA的prepare请求。则拒绝proposerB的accept请求。
  5. acceptorA收到proposerA的prepare请求，由于之前接收了proposerB发起accept请求，则给proposeA返回已批准的提案[3, 6]。
  6. 此时，proposerB重新进入prepare协商，proposerA收到大多数prepare响应，发起accept请求，由于收到acceptorA返回的提案[3, 6]，那么proposer的提案值也只能为6，即[4, 6]。
  7. accept完成协商。

multi-paxos算法

原始的paxos算法（Basic Paxos），只能完成一个值的共识。Lamport宗师提到可以通过执行多次basic-paxos实现一系列值的共识。但是由于多次协商会增加通信以及影响协商的活性（指协商进入死循环）。

宗师则提出multi-paxos的解决方案，但是由于宗师并没有把multi-paxos讲清楚，只是介绍了大概的思想，缺少算法过程必要细节。所以这给了我们很大的想象空间，因此每个人实现的multi-paxos都有所差异。

总体来说multi-Paxos基于basic-paxos做了两点改进：

  1. 在所有Proposers中选举一个Leader，由Leader唯一地提交Proposal给Acceptors进行表决。这样没有Proposer竞争，解决了活锁问题。在系统中仅有一个Leader进行Value提交的情况下，Prepare阶段就可以跳过，从而将两阶段变为一阶段，提高效率。
  2. 针对每一个要确定的值，运行一次Paxos算法实例（Instance），形成决议。每一个Paxos实例使用唯一的Instance ID标识。

首先multi-Paxos是要选举一个leader的，宗师提到：可以通过basic-paxos进行leader的选举。

  • 选举leader后，只能由leader提出proposal。
  • 在leader宕机后，服务将临时不可用，等待leader重新选举。
  • 在系统中仅有一个leader进行proposal提交的情况下，prepare阶段可以跳过。

multi-paxos通过改变prepare阶段的作用范围至后面leader提交的所有实例，从而使得leader的连续提交只需要执行一次prepare阶段，后续只需要执行accept阶段，将两阶段变为一阶段，提高了效率。为了区分连续提交的多个实例，每个实例使用一个instance ID标识，instance ID由leader本地递增生成即可。

multi-paxos允许有多个自认为是leader的节点并发提交proposal而不影响其安全性，这样的场景即退化为basic-paxos。

paxos回顾，思考几个题目吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
怎么解决两个提案提出后陷入死循环？
---------------------------------------------------------
三个节点的集群A、B、C。
A和B通过提案[4, 6]，C没有通过任何提案。
此时C收到客户端请求，将值设置为5，C生成的编号为5，通过basic-paxos后。

最后集群中通过的提案应该是多少呢？
---------------------------------------------------------
假如有三个提案者A, B, C，五个接受者SERV1, SERV2, SERV3, SERV4, SERV5
A提案编号为1，值为3
B提案编号为2，值为5
C提案编号为3，值为8

①A第一阶段发给SERV1, SERV2, SERV3获得回应，赢得半数选票
②B开始第一阶段，获得SERV3, SERV4, SERV5的选票
③A开始第二阶段，发给SERV1值为3的提案后，SERV1允许提交该值，此时A宕机
④B开始第二阶段，发给SERV5值为5的提案后，SERV5允许提交该值，此时B宕机
⑤C开始第一阶段，获得SERV1, SERV2, SERV5的选票，根据规定，它将收到SERV1接受的值为3，SERV5接受的值为5。
那C的第二阶段提案应该是[3, 3]还是[3, 5]呢？

----------------------------------------------------------
multi-paxos提出leader的角色，提案只能由leader提出，那么当写性能达到leader的瓶颈，怎么解决呢？

答：应该裂变分区，拆成多个不相干的分区，由多个paxos-group来完成之前一个leader的工作

参考文章：https://zhuanlan.zhihu.com/p/31780743。文中提到paxos推导过程，也可以了解下。