正文
最近在学习分布式相关的知识，正好看到了raft算法，在此记录一下自己的学习笔记。raft是工程上使用较为广泛的强一致性、去中心化、高可用的分布式协议。说到raft，还有一个不得不提的算法，Paxos。但是Paxos理解起来很难，然后自己对这方面还是积累未深，所以决定从raft开始学起。
raft是一个共识算法(consensus algorithm)，用于分布式系统当中，实现多个节点的统一性，强一致性，并且保证高可用。在分布式系统中，强调高可用，无他办法，只有多备份；那么在多备份的情况下，就需要用到共识算法来保证系统的强统一性，容错性。raft算法就是这么一种leader-based的共识算法，与之相对应的是leaderless算法。
raft算法概括
Raft is a consensus algorithm for managing a replicated log. It produces a result equivalent to (multi-)Paxos, and it is as efficient as Paxos, but its structure is different from Paxos; this makes Raft more understandable than Paxos and also provides a better foundation for building practical systems.
raft算法的头号目标，是更易于理解(more understandable)，为了达到这个目标，raft将一致性分解成多个子问题：Leader Election、Log replication、Safety、Log compaction、Membership change等。同时，raft使用了更强的假设来减少所需考虑的情况，使之变的易于理解和实现。
Raft将系统中的角色分为Leader、Follower、Candidate三种，
- Leader：接受客户端请求，并和Follower同步请求日志，当日志同步到大多数节点上后告知Follower同步日志；
- Follower：接受并持久化Leader的日志；
- Candidate：Leader Election过程中临时的角色；
Raft算法的角色状态转移图：
可以看出来，所有的节点从开始时都是Follower状态，在一段时间内（heartbeat timeout）如果没有收到来自Leader的心跳，则从Follower切换至Candidate状态，开始一轮选举；如果收到majority的选票（包含自身的一票）则切换到Leader的状态；如果发现存在当前Leader或者更新的term，则自动却换到Follower状态。简言之，在任意一个term中，有且仅有一个Leader，正常的工作期间只有Leader和Followers两种角色。Leader会不断给Follower发送心跳信息，表明自己的存活状态；如果Leader故障，那么Follower就会转换成Candidate，重新选举出新Leader。
Term
每一次选举加上Leader任期的过程，叫做Term。Term以选举开始，然后进入任期，即一段稳定的工作期（normal operation），见图示：
从图中可以看出来，任期是递增的，这就充当了逻辑时钟的作用，此外，term 3的情况，就是没有成功选举Leader，这时候就会发起新的一轮选举，term 3这种情况称为split vote。
Leader Election选举过程
Follower在election timeout内没有收到来自Leader的心跳，则会主动发起选举。步骤如下：
- 增加本地节点的current term，切换至Candidate状态；
- 投自己一票；
- 并行给其他节点发送选举请求，RequestVote RPCs；
- 等待其他节点回复；
在这个过程中，会出现三种结果：
- 成功获取majority的投票，当选为新的Leader；
- 被告知别人已当选，自动切换至Follower状态；
- 一段时间内没有收到majority的选票，保持Candidate的状态，重新发出选举
针对三种结果，逐一分析：
第一种情况，赢得选举以后，新Leader会立刻给所有节点发消息，广而告之，避免其他节点出发新的一轮选举；对于投票者，如何决定是否要给一个选举请求投票呢，约束如下：
- 在一个任期内，单个节点最多只能投票一次；
- Candidate知道的信息不能比自己的少
- first come first served原则，先到先得
第二种情况，假设有当前有A，B，C三个节点，由A和B同时发起选举，而A的消息先达到C，那么C就会给A投一票，此后，B的消息到达C，C已经投过一票了，为了满足以上所说的约束，无法再给B投票，而A和B不会给对方投票，那么A自然也就获得了majority的选票，选举生出。A胜出以后，会给B和C发送心跳消息，节点B发现A的term不低于自己的term，知道已经有了新的Leader了，就会自动切换至Follower。
第三种情况，没有任何节点获得majority的选票，比如如下这种情况：
共有四个节点，C和D同时称为Candidate，进入term 4，但A投了D一票，B投了C一票，出现了平票split vote的情况。这种情况下，就会重新进入等待，直到超时后重新发起选举。那么如果系统中经常出现平票的情况，就会导致系统经常性进入不可用的状态，因此raft引入了randomized election timeout来尽量避免这种情况的发生。同时，leader-based共识算法中，节点的数目都是奇数个，尽量保证majority的出现。
Log Replication
在leader election完成以后，系统开始进入对外工作期。此时客户端发送的请求将会被leader处理，并且leader会保证与followers的状态一致。raft中的做法是，将这些请求以及执行顺序告知followers。leader和followers以相同的顺序来执行这些请求，保证状态的一致性。
-
Replicated state machines
共识算法的实现一般依赖于复制状态机（Replicated state machines），在raft的论文中很好地解释了复制状态机：
If two identical, deterministic processes begin in the same state and get the same inputs in the same order, they will produce the same output and end in the same state.
如果两个相同的，确定的进程开始于相同的状态，并在相同顺序的情况下获取到相同的输入，那么最终他们会以相同的输出状态结束。
要保证这个状态的关键，是文中所说的deterministic，即确定性。如果用函数来处理，那么在函数中就不应该引入不确定性的值，例如时间，地址等。使用replicated log，则可以解决相同顺序下的相同输入的问题；因为log具有持久化，有序性的特点。
在raft中，leader将客户端的请求封装成一个个log entry。将这些log entries复制到所有的follower节点，然后大家按照相同的顺序去应用（apply）log entry中的命令。引用网上的图片：
-
请求完整流程
- leader 追加新的log entry
- leader平行地发布AppendEntries RPC
- leader等待大部分（majority）的响应
- leader应用（apply）entry到state machine
- leader 回应客户端
- leader通知followers同步应用log
可以看到日志提交过程类似于两阶段提交，不过区别在于，第一阶段只需要大多数的节点回应即可；这样只要超过一半的节点处于工作状态下，那么系统就是可用的。每个节点中保存日志的样式，借用网上的图片：
每个log由顺序编号的log entry组成，每个log entry包含了command和产生该entry的leader term。如图中，x <- 3为command，1为leader term。每个节点上的日志并不是完全一致的，raft算法为了保证高可用性，没有要求强一致性，而是最终一致性。leader会不断尝试给followers发log entries，直到所有的节点的log entries都相同。
一旦leader接收到大多数节点的回应，就会向客户端返回。一旦成功返回客户端信息，则系统就必须保证log在任何异常的状态下，都不可以发生回滚。raft论文中提及到两个操作，commit和apply。
The leader decides when it is safe to apply a log entry to the state machines; such an entry is called committed. Raft guarantees that committed entries are durable and will eventually be executed by all of the available state machines. A log entry is committed once the leader that created the entry has replicated it on a majority of the servers.
commit指的是leader收到大多数节点回复以后，这个entry就会被commited。而apply是针对于状态机而言的，leader会将committed的entries应用到状态机。raft保证了所有committed的entry都是可持续的并且最终都会被所有可用的状态机执行。
Safety
对于一个分布式系统，在任何的情况下，都需要保证系统不出现不可逆的错误。对于raft算法，会保证以下属性：
- Election Safety: at most one leader can be elected in a given term;
- Leader Append-Only: a leader never overwrites or deletes entries in its log; it only appends new entries;
- Log Matching: if two logs contain an entry with the same index and term, then the logs are indentical in all entries up through the given index;
- Leader Completeness: if a log entry is commited in a given term, then that entry will be present in the logs of the leaders for all higher-numbered terms;
- State Machine Safety: if a server has appplied a log entry at a given index to its state machine, no other server will ever apply a different log entry for the same index;
Election Safety
选举安全性，在任一任期内最多只能有一个leader被选出。这一点很好理解，不过多阐述了。
Leader Append-Only
Leader不会覆盖或者删除log上的entries，只会追加写；这一点可以保证leader上的log绝对统一。
Log Matching
如果两个节点上某个log entry的log index一致，那么在这个index之前的所有logs都会保持一致。如何做到这一点呢？
首先，leader在某一个term的任一位置只会创建一个log entry，并且是append-only的；其次，consistency check，leader在AppendEntries中包含最新的log entry之前的一个log的term和index，如果follower在对应的位置找不到日志，那么就会告知leader不一致，此时leader会强制follower复制自己的log。具体的算法逻辑如下：
leader会维护一个nextIndex[]数组，记录了leader可以发送每一个follower的log index，初始化为leader的最后一个log index + 1；
- 1: leader初始化nextIndex[x]为leader最后一个log index + 1；
- 2: AppendEntries里prevLogTerm和prevLogIndex来自logs[nextIndex[x] - 1];
- 3: 如果follower判断prevLogIndex位置的log term不等于prevLogTerm，那么返回False，否则返回True；
- 4: leader收到follower的回复，如果返回值是False，则nextIndex[x] -= 1，往前挪一个log，跳转至第2步，否则
- 5: 同步nextIndex[x]后的所有log entries
Leader completeness
leader完整性，如果一个log entry在某个任期被commit了，那么这条日志一定会出现在所有更高的term的leader的日志下面。
State Machine Safety
如果一个服务器已经向自己的state machine提交了某个特定的下标的log entry，那么其他任何服务器则不再能够在这个下标下提交一个不同的log entry，即所有节点在同一位置应该是应用同一个log entry。来看一个特殊的情况：
在时刻(a)，s1是leader，在term2提交的日志，只被赋值到s1和s2两个节点就crash了；在时刻(b)，s5成为了term3的leader，日志只赋值到了s5，然后crash；到了(c)时刻，s1又成为了leader，开始将term2的log entry赋值给s3，此时term2对应的log entry已经被赋值到了大多数的节点了，可以commited提交给自动机了。但是，到了(d)时刻，s1再次crash，s5重新当选，然后把term3的日志赋值给其他的节点，这就导致了一种奇怪的现象，被复制到大多数节点的log entry被回滚了。出现这种现象的根本原因，是因为term4的时候，s1将term2任期的日志提交了。为了杜绝这种情况的出现，raft采用的方式是：
Raft never commits log entries from previous terms by counting replicas. Only log entries from the leader’s current term are committed by counting replicas; once an entry from the current term has been committed in this way, then all prior entries are committed indirectly because of the Log Matching Property.
在某个leader选举成功以后，不会直接提交前任时期的日志，而是通过提交当前任期的日志的时候，同时也把之前的日志也提交了。假如在leader被选举之后，没有收到来自客户端的请求，那么leader会在任期开始的时候立即尝试复制并提交一条空的log。
因此，在上图中，不会出现(c)的情况，而是如同(e)时刻一样，同时把term4的日志和term2的日志一起提交。如果term4的日志提交成功了，那么term2的日志肯定也会一并提交成功，此时即使s1 crash了，term已经到4了，s5也不会重新当选了。
总结
raft算法是分布式系统中很重要的一个算法，学习raft算法有助于更好地理解一些主流的分布式系统的实现。深入学习raft算法的方法是阅读论文，我也是粗略地略看了论文，并结合了网上写raft算法写得比较的博文。另外，有一个很好的动画展示了raft算法的流程，有助于理解。关于raft算法相关的内容，当然也可以上github上面查找阅读学习。
