分布式存储系统通常采用多个副本进行容错，提高系统的可用性。要实现此目标，就必须要解决分布式存储系统的最核心问题，维护多个副本的一致性。
一致性是构建容错性的分布式系统的基础。在一个具有一致性的性质的集群里，同一时刻所有的节点对存储在其中的某个值都有相同的结果，即对其共享的存储保持一致性。集群具有自动恢复的性质，少数节点失效时不会影响整个集群的正常工作。
说白了，一致性就是保证即使在部分副本宕机时，系统仍然能正常对外提供服务。一致性协议通常基于replicated state machines，即所有结点都从同一个state出发，都经过同样的一些操作序列（log），最后到达同样的state。 >系统中每个节点有三个组件 >- 状态机：当我们说一致性的时候，实际就是在说要保证这个状态机的一致性。状态机会从log里面取出所有的命令，然后执行一遍，得到的结果就是我们对外提供的保证了一致性的数据 >- log：保存了所有修改记录 >- 一致性模块：一致性模块算法就是用来保证写入的log的命令的一致性，这也是raft算法核心内容
Raft协议将一致性协议的核心内容分拆成为几个关键阶段，以简化流程，提高协议的可理解性。
1. Leader election（选主）
Raft协议的每个副本都会处于三种状态之一：Leader、Follower、Candidate。 >- Leader：所有请求的处理者，Leader副本接受client的更新请求，本地处理后再同步至多个其他副本； >- Follower：请求的被动更新者，从Leader接受更新请求，然后写入本地日志文件 >- Candidate：如果Follower副本在一段时间内没有收到Leader副本的心跳，则判断Leader可能已经故障，此时启动选主过程，此时副本会变成Candidate状态，直到选主结束。
时间被分为很多连续的随机长度term，term有唯一的Id。每个id一开始就进行选主。 - 1.Follower将自己维护的current_term_id加1 - 2.将自己的状态转为Candidate - 3.发送RequestVoteRPC消息（附带current_term_id）给其他所有server
此过程会有三种结果： - 自己被选为主。当收到majority的投票后，状态切成了Leader，并定期给其他的所有的server发心跳消息（不带log的AppendEntriesRPC）以告诉对方自己是current_term_id所标识的term的Leader。每个term最多有一个leader，term id作为logical lock，在每个RPC消息中都会带上，用于检测过期的消息。当一个server收到的RPC消息中的rpc_term_id比本地的current_term_id更大时，就更新 current_term_id为rpc_term_id，并且如果当前state为Leader或者Candidate时，将自己的状态切为Follower。如果更小，则拒绝这个消息。 - 别人成了主。当Candidate在等待投票的过程中，收到了大于或者等与本地的current_term_id声明对方是Leader的AppendEnteriesRPC时，则将自己的的state切换为Follower，并更新自己本地的current_term_id。 - 没有选出主。没有Leader被选出，每个Candidate等待投票的额过程就已超时，接着Candidates就会将本地的current_term_id再加一，发起RequestVoteRPC进行新一轮的Leader election。
投票策略： - 每个节点只会给每个term投一票，具体的是否同意和后续的Safety有关。 - 当投票被瓜分后，所有的Candidate同时超时，然后有可能进入新一轮的票数被瓜分。为了避免这个问题，Raft采用一种很简单的方法：每个Candidate的election timeout从150ms-300ms之间随机取，那么第一个超时的Candidate就可以发起新一轮的leader election，带着最大的term_id给其它所有server发送RequestVoteRPC消息，从而自己成为leader，然后给他们发送心跳消息以告诉他们自己是主。
Raft有2个timeout设置 1）从follow而转换到candidate的timeout： election timeout，设置为：150ms到300ms中的随机数。一个node到达这个timeout之后会发起一个新的选举term（递增的，大的表示新的），向其他节点发起投票请求，包括投给自己的那票，如果获得了大多数选票，那么自己就转换为leader状态 2）node成为leader之后会向其他node发送Append Entries，这个时间为heartbeat timeout 如果lead在实际使用中down掉，剩下的节点会重新开启1）和2）描述的选举流程，保证了高可用性 特殊情况:
如果集群中剩下偶数个node，并且在选举的过程中有2个node获得相等的选票数，那么会开启新的一轮term选举。直到有一个node获得多数选票（随机的election timeout保证可行）
2. Log Replication
当Leader被选出来后，就可以接受客户端发来的请求了，每个请求包含一条需要被replicated state machines执行的命令。leader会把它作为一个log entry append到日志中，然后给其它的server发AppendEntriesRPC请求。当Leader确定一个log entry被safely replicated了（大多数副本已经将该命令写入日志当中），就apply这条log entry到状态机中然后返回结果给客户端。如果某个Follower宕机了或者运行的很慢，或者网络丢包了，则会一直给这个Follower发AppendEntriesRPC直到日志一致。
当一条日志是commited时，Leader才可以将它应用到状态机中。Raft保证一条commited的log entry已经持久化了并且会被所有的节点执行。
如果Leader和其他Fellower的日志不同怎么办
我们需要一个机制来保证日志的一致性
如图中例子，最上面这个是新Leader，a~f是Follower，每个格子代表一条log entry，格子内的数字代表这个log entry是在哪个term上产生的。
新Leader产生后，就以Leader上的log为准。其它的follower要么少了数据比如b，要么多了数据，比如d，要么既少了又多了数据，比如f。
因此，需要有一种机制来让leader和follower对log达成一致，leader会为每个follower维护一个nextIndex，表示leader给各个follower发送的下一条log entry在log中的index，初始化为leader的最后一条log entry的下一个位置。leader给follower发送AppendEntriesRPC消息，带着(term_id, (nextIndex-1))， term_id即(nextIndex-1)这个槽位的log entry的term_id，follower接收到AppendEntriesRPC后，会从自己的log中找是不是存在这样的log entry，如果不存在，就给leader回复拒绝消息，然后leader则将nextIndex减1，再重复，知道AppendEntriesRPC消息被接收。
以leader和b为例：
初始化，nextIndex为11，leader给b发送AppendEntriesRPC(6,10)，b在自己log的10号槽位中没有找到term_id为6的log entry。则给leader回应一个拒绝消息。接着，leader将nextIndex减一，变成10，然后给b发送AppendEntriesRPC(6, 9)，b在自己log的9号槽位中同样没有找到term_id为6的log entry。循环下去，直到leader发送了AppendEntriesRPC(4,4)，b在自己log的槽位4中找到了term_id为4的log entry。接收了消息。随后，leader就可以从槽位5开始给b推送日志了。
哪些follower有资格成为leader?
Raft保证被选为新leader的节点拥有所有已提交的log entry，这与ViewStamped Replication不同，后者不需要这个保证，而是通过其他机制从follower拉取自己没有的提交的日志记录
这个保证是在RequestVoteRPC阶段做的，candidate在发送RequestVoteRPC时，会带上自己的最后一条日志记录的term_id和index，其他节点收到消息时，如果发现自己的日志比RPC请求中携带的更新，拒绝投票。日志比较的原则是，如果本地的最后一条log entry的term id更大，则更新，如果term id一样大，则日志更多的更大(index更大)。
哪些日志记录被认为是commited?
- Leader正在replicate当前term（即term 2）的日志记录给其它Follower，一旦Leader确认了这条log entry被majority写盘了，这条log entry就被认为是committed。如图中(a)，S1作为当前term即term2的leader，log index为2的日志被majority写盘了，这条log entry被认为是commited。
- Leader正在replicate更早的term的log entry给其它Follower。图(b)的状态是这么来的。
这里面隐含一个很严重的问题：一应用到状态机的日志被截断： 1. 在阶段a，term为2，S1是Leader，且S1写入日志（term, index）为(2, 2)，并且日志被同步写入了S2。 2. 在阶段b，S1离线，触发一次新的选主，此时S5被选为新的Leader，此时系统term为3，且写入了日志（term, index）为（3， 2）。 3. S5尚未将日志推送到Followers变离线了，进而触发了一次新的选主，而之前离线的S1经过重新上线后被选中变成Leader，此时系统term为4，此时S1会将自己的日志同步到Followers，按照上图就是将日志（2， 2）同步到了S3，而此时由于该日志已经被同步到了多数节点（S1, S2, S3），因此，此时日志（2，2）可以被commit了（即更新到状态机）。 4. 在阶段d，S1又很不幸地下线了，系统触发一次选主，而S5有可能被选为新的Leader（这是因为S5可以满足作为主的一切条件：1. term = 3 > 2, 2. 最新的日志index为2，比大多数节点（如S2/S3/S4的日志都新），然后S5会将自己的日志更新到Followers，于是S2、S3中已经被提交的日志（2，2）被截断了。
为了避免这种错误，对协议作出修改 >只允许主节点提交包含当前term的日志
针对上述情况就是：即使日志（2，2）已经被大多数节点（S1、S2、S3）确认了，但是它不能被Commit，因为它是来自之前term(2)的日志，直到S1在当前term（4）产生的日志（4， 3）被大多数Follower确认，S1方可Commit（4，3）这条日志，当然，根据Raft定义，（4，3）之前的所有日志也会被Commit。此时即使S1再下线，重新选主时S5不可能成为Leader，因为它没有包含大多数节点已经拥有的日志（4，3）。
节点之前的网络状况十分不好，有多个leader怎样处理？
节点之前的网络状况十分不好，此时会有多个leader，其term也是不同的。 由于commit的修改需要多数通过，那么只有具有最多node的一个集群会commit修改成功。 当网络状况恢复，整个集群的节点会向多数节点的集群同步。这样整个集群中的数据会继续保持一致
综述一下Log Replication client给leader发送数据修改请求 leader通过Append Entries在心跳的过程中将修改内容下发到follower nodes 在多数follower 接收了修改内容返回后，leader向client确认 leader向follower发送心跳，具体执行修改操作，此后数据在集群中保持一致
3. Log Compaction
在实际的系统中，不能让日志无限增长，否则系统重启时需要花很长的时间进行回放，从而影响availability。Raft采用对整个系统进行snapshot来处理，snapshot之前的日志都可以丢弃。Snapshot技术在Chubby和ZooKeeper系统中都有采用。 >Raft用的方案是：每个副本独立的对自己的系统状态进行Snapshot，并且只能对已经提交的日志记录（已经应用到状态机）进行snapshot。
Snapshot中包含以下内容： - 日志元数据，最后一条commited log entry的 (log index, last_included_term)。这两个值在Snapshot之后的第一条log entry的AppendEntriesRPC的consistency check的时候会被用上。一旦这个server做完了snapshot，就可以把这条记录的最后一条log index及其之前的所有的log entry都删掉。