您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

包教包会!用一张白纸教你推导出 RAFT 算法

时间:2020-12-08 12:19:24  来源:  作者:
包教包会!用一张白纸教你推导出 RAFT 算法

 

作者:nolanyang,腾讯 PCG 后台开发工程师

分布式共识算法中,raft 主打的就是易理解性,近年来随着业界对算法的开发,raft 算法的应用也被大大拓展。raft 的论文,先描述了算法协议,再用反证法为主的多种证明方法证明其正确性,并没有给出完整的算法推导过程,因此很多同学多次阅读论文后,对算法的掌握心里还是没什么底,而闭着眼睛用组件总是有点发虚的。本文从一个故事开始,给大家模拟推导一遍 raft 协议中的核心规则是怎么构建出来的,希望能让更多的同学有动力去理解和应用分布式共识算法。感谢 raft 论文翻译项目为我们高效阅读论文提供了很大帮助。
项目地址:https://github.com/maemual/raft-zh_cn

一、故事缘起

故事要从一次具有历史意义的时空之旅开始,5 个家学渊源的家庭,以更准确的记录下 3000 多年的文明兴衰史为目标,穿越到华夏文明的起点,他们要各自建立起以自己家族为中心的村落,通过自己的历史小村一代一代将发生的历史事件记录并传承下去。出发前 5 个历史小村的第一代村长进行了一次拟定这个宏伟计划的会议。会前他们先随手在白纸上贴上了一张古代地图,标注了自己村子的起始地点。白纸如图:

包教包会!用一张白纸教你推导出 RAFT 算法

 

图1 5村起始位置(图片来源于网络)

准确记录历史在很多时代都是一件危险的事情,这也是为什么 5 个村庄需要分散在天南地北的主要原因,司马村长提出了他们的第一个目标,任何时代只要还有三个村落能正常运作,就要能够准确一致的记录下这个时代的事情。5 个村长彼此间都无比信任,也坚信他们各自的历史小村无论何时都不会在规则之外篡改记录下来的信息。

记录历史事件自然需要纸张什么的,远古时代编年历法不一定统一,各村落通信周期也不稳定,村长们很快商量出了一个方案,统一使用编好页码的记事本进行记录,1 件事情记录在 1 页上,这样至少事情的先后顺序不会轻易搞错了。然后左村长提出一个关键问题,纸质材料和油墨虽然修改方便,但是不易保存,就算在历史长河中不被损毁,千年过去最早的记事本也没法再看了,根据他看过一部科幻小说,左村长提出,记事本上的事情只要村落之间“达成一致”了,就可以把事情按顺序刻在石碑上埋到地底下,这就是人类目前最有效的保存信息的方法了,这样做的缺点就是刻在石碑的内容就不好更改了。大家纷纷表示同意,司马村长把这些信息记录在他的大白纸上:

包教包会!用一张白纸教你推导出 RAFT 算法

 

图2 记录历史的主要工具:记事本和石碑

二、前提条件的制定

讲完这些,大家都把注意力集中到了刚才左村长无意间提出来的“达成一致”这四个关键字上。班村长首先提出来,如果每个时期只有一个村落负责把发生的事件记录下来而且保持所有村落都是 1 页上面只记录 1 个事件其他村落只负责接收这个村落的消息把接收到的消息记录在记事本对应的页码上,那记事本上每一页上的事件保持一致的难度就小很多了。如果多个村落同时记录历史事件,然后通过互通消息来协调一致,难度就会大很多,处理每一页上的记录冲突也会需要很多时间。

大家一商量,虽然有一点争议,但最终还是认同了这个提议,多点记录确实比较难,最终效率也不一定高。左村长接着就抛出了两个名词作为约定,“主家”即当前负责记录的村子,“分家”即当前接收主家消息的村子。左村就主动承担第一期的主家任务了。接下来就是司马村长发话了,前面他也说过,目标是任何时代即使有两个村落被灭,记录也要准确的传下去,左村长的方案里面,每个时代负责记录的村子发生意外的时候,如果他们记在石碑上的事件,别的村子还没收到,那记录的事件就会出现不一致了,以后之前被灭村子的石碑被后人挖出来以后,历史事件可能出现矛盾,当然这还是最简单的情况了,更复杂的这一类情况还能一口气说出很多。

大家开始继续思考这个问题,顾村长第一个发表观点,一件事情只要有 3 个村落记录下来,那之后任何时刻失去任意两个村子,这件事情都不会丢,因为最差也是还有一个村落记下了这件事。所以说一件事情只要有 3 个村落在记事本上记下来了,那这件事情就可以被放心的刻到石碑上了,一个事件确认可以被记录在石碑上了,就称这个事件安全了。至于谁来统计有几个村庄记录了某一件事情,那自然是主家了。左村长的方案里面只有主家负责发出消息,其他从家都只能在主家发来消息以后做相应记录,再让信使把记录的情况发回给主家,主家根据回来的信使的消息自然可以统计有多少村落记记录下了这个事件了,主家在后面的通信中再把哪些事件可以刻到石碑上了,带给各村,那就很稳妥了,所以主家要统计一份各村已经记录下的事件列表

司马村长一听立刻就说这还不够:要是左村长记录下来的第一页上的事情,简称事件 1,同步给了顾村和欧阳村,但没传给另外两个村子,然后左村记录的事件 2,又只同步给了司马村和班村,这时候左村长是可以大大方方刻石碑了,但要是刻完石碑就被灭村,那剩下 4 家选谁做主家,都没有两件事情完整的记录,要把剩下 4 家手上的记录合起来又要非常复杂的通信规则了。情况就像图上这样(填了蓝色代表这页记录了事件):

包教包会!用一张白纸教你推导出 RAFT 算法

 

图3 可能出现的记事本有空页的情况

左村长这时也提出一个问题,就算主家一直没出什么问题,过了一千年,那主家记录各个事件在各村的记录情况的列表也是长的看不懂了,给各家补齐少记录的事件也是不知从何下手啊。一时间与会众人难以定出个结论来,这时候欧阳村长终于发言了:太复杂的事情不好分析,我们就简单点处理吧,每次同步事件的时候,有 3 个以上村落都有着从开始到当前页码都相同的记录时,才算安全,才可以把这件事刻到石碑上,这样任意 2 个村被灭,都会至少有一个村保留所有可以被刻到石碑上的事件,下一轮只要能把满足这样条件的村庄选出来做主家,那这个新的主家就能带领剩下的分家把之前的记录传承下去了。

另外这样做了以后,任何分家接收到主家传来的消息,如果发现前面有缺漏的事件,那也不用再跳过前面的页码来记录当前事件了,因为记下来了也不能作为当前事件的确认方被统计计数,也就是说记事本中间再也不会有空洞了,而主家也不用保留超级复杂的统计列表了,只要记一下各个分家最后记录下来的事情是第几页的事情就能掌握全局情况。其实这时候还得出了一个阶段性成果:因为记录事件的时候,要确认前面的事件是不是都一样,只有都一样才能记录下来,只要一个时期只有一个村庄做主家,那么两个和主家正常通信的分家的记事本上,只要在任意一页上“相同”,那这页之前的内容肯定是“相同”的了,任意分家和主家之间也满足这个结论

这一下大家都开心了,这个办法简单易懂,司马村长立刻把刚才讨论的结果记录到大白纸上:(到这里大家讨论出来的两个最关键的前提条件:只有一个主家负责记录事件,其他分家只负责接收主家的消息;记事本不能有空洞。这两个前提条件并不是靠推理得出的,而是大家希望简化后面的规则提出的假设,如果没有这两个条件,那大家后面可能会推导出别的分布式共识算法哦)

包教包会!用一张白纸教你推导出 RAFT 算法

 

图4 最初提出的复制事件的规则

三、解释解释什么叫做“相同”

但是很快大家就发现了新的问题,确认过往所有的记录事件是不是都“相同”,这可不容易做啊,先不说确认“相同”是不是就是比较记录的每一个字都一样,只要持续记录很多年,比较一次也要花上太多时间了吧,每次有新的事件都要从头开始比较,这谁受得了?司马村长立刻发表了高论:用我小学二年级学过的最简单的数学归纳法就可以破这个问题了,对于在区间(0,N]的任意 n, 都满足元素 S1(n)== S2(n)且 S2(n-1)== S1(n-1),那么在[0,N]区间内,S1 和 S2 这两个数组每个位置上的元素都是相等的。

在我们这个问题里,说人话就是每一个新事件记录的时候,主家在同步消息的时候除了当前事件还要带上前一页记录的事件,收到消息的分家要比较一下前一页上的事件和自己记录的是不是“相同”,只有前一页的事件“相同”才记录新一页的事件,只要从头一开始就这么做,那么每次能顺利记录下新事件的村落,前面记录的事件和主家肯定是都“相同”的。大家纷纷拍案叫绝,只有顾村长问了一声,要是分家接到消息的时候,发现主家传来的前一页事件和自己这里记录的不一样或者根本还没记录过这一页的事情,那可怎么办呢?

欧阳村长立刻发话,还是用简单的方法,上面的情况,分家直接回复主家现在不能记录这一页上的事件,主家接到失败的消息就把前一页的事件作为这个分家下次要同步的事件在下次发消息的时候发前一页的事件,而下次发消息附带的也就是前前页的事件了,要是这次同步能成功,那就继续尝试同步新的事件,反之,就以此类推,继续往前尝试更靠前的页码上的事情,主家再单独保存一份要给各分家下次尝试同步哪一页的列表就能轻松做好这个事情了。这一波讨论完,大家一下子都安心了,最重要的主家怎么把自己记录下来的事件复制给分家的主要机制都讨论出来了,司马村长开心的在白纸上开始了记录。他先画了一张草稿说明以后主家怎么同步消息给分家:

包教包会!用一张白纸教你推导出 RAFT 算法

 

图5 主家发送同步事件的基本规则

司马村长刚画完示意图,左村长就发现了问题:就算只比较前一页的事件一样不一样,也没有百分百的把握啊,远古时期年历容易出现偏差,地名也不一定对齐,传递消息时间又长,万一不同的地方连续出现类似的天灾一类的事件,说不定记录都差不多,前面反复说到的事件“相同”的这个“相同”要有明确的判断标准才行啊。

大家再次陷入沉思,大概五分钟之后,又是欧阳村长说话了:要简单判断事件是不是“相同”,要把我们之前一个没用上的关键信息给用起来了。按照我们之前的设定,理想情况下一个时期只会有一个主家负责记录事件,如果主家出事了,分家都收不到主家的信息了,可能选出一个新的村落做主家,每一个主家上任后负责记录的这段时间就叫主家的任期好了,我们给每一个任期遍一个号,叫任期号任期号从 1 开始,每次新上任的主家的任期号就是上一个任期号加 1,这样每段任期就有唯一的任期号了。

每一个主家记录事件的时候,给每个事件都记上自己当时的任期号并在同步事件的时候都带着事件对应的任期号,分家收到事件的时候,记录的时候也把对应的任期号记录在那一页上,这样下来,只要所有主家保证不修改自己之前记录下的任何一页上的事件,那可以简单推导出来:同一页上标注的任期号相同,这一页的记录就一定相同。这时候顾村长表示这通操作不太理解了,这时不怎么说话的班村长拿起记事本给他演示了一下:

包教包会!用一张白纸教你推导出 RAFT 算法

 

图6 记事本每一页记录事件的样式

正常情况下任何时期我们里面的主家只有一个,对应的任期号 T 也只有一个,主家在第 N 页上记下事件的时候带上了自己的任期号 T,相当于告知大家这页的事件是我写的,只要主家保证自己记录下来的事件,自己在这一个任期内绝对不会改,那分发出去的任何一页上的事件,只要任期号相同就代表是同一个主家在同一个任期记录下来的,这个主家在这个任期里又绝不可能回去改这个事件,那这页上的事件也就是相同的了

所以我们以后表示一个事件只要用 S(N,T)这种形式就可以了,页码 N 和任期 T 都相等,事件一定“相同”,以后这就是事件“相同”的定义了,事件相同也就再也不用打引号了。顺带一提,主家每次同步过来的事件里的任期号,分家也要找个地方记下来,这样下次分家被选为主家的时候,才能正确的把任期加 1 哦。说到这里,大家都懂了,主家向分家同步记录下来的事件的步骤都差不多出来了,司马村长也飞快的完成了这阶段的记录。(图片请双击放大浏览)

包教包会!用一张白纸教你推导出 RAFT 算法

 

图7 初步完成了复制事件机制的设计

司马村长记录的同时还补上了主家怎么确认一页上记录的事件是不是可以被安全送去刻到石碑上的相关操作规则,还把主家已经确认的最大安全页码加在了主家传给分家的消息里,这样分家也能结合自己的情况确定自己可以刻到石板上的最大页码了。为了方便刻石碑,还规定了每个村落把已经刻好的最大页码以及可以安全刻下来的最大页码分别记录一下

最后他还提出来,可能以后有些人会向村落爆料一些事件,如果这时候这个村落不是主家,又不知道主家现在是谁,那还挺尴尬的,所以每次主家传消息的时候记得报一下自己是谁,这样就可以引导爆料群众直接去主家那里直接爆料了。这些设定都很容易理解,大家纷纷直呼内行。不过班村长还是指出了笔记上几处语句不通顺以及字写错的地方。

四、选举争霸

讨论到这里,大家都挺累的了,司马村长和欧阳村长相视一笑,有了这些设定,是时候短兵相接,快速讨论一下选举主家的规则了吧。

司马:穿越过去以后,要是我们一段时间没收到左村长的消息,我们是不是就可以开始选新的主家了,但是万一这段时间其实是左村长觉得没发生什么值得记录的事件,那就不太好了,我们到时候搞出两个主家来,前面的规则都破了。

欧阳:简单处理,主家的人,就算没有要记录的事件发生,也最少每个月给所有分家发个消息,就算消息里面没有要记录的事件也要发,算是报个平安吧。哪个分家连续三个月没收到主家的消息,再发起选举不迟

司马:发起选举是容易,我们收到选举要按什么规则投票呢?按照前面的思路,我们可是要选出一个拥有前任主家进行过安全确认的所有事件的村落出来传承的哦。

欧阳:简单处理,任期号代表时代只增不减,记事本上有记录事件的最大页码上的任期号谁大,谁的记事本就内容更全,如果任期号一样大,那最大页码大的记事本就更全,要是页码和任期号都一样,那记事本就一样全。每个村庄只投票给记事本最少和自己一样全的村庄不就可以了么。

司马:那得了几票,就可以做主家了呢?

欧阳:简单处理,就是包括自己在内的 3 票啊,前面我们设定过了,最后一个被确认安全的事件,包括主家最少有 3 个村庄已经记下来了。记录下最新事件的村子就是有最全内容的村子,包括主家在内有 3 个这样的村子。就算剩余其他 2 个村庄还没来得及记下最新的事件的时候,主家被灭了,记下最新事件的 2 个村庄里面不管谁参与选举,谁就能得到包括自己在内的 4 票,反之,没记下最新事件的 2 个村子参与选举,最多只能得 2 票。我们设定的最坏情况也就是同时再被灭掉一个记录事件最全的村子,那这时候剩下唯一一个记录最全的村子还是能够得到包括自己在内的 3 票支持,成功当选新的主家。

总结起来说就是不管被灭几家,只要能赢得 3 票上一个任期的主家能确认安全的事件,在新选出来的主家记事本里面肯定有。我图都给你画出来了:

包教包会!用一张白纸教你推导出 RAFT 算法

 

图8 记录“最新”事件的村庄能赢得竞选

司马:不对啊,你的图里面,我只要拿到你和班村的票就能做主家了,万一顾村没给我投票,而是也发起了选举,他也能赢得你和班村的选票,也是 3 票也能成为主家,那不就 2 个主家了吗

欧阳:这个问题连简单处理都不需要了,你们发起选举的时候,先把自己的任期号增加一下,变成自己当选以后要用的任期号发出去,每个村子在一个任期号里最多投一次票记录下来每个任期号是投票给了哪个村子。这样你拿到 3 票时候,顾村长再开始发起投票,他的任期号最多和你一样,他是拿不到其他已经投过票的村子的支持的。除非再过三个月,期间顾村长都没收到过你同步的任何消息,他再次增加任期号发起选举才有机会再当主家。而如果这三个月里面,你真的什么事都没记下来,那顾村才可能当选,但是任期号也增加了,他用的还是唯一任期号,我们的机制也继续维持着,没什么影响。

司马:还有问题啊,你刚才说的是我先拿到 3 票的情况,问题是我和顾村可能是同时发起选举的,万一我们一个得到了你的支持,一个得到了班村的支持,那我们岂不是这一轮不分胜负,到下一轮我们再同时发起,又是各得两票,岂不是没完没了,我们时间都花在选举上了,怎么好好记录历史啊。

欧阳:这个也是可以简单处理的,我们每家每次发起选举的时间不要那么固定嘛。比如说你有时候是 3 个月零 7 天收不到任何消息发起选举,有时候是 4 个月发起选举,顾村他们有时候是 3 个月零 14 天收不到消息发起选举,有时候是 4 个月零 7 天发起选举,你们发起选举冲突的概率不就低了?

左村长:你们别太过分了,万一上面那个情况里面,我们村不是被灭了,只是信使都被拦截了,我可是一直都在辛苦的记录着各种事件,只是没法同步给你们,我自己也没法确认新记录的事件是不是可以被刻到石碑上。那三年后我龙王归来,哦不是,我找回信使,把我这隐忍三年记录下来的事件传递给你们,你们认还是不认?

欧阳:简单起见,不管你是修罗还是什么神医,我们都不认,因为你的内容合进来,我们还要要保持一致太复杂了,而且你那三年记下来的内容又没被安全确认过,你也不敢刻在石碑上,你回来以后乖乖接收我们补给你的安全的事件,去刻你的石碑就完事了。哪一页开始,你记录事件的任期号和新主家不一样了,你就从这一页开始把后面的内容都划掉啊

左村长:我 TM 什么时候说过修罗、神医什么的了?而且我们之前定的规则里面,也没说我这个归来龙王,哦不,我这个归来主家不能继续同步记录的事件给你们啊!

欧阳:简单处理,我补个通用规则,反正同步事件和发起选举两种消息里面都带有任期号这个信息了,任期号只增不减,更大的任期号代表更新的时代,所以我宣布收到的消息里面,任期号小于自己之前记录下来的,一律拒绝,任期号大于自己之前的,一律把自己记录的任期号更新为接收到的任期号,然后再根据之前的设定操作,谁赞成,谁反对?

左村长:我之前是主家,我收到你们的消息里面的任期号比我自己的大,我也要听你们的吗?

欧阳:简单处理啊,不管你是主家,还是你发起选举做了候选人,收到的消息里面的任期号比你们自己的大,就自觉一点,主动把自己村的地位降到分家,不就可以了吗?因为你们都错过了至少一个时代了,还想继续做主家,别人岂不是都要配合你们,这时候说不定别人好多你们错过的事件都刻到石碑上了。顺便说一下啊,刚才我已经设定了每家等待个一定范围内的随机时间再发起选举的规则,选举冲突不容易发生了,我们刚穿越回去那会儿,也不用提前指定谁做第一个主家了,也用这种选举机制来选吧,这样左老师你压力也不用那么大了哈。

左村长:。。。

大家停下来消化了一下前面对话的内容,发觉欧阳村长说的这一套还真是能解决很多问题,司马村长开始整理笔记了。

包教包会!用一张白纸教你推导出 RAFT 算法

 

图9 根据针对选举的讨论完善出来的全套机制

这次因为新增的内容比较多了,司马村长把新增的内容都用红色笔来记了,还修复一些班村长之前吐槽的不通顺的语句,还补充了投票过程中容易想出来的一些细节。写完以后大家看了一会,司马村长觉得十分满意了,最后达成的成果(5)就是大家的终极目标了,但是这时候顾村长又看出问题来了。

顾村长:前面那个图 8 里面,要是通信方式全部被卡断的,不是作为主家的左村,而是作为分家的我们顾村的话,就有问题了。我们顾村收不到任何消息,3 个月以后自己成为候选村,增大自己的任期号,发出去的选举消息你们也收不到,然后我们顾村继续提升自己的任期号,不断发起新的选举。要是三年后,通信恢复了,我的任期号最大,你们收到我的选举请求,都要参见龙王了。

欧阳:三年后我们收到你的选举消息,确实主家也要自认任期号不够看,自降为分家,但只要这三年里有新事件被主家安全确认过,你也不可能被投成新的主家。因为我们投票还要看你最后的记录事件有没有我们的新。你自己这三年记录不了任何事件,主家只要有新事件安全确认过,那至少有 3 家记录了这个新事件,这 3 家都不会投票给你,你最多 2 票,怎么当选主家呢?所以说,最后当主家的,一定还是记下了所有事件的村子。反过来说,要是三年里面没新事件被安全确认,那你当上主家,也没什么问题,因为你也是记录了所有事件的,你当主家就当呗。

当然了,你这样冒出来,打断本来干的好好的主家的工作,确实影响了大家对历史的记录,投票这段时间,都没有主家正常工作了,所以这点我们可以补一些限制规则,比如正式投票前让你发个民意调查什么的,要是你民意调查都过不了,就不要发什么选举来浪费大家时间了,当然这个规则可以以后补充清楚,因为民意调查也可能拖慢了正常需要发起选举的节奏

五、龙王归来

欧阳村长说完以后,大家都很佩服其深谋远虑,这时候班村长拿出来一份打印材料,大家都瞥了一眼,居然是洋文的,标题很长:“In Search of an Understandable Consensus Algorithm”。然后班村长发话了,今天晚上大家能制定出这样一个计划来,很了不起了,不过还有两个点大家是没想到的,一个是主家新上任的时候,主家已经确认安全的最大页码,不一定比分家都大,传递记录事件消息的时候,要特别注意,司马你记得笔记里复制规则那里其实是凭直觉蒙对的。这一点我提示你们以后,你们仔细想想,应该都能想到的。不过还有一种情况就不容易想到啦,你们过来看看这张图:

包教包会!用一张白纸教你推导出 RAFT 算法

 

图10 超级复杂的轮流做主家(论文原文图8)

班村长开始解释了,我这个图上不同颜色的小方块代表不同任期记录下来的事件,小方块里的数字代表事件记录里的任期号是多少,abcd(e)代表顺序的4 个时间点,每个时间点上,谁的记录外面的框轮廓粗,谁就是当时的主家,比如(a)时期 S1 就是主家,(d)时期 S5 就是主家。我们来看一下发生了什么啊,(a)这个时间点呢,S1 是主家,把他记录的第 2 页上的事件(黄色)同步给了 S2,然后他们村连同还在路上的信使都被灭了。

到了(b)这个时间呢,S5 因为在选举中,得到 S3,S4 的支持当上了主家,并且他在第 2 页上记录了一个新事件(蓝色)。这里都好理解吧,S5 赢得选举的时候,因为只有 S2 一个村有更新的事件,所以只要 S5 先发起选举,S5 就可以得到 3 票了,反正黄色事件之前也不可能被任何村子确认为安全,所以这个结果也合理嘛。

到了(c)时期,S5 这个村子连同信使都被灭了,他们记录下来的事件一个村子都没传递到,而 S1 那边出现了幸存者,凭着记录的黄色事件,在连续将任期号提升到 4 以后,赢得了选举,并且在第 3 页上记录下来了新的事件(粉色)。在将新事件传递给 S3 的时候,因为被拒绝所以退而求其次将将第 2 页上的黄色事件同步给了 S3,这样 S3 在第 2 页上也记录下了黄色事件,黄色事件也就有 3 个村子记录下来了,按照你们前面的讨论,S1 就要对黄色事件做安全确认了。

要是 S1 确认黄色事件安全,将其刻到石碑上,之后再次被灭村,S5 那边的幸存者,凭借自己在第二页上记录下来的蓝色事件,至少可以在连续提升自己任期号到 5 以后,在选举中得到 S3 和 S4 的支持。因为 S3 虽然记录了黄色事件,但黄色事件的任期号是 2,蓝色事件的任期号是 3,蓝色事件在规则中是更新的。S5 赢得选举做了主家以后,在(d)这个时候,是可以把第 2 页上的蓝色事件复制到其他所有村子记事本的第 2 页上的,蓝色事件在第 2 页上被确认安全的话,和之前在第 2 页上已经被 S1 确认甚至被刻到石碑上的黄色事件就冲突了。

所以说你们前面讨论的规则里面还是有一个关键漏洞的。不过你们也别那么痛苦的一副表情了,你们继续看图吧。如果 S1 没有那么快被屠村,没有(d)这个时刻的事情,而是到了(e)这个时间点上,完成了复制粉色事件给 S2,S3 的任务,这时候 S1 确认粉色事件是安全的并刻到石碑上。之后不管发生什么事情,S5 的蓝色事件在选举中都是不如 S1,S2,S3 最后记录的粉色事件新的(任期号直接分胜负),也就再也选不上主家了。

总结一下呢,就是主家只能确认自己当前任期内的事件是否安全,而不能确认之前任何一个任期内的事件是否安全,而根据你们最早就得出的成果(1),一页上的事件被确认安全了,那这一页之前所有页上记录的事件也就安全了,所以过往任期中的事件是可以通过当前任期的事件安全性被确认的。司马你的纸给我,我来修改一下吧。

包教包会!用一张白纸教你推导出 RAFT 算法

 

图11 集中大家的智慧讨论出来的最终方案

班村长写完以后继续说到,我把改动都用蓝色标记出来了,复制记录事件的规则里面,司马刚才是凭直觉写对了“要确认主家的安全页码大于自己的”这类规则的,所以这个我也标出来了。最重要的,就是最后达成的成果,我改了一下,可不是随便一页上的事件有超过 3 个村子记录了,就可以确认安全哦。切记切记。我在这里隐忍了三个小时了,听你们说了这么多,现在我要回去睡觉了。

剩下的村长沉思了大半个小时,然后对着班村长离去的方向拱手作揖,“参见龙王”。

六、推广总结

到这里呢,这个穿越时空的小故事就差不多结束了。之前看过 raft 论文或者现在再去看的同学,应该都可以轻松的把故事里面的名词和论文中的对应起来了,多多少少对论文中一开始就出现的协议规则是怎么来的能有一些新的理解了。写这个故事的时候,通过好友之间讨论的形式来构造的情节,希望通过这种方式能让更多同学对分布式共识算法产生兴趣,消除恐惧,在自己业务里面合适的场景中用上这种能力来提升服务的质量,当然因为水平有限出现的一些错误也请大家多多包涵指正。

感谢所有不吝三连支持的同学。最后把这篇文章送给这些年来在一线研发岗位上一起奋斗战友,过去和你们每一次为了更完美的解决方案的讨论,都让我受益良多,很多场面我会永远记得,以这个故事向纯粹的你们致敬。

后记

司马:左老师,除了我给你们的笔记上提到的那些东西,你还准备带些什么宝贝一起穿越啊?

左村长:我要带上我最喜欢的愤怒的小鸟周边,哈哈哈!



Tags: RAFT 算法   点击:()  评论:()
声明:本站部分内容来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系,我们将及时更正、删除,谢谢。
▌相关评论
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表
▌相关推荐
作者:nolanyang,腾讯 PCG 后台开发工程师分布式共识算法中,raft 主打的就是易理解性,近年来随着业界对算法的开发,raft 算法的应用也被大大拓展。raft 的论文,先描述了算法协议,再...【详细内容】
2020-12-08    RAFT 算法  点击:(3)  评论:(0)  加入收藏
相关文章
    无相关信息
最新更新
栏目热门
栏目头条