关于rust:将-Paxos-和-Raft-统一为一个协议-Abstractpaxos

前言

之前写了一篇 Paxos 的直观解释，用简略的语言形容了 paxos 的工作原理，看过的敌人说是看过的最易懂的 paxos 介绍，同时也问我是否也写一篇 raft 的。但 raft 介绍文章曾经很多很优质了，感觉没什么可写的，就始终拖着。起初想起来，在分布式岗的面试中，会常常被问到 raft 和 paxos 有什么区别，尽管可能会惹恼面试官，但我会说：没区别。明天介绍一个把 paxos 和 raft 等对立到一起的分布式一致性算法 abstract-paxos，解释各种分布式一致性算法从 0 到 1 的推导过程。算是填了 raft 的坑，同时在更形象的视角看 raft，也能够很容易看出它设计上的有余和几个优化的办法。为了分明的展示分布式一致性协定要解决的问题，咱们将从 0 开始，即从 2 个根本需要：信息确定 和分布式 开始。推导出所有的分布式强统一协定的对立模式，而后再把它特例化为 raft 或 paxos。本文的整个推导过程顺着以下过程，从 assumption 开始，最终达到 protocol：

本文构造

• 提出问题
• 协定推导
• • 定义 commit
  • 定义 零碎状态（State）
• 协定形容
• 工程实际
• 成员变更
• 应用 abstract-paxos 形容 paxos
• 应用 abstract-paxos 形容 raft

问题

从咱们要解决的问题登程：实现一个 分布式 的、强统一的 存储 零碎。存储系统是存储信息的，咱们首先给出 信息 和分布式存储 的定义：

香农信息定义

香农信息实践定义：信息是用来打消随机不定性的货色 。具体来说，对某个信息的 读操作，每次失去的内容应该都是惟一的，确定的。这个定义将贯通本文，作为咱们设计一致性协定的最基本的公理。

分布式存储

• 存储系统能够看做一个能够依据外部命令（Cmd）扭转零碎状态（State）的货色。例如一个 key-value 存储，set x=1 或 set x=y+1 都能够看做一个 Cmd。

• 而分布式则示意存储系统由多个节点（node）组成（一个 node 能够简略的认为是一个过程），存储系统的操作者是多个并发的写入者（write）和读取者（reader）。

• 而一个牢靠的分布式也意味着它必须容许宕机：它必须能容忍局部节点宕机还能失常工作。

所以它必须有 冗余 ，即：每个节点存储一个 State 的正本，而咱们须要的分布式一致性协定的目标，就是保障对外界观察者（reader）可能提供保障 香农信息定义 的 State 的信息。零碎要提供在 writer 或 reader 只能拜访到 局部 节点时零碎也能工作，这里的 局部 节点在分布式畛域个别定义为一个 quorum：

Quorum

一个 quorum 定义为一个节点（node）汇合。e.g. HashSet<NodeId>。

在这个零碎中，分布式 的个性要求 writer 只需能分割到一个 quorum 就能够实现一个 信息 的写入，即：实现 quorum-write。 而 reader 只须要分割到一个 quorum 就能够确定的读取到 信息，即实现 quorum-read。因为 writer 写入的信息 reader 必须能读到，所以任意 2 个 quorum 必须有交加：

大部分时候，一个 quorum 都是指 majority，也就是多于半数个 node 的汇合。例如【a,b】，【b,c】，【c,a】是汇合【a,b,c】的 3 个 quorum。

如果 任何一个 reader 都能通过拜访一个 quorum 来读到某个数据，那么这条数据就满足了 香农信息定义，咱们称这条数据为 commit 的。Commit

Commit

依据 香农信息定义 ， 如果写入的数据肯定能通过某种办法读取到，则认为它是 committed。\
如果某个数据有时能读到有时不能，它就不是一个 信息。

不确定读的例子

例子 1: 读到不确定的后果

例如上面 3 个 node N1，N2，N3 的 例子 1，

• N1 存储了[x,y]，
• N3 存储了 [z]，

应用 quorum-read 去读的时候，有时能失去【x,y】（拜访 N1,N2），有时能失去【z】（拜访 N2,N3）\
所以【x,y】和【z】在这个零碎中都不是信息，都不是 commit 实现的状态。

例子 2: 总能读到的后果

而像以下这个 例子 2，一次 quorum-read 不管落到哪 2 个 node 上，都能看到【z】\
所以【z】在这个零碎中有机会成为一个信息。\
这时还不能确定【z】是一个信息，因为这里如果 reader 拜访 N1,N2，还波及到是选【x,y】还是选【z】作为零碎以后的状态的问题，也就是说读取的后果还不能保障惟一。前面持续探讨。

因而，咱们就失去了在一个多正本的存储系统中 commit 实现的条件：

• commit- 写 quorum：以保障任何 reader 都可读到。
• commit- 惟一：以保障多个 reader 返回雷同的后果。
• commit 后不能批改：以保障屡次读返回同样的后果。

咱们先解释这几个条件，接着探讨如何设计一个 commit 的协定来满足这几个条件，从而达到一致性。

commit- 写 quorum

一个数据必须有机会被 reader 见到：即一个数据曾经写到一个 quorum 中：commit- 写 quorum。

commit- 惟一

这里惟一是指，在可见的根底上，减少一个惟一确定的要求：

例如在下面的例子 2 中，如果 reader 一次读操作拜访到 N1, N2 这 2 个  node，那么它收到的看到的 2 个 State 的正本别离是【x,y】和【z】，这 2 个 State 的正本都是可见的，但作为一个存储系统，任何一个 reader 都必须抉择同样的 State 作为以后零碎的 State（否则违反香农信息定义的打消不确定性的准则）。

所以咱们对读操作还要求 reader 能有方法在所有可见的正本中惟一确定的抉择一个 State，作为读操作的后果。

commit 后不能批改

香农信息定义 要求一个 commit 实现的 State 必须永远可被读到：即要求 commit 的 State 不能被笼罩和批改，只能 减少。

State 不能被批改有点反直觉,，因为个别的存储系统,，先存储了 x=1，还能够批改为 x=2。看起来是容许批改的。这里能够这样了解：经验了 x=1，再到 x=2 的一个 State（【x=1, x=2】），跟间接到 x=2 的 State（【x=1,】）是不同的。这个不同之处体现在：可能有个工夫点，能够从第一个 State 读出 x=1 的信息，而第二个 State 不行。

常见的 State 定义是：一个 Cmd 为元素的，只容许 append 的 list：Vec<Cmd>.

这也就是一个记录变更操作（Cmd）的日志（log），或称为 write-ahead-log(WAL). 而零碎的 State 也由 WAL 惟一定义的。在一个典型的 WAL + State Machine 的零碎中（例如 leveldb），WAL 决定了零碎状态（State），如这 3 条 log：【set x=1, set x=2, set y=3】，而平时人们口中的 State Machine，仅仅是负责最终将整个零碎的状态出现为一个 application 方便使用的模式，即个别的 HashMap 的模式：【x=2, y=3】。

所以在本文中，WAL 是实在的 State，咱们这里说的不能批改，只能追加，就是指 WAL 不能批改，只能追加。本文中咱们不探讨 State Machine 的实现。如果把存储系统的 State 看做是一个汇合，那么它必须是一个只增的汇合：

State

本文的目标仅仅是来对立 paxos 和 raft，不须要太简单，只需把 State 定义为一个只能追加的操作日志：

log 中的每个 entry 是一个扭转零碎状态的命令（Cmd）。

这是 State 的初步设计，为了实现这个一致性协定，前面咱们将对 State 减少更多的信息来满足咱们的要求。

依据 commit- 写 quorum 的要求，最终 State 会写到一个 quorum 中以实现 commit，咱们将这个过程临时称作 phase-2。它是最初一步，在执行这一步之前，咱们须要设计一个协定，让整个 commit 的过程也恪守：

• commit- 惟一，
• commit 后不能批改

的束缚。首先看如何让 commit 后的数据 惟一， 这波及到 reader 如何从 quorum 中多个 node 返回的不同的 State 正本中抉择一个作为 读操作的最终后果：

reader：找出没有实现 commit 的 State 正本

依据 香农信息定义 ，曾经 commit 的 State 要求肯定能被读到，但多个 writer 可能会（在互不通晓的状况下）并发的向多个 node 写入 不同 的 State。

写入了不同的 State 指：两个 State：s₁, s₂，如果 s₁ ⊆ s₂ 和 s₂ ⊆ s₁ 都不满足，那么只有一个是可能被 commit 的。否则就产生了信息的失落。

而当 reader 在不同的 node 上读到 2 个不同的 State 时，reader 必须能排除其中一个必定没有 commit 的 State，如 例子 2  中形容问题。

即，commit- 惟一 要求：两个 非蕴含关系 的 State 最多只有一个是可能 commit 状态的。并要求 2 个 State 能够通过相互比照，来排除掉其中一个必定不是 commit 的 State，这示意 State 之间存在一个 全序关系：即任意 2 个 State 是能够比拟大小的，在这个大小关系中：

• 较大的是可能 commit 的，
• 较小的肯定不是 commit 的。

State 的全序关系

State 的 全序关系 来示意 commit 的有效性，但到目前为止，State 自身是一个操作日志，也就是一个 list，list 之间只有一个 偏序关系，即蕴含关系。互不蕴含的 2 个 list 无奈确定大小关系。

例如, 如果在 2 个节点上别离读到 2 个 log：【x, y, z】和【x, y, w]】，无奈确认哪个是可能 commit 的，哪个是肯定没有 commit 的：

所以 State 必须具备更多的信息让它能造成全序关系。并且这个全序关系是可控的：即，对任意一个 State，能够使它变得比任何已知 State 大。 否则，writer 在试图 commit 新的数据到零碎里时将无奈产生一个足够大的 State 让 reader 去选它，导致 writer 无奈实现 commit。

给 State 增加用于排序的信息

例如上面 例子 3 中，如果每个 node 都为其 State 减少一个序号（在例子中的角标地位），那么 reader 不管分割到哪 2 个节点，都能够确定抉择序号更大的【y】作为读取后果，这时就能够认为【y】是一个信息了。

而 commit 后不能批改 的准则要求零碎所有的批改，都要基于已 commit 的 State，所以当零碎中再次 commit 一个数据后可能是在【y】s 之上追加【z,w】：

为了实现上述逻辑，一个简略的实现是让最初一个 log 节点决定 2 个 State 之间的大小关系。

于是咱们能够对 State 的每个 log 节点都须要退出一个偏序关系的属性 commit_index（本文为了简化形容, 应用一个整数）来确定 State 的全序关系：

在前面的例子中，咱们将 commit_index 写成每条 log 的下标的模式，例如

将示意为：

同时定义一个 method 用来获得一个 State 用于比拟大小的 commit_index：

commit_index 的值是由 writer 写入 State 时决定。即 writer 决定它写入的 State 的大小。

如果两个 State 不是蕴含关系，那么大小关系由 commit_index 决定。writer 通过 quorum-write 写入一个足够大的 State，就能保障肯定被 reader 抉择，就实现了 commit。

这也暗示了：

• 非蕴含关系的 2 个 State 的 commit_index 不能雷同。否则 State 之间无奈确定全序关系。即，任意 2 个 writer 不容许产生雷同的 commit_index。

• 同一个 writer 产生的 State 肯定是蕴含关系，不须要应用 commit_index 去决定大小：

  对于 2 个蕴含关系的 State：sₐ ⊆ sᵦ，显然对于 reader 来说，应该抉择更大的 sᵦ，无需 commit_index 来确定 State 的大小。因而一个 writer 产生的 State，容许多个 log 的 commit_index 雷同。并用 log 的长度确定大小关系。

这样咱们就失去了 State 的大小关系的定义：

State- 全序定义

两个 State 的程序关系：通过 commit_index 和 log 长度确定，即比拟 2 个 State 的：（s.commit_index(), s.log.len()）。

下面提到，commit_index 是一个具备偏序关系的值，不同类型的 commit_index 会将 abstract-paxos 具体化为某种协定或协定族，例如：

• 如果 commit_index 是一个整数，那就是相似 paxos 的 rnd。
• 而 raft 中，与 commit_index 对应的概念是【term, Option<NodeId>】，它是一个偏序关系的值，也是它造成了 raft 中选举容易呈现抵触。

对于 abstract-paxos 如何映射为 paxos 或 raft，在本文的最初探讨。

另一方面，从 writer 的角度来说：

• 如果一个 writer 能够生成一个 commit_index 使之大于任何一个已知的 commit_index，那么这时 abstract-paxos 就是一个活锁的零碎：它永远不会阻塞，但有可能永远都不会胜利提交。例如 paxos 或 raft
• 如果一个 writer 无奈生成任意大的 commit_index，那么它就是一个死锁的零碎，例如 2pc

当然也能够结构 commit_index 使 abstract-paxos 既活锁又死锁，那么能够认为它是一个联合了 paxos 和 2pc 的协定。

有了 State 之间的全序关系，而后再让 writer 保障 phase-2 写到 quorum 里的 State 肯定是最大的，进而让 reader 读取时都能够抉择这个 State，达到 香农信息定义 要求的信息确定性要求，即 commit- 惟一 的要求，实现 commit：上面来设计协议，实现这一保障：

协定设计

当初咱们来设计整个协定，首先，有一个 writer w，w 最终 commit 的操作是在 phase-2 将 State 写到一个 quorum。writer 的数据结构定义为一个它抉择的 quorum，以及它决定应用的 commit_index：

因为 reader 读取时，只选它看到的最大的 State 而疏忽较小的。所以如果一个较大的 State 曾经 commit，那么整个零碎就不能再容许 commit 一个较小的 State，否则会造成较小的 State 认为本人 commit 实现，但永远不会被读到，这就造成了信息失落。

例如上面 例子 5 中形容的场景，如果最终写入 State 前不做进攻，那么是无奈实现 commit 的：假如有 2 个 writer w₁, w₂ 同时在写它们本人的 State 到本人的 quorum：

• t1 工夫 w₁ 将【y₅】写到 N2, N3,
• t2 工夫 w₂ 将【x₁,y₇】写到了 N1。

那么当一个 reader 分割到 N1, N2 进行读操作时，它会认为【x₁,y₇】是 commit 实现的，而真正由 w₁ commit 的数据就失落了，违反了 香农信息定义。

所以：writer 在 commit 一个 State 前，必须阻止更小的 State 被 commit。这就是 phase-1 要做的第一件事：

Phase-1.1 阻止更小的 State 被 commit

假如 writer w₁ 要写入的 State 是 s₁，在 w₁ 将 s₁ 写到一个 quorum 前，整个零碎必须阻止小于 s₁ 的 State 被 commit。

因为不同的 writer 不会产生同样的 commit_index。所以整个零碎只需阻止更小的 commit_index 的 State 被 commit：

为达到这个目标，在这一步，首先告诉 w₁ quorum 中的每个节点：回绝所有其余 commit_index 小于 w₁。commit_index 的 phase-2 申请。

于是咱们基本上能够确定 node 的数据结构，它须要存储 phase-2 中真正写入的 State，以及 phase-1.1 中要回绝的 commit_index：

在前面的例子中，咱们将用一个数字前缀示意 node 中的 commit_index，例如：

将示意为:

一个间接的推论是, 一个 node 如果记录了一个 commit_index , 就不能承受更小的 commit_index , 否则意味着它的进攻生效了: Node.commit_index 枯燥增。如果 writer 的 phase-1.1 申请没有被 quorum 中全副成员认可，那么它无奈平安的进行 phase-2， 这时只能终止。最初咱们整顿下 phase-1.1 的流程：

每个 node 在 P1Reply 中返回本人之前保留的 commit_index，writer 拿到 reply 后跟本人的 commit_index 比照，如果 w.commit_index >= P1Reply.commit_index，示意 phase-1.1 胜利。实现 phase-1.1 后，能够保障没有更小的 State 能够被 commit 了。而后，为了满足 commit 后不能批改 的准则，还要求 s₁ 必须蕴含所有已提交的，commit_index 小于 s₁.commit_index() 的所有 State：

Phase-1.2 读已实现 commit 的 State

因为 commit 的条件之一是将 State 写入一个 quorum，所以 w₁ 询问 w₁.quorum，就肯定能看到小于 w₁.commit_index 的，已 commit 的其余 State。这时 writer 是一个 reader 的角色（如果遇到大于 w₁.commit_index 的 State，则以后 writer 是可能无奈实现提交的，应终止）。\
且读过某个 node 之后，就不容许这个 node 再承受来自其余 writer 的，小于 w₁.commit_index 的 phase-2 的写入。以防止读后又有新的 State 被 commit，这样就无奈保障 w₁ 写入的 State 能蕴含所有已 commit 的 State。\
w₁ 在不同的节点上会读到不同的 State，依据 State 的全序的定义，只有最大的 State 才可能是已 commit 的（也可能不是, 但更小的肯定不是），所以 w₁ 只有选最大的 State 就能保障它蕴含了所有已 commit 的 State。\
在最大 State 的根底上，减少 w₁ 本人要写的内容。最初进行 phase-2 实现 commit。\
phase-1.1 跟 phase-1.2 个别在实现上会合并成一个 RPC，即 phase-1。

Phase-1

Phase-1: Data

Phase-1: Req

Phase-1: Reply

Phase-1: Handler

Phase-2

最初，保障了 s₁ 以后最大，和 commit 后不能批改这两个条件后，第 2 阶段，writer 就能够平安的写入一个 s₁ 实现 commit。\
如果 phase-2 实现了，则示意 commit 肯定胜利了，任何一个 reader 都能读到惟一确定的 State s₁（除非有更大的 State 被写入了）。\
反之，如果有其余 writer 通过 phase-1 阻止了 w₁.commit_index 的写入，那么 w₁ 的 phase-2 就可能失败，这时就退出 commit 过程并终止。

这里有一个学习分布式系统时常常提出的问题：

Q:

因为在 phase-1 中 w 曾经阻止了所有小于 w.commit_index 的 State 的提交，phase-2 是否能够写入一个小于 w.commit_index 的 State？

A:

不能够，phase-2 写入的 State 的 commit_index() 跟 w.commit_index 相等时能力保障平安，简略剖析下：

• 显然要写的 s₁.commit_index() 不能大于 w₁.commit_index，因为 phase-1.1 没有爱护大于 w₁.commit_index 的 State 的写入。
• 尽管在 phase-1 阶段，零碎曾经阻止了所有小于 s₁.commit_index() 的其余 State 的 phase-2 写入，如果 w₁ 写的 State 的 s_1.commit_index() 小于 w.commit_index，那么零碎中可能存在另一个稍大一点的 State (但没有 commit，导致 reader 不认为 s₁ 是 commit 的。

例如：

• 一个 writer w₅ 在 t1 工夫实现了 phase-1，在 t2 工夫 phase-2 只写入了 N1；
• 而后另一个 writer w₆ 在 t3 工夫实现了 phase-1，phase-2 只写入了一个较小的 commit_index=4 的 State。

那么某个 reader 如果通过拜访 N1,N2 读取数据，会认为 N1 上的【x₅】是 commit 的，毁坏了 香农信息定义。

所以必须满足：s₁.commit_index() == w₁.commit_index 这时，只有将 State 写入到 w₁.quorum，就能够认为提交。
对应每个 node 的行为是：在每个收到 phase-2 申请的节点上，如果 node 上没有记录回绝 commit_index 以下的 phase-2 申请，就能够承受这笔写入。\
一个推论：一个节点如果承受了 commit_index 的写入，那么同时它应该回绝小于 commit_index 的写入了。因为较小的 State 肯定不是 commit 的，如果承受，会造成信息失落。

Phase-2: data

• 和 phase-1 相似，一个 node 返回它本人的 commit_index 来示意它是否承受了 writer 的 phase-2 申请。
• 在 P2Req 中，如果 state 是残缺的，commit_index 总是与 state.commit_index() 一样，能够去掉；这里保留是因为之后将会探讨到的分段传输：每个申请只传输 State 的一部分，这时就须要额定的 P2Req.commit_index。

Phase-2: Req

Phase-2: Reply

Phase-2: Handler

也就是说 phase-2 不止可能批改 Node.state，同时也会批改 Node.commit_index。

这里也是一个学习分布式容易产生误解的中央，例如很多人已经认为的一个 paxos 的 bug: paxos-bug。

这里也很容易看出为何在 raft 中必须以后 term 复制到 quorum 才认为是 commit 了。

可反复的 phase-2

要保障写入的数据是 commit 的，只需保障写入一个 quorum 的 State 是最大的即可。所以 writer 能够一直追加新的日志，不停的反复 phase-2。Writer 协定形容

Writer 协定形容

最初将整个协定组装起来的是 writer 的逻辑，如前所讲，它须要先在一个 quorum 上实现 phase-1 来阻止更小的 State 被 commit，而后在 quorum 上实现 phase-2 实现一条日志的提交。

工程实现

Phase-2: 增量复制

这个算法的正确性 还需思考工程上的不便，到目前为止，算法中对 State 的写都假如是原子的。但在工程实现上，State 是一个很大的数据结构，很多条 log 所以在 phase-2 传输 State 的过程中，咱们还须要一个正确的分段写的机制：准则还是保障 香农信息定义，即：commit 的数据不失落。

• State 不能留空洞：有空洞的 State 跟没空洞的 State 不同，不能通过最初一条日志来确定其所在的 State 大小。
• writer 在 phase-1 实现后能够保障肯定蕴含所有曾经 commit 的 State。

所以在一个承受 phase-2 的 node 上，它 Node.state 中任何跟 Writer.State 不同的局部都能够删除，因为不统一的局部肯定没有被 commit。以下是 phase-2 过程中删除 N3 上不统一数据的过程：

• t1 时刻，writer W 分割到 N1，N2 实现 phase-1，读到最大的 State【x₃,z₅】，增加本人的日志到最大 State 上：【x₃,z₅,w₆】，这时零碎中没有任何一个 node 的 State 是 commit 实现状态的，一个 reader 可能抉择【x₃,z₅】作为读取后果（拜访 N1,N2），可能抉择【x₃,y₄】作为读取后果（拜访 N2,N3）。

但这时一个 State 的子集：【x₃】是 commit 实现的状态。

• t2 时刻，W 向 N3 复制了一段 State：【x₃】，它是 N3 本地日志的子集，不做变动。

  这时 reader 还是可能读到不同的后果，同样【x₃】是 commit 实现的状态。

• t3 时刻，W 向 N3 复制了另一段 State z₅，它跟 N3 本地 State 抵触，于是 N3 放弃本地的一段与 writer 不统一的 Statey₄，将本地 State 更新为：【x₅,z₅】

这时【x₅,z₅】是 commit 实现状态。

• t4 时刻，W 持续复制 w_6 到 N3，这是【x₅,z₅,w_4】是 commit 实现状态。

Snapshot 复制

snapshot 复制跟 State 分段复制没有本质区别，将 State 中的 log 从 0 到某一范畴以压缩后的模式传输的到其余 node。

成员变更

为反对成员变更，咱们先退出上面这几个行为来反对成员变更操作：

• State 中某些日志（config 日志）示意集群中的成员配置。
• State 中最初一个成员配置（config）日志呈现就开始失效。
• config 日志与一般的日志写入没有区别。

config 定义一个集群的 node 有哪些，以及定义了哪些 node 汇合是一个 quorum。

例如一个一般的 3 成员集群的 config【{a,b,c}】，它定义的 quorum 有

再如一个由 2 个配置组成的 joint config【{a,b,c}, {x,y,z}】。它定义的 quorum 汇合是【a,b,c】的 quorum 汇合跟【x,y,】的 guorum 汇合的笛卡尔积：

而后，咱们对成员变更减少束缚，让成员变更的过程同样保障 香农信息定 的要求：

成员变更束缚 -1

首先，显然有 2 个相邻 config 的 quorum 必须有交加。否则新配置启用后就立刻会产生脑裂。即：

在前面的探讨中咱们将满足以上束缚的 2 个 config 的关系示意为：cᵢ ~ cᵢ₊₁。

例如：假如 State 中某条日志定义了一个 joint config：【{a,b,c}, {x,y,z}】那么，

• 下一个非法的 config 能够是：
• • uniform config【{a,b,c}】，
  • 或另一个 joint config【{x,y,z}, {o,p,q}】。

• 但不能是【{a,x,p}】，因为它的一个 quorum【a,x}】与 上一个 config 的 quorum【{b,c}, {y,z}】没有交加。

成员变更 Lemma-1

对 2 个 config cᵢ ~ cⱼ，以及 2 个 State Sᵢ 和 Sⱼ 如果 Sᵢ 和 Sⱼ 相互不是子集关系，Sᵢ 在 cᵢ 上 commit 跟 Sⱼ 在 cⱼ 上 commit 不能同时产生。

成员变更束缚 -2

因为 2 个不同 writer 提出（propose）的 config 不肯定 有交加，所以为了满足 commit- 惟一  的条件， 蕴含新 config 的日志要提交到一个新，旧配置的 joint config 上。即, cᵢ₊₁ 必须在【cᵢ, cᵢ₊₁】上 commit. cᵢ₊₁ 之后的 State，只需应用 cᵢ₊₁ 进行 commit。

然而，当 writer 中断，另一个 writer 看到 cᵢ₊₁ 时，它不晓得 cᵢ₊₁ 处于变更两头，也就是说新的 writer 不晓得当初的 commit 应该应用【cᵢ, cᵢ₊₁】，它只应用【cᵢ₊₁】。
所以对 config 日志向 joint config 的 commit 分为两步：

• 先在旧配置上回绝更小的 State 的提交，再 propose 新配置。依据成员变更 Lemma-1，即：至多将一个与 w.commit_index 雷同的 State commit 到 cᵢ 上。

• 再 propose cᵢ₊₁，从日志 cᵢ₊₁ 之后的日志开始，都只需 commit 到 cᵢ₊₁ 上。

最初总结：

成员变更的约束条件

• 上一个 config 在以后 commit_index 上提交后才容许 propose 下一个配置。
• 下一个配置必须跟最初一个已提交的配置有交加。

成员变更举例

• raft 只反对以下的成员变更形式 c1 → c1c2 → c2 → c2c3 → c3 …其中 c1c2 指 c1 跟 c2 的 joint config，例如：
• • cᵢ：【a, b, c】；
  • cᵢcⱼ：【{a, b, c}，{x, y, z}】。
• abstract-paxos 能够反对更灵便的变更:c1 → c1c2c3 → c3c4 → c4 或回退到上一个 config：c1c2c3 → c1

非法变更状态转换图示

上面的图示中简略列出了至少 2 个配置的 joint config 跟 uniform config 之间可转换的关系：

Variants

以上为 abastract-paxos 的算法形容局部。接下来咱们将看它是如何通过减少一些限度条件，absract-paxos 将其变成 classic-paxos 或 raft 的。

秒变 Paxos

• 限度 State 中的日志只能有一条，那么它就变成 paxos。
• 不反对成员变更。

其中概念对应关系为：

秒变 Raft

Raft 为了简化实现（而不是证实），有一些刻意的阉割：commit_index 在 raft 里是 一个 偏序关系 的 tuple，包含：

• term
• 和是否投票给了某个 Candidate：

其中 VotedFor 的大小关系（即笼罩关系：大的能够笼罩小的）定义是：

即，VotedFor 只能从 None 变动到 Some，不能批改。或者说，Some（A）和 Some（B）没有大小关系，这限度了 raft  选主时的胜利几率.。导致了更多的选主失败抵触。

commit_index 在每条日志中的存储也做了简化，先看间接嵌入后的构造如下：

raft 中，因为 VotedFor 的非凡的偏序关系的设计，日志中 Term 雷同则 voted_for 肯定雷同，所以最终日志里并不需要记录 voted_for，也能用来惟一标识日志，State，及用于比拟 State 的大小。最终记录为：

这样确实让 raft 少记录一个字段, 但使得其含意变得更加费解，工程上也引入了一些问题, xp 并不观赏这样的作法。但不否定 raft 的设计在呈现时是一个十分丑陋的形象，次要在于它对 multi-paxos 没有明确定义的问题，即多条日志之间的关系到底应该是怎么的，给出了一个确定的答案。

概念对应关系:

成员变更方面，raft 的 joint 成员变更算法将条件限度为只容许 uniform 和  joint 交替的变更：c0 -> c0c1 -> c1 -> c1c2 -> c2 ….
不难看出，raft 的 单步变更算法也容易看出是本文的成员变更算法的一个特例。

Raft 的优化

abstract-paxos 通过推导的形式，得出的一致性算法能够说是最形象最通用的。不像 raft 那样先给出设计再进行证实，当初从上向下看 raft 的设计，就很容易看出 raft 抛弃了哪些货色和给本人设置了哪些限度，也就是 raft 可能的优化的点：

•  一个 term 容许选出多个 leader：将 commit_index 改为字典序，容许一个 term 中先后选出多个 leader。
• 提前 commit：raft 中 commit 的规范是复制本 term 的一条日志到 quorum。这样在新 leader 刚刚选出后可能会延后 commit 的确认，如果有较多的较小 term 的日志须要复制的话。因而一个能够较快 commit 的做法是复制一段 State 时（raft 的 log），也带上 writer 的 commit_index 信息（即 raft leader 的 term）到每个 node，同时，对 State 的比拟（即 raft 的 log 的比拟）改为比拟【writer.commit_index, last_log_commit_index, log.len()】，在 raft 中，对应的是比拟【leader_term, last_log_term, log.len()】。
• 成员变更容许更灵便的变动：例如 c0c1 -> c1c2.

其中 1,3 曾经在 openraft 中实现（敌人说它是披着 raft 皮的 paxos/:-)）。

Reference

• 牢靠分布式系统 -paxos 的直观解释 : https://blog.openacid.com/alg…
• abstract-paxos : https://github.com/openacid/a…
• (Not a) bug in Paxos : https://github.com/drmingdrme…
• leveldb : https://github.com/google/lev…
• openraft : https://github.com/datafusela…
• Two phase commit : https://en.wikipedia.org/wiki…
• 偏序关系 : https://zh.wikipedia.org/wiki/ 偏序关系
• 字典序 : https://zh.wikipedia.org/wiki/ 字典序

对于 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