包教包会！用一张白纸教你推导出 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 页上，这样至少事情的先后顺序不会轻易搞错了。然后左村长提出一个关键问题，纸质材料和油墨虽然修改方便，但是不易保存，就算在历史长河中不被损毁，千年过去最早的记事本也没法再看了，根据他看过一部科幻小说，左村长提出，记事本上的事情只要村落之间“达成一致”了，就可以把事情按顺序刻在石碑上埋到地底下，这就是人类目前最有效的保存信息的方法了，这样做的缺点就是刻在石碑的内容就不好更改了。大家纷纷表示同意，司马村长把这些信息记录在他的大白纸上：

文章插图

图2 记录历史的主要工具：记事本和石碑
二、前提条件的制定讲完这些，大家都把注意力集中到了刚才左村长无意间提出来的“达成一致”这四个关键字上。班村长首先提出来，如果每个时期只有一个村落负责把发生的事件记录下来，而且保持所有村落都是 1 页上面只记录 1 个事件，其他村落只负责接收这个村落的消息，把接收到的消息记录在记事本对应的页码上，那记事本上每一页上的事件保持一致的难度就小很多了。如果多个村落同时记录历史事件，然后通过互通消息来协调一致，难度就会大很多，处理每一页上的记录冲突也会需要很多时间。
大家一商量，虽然有一点争议，但最终还是认同了这个提议，多点记录确实比较难，最终效率也不一定高。左村长接着就抛出了两个名词作为约定，“主家”即当前负责记录的村子，“分家”即当前接收主家消息的村子。左村就主动承担第一期的主家任务了。接下来就是司马村长发话了，前面他也说过，目标是任何时代即使有两个村落被灭，记录也要准确的传下去，左村长的方案里面，每个时代负责记录的村子发生意外的时候，如果他们记在石碑上的事件，别的村子还没收到，那记录的事件就会出现不一致了，以后之前被灭村子的石碑被后人挖出来以后，历史事件可能出现矛盾，当然这还是最简单的情况了，更复杂的这一类情况还能一口气说出很多。
大家开始继续思考这个问题，顾村长第一个发表观点，一件事情只要有 3 个村落记录下来，那之后任何时刻失去任意两个村子，这件事情都不会丢，因为最差也是还有一个村落记下了这件事。所以说一件事情只要有 3 个村落在记事本上记下来了，那这件事情就可以被放心的刻到石碑上了，一个事件确认可以被记录在石碑上了，就称这个事件安全了。至于谁来统计有几个村庄记录了某一件事情，那自然是主家了。左村长的方案里面只有主家负责发出消息，其他从家都只能在主家发来消息以后做相应记录，再让信使把记录的情况发回给主家，主家根据回来的信使的消息自然可以统计有多少村落记记录下了这个事件了，主家在后面的通信中再把哪些事件可以刻到石碑上了，带给各村，那就很稳妥了，所以主家要统计一份各村已经记录下的事件列表。