好久没有更新博客了，最近研究了Raft 协议，谈谈自己对 Raft 协议的理解。希望这篇文章能够帮助大家理解 Raft 论文 。

Raft 是什么？

Raft 是一种分布式系统的一致性算法。

在分布式系统中，我们需要让一组机器作为一个整体向外界提供服务。由于在实际的条件下，我们认为每台机器都是不100%可靠的，随时都可能发生宕机。每台机器之间的通信也不是可靠的，可能发生通信的阻塞、丢失、重试。所以需要某些算法来保证在大多数机器都正常的情况下向外提供可靠的服务。

在 Raft提出之前，Paxos 已经被提出，但是 Paxos 相当复杂。Raft 的目标就是提出一种易于理解的分布式一致性算法。

在了解 Raft 之前需要了解一下什么状态机:

论文指出，Raft 是一种用来管理日志复制的一致性算法。所以我们就要先了解一下。什么是日志复制状态机。我们思考一个问题。如果你要与你的小伙伴分享一个很复杂的操作及计算。一般来说你有两种做法： 第一种:你自己负责计算，经过一段时间的计算，算出结果后，直接把计算结果告诉你的小伙伴。 第二种:你把每一个操作的步骤都告诉你的伙伴，告诉他怎么做，由你的伙伴自己计算出结果。

第二种方式，就是复制状态机的工作原理。复制状态机是通过复制日志来实现的。每一台服务器保存着一份日志，日志中包含一系列的命令，状态机会按顺序执行这些命令。因为每一台计算机的状态机都是确定的，所以每个状态机的状态都是相同的，执行的命令是相同的，最后的执行结果也就是一样的了。

在实际中这种有很多类似的应用比如 mysql 的主从同步就是通过 binlog 进行同步。

在现实生活中，如何有效的组织多人进行协助，最自然的想法就是选举一个领导，交由领导极大的权威，就能极大的提升整个团队工作效率。

下面就谈谈我对 Raft 算法的理解。

基本安全保证：

为了保证过程正确性，Raft需要保证以下的性质时刻为真：

• 选举安全原则： 同一届任期内至多只能有一个领导人。

• 领导人只加原则： 领导人的日志只能增加，不能重写或者删除。

• 日志匹配原则： 如果两个日志具有相同的任期和索引，则这两段日志在[0,索引]之间的日志完全相同。

• 领导人完全原则： 如果一条日志被提交，那么后续的任意任期的领导人都会有这条日志。

• 状态机安全原则： 如果一个服务器已经将给定索引位置的日志条目应用到状态机中，则所有其他服务器不会在该索引位置应用不同的条目。

选取领导者

所以 Raft 算法成立的最重要的前提之一就是选举。

• Raft 由多个节点组成。
• 强领导者， 整个 Raft 在同一时间，只有一个领导者，日志有领导者负责分发和同步。
• 领导选举， 领导是由民主选举产生的，集群中多数节点投票通过就能成为主。

对于在集群中的节点。在任意时间中，都有可能处于以下三种状态之一：

• 跟随者
• 候选人
• 领导人

每个领导人都有一个任期限制。每一届任期的开始阶段，都是选举。如果选举出了领导者就由该领导人负责领导集群。如果没有选举出领导，就会进入下一次选举。直到选举出领导者为止。

角色之间的转换：

领导者会周期性的向每台机器发送心跳，确保自己的领导地位。

跟随者在长时间没有收到领导人的心跳，就会发起投票成为候选人，同时任期 + 1，如果获得超过半数的支持，就升任为领导。

如果候选人，在发起投票的时候，发现集群里面有领导人的时候，就会重新成为追随者。

如果候选人，发起投票后，一定时间里面没有收到超过半数的反馈，就会再次发起投票。

如果领导者发现在集群中发现存在下一任期的领导者，就会变为追随者。

日志同步

在选举出领导人以后，就开始处理客户端的日志。

领导者在收到客户端的请求，每个请求包含一个操作的命令。领导者会将命令记录到自己的日志中，并向自己的追随者发起同步的请求，要求自己的追随者复制这个命令。

一旦这个命令被大多数的追随者保存了。领导者就认为这个状态已经处于提交（commited）的状态。同时告知客户端，命令已经被提交。如果这个时候，追随者发生了崩溃或者延时。领导者会一直尝试重试，直到追随者接受命令，并存储到自己的日志中。这个过程一直持续到所有的追随者最终存储了所有的日志条目。

作为 Raft 的节点需要保证如下性质。

• 如果在不同日志中的两个条目有着相同的索引和任期号，则它们所存储的命令是相同的。
• 如果在不同日志中的两个条目有着相同的索引和任期号，则它们之间的所有条目都是完全一样的。

有了如上性质的保证。如果在某些情况下，发生了追随者的日志与领导者不同步的情况。（包括的情况，就可能是丢失日志，或者保存了领导者没有的日志，或者两兼有），在 Raft 算法中，领导人通过强制追随者们复制它的日志来处理日志的不一致。这就意味着，在追随者上的冲突日志会被领导者的日志覆盖。

为了使得追随者的日志同自己的一致，领导人需要找到追随者同它的日志一致的地方，然后删除追随者在该位置之后的条目，然后将自己在该位置之后的条目发送给追随者。

安全分析

需要分析在各种情况下，每个角色发生宕机，数据的安全性。

选举限制

Raft 保证自己的日志，永远由领导者向追随者流动。也就是说领导者永远不会删改自己的日志，只能向上增加日志。为了达成这个限制，Raft 使用投票的方式来阻止没有包含全部日志条目的服务器赢得选举。

当一个候选人发起投票的时候，需要告诉大家，自己最新的日志。其他节点在投票的时候，要保证自己的日志不能比候选人的新，否则就拒绝投票。通过这个限制就保证了获取多数票的领导者的日志，至少比大多数人要新。

任期越大，日志越长，越容易成为领导者。

提交之前任期的日志条目

这个在论文中比较难以理解。我看到这一节的时候也是读了好几遍才理解论文的意思。实际上作者表达的意思是图 （d）是正确的，而（e）是错误的。

因为 2 号日志没有commited，但是由于一系列操作，造成了 2 号日志没有提交，但是高任期的leader 却认为 2 号日志被提交了。

为了解决这个问题。Raft 限制，只有当前任期的 leader 可以决定一条日志是否 commited，而不能由高任期的 leader 通过计算某条日志（例子中的 2号日志）超过半数节点持有，就确定日志被commited。

换句话说，就是 Raft 限制每个leader 只能确定自己任期内的日志是否commited。而不能由高任期的 leader确定。

追随者和候选人崩溃

由于 Raft 是一个强领导的，少数服从多数的系统。上面花了了很多的篇幅讨论 leader 奔溃后 Raft 协议是如何保证准确性和安全性的。如果追随者或者候选人挂了，就比较简单了。