分布式一致性算法:可能比你想象得更复杂

上图中节点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,不过人家对日志的复制,以及如何确保数据的一致性有着非常详细的规定。 ”

张大胖一听说有现成的算法,立刻高兴起来: “太好了,分布式的难题已经被别人解决,我去把它实现了。”