分布式一致算法raft
【raft算法起源】
随着分布式系统的普及，系统内各存储节点的数据一致性问题成为分布式系统的关键点。raft算法是为了解决分布式系统中的数据一致性问题而产生的。除了raft外，还有其他的分布式一致性算法Paxos， ZAB等。
【raft术语】
| 名称 | 含义 |
初始值 |
属性 C(通用)/ L(leader专有) |
是否持久化 Y(持久化) N(非持久化) |
| leader | 中心节点 | NA | NA | NA |
| follower | 跟随节点 | NA | NA | NA |
| candidate | 候选节点 | NA | NA | NA |
| currentTerm | 当前周期 | 0 | C | Y |
| votedFor | 点赞同的节点ID | null | C |
Y |
| log[] | 日志条目数组；每个日志条目包含操作命令和生成该日志条目时leader的周期 | null | C | Y |
| commitIndex | 可以提交的日志索引 | 0 | C | N |
| lastApplied | 最近应用的日志索引 | 0 | C | N |
| nextIndex[] | 下一次给每个follower发送的日志索引 | null | L | N |
| matchIndex[] | 每个follower匹配的日志索引 | null | L | N |
【raft基本思想】
分布式系统中选举出一个中心节点leader，其他节点为follower；当客户端发送写请求时，交由leader处理（每个follower节点中记录了leader信息），leader生成logEntry记录并并行发送给每个follower，当集群过半节点完成logEntry记录后，leader执行提交操作并应用logEntry到存储层，执行成功后返回给客户端；当客户端发送读请求时，也由leader处理，保证读到最新的数据。
【几个关键点】
- leader的选举
每个节点维护一个minumElectionTime，超过这个时间未收到leader的心跳请求，节点进入选举状态，向其他节点发送VoteRequestRPC请求，请求中包含的信息如下， 收到请求的节点根据本节点的信息判断是否投票给请求节点，具体步骤如下，当某个节点收到半数以上的投票时，该节点成为leader并通过AppendEntriesRPC与follower保持通信。
pulic class ResponseVoteRPC {
boolean voteGranted; // accept or not
int term; // currentTerm of receiver
... // others
}
public class RequestVoteRPC {
int term;
int candidateId;
int lastLogIndex;
int lastLogTerm;
... // others
}
// implementation of receiver
ResponseVoteRPC voteFor(RequestVoteRPC req) {
... // parse req and get parameters
if (currentTerm > term) {
return new ResponseVoteRPC(currentTerm); // reject vote
}
if (currentTerm < term) {
currentTerm = term; // set currentTerm
return new ResponseVoteRPC(); // grant vote
}
if (currentLastLogTerm > lastLogTerm) {
return new ResponseVoteRPC(currentTerm); // reject vote
}
if (currentLastLogTerm < lastLogTerm) {
return new ResponseVoteRPC(); // grant vote
}
if (currentLastLogIndex > lastLogIndex) {
return new ResponseVoteRPC(currentTerm); // reject vote
}
return new ResponseVoteRPC(); // grant vote
}- 有序更新&日志同步
leader除了向各follower同步心跳包(AppendEntriesRPC请求，其中logEntries为空)外，还因更新操作向各follower同步日志(AppendEntriesRPC请求，其中logEntries非空，为待同步的操作日志)，为了保证各follower中操作日志的顺序同leader中的日志顺序完全一致，AppendEntriesRPC请求中增加了日志直接前驱信息，即本次同步日志的前一条日志的索引和周期，当follower收到请求后，查找本地是否有日志直接前驱信息，即根据前驱索引找到前驱日志再比较周期是否一致，如果匹配成功，则本次同步成功，否则同步失败，leader将前驱日志索引递减后重试，直到找到匹配的索引。
- 网络分区
当网络出现分区时，分区内的节点间可以通信，分区间的节点无法通信，如果这些分区都是可用分区，则会出现多个leader，最终导致数据不一致，因此需要规定一个可用分区（包含集群半数以上节点），比如5个节点A, B, C, D, E, 网络分区A, B, C为可用分区，网络分区D, E为不可用分区，此时集群还可以提供服务。
- 成员变化
当集群中有节点加入或退出时，即集群的成员发生了变化，需要一个过渡期防止脑裂以及数据不一致的问题。成员信息的变化由leader通过AppendEntriesRPC请求的方式同步给各follower，同步的成员包括两部分：新集群成员和老集群成员，每个follower收到该请求后，使用新集群的成员信息，联合一致性由新老成员共同保证。
【参考资料】