分布式一致性算法：Paxos

Posted on Edited on In Views:

1 引言（什么是 Paxos）

分布式系统流行的当下，集群的机器总会发生诸如机器宕机或网络异常（还有消息延迟、丢失、重复、乱序）等问题。分布式式一致性（强一致性）算法就是在系统中出现以上异常情况时，如何快速且正确地在集群内部对某个数据或者命令达成一致，并且保证不会破坏整个集群的一致性。Paxos 就是此类算法中一种，并且在分布式领域有着非常重要的地位。

Paxos 算法是基于消息传递且具有高度容错特性的一致性算法，是目前公认的解决分布式一致性问题最有效的算法之一。

2 一个问题

由一个实际场景作为出发点，介绍 Paxos（来自 Diego Ongaro）算法

image-20210704161321540

假设服务端 (Servers) 系统是实现了多副本状态机 (Replicated state machine)，客户端发送的命令将会被保存为一个日志，以特定的顺序保存，并且被同步模块同步到集群的其他机器上，然后被各自的状态机消费，最后将结果返回给客户端。其中，如果日志的内容和顺序都相同，多个进程从同一状态开始，并且以相同的顺序获得相同的输入，那么可以预见的是这些进程将会生成相同的输出，并且结束在相同的状态。

问题

如何保证复制后的日志数据在每台机器上都一样？

3 不太完美的解决方案

为解决上述问题，此小节进行一些方案讨论，用以引出 Paxos 算法。

主从异步复制

主从异步复制是较为简单的策略之一，但是存在一个问题。客户端接收到服务端返回的 200 OK 的结果码后，就认为数据已经安全，但是距离主节点将数据复制到全部结点还有一个时间空隙，这段时间内，若主节点宕机或者网络异常，则数据可能丢失，因此该策略不可靠。

具体复制概念参考文章

主从同步复制

主从同步复制能够完整数据的完整性，同步复制保证了全部数据都被复制到所有结点上，主节点才返回客户端 200 OK，但是同步复制的缺点是，延迟很大（主节点需要等待所有从节点都返回 200 OK 后才返回给客户端结果），若是有从节点宕机或者网络异常，同步复制会一直阻塞下去。

主从半同步复制

在同步和异步之间，做一个折中，看起来是一个不错的方案，这就是半同步复制。它要求 Leader 在应答客户端之前必须把数据复制到足够多的机器上，但不需要是全部。这样副本数够多可以提供比较高的可靠性；1 台机器宕机也不会让整个系统停止写入。
但该策略还是有缺点，例如数据A 复制到节点1, 但没有到达节点2; 数据B 复制达到了节点2 但没有到达节点1, 这时如果主节点挂掉了需要从某个从节点恢复出数据，任何一个节点都不能提供完整的数据。所以在整个系统中，数据存在某种不一致。

多数派写 (Quorum)

为了解决半同步复制中数据不一致的问题，可以将这个复制策略再做一改进: 多数派读写: 每条数据必须写入到半数以上的机器上。每次读取数据都必须检查半数以上的机器上是否有这条数据。即，如果集群中有 N 个节点，客户端需要写入 W >= N/2 + 1 个节点。不需要主节点。这种方法可以容忍最多 (N-1)/2 个节点故障。

在这种策略下，数据可靠性足够，宕机容忍足够，任一机器故障也能读到全部数据.

多数派写 (Quorum) 后写入优胜

由于多数派写无法区分写入数据的版本，此时也可能数据数据不一致问题。如：

  • 第一次更新时：节点 1、节点 2 都写入了 A = x;
  • 第二次更新时：节点 2、节点 3 都写入了 A = y;

此时若一个客户端发送读取 A 的请求到节点 1 和节点 2 时，会得到 2 条不一样的数据。

基于以上问题，可以对多数派写进行优化，加入一个全局单调递增的时间戳作为一个版本号，并且规定最新版本的优先级高于旧版本。如此，客户端读取 A 的请求发送到节点 1 和节点 2 时，可以针对两条不一样的数据进行版本比较，取最新版本的即可。

缺点

上述带版本号的多数派写入仍然存在问题，在客户端没有完成一次完整的多数派写的时候，例如，上面的例子中：

  • 第一次更新时：节点 1、节点 2 都写入了 A = x;
  • 第二次更新是：节点 3 写入了 A = y，客户端进程挂掉；

此时集群中的状态为：

1
2
3
节点1： A = x
节点2： A = x
节点3： A = y

同一时间，另外一个客户端读取时：

  • 如果请求发送到节点 1 和节点 2 时，此时 A = x
  • 如果请求发送到节点 2 和节点 3 是，此时 A = y

对外的提供的信息仍然不一致。

4 方案推演优化（Paxos 的思想雏形）

假设

假设有一个分布式存储系统，配置为 3 个存储节点，使用多数派写的策略，系统提供以下功能：

  • 只能存储一个变量 i;
  • i 具有版本区分，随着每次更新，版本号也随之更新: i1、i2、i3....
  • 对变量 i 只能有 3 种更新操作：
    • get 读取变量 i 最新版本的值；
    • set<n> 将变量 i 的值更新为 n，并更新版本号；
    • inc<n> 对变量 i 的值增加 n，并更新版本号；

使用此分布式存储系统来更清晰地展示出对一致性问题多数派写的不足，以及如何用 Paxos 来解决这些问题；

系统实现

对于上述系统提供的 get、set<n>、inc<n> 命令的实现

  • get：对应多数派读（若集群节点数量为 N，则至少需要读取 N/2 + 1 个节点的数据）；
  • set<n>：对应多数派写逻辑；
  • inc<n>：拆分为几步，为一个事务型操作：
    1. get 多数派读操作，读取变量 i 最新数据；
    2. 将 i2 = i1 + n
    3. set<i2>

并发问题

如果有 2 个并发的客户端进程同时做这个 inc 的操作，在多数派读写的实现中，必然会产生一个 Y 客户端覆盖 X 客户端的问题。从而产生了数据更新点的丢失。

image-20220715233011323

提取一下上面提到的问题：让 Y 去更新的时候不能直接更新 i2，而是应该能检测到 i2 的存在，进而将自己的结果更新到下一个版本 i3 中，再写回系统中。

问题进一步抽象：变量 i 的每个版本只能被写入一次，不允许修改。如果系统设计能满足这个要求，那么 X 和 Y 的 inc 操作就都可以正确被执行了。

解决方案

这里引申出一个更基础的问题：如何确定变量 i 的某个版本是否已经被写入到系统？

一个最直观的的解决方法是：在客户端 X 或 Y 写之前先做一次多数派读，以便确认是否有其他客户端进程已经在写了，如果有，则放弃。

image-20220715233851788

此方法还是有个并发问题：客户端 X 和 Y 可能同时做这个写前读取的操作，并且同时得出一个结论：还没有其他进程在写入，我可以写。这样还是会造成更新丢失的问题。

可以通过为所有的存储节点添加一个功能来解决这个问题，即，每个存储节点必须记住谁最后一个做过写前读取的操作，并且只允许最后一个完成写前读取的客户端进程可以进行后续写入，同时拒绝之前其它写前读取的进程写入的权限（类似于保持最新版本的一个写前读取的操作）。

image-20220715234846368

总结

以上的优化方案为 paxos 的核心思想。

最终的问题只需要解决:

  • 如何标识不同客户端？例如：客户端 X 和 Y；
  • 如何确认谁是最后一个完成写前读写的进程？
  • …

5 Basic Paxos 算法描述

Basic Paxos 很多地方也称作 Classic Paxos。

Basic Paxos 的价值在于开拓了分布式共识算法的发展思路，但它因有如下缺陷，一般不会直接用于实践：Basic Paxos 只能对单个值形成决议，并且决议的形成至少需要两次网络请求和应答（准备和批准阶段各一次），高并发情况下将产生较大的网络开销，极端情况下甚至可能形成活锁。总之，Basic Paxos 是一种很学术化但对工业化并不友好的算法，现在几乎只用来做理论研究。实际的应用都是基于 Multi Paxos 和 Fast Paxos 算法的。

基本概念

  • Proposer：提议发起者「主动」，处理客户端请求，将客户端的请求发送到集群中，以便决定这个值是否可以被批准

  • Acceptor：提议批准者「被动」，负责处理接收到的提议，他们的回复就是一次投票。会存储一些状态来决定是否接收一个值

    同一个集群服务器，同时可以有多个角色「Proposer 、Acceptor」

  • Proposal：提议发起者 Proposer 提出的值

  • Proposal Number：提议者提出的值的编号，每个请求带有唯一编号

    Round Number Server Id
    Round Number：为 Proposer 发起提议的次数，单调递增 为发起 Proposal 的 Proposer「服务器」Id，如：服务器名称

    Round Number 更大，则优先级更高；
    规则：提案者必须选择一个比之前见过的还大的提案值

两个原则

a. Safety - 安全原则

安全原则保证算法不能做错的事，即：

  • 针对某个实例的表决只能有一个值被批准，不能出现一个被批准的值被另一个值覆盖的情况；(假设有一个值被多数 Acceptor 批准了，那么这个值就只能被学习)
  • 每个节点只能学习到已经被批准的值，不能学习没有被批准的值。

有点类似于前面解决方案提到的方式

每个存储节点必须记住谁最后一个做过写前读取的操作，并且只允许最后一个完成写前读取的客户端进程可以进行后续写入，同时拒绝之前其它写前读取的进程写入的权限（类似于保持最新版本的一个写前读取的操作）。

b. Liveness- 存活原则

存活原则 - 只要有多数服务器存活并且彼此间可以通信，最终都要做到的下列事情：

  • 最终会批准某个被提议的值；
  • 一个值被批准了，其他服务器最终会学习到这个值。

算法过程

将前面总结和问题抽象一下：Basic-Paxos 只会 Chosen 一个值。基于此，就需要一个两阶段（2-phase）协议，对于已经 Chosen 的值，后面的提案也要使用相同的值。

思想：

每个存储节点必须记住谁最后一个做过写前读取的操作，并且只允许最后一个完成写前读取的客户端进程可以进行后续写入，同时拒绝之前其它写前读取的进程写入的权限（类似于保持最新版本的一个写前读取的操作）。

两阶段算法

image-20220716222240683

Phase 1: 准备阶段（Prepare PRCs）

  • 找到已经被选中的值
  • 阻止旧的提案

Phase 2: 接受阶段（Accept RPCs）

  • 请求 Acceptors 接受值

image-20220716223056759

过程

Phase 1: 准备阶段（Prepare PRCs）

  1. Proposer 选择一个提案编号 n；
  2. 向所有的 Acceptor 广播 Prepare(n) 请求；
  3. Acceptor 接收到 Prepare(n) 请求，此时有两种情况：
    1. 如果 n 大于之前接受到的所有 Prepare 请求的编号 minProposal，则返回响应，并承诺将不会接收编号小于 n 的提案。如果之前已经有提案被 Chosen 的话，响应还应包含前一次提案编号 acceptedProposal 和对应的值 acceptedValue;
    2. 否则（即 n 小于等于 Acceptor 之前收到的最大编号）忽略，但一般会回复一个拒绝响应；
  4. Proposer 接收到 Acceptors 的响应后，查看响应中是否包含 acceptedValue，如果有的话，说明之前已经有提案被 Chosen，替换当前 Proposal 的值为 Chosen 的值 (Conflicting Choices 问题)；

Phase 2: 接受阶段（Accept RPCs）

  1. 向所有的节点广播 Accept(n, value) 请求；
  2. Acceptor 收到 Accept() 请求，在这期间如果 Acceptor 没有对比 n 更大的编号，则接受该提案。否则拒绝接受 Proposal，直接返回；
  3. Proposer 己收到大多数 Acceptor 的请求，此次请求的 Proposal 被接受。如果 Proposal 没有被大多数 Acceptors 接受，则回到第一步，重新发起新一轮的请求；

一些例子

Case1: 前提案已经被 Chosen

image-20220716225952952

  1. S1 收到客户端提案请求 X，于是 S1 向 S1-S3 发起 Prepare(3.1) 请求，Acceptor 响应返回目前没有提案被 Chosen；
  2. 由于 S1-S3 没有任何提案被 Chosen，S1 继续向 S1-S3 发送 Accept(3.1, X) 请求，提案被成功 Chosen；
  3. 在提案被 Chosen 后，S5 收到客户端提案值为 Y 的请求，向 S3-S5 发送 Prepare(4.5) 请求，由于编号 4 > 3，S5 会收到提案值为 X 已经被 Chosen 的响应；
  4. 于是 S5 将提案值 Y 替换成 X，向 S1-S3 发送 Accept(4.5, X) 请求，提案再次被 Chosen;

Case2: 前提案未被 Chosen，对新一轮 Proposer 可见

image-20220716230833862

  1. S1 收到客户端提案请求 X，于是 S1 向 S1-S3 发起 Prepare(3.1) 请求，响应返回没有提案被 Chosen；
  2. 由于 S1-S3 没有任何提案被 Chosen，S1 继续向 S1-S3 发送 Accept(3.1, X) 请求，由于网络延迟等关系，Proposal 首先在 S3 被 Chosen；
  3. 在提案被 Acceptor S1 和 S2 Chosen 之前，S5 收到客户端提案值为 Y 的请求，向 S3-S5 发送 Prepare(4.5) 请求，其中由于 S3 作为上一轮的 Acceptor，可以知道自己有了 Chosen 的 Proposal，并且新一轮的 Proposal Number 4 > 3 ，则会在返回给 S5 的响应中带上上一轮的 Proposal 的值；
  4. 于是 S5 将提案值 Y 替换成 X，向 S1-S3 发送 Accept(4.5, X) 请求，提案再次被 Chosen；

Case3: 前提案未被 Chosen，对新一轮 Proposer 不可见

image-20220716232014065

  1. S1 收到客户端提案请求 X，于是 S1 向 S1-S3 发起 Prepare(3.1) 请求，响应返回没有提案被 Chosen；
  2. 由于 S1-S3 没有任何提案被 Chosen，S1 继续向 S1-S3 发送 Accept(3.1, X) 请求，由于网络延迟等关系，Accept 请求一直没有被响应；
  3. 在上一轮提案被 Acceptor S3 响应之前，S5 收到客户端提案值为 Y 的请求，向 S3-S5 发送 Prepare(4.5) 请求，响应返回没有提案被 Chosen；
  4. 此时 S3 收到 Accept(3.1, X) 请求，但是由于此时新的 Proposal Number 更大，会导致上一轮的 Proposal 被拒绝。而上一轮 Proposal，只有 S1-S2 响应，不能占到系统的大多数，会被拒绝；
  5. 由于 S3-S5 没有任何提案被 Chosen，S5 继续向 S3-S5 发送 Accept(4.5, Y) 请求，提案被成功 Chosen；

Case4: 活锁

image-20220716233504393

当 Proposer 在第一轮 Prepare 发出请求，还没来得及完成后续的第二轮 Accept 请求，紧接着第二个 Proposer 在第一阶段也发出编号更大的请求。如果这样无穷无尽，Acceptor 始终停留在决定顺序号的过程上，那大家谁也成功不了。

解决活锁最简单的方式就是引入随机超时，这样可以让某个 Proposer 先进行提案，减少一直互相抢占的可能。

异常处理（持久化存储）

在算法执行的过程中会产生很多的异常情况：proposer 宕机，acceptor 在接收 proposal 后宕机，proposer 接收消息后宕机，acceptor 在 accept 后宕机，存储失败，等等。为保证 paxos 算法的正确性，proposer、aceptor 都实现持久存储，以做到 server 恢复后仍能正确参与 paxos 处理。

Propose 存储已提交的最大 proposal 编号、决议编号（instance id）
Acceptor 存储已承诺（promise）的最大编号、已接受（accept）的最大编号和 value、决议编号。

6 Multi Paxos

回到文章最开始的例子 —— 多副本状态机（Replicated state machines），Paxos 就是为了实现 Replicated Log。Paxos 只从一个或多个值中选择一个值，分布式系统常常需要重复运行 Paxos 来创建多副本状态机，但如果每个命令都通过一个 Basic Paxos 算法实例来达到一致，每次都要两轮 RPC，会产生大量开销。所以需要对 Paxos 做一些调整解决更实际的问题，并提升性能。经过一系列优化后的 Paxos 我们称之为 Multi-Paxos。

Multi Paxos 对 Basic Paxos 的核心改进是增加了 “选主” 的过程，提案节点会通过定时轮询（心跳），确定当前网络中的所有节点里是否存在有一个主提案节点，一旦没有发现主节点存在，节点就会在心跳超时后使用 Basic Paxos 中定义的准备、批准的两轮网络交互过程，向所有其他节点广播自己希望竞选主节点的请求，希望整个分布式系统对 “由我作为主节点” 这件事情协商达成一致共识，如果得到了决策节点中多数派的批准，便宣告竞选成功。当选主完成之后，除非主节点失联之后发起重新竞选，否则从此往后，就只有主节点本身才能够提出提案。此时，无论哪个提案节点接收到客户端的操作请求，都会将请求转发给主节点来完成提案，而主节点提案的时候，也就无需再次经过准备过程，因为可以视作是经过选举时的那一次准备之后，后续的提案都是对相同提案 ID 的一连串的批准过程。也可以通俗理解为选主过后，就不会再有其他节点与它竞争，相当于是处于无并发的环境当中进行的有序操作，所以此时系统中要对某个值达成一致，只需要进行一次批准的交互即可。 [摘自凤凰架构]

为此，Multi-Paxos 提出了几个问题需要解决：

  1. 日志内容如何选择？
  2. 性能优化
    1. 使用 Leader 降低多个 Proposers 带来的冲突消耗；
    2. 降低不必要的 Prepare 请求，来降低不必要的 RPC 请求
  3. 如何保证副本的完整性
  4. 客户端请求协议
  5. 分布式集群配置

日志内容选择

image-20220717000723564

客户端的请求在服务端作为一个元素保存在数组中，然后数组被作为日志，被一致性模块同步到所有的服务端，最后被状态机消费，返回结果给客户端。Replicated log 类似一个数组，我们需要知道当次请求是在写日志的第几位。因此，Multi-Paxos 做的第一个调整就是要添加一个日志的 index 参数到 Prepare 和 Accept 阶段，表示这轮 Paxos 正在决策哪一条日志记录。

当新的客户端指令发送到服务器时，Multi Paxos 大致流程如下：

  1. 寻找第一条没有 chosen 的日志 (该日志中没有提案或者提案还没有通过)；
  2. 执行 Basic Paxos，以该条目 index 为编号提出提案；
  3. 通过的提案内容就是该条目日志选择的内容，如果：
    1. 选择了服务器中存在的指令，即该提案编号以下的最大未通过提案指令，就从步骤一重新开始；
    2. 否则就选择该客户端的请求指令；

例子：

image-20220717001144973

服务器上的每条日志记录可能存在三种状态：

  • 已经保存并知道被 chosen 的日志记录。例如 S1 方框加粗的第 1、2、6 条记录（后面会介绍服务器如何知道这些记录已经被 chosen）
  • 已经保存但不知道有没有被 chosen。例如 S1 第 3 条 cmp 命令。观察三台服务器上的日志，cmp 其实已经存在两台上达成了多数派，只是 S1 还不知道
  • 空的记录。例如 S1 第 4、5 条记录，S1 在这个位置没有接受过值，但可能在其它服务器接受过，例如 S2 第 4 条接受了 sub，S3 第 5 条接受了 cmp

多数派写方案中，3 个结点的集群可以容忍一台故障，为了更具体的分析，我们假设此时是 Server3 宕机的情况。同时，这里的提案值是一条具体的命令。当 S1 收到客户端的请求命令 jmp 时：

  1. 找到第一个没有 chosen 的日志记录：图示中是第 3 条 cmp 命令；（指令 1 和指令 2 已经被选中了，通过前两轮 Paxos 选中）
  2. 这时候 S1 会尝试让 jmp 作为第 3 条的 chosen 值，运行 Basic Paxos；
  3. 因为 S1 的 Acceptor 已经接受了 cmp，所以在 Prepare 阶段会返回 cmp，接着用 cmp 作为提案值跑完这轮 Paxos，s2 也将接受 cmp 同时 S1 的 cmp 变为 chosen 状态，然后继续找下一个没有 chosen 的位置 —— 也就是第 4 位；
  4. S2 的第 4 个位置接受了 sub，所以在 Prepare 阶段会返回 sub，S1 的第 4 位会 chosen sub，接着往下找；
  5. 第 5 位 S1 和 S2 都为空，不会返回 acceptedValue，所以第 5 个位置就确定为 jmp 命令的位置，运行 Paxos，并返回请求。

值得注意的是：

  • 这个系统是可以并行处理多个客户端请求，比如 S1 知道 3、4、5、7 这几个位置都是未 chosen 的，就直接把收到的 4 个命令并行尝试写到这四个位置。
  • 如果是状态机要执行日志时，必须是按照日志顺序逐一输入，如果第 3 条没有被 chosen，即便第 4 条已经 chosen 了，状态机也不能执行第 4 条命令。

性能优化

Basic Paxos 的效率很低。并发情况下，所有的 Proposer 都一起并行工作，因 Proposer 间大量的冲突而至少需要两轮乃至更多轮 RPC 才能达成共识。

解决方案：

  • 选择一个 Leader，任意时刻只有它一个 Proposer，这样可以避免冲突；

    Leader 选举：

    1. 既然每台服务器都有一个 serverid，我们就直接让 serverid 最大的服务器成为 Leader，这意味着每台服务器需要知道其它服务器的 server_id；

    2. 服务器之间通过 T ms 的心跳来维持联系；

    3. 如果一个节点在 2Tms 时间内没有收到比自己 server_id 更大的心跳，那它自己就转为 Leader，意味着：

      1. 该节点处理客户端请求；
      2. 该节点同时担任 Proposer 和 Acceptor；

    4. 如果一个节点收到比自己 server_id 更大的服务器的心跳，那么它就不能成为 Leader，意味着

      1. 该节点拒绝掉客户端请求，或者将请求重定向到 Leader；
      2. 该节点只能担任 Acceptor；

  • 减少大部分 Prepare 请求（压缩 prepare 过程的 RPC）只需要对整个日志进行一次 Prepare，后面大部分日志可以通过一次 Accept 被 Chosen;

    压缩 Prepare 请求:

    在讨论如何减少 Prepare 请求之前，先讨论下 Prepare 阶段的作用，需要 Prepare 有两个原因：

    1. 屏蔽老的提案：但 Basic-Paxos 只作用在日志的一条记录；
    2. 检查可能已经被 Chosen 的 value 来代替原本的提案值：多个 Proposer 并发进行提案的时候，新的 Proposal 要确保提案的值相同；

    可以见得，Prepare 还是很有必要的，可以通过以下几个方面来减少 Prepare 的请求：

    • 对于 a: 我们不再让提案编号只屏蔽一个 index 位置，而是让它变成全局的，即屏蔽整个日志。一旦 Prepare 成功，整个日志都会阻塞（值得注意的是，Accept 阶段还是只能写在对应的 index 位置上）。
    • 对于 b: 需要拓展 Prepare 请求的返回信息，和之前一样，Prepare 还是会返回最大提案编号的 acceptedValue，除此之外，Acceptor 还会向后查看日志记录，如果要写的这个位置之后都是空的记录，没有接受过任何值，那么 Acceptor 就额外返回一个标志位 noMoreAccepted。

    后续，如果 Leader 接收到超过半数的 Acceptor 回复了 noMoreAccepted，那 Leader 就不需要发送 Prepare 请求了，直接发送 Accept 请求即可。这样只需要一轮 RPC。

如何保证副本的完整性

目前为止，通过选 Leader 和减少 Prepare 请求之后的 Multi-Paxos 依然不够完整，还需要解决：

  • 之前的日志只需要被多数派接受，完整的日志记录需要复制到全部节点；
  • 只有 Proposer（也就是 Leader） 知道哪些记录被 chosen 了，需要所有的服务器都知道哪些记录被 chosen；

要保证集群的所有节点的得到相同的输出，需要保证所有的节点的日志和指令都一致。

方案：

  1. 为了让日志尽可能被复制到每台服务器：Leader 在收到多数派 Acceptor 回复后，可以继续做后面的处理，但同时在后台继续对未回复的 Acceptor 进行重试。这样不会影响客户端的响应时间，但这也不能确保完全复制了（例如，如果 Leader 在中途宕机了）

  2. 为了追踪哪些记录是被 chosen 的，增加一些内容：acceptedProposal 代表日志的提案编号，如果第 i 条记录被 chosen，则 acceptedProposal[i] = ∞（这是因为，只有提案编号更大的提案才能被接受，无穷大则表示无法再被重写了）每个节点都维护一个 firstUnChosenIndex，表示第一个没有被 chosen 的日志位置。（即第一个 acceptedProposal[i] != ∞的节点）

  3. Leader 告诉 Acceptor 哪些日志被 chosen ：Leader 在向 Acceptor 发送 Accept 请求的时候带上 firstUnChosenIndex，这样 Acceptor 收到 Accept 请求的时候，如果第 i 条日志满足 i < request.firstUnchosenIndex && acceptedProposal[i] == request.proposal，则标记 i 为 chosen（即设为无穷大）

    例子：

    image-20220717225727574上图表示同一个 Acceptor 节点 Accept 请求前后的 acceptedProposal 的数组结果。

    Before Accept： index(i) = 6, acceptedProposal = 3.4;

    Accept 请求中：proposal = 3.4, index = 8, value = v, firstUnchosenIndex = 7;

    => i < request.firstUnchosenIndex && acceptedProposal[i] == request.proposal

    After Accept: accetpedProposal[6] = ∞

    总结： acceptor 已经学习了大部分被选择的日志

  4. 若 Leader 宕机，Acceptor 的日志条目中仍然可能有一些宕机的 Leader 留下的提案记录，还没有完成提案的复制或者 chosen。更换新 Leader 时，需要：

    • Acceptor 将其 firstUnchosenIndex 作为 Accept 请求的响应返回给 Proposer；

    • Proposer 判断如果 Acceptor.firstUnChosenIndex < Proposer.firstUnChosenIndex，则在后台（异步）发送 Success(index, v) RPC：

    • Acceptor 收到 Success RPC 后，更新已经被 chosen 的日志记录：

      • acceptedValue[index] = v

      • acceptedProposal [index] = 无穷大

      • return firstUnchosenIndex

        如果需要 (可能存在多个不确定的状态)，Proposer 发送额外的 Success RPC

通过 4 个步骤就可以确保所有的 Acceptor 都最终知道已被 chosen 的日志记录。在一般的情况，并不需要额外的第 4 步，只有在 Leader 切换时才可能需要第 4 步

客户端请求协议

考虑客户端如何与集群交互。

当客户端第一次请求时，并不知道谁是 Leader，它任意请求一台服务器，如果该服务器不是 Leader，重定向给 Leader。
Leader 直到日志记录被 chosen 并且被 Leader 的状态机执行才返回响应给客户端。

客户端会一直和 Leader 交互，直到无法再联系上它（例如请求超时）。在这种情况下，客户端会联系任何其它服务器，这些服务器又在重定向到实际的 Leader。

但这存在一个问题，如果请求提案被 chosen 后，Leader 在回复客户端之前宕机了。客户端会认为请求失败了，并重试请求。这相当于一个命令会被状态机执行两次或者多次，在很多情况下是不能被接受的（幂等问题）。

方案：

客户端为每个请求增加一个唯一 id，服务器将该 id 与命令一起保存到日志记录中。状态机在执行命令之前，会根据 id 检查该命令是否被执行过。

分布式集群配置

现在分布式使用的都是服务发现、配置中心来管理，是个非常复杂的问题，这里不再做过多介绍，之后用其他的篇幅来学习讲解。

总结

Paxos 是由 Leslie Lamport（就是大名鼎鼎的 LaTeX 中的 “La”）提出的一种基于消息传递的协商共识算法，现已是当今分布式系统最重要的理论基础，几乎就是 “共识” 二字的代名词。

Paxos 是以复杂著称的算法，本章节从一个问题出发，来引出如何推演出 Paxos 的思想，主要讲解了下 Basic Paxos 的算法流程，即，以 prepare 和 accept 两个阶段以及在这两个阶段中 proposer 和 acceptor 的行为来解决：如何保证复制后的日志数据在每台机器上都一样？的问题。

同时也大概介绍了一下基于 Basic Paxos 的改进版本”Multi Paxos”，给出几个优化的点。

引用