分布式一致性算法04 RAFT协议
Raft算法是一种用于分布式系统中的一致性算法，它通过选举领导者（Leader）来确保数据的一致性。Raft算法易于理解和实现，并且它通过日志复制（Log Replication）来保持集群中所有节点的状态一致。
Raft算法的关键组件：
领导者（Leader）：负责处理所有客户端请求，将日志条目（Log Entries）复制到其他节点。
跟随者（Follower）：接收领导者的日志条目并保持与领导者的心跳连接。
候选者（Candidate）：当跟随者在一定时间内没有收到领导者的心跳时，它们会变成候选者并尝试成为新的领导者。
日志条目（Log Entries）：记录了所有的事务操作，必须在所有节点上顺序一致。
Raft算法的工作流程：
选举领导者：
系统启动或领导者崩溃时，所有跟随者开始新一轮的领导者选举。
日志复制：
领导者接收到客户端的请求后，将其转换为日志条目并追加到自己的日志中。
日志同步：
领导者将新的日志条目发送给所有跟随者，跟随者接收并存储这些日志条目。
日志提交：
当领导者确认日志条目已经被大多数跟随者接收后，它将向跟随者发送提交指令，然后所有节点将日志条目应用到状态机中。
心跳和领导者续租：
领导者定期向跟随者发送心跳以维持其领导者地位，并接收跟随者的确认。
举例说明：
假设我们有一个由三台服务器组成的Raft集群，每台服务器初始状态都是跟随者。
系统启动：
所有跟随者启动后，由于没有领导者，它们开始进入选举超时，并转换为候选者。
选举领导者：
假设服务器A的任期（Term）最大，它收到了超过半数跟随者的投票（服务器B和C的投票），因此服务器A成为领导者。
客户端请求：
客户端向领导者A发送一个写请求，比如设置键值对key1=value1。
日志复制：
领导者A创建一个新的日志条目，包含这个写请求，并将其追加到自己的日志中。
日志同步：
领导者A将这个日志条目发送给跟随者B和C，它们接收并存储这个日志条目。
日志提交：
领导者A等待跟随者B和C的确认，一旦收到大多数确认（这里是B和C），它就向它们发送提交指令。
应用日志：
跟随者B和C接收到提交指令后，将日志条目应用到自己的状态机中，更新键值对。
心跳和续租：
领导者A定期向跟随者B和C发送心跳，以维持其领导者地位，并确保跟随者不会超时转换为候选者。
故障恢复：
如果领导者A发生故障，跟随者B和C会在超时后转换为候选者，并开始新的领导者选举过程。
通过这个例子，我们可以看到Raft算法如何通过领导者选举、日志复制、日志同步、日志提交和心跳机制来确保分布式系统中的数据一致性。
Raft算法中的领导选举过程是其核心机制之一，用于在没有领导者或当前领导者失败时选出新的领导者。以下是Raft算法领导选举过程的示例：
假设我们有一个由五台服务器组成的Raft集群，每台服务器初始状态都是跟随者（Follower）。集群中的每个节点都维护一个当前任期（Term）的记录，任期是一个递增的计数器，每次选举都会增加。
领导选举过程：
选举超时：
每个跟随者节点都有一个随机的选举超时时间，这个时间用来在没有收到领导者的心跳时触发新的选举。假设服务器1、2、3、4、5的超时时间分别随机设置为150ms、300ms、450ms、600ms和750ms。
超时转换：
假设当前没有领导者，并且跟随者节点没有收到任何心跳。当跟随者的选举超时时间到达后，它们会将自己的状态从跟随者转换为候选者（Candidate）。
增加任期：
候选者节点会首先增加自己的当前任期计数（Term），比如从Term 1增加到Term 2。
发送投票请求：
候选者向集群中的所有其他节点（包括其他跟随者和候选者）发送投票请求（RequestVote），包含自己的任期号和自己日志的索引和术语。
收集选票：
收到投票请求的节点会根据以下规则决定是否投票：
如果请求的任期号大于或等于自己的当前任期号，节点会更新自己的任期号并投票给请求者。
如果请求的任期号小于自己的当前任期号，节点会拒绝投票。
确定领导者：
如果一个候选者从集群中大多数节点那里收到投票，它就赢得了选举，成为新的领导者。
发送心跳：
新的领导者会立即向所有节点发送心跳信息，以通知它们自己的存在，并防止它们变成候选者。
跟随者响应：
当跟随者收到心跳信息时，它们会将自己的状态更新为跟随者，并开始接收和复制领导者的日志条目。
示例：
假设在150ms后，服务器1的超时时间最先到达，它变成候选者并开始选举过程。它将自己的任期计数增加到Term 2，并向其他服务器发送投票请求。
服务器2、3、4、5收到投票请求，检查任期计数，发现请求的任期（Term 2）大于它们自己的（Term 1），因此它们投票给服务器1。
服务器1收到超过半数的投票（4票），成为新的领导者。
服务器1开始向所有其他服务器发送心跳，其他服务器收到心跳后，确认服务器1为领导者，并开始跟随它的日志。
通过这个选举过程，Raft算法确保了在没有领导者或领导者失败的情况下，能够快速且一致地选出新的领导者，从而维持集群的一致性和可用性。
Raft算法的日志复制机制通过一系列步骤确保数据的一致性，这些步骤确保了所有跟随者（Follower）节点上的日志与领导者（Leader）节点上的日志保持一致。以下是Raft算法日志复制机制的详细说明：
日志条目的创建：
当领导者接收到来自客户端的请求时，它会创建一个新的日志条目，并将该条目附加到自己的日志末尾。
日志复制：
领导者将新日志条目发送给所有的跟随者。这个过程称为“AppendEntries RPC”，其中包含了日志条目的信息以及领导者的任期号等。
日志存储：
跟随者接收到AppendEntries RPC后，首先会验证领导者的任期号是否有效。如果有效，跟随者会将接收到的日志条目附加到自己的日志末尾。
日志一致性检查：
在存储新日志条目前，跟随者会检查新条目是否与自己日志中的最后一个条目兼容。如果兼容，即前一个日志条目的索引和术语与领导者发送的匹配，跟随者才会继续存储新的日志条目。
日志条目确认：
跟随者在成功存储日志条目后，会向领导者发送一个确认响应（包含当前的任期号和成功标识）。
提交日志条目：
当领导者接收到大多数跟随者的确认响应后，它会将该日志条目标记为“提交”状态，并应用该条目到自己的状态机中。
日志条目应用：
领导者随后会向所有跟随者发送包含已提交日志条目的AppendEntries RPC，指示跟随者也应用这些条目到它们的状态机中。
状态机一致性：
由于所有节点都按照相同的日志条目顺序执行操作，因此所有节点的状态机最终将保持一致。
处理并发日志：
如果领导者在等待日志条目提交的过程中接收到新的客户端请求，它会为每个请求创建新的日志条目，并按照顺序追加到日志中。
日志压缩：
为了减少存储空间的使用，Raft算法会定期进行日志压缩，保留关键的日志信息，而丢弃已经被持久化和应用的日志条目。
通过这个日志复制机制，Raft算法确保了即使在领导者发生故障的情况下，新的领导者也能够从跟随者那里获取完整的日志状态，继续处理客户端请求，并保持集群的数据一致性。
在Raft算法中，如果领导者节点失败，新选举出的领导者将通过以下步骤恢复之前的状态：
日志复制：
一旦新的领导者被选举出来，它将开始向所有跟随者发送心跳信息，同时开始日志复制过程。
日志匹配：
在日志复制之前，新的领导者需要确定自己的日志与跟随者的日志是否一致。它会发送AppendEntries RPC请求给跟随者，并在请求中包含自己日志的最后一条条目的索引和术语。
跟随者的响应：
跟随者接收到AppendEntries RPC后，会检查自己的日志以确定是否可以匹配领导者的日志。如果跟随者的日志在指定索引处的术语和索引与领导者的匹配，它会发送一个成功的响应。
日志不一致的处理：
如果跟随者的日志与领导者的不匹配，它会发送一个失败的响应，并告知领导者自己的日志信息。新的领导者将根据跟随者的响应调整自己的日志，可能会删除或追加日志条目以确保一致性。
日志压缩：
在日志同步过程中，如果发现日志存在空洞（即缺少中间的日志条目），新的领导者将引导跟随者进行日志压缩，删除已经被持久化和应用的日志条目，以减少存储空间并加快同步速度。
日志提交：
新的领导者会等待大多数跟随者确认日志条目的一致性后，才会将日志条目标记为已提交，并应用到状态机。
状态机恢复：
一旦日志同步完成，并且所有已提交的日志条目都已应用到状态机，新的领导者就完全恢复了之前领导者的状态。
继续处理请求：
状态恢复后，新的领导者可以继续处理客户端的请求，并保证集群的数据一致性。
日志的持续同步：
在整个集群运行过程中，领导者会持续地与跟随者同步日志，确保任何时候集群的状态都是一致的。
通过这些步骤，Raft算法确保了即使领导者失败，新的领导者也能够准确地恢复之前的状态，并且继续提供服务。这种机制提高了系统的可靠性和容错能力。