（本文仅为个人的一些理解，论文原文。译文1，译文2)
相关文章：1.分布式问题由来，2.原理学习（一）——时间，时钟，事件顺序

1.介绍

Raft协议与Paxos协议类似，都是一种分布式系统中的强一致算法¹。Paxos主要从理论的角度上证明了强一致性可以被保证，但是对于协议的实现细节上并没有给出很好的说明²，同时Paxos算法本身也非常难理解。Raft协议能够达到与Paxos协议相同的效果，但是在理解和实现上面更加容易。

2.复制状态机

一致性算法是在复制状态机的背景下产生的。 在这种方法中，一组服务器上的状态机计算相同状态的相同副本，并且即使某些服务器宕机，也可以继续运行。

复制状态机

复制状态机的一种实现方式是复制日志，raft协议就是通过复制日志来实现复制状态机的。

3.核心功能

Raft算法主要实现了几个功能：

• Leader选举：保证有一个leader能够被选举出来，且某个任期内只能有一个leader存在。
• 日志复制：Leader 必须从客户端接收日志条目然后复制到集群中的其他节点，并且强制要求其他节点的日志和自己的保持一致。
• 安全性：在故障、冲突等各种条件下保证状态机是一致的。

4.实现

(1).Leader选举

• 竞选：Leader会向每个节点(follower)发送心跳，如果某个follower一段时间没有收到心跳，就会开始竞选（变成candidate）。竞选的时候会向所有follower发送申请，如果超过半数的follower通过了，则candidate升级为ledaer。特别的，为了防止瓜分选票，每个follower的超时时间都是不一样的。
• 逻辑时钟^[1] :所有竞选请求都带了逻辑时钟值，通过该值来判断竞选是否有效。如果candidate的时钟值落后于follower，则follower会拒绝这个竞选请求。同时如果某个leader收到了更高的时钟值的心跳，会自动退位成为follower。
• 任期： 从一个选取开始到下一个选举开始的一段时期。为了保证只有一个leader被选举出来，某个任期内每个follower只会投一票。
  
  任期

(2).日志复制

• 复制：Leader负责把日志复制到其他节点，当日志安全的复制（超过一半成功）成功过后，状态机会执行指令，并返回结果给客户端。如果出现意外，Leader会不断重试知道所有节点都复制成功。
• 索引：每条日志都有一个索引，且对于已经提交的日志，相同索引的日志一定是相同的。Raft 维护着以下特性（比较抽象，但是通过这些特性可以满足日志索引的唯一）：
  1. 如果不同日志中的两个条目拥有相同的索引和任期号，那么他们存储了相同的指令。
  2. 如果不同日志中的两个条目拥有相同的索引和任期号，那么他们之前的所有日志条目也都相同。
• 冲突：某些故障情况下，某些节点先后变成Leader，可能会导致不同节点日志的不一致。这个时候leader需要负责把所有节点的日志同步，Leader不会删除自己的日志，而是会把follower的不一致的日志清楚，然后再同步成自己的。
  
  日志冲突

(3).安全性

如果一个日志已经被提交，我们要确保在解决冲突的时候不会把它删掉，这样才能保证安全性。

• 选举限制：candidate在竞选的时候需要包含最新日志信息，如果follower发现自己的日志比candidate要新，就会拒绝它的选举请求³。
• Follower 和 candidate 崩溃：如果某个节点崩溃了，Leader会不断同步日志过去，而且因为是幂等操作，不会影响安全性。
• 活性：只要整个系统满足下面的时间要求，Raft 就可以选举出并维持一个稳定的 leader。
  
  活性时间要求
  
  一般来说广播时间大约是 0.5 毫秒到 20 毫秒之间，所以选举超时时间可能需要在 10 毫秒到 500 毫秒之间。大多数的服务器的平均故障间隔时间都在几个月甚至更长，很容易满足条件。

5.其他

• 集群成员变更：raft协议还考虑了集群增加和减少节点的情况，这个时候一个中间态。中间态竞选需要同时满足新旧两套规则，通过这种方式可以保证安全性，同时规则的生效时机也是基于日志复制一样的方式，所以是一致的。（详见原文）。
• 日志压缩：因为不停的写日志磁盘会满，而且如果每次新节点加入都从头开始同步日志，效率会很低。所以各个节点会定期对已经提交的日志进行压缩⁴。
• 客户端交互：
  1. 开始的时候客户端随机访问一个节点，节点会告诉客户端Leader的位置。
  2. 客户端的请求也需要带上序号，这样可以通过幂等的方式应对网络问题。
  3. 对于客户端的读请求，leader必须要确保现在自己确实还是Leader才能够进行返回，所以需要先与超过半数的节点交互心跳⁵。

¹：强一致，且基本可用，不违背CAP原理。
²：比如在增加，减少机器的时候也保持一致。
³：一个follower如果承认某个选举，那么它就会拒绝之前leader后续的写日志请求。如果接受了写日志请求，那么就要确保candidate的日志是最新的。选举条件变得更加严格，在故障发生的时候可用性会有所降低。
⁴: 这里也会有安全性问题，原文中也给出了解决方法。
⁵: 这里原理类似与客户端与超过半数的节点通信，无疑会对性能有一定影响。

^[1]：Time, Clocks, and the Ordering of Events in a Distributed System.