vlambda博客
学习文章列表

    Multi Paxos 给出了广义分布式日志状态机的抽象理论，但是和软件行业的工程实践有着很大差距，理解和落地都非常复杂。2014 年，来自斯坦福大学的 Diego Ongaro 和 John Ousterhout 发表了论文《In Search of an Understandable Consensus Algorithm》，提出了一种更易于理解和实现的分布式一致性算法 Raft。

    Raft 基于 Multi Paxos 演化而来，从工程实践的角度对 Paxos 理论和流程做了进一步拆分整理，通过增加限制来减少分布式系统需要考虑的状态，可以看作是 Multi Paxos 的简化版。Raft 强化了 Leader 的地位和作用，把分布式系统的工作过程显式地分成了两个阶段：Leader 选举和日志复制，Raft 强调 Leader 的唯一性和日志的连续性，另外，对数据安全、分区容错、配置变更等关键问题都给出了规范清晰的细节描述，可以直接用于实现。

Leader 选举

节点角色

    Raft 算法采用 Strong Leader 模型，以 Leader 为核心组织集群运作，集群中每个节点都处于以下三种角色之一：

• Leader：集群主节点，接收客户端发起的操作请求，写入本地日志后同步至集群其它节点。周期性地向所有 Follower 发送心跳消息（空的日志复制 RPC 消息）。

• Follower：集群成员，重定向客户端请求给 Leader，从 Leader 接收更新请求，写入本地文件。选举过程中负责投票。

• Candidate：候选节点，如果 Follower 在超时时间内没有收到 Leader 的心跳，则认为 Leader 可能已经故障，本节点切换为 Candidate 并发起重新选举。

任期

    为了区分日志的时序关系，Raft 将每一次选举开始，称为一个任期（term），每个 term 都有一个严格递增的整数 termID 与之关联。

    每当 Candidate 触发 Leader 选举时 termID 都会递增，如果一个 Candidate 赢得选举，它将在本 term 中担任 Leader 的角色。但并不是每个 term 都一定对应一个 Leader，有时候某个 term 内会由于选举超时选不出 Leader，这时 Candicate 会继续递增 termID 并开始新一轮选举。

    每一个节点都持久化保存一个 currentTerm，并带入通信消息的请求和响应中，Raft 通过节点之间的 term 交互来辅助选举，检测冲突，判断日志状态。节点之间通过 RPC 来通信，RPC 消息主要有两类：

• RequestVote RPCs: 用于 Candidate 拉票选举。

• AppendEntries RPCs: 用于 Leader 向其它节点复制日志以及同步心跳。

选举过程

    每个 Follower 都有一个随机选举超时时间 election timeout（150~300ms），Follower 每次收到 Leader 的心跳消息时就随机生成 election timeout 并重新开始计时；如果超时时间结束还没收到心跳，则认为 Leader 故障，Follower 切换成 Candidate 准备开始选举。

    Candidate 发起选举的动作包括：

• 重置选举超时时间。

• 把自己的 currentTerm 加1。

• 给自己投一票。

• 向其它节点发送 RequestVote(termID, candidateID, lastLogIndex, lastLogTerm) RPC 消息进行拉票，消息里包括了加1后的 termID，自己最后一条日志的索引 lastLogIndex 和任期 lastLogTerm。

    Follower 节点收到选举消息后遵循以下投票策略：

• Candidate 的 termID 小于自己的 currentTerm，投反对票。

• Candidate 的 lastLogTerm 大于自己，则 Candidate 日志较新，投赞成票。

• Candidate 的 lastLogTerm 和自己相等，且 lastLogIndex 大于等于自己，Candidate 日志较新，投赞成票，否则投反对票。

• Candidate 的 lastLogTerm 小于自己，投反对票。

• 每个 termID 只投出一个赞成票，先到先得，投票同时更新自己的 currentTerm。

    Candidate 在等待其它节点响应过程中会出现三种情况：

• 该 Candidate 收到了多数（majority）的赞成票当选了 Leader，并发送 Leader 心跳告知其它节点，其它节点全部变成 Follower，集群选主成功。

• 该 Candidate 收到了 Leader 发来的 AppendEntries 消息，且 Leader 的 termID 大于等于自己的，说明主节点已经选举成功，该 Candidate 切换成 Follower，集群选主成功。

• 选举超时时间内，该 Candidate 未收到超过半数的选票，也未收到 Leader 心跳，则说明该轮选主失败，重新发起 Leader 选举，直到选主成功。

    另外，所有节点在发现有更高 termID 的请求或响应消息时都会自动降级成 Follower 节点，同时更新自己的 currentTerm，从而保证任期内的 Leader 唯一，且拥有最新最全的已提交日志。

日志复制

    Raft 日志的每一条 log entry 包括三个部分：logIndex，termID，logValue（command）。

    Raft 中，所有的客户端请求都由 Leader 处理，Leader 通过以下步骤将日志分发到所有节点：

1. Leader 将客户端请求持久化附加到本机日志的最后，然后向其它节点发起同步日志记录消息 AppendEntries(termID, leaderID, PreLogIndex, PreLogTerm, entries[]) RPC，参数 PreLogIndex 和 PreLogTerm 表示本次请求之前一条日志记录的索引和任期，entries[] 代表本次请求日志列表，一次可以发送0或多条日志记录。

2. 其它节点收到请求后，如果 Leader 的 termID 小于自己的 currentTerm，返回拒绝；否则进一步对比 Leader 和本机的日志记录，有以下几种可能的场景：

1. 本机日志和请求之前的 Leader 日志一致（即本机 PreLogIndex 位置的日志记录的 term 和收到的 PreLogTerm 一致），则将 entries[] 按顺序覆盖记录到本机日志，返回接收信息给 Leader。

2. 本机日志和请求之前的 Leader 日志不一致（即本机 PreLogIndex 位置没有日志，或 PreLogIndex 位置的日志 term 小于 Leader 的 PreLogTerm），返回拒绝。下图展示了各种不一致场景。




1. 

2. 
   

3. Leader 收到拒绝信息后，将发送的日志索引回退一格（PreLogIndex-=1），把不一致的日志记录加入请求 entries 列表，重新发起同步日志记录消息 AppendEntries(termID, leaderID, PreLogIndex, PreLogTerm, entries[]) RPC。直到 Follower 找到和 Leader 匹配的日志记录后，则开始接受处理请求里的 entries。如下图。

   
   

4. Follower 使用 Leader 日志记录覆盖本机日志时，会同时把该日志后续的所有日志清空，确保集群节点日志都以 Leader 日志为准。如下图。

   
   

5. Leader 收到多数节点的日志接收回复后，将本机的 log entry 置为 commited，交由状态机执行（apply），并返回结果给客户端。然后向其它节点发送提交日志记录消息 AppendEntries(termID, leaderID, PreLogIndex, PreLogTerm, entries[], commitIndex) RPC 通知其它节点提交并执行，commitIndex 表示 Leader 提交后的最大日志索引。

6. Follower 节点每提交一条日志到状态机，同时更新本地的 commitIndex 和 lastApplied 记录，直到和 Leader 发送的索引位置一致，实现日志和状态双同步。 

    最后推荐下原文链接里的 Raft 算法动画演示，简单易懂，一学就会。