1.raft协议
raft协议是一个共识算法，主要包括leader election，log replication，safety三个关键部分，另外还包括membership changes和snapshot。
1.1 复制状态机
复制状态机是分布式系统中解决fault tolerance问题的常用手段。raft通过log replication来保证集群的多个server，会有同样的数据输入到各自的状态机。如图1所示。
关键术语：
Apply：将entry输入到状态机
committed：entry可以被安全的Apply到状态机，一般情况下entry被同步到集群的大多数节点上时，就可以认为是committed（有特殊情况）。
每个server都有一个log，log中包含一系列的entry（entry中有相应的命令，即客户端请求），状态机按照log中的顺序执行这些命令。
如果每个server输入状态机的数据相同，状态机产生的结果也是相同的。因此共识算法的目的就是保证多个server的log一致。
leader上的consensus module接收到客户端的命令，将这些命令作为entry添加到log中，并且和其他follower上的consensus module通信，将log entry同步到其他follower，以确保多个server之间日志文件的最终一致。
当达到一定条件，即该条entry committed时，leader会将命令输入状态机，并将输出返回给客户端，同时通过心跳通知其他follower可以Apply该entry。
共识算法有以下特点：
1.safety，在所有非拜占庭条件下（包括网络延迟，分区，丢包，duplication，reordering等），不会返回错误的结果
2.大部分节点正常话，系统就可以正常工作
3.不依靠物理时钟来确保日志的一致，错误的物理时钟和消息延迟最多会造成可用性问题
4.集群中的大多数节点在一轮rpc调用中正常响应的话，一个客户端的请求就会被正常返回，不会受部分慢节点的影响
1.2 基本概念
任何时刻，一个server处于以下三个状态之一：leader，follower，candidate。
一般情况下，有1个leader，其他节点都是follower，follower是被动的，不会发送请求，只会响应leader和candidate的请求。
leader处理所有客户端的请求（如果客户端请求了follower，follower将请求重定向到leader）。
candidate状态用于选举一个新的leader，状态转换如下图
raft将物理时间分隔为一个个的任意长度的term，term是连续的。
每个term从election开始，一个或者多个candidate尝试竞选为leader，如果一个candidate赢得了选举，就会成为term的余下时间内的leader。
一些情况下，会产生split vote，term会以没有leader的状态结束，开始新一轮的term以及选举
raft确保一个term中最多只会有一个leader。
term是逻辑时钟，每个server存储一个current term number，current term number随着时间单调递增，当节点之间通信时，会交换current term number，
如果一个server发现自己的current term number小于其他节点的，该server会将自己的term更新为更大的term，
如果一个candidate或者leader发现有节点的term大于自己的term，就会转变为follower（有特殊情况），
如果一个节点接收到一个有着过期term number的请求，则会拒绝这个请求。
1.3. RPC
raft的server之间使用RPC通信，主要为两种类型的RPC，
RequestVote RPC：用于candidate选举
AppendEntries RPC：用于leader发送log entry给follower，或者心跳
另外还有一种InstallSnapshot RPC，用于传输snapshot
2. leader election
raft协议首先需要选举一个唯一的leader，leader接受客户端的命令，将这些命令复制到其他follower，通知follower什么时候可以将这些日志输入到状态机。data flow是单向的，从leader到follower。
raft使用心跳机制触发leader election，当一个server start up，起始状态是follower，只要收到leader和candidate的正确RPC请求，server就会保持follower的状态。
如果follower在一定时间内（election timeout）没有收到心跳，follower会认为当前没有leader，并开始竞选。
开始竞选时，follower增加自己的current term并将状态转换为candidate，然后会选举自己并发送RequestVote RPC请求给集群中的其他server。
一个candidate会保持自己的状态直到下面三种情况之一发生：
1.赢得选举
一个candidate在接收到集群中大多数节点对当前term的投票之后，赢得选举。每个server在一个term中，最多只会给一个candidate投票，first-come-first-served，
2.其他节点成为leader
如果candidate收到其他节点的RPC请求，而且请求中的term大于等于candidate的current term，candidate会认为已经选出leader，并返回到follower状态。
如果RPC请求中的term小于candidate的current term，candidate会拒绝该RPC请求。
3.一定时间内（election timeout）没有选举出leader
每个candidate都会time out，并且增加自己的term，开始新一轮的选举
election timeout是在一个固定范围内（例如150ms-300ms内）随机的
上述机制保证在一个term中，只有一个candidate会成为leader，当一个candidate成为leader，它会发送心跳信息给所有其他的节点。
3. log replication
当一个leader被选举出来之后，client发送请求给leader，leader将将请求作为一个新的entry添加到log中，然后并行的发送AppendEntries RPC请求（携带该entry）给follower。
leader判断当前是否可以安全地将entry apply到状态机中，此时该entry被叫做committed。然后leader将请求Apply到状态机，并返回执行结果。
log entry中会保存接受到entry时的term，以及一个用于标记log entry位置的index。
raft保证committed entries是持久化的，并最终会被所有的状态机执行。
当一个entry被leader replicate到集群中的大多数节点上时，该entry就是committed。
如果某条entry是committed的，该entry之前的entry也都是committed的，包括之前的leader创建的entry。
leader会记录committed的日志的最高index，并将该index包含在之后的AppendEntries RPC中（包括 heartbeats），
follower知道某个entry是committed，就会将该entry apply到状态机中。
AppendEntries Consistency Check:
当发送一个AppendEntries RPC，leader将新entries之前最近的log entry的index和term包含在RPC请求中。如果follower发现自己的log中没有该index和term的entry，就会拒绝新的entries。
类似于一个归纳的过程，最初的空的log满足Log Matching Property，当有新的log entry时，consistency check同样保证了新的log entry满足Log Matching Property。
这样，当AppendEntries请求返回成功的响应时，leader就知道follower的log在new entries之前的部分和自己的log一样。
一个新的leader被选举出来之后，follower的log可能和新的leader不一样，follower可能有leader没有的entry，也可能有老的leader没有commit的entry。
为了让follower的log和leader的完全一致，leader需要找到follower的log和自己的log分叉的地方，删除follower在分叉点之后的log entry，然后leader向follower发送自己在分叉点之后的log entry。
上述操作通过AppendEntries RPC来实现，leader会记录每个follower的nextIndex，即leader应该发送给这个follower的下一个log entry的index。
如果follower的log和leader的不一样，AppendEntries RPC会失败，leader减小nextIndex并重试。
如果需要，这个协议也可以优化，如果AppendEntries RPC失败，follower可以返回冲突的term，以及该term的第一个index。这样原来一个不同的entry就需要一个AppendEntries请求，现在一个term需要一个AppendEntries请求。
这样多个节点之间的日志就会收敛一致。同时，leader从不会覆盖或者删除自己的log entry，符合Leader Append-Only Property。
4.safety
election safety：一个term中最多只有一个leader
leader append-only：leader不会覆盖或者删除log中的entry，只会append新的entry到log中
log matching：如果2个log包含一个相同term和相同index的entry，那2个日志中在该index之前的entry都是相同的。
leader completeness：如果一个entry在某个term中committed，那么这个entry会出现在所有具有更高term的leader的log中
state machine safety：如果一个server apply了一个index为n的entry，其他server不会apply一个不同的entry，且这个entry的index也为n
上述部分并不能完全保证每个状态机以相同的顺序执行相同的命令。
例如，一个follower可能在当前leader commit一些log entry的时候不可用，然后该follower被选举为新的leader后，就可能覆盖之前committed的日志，从而造成不同的状态机执行了不同的命令。
下面讨论leader election的限制，这些限制能保证任何term的leader都会包含之前term中committed的log entry。
4.1 选举限制
RequestVote RPC请求包含candidate的log，如果voter的log比candidate的log更加up-to-date，voter会拒绝这次投票。
up-to-date：两个log，如果term不同，term更大的更新，如果term相同，日志更长的更新
4.2 commit之前term的log entry
一个leader不能立即判断出一个之前term的entry是否应该committed，即使该entry被存储到了大多数节点上。
（a）S1是leader，写入一条命令，index是2
（b）S1 crash，S5选举为leader，写入一条命令，index是3
（c）S5 crash，S1选举为leader，写入一条命令，index是4，并将index为2的log entry同步到S3，commit和apply index为2的log entry
（d）S1 crash，S5选举为leader，会覆盖掉index2，造成多个server的状态机apply不一样的log entry
因此，raft不会因为之前term的log entry被存储到了大多数节点上，就将该entry commit（raft never commits log entries from pervious terms by counting replicas），只有当前term的log entry被存储到大多数节点上时，才会判断该entry为commit
（only log entries from the leader's current term are committed by counting replicas）。这样，由于Log Matching Property，所有之前的entries都会间接地被commit掉。
5. Membership change
raft使用two-phase的方案来处理configuration change，集群首先会切换到一个名叫joint consensus的中间状态，一旦joint consensus被committed了，集群就会使用新的configuration。
joint consensus将老的和新的configuration结合在一起：
log entries会被同步到两个configuration的server中
两个configuration的server都可以被选举为leader
agreement（election或者entry commitment）分别需要两个configuration的大多数节点同意
集群configuration也是以log entry的方式存储和同步到其他server上。
当leader接收到configuration从C-old变为C-new的请求之后，将C-old,new的entry存储到log中，并同步到其他server上。
follower接收到entry后，无论该entry是否已经committed，都会使用entry包含的configuration替换当前的configuration。
如果leader crash，新的leader的configuration只可能是C-old或者C-old,new。
C-old,new被committed之后，leader创建一条C-new的entry，并同步到其他server上。
follower接收到该entry之后，无论该entry是否已经committed，都会使用C-new替换之前的configuration。
当C-new被committed之后，C-old中的节点就可以被shut down。
上述方案需要解决三个问题：
1.新加入的server需要很长时间才能追上leader，在这段时间内无法committed，为此raft引入了non-voting 成员
2.老的leader可能不在新的configuration中。为此，leader在C-new committed之后，leader需要变成follower
3.removed servers可能会影响集群。这些节点不会接收到心跳，然后time out，然后开始新一轮的选举。这会造成当前的leader变成follower，然后重新选举leader。上述过程会不断重复。
为此，server需要忽略RequestVote RPC，如果当前的leader没有time out。
6.Log compaction
snapshotting是log compacting的最简单的办法，状态机将当前系统状态被写进snapshot，之前的log entry会被删除。
每个server会独立的take snapshot，snapshot会包含log中已经committed的log entry。
snapshot中会包含少量的元数据，
last included index：状态机apply的最后一个log entry，也就是snapshot替换掉的最后一个log entry 的index。
last included term：上述entry的term
元数据用于snapshot之后的第一个log entry的AppendEntries consistency check，由于该entry需要之前的log的index和term。
元数据也包含最近的configuration。
对于一个刚加进集群的server，leader使用InstallSnapshot RPC发送snapshot给follower。
7. Client interaction
raft需要把所有的请求发送给leader，当一个client start，client连接集群中的任意一个节点，如果该节点不是leader，则会拒绝client的请求，并返回leader的信息（AppendEntries请求包含了leader的网络地址）。
如果leader crash，client请求会timeout，然后随机选择一个节点继续重试。
raft协议需要实现线性语义（linearizable semantics），每个操作会且只会执行一次（exactly once），但是仅靠之前提到的几点，raft协议的可能会让一个命令执行多次。
7.1
例如，leader在commit一个log entry，但是还没有来得及返回给client之后，就crash掉，client会在新的leader上重复发送相同的请求，造成该请求执行两次。
解决方法是client给每个命令一个序列号，状态机记录每个client最近执行的序列号。如果状态机收到一个命令，该命令的序列号是之前执行过的，就立即返回而不再执行该命令。
7.2
只读操作可能会读到过期的数据。因为client访问一个leader时，集群中选举出了其他leader，该leader马上就会变成follower。linear semantics不能返回过期数据。
raft的解决方案分两步，
首先，一个leader必须确认哪些entry是committed，Leader Completeness Property保证一个leader拥有所有committed的entry，但是在term的开始阶段，leader并不知道哪些是已经committed的。因此，leader需要在term的开始，先commit一个no-op entry。
然后，leader必须检查当前是否有其他leader被选举出来，将要取代自己的leader位置。raft在返回read-only请求的响应之前，需要和集群中的大多数节点发送心跳。
