上图中节点C占据了先机,率先发起竞选投票。
节点B慢了一步, 无奈中同意支持节点C , 节点C获得了超过半数的支持,成为“老大” , 节点B成为“小弟”。
(可能有人会想到:节点B和节点C 同时发起竞选投票,每个节点的投票计数都是1 ,都过不了半数, 该怎么处理呢? 很简单,再次发起一轮竞选投票即可,当然为了防止B和C一直同时发起竞选投票,从而陷入无限循环,要重置一个随机的等待时间。)
投票过半数很重要,张大胖想,只有这样才能保证“老大”节点的唯一性。
对于每个节点,处理流程其实非常简单:
3.数据的复制
张大胖费了半天劲,终于把分布式系统中怎么自动地选取“老大”节点给确定了。
接下来就是要把发给“老大”的数据,想办法复制到“小弟”的节点上。 该怎么处理?
由于是分布式的,只有大多数节点都成功地保存了数据,才算保存成功。
所以那个“老大”节点必须得承担起协调的职责。
张大胖想了一个复制日志的办法: 每个节点都有一个日志的队列。
在真正把数据提交之前,先把数据追加到日志队列中,然后向个“小弟”复制。
1. 客户端发送数据给节点A (“老大”)。
节点A 先把数据记录到日志中,即此时处于“未提交状态”
2. 在下一次的心跳消息中, 数据被发送给各个“小弟”。
3. 各个“小弟” 也把数据记录到日志中(也处于未提交状态),然后向“老大”报告自己已经记录了日志。
4. 如果节点A收到响应超过了半数, 节点A就提交数据,通知客户端数据保存成功。
5. 节点A在下一次心跳消息中,通知各个“小弟”该数据已经提交。各个“小弟”也提交自己的数据。
如果某个“小弟”不幸挂掉,那“老大”会不断地尝试联系它, 一旦它重新开始工作,就需要从“老大”那里去复制数据,和“老大”保持一致。
4.RAFT
张大胖对这个初步的设计还比较满意,他把这个方案交给领导Bill去审查。
Bill 看了以后,笑道: “你现在其实就是在折腾一个一致性算法, 说白了就是允许一组机器像一个整体一样工作,即使其中一些机器出现故障也能够继续工作下去。”
“没错没错,领导总结得真是精准。” 张大胖拍马屁。
“不过,”Bill 话锋一转, “ 你设计的日志的复制还有很多漏洞,我看你的设计中一共有5步, 如果在这5步中,那个“老大”节点A挂掉了怎么办?数据是不是就不一致了?”
“这个...... ” 张大胖确实没有仔细考虑。他暗自后悔,只顾低头拉车,忘了抬头看路,忽略了分布式环境下的复杂问题。
“不过你已经做得很不错了,” 领导马上鼓励道, “你设计的这一套体系其实和RAFT算法非常类似。”
“RAFT? ”
“对,RAFT是个分布式的一致性算法,相比复杂难懂的Paxos, RAFT在可理解,可实现性上做了很大的改进。 你这里的‘老大’,RAFT算法叫做Leader, ‘小弟’叫做Follower,不过人家对日志的复制,以及如何确保数据的一致性有着非常详细的规定。 ”
张大胖一听说有现成的算法,立刻高兴起来: “太好了,分布式的难题已经被别人解决,我去把它实现了。”