vlambda博客
学习文章列表

将 paxos 和 raft 统一为一个协议: abstract-paxos

原文连接:  https://blog.openacid.com/algo/abstract-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可以简单的认为是一个进程), 存储系统的操作者是多个并发的写入者(writer)和读取者(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 必须有交集:

将 paxos 和 raft 统一为一个协议: abstract-paxos

大部分时候, 一个 quorum 都是指 majority, 也就是多于半数个node的集合. 例如{a,b}, {b,c}, {c,a} 是集合{a,b,c}的3个 quorum.

如果 任何一个 reader 都能通过访问一个 quorum 来读到某个数据, 那么这条数据就满足了 香农信息定义 , 我们称这条数据为 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 完成的状态.

将 paxos 和 raft 统一为一个协议: abstract-paxos

例子2: 总能读到的结果

而像以下这个 例子2, 一次 quorum-read 不论落到哪2个 node 上, 都能看到 [z].

所以 [z] 在这个系统中有机会成为一个 信息.

这时还不能确定 [z] 是一个信息, 因为这里如果 reader 访问 N1,N2, 还涉及到是选 [x,y] 还是选 [z] 作为系统当前的状态的问题, 也就是说读取的结果还不能保证 唯一. 后面继续讨论.

将 paxos 和 raft 统一为一个协议: abstract-paxos

因此, 我们就得到了在一个多副本的存储系统中 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=2])是不同的. 这个不同之处体现在: 可能有个时间点, 可以从第一个 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 定义为一个只能追加的操作日志:

将 paxos 和 raft 统一为一个协议: abstract-paxos

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 的:

将 paxos 和 raft 统一为一个协议: abstract-paxos

所以 State 必须具备更多的信息让它能形成全序关系.

并且这个全序关系是可控的: 即, 对任意一个 State, 可以使它变得比任何已知 State 大. 否则, writer 在试图 commit 新的数据到系统里时将无法产生一个足够大的 State 让 reader 去选它, 导致 writer 无法完成 commit.

给 State 添加用于排序的信息

例如下面 例子3 中, 如果每个 node 都为其 State 增加一个序号(在例子中的角标位置), 那么reader 不论联系到哪2个节点, 都可以确定选择序号更大的[y] 作为读取结果, 这时就可以认为[y] 是一个信息了.

将 paxos 和 raft 统一为一个协议: abstract-paxos

而 commit后不能修改 的原则要求系统所有的修改, 都要基于已 commit 的 State, 所以当系统中再次 commit 一个数据后可能是在[y]₅ 之上追加[z,w]:

将 paxos 和 raft 统一为一个协议: abstract-paxos

为了实现上述逻辑, 一个简单的实现是 让最后一个 log 节点决定2个 State 之间的大小关系.

于是我们可以对 State 的每个 log 节点都需要加入一个 偏序关系 的属性 commit_index (本文为了简化描述, 使用一个整数)来确定 State 的全序关系:

将 paxos 和 raft 统一为一个协议: abstract-paxos

在后面的例子中, 我们将 commit_index 写成每条 log 的下标的形式, 例如

将 paxos 和 raft 统一为一个协议: abstract-paxos

将表示为:

将 paxos 和 raft 统一为一个协议: abstract-paxos

同时定义一个 method 用来取得一个 State 用于比较大小的 commit_index:

将 paxos 和 raft 统一为一个协议: abstract-paxos

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 ww 最终 commit 的操作是在 phase-2 将 State 写到一个quorum. writer 的数据结构定义为一个它选择的 quorum, 以及它决定使用的 commit_index:

将 paxos 和 raft 统一为一个协议: abstract-paxos

因为 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 的数据就丢失了, 违背了 香农信息定义.

将 paxos 和 raft 统一为一个协议: abstract-paxos

所以: 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:

将 paxos 和 raft 统一为一个协议: abstract-paxos

在后面的例子中, 我们将用一个数字前缀表示 node 中的 commit_index, 例如:

将 paxos 和 raft 统一为一个协议: abstract-paxos

将表示为:

将 paxos 和 raft 统一为一个协议: abstract-paxos

一个直接的推论是, 一个 node 如果记录了一个 commit_index , 就不能接受更小的 commit_index , 否则意味着它的防御失效了: Node.commit_index 单调增.

如果 writer 的 phase-1.1 请求没有被 quorum 中全部成员认可, 那么它无法安全的进行 phase-2, 这时只能终止.

最后我们整理下 phase-1.1 的流程:

将 paxos 和 raft 统一为一个协议: abstract-paxos

将 paxos 和 raft 统一为一个协议: abstract-paxos

每个 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

将 paxos 和 raft 统一为一个协议: abstract-paxos

Phase-1: Req

将 paxos 和 raft 统一为一个协议: abstract-paxos

Phase-1: Reply

将 paxos 和 raft 统一为一个协议: abstract-paxos

Phase-1: Handler

将 paxos 和 raft 统一为一个协议: abstract-paxos

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 的, 破坏了 香农信息定义 .

将 paxos 和 raft 统一为一个协议: abstract-paxos

所以必须满足: 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

将 paxos 和 raft 统一为一个协议: abstract-paxos

  • 和 phase-1 类似, 一个 node 返回它自己的 commit_index 来表示它是否接受了 writer 的 phase-2 请求.

  • 在 P2Req 中, 如果 state 是完整的, commit_index 总是与 state.commit_index() 一样, 可以去掉; 这里保留是因为之后将会讨论到的分段传输: 每个请求只传输 State 的一部分, 这时就需要额外的 P2Req.commit_index.

Phase-2: Req

将 paxos 和 raft 统一为一个协议: abstract-paxos

Phase-2: Reply

将 paxos 和 raft 统一为一个协议: abstract-paxos

Phase-2: Handler

将 paxos 和 raft 统一为一个协议: abstract-paxos

也就是说 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 的逻辑, 如前所讲, 它需要先在一个 quorum 上完成 phase-1 来阻止更小的 State 被 commit, 然后在 quorum 上完成 phase-2 完成一条日志的提交.

将 paxos 和 raft 统一为一个协议: abstract-paxos

工程实现

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 上不一致数据的过程:

将 paxos 和 raft 统一为一个协议: abstract-paxos

  • 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 有

将 paxos 和 raft 统一为一个协议: abstract-paxos

再如一个由2个配置组成的 joint config [{a,b,c}, {x,y,z}]. 它定义的 quorum 集合是{a,b,c} 的 quorum 集合跟 {x,y,z}的 guorum 集合的笛卡尔积:

将 paxos 和 raft 统一为一个协议: abstract-paxos

然后, 我们对成员变更增加约束, 让成员变更的过程同样保证 香农信息定 的要求:

成员变更约束-1

首先, 显然有 2个相邻 config 的 quorum 必须有交集. 否则新配置启用后就立即会产生脑裂. 即:

将 paxos 和 raft 统一为一个协议: abstract-paxos

在后面的讨论中我们将满足以上约束的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 之间可转换的关系:

将 paxos 和 raft 统一为一个协议: abstract-paxos

Variants

以上为 abastract-paxos 的算法描述部分. 接下来我们将看它是如何通过增加一些限制条件, absract-paxos 将其变成 classic-paxos 或 raft 的.

秒变 Paxos

  • 限制 State 中的日志只能有一条, 那么它就变成 paxos.

  • 不支持成员变更.

其中概念对应关系为:

abstract-paxos classic-paxos
writer proposer
node acceptor
Writer.commit_index rnd/ballot
State.commit_index() vrnd/vbal

秒变 Raft

Raft为了简化实现(而不是证明), 有一些刻意的阉割:

commit_index 在 raft 里是 一个 偏序关系 的 tuple, 包括:

  • term

  • 和是否投票给了某个 Candidate:

将 paxos 和 raft 统一为一个协议: abstract-paxos

其中 VotedFor 的大小关系(即覆盖关系: 大的可以覆盖小的) 定义是:

将 paxos 和 raft 统一为一个协议: abstract-paxos

即, VotedFor 只能从 None 变化到 Some, 不能修改. 或者说, Some(A) 和 Some(B) 没有大小关系, 这限制了raft 选主时的成功几率. 导致了更多的选主失败冲突.

将 paxos 和 raft 统一为一个协议: abstract-paxos

commit_index 在每条日志中的存储也做了简化, 先看直接嵌入后的结构如下:

raft 中, 因为 VotedFor 的特殊的偏序关系的设计, 日志中 Term 相同则 voted_for 一定相同, 所以最终日志里并不需要记录voted_for, 也能用来唯一标识日志, State, 及用于比较 State 的大小. 最终记录为:

这样的确让 raft 少记录一个字段, 但使得其含义变得更加隐晦, 工程上也引入了一些问题, xp并不欣赏这样的作法.

但不否认 raft 的设计在出现时是一个非常漂亮的抽象, 主要在于它对 multi-paxos 没有明确定义的问题, 即多条日志之间的关系到底应该是怎样的, 给出了一个确定的答案.

概念对应关系:

abstract-Paxos raft
writer at phase-1 Candidate
writer at phase-2 Leader
node node
Writer.commit_index (Term,VotedFor)
State.commit_index() Term

成员变更方面, raft 的 joint 成员变更 算法将条件限制为只允许 uniform 和 joint 交替的变更: c0 -> c0c1 -> c1 -> c1c2 -> c2 ....

不难看出, raft 的 单步变更 算法也容易看出是本文的成员变更算法的一个特例.

Raft 的优化

abstract-paxos 通过推导的方式, 得出的一致性算法可以说是最抽象最通用的. 不像 raft 那样先给出设计再进行证明, 现在从上向下看 raft 的设计, 就很容易看出 raft 丢弃了哪些东西和给自己设置了哪些限制, 也就是 raft 可能的优化的点:

  • 1, 一个term允许选出多个 leader: 将 commit_index 改为 字典序, 允许一个 term 中先后选出多个 leader.

  • 2, 提前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()].

  • 3, 成员变更允许更灵活的变化: 例如 c0c1 -> c1c2.

其中1,3已经在 openraft 中实现(朋友说它是披着raft皮的paxos/:-)).

Reference:

  • 可靠分布式系统-paxos的直观解释 : https://blog.openacid.com/algo/paxos/

  • abstract-paxos : https://github.com/openacid/abstract-paxos

  • (Not a) bug in Paxos : https://github.com/drmingdrmer/consensus-bugs#trap-the-bug-in-paxos-made-simple

  • leveldb : https://github.com/google/leveldb

  • openraft : https://github.com/datafuselabs/openraft

  • Two phase commit : https://en.wikipedia.org/wiki/Two-phase_commit_protocol

  • 偏序关系 : https://zh.wikipedia.org/wiki/偏序关系

  • 字典序 : https://zh.wikipedia.org/wiki/字典序

本文链接: https://blog.openacid.com/algo/abstract-paxos