Raft是一种分布式环境下的一致性算法，通过少数服从多数的选举来维护集群中数据的一致性。它类似于RBFT算法的名字，但是Raft算法中不能有拜占庭节点，而RBFT可以容忍BFT节点。Raft与paxos协议非常相似，但比paxos协议更容易理解(由于paxos协议难以具体实现，zookeeper参考paxos实现了自己的Zab算法)。同样，Raft也有一个用GO语言实现的etcd服务，与Zookeeper功能相同，在容器操作系统CoreOS中作为核心组件使用。 　　

　　

　　本文首先从整体上说明了算法的特点，然后详细描述了算法的实现。为了方便大家理解，本文还是以图解为主，没有过多的算法细节。Raft易于理解和实现，是我们入门分布式一致性算法的捷径！ 　　

　　

　　1.算法很好理解。Raft协议的性能并不比paxos的各种实现高。它的优点在于具有良好的可理解性和可操作性，并且很容易根据协议实现稳定、健壮的算法。作者在分别为本科生和研究生修完paxos和Raft协议课程后，在斯坦福和加州大学进行了测试。在总分60分的测试中，分数如下图所示： 　　

　　

　　 　　

　　

　　从上图可以看出，Raft协议(平均25.7)的得分明显高于paxos(平均20.8)。相信每个学过paxos算法的人都有这样的体验：经过一段时间的努力理解，我完全不记得细节了，至少对我自己来说是这样的。Raft协议很简洁清爽，这个测试也能反映问题。测试结束后，作者还发起了一个调查问卷，问学生这两种算法哪个更容易实现？哪个更容易理解？答案如下图所示： 　　

　　

　　 　　

　　

　　可以看出，这种主观问卷具有压倒性的优势：Raft是一种易于理解、易于实现的算法。 　　

　　

　　2.etcd性能测试数据筏的算法实现已经用多种语言实现，包括C、GO、Scala、Java等。(详情见https://raft.github.io/)，但最著名的实现是etcd，它作为CoreOS生态系统的重要组成部分而闻名。我们可以通过etcd的性能数据来看看Raft算法的实际性能。 　　

　　

　　测试集群由3台服务器组成，其配置如下： 　　

　　

　　Google compute engine 3机8VCPUS 16GB内存50GB SSD D1机(客户端)16VCPUS 30GB内存50GB SSD Ubuntu 17.04ETCD 3.2.0，GO 1.8.3下面分别测试读写性能。下表显示了写入性能数据： 　　

　　

　　密钥数量密钥大小(字节)值大小(字节)连接数客户端数量获取etcd服务器平均写入QPS每个请求的平均延迟仅平均服务器RSS10，000825611仅5831.6ms48 MB仅44，34122ms124MB100，00082561000所有成员50，10420m 126 MB 　　

　　

　　和读取性能数据如下表所示： 　　

　　

　　请求数以字节为单位的密钥大小以字节为单位的值大小连接数客户端数一致性平均读取QPS每个请求的平均延迟10，000825611可线性化1，3530.7m 10，000825611可串行化2，9090.3m 10，00082561001000可线性化141，5785.5m 10，00082561001000可串行化1 　　

　　

　　在读取性能数据时，线性化的一致性高于序列化，所以性能稍差。它的原始页面在这里：https://coreos.com/etcd/docs/latest/op-guide/performance.html. 　　

　　

　　其实在算法的正常运行上和paxos没什么区别。一旦领导下去，从发现到新领导连任，到新领导开始工作的时间是影响业绩的重要指标。在下图中，由五个节点组成的集群反复停止主节点并观察恢复时间。结果如下： 　　

tps://tupian.lamuhao.com/pic/img.php?k=raft数字切换,raft数字切换有什么用4.jpg">

　　

在上图中有以下几个关注点：

　　

不同颜色及线条代表着follower的定时器。如在300ms内没有收到leader的心跳，则发起选举。其中150-300ms这样的数据表明，这5台follower的定时器分布在150ms到300ms之间，呈现随机化。而150-150ms表示没有随机化，所有节点的超时时间是一样的。横坐标代表着发现到替换掉宕机leader开始服务的时间。数值的单位为毫秒。纵坐标表示测试时间在全部测试数据中的比例。以上每条线都做了1000次试验（除150-150ms只试验了100次）。上图表明，增加随机化后，可以大幅减少选举的平均用时。下面的图表明，通过降低最短的超时时间，也可以减少宕机时间。Raft推荐的时间为150-300ms。

　　

3、Raft算法概述复杂的问题可以通过分解为多个简单的子问题来解决，Raft正是如此（paxos很难分解）。Raft首先定义自己是一个key/value数据库。那么，请求就分为读和写。Raft将问题分解为以下几个要点：

　　

集群里有一台为leader节点服务器，且读写请求都只能向该节点发送，以此保证一致性；当集群内没有leader节点时，leader节点被多数节点选出来。比如集群有3个节点，那么2个节点同意的话，就可以选出1个作为leader；除leader节点外，其他节点叫做follower追随者。leader节点向follower节点同步每条写请求；因此Raft将一致性问题转换为leader的选举上，以及leader与follower之间的数据同步。我们先来谈leader与 follower之间的数据同步问题。每一次写请求会修改数据，读请求则不会，所以把leader收到的写请求当作一次操作日志记录下来，且同时把操作日志同步给所有的follower节点，而有一个最终状态数据库记录某一个key的最终值，如下图所示（事实上这与fabric区块链里，多条交易日志构成的世界状态数据库非常相似）：

　　

　　

上图中其步骤含义如下：

　　

leader收到写请求y=9，此时状态数据库是y=1；将y=9这条日志追加到Log的末尾，同时将该条日志同步给其他follower；当多数follower成功收到这条y=9的日志后，leader将状态数据库从y=1更新为y=9；返回client表示y=9设置成功。4、如何选举出leader当一个集群刚启动时，所有的节点都是follower，follower只能被动的接收leader的消息并响应。此时经过一段时间若follower节点发现全集群没有leader，开始把自己作为leader的候选人向大家征询投票，此时该节点叫做Candidate候选人。若多数follower节点同意后，则升级为leader节点。而leader节点有义务定时心跳通知所有的 follower节点，使follower节点知道此时集群中的leader是谁。如下图所示：

　　

　　

上图的状态变迁里，follower在一个随机定时器（例如150ms到300ms之间）内没有收到leader的心跳，则开始发起选举，而候选人就是自己，所以自己转化为Candidate，且自己首先投自己一票。若在投票未完成时，发现新的leader出现，则取消投票，由candidate转换为follower。

　　

每次选举是一个任期，这个任期叫做term。每次任期有一个任期号，它是全局的、递增的，当网络中断时虽然会暂时不一致，但网络畅通后会很快同步，如下图所示：

　　

　　

如上图中，蓝色是选举期，绿色是产生leader后。如果不出现意外，这个leader会一直当下云，所以term周期会很长。出现宕机或者网络波动时，重新选举于是出现term2。在term3时也可能一直选举不出新的leader，此时很可能多个candidate发起了投票，票数被平摊后谁也没拿到大多数（由于每台follower的定时器时间是随机的，因此该情况发生概率很小，且发生后也能很快回归正常）。于是会进入term4。

　　

5、操作日志的同步leader需要把写日志同步到大多数follower后才能更新状态数据库，并向client回复写成功。如果没有得到多数follower的成功应答，leader会重复发送这条日志更新请求。下图中有8条日志3个任期5个节点，每条日志里除记录了操作行为外还记录了当时的任期：

　　

　　

上图中，绿色是第一个任期，其中3条日志条目中第3条日志y=9没有被第4个节点接收到。黄色是第2个任期。绿色与黄色任期内，所有的日志皆被多数节点收到，因此都是写入状态数据库的，这些日志的状态都是commited已提交状态。蓝色是第3个任期，其第8条日志x=4没有被多数节点收到，因此该日志不是committed状态。

　　

leader与 follower之间的日志也可能存在不一致的情况，follower或者少了一些日志，或者多了一些日志，如下图所示：

　　

　　

上图中最上面一行是leader的日志，而follower的日志存在以下情况：

　　

a、b表示follower相比leader少了几条日志；c、d表示follower相比leader多了几条日志；e、f表示同时少了一些日志，又多了一些日志。比如f情况就是这台follower在任期2时被选为leader，刚添加3条日志还没有提交呢就宕机了，重启后被选为leader，又迅速收到5个写请求加了5条日志，还没提交又宕机了，此时再启动作为follower存在时的状态就是上图f的状态。leader如果确定多数机器收到日志，自然可以提交。如果新leader刚被选出来，它会试图把多数机器上保存的日志（即使它自己没有这条日志）–也就是前任的日志也提交，但这未必保证一定成功，如下图所示：

　　

　　

在上图中，d和e就是提交前任日志努力下可能导致的两种状况：

　　

在a中，S1是leader，前写入日志2并只同步日志到S1和S2，还未到其他节点时就宕机了；在b中，S5通过它自己、S3、S4的投票被选为leader，因此它并不知道日志2的存在。此时它收到client的新请求写入日志3，而刚写入日志3就宕机了；在c中，S1重新被选为leader，此时它发现日志2还未被复制到多数follower，开始复制日志2。此时S1收到新请求，并记录了日志4；在d中是第一种场景，此时老的日志2被复制到了S3上，然而此时的日志2虽然被S1、S2、S3多数节点持有，但却是通过2次任期完成的，且新任期里的日志4并未被复制到多数机器上，所以日志2并不能认定可以处于commited状态。若此时S1宕机，S5重新当选，则日志2会被覆盖丢弃，当然也包括未被复制到多数机器的日志4；在e中是接着c的第二种场景，若日志4也被复制到S1、S2、S3这多数机器上，则日志2与日志3同时处于commited状态，永远不会被覆盖。6、集群规模的配置变化通常我们把raft集群配置为3或者5个节点，特别是5个节点时可以容忍2个节点宕机。这给我们平滑升级时带来了好处：1台台升级时仍然可以容忍1台宕机。但若我们的集群原来是3个节点的组合，却改为5个节点，如果这个过程是不停止服务动态完成的，这可能出现问题，如下图所示：

　　

　　

　　

在上图中，绿色的老配置只有1、2、3这三台server组成集群，而在蓝色的新配置里则在1、2、3、4、5这五台server组成的新集群。于是，存在红色箭头指标的点，在该点上，可能1、2这两台server根据老配置在它们2个中选出第1个leader，而3、4、5根据新配置在它们3个中选出了第2个leader。同一时刻出现了2个leader，这样数据就会不一致。

　　

为了解决上述问题，Raft提出了一个共同一致状态，该状态处于老配置和新配置生效的中间阶段。首先，我们设C(old)为老配置，而新配置为C(new)，欲从C(old)状态置C(new)，必须经历C(old,new)状态。其中，更新到C(old,new)以及C(new)时，仍然以复制日志的方式进行，即：先进行日志复制，当确定多数节点收到该日志后，则该日志为commited已提交状态。如下图所示：

　　

　　

从上图中可以看到：

　　

在C(old,new)日志开始复制时，仍然仅使用C(old)这一种配置，所以不会出现双leader；而C(old,new)一旦进入commited提交状态，此时若leader宕机重新选举，则要求必须是具备C(old,new)的candidate才能被选为新leader；之后，leader开始复制日志C(new)，从这一刻起leader的新配置开始生效。7、日志的优化可以看到，Raft算法的核心就是leader选举以及日志复制。而日志的无限增长，必然带来性能问题，这是从工程角度必须解决的问题。日志表示的是过程，状态数据库表示的是结果；同样，我们可以定期把某一时间点之前的日志做成状态数据库，或者称为快照，仅保留该时间点后的日志，这样就可以大幅减少日志的数量。如下图所示：

　　

　　

在上图中，原先的已经被提交的5条日志最终导致的状态是x=0&&y=9，故可以被快照替代，这便减少了日志量。

　　

8、小结Raft还有一个非常形象的算法演示动画，包含了一致性算法的由来、leader的选举、隔离网络下的leader选举、日志的复制等场景，请打开RaftUnderstandable Distributed Consensus链接观看。

　　

学习Raft算法有助于我们理解分布式环境下的一致性解决方案，而且它确实比paxos好理解许多，可以作为我们的入门算法。