什么是Replicated state machines(复制状态机):

一致性算法之所以可以保证在有节点挂掉时也能够继续服务， 就是因为有Replicated state machines的存在。 在分布式系统中， 有两种方式来实现这个复制状态机

1. 用一个专门节点负责记录整个集群的元信息， 如HDFS， GFS
2. 每个节点都会记录replicated log，确保每个节点的log最终都包含了相同的请求， 并且是同样的顺序

一致性算法一般有一下特点：

1. 保证安全（不会返回错误数据）
2. 只有半数以上的节点存活就可以继续提供服务
3. 不依赖时钟来提供一致性， 最多会造成不可用
4. 通常只要半数以上节点完成请求就算成功， 小部分慢节点不会影响整个系统的性能

为啥不用Paxos？

1. 不清晰， 难以理解
2. 不好实现， 只提供了single-decree Paxos的细节， 没有给出multi-Paxos的细节

Raft一致性算法

Raft算法首先会选举一个leader， 然后又leader来管理replicated log。 leader会从client处接收请求， 然后转发给别的节点， 并且告诉这些节点什么时候可以把这些请求应用在状态机上（落地）。 当一个leader挂了的时候， 会马上选举出一个新的leader。 由上可知， Raft将一致性问题拆分成了3个独立的子问题：

1. Leader选举
2. 日志的复制（Log replication）
3. Safty： 不能有错误数据

• Raft的实践基础
  一个Raft集群会有多个节点， 一般至少5个， 这样可以忍受2个节点fail。 这些节点在任何时间点都会是以下3个状态之一： leader， follower， candidate。
  Raft将时间分为了多个term， 选举会产生一个新的term， 每个term的时长不定，但是每个term都至多有一个leader
  不同的节点会在不同时间感知到变化，有些节点甚至在一个term完结时都没有感知到。 Terms是一个逻辑时钟， 每个节点都会存储当前term， 并且会一直跟别的节点交换信息， 一旦发现自己的term不是最新的， 就会更新term， 如果一个candidate或者leader发现他的term过时了，就会马上回退成follower。 如果一个节点收到一个过期term的请求， 那么他会拒绝这个请求
  Raft节点间通过RPC请求进行通信， 基本的算法只要求两种RPC请求类型。 一种是RequestVote RPCs, 由candidate在选举时发出。 一种是AppendEntries RPCs， 由leader发出， 用来复制log和发送心跳

• leader选举
  Raft用心跳来触发leader选举， 当节点启动时， 都是follower的状态。只要节点能够收到来自leader或者candidate的RPC， 节点就会保持follower状态。
  Leader会定期发送RPC给所有的follower来维持他的leader地位， 但是一旦有一个节点在一段时间没有收到心跳， 那么节点就会认为没有存活的leader并且触发新一次的选举。
  选举开始时，一个follower会给当前term加1并且转换成candidate状态。 然后这个节点会给自己投票并且给所有其他节点发送RequestVote RPC。
  Candidate会保持这个状态直到以下3个事件中的一个发生：

  1. 这个节点赢得选举
     如果这个节点赢得了半数以上的vote就会成为leader，每个节点会按照first-come-first-served的原则进行投票，并且一个term中只能投给一个节点， 这样就保证了一个term最多有一个节点赢得半数以上的vote。
     当一个节点赢得选举， 他会成为leader， 并且给所有节点发送这个信息， 这样所有节点都会回退成follower。
  2. 另外一个节点赢得选举
     在等待vote时， 如果这个candidate收到了别的节点请求vote的RPC， 那么他会检查是否这个节点的term大于等于自己的term， 如果是那么这个candidate就会回退成follower。 如果不是就会reject这个RPC。
  3. 一个选举周期结束并且没有leader选出来
     这种情况是由于可能有很多follower都成为了candidate， 那么vote就会很分散， 最后没有一个节点拿到半数以上的vote。最后这个term超时并且进入下个term继续选举。
     为了防止这种情况一直重复，每个节点的election 超时时间是(150~300ms)的随机数， 这样在一个term就会有一个节点很快超时进入下一个term， 然后就能在别的节点timeout之前赢得选举

Figure3

• Log replication
  当leader选出来后，他就可以正式给客户端提供服务。 leader会将请求以entry的形式追加到自己的log中，并且将这个entry以AppendEntries RPC并发发送给所有的follower节点。 当这个entry成功的复制后（怎么算成功之后会谈到）， leader会将这个entry 应用到自己的state machine并且给client返回成功。 如果复制失败， leader会一直重试AppendEntries RPC直到所有log entry都被成功复制。

Logs Organization

Logs 组织的形式如图所示。 当leader收到一个Log entry时， 每个log entry都会存储一个带有term number的state machine命令。 Term number是用来探测log之间的不一致性并且保证Figure3的一些特性。 每个log也还带有他们在log里的索引数字。

当leader认为这个entry是可以成功应用到状态机上， 那么这个entry就被成为commited。Raft保证所有commited entry最终都会被应用到所有的节点上。

当一个entry被成功复制到半数以上的节点后， 这个log就可以认为成功写入了。并且会将leader之前的写入也视为commit。

设计Raft日志机制不仅简化了系统的行为， 也保证了正确性。 保证了Figure3的以下特性
1. 当不同log中的两个entry有相同的term和index， 那么这两个entry就是相同的
2. 当不同log中的两个entry有相同的term和index， 那么这两个entry之前的所有entry也都是相同的

Paste_Image.png

当leader发现follower的log跟自己的不同时， 他会针对每个follower维护一个nextIndex。 这个nextIndex就是Leader下次会发第几个entry给这个follower。 而follower也会拒绝这个append entry的rpc。

Safety

• 如何保证数据不丢失和数据的正确性是分布式数据库最重要的两点， Raft协议也设计了相应的算法来保证这两点。
  1. 所有的entry都只能从leader流向follower，而要成为leader必须有所有的committed entries。 如果有server发现candidate的数据没有自己更update-to-date, 那么他会拒绝这个vote request。 如果两个server的log term不同， 那么term number更大的更update-to-date, 如果term相同， 那么index更大的更update-to-date。

Figure 3

2. 仅有第一点的保证我们仍旧可能会遇到问题。 如上图所示， a） s1成为leader，部分拷贝了index 2; b) s1挂了， s5成为leader, 写入index 3; c）s5又挂了， s1再次成为leader并且继续将index 2拷贝到其余follower； d) s1又一次挂了， s5成为leader(获得2,3,4的选票)， 将自己所有的s3拷贝到别的机器并且覆盖掉了index 2; e)如果c阶段没有挂那么日志会被拷贝到s2,s3, 之后s5就不会被选为leader。
   上图演示了写入数据可能会被覆盖的问题， 那么如何避免这个问题。 Raft规定绝不通过计算副本数的方式commit 之前term的log entries。 只有当前term的log enties使用计算副本的方式来提交。 对于之前的term来说，当一个log通过这个方式提交成功了，那么他之前的所有log都算commit成功了。

   如何证明这个结论的正确性， 论文用反证法进行了论证：

Figure 4

如Figure 4所示， 如果term T commit的数据在之后的term U丢失了， 那么
1. 这个log一定不在Leader-U的log中（因为leader不会覆盖旧数据）
2. Leader-T把这个日志复制给了大多数节点并且Leader-U收到了大多数节点的投票， 所以至少有一个节点是既收到了这个entry并且又给Leader-U投票了
3. 那么这个投票的节点也一定收到了所有Leader-T的commited entries
4. 因为这个投票节点把票投给了U, 那么说明Leader-U也至少有所有这个节点的entries
由此可知， 如果投票节点和Leader-U 共享了之前的log， 那么Leader-U肯定会有所有投票节点的entry。 另外， Leader-U的last-log-term必须比T大， 而投票节点的term至少是T。之前term的leader在复制entry给Leader-U时也必须包含了之前的这个entry。 投票节点和之前term的leader都会有这个entry， 所以Leader-U也不会没有这个entry。可下结论所有大于T的term的leader绝对包含了所有term T commited的entries。