Raft算法
一、leader选举过程
raft协议中，一个节点任一时刻处于以下三个状态之一：
- leader：主节点
- follower：从节点
- candidate：候选主节点
1、启动时选举：
有节点启动时都是follower状态，在一段时间内如果没有收到来自leader的心跳，从follower切换到candidate，发起选举。如果收到集群中大多数的票（含自己的一票）则切换到leader状态；如果发现其他节点比自己先成为了leader，则主动切换到follower。
2、运行时选举：
如果follower在election timeout内没有收到来自leader的心跳，（也许此时还没有选出leader，大家都在等；也许leader挂了；也许只是leader与该follower之间网络故障），则会主动发起选举。步骤如下：
- 某个节点切换到candidate状态并投自己一票
- 并行给其他节点发送 RequestVote RPCs请求（请求投票）
- 等待其他节点的回复
在这个过程中，根据来自其他节点的消息，可能出现三种结果
- 收到majority的投票（含自己的一票），则赢得选举，成为leader
- 被告知别人已当选，那么自行切换到follower
- 一段时间内没有收到majority投票或者两个candidate平票，则保持candidate状态，重新发出选举
因为经常性的平票会让节点不停地重新选举，导致长时间不可用，所以raft引入了randomized election timeouts来尽量避免平票情况（每个节点的选举超时时间都是随机的）。同时，leader-based 共识算法中，节点的数目都是奇数个，尽量保证majority的出现。、
3、log replication
客户端的一切请求来发送到leader，leader来调度这些并发请求的顺序，并且保证leader与followers状态的一致性。raft中的做法是，将这些请求以及执行顺序告知followers。leader和followers以相同的顺序来执行这些请求，保证状态一致。leader将客户端请求（command）封装到一个个log entry，将这些log entries复制（replicate）到所有follower节点，然后大家按相同顺序应用（apply）log entry中的command，则状态肯定是一致的。
leader只需要日志被复制到大多数节点即可向客户端返回，一旦向客户端返回成功消息，那么系统就必须保证log（其实是log所包含的command）在任何异常的情况下都不会发生回滚。这里有两个词：commit（committed），apply(applied)，前者是指日志被复制到了大多数节点后日志的状态；而后者则是节点将日志应用到状态机，真正影响到节点状态。
4、脑裂问题
raft算法保证任一任期内最多一个leader被选出。在一个复制集中任何时刻只能有一个leader。系统中同时有多余一个leader，被称之为脑裂（brain split），这是非常严重的问题，会导致数据的覆盖丢失。在raft中，两点保证了这个属性：
- 一个节点某一任期内最多只能投一票
- 只有获得majority投票的节点才会成为leader
因此，某一任期内一定只有一个leader。
但是，在网络分割（network partition）的情况下，可能会出现两个leader，但两个leader所处的任期是不同的。
上图中，Node A、B和Node C、D、E可能由于网络问题出现了分割，因此Node C、D、E无法收到来自leader（Node B）的消息。
在election time之后，Node C、D、E会分期选举，由于满足majority条件，Node E成为了term 2的leader。
因此，在系统中貌似出现了两个leader：term 1的Node B， term 2的Node E。Node B的term更旧，但由于无法与Majority节点通信，NodeB仍然会认为自己是leader。
此时，有客户端往Node B发送了写请求，NodeB发现自己无法将log entry 复制到majority大多数的节点，因此不会告诉客户端写入成功。如果客户端往C发送了写请求，Node C是能将log entry 复制到majority大多数的节点，所以Node C所在的网络分区能正常接收请求。
当网络被修复后，Node B和Node A发现自己所在的Term为1，比Node C的term小，因此会退化为follower并同步集群数据。