江苏龙网

  1. 主页 > 生活百科 > >

包教包会！用一张白纸教你推导出 RAFT 算法( 四 )

RAFT 算法


司马：发起选举是容易，我们收到选举要按什么规则投票呢？按照前面的思路，我们可是要选出一个拥有前任主家进行过安全确认的所有事件的村落出来传承的哦 。
欧阳：简单处理，任期号代表时代只增不减，记事本上有记录事件的最大页码上的任期号谁大，谁的记事本就内容更全，如果任期号一样大，那最大页码大的记事本就更全，要是页码和任期号都一样，那记事本就一样全 。每个村庄只投票给记事本最少和自己一样全的村庄不就可以了么 。
司马：那得了几票，就可以做主家了呢？
欧阳：简单处理，就是包括自己在内的 3 票啊，前面我们设定过了，最后一个被确认安全的事件，包括主家最少有 3 个村庄已经记下来了 。记录下最新事件的村子就是有最全内容的村子，包括主家在内有 3 个这样的村子 。就算剩余其他 2 个村庄还没来得及记下最新的事件的时候，主家被灭了，记下最新事件的 2 个村庄里面不管谁参与选举，谁就能得到包括自己在内的 4 票，反之，没记下最新事件的 2 个村子参与选举，最多只能得 2 票 。我们设定的最坏情况也就是同时再被灭掉一个记录事件最全的村子，那这时候剩下唯一一个记录最全的村子还是能够得到包括自己在内的 3 票支持，成功当选新的主家 。
总结起来说就是不管被灭几家，只要能赢得 3 票，上一个任期的主家能确认安全的事件，在新选出来的主家记事本里面肯定有 。我图都给你画出来了：

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

文章插图
 
图8 记录“最新”事件的村庄能赢得竞选
司马：不对啊，你的图里面，我只要拿到你和班村的票就能做主家了，万一顾村没给我投票，而是也发起了选举，他也能赢得你和班村的选票，也是 3 票也能成为主家，那不就 2 个主家了吗？
欧阳：这个问题连简单处理都不需要了，你们发起选举的时候，先把自己的任期号增加一下，变成自己当选以后要用的任期号发出去，每个村子在一个任期号里最多投一次票，记录下来每个任期号是投票给了哪个村子 。这样你拿到 3 票时候，顾村长再开始发起投票，他的任期号最多和你一样，他是拿不到其他已经投过票的村子的支持的 。除非再过三个月，期间顾村长都没收到过你同步的任何消息，他再次增加任期号发起选举才有机会再当主家 。而如果这三个月里面，你真的什么事都没记下来，那顾村才可能当选，但是任期号也增加了，他用的还是唯一任期号，我们的机制也继续维持着，没什么影响 。
司马：还有问题啊，你刚才说的是我先拿到 3 票的情况，问题是我和顾村可能是同时发起选举的，万一我们一个得到了你的支持，一个得到了班村的支持，那我们岂不是这一轮不分胜负，到下一轮我们再同时发起，又是各得两票，岂不是没完没了，我们时间都花在选举上了，怎么好好记录历史啊 。
欧阳：这个也是可以简单处理的，我们每家每次发起选举的时间不要那么固定嘛 。比如说你有时候是 3 个月零 7 天收不到任何消息发起选举，有时候是 4 个月发起选举，顾村他们有时候是 3 个月零 14 天收不到消息发起选举，有时候是 4 个月零 7 天发起选举，你们发起选举冲突的概率不就低了？
左村长：你们别太过分了，万一上面那个情况里面，我们村不是被灭了，只是信使都被拦截了，我可是一直都在辛苦的记录着各种事件，只是没法同步给你们，我自己也没法确认新记录的事件是不是可以被刻到石碑上 。那三年后我龙王归来，哦不是，我找回信使，把我这隐忍三年记录下来的事件传递给你们，你们认还是不认？
欧阳：简单起见，不管你是修罗还是什么神医，我们都不认，因为你的内容合进来，我们还要要保持一致太复杂了，而且你那三年记下来的内容又没被安全确认过，你也不敢刻在石碑上，你回来以后乖乖接收我们补给你的安全的事件，去刻你的石碑就完事了 。哪一页开始，你记录事件的任期号和新主家不一样了，你就从这一页开始把后面的内容都划掉啊 。
左村长：我 TM 什么时候说过修罗、神医什么的了？而且我们之前定的规则里面，也没说我这个归来龙王，哦不，我这个归来主家不能继续同步记录的事件给你们啊！
欧阳：简单处理，我补个通用规则，反正同步事件和发起选举两种消息里面都带有任期号这个信息了，任期号只增不减，更大的任期号代表更新的时代，所以我宣布收到的消息里面，任期号小于自己之前记录下来的，一律拒绝，任期号大于自己之前的，一律把自己记录的任期号更新为接收到的任期号，然后再根据之前的设定操作，谁赞成，谁反对？


推荐阅读


上一篇：曼松贡茶能存多少年,把逍遥化进曼松

下一篇：补肾养生茶配方大全,五宝补肾茶配方