最近看了Ongaro在2014年的博士论文《CONSENSUS: BRIDGING THEORY AND PRACTICE》的部分章节，对raft有了初步的理解。其中论文中提到用于教学的user study，个人感觉非常不错，言简意赅，特此分享出来。本文基本与原讲解一致，又加上了笔者的一点理解。
资源来源于Ongaro和Ousterhout在youtube上的分享（http://youtu.be/YbZ3zDzDnrw），共有31个slide，因篇幅字数限制分为上下：
slide 1：
John Ousterhout,对分布式一致性算法Raft进行简单介绍。
slide 2：
Raft的总体目标是将log完全一样地复制到集群中的所有机器上，用来创建所谓的Replicated State Machine(多副本状态机，就是具有多个copy的应用程序)。
设想你有一个程序或应用，你想让它非常可靠，其中一个办法就是，在多个机器上同时运行这同一个程序，并且保证完全一样地运行，这就是replicated state machine的思想。state machine是个抽象概念，就是指一个程序或应用，能接收请求，并能输出结果（可以理解为有输入能输出的程序黑盒子）。（注意state machine指的是一个具体的应用程序，不是通常理解的机器；server才是指的通常的机器或实例。）
引入log这个概念，有助于使这些state machines执行完全一样的命令。下面解释下运作过程：如果一个客户端，想执行一个command（命令，指令，指的是具体的某个操作请求），那么它可以请求其中一台state machine，这台machine就把这个命令，如command X，记录到自己的本地日志log中，另外还要把command X传递给其他所有machines；其他machine也在各自的log中记录下这条命令；一旦这条command X被safely replicated(安全地复制)到所有machine的所有log中，那么这个command X就可以被传递给各个machine开始执行，一旦有machine执行完成命令X，就会把结果返回给客户端。
（大家注意这个过程：收到请求command->记录本地log->将log复制到其他machine->一旦认为log被安全地复制完成->才允许各个machine开始执行command->一旦有machine执行完成command->即把command的执行结果返回给客户端。这也就意味着不是所有请求command都能被最终执行，只有那些“安全地复制”完成的，才允许执行。特别注意理解什么叫安全地复制完成，直觉理解就是只要复制完成，就是最终状态，不允许再反悔再更改；我理解是两点，一是复制必须持久化，如写磁盘；二是必须复制到集群中大多数machine，得到大多数的承认；）
所以可以看到，只要所有log和machine都完全一样，且所有不同server（机器）上的所有state machine都按照完全一样的顺序执行log中的相同命令，那么所有machine必定输出完全一样的结果。（大家注意下这个推理过程：1 所有机器上都部署相同的machine应用；2 因为log是复制过去的，安全地复制保证了所有机器上的所有machine的log都完全一样；3 所有机器上的所有machine都按照log中的相同顺序执行命令；4 log是相同的，log中相同位置的命令也是相同的；5 所有机器上的所有machine都一样，执行的命令也一样，输出的结果也必定完全一样。其实这里还有个隐含条件，就是machine应用必须是deterministic的，即确定性的，由输入必定能推出唯一的输出，不能带有随机性模糊性；其实跟我们通常理解的应用是一致的；）
Consensus Module（一致性模块，图中有标注，是machine里的一个协调控制模块）的工作职责是管理这些logs，确保被合理地复制，并决定什么时候将这些logs中的command提交给state machine执行（其实consensus module就是一个协调模块，相当于整个系统的大脑，是整个算法的控制核心）；之所以叫consensus based算法，是因为我们并不要求所有机器都是一直在线并运行良好。事实上为了保证效率，只要求大多数机器在线，并能互相通信即可。（consensus在英文中的本意是共识、一致意见、大多数人的意见）比如，一个集群中3台机器，可以容忍1台机器故障，只要有2台在线即可；再比如5台机器的集群，可以容忍2台机器故障，只要3台在线即可。这里简要说下我们的系统能处理的异常：机器可以crash，可以停止运行，可以暂停运行再过段时间恢复，但要求运行的时候必须正常（意思是你可以罢工，但你在岗的时候干活儿必须正确）；因此我们不能处理Byzantine failures（拜占庭将军问题，指的是恶意篡改数据这类行为）；我们也允许网络中断、消息丢失、消息延迟、消息传递乱序、网络分化等。（意思就是我们正常分布式环境中会遇到的网络问题、消息丢失延迟等问题，raft都能应对；唯一不能处理的就是恶意篡改数据这类，比如受到恶意网络攻击、或者你恶意篡改磁盘中的log日志等这类非正常行为）。
slide 3：
实现一致性算法有两种可能方式：
1）第一种叫对称式，或无leader：这种方式中所有server的角色完全一样，权利也一样，在任意时刻的行为也基本一样，所有server都是对等的；客户端可以请求任意一台server，将command写入log中，并复制到其他server（其实就是完全平等制、无政府主义）；
2）第二种叫非对称式，或leader-based：在任意时间各个server都是不平等的，某个时刻只有一个server是leader，管理集群中的所有操作；其他server都是被统治的，只能简单按照leader的旨意干活；在这类系统中，客户端只能与leader通信，也只有leader能与其他server交流（其实就是专制独裁统治，只有一个leader，可以为所欲为，其他所有人都必须听命于leader，只有leader能对外交流）；
raft采用的就是第二种leader-based的方式，并且把一致性问题分解为两个不同问题：一是在有leader的情况下集群如何正常运作，二是leader挂掉之后如何选举更换leader。raft采用的这种leader-based方式的优势是使得正常运作过程非常简单，因为你不需要担心多个leader同时指挥导致的冲突，记住只有一个leader，leader可以为所欲为；raft算法的所有复杂性其实都来自于leader变更，这是因为旧leader忽然挂掉，可能导致整个系统处于不一致的状态，新leader上任后必须收拾残局。（后面大家会有切身体会，raft正常的运行过程非常简单，但是leader变更过程非常复杂）
通常来讲，有leader的系统比无leader的系统效率更高，原因很简单，你不需要担心多个server之间的冲突，你只需要额外处理下leader变更流程；（独裁不一定是坏事，效率更高！）
slide 4：
raft讲解提纲，共6个部分：
1、leader选举：如何从多个server中挑选一台作为leader；当leader挂掉之后，如何感知到，并挑选出新的leader来替换旧leader；
2、正常运行（最基本的log复制过程）：leader从客户端收到请求后如何将log复制到其他机器；这其实是整个raft算法中最简单的部分；
3、leader变更过程中的安全性和一致性：leader变更是raft中最难的，也是最关键的；首先会讲下safety到底意味着什么，以及如何保证safety；接着讲新leader上任后如何处理log，使得整个系统恢复一致性状态；
4、neutralize 旧leader：这是leader变更中的另一个问题，就是旧leader并没有真的死掉，死灰复燃，重新恢复之后，我们该如何处理；
5、客户端交互：客户端如何与整个系统交互？关键点是请求过程中server挂掉了client怎么办？如何实现linearizable semantics（线性化语义），即每个客户端命令只能执行一次（once and exactly once，其实就是防止出现多次执行出问题，类似于幂等性概念）;
6、配置变更：如何在集群中新增、或删除机器？
slide 5：
开始讲解6个部分之前，先从整体上说下系统中的server状态：
在任意时刻，系统中的任意一个server，只能是以下3种状态中的一种：
1）leader：同一时刻至多只能由一个server处于leader状态，处理所有的客户端交互、日志复制等；（同一时刻至多一个，意思是要么一个leader，要么没leader）
2）follower：大部分时候集群中的绝大部分server都是follower的状态，这些server是完全被动的状态，即不能主动发出请求，只能响应来自其他server的请求；（意思就是不能主动问别人，只能别人问了你回答；don't ask me! I ask you, you answer only!）
3）candidate：这是一个从follower到leader之间的中间状态；只是leader选举过程的一个临时状态；
正常情况下的集群状态应该是：1个leader，其他所有都是follower。
上图的下半部分展示了server状态的变迁过程：
1）follower想成为leader，必须先变成candidate，然后发起选举投票；如果投票不足，仍回到follower状态；如果投票过半，变成leader；
2）leader故障恢复后发现已经有新leader了，则自动下台，进入follower状态；
slide 6：
时间被划分成一个个的term（这里的term，还有zookeeper中的epoch，都是同一个意思，指的就是任期、时期、年代；指的是某一个leader的统治时期），每个term都有一个number，这个number必须单向递增且从未被用过；
每个term时期，分两部分，一是为这个term选举leader的过程，二是一旦选举成功，这个leader在这个term的剩余时间内作为leader管理整个系统；
可见，raft保证一个term内只有一个server可以被选举成leader；但有些term内可能没有选出leader，如上图的term 3，这意味着candidate没有获得过半投票，选举流产；一旦出现这种情况，系统立即进入新的term时期，开始新的一轮选举。
（认真理解下这里，并不是leader选举成功，才进入新term；而是旧leader一挂，就进入新term；新term一开始必须进行选举，选举成功则leader登基开始执政；选举不成功则立即进入新的term，开始新的一轮；）
每个term内至多有一个leader；有些term没有leader，意味着选举失败，没有选出leader；
raft中的每个server必须保存current term值（当前年代、当前任期号），这个值是当前server所认为的（best guess，为什么说是guess，是因为有时候比如server断网又恢复了，它其实是不知道当前term的，只能猜测现在还处于之前的term中，而这个猜测不一定是对的）当前系统所处于的term；这个term值必须被可靠地存储在磁盘中，以保证server宕机重启之后该值不丢失。
term的作用非常重要，其核心作用是让raft能够及时识别过期信息，比如某个认为当前term是2的server跟另外一个认为当前term是3的server进行通讯，我们就知道前一个server的信息是过时的；我们总是使用最新term的信息；后面的讲解中有几种场景，大家可以看到term用来检测并去除过期信息。
（term这种类似概念，在所有分布式一致性算法中都非常重要；其理念类似于抢夺式锁，用于解决不同term信息的冲突；我们的系统认为来自于更大term的信息一定是更准确的，总是采纳来自于最新term的信息；类似于新人胜旧人，后人总是比前人聪明）
slide 7：
上图是整个raft算法的总结，这里不详细说。
简要说下图中展示的几点：
1）各个角色的行为过程：参见follower、candidate和leader下面的描述；
2）需要持久化到磁盘上的状态数据（Persistent Satate）、log中每条数据的格式；
3）各个server之间如何交互：raft中所有server之间的通信都是RPC调用，并且只有两种类型的RPC调用：第一种是RequestVote，用于选举leader；第二种是AppendEntries，用于normal operations中leader向其他机器复制log；
现在不详细说了，等整个讲完之后，需要反复回顾这里。
slide 8：
现在开始讲解算法的第一部分，选举过程，raft必须保证在任意时刻，集群中至多只有一个server充当leader。
下面说下启动过程：
1）当整个系统启动的时候，所有的server都是follower状态；
2）回忆我们之前所说的，follower是完全被动的，它不会主动尝试联系其他server，只能被动响应来自其他server的信息；但是follower为了保持在自身的follower状态，它必须要相信集群中存在一个leader；而follower唯一可能的通信方式就是接收来自leader或candidate的请求；
3）leader为了保持自身的权威，必须不停地向集群中其他所有server发送心跳包；而在raft中，心跳信息非常简单，就是不带数据的AppendEntries RPC请求；
4）如果过了一段时间，某个follow还一直没收到任何RPC请求，那么它就会认为集群中已经没有可用的leader了，它就会发起选举过程，争取自己当leader；follow的等待时间，就叫election timeout（选举超时），一般是100-500ms；
因此，集群启动时候，所有server都是follower，并没有leader，所有的server都一直等待，直到election timeout，然后所有server都开始竞选leader；
（感性认识+直觉：leader为了保持自己的权威地位，必须不停发心跳；一旦某个follower在election timeout内没收到心跳，就自认为leader已挂，自己翻身开始竞选leader；类似于皇帝通过发心跳来压制子民，一旦某人收不到心跳包，就起身造反，但造反不一定能成功）
slide 9：
下面讲解选举过程到底是怎样的：
1）当一个server开始竞选leader，第一件事就是增大current term值；所用的这个current term值必须比系统中所有之前的term值都大；（此处注意，之前说current term值必须是单向递增，更准确地说是必须全局单向递增；即是对所有server而言的，新term值必须比集群中所有server的已有term值都大）
2）为了进行竞选，这个follower必须先转变到candidate状态；在candidate状态中，该server只有一个目标，就是争取自己当leader；为了当leader，它必须要争取到大多数投票；
3）先投自己一票；（不想当leader的follower不是好的follower；迫切想当，先投自己一票，这就叫自信！）
4）发送RequestVote RPC请求到其他所有server，典型场景下是并发同时发送请求的；如果请求发送出去之后没有响应，就会不断重试，一直发，直到出现下面三种情况之一：
a.该candidate得到大多数server的投票：这是我们最希望出现的情况，也是绝大部分情况下会出现的情况；一旦投票过半，则该candidate立即变成leader状态，且同时立即向其他所有follower发送心跳包；（发送心跳包是为了宣告天下，保持自己的权威地位）
b.该candidate收到了来自leader的RPC请求：这说明有其他candidate在同时跟自己竞选leader，并且已经竞选成功（注意可以同时有多个candidate同时竞选）；一旦发现已有leader，则该candidate立即回到follower状态，接收来自leader的请求，并被动响应。（一旦竞选失败，立即俯首称臣）
c.过了election timeout的时间，以上两种情况都没发生：这说明在这段时间内没有选出任何leader，自己没当选，别人也没当选；在多个server同时变成candidate，同时竞选的时候很容易出现这种情况，因为很可能导致投票分裂，而没有一个candidate获得过半投票；这个时候，处理很简单，即回到步骤1）中，增加当前current time值，开始新一轮的竞选；
slide 10：
选举过程中必须保证两大特性（图中cont'd是continued的意思，表示接着上一个slide继续）：
1）safety：安全性，意思是说在任意一个给定的term内，最多只允许一个server获胜成为leader；为了保证这一点，需要两个条件：
a.任意一个server在一个term内只能投出一票；一旦已经投给了一个candidate，它必须拒绝其他candidate的投票请求；其实server根本不在意把票投给谁，它只会把票投给最先到请求到它的candidate；为了保证这一点，必须把投票信息持久保存到磁盘上，这样可以保证即使该server投完票后宕机，稍后又立即重启了，也不会在同一个term内给第二个candidate投票了。
b.只有获得大多数投票才能获胜
结合a,b：一个server在同一个term内只能投一票，一个candidate为了获胜必须获得过半投票，显而易见，在同一个term内不可能有两个candidate同时当选；一旦有candidate获得大多数投票，其他candidate不可能再获得过半投票了；不同term内，当然可以有不同的candidate获胜，但同一个term内，只可能有一个获胜；
2）liveness：为了保证系统能向前运行，我们要确保不能一直都是无leader状态，必须要能最终选出一个leader；
问题的关键就是我们要确保不要总是出现splited vote（投票分散），即我们不要让多个candidate总是同时开始竞选，这很容易使投票分散；同时开始竞选，然后投票分散，无法形成大多数一直，然后等待超时，然后再同时开始竞选，这成了一个恶性循环；
raft的解决办法很简单，即使得election timeout分散开来，不要让所有server的election timeout都相同，而是在T到2T之间随机选择超时时间（T就是election timeout，这个值通常要比系统中最快的机器的超时时间短）；每个server每次都用随机方法计算出超时时间；通过把timeout分散开来，每次取值不一样，这样不太可能还会出现两个server同时超时然后同时开始竞选的情况；总有机器最先超时，然后有充足时间在其他server也超时之前发起投票、赢得选举；这种办法在T远大于broadcast time（传播时间，指的是server发起投票、收到投票所花时间）的情况下效果尤其明显；
（点评：safety其实是保证系统一致性运行的最低要求，其核心是cannot do something bad，即不能干坏事、不能做错事；liveness其实是更高要求，意味着不能只是不干坏事，也不能一直不干事，you must do something good，即必须使得整个系统能良好运转下去；因为如果一直处于无leader状态，其实系统是不能对外提供服务的；liveness本意就是活性、生存性，在java并发编程中也有该概念，定义如A concurrent application's ability to execute in a timely manner is known as its liveness.总结来说，liveness说的是应用程序运行及时性的能力，核心在于要“及时”执行，即在通常认为的合理时间内要能执行。）
slide 11：
下面开始讲第二部分，即leader选举成功之后的normal operation过程中，leader如何复制log entries到其他机器，先说一下log：
1）每个server都会保存一份自己私有的log：leader有，各个followers也都有；这些log保存在各自的机器上，只供自己操作；
2）log由entry组成，每个entry都有一个index，用来标记该entry在log中的位置；（就是数组与元素的关系）
3）每个entry内包含两个东西：
a. command：即可以在state machine上执行的具体指令；指令的格式是由客户端和state machine协商制定的，consensus module毫不关心，你可以把它想象成是某个方法和对应的参数；
b. term number：标识该条entry在哪个leader的term内被创建；之前已经说了term是全局单向递增的，在一个log内，term当然更是单向递增（increase monotonically）的；
4）log必须被持久可靠地保存，即log必须保存在磁盘等可靠的存储介质中；另外，server每次收到有log的变更请求，server必须操作完成，并确保log被安全保存之后才再返回请求；
5）如果某个entry在集群中大多数server中都有，那么我们认为这条entry是committed的（已提交的）；这一点在raft系统非常重要；一旦某条entry被committed，这意味着这条entry可以被安全地交给state machine去执行；raft保证entry是持久存储的，并最终被集群中的所有机器都执行；
如图所示，图中entry 7是committed，且其之前的1-6也都是committed的，而entry 8不是；
提醒一点：过半即是提交，这个定义并不精确，后面会稍作修改。（现在你可以暂时认为committed就是指的过半，后面会看到还会加一点额外限制条件，用于解决server变化时候的log一致性问题）
（点评：committed在所有分布式系统中都是一个重要概念，意味着某条数据已经得到集体中的大多数个体的认同，且是持久认同；某条命令一旦被committed（得到过半认同），就会被执行，并能保证最终系统中的所有机器都要执行，包括最初没有认同的那些机器；这类似于集体决议，一旦通过，必须执行，并最终在所有个体上都得到执行；回想分布式系统的设计初衷，即是要保证所有machine最终都执行完全一样的操作，并保持完全一致的状态；过半即提交，只是实现最终一致性目的的一种安全而高效的策略而已）
slide 12：
normal operation过程非常简单：
1）客户端向leader发送command请求；
2）leader将command存入自己的log中；
3）leader向所有follower发送AppendEntries RPC请求；典型场景下leader是并发请求的，即会同时向所有follower发送相同的请求，并等待接收响应结果；
4）一旦leader接收到足够多的响应，即至少一半（加上自己刚好过半，形成大多数），即认为这条entry已经被committed，则认为可以安全地执行这条command了（回忆前面说的，过半即提交，提交即可执行）：
a. leader一旦认为某条entry已committed，则将对应的command传给它的state machine执行，执行完成之后返回结果给client；
b. leader一旦认为某条entry已committed，则会通知其他所有follower；即通过发送AppendEntries请求通知其他所有follower这条entry已经被committed了；最终集群中所有机器都知道这条entry已经被提交了；
c. 一旦followers知道这条entry已经被提交了，也会将对应的command传递给自己的state machine执行；
（再次总结下这个过程：client请求leader-》leader在本地log中写入entry-》leader向所有followers广播entry-》leader收到过半响应，认为已提交-》leader执行对应命令，返回结果-》同时leader向所有followers广播提交信息-》其他follower获知已提交则也执行对应命令。可见，最终所有server都会执行该请求，但client不会等到所有server执行完，只需等到leader执行完即可；但执行是有条件的，即log必须复制到过半server上才能开始执行；如果给定时间内仍复制不到过半server，则本次请求失败，客户端必须发起重试；）
注意几点：
1）如果在这个过程中，某个follower挂掉了（crashed）或对leader的RPC请求响应特别慢，会怎么样？
leader会一直不断地重试、重试，直到请求成功；即使follower宕机了，重启后leader仍会接着发请求，直到请求成功；
需要注意的是，leader并不需要等待所有follower都响应，只需要收到大多数server的响应以确保log被复制到大多数server即可；
因此在通常情况下，性能很好。因为为了完成client请求，并不需要等待所有server，只需要等到集群中过半的server响应即可；其实就是集群中运行最快的那部分server；一旦有过半的server响应，leader即可立即执行命令，并返回结果给client；
这意味着集群中个别机器慢或出问题，不会导致整个系统变慢，因为leader根本不需要等待那些server；
（注意：有请求进来，leader只需等到大多数机器有响应即可执行命令并返回结果；leader不需要等待所有机器有响应才执行命令，但是leader需要不断发请求给所有机器，以确保最终所有机器都有响应，并执行相同的命令；这是不矛盾的；）
slide 13：
raft尽量保证不同server上的log具有高度的一致性；最理想的情况当然是任何时候所有server上的log都完全一样；当然，这是做不到的，因为总有机器可能会宕机；但是raft还是会尽可能地保证log的一致性，上图列出的，就是raft能够保证的、在任何时候都成立的一致性承诺：
1）index和term组合起来唯一标识一条entry，即不同server上只要某条entry的index和term相同，则这条entry完全相同（类似于联合索引的概念）：
a.entry完全相同意思是它们存储的command一样；
b.另外，这条entry所有之前的entry也都完全相同；（例如发现server1和server2在第7个位置的entry 7相同，则之前的entry1到entry6也一定都完全相同；先记住，后面会加其他限制来保证这一点，且会有归纳证明；）
因此，结合a b，得出进一步结论：index和term组合起来唯一标识从开始到index位置的整条log；（这是一个更强的结论，意味着不仅当前一致，历史也一致）
2）如果某条entry已被committed，则其之前所有的entries也一定已被committed：
这一点可以从1）推导出来，如发现entry 7已提交，则意味着entry 7在大多数server上都存在；则根据1）可知，entry1到entry6在那些机器上也一定存在，而那些机器已构成大多数，所以entry1到entry6也一定已被提交；
（点评：这两点非常重要，贯穿整个后续的讲解；最核心的就是：index和term唯一标识一条entry；其他结论都可据此推导出；一言以蔽之，就是两句话：a.只要发现某两个log中的某个entry的index和term都相同，则这两条log中这条entry包括之前的所有entries都相同 b.只要在某条log中发现某个entry已提交，则这条entry之前的所有entries也一定已提交）
slide 14：
上一个slide提到的log之间的一致性，即两条entry的index和term相同，则其之前的entries也都相同；这个并不是显而易见的，需要额外加限制条件来实现，就是通过AppendEntries Consistency Check：
1）当leader向follower发送AppendEntries RPC请求的时候，除了要发送新的log entry之外，还要额外带上两个值：即新entry的前一个entry的index和term；
2）follower收到AppendEntries 请求时，必须先判断自己的log中是否已有相同的entry（即是否存在entry与请求中的index和term相同），只有匹配上了才会接受新的entry；如果不匹配，直接拒绝；
如图中示例1，leader发送新的entry 5和前面之前entry的index和entry，即（4,2）给follower，follower发现自己的log中有（4,2）这条entry，所以接收新的entry 5；图中示例2，leader发送新的entry 5和紧挨着前一个entry的index和term，即（4,2）给follower，follower发现自己没有（4,2）这个entry，自己在第4个位置的entry的term是1，不是2，所以直接拒绝，leader请求失败；
3）注意2）中的consistency check非常重要，显而易见，这其实是个归纳推理过程：每次接受新entry的时候，都必须要求前一个entry必须匹配；以此类推，才能得出前一个slide里面的结论：一旦两条entry相同，则这条entry之前的所有entries也必定相同，也只有如此才能保证log的一致性。
换言之，一旦某个follower接收了某条entry，则意味着这个follower的log中从起始位置到这条entry为止的所有entries都跟leader的完全匹配；
至此，normal operation过程讲解结束。
（点评：entry是整个raft的基石，需要认真理解；先想一想，一个entry中到底有什么东西？如图所示，entry中有term和command，只有这两个信息；而index并不是entry中的信息，而是entry的属性，即用来标记该entry在log中的位置。那为什么之前说如果两个entry的index和term相同，则两个entry也相同（即command相同）呢？follower的log里的entry都是来自leader，而term相同，说明是来自同一个leader；而同一个leader发送的某个index位置的entry都是完全相同的；）
