引言

关于一致性的话题，在分布式领域算是一个殿堂级的课题。但从各种文章上看出大家对其理解比较模糊，大概都能说出一些相关的概念，但都没法完全解析清楚。本篇文章我将从一致性说起，好好聊一聊对一致性概念的思考和理解，然后引出paxos算法。

关于paxos算法，先给出几个形容该算法的表述：

• Google Chubby的作者Mike Burrows说过:这个世界上只有一种一致性算法，那就是Paxos
• 计算机分布式系统中号称最难理解的协议-Paxos
• Paxos的作者Leslie Lamport写了篇paper，因此获得了图灵奖

可能大家对paxos不是很了解，而说起raft都知道。因为paxos的理论太抽象，无法很容易落地工程中，而raft作为multi paxos的一个应用，其贡献在于其一致性理论很好理解，落地又比较简单，所以被大家所熟知。raft很好地解释了HOW，但缺少WHY，而paxos从本质上解释了WHY。
本文从一致性的理论一步一步推导出paxos的核心理念，然后给出paxos的具体步骤（很多paxos的文章也只是谈了这一步，并没有给出理念）。

1. 一致性

一般我们在谈论一致性的时候，有的人会说事务中的ACID中的C，有的人会说是分布式事务中的强一致性，有的人会说是CAP理论上中C，也有的人会说是实现了paxos/raft算法的就是一致性结构。很多人都会对一致性的理解都是模凌两可的，拿这个一个领域内的原理去解释另一个领域的东西。

那今天我们来先好好说一说一致性这个问题。
在计算机软件领域，我们谈到一致性，其实会涉及到三个领域：数据库，业务逻辑以及分布式。

在数据库中，一致性是指事务特性中ACID的C，在事务的开始和结束以后，数据库的一致性约束没有被破坏。即以事务为单位，数据库从一个一致性状态变到另一个一致性状态。

在业务逻辑中，通常一份逻辑数据，被拆分到不同的数据库中甚至不同的系统中，我们没有办法使用本地事务来保证这份逻辑数据的原子性和一致性，这个时候通常可以借助分布式事务来解决，或者其他一些可补偿的机制。通常这些一致性都维持在弱一致性（最终一致性）层面上。

在分布式系统中，一致性（强一致性）是指一份逻辑数据冗余存在多个物理副本中，对其执行读写操作的表现行为是否一致的。这也符合CAP原理的阐述。（所以当有人让你举例CP场景的时候，千万别再拿银行转账说事了。）下面我们着重说一下分布式系统的一致性理论。

2. 分布式一致性

上面我们说到分布式系统一致性是指，一份逻辑数据冗余存在多个物理副本中，对其执行读写操作的表现行为是否一致的。我们下面来好好解读一下这句话。

首先，提问一下，什么一份逻辑数据需要冗余存在多个物理副本中？
核心点在于可用率。我们知道一些牛逼的系统的可用率都很高，可以达到9个9（99.9999999%）。这些牛逼的系统其实都是搭建在一些不那么可靠的硬件设施上。那提升可用率一个很明显的做法就是冗余恢复，我使用多台机器存在同一份数据，当一台机器出问题后，我可以读另一台机器。假设一台机器出问题的概率是1%，那两台都出问题的概率就是1%*1%，随着机器的增加，都出问题的概率越小，而从可用率得到有效提高。

然后，再来看“对其执行读写操作的表现行为是否一致”这句话。
多副本的意思是说同一份逻辑数据冗余在多个副本中，那么是否是说所有副本每时每刻都必须数据完全一样呢？
这个问题的答案是显然不需要的。我们引入多副本的目的在于提高可用率，即当出现某几台机器挂掉，或者网络不可达，或者数据延迟的时候，副本集群仍然可以给出正确的读写结果。
其实这里引出两个概念：状态视角的一致性和操作视角的一致性。
状态视角的一致性是说：所有副本的数据状态在任何时刻都是一致的。
操作视角的一致性是说：任何对副本集群的操作的结果是一致的。

然后再来引申一下，当多个副本中，因为一些原因（网络不可靠）出现数据状态的不一致的时候，整个副本集群可以通过自己的方式来对某个提议（操作）能够达成统一的意见。这个概念就叫做共识。这里我们只是简单聊一下共识，下面我们会详细讨论下这个问题。
对，这里也解释了，当我们说到paxos算法的时候，都说他是一个共识算法的原因。

3. 复制算法

上面说到一份逻辑数据冗余在多个副本中。如何冗余呢？
说到底就是数据复制，当一个副本收到一个新数据的时候，将这个数据复制给其他副本的动作。
下面我们来看一下常见的几种复制算法从引出我们的paxos。

主从同步复制

image.png

原理很简单，所有的读写交给主节点。当主节点收到写操作时，必须同步复制给所有从节点，只有所有从节点都返回成功后，主节点才向客户点返回成功。
这里的主从同步复制保证了上面提到的状态视角的一致性。
但是对于可用率来反而降低了。任何一个从节点失败，本次客户端的请求就会失败。

主从异步复制

image.png

原理上将也很简单，就是写请求只要写主节点就返回给客户端成功。
然后从节点异步复制。这也是MySQL binlog的复制策略。
异步复制解决了上面同步复制的可用率问题，但是如果当主节点写入成功到复制给从阶段这段时间，主节点故障，这样数据就丢失了。

多数派读写

我们既希望能保证可用率，又希望能够保证在部分机器挂的时候，不会数据丢失造成不一致。
那么思路就是写的时候，同步写一部分副本，其他副本异步去写。
这也就引出来多数派读写。
那么我们面临的问题是同步多多少个副本呢？读的时候？

image.png

如上图所示，我们怎么保证读到就是刚才写入的副本呢？
这里就引入多数派读写的理论。
假设，我们有3个副本（一般副本数都是奇数，至于为什么，聪明的你肯定能想出来），我们同步写2个，读的时候，如果一定到2个上都去读，那么无论我们读到的是哪2个，肯定至少能得到刚才同步写的一台机器上。
即多数派写的机器和多数派读机器的情况下，一定有重复机器。
（n/2+1）+(n/2+1) > n。
所以说多数派读写既有主从同步复制的数据一致性，又有主从异步复制的可用率（因为同步写，只需要超过半数的机器的成功就同步返回成功了）。

4. 从多数派读写引出paxos

版本号的引入

刚才说了多数派读写的基本原理，首先会面临一个问题：

image.png

假设3副本集群中a的初始状态是0，然后客户端将a改为1。副本1和副本2此时a=1，副本3的a=0，然后客户端进行多数派读，读到的是副本1和副本3，这样到底a是0还是1呢？
解决这个问题的办法就是引入版本号。
当写数据的时候，将版本号+1，这样，读取的时候，取版本号最大的那个。

共识问题

当我们引入版本号之后，其实还是会有问题。

image.png

首先客户端希望写入a1的值是1，然后当进行了多数派写后，还未返回客户端结果时，副本1宕机了。这样因为客户端收不到任何response，就会进行重试，那这次，突然又想把a的值设置为2了。
然后这是就出现的问题。版本号最大的是1，但1这个版本号居然对应了两个值。无法决定应该返回哪个值了。
我们把这个问题扩展引申一下，我们希望的是对同一件事（a1的更新）的多个提议，只能有一个提议被确认。

这里引申出一个很重要的概念：共识。
我们先来看一下共识的问题域的定义：

Assume a collection of processes that can propose values. A consensus algorithm ensures that a single one among the proposed values is chosen. If
no value is proposed, then no value should be chosen. If a value has been
chosen, then processes should be able to learn the chosen value. The safety
requirements for consensus are:
• Only a value that has been proposed may be chosen,
• Only a single value is chosen, and
• A process never learns that a value has been chosen unless it actually
has been.
We won’t try to specify precise liveness requirements. However, the goal is
to ensure that some proposed value is eventually chosen and, if a value has
been chosen, then a process can eventually learn the value.

这里解读一下，假设一个多节点的数据集群，每个节点都可以对同一件事进行提议，共识算法的目标是保证只会有一个提议被选择。
即：

1. 仅会有一个被提议的value被选择。
2. 被选择的提议将不会发生改变。
3. 一旦某个提供被选择，则任何一个节点最终都会学到这个被选择的提议值。

5. 引入paxos算法

5.1 思想

那么为了达到这个目的，我们应该如何解决呢？
如果只有一个acceptor的话，其实这个问题很好解决。第一个proposer提议后，拒绝后面所有的提议。有多个acceptor的话，如果每次读写都是对所有acceptor同步的话，这个问题就变成了单个acceptor的问题。但为了可用率，我们只允许每次读写，多数派成功后就可以。那应该怎么办呢？

paxos里引入一个很有意思的理念：反向理念。即让数据记住写入者。
paxos算法是通过引入两阶段的多数派读写+数据记忆来实现。
增加一个阶段的最主要目的为了让副本上记住最后一个提议者。使得二阶段的时候，副本只接受记录到的最后一个提议者。

5.2 roles

这里引入paxos算法的几个角色。一个副本节点可以同时担当几个角色，不会影响算法协议的正确性。

Client
表示发起请求给副本集群的客户端。
Acceptor (Voters)
就是副本集群中的普通节点。超过半数的Acceptors are called Quorums
Proposer
是副本集群中的某个节点，承接客户端的请求以及发起提议。
Learner
与协议算法本身无关。当一个值被确认后，发送给所有learner。learner用来对客户端作出响应。多数情况下，proposer也是一个learner。
目的为了提高可用率，可以增加learner的数量。

5.3 具体过程

paxos的两阶段分为两个步骤：prepare和accept
为了下面好理解，我们事先先定义几个概念：

round：代表一个提议。

• proposer端：
  round_num： 代表proposer发起一次提议标识。这个值递增。即每次发起提议时，这个值一定大于历史上发起过的round_num。
• acceptor端
  last_round_num：代表acceptor可以接受哪个proposer来写。
  v：代表acceptor已经写入的值
  v_round_num：代表v写入的时候，对应的proposer的round_num

image.png

5.3.1 Phase 1

第一阶段包括

Prepare过程

proposer向acceptor进行提议，发送一个round_num，这个值递增。即每次发起提议时，这个值一定大于历史上发起过的round_num。

Promise过程

当acceptor收到proposer的prepare请求后，需要向proposer保证，我以后只会接受你的请求。

if (last_round_num > round_num) { // 代表本次提议round_num是一个老的了，直接拒绝
    refuse;
}
set last_round_num = round_num; // 代表从现在开始我只接受last_round_num的提议

return (last_round_num, v, v_round_num);

5.2.2 Phase 2

Accept过程

当proposer收到多数派的acceptor的Promise返回值后，做出以下判断：

if (v全部都是null){ // v从来没有被设置过，那么我就设置自己想设置的值
    set accept_value = want_set_v;
} else {
    if (发现有一个的last_round_num要大于自己的round_num){// 本次提议为老提议
        中断本次提议;
    }else {// 这一步又叫做修复。修复在Phase1的时候，少数派的节点
        从多个acceptor的返回值中挑一个最大的v_round_num对应v
        set accept_value = v; round_num =  v_round_num;
    }
}
send round_num, accept_value

总结一句话，当发现有人已经设置v了，则我也设置v，保持不变。
如果都没人设置v，那我就设置自己想设置的值。
这一步也是保证了

只会有一个提议被确认的理论。

Accepted过程

当acceptor收到proposer的Accept请求后，拒绝不等于last_round_num的请求，然后更新v和v_round_num。

if (round_num != last_round_num) { //拒绝不等于last_round_num的请求。
    refuse;
}else{
    set v = accept_value;
    set v_round_num = round_num;
}

5.4 看paxos如何解决有冲突的现象

以下这张图解释了发生了冲突的时候，paxos是如何解决的。

image.png

图中已经画的很清楚了，就不做详细解释了。

5.5 活锁问题

其实paxos是有一个可能存在活锁的问题的。从上面我们知道当某个proposer失败后，它会递增round_num进行重试。
当两个proposer交替失败后重试后，可能出现循环锁的问题，导致一直都没法确认值。
如图所示

image.png

6. 扩展

我们上面说的额paxos实际上是最朴实的classic paxos。
classic paxos一直以来被诟病的地方是说，一次写入，需要两次rpc，影响效率。
所以Leslie Lamport老爷子对paxos进行了优化, multi paxso和fast paxos。

multi paxso

我们引入另一个角色：leader。
所有的提议都由leader来做，如果leader相对稳定的话。其实我们可以不要classic paxos中的第一阶段。
前面我们说过，第一阶段的一个最主要的目的是数据记忆，即我只允许你来修改我的值。那如果都是由leader来提议的话，第一阶段可以省略的。
如果省略，那round_num怎么搞的？
在实际应用中，我们一般都是对一组连续的value进行提议。
所以假设我们第一次提议的时候，两阶段，使用的round_num是N。那么后续直接使用N+1就可以了。这样后续的提议就只需要第二阶段就可以了。

而且，因为我们都是使用leader来提议，也解决了上面提到的活锁的问题。

我们熟知的raft，其核心就是multi paxos的一个应用。之所以raft比paxos流行的原因是因为raft的描述额更佳直白，更加工程化。

chubby，zookeeper，spanner等著名应用都是使用multi paxso协议的一些扩展。

fast paxso

没冲突：1轮rpc
有冲突：2轮rpc
意思就是说先直接进行第2次rpc写入看看，如果发现失败（多数派写入的时候副本的可接受的客户端不是本次请求的客户端），就会退化为class paxos。如果成功就成功了。
有点类似于JAVA中的偏向锁的概念。

参考文档：

https://blog.openacid.com/algo/paxos/
http://www.lamport.org/
http://lamport.azurewebsites.net/pubs/pubs.html#paxos-simple
http://lamport.azurewebsites.net/pubs/pubs.html#fast-paxos