Raft

2017-04-19

Raft 是一种用来管理日志复制的一致性算法
可用性：避免单点故障
性能：多机器提供相同服务
分两阶段实现：Leader选举和日志复制

1.基本概念

为便于后面的理解或查阅，把主要概念提出来，因此有些介绍会和后面重复

1.1 基本角色

每个服务器节点都处于这三种状态之一：follower 、 candidate 、leader 。

Follower：每个节点最初都是follower，完全被动，不发出请求，响应leader和candidate的请求。
Candidate：候选者，用来选举出一个leader。
Leader：集群主节点，整个集群仅有一个leader节点可以存在。处理所有的客户端请求（如果一个客户端和follower通信，follower会将请求重定向给 leader），向其他节点周期性的发送心跳（不包含日志条目的 AppendEntries RPC）来维持自己的地位。

follower，candidate，leader的升级序列，角色不会跨级别提升

节点角色转变

1.2 两种RPC

服务器节点之间使用 RPC 进行通信。

请求投票（RequestVote） RPC ：由 candidate 在选举期间发起，发送给每个节点
追加条目（AppendEntries）RPC ：由 leader 发起，用来复制日志和提供一种心跳机制

1.3 两种timeout

election timeout：每个follower若在election timeout中未收到RPC，则成为candidate，并发出投票，在这段时间内收到半数以上投票则成为Leader
heartbeat timeout：用于Leader发送AppendEntries RPC心跳机制。

1.4 Term

Term：一轮选举开始到下一轮选举开始则为一个term（任期）。

1.5 节点状态

2.Leader选举

每个节点最初都是follower，每个follower都有一个选举超时时间（election timeout），通常为150ms到300ms之间。如果一个节点在election timeout内没有接收到任何消息（来自 leader 或 candidate的RPC），它就认为系统中没有可用的 leader ，成为candidate，最终选举出新leader。

开始一次选举过程，follower 先增加自己的当前任期号并且转换到 candidate 状态。然后投票给自己并且并行地向集群中的其他服务器节点发送 RequestVote RPC（让其他服务器节点投票给它）。每轮Term，每个节点按照先来先服务（first-come-first-served）的原则只能投一票，一个candidate得到大多数节点投票才能成为leader。Leader周期性向其他节点发送心跳（不包含日志条目的 AppendEntries RPC）来维持自己的地位。

Candidate 会一直保持当前状态直到以下三件事情之一发生：(a) 它自己赢得了这次的选举——变为leader，(b) 其他的服务器节点成为 leader——变为follower ，(c) 一段时间之后没有任何获胜者——重新选举。

如果有多个 follower 同时成为 candidate ，那么选票可能会被瓜分以至于没有 candidate 赢得过半的投票。当这种情况发生时，每一个候选人都会超时，通过增加当前任期号来开始一轮新的选举。每个 candidate 在开始一次选举的时候会重置一个随机的选举超时时间，防止在新的选举中再次发生选票瓜分情况，然后开始新一轮选举。

3.日志复制

Leader 一旦被选举出来，就开始为客户端请求提供服务。客户端的每一个请求都包含一条将被复制状态机执行的指令。Leader 把该指令作为一个新的条目追加到日志中去，然后并行的发起 AppendEntries RPC 给其他的服务器，让它们复制该条目。当该条目被安全地复制（复制到过半的服务器上），该日志条目就会被提交，leader 会应用该条目到它的状态机中（状态机执行该指令，这种日志条目被称为已提交的）然后把执行的结果返回给客户端。同时，leader 日志中该日志条目之前的所有日志条目也都会被提交，包括由其他 leader 创建的条目。如果 follower 崩溃或者运行缓慢，或者网络丢包，leader会不断地重试 AppendEntries RPC（即使已经回复了客户端）直到所有的 follower 最终都存储了所有的日志条目(log entry)。

每个日志条目存储一条状态机指令和 leader 收到该指令时的任期号。任期号用来检测多个日志副本之间的不一致情况。每个日志条目都有一个整数索引值来表明它在日志中的位置。

AppendEntries RPC 执行一个简单的一致性检查。在发送 AppendEntries RPC 的时候，leader 会将前一个日志条目的索引位置和任期号包含在里面。如果 follower 在它的日志中找不到包含相同索引位置和任期号的条目，那么他就会拒绝该新的日志条目。

正常操作期间，leader 和 follower 的日志保持一致，所以 AppendEntries RPC 的一致性检查从来不会失败。然而，leader 崩溃的情况会使日志处于不一致的状态（老的 leader 可能还没有完全复制它日志里的所有条目）。

Follower 可能缺少一些在新 leader 中有的日志条目，也可能拥有一些新 leader 没有的日志条目，或者同时发生。缺失或多出日志条目的情况可能会涉及到多个任期。

在 Raft 算法中，leader 通过强制 follower 复制它的日志来解决不一致的问题。这意味着 follower 中跟 leader 冲突的日志条目会被 leader 的日志条目覆盖。

要使得 follower 的日志跟自己一致，leader 必须找到两者达成一致的最大的日志条目（索引最大），删除 follower 日志中从那个点之后的所有日志条目，并且将自己从那个点之后的所有日志条目发送给 follower 。所有的这些操作都发生在对 AppendEntries RPCs 中一致性检查的回复中。Leader 针对每一个 follower 都维护了一个 nextIndex ，表示 leader 要发送给 follower 的下一个日志条目的索引。当选出一个新 leader 时，该 leader 将所有 nextIndex 的值都初始化为自己最后一个日志条目的 index 加1。如果 follower 的日志和 leader 的不一致，那么下一次 AppendEntries RPC 中的一致性检查就会失败。在被 follower 拒绝之后，leaer 就会减小 nextIndex 值并重试 AppendEntries RPC 。最终 nextIndex 会在某个位置使得 leader 和 follower 的日志达成一致。此时，AppendEntries RPC 就会成功，将 follower 中跟 leader 冲突的日志条目全部删除然后追加 leader 中的日志条目（如果有需要追加的日志条目的话）。一旦 AppendEntries RPC 成功，follower 的日志就和 leader 一致，并且在该任期接下来的时间里保持一致。

只要过半的服务器能正常运行，Raft 就能够接受，复制并应用新的日志条目；在正常情况下，新的日志条目可以在一个 RPC 来回中被复制给集群中的过半机器；并且单个运行慢的 follower 不会影响整体的性能。