并发编程网 - ifeve.com

Raft是当前分布式领域最重要的一致性算法之一，今天我们就来好好研究研究这个算法的[论文][1], 还有对应[网站][2], [动画][3], 不想看英文的也有中文的[翻译][4]，所以我这边就不翻译了，主要还是记录一下论文重点和自己的心得。

Raft算法作者的初衷是对标Paxos算法（过去十年分布式一致性的事实标准），但是要比它更易理解，主要手段有：
1. 分解，把整个一致性问题拆分为**Leader选举**、**日志复制**和**安全机制**这**三大方面**还有**角色改变**这个小方面。所以**模块化**是一个软件系统可维护、理解和扩展的不二手段。
2. 减少状态空间的状态，相比于Paxos，Raft减少了非确定性和服务器之间可以处于不一致的方式。所以在复杂的问题上**做减法**，可以减少很多不必要的繁琐的步骤。

Raft使用了更强的Leader，感觉这和我之前看的[OceanBase][5]是相似的，就是增强Leader（UpdateServer）或者说**单点**的作用，加重中心化（这也是社会的运作方式，没有Leader就是大家一盘散沙，文明是达不到今天这个程度的），要做决策就先选择一个Leader，然后让他去协调所有的决议，会更加简单快速，而Paxos就是P2P或者说弱Leader的方式。事实上，我们之所以使用分布式系统也是迫不得已，如果单台机器能搞定还要这么多系统干嘛？所以我们也要看到单点系统的好处，那就是一致性很容易保证，所以在**分布式系统中使用一个增强（能力和责任）的单点**既利于一致性的保证也能获得分布式的优势。

Leader全权负责管理日志复制，从而实现一致性，所以有了Leader这一机制，一致性问题就可以被分解为上述三大方面了，下面分别说明。

1. Raft 的 Leader 是有 Term 时间限制的，类似于[租约机制][6]，这个机制能完善单纯的心跳(因为有的机器太忙可能发不出或没法响应心跳)。
随机的选举超时时间可以使得 **Leader 选举**很少有选票平分的时候，按 `Term number` 最大和先来先服务原则可以使得每一个 Term 内最多有一个 Leader（如果没有 Leader 就会超时进入下一个 Term 进行新的选举）。Leader 保持身份并阻止其他节点成为 Leader 的方法是不停地向其他节点发送心跳消息（也包含需要复制的日志）。

2. Leader 为客户端服务，处理所有客户端请求亦即**所有的系统变更**，并把**日志复制**分发给其他节点（包含失败重试），leader 处理日志不一致的手段是强制follower 复制自己的日志，所以 follower 中与 leader 冲突的日志会被覆盖，leader 不删除自己的日志（只附加原则）。

3. leader选举和日志复制都需要一些**安全机制**来保证每个状态机都按照相同的顺序来执行相同的指令：
①. 选举限制，除了1中的条件，还要求 candidate 具有已经提交的所有日志条目，所以 voter 会主动拒绝日志没有自己新（通过Term Number 和 日志长度 两个指标进行比较）的候选人的投票请求。
②. 提交之前Term内的日志条目时，Leader 会使用这个条目的原始Term Number，而不是使用当前的Term Number，这样更容易辨别日志，而且要提交之前Term（如 2 ）的日志时必须同时提交当前Term（如 4）的日志，保证得到复制日志的 follower A 下次更有可能成为Leader而不是那些只有较旧日志但是新于A得到的旧日志（如 3 新于 2 ）的follower

如果 follower 或者 candidate 崩溃了，那么后续发送给他们的请求都会失败。Raft 中处理这种失败就是简单的通过无限的重试，因为Raft的这种请求都是幂等的，所以这样重试不会造成任何问题。比如，一个follower如果收到附加日志请求但是他已经包含了这一日志，那么他就会直接忽略这个新的请求。

Leader 选举是 Raft 中对时间要求最为关键的方面。只要系统满足下面的时间要求：

> 广播时间（broadcastTime） << 选举超时时间（electionTimeout） << 平均故障间隔时间（MTBF）

Raft 就可以选举并维持一个稳定的Leader。当**Leader崩溃后，整个系统会大约相当于选举超时的时间里不可用**，广播时间和平均故障间隔时间是由系统决定的，但是选举超时时间是我们自己选择的， Raft的请求 要接收方将信息持久到存储中去，所以广播时间大约是 0.5 毫秒到 20 毫秒，取决于存储的技术。因此，选举超时时间可能需要在 10 毫秒到 500 毫秒之间。大多数的服务器的平均故障间隔时间都在几个月甚至更长，很容易满足时间的需求。

集群状态切换通过一个**共同一致**（新老配置的结合）的中间状态转换实现，这样**基于两阶段**的做法可以使得集群平滑地进行状态迁移。

阅读原文：[Mageekchiu][7]

[1]: https://ramcloud.atlassian.net/wiki/download/attachments/6586375/raft.pdf
[2]: https://raft.github.io/
[3]: http://thesecretlivesofdata.com/raft/
[4]: https://github.com/maemual/raft-zh_cn
[5]: https://segmentfault.com/a/1190000013522687#articleHeader4
[6]: https://segmentfault.com/a/1190000014503967#articleHeader8
[7]: http://mageek.cn/archives/101/