一、Paxos 是什么

在分布式系统中保证多副本数据强一致性算法。

没有 paxos 的一堆机器, 叫做分布式

有 paxos 协同的一堆机器, 叫分布式系统

这个世界上只有一种一致性算法，那就是 Paxos … - Google Chubby 的作者 Mike Burrows

其他一致性算法都可以看做 Paxos 在实现中的变体和扩展，比如 raft。

二、先从复制算法说起

防止数据丢失，所以需要数据进行复制备份

2.1 主从异步复制

主节点接到写请求，主节点写本磁盘，主节点应答 OK，主节点复制数据到从节点

如果数据在数据复制到从节点之前损坏，数据丢失。

2.2 主从同步复制

主节点接到写请求，主节点复制日志到所有从节点，从节点可能会阻塞，客户端一直等待应答，直到所有从节点返回

一个节点失联导致整个系统不可用，整个可用性的可用性比较低

2.3 主从半同步复制

主接到写请求，主复制日志到从库，从库可能阻塞，如果 1~N 个从库返回 OK，客户端返回 OK

可靠性和可用性得到了保障，但是可能任何从库都没有完整数据

2.4 多数派写读

往一个主接节点写入貌似都会出现问题，那我们尝试一下往多个节点写入，舍弃主节点。

客户端写入 W >= N / 2 + 1 个节点, 读需要 W + R > N, R >= N / 2 + 1，可以容忍 （N - 1）/ 2 个节点损坏

最后一次写入覆盖先前写入，需要一个全局有序时间戳。

多数派写可能会出现什么问题？怎么解决这些问题呢？

三、从多数派到 Paxos 的推导

假想一个存储系统，满足以下条件：

1. 有三个存储节点 2. 使用多数派写策略 3. 假定只存储一个变量 i 4. 变量 i 的每次更新对应多个版本，i1，i2, i3..... 5. 该存储系统支持三个命令： 1. get 命令，读取最新的变量 i，对应多数派读 2. set <n> 命令，设置下版本的变量 i 的值<n>，直接对应的多数派写 3. inc <n> 命令, 对变量 i 增加<n>,也生成一个新版本，简单的事务型操作

3.1 inc 的实现描述

1. 从多数中读取变量 i，i 当前版本 1

2. 进行计算，i2 = i1 + n，i 变更，版本+1

3. 多数派写 i2，写入 i,当前版本 2

4. 获取 i，最新版本是 2

这种实现方式存在一下问题：

如果 2 个并发的客户端同时进行 inc 操作，必然会产生 Y 客户端覆盖 X 客户端的问题，从而产生数据更新丢失

假设 X，Y 两个客户端，X 客户端执行命令 inc 1，Y 客户端执行 inc 2，我们期望最终变量 i 会加 3

但是实际上会出现并发冲突

1. X 客户端读取到变量 i 版本 1 的值是 2

2. 同时客户端 Y 读取到变量 i 版本 1 的值也是 2

3. X 客户端执行 i1 + 1 = 3,Y 客户端执行 i1 + 2 = 4

4. X 执行多数派写，变量 i 版本 2 的值是 2，进行写入（假定 X 客户端先执行）

5. Y 执行多数派写，变量 i 版本 2 的值是 4，进行写入（如果 Y 成功，会把 X 写入的值覆盖掉）

所以 Y 写入操作必须失败，不能让 X 写入的值丢失 。 但是该怎么去做呢？

3.2 解决多数派写入冲突

我们发现，客户端 X，Y 写入的都是变量 i 的版本 2，那我们是不是可以增加一个约束：

整个系统对变量 i 的某个版本，只能有一次写入成功。

也就是说，一个值（一个变量的一个版本）被确定（客户端接到 OK 后）就不允许被修改了。

怎么确定一个值被写入了呢？在 X 或者 Y 写之前先做一次多数派读，以便确认是否有其他客户端进程在写了，如果有，则放弃。

客户端 X 在执行多数派写之前，先执行一个多数派读，在要写入的节点上标识一下客户端 X 准备进行写入，这样其他客户端执行的时候看到有 X 进行写入就要放弃。

但是忽略了一个问题，就是客户端 Y 写之前也会执行多数派读，那么就会演变成 X，Y 都执行多数派读的时候当时没有客户端在写，然后在相应节点打上自己要写的标识，这样也会出现数据覆盖。

3.3 逐步发现的真相

既然让客户端自己标识会出现数据丢失问题，那我们可以让节点来记住最后一个做过写前读取的进程，并且只允许最后一个完成写前读取的进程进行后续写入，拒绝之前做过写前读取进行的写入权限。

X，Y 同时进行写前读取的时候，节点记录最后执行一个执行的客户端，然后只允许最后一个客户端进行写入操作。

使用这个策略变量 i 的每个版本可以被安全的存储。

然后 Leslie Lamport 写了一篇论文，并且获得了图灵奖。

四、重新描述一下 Paxos 的过程（Classic Paxos）

使用 2 轮 RPC 来确定一个值，一个值确定之后不能被修改，算法中角色描述：

•Proposer 客户端

•Acceptor 可以理解为存储节点

•Quorum 在 99%的场景里都是指多数派, 也就是半数以上的 Acceptor

•Round 用来标识一次 paxos 算法实例, 每个 round 是 2 次多数派读写: 算法描述里分别用 phase-1 和 phase-2 标识. 同时为了简单和明确, 算法中也规定了每个 Proposer 都必须生成全局单调递增的 round, 这样 round 既能用来区分先后也能用来区分不同的 Proposer(客户端).

4.1 Proposer 请求使用的请求

// 阶段一 请求class RequestPhase1 {    int rnd; // 递增的全局唯一的编号，可以区分Proposer}

// 阶段二 请求class RequestPhase2 {     int rnd;    // 递增的全局唯一的编号，可以区分Proposer     Object v;   // 要写入的值 }

4.2 Acceptor 存储使用的应答

// 阶段一 应答 class ResponsePhase1 {     int last_rnd; // Acceptor 记住的最后一次写前读取的Proposer，以此来决定那个Proposer可以写入    Object v;     // 最后被写入的值    int vrnd;     // 跟v是一对，记录了在哪个rnd中v被写入了}

// 阶段二 应答class ResponsePhase2 {     boolean ok;}

4.3 步骤描述

阶段一

当 Acceptor 收到 phase-1 的请求时:

● 如果请求中 rnd 比 Acceptor 的 last_rnd 小，则拒绝请求

● 将请求中的 rnd 保存到本地的 last_rnd. 从此这个 Acceptor 只接受带有这个 last_rnd 的 phase-2 请求。

● 返回应答，带上自己之前的 last_rnd 和之前已接受的 v.

当 Proposer 收到 Acceptor 发回的应答:

● 如果应答中的 last_rnd 大于发出的 rnd: 退出.

● 从所有应答中选择 vrnd 最大的 v: 不能改变(可能)已经确定的值，需要把其他节点进行一次补偿

● 如果所有应答的 v 都是空或者所有节点返回 v 和 vrnd 是一致的，可以选择自己要写入 v.

● 如果应答不够多数派，退出

阶段二：

Proposer:

发送 phase-2，带上 rnd 和上一步决定的 v

Acceptor:

● 拒绝 rnd 不等于 Acceptor 的 last_rnd 的请求

● 将 phase-2 请求中的 v 写入本地，记此 v 为‘已接受的值’

● last_rnd==rnd 保证没有其他 Proposer 在此过程中写入 过其他值

4.4 例子

无冲突：

有冲突的情况，不会改变写入的值

客户端 X 写入失败，因此重新进行 2 轮 PRC 进行重新写入，相当于做了一次补偿，从而使系统最终一致

五、问题及改进

活锁（Livelock）： 多个 Proposer 并发对 1 个值运行 paxos 的时候，可能会互 相覆盖对方的 rnd，然后提升自己的 rnd 再次尝试，然后再次产生冲突，一直无法完成

然后后续演化各种优化：

multi-paxos：用一次 rpc 为多个 paxos 实例运行 phase-1

fast-paxos ： 增加 quorum 的数量来达到一次 rpc 就能达成一致的目的. 如果 fast-paxos 没能在一次 rpc 达成一致, 则要退化到 classic paxos.

raft: leader, term，index 等等..

六、参考

1. 文章主要来自博客：https://blog.openacid.com/algo/paxos/
   

2. 一个基于 Paxos 的 KV 存储的实现：https://github.com/openacid/paxoskv
   

3. Paxos 论文：https://lamport.azurewebsites.net/pubs/paxos-simple.pdf