目录

什么是 Raft 算法？

Leader的选举

投票分裂后的选举过程

Raft算法日志复制过程

修复不一样的日志 

数据安全性的保证

---

什么是 Raft 算法？

Raft 算法是一种是一种用于管理复制日志的强一致性算法，用于保证分布式系统中节点数据的一致性。

Raft 算法中节点有三个角色：

• 领导者（Leader）：负责接收客户端的请求，向其他节点发送日志条目，并协调日志的复制和提交。在一个 Raft 集群中，同一时刻只会有一个领导者。
• 跟随者（Follower）：被动地接收来自领导者的日志条目和心跳消息。如果在一定时间内没有收到领导者的心跳，跟随者可能会转变为候选人，发起选举。
• 候选人（Candidate）：由跟随者在选举期间转变而来，会向其他节点发送投票请求，试图成为领导者。

Leader的选举

现在有五个节点均处于未启动状态，如下图：

每个节点初始时都是Follower并且维护维护一个定时器与任期号，在定时器到期前如果没有收到 Leader 节点的心跳消息就会发起选举，过程如下：

• 增加任期号：候选人将自己的任期号加 1。任期号是 Raft 算法中用于区分不同选举轮次和标识数据新旧的重要概念，每次选举都会产生一个新的、更大的任期号。
• 投票给自己：候选人给自己投一票。每个节点在每一轮任期内只能投出一票，且按照先到先得的原则，谁先发送投票请求就投给谁。
• 发送请求投票 RPC：候选人向集群中的其他节点发送请求投票的 RPC（远程过程调用）消息。该消息包含候选人的任期号、自身 ID 等信息。
• 其他节点处理投票请求：跟随者节点在收到请求投票的 RPC 消息后，会进行一系列检查，如检查候选人的任期号是否大于自己当前的任期号等。如果候选人的任期号大于跟随者当前的任期号，且跟随者在当前任期内还没有投过票，并且候选人的日志至少和跟随者的日志一样新，那么跟随者就会投赞成票，并更新自己的任期号为候选人的任期号。如果候选人的任期号小于跟随者当前的任期号，或者候选人的日志没有跟随者的日志新等不满足投票条件的情况，跟随者会投反对票。
• 判断选举结果：候选人在发送投票请求后，会等待接收其他节点的投票响应。如果候选人在一段时间内收到了集群中大多数节点（超过半数）的赞成票，那么它就赢得了选举，成为领导者。如果没有候选人获得多数票，或者出现多个候选人获得相同票数的情况，那么就会进入新的一轮选举。在新的选举中，候选人会再次增加任期号，重复上述选举过程，直到有候选人成功当选领导者为止。

我们启动节点，直观的感受一下这个过程：

如果候选人的任期号小于跟随者当前的任期号，跟随者会投反对票。

投票分裂后的选举过程

如果在一轮选举中，有多个候选人，获得了相同的票数，那么就会进入新的一轮选举：

Raft算法日志复制过程

Raft 中的日志由一系列的日志条目组成，每个条目包含一个任期号（term）、一个条目索引（index）和一个操作指令。任期号用于标识日志条目的所属任期，索引用于唯一标识每个日志条目中的位置。日志复制流程如下：

• 客户端请求：客户端向 Leader 节点发送写请求，请求中包含要执行的操作指令，例如创建、更新或删除数据等。
• Leader 记录日志：Leader 接收到客户端请求后，为该操作分配一个唯一的日志索引，并在本地日志中追加一个新的日志条目，包含当前任期号、日志索引和操作指令。然后，Leader 将该日志条目标记为未提交状态。
• 复制日志到 Follower：Leader 将新的日志条目发送给所有 Follower 节点。信息包含了日志条目的任期号、索引以及之前条目的任期号和索引等信息，以便 Follower 进行验证和匹配。
• Follower 处理日志：Follower 节点接收到信息后，会进行一系列的检查。首先检查消息中的任期号，如果发现任期号小于自己当前的任期号，则认为该消息过期，直接拒绝并向 Leader 发送包含自己当前任期号的响应。如果任期号匹配，Follower 会检查日志条目的索引和之前条目的信息是否与自己的日志匹配。如果匹配，Follower 将日志条目追加到自己的日志中，并向 Leader 发送确认响应，表示日志已成功接收。
• 日志提交：Leader 在收到大多数 Follower 对某个日志条目的确认响应后，认为该日志条目可以提交。Leader 将该日志条目标记为已提交状态，并应用该日志条目中的操作到本地状态机，更新本地数据。然后，Leader 会向 Follower 发送 AppendEntries RPC，通知 Follower 该日志条目已提交，Follower 收到后也将相应的日志条目标记为已提交，并应用到本地状态机。
• 响应客户端：一旦 Leader 将日志条目应用到本地后，就可以向客户端发送响应，告知客户端操作已成功完成。

修复不一样的日志 

在系统中，节点可能因硬件故障、软件错误或网络问题等原因而崩溃，在重新启动后可能会导致日志与其他节点不一致。为了保证数据的一致性，Leader节点需要对日志进行修复。

如何检测日志一致性？

Raft 算法通过日志的索引和任期号来进行日志匹配。Leader 在发送消息时，会携带前一个日志条目的索引和任期号。Follower节点会检查自己的日志中是否存在与 Leader 发送的前一个日志条目相匹配的条目。

如果匹配，则认为 Leader  的日志是最新的，并尝试将自己的日志与 Leader 的日志进行对齐。如果发现自己的日志与 Leader 的日志存在冲突，它会根据日志条目的任期号和索引来进行冲突解决。

如果追随者的日志条目任期号小于领导者的日志条目任期号，则追随者会删除自己的日志条目，并接受领导者的日志条目。如果任期号相同但索引不同，则追随者会根据日志条目的内容来判断哪个日志条目是正确的，并进行相应的处理。

同时领导者会定期向Follower发送消息，检测日志一致性。当领导者发现某个 Follower 的日志与自己不一致时，它会强制Follower删除不匹配的日志条目，并将自己的日志条目发送给Follower，让Follower进行追加。
 

数据安全性的保证

在日志修复时，我们知道 Leader 节点会将自己的日志同步到所有节点，那么如果有一个节点失去与主节点的连接在超时后，竞选Leader节点同时连接恢复竞选并成功，然后同步日志，由于新的 Leader 节点没有断连时期的数据，断连时期的数据就会被覆盖。

Raft 为了避免这种情况，在竞选时不仅依靠任期号，候选人的日志至少要跟随者的日志一样新，跟随者才会投赞成票。

动画来源：Raft Consensus Algorithm