部分内容来源：b站码上加薪，JavaGuide

---

Basic Paxos算法

Basic Paxos 中存在 3 个重要的角色：

1. 提议者（Proposer）：也可以叫做协调者（coordinator），提议者负责接受客户端的请求并发起提案。提案信息通常包括提案编号 (Proposal ID) 和提议的值 (Value)。
2. 接受者（Acceptor）：也可以叫做投票员（voter），负责对提议者的提案进行投票，同时需要记住自己的投票历史；
3. 学习者（Learner）：如果有超过半数接受者就某个提议达成了共识，那么学习者就需要接受这个提议，并就该提议作出运算，然后将运算结果返回给客户端。

为了减少实现该算法所需的节点数，一个节点可以身兼多个角色。

并且，一个提案被选定需要被半数以上的 Acceptor 接受，也就是多数决策，少数服从多数

因为是多数决策，所以Basic Paxos 算法还具备容错性，在少于一半的节点出现故障时，集群仍能正常工作。

我们的Basic Paxos算法是我们的分布式系统中，对于某一个特定的值达成一致意见

缺点就是，我们不能对于多个值达成一致的意见，这个时候就要聊一下我们的Multi Paxos算法了

---

Multi Paxos算法

Basic Paxos 算法的核心目标是让分布式系统中的多个节点在众多可能的选项中，对于某一个特定的值达成一致意见

Multi Paxos 是在 Basic Paxos 基础上发展而来的，它的核心思想是通过对多个 Basic Paxos 实例进行优化组织，来实现对一系列值的共识。

它将一系列的值的共识问题分解为多个阶段或多个实例

每个实例仍然基于 Basic Paxos 的原理，但通过一些优化和协调机制，使得这些实例之间能够相互关联和协同工作，从而实现对多个值按照一定顺序依次达成共识

Basic Paxos 算法的仅能就单个值达成共识，为了能够对一系列的值达成共识，我们需要用到 Multi Paxos 思想

⚠️注意：

Multi-Paxos 只是一种思想，这种思想的核心就是通过多个 Basic Paxos 实例就一系列值达成共识

简单来说，Basic Paxos 是 Multi-Paxos 思想的核心，Multi-Paxos 就是多执行几次 Basic Paxos

由于Multi-Paxos 思想缺少代码实现的必要细节(比如怎么选举领导者)，所以在理解和实现上比较困难。

我们并不需要自己实现基于 Multi-Paxos 思想的共识算法，业界已经有了比较出名的实现。

像Raft 算法就是 Multi-Paxos 的一个变种，其简化了 Multi-Paxos 的思想，变得更容易被理解以及工程实现，实际项目中可以优先考虑 Raft 算法

---

Raft算法

我们介绍下面几个方面

状态机

共识算法（Follower复制Leader日志保证状态机一致）

如何进行Leader选举的（心跳机制，少数服从多数）

Leader选举的时候遇到不同term时候的修改和随机的超时时间，和同时出现多个Candidated后选不出Leader的下一轮选举（投票分裂）

日志复制和提交（多数Follower都复制了该记录，Leader才将该记录日志标记为已提交状态）

数据安全性（根据比较term和index防止缺失大量数据的节点变成Leader主节点）

修复不一致日志（旧Leader的提交记录不算，以新Leader的提交记录为标准）

---

什么是状态机

状态机，全称为有限状态自动机（Finite State Machine，FSM），是一种抽象的计算模型，是一个抽象的概念

用于描述对象在不同状态之间的转换以及在状态转换过程中所执行的操作

其作用主要是描述对象在它的生命周期内所经历的状态序列，以及如何响应来自外界的各种事件

不管集群中有多少个节点，只要每个节点都具有相同的初始状态

在输入相同的指令后，最终的输出结果都相同

基本组成要素

• 状态（States）：指对象在其生命周期中可能处于的不同条件或情况。例如，在一个交通灯系统中，“红灯”“绿灯”“黄灯” 就是交通灯的不同状态。
• 事件（Events）：是导致状态机从一个状态转换到另一个状态的触发条件。比如在交通灯系统中，“定时时间到” 就是一个事件，它会使交通灯从 “绿灯” 状态转换到 “黄灯” 状态。
• 转换（Transitions）：定义了从一个状态到另一个状态的迁移过程。通常由事件触发，并且可能伴随着一些动作的执行。比如，当交通灯接收到 “定时时间到” 这个事件时，就会从 “绿灯” 状态转换到 “黄灯” 状态，这就是一个转换过程。
• 动作（Actions）：在状态转换过程中或者处于某个特定状态时所执行的操作。例如，在交通灯从 “绿灯” 转换到 “黄灯” 的过程中，可能会执行 “开启黄灯闪烁” 的动作。

工作原理（文字理论）

状态机在初始时处于某个初始状态，然后在运行过程中不断地接收外部事件。

当一个事件发生时，状态机根据当前所处的状态以及预先定义好的转换规则，决定是否进行状态转换以及执行相应的动作

如果满足转换条件，状态机就会从当前状态转换到目标状态，并执行与该转换相关的动作；

如果不满足条件，则保持当前状态不变

简单来说，我们就是定义一系列状态转换规则，从而让相同的行为决策进行相同的状态转换，从而达到相同决策得出相同状态

处理相同的状态，得到相同的输出

---

Raft算法中状态机起到的重要作用

set例子描述状态机工作原理

灰色背景的方框就表示我们的一个节点

在一个Raft集群中呢可以包含三个状态节点

Leader，Follower，Candidate

当集群中选出一个Leader节点后，其他的节点就会自动变成Follower

当集群中没有Leader节点的时候，其他节点可能会变成Candidate，然后进行下一轮的Leader选举

Raft集群中的操作其实主要都是针对Leader节点进行操作的

例如我们的程序调用我们的set X=5命令时

Leader节点中Consensus Module并不会把这个命令的值写到状态机或者数据库中

而是会先生成一条Raft Log，先向日志中先追加一条记录

然后Raft算法中的Leader会将这条set X=5的日志赋值给两个Follower节点

红色的set X= 5表示我们的数据写入到了日志中，但是还没有被Commit。

或者说，此时并没有在状态机中更改状态

此时客户端仍然不能读到x=5的信息，客户端读到的x仍然为3

相当于能读取到的值永远是状态机中的值

随后每个follower节点在接收到数据发送请求之后就会将消息存储在本地的Raft Log中

然后follower会向Leader节点反馈已经收到了数据

只要我们的成功备份的节点超过了总节点数的一半，就说明是多数存储了

这个时候我们的Leader节点就会将X=5这个状态变成已提交状态

然后Raft算法会根据apply状态，将自己状态机里面的状态从X=3改成X=5

然后客户端就会收到Leader的响应，告知它我们已经成功写入了

为什么我们不可以先修改状态机状态再更新日志呢？

因为我们修改完状态机状态后读取数据X=5，然后Leader在日志还没同步的时候宕机了

我们重新进行Leader选举

新选出来的节点因为没有同步日志，此时我们读取到的X的值为3

这样子就会导致前后读取数据的不一致

---

共识算法（Follower复制Leader日志保证状态机一致）

正如标题所说，我们所谓的共识，其实就是我们保证我们的Leader和Follower的状态机一致，这样子我们的节点的状态就一致了

共识是可容错系统中的一个基本问题：即使面对故障，服务器也可以在共享状态上达成一致。

共识算法允许一组节点像一个整体一样一起工作，即使其中的一些节点出现故障也能够继续工作下去

其正确性主要是源于复制状态机的性质：一组Server的状态机计算相同状态的副本，即使有一部分的Server宕机了它们仍然能够继续运行。

图-1 复制状态机架构

一般通过使用复制日志来实现复制状态机

每个Server存储着一份包括命令序列的日志文件，状态机会按顺序执行这些命令

因为每个日志包含相同的命令，并且顺序也相同，所以每个状态机处理相同的命令序列。

由于状态机是确定性的，所以处理相同的状态，得到相同的输出

因此共识算法的工作就是保持复制日志的一致性。服务器上的共识模块从客户端接收命令并将它们添加到日志中。它与其他服务器上的共识模块通信，以确保即使某些服务器发生故障。每个日志最终包含相同顺序的请求

一旦命令被正确地复制，它们就被称为已提交。每个服务器的状态机按照日志顺序处理已提交的命令，并将输出返回给客户端，

因此，这些服务器形成了一个单一的、高度可靠的状态机

适用于实际系统的共识算法通常具有以下特性：

• 安全：确保在非拜占庭条件（也就是上文中提到的简易版拜占庭）下的安全性，包括网络延迟、分区、包丢失、复制和重新排序。
• 高可用：只要大多数服务器都是可操作的，并且可以相互通信，也可以与客户端进行通信，那么这些服务器就可以看作完全功能可用的。因此，一个典型的由五台服务器组成的集群可以容忍任何两台服务器端故障。假设服务器因停止而发生故障；它们稍后可能会从稳定存储上的状态中恢复并重新加入集群。
• 一致性不依赖时序：错误的时钟和极端的消息延迟，在最坏的情况下也只会造成可用性问题，而不会产生一致性问题。
• 在集群中大多数服务器响应，命令就可以完成，不会被少数运行缓慢的服务器来影响整体系统性能

---

说一下Leader领导者选举是怎么实现的

三个节点的类型

领导者（Leader）：负责处理所有客户端请求，并将更新日志复制到追随者。每个Raft集群只能有一个领导者。

追随者（Follower）：被动响应领导者的请求，保存领导者的日志。

候选者（Candidate）：当追随者无法与领导者通信时，会转变为候选者以发起新的选举

---

任期term

raft 算法将时间划分为任意长度的任期（term），任期用连续的数字表示，看作当前 term 号。

每一个任期的开始都是一次选举

在选举开始时，一个或多个 Candidate 会尝试成为 Leader。

如果一个 Candidate 赢得了选举，它就会在该任期内担任 Leader

如果没有选出 Leader，将会开启另一个任期，并立刻开始下一次选举。

raft 算法保证在给定的一个任期最少要有一个 Leader

每个节点都会存储当前的 term 号，当服务器之间进行通信时会交换当前的 term 号

1.如果有服务器发现自己的 term 号比其他人小，那么他会更新到较大的 term 值

2.如果一个 Candidate 或者 Leader 发现自己的 term 过期了，他会立即退回成 Follower

3.如果一台服务器收到的请求的 term 号是过期的，那么它会拒绝此次请求

---

领导选举过程 

其实就是心跳机制+少数服从多数 

Raft 心跳机制的工作流程

节点之间通过心跳信号来互相传递信息，例如任期号Term和日志信息同步

1.领导者发送心跳：

领导者会周期性地向所有跟随者发送心跳消息（空的 AppendEntries RPC）。

心跳消息包含领导者的任期号（Term）和最新的日志索引。

2.跟随者接收心跳：

跟随者收到心跳消息后，会重置自己的选举超时计时器。

如果跟随者发现心跳消息中的任期号比自己的大，会更新自己的任期号并切换到跟随者状态。

3.选举超时：

如果跟随者在选举超时时间内没有收到心跳消息，就会认为领导者已经失效。

跟随者会将自己的状态切换为候选人（Candidate），并开始新的选举。

---

选举过程

Raft 使用心跳机制来触发 Leader 的选举。

如果一台服务器能够收到来自 Leader 或者 Candidate 的有效信息，那么它会一直保持为 Follower 状态，并且刷新自己的 electionElapsed（选举超时时间），重新计时

Leader 会向所有的 Follower 周期性发送心跳来保证自己的 Leader 地位

如果一个 Follower 在一个周期内没有收到心跳信息，就叫做选举超时，然后它就会认为此时没有可用的 Leader，并且开始进行一次选举以选出一个新的 Leader。

为了开始新的选举，Follower 会自增自己的 term 号并且转换状态为 Candidate

然后他会向所有节点发起 RequestVoteRPC 请求

Candidate 的状态会持续到以下情况发生：

• 赢得选举
• 其他节点赢得选举
• 一轮选举结束，无人胜出

赢得选举的条件是：一个 Candidate 在一个任期内收到了来自集群内的多数选票（N/2+1），就可以成为 Leader。

在 Candidate 等待选票的时候，它可能收到其他节点声明自己是 Leader 的心跳，此时有两种情况：

• 该 Leader 的 term 号大于等于自己的 term 号，说明对方已经成为 Leader，则自己回退为 Follower
• 该 Leader 的 term 号小于自己的 term 号，那么会拒绝该请求并让该节点更新 term

由于可能同一时刻出现多个 Candidate，导致没有 Candidate 获得大多数选票，如果没有其他手段来重新分配选票的话，那么可能会无限重复下去。

raft 使用了随机的选举超时时间来避免上述情况。每一个 Candidate 在发起选举后，都会随机化一个新的选举超时时间，这种机制使得各个服务器能够分散开来，在大多数情况下只有一个服务器会率先超时；

它会在其他服务器超时之前赢得选举

---

Raft算法的日志复制过程（多数Follower都复制了该记录，Leader才将该记录日志标记为已提交状态）

主要知识点在于，日志记录是否提交

S1在本地写入了三条日志（写到了硬盘上，但是还没有向状态机提交）

然后我们的S2一条一条跟着S1写入日志，但是虽然写入了日志，我们还是未提交的状态

只有半数节点写入这个日志的时候Leader节点才会将日志的状态修改成已提交

此时我们的S3恢复了，我们S1的复制请求发向S3，然后S3复制第一条日志。

此时我们的第一条日志的写入，已经在超过半数的节点写入了

然后我们的S1节点把第一条日志标位已提交状态，继续发起请求，同时携带着第一条日志已提交的信息给S3

然后S3接收到第一条日志已提交的信息，所以S3的第一条日志也变成了已提交状态

（其实他会像所有节点都发送心跳，所以此时S2节点的第一条日志其实也变成了已提交状态，只是他没有画出来）

---

如何保证数据安全性（根据比较term和index防止缺失大量数据的节点变成Leader主节点）

Leader节点S2要向S5节点发送心跳了

但是此时Leader节点S2宕机了，但此时S5节点接收到心跳然后成功加入集群了

加入集群之后发现没有Leader，此时就会触发新一轮的投票选举

S5先超时变成Candidate然后发起投票

但是大家不会把票投给S5

因为Raft算法是Leader强一致性算法，我们如果让S5这个没同步之前日志的节点变成主节点

那我们的其他Follower不就因为强一致性，然后把之前的日志清除了？这样子肯定是不可能的

所以我们投了反对票

所以我们的Raft算法为了阻止这种情况我们就加了我们的双重保险

也就是我们的term值和index值

如果我们的节点发现自己的term和index比Candidate节点要新的话，我们就会投反对票

例如第一个节点的term值比较新的话

那么就会优先选举第一个节点变成Leader

后两台的日志相等因此我们的index大的越新

总结

Raft算法的选举：Term越新优先级越高，然后Term优先级相同的时候就比较index的大小

---

在投票分裂的时候我们该怎么选出Leader节点

例如S1,S5同时超时，然后同时变成Candidate状态，然后开启投票

然后它们向其他节点发起拉票请求（即使是宕机的节点，我们也会向他发起请求）

然后我们的S1,S5获取相同的票数

一直选举不出来

然后我们的S2超时没有返回投票结果，所以我们会不断地向他发起投票请求（此时不会向已经投票过的节点发起投票请求）

然后这个时候我们也是在进行我们的超时等待的

S3超时，然后开启重新一轮的Leader选举

---

修复不一致日志（旧Leader的提交记录不算，以新Leader的提交记录为标准）

S1写入最近两条日志，但是没有提交，然后此时我们的S1宕机了

超时后，发起了新一轮的Leader选举

Leader节点选举出来后的第一件事就是初始化

初始化所有节点的next index，让所有的节点的next index都和Leader的next index保持一致

然后S2会发起我们的一致性检查（日志一致性检查请求）

检查index=3这个位置的日志是否和自己一致

此时我们的S3表示这个位置日志是一致的，但是我们的S4表示这个位置的日志是不一致的

S4的next index往左移动了一小格

然后S2会像S4再发起一个一致性检查

然后这个next index箭头会不断地往左检查，我们当前位置的日志是否一致

不一致我们就继续往左

检查完毕后，我们的S2就向我们的S4开始复制日志

此时S2写入数据，但是原来的S1节点恢复了

所以我们要去检查S1节点的位置的日志和Leader节点是否一样

我们发现前面一样但是后面不一样

我们的Raft算法是Leader强一致性算法，所以此时我们的S1和我们的Leader节点S2要变成一致

这样就做到了日志的一致性

---

简单概括Raft算法的概念

Raft算法的主要目标

一致性：确保分布式系统中的所有节点在任何时刻都能对数据的状态达成一致。

可用性：在节点故障时，系统仍能正常响应请求。

简化实现：相较于Paxos，Raft算法的设计更直观，易于理解和实现。

Raft算法的基本概念

Raft算法主要由以下几个组件构成：

节点角色

领导者（Leader）：负责处理所有客户端请求，并将更新日志复制到追随者。每个Raft集群只能有一个领导者。

追随者（Follower）：被动响应领导者的请求，保存领导者的日志。

候选者（Candidate）：当追随者无法与领导者通信时，会转变为候选者以发起新的选举。

日志条目

所有状态变化的请求都以日志条目的形式记录在节点中，确保数据的一致性。

选举过程

当领导者失效或与多数节点失去联系时，追随者会发起选举，选举新的领导者。

Raft算法的工作流程

选举领导者

节点启动后，默认是追随者。如果追随者在一定时间内未收到领导者的心跳信号，它会变为候选者并发起选举。候选者会请求其他节点投票，获得大多数节点的支持后成为新的领导者。

日志复制

领导者接收客户端的请求，将其作为新的日志条目添加到日志中，然后将该条目复制到所有追随者。追随者在接收到条目后，会将其添加到自己的日志中并发送确认。

日志提交

当领导者收到大多数追随者的确认后，会将日志条目标记为已提交。然后，领导者将提交的信息通知追随者，追随者也将条目标记为已提交。

状态机应用

一旦日志条目被提交，领导者和追随者都将日志条目应用到各自的状态机中，完成状态的更新。

优势和应用

易于理解：Raft算法的设计理念和流程相对直观，使得实现和调试变得更容易。

容错性：Raft算法能够容忍少数节点的故障，只要大多数节点正常工作，系统就能继续提供服务。

广泛应用：许多现代分布式数据库（如Etcd、Consul、CockroachDB）和文件系统使用Raft算法来确保数据一致性

---