分布式一致性协议之Raft(二)
在「分布式一致性协议之Raft(一)」中,描述了Raft
在正常情况下的算法流程,但当节点崩溃的情况下会有一些异常,影响状态机顺序的执行相同的指令。
领导人选举安全(Election safety)
选举安全性,即在一个任期内最多一个领导人
被选出,如果有多余的领导人被选出,则被称为脑裂(brain split)
,如果出现脑裂
会导致数据的丢失或者覆盖。Raft
通过下面两点保证了不会出现脑裂的情况
;
- 一个节点某一任期内最多只能投一票;
- 只有获得大多数选票才能成为领导人;
通过增加约束避免了脑裂
的情况出现,保证了同一时间集群中只有一个领导者
。但是当一个节点崩溃了一段时间,他的状态机已经落后其他节点很多,突然他重启恢复被选举为领导者
,这个时候,客户端发来的请求再经由他复制给其他节点的状态机执行,就会出现集群状态机状态不一致的问题。
其他算法可能会同步落后的日志给领导者,然后在由领导者复制日志给其他节点,但是Raft
认为这样会增加算法的复杂性,直接放弃了这种方法,而是采用拒绝
投票给那些日志没有自己新的节点。
通过比较两份日志中,最后一条日志条目的索引值和任期号,来定义谁的日志比较新。如果两份日志最后的条目的任期号不同,那么任期号大的日志更新。如果两份日志最后的条目任期号相同,那么日志比索引大的日志新。
拒绝
日志比自己旧节点投票是基于这样一种思考,要当选领导者,就必须获得大多数节点的选票,意味着他必须至少比大多数节点的日志新或者一致,这样拒绝比自己旧日志节点的投票请求,就保证了状态比大多数节点落后的节点是不会当选领导者。
如果一个领导者
把日志复制到大多数其他节点,在应用到状态机之前崩溃了,新选出的领导者,是不知道被复制到大多数节点的日志是否应用到了状态机。
(a) 中,S1 是领导者,部分的复制了索引位置 2 的日志条目;
(b) 中,S1 崩溃了,然后 S5 在任期 3 里通过 S3、S4 和自己的选票赢得选举,然后从客户端接收了一条不一样的日志条目放在了索引 2 处;
(c)中,S5 又崩溃了;S1 重新启动,选举成功,开始复制日志。在这时,来自任期 2 的那条日志已经被复制到了集群中的大多数机器上,但是还没有被提交;
(d) 中,S1又崩溃了,S5 可以重新被选举成功(通过来自 S2,S3 和 S4 的选票),然后覆盖了他们在索引 2 处的日志。注意:虽然s2复制日志过半,但是S5节点的任期号大,日志新,是可以接收S2选票
;反之S1在崩溃前把新接收到的日志复制到大多数机器中,如(e)所示的情况。
(e) 中那样,那么在后面任期里面这些新的日志条目就会被提交(因为S5 就不可能选举成功)。 这样在同一时刻就同时保证了,之前的所有老的日志条目就会被提交。
候选者和跟随者安全性
候选者
,跟随者
奔溃以后,领导者就是简单的周期性的发送RPC
请求,如果重启发生在节点处理完日志复制,响RPC
请求之前,收到一样的RPC
请求正常返回即可,没有任何问题。如果崩溃时间太长,重启以后落后其他节点日志太多,将会采取快照
的方式进行恢复。
Raft
的RPC
请求是幂等的。
可用性
Raft
的要求之一就是安全性不能依赖时间:整个系统不能因为某些事件运行的比预期快一点或者慢一点就产生了错误的结果。但是,可用性(系统可以及时的响应客户端)不可避免的要依赖于时间。这个时候就又会有一些限制;
- 服务器故障的时间必须比消息交换的时间长,否则每当一个节点要收集到足够多选票的时候就宕机了,新一轮的投票又重复这个过程,导致足够的时间选出领导人。
- 广播的世界必须小于选举超时时间一个数量级,这样领导者才能发送稳定的心跳阻止跟随者进入候选人状态。
- 当领导者崩溃后,整个系统在大约等于选举超时时间中不可用,所以平均故障间隔时间要大于选举超时时间几个数量级,系统可用性才比较高。
一般来说,广播时间在10毫秒左右,选举超时时间在300毫秒左右,服务器平均故障时间都大于一个月。