Raft算法

Raft是一种共识算法，旨在替代Paxos。 它通过逻辑分离比Paxos更容易理解，但它也被正式证明是安全的，并提供了一些额外的功能。[1] Raft提供了一种在计算系统集群中分布状态机的通用方法，确保集群中的每个节点都同意一系列相同的状态转换。 它有许多开源参考实现，具有Go，C ++，Java和Scala中的完整规范实现。

基本Raft通过当选的领导者达成共识。筏集群中的服务器是领导者或追随者，并且在选举的精确情况下可以是候选者（领导者不可用）。领导者负责将日志复制到关注者。它通过发送心跳消息定期通知追随者它的存在。每个跟随者都有一个超时（通常在150到300毫秒之间），它期望领导者的心跳。接收心跳时重置超时。如果没有收到心跳，则关注者将其状态更改为候选人并开始领导选举。

对Raft共识问题的探讨Raft通过领导方法实现共识。该集群只有一个当选的领导者，负责管理集群其他服务器上的日志复制。这意味着领导者可以决定新条目的放置和在其与其他服务器之间建立数据流而无需咨询其他服务器。领导者领导，直到失败或断开连接，在这种情况下，新的领导者当选。

共识问题在Raft中被分解为下面列出的两个相对独立的子问题。

领导人选举当现有领导者失败或启动算法时，需要选出新的领导者。

在这种情况下，新的术语在集群中开始。术语是服务器上的任意时间段，在此期间需要选出新的领导者。每个学期都以领导者选举开始。如果选举成功完成（即选出一名领导人），该任期将继续由新领导人精心策划的正常运作。如果选举失败，那么新的选举就会开始。

领导者选举由候选服务器启动。如果服务器在称为选举超时的时间段内没有收到领导者的通信，则服务器成为候选者，因此它假定不再有代理领导者。它通过增加计数器一词，投票给自己作为新的领导者，并向所有其他要求投票的服务器发送消息来开始选举。服务器每个学期只会投票一次，先到先得。如果候选人收到来自另一个服务器的消息，该消息的术语编号至少与候选人当前的期限一样大，则候选人的选举将被取消，候选人将变为追随者并将该领导者视为合法。如果候选人获得多数票，那么它就成为新的领导者。如果两者都没有发生，例如，由于分裂投票，则新的任期开始，新的选举开始。

Raft使用随机选举超时来确保快速解决分割投票问题。这应该减少分裂投票的机会，因为服务器不会同时成为候选者：单个服务器将超时，赢得选举，然后成为领导者并在任何关注者成为候选者之前向其他服务器发送心跳消息。

日志复制领导者负责日志复制。它接受客户端请求。每个客户端请求都包含一个由集群中复制的状态机执行的命令。在作为新条目附加到领导者的日志之后，每个请求将作为AppendEntries消息转发给关注者。如果关注者不可用，则领导者将无限期地重试AppendEntries消息，直到所有关注者最终存储日志条目。

一旦领导者收到其大多数粉丝的确认，该条目已被复制，领导者将该条目应用于其本地状态机，该请求被视为已提交。此事件还会提交领导者日志中的所有先前条目。一旦关注者得知提交了日志条目，它就会将该条目应用于其本地状态机。它通过集群为所有服务器之间的日志提供一致性，确保遵守日志匹配的安全规则。

在领导者崩溃的情况下，日志可能会保持不一致，旧的领导者的一些日志未通过群集完全复制。然后，新的领导者将通过强制关注者复制其自己的日志来处理不一致。为此，对于每个关注者，领导者将其日志与来自跟随者的日志进行比较，找到他们同意的最后一个条目，然后删除跟随者日志中此关键条目之后的所有条目，并将其替换为拥有日志条目。此机制将恢复出现故障的群集中的日志一致性。

安全Raft的安全规则Raft保证每个安全属性：

选举安全：在一个特定的任期内，最多只能选出一名领导人。

Leader Append-Only：领导者只能在其日志中添加新条目（它既不能覆盖也不能删除条目）。

日志匹配：如果两个日志包含具有相同索引和术语的条目，则日志在通过给定索引的所有条目中都是相同的。

领导者完整性：如果在给定的术语中提交了日志条目，那么从该术语开始，它将出现在领导者的日志中。

状态机安全性：如果服务器已将特定日志条目应用于其状态机，则其他服务器不会对同一日志应用不同的命令。

前四节中描述的算法的细节保证了四个第一规则。选举过程受到限制，保证了国家机器安全。

国家机器安全此规则通过一个简单的限制来确保：候选人无法赢得选举，除非其日志包含所有已提交的条目。为了当选，候选人必须联系群集的大多数，并且根据要提交的日志规则，这意味着每个提交的条目将出现在候选人联系的至少一个服务器上1。

通过比较日志中最后一个条目的索引项，Raft确定两个日志中的哪一个（由两个不同的服务器承载）更新。如果日志具有包含不同术语的最后一个条目，则具有较晚术语的日志将更新。如果日志以相同的术语结束，则更长的日志更新是更新的。

在Raft中，候选人对选民的请求包括有关候选人日志的信息。如果其自己的日志比候选人的日志更新，则选民拒绝其对候选人的投票。此实现确保了State Machine Safety规则。
追随者崩溃

如果关注者崩溃，其他服务器发送的AppendEntries和投票请求将失败。这些故障由服务器无限期地尝试到达被击落的追随者来处理。如果关注者重新启动，则挂起的请求将完成。如果在失败之前已经考虑了请求，则重新启动的关注者将忽略它。

时间和可用性随着时间的推移，时间对于Raft选择和保持稳定的领导者至关重要，以便拥有完美的群集可用性。通过遵守算法的时序要求来确保稳定性：

broadcastTime