包教包会！用一张白纸教你推导出 RAFT 算法( 二 ) _小知识

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

文章插图

图3 可能出现的记事本有空页的情况
左村长这时也提出一个问题，就算主家一直没出什么问题，过了一千年，那主家记录各个事件在各村的记录情况的列表也是长的看不懂了，给各家补齐少记录的事件也是不知从何下手啊。一时间与会众人难以定出个结论来，这时候欧阳村长终于发言了：太复杂的事情不好分析，我们就简单点处理吧，每次同步事件的时候，有 3 个以上村落都有着从开始到当前页码都相同的记录时，才算安全，才可以把这件事刻到石碑上，这样任意 2 个村被灭，都会至少有一个村保留所有可以被刻到石碑上的事件，下一轮只要能把满足这样条件的村庄选出来做主家，那这个新的主家就能带领剩下的分家把之前的记录传承下去了。
另外这样做了以后，任何分家接收到主家传来的消息，如果发现前面有缺漏的事件，那也不用再跳过前面的页码来记录当前事件了，因为记下来了也不能作为当前事件的确认方被统计计数，也就是说记事本中间再也不会有空洞了，而主家也不用保留超级复杂的统计列表了，只要记一下各个分家最后记录下来的事情是第几页的事情就能掌握全局情况。其实这时候还得出了一个阶段性成果：因为记录事件的时候，要确认前面的事件是不是都一样，只有都一样才能记录下来，只要一个时期只有一个村庄做主家，那么两个和主家正常通信的分家的记事本上，只要在任意一页上“相同”，那这页之前的内容肯定是“相同”的了，任意分家和主家之间也满足这个结论。
这一下大家都开心了，这个办法简单易懂，司马村长立刻把刚才讨论的结果记录到大白纸上：（到这里大家讨论出来的两个最关键的前提条件：只有一个主家负责记录事件，其他分家只负责接收主家的消息；记事本不能有空洞。这两个前提条件并不是靠推理得出的，而是大家希望简化后面的规则提出的假设，如果没有这两个条件，那大家后面可能会推导出别的分布式共识算法哦）

文章插图

图4 最初提出的复制事件的规则
三、解释解释什么叫做“相同”但是很快大家就发现了新的问题，确认过往所有的记录事件是不是都“相同”，这可不容易做啊，先不说确认“相同”是不是就是比较记录的每一个字都一样，只要持续记录很多年，比较一次也要花上太多时间了吧，每次有新的事件都要从头开始比较，这谁受得了？司马村长立刻发表了高论：用我小学二年级学过的最简单的数学归纳法就可以破这个问题了，对于在区间（0，N]的任意 n, 都满足元素 S1（n）== S2（n）且 S2（n-1）== S1（n-1），那么在[0,N]区间内，S1 和 S2 这两个数组每个位置上的元素都是相等的。
在我们这个问题里，说人话就是每一个新事件记录的时候，主家在同步消息的时候除了当前事件还要带上前一页记录的事件，收到消息的分家要比较一下前一页上的事件和自己记录的是不是“相同”，只有前一页的事件“相同”才记录新一页的事件，只要从头一开始就这么做，那么每次能顺利记录下新事件的村落，前面记录的事件和主家肯定是都“相同”的。大家纷纷拍案叫绝，只有顾村长问了一声，要是分家接到消息的时候，发现主家传来的前一页事件和自己这里记录的不一样或者根本还没记录过这一页的事情，那可怎么办呢？
欧阳村长立刻发话，还是用简单的方法，上面的情况，分家直接回复主家现在不能记录这一页上的事件，主家接到失败的消息就把前一页的事件作为这个分家下次要同步的事件在下次发消息的时候发前一页的事件，而下次发消息附带的也就是前前页的事件了，要是这次同步能成功，那就继续尝试同步新的事件，反之，就以此类推，继续往前尝试更靠前的页码上的事情，主家再单独保存一份要给各分家下次尝试同步哪一页的列表就能轻松做好这个事情了。这一波讨论完，大家一下子都安心了，最重要的主家怎么把自己记录下来的事件复制给分家的主要机制都讨论出来了，司马村长开心的在白纸上开始了记录。他先画了一张草稿说明以后主家怎么同步消息给分家：