Raft 解读

Raft 的作者其实对 Paxos 研究得很深,毕竟 Paxos 基本上就是共识算法的代名词,建议在了解 Raft 之前先看看 Paxos,因为 Paxos 里面有一段从单点开始完整的推断共识算法的正确性和必要性的过程,方便建立一种对共识算法上直觉的认同。Raft 论文最好看作者的博士论文,那个比较完整。

leader election

Raft 有 Term 的概念,把时间每分成了一个个的任期,每个任期开始是选举过程。Raft server 有三种角色,Candidate 就是选举中的状态,Leader 是当选的状态,Follower 是服从并选择接受 Leader 的 Log 的状态。

[raft server state]

其实可以把选主看作一个 basic Paxos,大家对 leader=? 达成一致,触发的条件是超时和初始化的时候,term 就是类似于 Paxos 的 propose number,和 basic Paxos 不一样的是每个 term 只能投一个人,所以每个 term 不会有冲突,只有一个人会当选,但是会有平票的问题,大家用同一个 term 选举的情况下就会发生(比如说大家都投自己,谁都不接受谁),所以为了减少冲突,把重试的时间随机化,快速超时的人能拿到高 term,并且其他慢速超时的 candidate 会服从这个先拿到下一个 term 的 leader。成为 leader 的标志是收到了大部分人的服从(3/5 或者 2/3)。

[raft terms]

log replication

[raft log conflicts]

log 不一致的就以上几种情况,可能少了 entry,可能多了没 commited 的 entry,可能又少了 entry 还多了没 commited 的 entry,log 不一致的情况就这几种。index term 能唯一确定一个 entry,如果一个 entry 确定,之前的也确定了。基于上面的性质,如果 entry commited 之前的就是都 commited 了。这个通过 append 的 prev index prev term,来保证这个特性。解决方法是在 AppendRequest 里面带上新的 entry 前的 index 和 term(在 leader 那里存的前一个),如果这个 entry 不在 follower 里面的话,就拒绝追加新 entry,然后 leader 就要用前一个 index 尝试,直到开始出现 match 的点,有点像 git tree 里面开始产生分支的那个 base,这个过程一直减少自己保存的 follower 的 nextIndex,一直到获得和自己 match 的最后一个 index 开始追加复制自己的 log。也就是说这样会强迫所有的 follower 复制主节点的 log,这里有一个按 term 回溯 base 的方法,但是这个优化作者认为有点多此一举,毕竟错误发生的情况比较少。这里会有一个问题(啥问题),后面会通过选举的时候加上限制解决。

这个问题就是,新的 leader 可能没有之前 commited 的 log,然后修改了其他 follower 的 log,导致每个 state machine 执行的命令是不一致的,所以要加一个约束,在投票的时候,新的 leader 必须包含之前 commited 的 log,这个保证就需要通过定义 entry 的 update-to-date,在投票的时候拒绝比自己老的 leader 当选。

safety

这个问题被称作 safety,为了解决这个问题 update-to-date 怎么定义呢?比如下面这个例子,如果 S3 挂了,其实 index 5 已经 commited 了,但是没有办法确定 index 5 的这个 log 是否 commited 了。所以要选个最可能包含所有 log 的做 leader。

[raft not commited]

先比 term,再比 log 数量,按顺序比,有点像字符串比较,这样可以确保 leader 有其他 follower 的 entry。没有大多数人的又新又全就无法成为 leader。

commit from previous entry

如果一个 leader 在 commit 之前 crash 了,并且新的 leader 没有已经在大多数节点上的 entry 可能会覆盖掉本该 commit 的 entry。

比如这图,如果是 (d1) 的情况,3 就会把 2 盖掉,但是实际上 2 本该 commited 了,但是在 commit 之前 S5 可能在 term 5 成为了主(这个没有违背上面的 upda-to-date 因为 3 确实比 2 要新,并且可以从 S2, S3, S4 那里获得选票)。

[raft conflict 2]

光看数量,没办法替之前 term 的 entry commit,因为 d1 的情况,可能就把 2 盖掉了。只有 term 4 的时候 4 commit 了(当前的 term 可以 commit)才能替之前 term 的 entry commit(实际上间接 commit 了,这个可以证明),这样 term 3 就不会成为主,就不可能盖掉 2。

总结一下,在 Raft 中 leader 不会 commit 之前 term 的 entry,只 commit 当前 term 的 entry。当前 term 的 entry commit 了,之前 term 的 entry 就间接 commit 了。

持久化数据

当前的 term 和 vote 。

membership change

[raft conf change]

raft conf change 有几个主要阶段,其中 C(old)+c(new) 的情况下,需要服从两个 conf 的大多数,并且,每次只能一个一个的增加 server 和 减少 server。

参考文献

Donate comment here