我们希望一个怎样的系统？
- 在部分断电或毁灭性灾难等，服务依然不中断，数据依然是安全的（高可用性）
- 得知数据写入成功的时点后，无论从哪个地方，从哪个服务器，都能感知到写入的数据（强一致性）
考虑可用性，最简单的想法就是引入多副本，每个副本都存在世界的不同地方，这样，一个副本坏了，那么可以用其他地方的副本，重建这个坏的副本
如果多个副本，这些副本间如何保持数据一致呢？
很直观的，一个副本把数据同步到另一个副本，总会有时间差，也就是总有一段时间数据是不一致的，或者一个客户端把数据群发给所有副本，接收数据的时间也是有差的。 所以需要一个定义：怎样的情况下数据是一致的？这种一致有什么特征？
Raft是一个强一致性的一致性协议
强一致性的特征 -> 可线性化（linearizablity）： 在一系列的操作中，能找出一种顺序，按照这种顺序，操作需要满足：
- 值的因果关系
- 时间的先后顺序
Raft中的三种角色Leader、Candidate、Follower
假设A、B、C三台机子，运行Raft协议，只有一台会被选为Leader， 比如是A，那么其他机器B、C就是Follower。 然后，客户端的所有请求都发给A，由A再将请求数据同步给B和C。
这个协议的两个重要部分：如何选Leader？如何同步数据？
如何选Leader？
协议采用一个古老的办法，选举，拿到大多数（majority）选票的机器， 则当选Leader，3台机器，majority=2，如果每个机器都只能投一票， 那只会有一台机器拿到大多数票，这就自然地解决了Leader只会有一台的问题。
直觉：机器都有可能挂掉，Leader也会挂掉，那么就该重新选举，那么就会有新Leader的诞生。 为了能区别新Leader，有个轮次的概念term，表明这是term轮的Leader。 每台机器都维护term变量，是单调递增的。
当一台机器发起选举时，首先开启新的一轮，将自己的term加1，比如term从7变为8，并且自己先投给自己，变为Candidate，再向其他机器群发term=8的选票申请，获得的选票达到大多数后，它就可以认为自己是term=8轮的Leader，最后给其他机器B、C，群发心跳消息，通知term=8的Leader已经诞生了，其他机器收到心跳，发现心跳的term大于等于自己的term，主动转为Follower。
什么时候选举？Leader挂了的时候？那如何知道Leader挂了？
Raft使用的机制是，每台机器维护着一个计时器，计时器时间一到， 比如200ms，就主动发起对自己的选举。 Leader的心跳消息，除了通知大家term轮的Leader已经诞生了， 其实还表明了，term轮的Leader还活着，于是，收到心跳的机器， 还要自己的重置计时器，阻止计时器到点，触发新一轮选举。
所以Leader的发送心跳任务的周期时间一定要小于计时器到点时间（论文中，发心跳周期100ms）。
运行Raft协议初始化时，这时候还没有Leader，如果每台机器的计时器都同时到点，就会同时发起选举， 选票就大概率被瓜分，难以选出Leader，所以引入随机性，每台机器的计时器到点时间不一样， 比如200ms+rand(100)。
另外，心跳还用于Leader给Follower同步数据。
如何同步数据？
选举的过程就是获得大多数选票的过程，数据同步也是大多数的同步的过程。
Raft维护一个log数组，数据同步的过程，也就是log数据同步的过程。
沿用上面例子的选举结果，当Leader，A收到一条消息，首先把消息包成一个log，添加到log数组末尾，给log打上自己的term和index（该log在log数组的索引），比如term=8，index=9。 再将新log群发给其他机器B、C，大多数回复成功收到，即只要B或C任何一台返回成功（A+B或C），A就可以认为新log已经达成一致。 在A发心跳时，告诉大家commitIndex=9，表明log数组中index<=9的log数据达成共识了。
什么叫“达成共识“？
只要不是大多数（majority）的机器被摧毁（硬件坏掉、机房火灾），可以保证：达成共识的数据是可以恢复的（有副本的），并且是不可变的。 什么叫不可变？
Leader的心跳会将自己log同步给Follower，Follower对比自己的log，如果log有不一致的地方（判断index位置的term是否一致），Follower会删掉自己，从不一致的log开始的log，然后加上Leader的log，直到和Leader的log数组同步。
这个过程中，有删掉log的可能，那么怎么保证“达成共识”的log不会有被删掉的风险？这就是不可变。 很直观的，如果保证Leader的log包含全部达成共识的log，那么将log同步给其他Follower就不可能删掉达成共识的log。 Leader的前身是Candidate，也就是说，Candidate必须要包含全部达成共识的log，才能有当选Leader的资格，那么就要求一台机器进行投票时，要检查Candidate的log数组是否满足。投票申请中包含Candidate的（lastLogIndex，lastLogTerm）
投票规则：
- 对比log数组末尾的log，要是Candidate的lastLogTerm大，投给这个Candidate
- 要是term相等，那判断log数组的长度，Candidate不短与自己的，投给这个Candidate
- 否则，拒绝
比如三台机器A、B、C，A是Leader，A的新log，记为aLog（term=8，index=9），达成共识。 有没可能之后选举的新Leader是不含aLog的？
A当前是为Leader，term=8，新的Leader没出现前，所有机器的log数组的最后的log一定term小于等于8，如果存在一台机器X不含aLog，有两种情况：
- X最后一条log的term<8，而aLog达成共识，说明大多数机器都有aLog，所以大多数的最后一条log的term=8，根据规则一，大多数都不会投给X，所以X不会当选Leader。
- X最后一条log的term=8，而aLog达成共识，说明大多数机器都有aLog，根据规则二，X缺少aLog，X的log数组一定更短，大多数不会投给X的，所以X不会当选Leader。
注意前提条件：aLog达成共识是在A作为Leader的term中的，才能保证X的最后一条log的term一定小于等于8，如果X的最后一条log的term大于8，就可能当选Leader（Figure8说明了这个问题）
实现细节：
- 如果一个log已经存在大多数的机器上了，该log是否达成共识？否，论文Figure8构建了这种案例。
- 持久化问题，为了保证一个term每台机器只能投一票，所以即使故障重启，不能忘记自己term轮投的票。