前言
最近准备去看看 ETCD 的源码，然后网上看到它是基于 Raft 论文实现的，所以为了后面更好的理解 ETCD，于是便想先来看看 Raft 论文，想先了解下这个分布式数据一致性算法 Raft 论文的具体内容。经过几天工作之余的时间，认真的看了下这个论文，于是乎写上这边总结。
在分布式中，有一个叫 CAP 的理论概念，及 C-一致性 (Consistense)，A-可用性 (Available)，P-分区容错性 (Partition toleration)。
及 BASE 理论， Basic Available， Soft state， Eventually Consistense。
概括
从 Raft 论文中，贯穿整个论文的一个核心思想就是它是为了便于理解而设计的。而这里的背景就是论文的作者学习了 Paxos，觉得它太难理解了，也不太好实现。（这里可以参考第 3 节 Waht's wrong with Paxos 中的两个缺点：The first drawback is that Paxos is exceptionally difficult to understand 和 The second problem with Paxos is that it does not provide a good foundation for building practical implementations.)。 此外作者不止一处指出论文的设计初衷就是便于理解，并专门安排一节（第四节 Desining for understandability) 去解释这个问题。而第 4 节中也提到了通过了两种方式去简化了这个问题。第一即是分解问题，第二则是减少中间的状态从而简化状态空间，并能够减少不确定性。及第 9.1 节 Understandability，根据实际调查，进行数据分析，从而对比 Raft 的易理解的优势。
论文看下来，确实觉得还是很好理解的，且也为实现者大大地简化了接口，目前只有三个接口 RequestVote，AppendEntries 及 State（除了 Log 压缩的接口 installSnapshot）。而所谓好理解，个人觉得也只是通篇来说比较好理解。之所以这么说，是因为我阅读了几遍之后，还是有个别地方理解不透，或没理解。具体地方我会在下面具体的章节中备注。如果有同学们理解了，可以私信我，共同学习一下。
算法理解
理解 Raft 具体的算法理论之前，我简单的描述下复制状态机的概念（第 2 节 Replicated state machines)。它其实在这章节的开始就提出来了，一致性算法是出现在复制状态机的上下文中的，也就是说一致性算法其实就是解决复制状态机中数据同步最后一致的问题的。而复制状态机的一致性，其实是其中如何对 Log 的复制同步问题。因为复制状态机是将 client 发送的 command 以每个 Entry 的形式存储在 Log 中，而不同的机器中的 Log 的复制问题也就是解决了复制状态机的一致性问题。为什么可以这么说呢，是因为，复制状态机的概念是如果多个不同的 Server 的初始状态是一致的，那么通过执行相同顺序的一些列命令后，最终状态必定是一致的。这里可以主要通过作者的两句话理解 (Replicated state machines are typically implemented using a replicated log 和 Keeping the replicated log consistent is the job of the consensus algorithm.)。
所以这里的一致性问题，个人觉得其实就是 Logs 的复制同步问题，及只要这些 log 的 entries 能按照同样的顺序复制到不同的机器上，则最终保证了算法的一致性问题。如是乎，个人理解，Raft 的算法即是重要解决 Log 复制同步问题。
基本概念
整个 Raft 算法理论分为三个子问题：Leader election, Log replication 及 Safety。并分了三个子章节去分别描述。
并提出了下面这些基本概念：
-
leader- 选举出来服务的 server。 -
follower- 被动的，只简单的响应 leader 和 candidate 的请求。如果一个 follower 被 client 请求，它将会重定向到 leader 中。 -
candidate- 用于选举一个新的 leader。 -
term- raft 将时间划为任意的 term 来表示，每一个 term 以选举开始，如果一个 candidate 赢得了选举，成为 leader，则它将会持有这个 term 的剩下的时间。 -
election timeout- 一个 follower 没有收到任何请求的一段时间，如果这段时间内没有收到任何请求，follower 则认为没有可用的 leader，将会触发一个新一轮选举。
这里引入了一个 split vote 的问题：即同时多个 candidate 被选为 leader，这是违背 Election Safety 的特性的，所以是不被允许的，具体的解决方法在 Leader 选举章节介绍了。而这里当这种情况发生后，这个 term 将只会有选举的时间，当重新选举的时候，会产生一个更新的 Term。
这里需要将 Raft 中几个性质介绍一下：
-
Election Safety- 即在一个 Term 中最多只可以选出一个 Leader。（个人觉得这是 Raft 一致性的基石） -
Leader Append-only- Leader 只能添加新的 Entries，不能删除或者重写 Log 中的 Entries。 -
Log Matching- 如果两个 logs 中包含一个相同的 index 和 term 的 entry，然后通过给定一个 index，这两个 log 中的所有的 entries 都是相同的。 -
Leader Completeness- 如果一个 Log entry 在一个给定的 Term 被提交，然后那个 entry 将会在那些所有比这个 Term 要大的 leader 的 log 中。 -
State Machine Safety- 如果一个 server 在一个给定的 index 已经将 log entry 应用到它的状态机中，于是乎，其他的 server 则不可能在相同的 index 处应用一个不同的 log entry。
Leader 选举
Raft 用心跳（不带任何 log entry 的 AppendEntries RPC) 的方式去维持leader的控制权。当开始的时候，所有的Server都是 follower，然后当一个 follower 收到从 Leader 或者 candidate 的有效的 RPC，它将保持 follower 状态。而通过选举成为leader的server，则会定期发送心跳给所有的 follower 去告诉它们，自己还活着，从而避免 follower 出现election timeout，以至于触发新的一轮选举。
这里在一次选举过程中，一个 server 可以有三种不同的结果：
-
server 赢得了选举， 成为了 leader
-
其他 server 赢得了选举，该 server 收到了对应的 heartbeat。
-
出现了 split vote，这次选举没有 server 成为 leader。
这里为了解决 split vote 的问题，提出了一个随机选举超时 (randomized election timeout) 的概念。主要思想是通过随机产生一个 election timeout 时间，从而降低 servers 触发成为 candidate 去触发选举的概率。（个人理解，这个算法不能根本解决这个问题，只能在一定程度上降低这个问题的概率。) 这里，作者还提到了一个 ranking 算法，但经过作者试验，在很多边界问题上，仍不能彻底解决，因此，作者最终选择了随机选举超时的方式。
Log 复制同步
当 leader 收到 client 的请求，它将创建一个新的包含这个请求的 entry，并追加到自己的 log 中，然后并行的发送 AppendEntries RPC 给所有其他的 Server 去复制这个 entry。当这个 entry 被复制，然后这个 leader 将请求提交到状态机中进去执行，再将结果返回给 client。这里如果某个 follower 出现问题 (crash or run slowly) 没有收到请求，leader 将会一直发送 AppendEntries，直到所有的 follower 最终存储了所有的 log entries。
这里重点问题就是这个当这个 entry 被复制。 什么叫 entry 被复制呢？按照这篇论文，提到了一个 commited 的概念（当 leader 决定它可以安全的应用这个 log entry 到状态机执行的时候，这样的一个 entry 可以被叫做 commited），及这个 entry 被大多数 follower 同步的时候及可理解为被复制了。（例如文中推荐的 5 个 sever，2 个 follower 同步后，几个当做是被复制了，可进行下面的操作）。
这里结合 Log Matching 性质提出了下面两个特性：
-
如果不同 logs 中的两个 entry 有相同的 index 和 term，则表示它们存储了相同的 client 请求命令。
-
如果不同 logs 中的两个 entry 有相同的 index 和 term，然后所有这些 logs 中之前的 entries 也是相同的。
这两个性质则能够保证，当不同 logs 中在同一个 index 下，如果 term 也相同，则这 index 的请求命令也相同，并且这个 index 之前的所有 entries 也都相同。这样就保证了 logs 的顺序是一致的。那么这种性质如果表示出来呢？ 作者这 AppendEntries 的接口中引入了两个参数及 preLogIndex，preLogTerm 来保证第二条性质的成立。
但这里并不能完全的解决 log 复制的一致性问题。例如当一个 leader 在刚复制 entry 到大部分 follower 中后，它自己在提交 entry 到状态机之前挂了，（及这个 entry 还不是 commited 的状态）。这个时候另外的 candidate 被选为 leader，进行同步，这个同步到大多数 follower 但没有 commited 的 entry，则会被新的 leader 的 entry 覆盖。及不同情况会导致不同的结果，即文中 Figure8 的 d 和 e 的情况。（其实我没有理解到底 d 的情况是不是正确的，从文中看下来，我并没有看到对这个问题的过多描述。不知道文中的 5.4.2 是不是描述的这个问题）
Safety
由于上面的 leader 选举和 log 复制的过程中并不是安全的，例如如何保证 Leader Safety 及 Leader Completeness 的性质呢，那这章节则描述了这些问题。
选举限制
Raft 保证当每个新的 leader 在它选举的时刻，它将有所有在之前 Terms 被提交的 entries，不需要将那些 entries 传输到 leader 中。这其实保证了 leader 中的 entries 始终是保证最新的，否则，这个 server 也不能被选为 leader。这种机制是通过 server 进行投票（RequestVote RPC）进行保证的。
提交之前 Term 的 entries
这一章节，说实话，我没有太看懂，虽然文中提交了上面所说的 Figure8 出现的问题（即 C 的情况下 Term2 被同步到大多数 server 中，但是此时 S1 只同步了 S3, 比还没有知道 S2 的状态，因此 S1 是不能立即知道 Term2 已经存储在大多数 Server 中，可以进行提交，但这时，S1 又挂了，出现了 D 的情况）。
但对于这个问题文中这么一段话 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.
这里几个问题没太理解：
-
counting replicas指的什么？ -
all erior entries are commited indirectly because of the Log Matching Property怎么个间接提交？
Timing 和 Availability
broadcastTime « electionTimeout « MTBF
-
broadcastTime: leader 发送 RPCs 且收到响应给 follower 的平均时间。 -
electionTimeout: follower 判断 leader 是否可得的超时时间。 -
MTBF: 一个 server 故障之间的平均时间
Cluster Membership changes
将 configuration 改变的请求同样通过 log entry 的方式进行同步更新，从而实现 Cluster 配置的更新。一般做法是将老的配置删除，再运用新的配置，但是这个过程中 服务是不能工作的。
可能是考虑到可用性，作者提出一种新的方式去做配置更新。引入一个 joint consensus 的概念。即将 C-old 和 C-new 合并成 C-old&new。 当将 C-old&new 复制到大多数 server 中，然后提交到状态机中执行，当这个 C-old&new 被提交后，则再将 Cnew 运用到已赋值的 sever 中，最后达到所有的 sever 都被更新到 Cnew。
Log 压缩
为什么要进行 log 的压缩，这是由于复制状态机中使用了 Log 存储 client 发送的请求，并在 servers 中进行同步，所以随着时间的推移及 client 请求的增加，Server 中的存储都会有压力，最终可能导致 Server 的不可用，从而影响到整个一致性算法的可靠性。因此对于日志的压缩是必不可免的问题。而文中则使用了常用的 Snapshotting（快照）的方式进行日志压缩。并提供了一个新的 installSnapshot RPC。
由于在 Server 间引入了一个新的 RPC，所以对性能方面还是会有一定的影响，例如文中提出两个问题：
-
决定什么时候发送 snapshot？发的太频繁，就会浪费带宽，如果时间太长，则有没有很好地作用。
-
由于写一个 snapshot 也会占用一些时间，从而会影响到正常的操作。
总结
由于还没有学习 Paxos 的算法，但是从网上大概的了解了下，个人感觉 Raft 算法正如它的宗旨一样还是比较好理解的。但可能是刚接触到这类问题，所以有些概念还不是太理解，就例如上面我提出的几个问题，我个人就没有理解其意。但总体是简洁明了的。