0%

Raft算法学习笔记

记录Raft算法中的细节:

leader选举随机超时机制

大于两个candidate参与选举时可能导致选票分散,没有candidate获得大多数选票。condidate上会出现选举超时的情况,candidate会增加自己的term并开启新一轮选举。

如果每个candidate的超时时间一致,新一轮选举依旧会出现投票分散的情况,因此每个candidate的超时时间会在一个范围内随机选取。

日志匹配性

不同节点上的日志条目若拥有相同的term和index,那该条目及其之前的条目都是一致的。

首先给定的term和index的条目只会由唯一确定的leader下发,且leader不会覆盖或删除自己的条目,因此该条目在各节点上都一致。此外下发请求会包含leader中上一个条目的term和index,只有其与follower本地的上一个条目一致时才会被接收,因此之前的条目也都是一致的。

通过比较term和index,follower发现本地条目与下发请求不一致时会拒绝请求。leader会维护每个follower的nextIndex,下发请求被拒绝时会回退nextIndex,并下发上一个条目,重复此过程直到某个条目被follower接收。follower接收后会使用下发的条目覆盖本地条目,因此系统能够自动收敛。

日志提交方案

假设先前term中有一条目已在多数节点上被存储,若leader在得知此信息后将该条目提交,仍有可能出现该提交条目未来被覆盖的情况,导致不同节点的执行结果不一致。

为保证安全性,Raft只会提交当前term中被多数节点存储的term,并利用日志匹配性推断先前的条目均被多数节点存储。该策略牺牲了一定的实时性,推迟了先前term中条目的提交时间。