浅显易懂的「Raft」分布式共识算法

Raft 共识算法

• 写在前面 – 什么是分布式系统

分布式系统是由多台计算机或多个节点组成的计算系统，这些节点之间通过网络进行通信和协调，共同完成特定的任务或提供某种服务。与传统的集中式系统不同，分布式系统的节点可以分布在不同的地理位置，并且在逻辑上是相互独立的。

其设计目标是通过将计算和数据分散到多个节点上，提高系统的可伸缩性、可靠性和性能。通过将工作负载分摊到多个节点上，分布式系统可以更好地应对大规模的计算和存储需求，并且能够容忍节点故障或网络中断的情况。

• 设计/使用分布式系统的目标

1. 更快，我们花了更多的钱，配了更多的机器，我们当然期望这些机器可以一起配合，发挥 1+1 >= 2 的性能
2. 容错，当磁盘被某人磕了一下坏了，数据怎么办，我们在这个磁盘不值钱数据值钱的时代，这样丢失数据是不可容忍的
3. 高可用，某个机房的交换机坏掉？网线被人拔了？服务直接就挂了吗？不行，不能容忍！
4. 可伸缩，通过添加更多的节点来扩展其计算和存储能力，以满足不断增长的需求。

理想是丰满的

• 设计/使用分布式系统面临的困难

1. 性能和延迟，每一台机器的性能情况是不一样的，如何进行负载均衡？每一台机器链接的路由和带宽也是不一样的，怎么在这种条件下，各个机器进行高效的通讯，数据传递？
2. 故障（灾难）恢复，我们期望某个机器挂掉之后不影响服务的进行，在修好后可以直接接入系统，不用统一重启
3. 数据一致，由上所述，我们网络的带宽、性能、延迟是不同的，还有可能出现意外（灾难），如何在这些问题下保证多机器的数据一致性，我们总不希望，因为一点点网络波动，俩机器数据不一样了吧？
4. 管理和调度，有上述问题，我们的分布式系统如何进行（优雅的）调度呢？

现实是骨感的

现有的所有分布式系统在上述问题中都有取舍，数据一致性与性能、可用性与一致性、容错性与性能、数据一致性与跨地理位置通信，目前没有一个各个方面都非常完美的方法（算法）。

什么是Raft

raft直译是‘筏子’，和这篇讲述的主题关系就如同雷锋和雷锋塔

Raft是一种共识算法，用于在分布式系统中实现一致性。它是由Diego Ongaro和John Ousterhout在2013年提出的，旨在解决分布式系统中复制状态机的问题。

• ok,新的问题来了，什么是复制状态机？望文生意
  • 通过复制来保证各个机器之间的一致性
  • 每个机器处于有限个状态（身份）进行工作

复制状态机（Replicated State Machine）是一种在分布式系统中实现容错性和一致性的技术。它是基于状态机复制的思想，通过在多个节点上复制相同的状态机，并通过一致性协议来确保各个节点之间的状态一致性。

复制式状态机用于解决分布式系统中的一些容错（fault tolerance）问题。

复制状态机

共识算法管理着客户端发来的状态机命令的一个日志副本 （replicated log），状态机以完全相同的顺序执行日志中的命令，因此产生完全相同的输出。

explain

• 每台 server 都保存着一个由命令序列组成的 log 文件，状态机按 顺序执行其中的命令。由于每个 log 都以完全相同的顺序保存了完全相同的命令，而 且状态机是确定性的（deterministic），因此每个状态机计算得到的是相同的状态， 产生的是相同的结果。
• 保持 replicated log 的一致性是共识算法的职责。某个节点上的 共识模块从客户端接收命令，然后写入 log 中；并与其他 节点上的共识模块通信，以保证即使某些机器挂掉，每个 replicated log 最终也以 相同的顺序包含相同的请求。
• 命令正确地复制到其他节点之后，每台机器的状态机会按顺序处理他们，然后将结果返回给客 户端。从客户端的角度来看，这些节点形成的是高度可靠的单个状态机。

共识算法的典型特征

• 在任何 non-Byzantine 条件下都能保证安全（从不返回错误结果）， 这里所说的 non-Byzantine 条件包括网络延迟、partitions、丢包、重复、乱序。
• 只要多数节点能工作、彼此之间及与客户端之间能通信，那整体系统的功能就完全正常（完全可用）； 因此，一个有 5 台节点的集群，能容忍任意 2 台机器的挂掉。
• 机器挂掉后，能够从持久存储中恢复，然后重新加入集群；
• 不依赖时序（timing）来保证日志的一致性：在最坏情况下，时钟不准 和极大的消息延迟都会导致可用性问题，因此避免依赖时序来保证一致性。

通常情况下，一条命令收到了集群大多数节点的响应时，这条命令就算完成了； 少量响应慢的机器不影响整体的系统性能。

一致性

一致性是分布式系统中的一个重要概念，指的是在系统中的所有节点上数据的状态保持一致。具体来说，一致性要求系统中的所有副本或节点在执行相同操作后，最终达到相同的状态。

分布式系统中，实现一致性是一个具有挑战性的问题，因为节点之间的通信可能会受到网络延迟、故障和并发操作的影响。

为了实现一致性，常见的方法包括：

• 强一致性（Strong Consistency）：强一致性要求系统中的所有节点在任何时间点看到的数据都是相同的。这意味着在写操作完成后，任何后续的读操作都将返回最新的写入结果。实现强一致性通常需要使用复杂的协议和算法，如Paxos、Raft等。
• 弱一致性（Weak Consistency）：弱一致性放宽了对一致性的要求，允许在系统中的不同节点之间存在一定的数据延迟和不一致。在弱一致性模型下，系统在数据更新后，并不保证立即反映到所有节点上，而是在一定的时间窗口内（例如，最终一致性）或特定的操作序列（例如，因果一致性）后达到一致状态。
• 顺序一致性（Sequential Consistency）：顺序一致性要求系统中的操作按照其在全局时间中的顺序执行。换句话说，对于任何两个操作，系统中的所有节点都会以相同的顺序观察到这两个操作的结果。顺序一致性通常通过在系统中引入全局时钟或通过向操作序列应用特定的顺序一致性规则来实现。
• 因果一致性（Causal Consistency）：因果一致性是一种弱一致性模型，它在系统中维护了一种因果关系，即当一个事件是另一个事件的因果关系时，所有节点都以一致的方式观察到这种因果关系。因果一致性是在分布式系统中实现较为常见的一致性模型之一。

Raft中的状态（身份）

Raft 是一种主从协议 ，一个集群中由一个leader和多个follower组成，进行提供服务

Leader （领导者）

在Raft协议中，只有一个节点可以作为领导者。领导者负责处理客户端请求，复制日志条目到其他节点，并向其他节点发送心跳以维持其领导地位。领导者在选举过程中被选为领导者，并且可以在没有故障的情况下持续保持其领导地位。

行为

• 领导者负责处理客户端请求，并将请求转换为日志条目，追加到自己的日志中。
• 领导者会向其他节点发送附带日志条目的心跳消息，以维持其领导地位。
• 领导者负责复制日志条目到其他节点的日志中，确保集群中的节点保持一致。
• 如果领导者接收到来自候选者或追随者的请求投票的消息，它会拒绝该请求并保持自己的领导地位。

Candidate （候选者）

当节点希望成为领导者时，它会成为候选者状态。节点成为候选者后，它会向其他节点发送请求投票的消息，并等待其他节点的响应。如果候选者在规定的时间内获得了大多数节点的选票，它将成为新的领导者。否则，如果出现投票平局或者在超时时间内没有获得足够的选票，候选者会重新发起新的选举。

行为

• 候选者状态是在选举过程中的临时状态。
• 候选者会向其他节点发送请求投票的消息，以获取其他节点的支持。
• 如果候选者在规定的时间内获得了大多数节点的选票，它将成为新的领导者。
• 如果候选者在选举超时时间内没有获得足够的选票，它会重新发起新的选举。

Follower （追随者）

大多数时间内，节点处于追随者状态。追随者接收来自领导者或候选者的消息，并按照其指示执行操作。如果追随者在一段时间内没有接收到来自领导者的心跳消息，则会开始新的选举过程，试图成为新的候选者。

行为

• 追随者是默认状态，当节点没有成为领导者或候选者时，它处于追随者状态。
• 追随者接收来自领导者或候选者的消息，并按照其指示执行操作。
• 如果追随者在一段时间内没有接收到来自领导者的心跳消息，它会触发新的选举过程，试图成为新的候选者。

Raft 共识算法

Raft 实现共识的机制是，

1. 共同选举出一个 leader，
2. 给予这个 leader 管理 replicated log 的完全职责，
3. Leader 接受来自客户端的 log entries，然后复制给其他节点， 并在安全（不会导致冲突）时，告诉这些节点将这些 entries 应用到它们各自的状态机。

为什么说Raft简单呢？因为只有一个 leader 的设计简化了 replicated log 的管理。例如，

• Leader 能决定将新的 entry 放到 log 中的什么位置，而不用咨询其他机器，
• 数据流也是从 leader 到其他节点的简单单向方式。

当Raft集群有半数以上节点工作时，集群是正常进行工作的

由上述所有 我讲共识所谓分成3个独立的子问题

1. Leader election
2. Log replication
3. Safety

因为是共识算法，那么从现在开始，我们要假设每台机器都是劣质的，随时会挂掉。网络也是不稳地的，随时会分区

Log Replication

先说说 日志复制 ，这里我觉得比较简单
Raft和大多数算法差不多，都是基于两段式提交

两段式提交 和 脑裂
两阶段提交（Two-Phase Commit，2PC）是一种常见的分布式事务协议，它可以用于处理脑裂（Split-Brain）问题，以确保分布式系统在发生故障或网络分区时的一致性。
脑裂是指分布式系统中的节点之间发生网络分区或通信故障，导致节点之间无法进行正常的通信和协调。在这种情况下，可能会出现多个子组（subgroup）形成的情况，每个子组中的节点相互独立，各自作出不同的决策，导致系统状态的不一致。

当Client（客户端）向leader提交一条新的Log entry时：

1. leader 会把新的 Log entry 统一发送给所有集群，并将此日志加入缓冲区buffer
2. follower 收到新的 Log entry ，将此消息加入缓冲区，重置leader的超时时间
3. follower 向leader回复 日志加入缓冲区
4. leader 收到过半 follower 将日志加入缓冲区的消息
5. leader 向所有 follower 发送 将此日志提交给所属服务 的信息
6. follower 向leader 回复 提交成功
7. leader 收到过半 follower 提交成功信息
8. leader 自己提交给所属服务

log 包含的信息

1. 自己的编号
2. 自己所在日志缓冲区的index（下标，索引）
3. 自己在接收这条消息时的 Trem（任期）「见下文」
4. Client发来的命令

日志的新旧程度要比较整个日志条目的最后一条日志的任期和下标

func Compare(a, b log) bool {
   
	if a.Term > b.Term {
   
		return true
	} else if a.Term == b.Term {
   
		return a.LogIndex > b.LogIndex
	} else {
   
		return false
	}
}

Commit

当前任期+副本数量过半，entry 才能提交

即使某个 entry 已经存储到了大多数节点，它仍然可能被新 leader 覆盖掉：

灾难

正常情况下，leader 和 follower 的 log 能保持一致，但 leader 挂掉会导致 log 不一致 （leader 还未将其 log 中的 entry 都复制到其他节点就挂了）。 这些不一致会导致一系列复杂的 leader 和 follower crash。 Figure 7 展示了 follower log 与新的 leader log 的几种可能不同：

图中每个方框表示一个 log entry，其中的数字表示它的 term。可能的情况包括：

• 丢失记录(a–b) ；
• 有额外的未提交记录 (c–d)；
• 或者以上两种情况发生 (e–f)。
• log 中丢失或多出来的记录可能会跨多个 term。

例如，scenario (f) 可能是如下情况：从 term 2 开始成为 leader，然后向自己的 log 添加了一些 entry， 但还没来得及提交就挂了；然后重启后迅速又成为 term 3 期间的 leader，然后又加了一些 entry 到自己的 log， 在提交 term 2& 3 期间的 entry 之前，又挂了；随后持续挂了几个 term。

解决

在进行日志更新追加时 发送前一条日志的任期和下标
在日志追加时

• 前一条的信息和leader发送的信息相同 追加成功
• 前一条的信息和leader发送的信息不相同 缓存
  • 向leader 回复失败 ，等待更早的日志

Leader Election

先说说 领导者选举

上面在说三种身份时，有提到过“当节点希望成为领导者时，它会成为候选者状态，进行领导者的竞选”。
什么是节点希望？

心跳

心跳（Heartbeat）在分布式系统中是一种常见的机制，用于监测节点的存活状态和通信连接的健康程度。它是通过定期发送小型的消息或信号来实现的。

分布式系统中，各个节点可以通过发送心跳消息来告知其他节点它们的存在和状态。这些心跳消息可以包含节点的标识符、时间戳以及其他相关信息。接收到心跳消息的节点可以根据这些信息来判断发送节点的存活状态和通信连接的可靠性。

在 Raft 中，leader会主动向每个follower进行心跳发送，向follower证明 – “嗯，我还活着，你不需要竞选”

当follower一段时间没有收到leader的心跳信息了，follower会进入Candidate状态，尝试成为新的leader

在 Raft 中心跳的超时时间是伪随机的 为了防止大家一起进行选举 都没票的情况重复发生

选举凭证

当然 Candidate 的选举并不是想成为 Leader 就可以成为的
其有三个凭证 – Term 、FreshLog 和 CommitIndex

FreshLog 顾名思义，更新的日志
我们着重说说 Trem

Term 任期

在Raft一致性算法中，Term（任期）是一个重要的概念，用于实现领导者选举和日志复制的一致性机制。每个节点在Raft中都有一个当前的任期，用于标识和比较节点之间的状态。

一个节点的工作生涯应该是像这样的，一个任期一个任期的

那么问题来了，任期何时会变更呢？

• 启动节点：当一个节点启动时，它会初始化自己的Term，并将其设置为一个较小的值（通常为0或1）。这个初始Term是为了确保节点在开始时具有较低的Term值，以便能够参与选举过程。
• 选举超时：每个节点都会定时检查是否需要发起选举。如果一个节点在一段时间内（称为选举超时）没有收到来自当前领导者的心跳消息或其他有效的RPC请求，它会认为当前领导者失效，并开始一个新的选举过程。在这种情况下，节点会增加自己的Term值，并发起选举。
• 收到更高Term的消息：当一个节点收到来自其他节点的消息时，它会检查消息中的Term值。如果消息中的Term值较高，表示有更高任期的领导者或候选者出现，节点会更新自己的Term值为收到的更高值，并根据相应的规则进行状态转换。
• 收到投票请求：在选举过程中，当一个节点收到来自其他节点的选举请求时，它会检查请求中的Term值。如果请求中的Term值较高，节点会更新自己的Term并投票给请求者。这样做是为了确保选举过程中的Term递增和节点状态的一致性。
• 收到日志任期都比自己高的领导者消息：在Raft算法中，领导者会定期发送心跳消息给其他节点以维持其领导地位。当一个节点收到来自当前领导者的心跳消息时，它会检查消息中的Term值。如果消息中的Term值较高，节点会更新自己的Term为领导者的Term，并保持跟随领导者。

CommitIndex

另外 只有包含并提交了所有提交日志的节点 才能成为Leader

灾难

现在需要思考一下，在Leader Election阶段灾难来了的情况了
情景：A B C D E 五台机器 在刚刚还是良好的状态 A是leader 任期是1

1. A 点挂掉了，集群行为是？
2. 网络分区 A B 两节点相互可见，与 C D E 之间不可见，集群行为是？
3. A 挂掉了 ， B 心跳超时 发起选举 C D 向 B 投完票后 ，B 也挂了，集群行为是？
4. 网络分区 A B C 之间可见 ， C D E 之间可见，集群行为是？
   1. 在这个问题下 提出了预选举

如果在上述条件下，Client还在不停的向集群提交日志，每个节点的日志新旧程度不一样 、每个节点的提交数目不一样，集群行为是什么？

SnapShot 和 persistent

快照（Snapshot）和持久化（Persistence）是两个关键概念，用于确保系统的一致性和可恢复性。

快照（Snapshot）：

• 快照是系统状态的全局副本，它包含了节点在某个时间点的整体状态信息。
• Raft中的快照用于压缩日志，防止日志不断增长导致占用过多的存储空间。
• 当节点的日志变得过于庞大时，Raft会生成快照来替代一部分日志，从而缩减日志的长度。
• 快照通常由自己（所属服务）生成，当raft节点落后很多时，leader可以向落后的follower发送快照以加速同步。

持久化（Persistence）：

• 持久化指的是将数据或状态持久保存在非易失性存储介质中，以便在系统故障或重启后能够恢复数据。
• 在Raft中，节点的状态（如日志、当前任期、投票信息等）需要持久化存储，以确保系统能够在故障后继续运行。
• 节点通过将状态写入持久化存储介质（如磁盘）中的日志文件或数据库来实现持久化。
• 当节点启动或重新启动时，它会从持久化存储中读取之前的状态，并根据该状态进行恢复和继续运行。
• 持久化还可以包括持久保存快照，以便在需要时能够快速加载和恢复系统状态。

快照和持久化在Raft中起着不同的作用。快照用于压缩日志，减少存储空间的占用，并且可以用于加快节点的恢复过程。持久化则是为了确保节点的状态能够在系统故障或重启后持久保存，并能够恢复到先前的状态，保证系统的可靠性和一致性。同时，快照和持久化是相互补充的，共同支持Raft协议的正常运行。通过定期生成快照和持久化存储节点的状态，Raft确保了即使在节点故障或重启的情况下，系统也能够从之前的状态恢复并继续提供服务。

---

Done