6.824-lab2-Raft简述

首页>焦点 > 正文
2023-03-27 14:17:13

来源:博客园

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的日志相匹配。

Raft论文中对节点的定义

所有servers的持久化变量:

currentTerm intvotedFor    intlogs      []LogEntry

所有servers的可不持久化变量:

// 正常情况下commitIndex与lastApplied应该是一样的,但是如果有一个新的提交,并且还未应用的话last应该要更小些commitIndex int // 状态机中已知的被提交的日志条目的索引值(初始化为0,持续递增)lastApplied int // 最后一个被追加到状态机日志的索引值

leader的可不持久化变量:

// nextIndex与matchIndex初始化长度应该为len(peers),Leader对于每个Follower都记录他的nextIndex和matchIndex// nextIndex指的是下一个的appendEntries要从哪里开始// matchIndex指的是已知的某个follower的log与leader的log最大匹配到第几个Index,已经applynextIndex  []int // 对于每一个server,需要发送给他下一个日志条目的索引值(初始化为leader日志index+1,那么范围就对标len)matchIndex []int // 对于每一个server,已经复制给该server的最后日志条目下标
// AppendEntriesArgs 由leader复制log条目,也可以当做是心跳连接,注释中的rf为leader节点type AppendEntriesArgs struct {   Term         int        // leader的任期   LeaderId     int        // leader自身的ID   PrevLogIndex int        // 预计要从哪里追加的index,因此每次要比当前的len(logs)多1 args初始化为:rf.nextIndex[i] - 1   PrevLogTerm  int        // 追加新的日志的任期号(这边传的应该都是当前leader的任期号 args初始化为:rf.currentTerm   Entries      []LogEntry // 预计存储的日志(为空时就是心跳连接)   LeaderCommit int        // leader的commit index指的是最后一个被大多数机器都复制的日志Index}type AppendEntriesReply struct {   Term     int                // leader的term可能是过时的,此时收到的Term用于更新他自己   Success  bool               // 如果follower与Args中的PreLogIndex/PreLogTerm都匹配才会接过去新的日志(追加),不匹配直接返回false   AppState AppendEntriesState // 追加状态}

Receiver实现:1、term小于currentTerm返回false2、若日志中不包含index 值和 Term ID 与 prevLogIndex 和 prevLogTerm 相同的记录,返回 false3、如果日志中存在与正在备份的日志记录相冲突的记录(有相同的 index 值但 Term ID 不同),删除该记录以及之后的所有记录4、在保存的日志后追加新的日志记录5、若 leaderCommit > commitIndex,令 commitIndex 等于 leaderCommit 和最后一个新日志记录的 index 值之间的最小值

type RequestVoteArgs struct {   // Your data here (2A, 2B).   Term         int // 需要竞选的人的任期   CandidateId  int // 需要竞选的人的Id   LastLogIndex int // 竞选人日志条目最后索引   LastLogTerm  int // 候选人最后日志条目的任期号}type RequestVoteReply struct {   // Your data here (2A).   Term        int       // 投票方的term,如果竞选者比自己还低就改为这个   VoteGranted bool      // 是否投票给了该竞选人   VoteState   VoteState // 投票状态}

Receiver实现:1、如果竞选者任期比自己的任期还短,那就不投票,返回false2、如果当前节点的votedFor为空,且竞选者的日志条目跟收到者的一样新则把票投给该竞选者

6.824的lab2需要实现上述规则

参考资料:

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

标签:

THE END
免责声明:本文系转载,版权归原作者所有;旨在传递信息,不代表热讯制鞋网的观点和立场。

相关热点

新华社电 上海市文化和旅游局近日发布《上海市密室剧本杀内容备案管理规定(征求意见稿)》,并截至12月8日面向社会公众广泛征求意见。这
2021-11-19 13:46:03
《中国证券报》17日刊发文章《备战2022 基金经理调仓换股布新局》。文章称,距离2021年结束仅剩一个多月,基金业绩分化明显。部分排名靠前
2021-11-19 13:46:03
交通运输部办公厅 中国人民银行办公厅 中国银行保险监督管理委员会办公厅关于进一步做好货车ETC发行服务有关工作的通知各省、自治区、直
2021-11-19 13:45:58
新华社北京11月17日电 题:从10月份市场供需积极变化看中国经济韧性新华社记者魏玉坤、丁乐读懂中国经济,一个直观的视角就是市场供需两端
2021-11-19 13:45:58
全国教育财务工作会议披露的消息称,2020年,中国国家财政性教育经费投入达4 29万亿元,占GDP总量的4 206%,我国国家财政性教育经费支出占G
2021-11-19 13:45:48
如果你也热爱“种草”,前方高能预警!让你心心念念、“浏览”忘返的网络平台,可能早已成为一块块“韭菜地”。近日,据《半月谈》报道,有...
2021-11-19 13:45:48
日前,工业和信息化部印发《“十四五”信息通信行业发展规划》(以下简称《规划》),描绘了未来5年信息通信行业的发展趋势。《规划》指出...
2021-11-19 13:45:40
本报讯(中青报·中青网记者 周围围)2021年快递业务旺季正式拉开帷幕。国家邮政局监测数据显示,仅11月1日当日,全国共揽收快递包裹5 69
2021-11-19 13:45:40
人民网曼谷11月17日电 (记者赵益普)17日上午,中国援柬埔寨第七批200万剂科兴新冠疫苗抵达金边国际机场。当天,柬埔寨政府在机场举行了
2021-11-19 13:45:35
金坛压缩空气储能国家试验示范项目主体工程一角受访者供图依托清华大学非补燃压缩空气储能技术,金坛压缩空气储能项目申请专利百余项,建立
2021-11-19 13:45:35
视觉中国供图42亿立方米据有关部门预计,今年山西煤炭产量有望突破12亿吨,12月份山西外送电能力将超过900万千瓦,今冬明春煤层气产量将达4
2021-11-19 13:44:34
14省份相继发布2021年企业工资指导线——引导企业合理提高职工工资今年以来,天津、新疆、内蒙古、陕西、西藏、山东、江西、山西、福建、四
2021-11-19 13:44:34
中新网客户端北京11月18日电 (记者 谢艺观)“一条路海角天涯,两颗心相依相伴,风吹不走誓言,雨打不湿浪漫,意济苍生苦与痛,情牵天下喜
2021-11-19 13:44:31
近日,交通运输部等三部门发布《关于进一步做好货车ETC发行服务有关工作的通知》。通知提到,对不具备授信条件的用户,商业银行可在依法合
2021-11-19 13:44:31
欧莱雅面膜陷优惠“年度最大”风波 涉及该事件集体投诉超6000人次美妆大牌双十一促销翻车?近日,因预售价格比双十一现货贵出66%,欧莱雅
2021-11-19 13:44:13
43 6%受访者会在工作两三年后考虑跳槽54 3%受访者认为跳槽对个人职业发展有利有弊如今对不少年轻人来说,想对一份工作“从一而终”不太容易
2021-11-19 13:44:13
超八成受访青年表示如有机会愿意开展副业 规划能力最重要64 4%受访青年指出做副业跟风心态最要不得如今,“身兼数职”已成为年轻人当中的
2021-11-19 13:44:01
发展氢能正当其时【科学随笔】氢能是一种二次能源,它通过一定的方法利用其他能源制取,具有清洁无污染、可储存、与多种能源便捷转换等优点
2021-11-19 13:44:01
“千杯不醉”的解酒“神药”能信吗?专家:网红“解酒药” 其实不算药俗话说,“酒逢知己千杯少”,酒一直是国人饭桌上至关重要的存在。尽...
2021-11-19 13:43:57
最新文章

相关推荐