6.824-lab2-Raft简述


Raft各阶段的描述

node有三个state:follwer candidate leader
所有节点一开始是follower state,如果followers没有收到leader的消息,那么他们可以成为candidate。
然后candidate请求其他节点投票(request vote),nodes将以投票方式回应,如果candidate获得了大多数
node的投票它将会成为leader。这个过程就是Leader Election。
现在,对系统的所有更改都要经过leader,每个更改都作为entry添加到节点的日志中。
log entry如果还未提交,就不会更新节点的值。要提交entry,节点首先将其复制到follower。
然后,leader等待大多数节点都写入了entry,写入之后会回应leader。该entry现在已在leader上提交(SET 5 从红色变成了黑色),当前节点状态为“5”。然后,leader通知follower这个entry已经提交。集群现在已经就系统
状态达成共识。此过程称为Log Replication。

Leader Election

在Raft中有两个控制选举的超时设置。首先是election timeout,选举超时是指follower等待成为candidate的时间。选举超时被随机设置为150毫秒到300毫秒之间。
在election timeout后,follower成为candidate(因为election timeout是随机的,所以有的follower会率先成为candidate),开始新的选举任期(term)。
成为candidate后会为自己投票(给自己投票了相当于投了一次票,就不会再给其他节点投票,意味着先转变为candidate就有了一票),并向其他节点发送请求投票消息。如果节点在本term还没有投票,那么它会投票给第一位向他要票的candidate。然后这个节点会重置其选举超时。一旦有一位candidate获得多数票,就成为leader。leader开始向其follower发送append entries messages。这些消息按照心跳超时(heartbeat timeout)指定的时间间隔发送。随后,follower会响应每个append entries message。这个选举任期将持续到follower停止接收心跳并成为候选人为止。

Re-election

当leader死了之后,超过了心跳超时,follower还没接收到心跳消息,follower在进行一个选举超时后成为
candidate向其他节点请求投票,成为新的leader。
要求多数票才能保证每届任期只能选举一位领导人。
如果两个节点同时成为候选节点,则可能会发生分裂投票。例如:四个node,有俩node同时先转换为
candidate,然后其他俩node给这俩candidate一人一票。这样每个candidate都是2票,此时平票。所有
节点将等待新的选举然后重试,进入新term选举leader。

Log Replication

一旦我们选出了leader,我们需要将系统的所有更改复制到所有节点,这是通过Append Entries来实现的(RPC)。当客户端send更改给leader,leader在下一次心跳时将更改发送给follower。一旦大多数follower接收到这个消息并回应leader,就commit这个entry,并向客户端发送相应。
细节:leader发送nextIndex与worker的日志下标进行匹配,如果匹配上了,worker会接收nextIndex之后的所有日志,返回成功给leader后,leader的nextIndex+=nextIndex+len(logs),matchIndex=nextIndex-1。leader会根据matchIndex数组里中位数更新commitIndex,当commitIndex>lastApplied,就会将日志存到channel中。同理worker会接收leader的leaderCommit(就是leader的commitIndex),worker更新commitIndex后也会把日志存到channel中。

Raft在网络分区时仍然work

让我们添加一个分区,将A和B(leader,term=1)与C(leader,term=3)、D和E分开。由于我们的分裂,我们现在有两位不同的leader。让我们添加另一个客户端并尝试更新这两个leader。一个客户端将尝试将节点B的值设置为“3”。节点B无法复制给大多数节点,因此其日志条目保持未提交状态。另一个客户端将尝试将节点C的值设置为“8”。这将成功,因为它可以复制给大多数。现在,让我们修复网络分区。节点B将看到更高的trem并下台。A和B都将回滚其未提交的条目,并与新leader的日志相匹配。

参考资料:

6.824课程表:https://pdos.csail.mit.edu/6.824/schedule.html
raft论文:https://github.com/OneSizeFitsQuorum/raft-thesis-zh_cn/blob/master/raft-thesis-zh_cn.md
raft可视化:http://thesecretlivesofdata.com/raft/
raft官网:https://raft.github.io/

热门相关:无量真仙   第一神算:纨绔大小姐   大神你人设崩了   第一神算:纨绔大小姐   第一神算:纨绔大小姐