关于paxos:MultiMasterPaxos3

Background

200 行代码实现 paxos-kv 中介绍了一款十分简洁的分布式 kv 存储实现，它是基于 classic-paxos 实现分布式一致性。在 paxos 的直观解释 中咱们提到，每次写入，也就是每个 paxos 实例须要 2 轮 RPC 实现，效率低。

一个常见的优化就是 mutli-paxos（或 raft），用一次 RPC 对多个实例运行 phase-1；再对每个实例别离运行 phase-2，这样均摊开销是一次 RPC 实现一次写入。它通过 phase-1 在集群中确定了一个惟一可写的 leader。这种设计在跨机房（或跨云）部署的环境中的缺点是：异地机房的写入就须要 2 个 RTT 能力实现：

client → leader → followers → leader → client

也就是说它无奈做到 异地多活，在 3 节点的场景里，有 2/3 的写入效率升高到 2 个 RTT。

本文从另一角度登程来解决异地多活的问题，3 机房部署的 3 正本集群中：

• 任一节点都可写，
• 任一笔写入都能够严格在 1 个 RTT 内实现。

这就是明天要介绍的 200 行代码实现 paxos-kv 的改进版: mmp-3: multi-master-paxos 3 正本实现。

同样 show me the code 的准则不能变：本文实现的 3 节点多活代码在: mmp3

异地多活是目前分布式畛域越来越被器重的一个问题，机房正在变成单机，单机房多机分布式在当初大规模部署的业务中曾经满足不了业务的可用性需要了。

简直所有线上环境部署的分布式存储, 都须要跨机房（或者跨云）的部署。而大家也踊跃在解决这些问题：

• 或者用队列等最终一致性的伎俩来实现跨机房的复制，这样会产生数据不统一，2 条互相冲突的数据可能同时被写入；业务层须要参加解决这类抵触。
• 或者将数据做拆分。将在 A 地写入多的调配到 A 机房为 leader 的 sharding，将 B 地写入较多的数据调配到 B 机房为 leader 的 sharding。
• 或者一个机房为主：部署 2 个正本，另一个机房部署 1 个副原本造成 3 正本的集群，这样实际上 A 机房故障会导致全局不可读写，B 机房只能提供额定的数据冗余，无奈提供更多的数据可用性。

paxos 在集群较小时能够通过定制 paxos 来实现 1 个 RTT 的写入, 如果应用 majority-quorum, 最多反对 5 个正本的多活.

在 epaxos 定义的多活设计，简略介绍了 3 节点的设计，但并没有给出实现的细节，其中各种抵触的解决以及修复的流程并没有明确的定义。

• 同时 epaxos 的 apply 算法存在不可解决的 livelock 问题：通过 SCC 来确定 instance 程序无奈保障在无限工夫内完结。
• 另外 epaxos 的设计中短少一个 rnd 记录（paxos 中的 last-seen-ballot 或 vbal），导致其一致性实现是谬误的。
• 以及 instance 之间的依赖关系会在修复过程中产生不统一的问题。
• epaxos 须要另外一个 seq 来确定 instance 之间的程序，在 mmp3 的设计中，seq 是不必要的，只需依赖关系就能够确定确定的 apply 程序。

Multi master paxos – 3

咱们从 classic-paxos 登程来剖析问题。

xp 的 tips：要实现一个稳固的分布式系统，最好用 raft，因为开箱就用。要学习分布式系统，最好从 paxos 开始。raft 看似简略的设计暗藏了一些费解的条件，其正确性的证实要比 paxos 简单。

咱们须要达到 2 个目标：

• 1 个 RTT 实现一次 commit。
• 3 个节点同时无抵触写。

1 RTT 的 classic- paxos

如果 classic-paxos 不须要 2 个 RTT，咱们就不须要 multi-paxos 或 raft 这些货色来优化提早了。

在 3 节点的零碎中，这是能够实现的。

首先做一些根底的设定：一个 replica 在零碎中是一个 replica（或叫作 server 或 node）。它同时是 proposer 和 acceptor。一个 replica 承受到一个写入申请时，它就用本地的 proposer 来实现提交。

回顾 classic paxos

200 行代码实现 paxos-kv 介绍的 classic-paxos 写入流程如下，replica-0 上的 proposer P0，依次实现 phase-1, phase-2 和 commit：

🤔 思考以上过程…

优化 classic paxos 为 1 个 RTT

因为 proposer 自身只是一个数据结构，在 paxos 中，它不须要跟 acceptor 有什么绑定关系，所以，咱们能够 让 proposer 运行在任何一个 replica 上：把 proposer 发到另一个 replica 上运行，这样音讯的传输就能够转变成 proposer 的传输。

要达到 paxos 要求的 2/3 的多数派，也只须要将 proposer 发到另外一个 replica，因为这个 proposer 永远只有 1 个实例，所以不会呈现不统一（proposer 或者在 R0 上工作或者在在 R1 上工作）。

如果要将 proposer 发到 2 个 replica 就会简单一些，例如 5 节点中 quorum=3，2 个不同的 proposer 可能会尝试应用不同的值。

通过发送 proposer 的形式，paxos 能够被优化成如下的 1 RTT 实现：P0 在 R1 上依次执行 phase-1 和 phase-2，而后再被送会 R0：

在传输 proposer 的过程中，区别于原始 paxos 的是：往返两个过程都要包含 proposer 的残缺信息：

• R0 到 R1 的过程中，要带上用户要提交的值，以便在 R1 上 Prepare 胜利后间接运行 Accept；
• R1 到 R0 的过程中，要带上 R1 的 Prepare 和 Accept 的执行后果。

这样一轮 RPC 后, R0 和 R1 就能够造成多数派, 而后 R0 能够间接 commit。

留神，这个模型中，除了 proposer 的地位变动了，跟 classisc-paxos 没有任何区别！也就是说，任何 paxos 能实现的事件它都能够实现。

当初咱们实现了第一个工作。如果以此模型来重写 200 行代码实现 paxos-kv，能够在 3 正本零碎上实现 1 RTT 提交，但多写入点仍然会有抵触，例如 R0 和 R1 同时发动同一个 paxos instance 的写入，R0 在收到发送回来的 P0 后，可能就会发现本地的 instance 曾经被 P1 以更高的 ballot 笼罩了，要从新晋升 P0 的 ballot 再重试。

这就是咱们要解决的第二个问题：防止不同 replica 的写入抵触。

Multi column log

2 个 replica 同时写一个 instance 产生存锁，导致无奈保障 1 个 RTT 实现写入。要防止抵触，咱们就须要让每个 replica 不能产生互相冲突的 instance，所以给每个 replica 调配 instance 的空间要离开。

在 mmp3 的实现中，有 3 个 replica 就须要有 3 列 instance，每个 replica 只写其中一列。

例如:

• R0 保护一个 proposer P0，一直的运行 paxos 在每个 replica 上 column A 的 instance，
• R1 保护 proposer P1，只写每个 replica 上的 column B 列的 instance。

这种构造有点相似于 3 个规范的 raft 组，每组都部署在 3 个 replica 上，第 i 组的 raft 的 leader 就是 R[i]

这样，因为没有 instance 抵触，所以不管任何一个 replica 上收到的写申请，都只需 1 个 RTT 实现 instance 的提交。

然而！

这 3 列的 instance 目前还是 无关 的，要想将 instance 利用到 state machine，所有 replica 上的 instance 都必须以雷同的程序 apply。（不像 raft 里的 instance 是简略的枯燥递增的，只有保障 instance 统一，apply 的程序就统一）。

因而在 mmp3 中，除了 instance 内容统一外，还须要额定减少每列 instance 之间的束缚，来保障 apply 程序统一。3 个 column 中的 instance 之间是一种（较弱但统一的）拓扑程序，因而在 mmp3 中，paxos 要确定的值（Value）包含 2 个：

• 用户要提交的数据：一条操作 state machine 的日志：instance.Val，
• 还须要确定这个 instance 与其余 instance 的关系。

应用 paxos 确定 instance 之间的关系

这个 关系 咱们形容为：一个 instance  X 看到了哪些其余 instance：用 X.Deps 来示意，用它来确定 instance 之间的 apply 的程序：

例如在单机零碎中，并发写入 3 条数据 a，b，c，能够这样确定 a，b，c 的程序：如果 a 写入时没有看到 b，那么 a 就在 b 之前运行。所以可见性就示意了 instance 之间的程序。

当然这个思路在分布式系统中要简单一些，因为多个 replica 之间没有单机中的锁的爱护，多个 replica 上同一个 instance 看到的其余 instance 也可能不一样。

最终 mmp3 中的 instance 数据结构相比 classic-paxos，多了一个 Deps 字段：

• instance.Deps：看到了哪些其余的 instance.

message Ins {
    InsId          InsId

    Cmd            Val
    repeated int64 Deps // <--

    BallotNum      VBal // <--
    bool           Committed
}

Deps 的实现包含以下步骤的变动：

Proposer 抉择 Deps 的值

在下面 1-RTT 的 classic-paxos 根底上:

• 在初始化 instance X 的时候（也就是创立 X 后，在本地 replica 执行 prepare 的时候），将以后 replica 上所有晓得其存在的 instance 汇合初始化为 X.Deps（包含 replica 上能看到的所有 instance，以及这些 instance 看到的 instance，尽管间接看到的 instance 可能不存在于以后 replica）
• 执行 accept 的时候, 最终 X.Deps 的值为 2 次 prepare 取得的 Deps 的 并集 作为 accept 的值。

例如 instance a4，在创立它的 replica 上和被复制到的另一个 replica 上别离看到 b2, c2 和 b1, c3，对应失去的 2 个 a4.Deps 别离是: [4, 2, 2] 和 [4, 1, 3]：

那么 a4 将用来运行 accpet 的 Deps 值就是 [4, 2, 3]：

classic-paxos 中要求 prepare 阶段看到的已存在的值要应用，而 mmp3 中将所有 prepare 阶段看到的 Deps 的值做了并集, 实际上并没有毁坏 paxos 的束缚，只不过 classic-paxos 假如它的 值是任意的，不肯定可取并集，mmp3 中能够把 prepare 过程中看到的 Deps 的值认为是 VBal 为 0 的一个值。

读者能够自行验证，它不会毁坏 classic-paxos 要求的任何束缚。

因为 X.Deps 的值的确定也通过 paxos，所以能够保障每个 replica 上的每个 instance 最终提交的 Deps 都是统一的。

这时再通过一个确定的算法应用每个 instance Deps 的值来决定 apply 的程序，就能够保障多个 replica 上的 state machine 最终状态统一。

以上两点满足了 apply 算法的第一个要求：Consistency。此外，apply 的程序还需提供另外一个保障 Linearizability，即: 如果 propose A 产生在 commit B 之后，那么 A 应该在 B 之后 apply。

这是一个直觉上的要求: 如果一个命令 set x=1 发给存储系统并返回 OK(committed)，那么这之后发给存储的 get x 命令，应该肯定能看到 x=1 的值。

实际上 xp 认为在分布式系统全局范畴内应用相对工夫的先后并不是一个感性的抉择。不过它更容易被业务应用。

接下来咱们设计一个算法来满足 Linearizability 的要求：

Apply 算法: 有环有向图中节点的定序

Interfering instance

mmp3 中设定：任意 2 个 instance 都是 interfering 的，即，替换 2 个 instance 的 apply 程序会导致后果不同（尽管可能是能够调换程序的）。

epaxos 中认为 set x=1 和 set y=2 这 2 个 instance 能够调换程序，因为 x 的值跟 y 的值无关，但 set x=y 和 set y=2 这 2 个 instance 不能调换程序 appl，因为程序的变动会产生不同的 x 的后果。也是因为 epaxos 须要通过缩小 interfering 的数量来实现 1 个 RTT，所以才有了这个设计。

在 3 replica 的零碎中，mmp3 有无抵触都只须要 1 个 RTT，所以咱们能够无需放心 interfering 的 instance 的抵触带来的另一个 RTT 开销。只需假如任意 2 个 instance 都是 interfering 的，这样反倒能简化问题。

Lemma-0: instance 之间的依赖关系

定义 A 依赖 B，即 A → B 为：A.Deps ∋ B

因为 mmp3 假设任意 2 个 instance 都是 interfering 的，并且 2 个 instance 提交的 quorum 必然有交加，所以任意 2 个 instance 之间至多有一个依赖关系，即, A, B 之间的关系只可能是：

• A → B
• B → A
• A ↔ B

依赖关系形成一个可能带环的有向图, 例如依照以下工夫程序执行：

• R0 propose a1，a1.Deps = [1, 0, 0]，
• R1 propose b1，b1.Deps = [0, 1, 0]，
• R0 send a1 to R1，a1.Deps = [1, 1, 0]
• R1 send b1 to R0，b1.Deps = [1, 1, 0]
• R0 commit a1
• R1 commit b1

这样 a1 ∈ b1.Deps 且 b1 ∈ a1.Deps

依赖关系很直观，这个依赖关系的图中，咱们将试图寻找一个无限大小的汇合来实现一个无效的 apply 算法。

Lemma-1: 用 Deps 确定 Linearizability

首先咱们有一个小论断:

如果 A 在 B commit 之后被 propose，那么肯定有 A.Deps ⊃ B.Deps。

因为 B 如果 commit 了，那么 B.Deps，也就是 B 看到的所有其余 instance 的 id 汇合，就曾经复制到了某个 quorum。那么 A 在运行 paxos 的时候，肯定会看到 B commit 的 B.Deps 的值。

又因为 A.Deps 是 2 个在 prepare 阶段看到的 Deps 的值的并集，因而 A.Deps 肯定蕴含全副 B.Deps 的 instance。

于是实现 apply 算法的思路就是：

• 如果 A.Deps ⊃ B.Deps，先 apply B，即能够保障 Linearizability。
• 其余状况下，抉择何种程序都不会毁坏 Linearizability，所以 mmp3 中应用 instance 的（columnIndex, index）的大小排序来确定 apply 程序。

epaxos 提供了一种简略粗犷的办法来在有环图中确定 apply 程序：从图中一个节点登程：找到最大连通子图（Strongly-Connected-Component or SCC）（没有出向边的一个节点也是一个 SCC），而后依照节点，也就是 instance 的某个属性（例如 epaxos 中应用（seq，instanceId））来排序一个 SCC 中的节点，再按程序 apply.

epaxos 的 SCC 算法有个问题，就是一个 SCC 可能有限增大，例如 A commit 之前有另一个 interfering 的 instance B 被 propose，而后 B commit 之前又呈现 interfering 的 instance C…,

那么 epaxos 的做法就无奈保障在无限工夫内找出 SCC。

epaxos 倡议中断一小段时间的新 instance 的 propose 来断开 SCC，这也是不容易实现的，因为必须在 n-1 个 replica 同时中断才无效。只有有 2 个 replica 在继续的写入新 instance，那么就有可能造成无限大的 SCC。

Lemma-2: 不须要 SCC

第 2 个小论断：

如果 A、B 不属于同一个 SCC，即 A ∈ SCC₁ B ∉ SCC₁，那么：

• A → B ⇒ A.Deps ⊃ B.Deps
• B → A ⇒ B.Deps ⊃ A.Deps

因为依据 Lemma-0，任意 2 个 instance 至多有一个依赖关系，如果 X ∈ B.Deps 且 X ∉ A.Deps，那么必然有 X → A，导致 A → B → X → A 成为一个 SCC。

因而，不管 A、B 是否在一个 SCC 中，保障 Linearizability 的条件都能够用 Deps 来确定，所以咱们的算法不用寻找 SCC，只需遍历依赖关系。

减小遍历数量：只需思考最老的 instance

以上 apply 算法还能够进一步优化为最多只思考 3 个 instnace 的形式：

假如 a1，a2 是 column-A 上相邻的 2 个 instance，那么肯定有 a1 ∈ a2.Deps，依据 apply 算法设计，a1.Deps ⊃ a2.Deps 肯定不成立，a2 肯定不会在 a1 之前 apply：

• 如果 a1 不依赖 a2，a1 肯定先 apply，
• 如果 a1 依赖 a2，但 a1 的（a3.columnIndex, a3.index）较小，所以 a1 也肯定会在 a2 之前 apply。

因而只需思考每个 column 上最老的一个未 apply 的 instance 就能够找出下一个 apply 的 instance。在 mmp3 中，最多有 3 个（但算法自身不限于 3）。

Lemma-3: Deps 汇合数量来决定

定义一个依赖数量：|X.Deps| 为 X 依赖的，未 apply 的 instance 的所在 column 的数量。

例如：a3.Deps = [3, 2, 2]：

• 如果实现 apply 的 instance 是 [2, 1, 1]，即 a1, a2，b1，c1，那么此时 a3 在 3 个 column 上都依赖一个未 apply 的 instance:|a3.Deps|=3
• 之后如果 c2 被 apply 了，那么 |a3.Deps|=2

这里能够分明的看到一个论断：A.Deps ⊃ B.Deps ⇒ |A.Deps| > |B.Deps|

最终 apply 算法为：

找到一个 column 高低一个已 commit，未 apply 的 instance X，遍历 X.Deps，失去未遍历过的 column 上的最老的未 apply 的 instance，遍历完结后，抉择（|X.Deps|, X.columnIndex）最小的一个 apply 到 state machine。

下次再 apply 时，从新结构这个图，找到第二个要执行的 instance。

必须从新遍历，因为之前排序第 2 的 instance，在新退出一个 instance 之后可能还是第 2。

这样，每个 replica 上，committed 的 instance 的 Deps 值都一样，最老的 3 个 instance 形成的依赖图也都一样，于是找出第 1 个 apply 的 instance 也一样，反复这个步骤，找出的第 2 个 apply 的 instance 也一样… 最终每个 replica 上的 state machine 达到统一的状态，保障了 Consistency。

Apply 执行的例子

例如以下 20 个 instance 的 Deps 关系是一个有向图，最终生成的 apply 程序是一个单向门路：

RPC 的超时重试

paxos 假如工作在一个网络不牢靠的环境中，在规范的实现中，如果某个申请超时，实践上应该进行重试。mmp3 的运行环境假如与 classic-paxos 一样，也须要对超时重试。这里跟 classic-paxos 有一点差异，就是 重试时必须晋升本人的 BallotNum，从新在本地执行 prepare，再用新的 BallotNum 重发 RPC。

这是因为 prepare 过程中，在每个 replica 上失去的 Deps 值可能不同

例如 R0 propose 的 instance X，在 R1 和 R2 上的 prepare 后，可能会别离失去不同的 X.Deps 的值（2 个 replica 蕴含的 instance 不同）应用同一个 BallotNum 无奈辨别哪一个才是最新的值。重试晋升 BallotNum，能力保障最初被确定的值能被辨认进去。

一个修复过程（例如 R0 宕机后，R1 或 R2 都能够从新运行 paxos 进行修复）在 R1 和 R2 上看到 2 个不同 BallotNum 的 X，那么阐明较小 BallotNum 的 X 没有胜利返回应答给 R0，R0 放弃了它，并进行了重试。这时只需思考较大 BallotNum 的 instance，它是惟一可能被 R0 commit 的。

以下是重试过程：

recovery

下面提到的重试机制为正确的 recovery 做好了筹备：当 R0 发动一轮 paxos 后并宕机了，R1 或 R2 都能够通过超时查看来发现这个问题并修复未 commit 的 instance。要修复的内容仍旧是 2 个：instance 要执行的命令 Val，以及 instance 看到哪些其余的 instance: Deps。

因为这 2 个值都是通过 classic-paxos 来确立的，修复过程也很简略，晋升 BallotNum 再运行一次 paxos 就能够了。相当于将 R0 的 leadership 抢走赋予给了另一个 replica。

代码和测试

git repo mmp3 是一份本文介绍的 multi-master 的三正本实现（mmp3 分支），其中次要的 server 端 instance 提交的逻辑实现在 mmp.go，apply 算法实现在 apply_* 中。

代码中除了根本的单元测试，最次要的是：Test_set_get 对一个三正本集群进行随机读写压测，这个测试中模仿发送和承受的网络谬误（各 20% 几率）在这种状况下，查看：

• 全副写申请都提交
• 3 个 replica 的 instance 统一
• 3 个 replica 上 apply 程序统一，以及最终 state machine 中的状态统一。

Limitation

mmp3 设计上只反对 3 节点零碎, 其次这个实现中不蕴含成员变更实现。

总结

mmp3 是一个齐全对等的设计实现的 multi-master consensus。之前在试图基于 epaxos 实现一个 multi-master 的存储，两头却发现几处不易修复的问题（开始还有几个容易修复的问题），于是打算本人设计一套。

期待与对这个方向感兴趣各路神仙交换蛋逼~

Reference:

• 200 行代码实现基于 paxos 的 kv 存储: https://mp.weixin.qq.com/s/YZ…
• classic paxos: http://lamport.azurewebsites….
• 牢靠分布式系统 -paxos 的直观解释: https://mp.weixin.qq.com/s/fg…
• multi-master-paxos-3: https://github.com/openacid/p…
• 多数派读写的少数派实现: https://zhuanlan.zhihu.com/p/…

对于 Databend

Databend 是一款开源、弹性、低成本，基于对象存储也能够做实时剖析的旧式数仓。期待您的关注，一起摸索云原生数仓解决方案，打造新一代开源 Data Cloud。

• Databend 文档：https://databend.rs/
• Twitter：https://twitter.com/Datafuse_…
• Slack：https://datafusecloud.slack.com/
• Wechat：Databend
• GitHub：https://github.com/datafusela…

文章首发于公众号：Databend