RAFT 论文——村委会版

RAFT 论文——村委会版写给完全忘记 RAFT 的自己。读完这篇等于把论文学了一遍。登场角色村委会里的人/物论文里叫什么村长Leader领导者委员Follower跟随者正在竞选的委员Candidate候选人小张来办事的村民Client客户端记录本Log日志记录本里的一条Log Entry日志条目村长盖章生效Committed已提交本届任期编号Term村长定期打招呼Heartbeat心跳村长同步记录的消息AppendEntries RPC候选人拉票的消息RequestVote RPC发快照的消息InstallSnapshot RPC小张给消息贴的编号Session ID流水号第一章RAFT 是什么想象一个村委会有 1 个村长、4 个委员共 5 人。村里所有决定——批地、盖房、开店——都要记在记录本里。问题是这 5 个人每人手里有一本怎么保证 5 本始终一样万一村长突然晕倒怎么办RAFT 就是解决这个问题的方法。核心思路三句话所有写入都经过村长村长说了算超过半数的人记下来才算正式生效记录最全的人才有资格当村长第二章正常运转——日志复制小张来申请建新房第一步小张找到村长小张只能找村长办事不能找委员。村长在自己的记录本上写下第88条批准小张建房未盖章第二步村长通知所有委员村长给 4 个委员发消息AppendEntries RPC“大家在第88条写上批准小张建房”第三步超过半数回复已记委员回复委员A✅ 已记委员B✅ 已记委员C❌ 没反应在睡觉委员D✅ 已记5 人里 4 人写好了超过半数 → 可以生效。第四步村长盖章通知大家也盖章村长在自己本子上盖章Commit通知委员们也盖章再告诉小张“批了”那个睡觉的委员C呢不用管他。村长下次发消息时顺带把他落下的条目补给他他自己追上来。关键原则超过半数写好就算数不需要所有人都确认。5 人村3 人确认就够。7 人村4 人确认就够。第三章村长失联——领导者选举村长定期打招呼正常情况下村长每隔一小段时间给所有委员发一条空消息Heartbeat意思是我还在别慌。委员们收到后重置自己心里的倒计时。村长突然失联委员们停止收到心跳各自的倒计时开始走。倒计时是随机的150 到 300 毫秒之间每个人不一样。为什么随机防止大家同时举手、同时拉票谁也选不上。先数完的人举手拉票委员B的倒计时先到 → 升级为Candidate→ 把任期编号Term加一 → 给所有人发消息RequestVote RPC“村长失联了我要竞选请投我一票”其他委员怎么投票两个条件都满足才投条件说明这轮没投过票每轮每人只能投一票候选人记录本不比我旧记录落后的人没资格当村长两个都满足 → 投票。任意一个不满足 → 拒绝。当选委员B收到超过半数的票 → 当选村长 → 立刻发心跳告诉大家我是新村长。平票或没人过半怎么办这轮作废所有人重新随机倒数再来一轮。会不会永远选不出来极低概率。每次碰撞都要求大家倒计时恰好一样长连续碰撞的概率像连续中彩票实际上几乎不发生。第四章新村长上任——记录怎么保持正确为什么新村长记录一定最新选举时候选人要亮记录本——通过 RequestVote RPC 告诉大家自己的最后一条记录编号。委员的规则你的记录比我旧我不投你。所以记录落后的候选人拿不到多数票天然被淘汰。当选的人必然是记录最新的。新村长上任后做什么把自己记录本里还没盖章的条目继续同步给所有委员重新走一遍超过半数确认 → 盖章的流程把之前没完成的事情收尾。第五章小张怎么找村长正常情况小张直接找村长办事。村长挂了小张不知道新村长是谁小张随机挑一个委员去问。委员会拒绝办理但告诉小张“我不是村长去找B他是新村长。”委员通过收到的心跳消息知道谁是现任村长AppendEntries RPC 里附带村长地址。选举还没结束委员也不知道新村长是谁委员无法提供地址小张的请求超时没有回应。小张随机换一个委员再问不是反复问同一个人。选举通常在 150~300 毫秒内结束多问几次就能得到答案。第六章村子要加人减人——集群成员变更为什么不能直接换名单原来 5 人加 2 人变 7 人。如果消息发出去有人早收到、有人晚收到可能同一时刻用旧名单5人的人3票过半 → 选出村长甲用新名单7人的人4票过半 → 选出村长乙两个村长同时存在记录本就乱了。解法联合共识Joint Consensus——过渡期村长不发换成新名单而是发一张过渡公告同时写着新旧两份名单过渡公告旧名单A B C D E新名单A B C D E F G收到此公告的人两份名单都要用过渡期投票规则一票同时计入两份名单两边都要超过半数才算通过。为什么这样就安全了鸽巢原理用旧规则选出的村长必须拿到旧名单里的多数≥3票用新旧双规则选出的村长也必须拿到旧名单里的多数≥3票两边合计需要至少 336 票但旧名单只有 5 个人每人只有一票65票不够分。结论两个多数派必然重叠不可能同时存在两个合法村长。过渡期结束村长确认过渡公告被多数人收到后发第二份公告切换到纯新名单。过渡期通常只持续几百毫秒。第七章记录本太长怎么办——快照问题村子运行 3 年记录本写了 10 万条。新来的委员 F 要从头抄抄到什么时候解法定期拍快照Snapshot每隔一段时间把前面所有记录压缩成一张现状表村民当前状态小张已批建房小李已批开店小王申请中这张表代替了前面所有记录旧记录直接删掉。快照里还要记两个数字压缩到第几条比如第400条那条记录的任期编号用来告诉别人从第401条开始接着抄。每个委员自己决定拍快照的时机不需要村长统一指挥记录本超过一定大小就自己拍。新委员落后太多怎么办村长通过InstallSnapshot RPC把快照切成小块发给委员 F村长 → F第1块共10块 村长 → F第2块 ... 村长 → F第10块发完了F 收齐后整体替换自己的记录本从快照最后一条编号接着同步新记录。收到一半村长挂了F 把收到的块存在草稿里没收齐不替换正式记录本新村长上任后重新发一遍。第八章小张重复发消息怎么办——线性化语义问题小张发批准建房村长处理了盖章生效村长回复的消息路上丢了小张没收到再发一次会不会被批两次解法流水号Session ID小张给每条消息贴唯一编号消息#001批准建房村长处理完把#001已处理记在本子上。下次再收到消息#001查一下发现处理过了直接回放上次结果不重新执行。村长换人了也没事——流水号记录随日志同步新村长也知道哪些已处理。论文把这叫做Linearizability线性化语义每条操作恰好执行一次不多不少。第九章三条铁律——安全性保证铁律含义村委会说法Election Safety每个 Term 最多只有一个 Leader同一届任期只能有一个村长Leader Completeness已提交的条目未来所有 Leader 都有盖了章的记录永远不消失State Machine Safety所有节点在同一编号位置执行的命令相同所有记录本在同一行写的内容完全一样最后一句话强领导者统一写入随机超时避免选举冲突多数派确认保证持久记录越新越有资格当选——四点合在一起让分布式系统的记录本永远不乱。基于 RAFT 论文In Search of an Understandable Consensus AlgorithmDiego Ongaro John Ousterhout整理