Raft算法


原文地址

拜占庭将军问题是分布式领域最复杂、最严格的容错模型。但在日常工作中使用的分布式系统面对的问题不会那么复杂,更多的是计算机故障挂掉了,或者网络通信问题而没法传递信息,这种情况不考虑计算机之间互相发送恶意信息,极大简化了系统对容错的要求,最主要的是达到一致性。

针对简化版拜占庭将军问题,Raft 解决方案类比

假设将军中没有叛军,信使的信息可靠但有可能被暗杀的情况下,将军们如何达成一致性决定?

Raft 的解决方案大概可以理解成 先在所有将军中选出一个大将军,所有的决定由大将军来做。选举环节:比如说现在一共有3个将军 A, B, C,每个将军都有一个随机时间的倒计时器,倒计时一结束,这个将军就会把自己当成大将军候选人,然后派信使去问其他几个将军,能不能选我为总将军?假设现在将军A倒计时结束了,他派信使传递选举投票的信息给将军B和C,如果将军B和C还没把自己当成候选人(倒计时还没有结束),并且没有把选举票投给其他,他们把票投给将军A,信使在回到将军A时,将军A知道自己收到了足够的票数,成为了大将军。在这之后,是否要进攻就由大将军决定,然后派信使去通知另外两个将军,如果在一段时间后还没有收到回复(可能信使被暗杀),那就再重派一个信使,直到收到回复。

………………

小总结

Raft 是能够实现分布式系统强一致性的算法,每个系统节点有三种状态 Follower,Candidate,Leader。实现 Raft 算法两个最重要的事是:选主和复制日志

参考链接:

Raft 官网:https://raft.github.io/

Raft 原理动画 (推荐看看):http://thesecretlivesofdata.com/raft/

Raft 算法解析图片来源:http://www.infoq.com/cn/articles/coreos-analyse-etcd


文章作者: Micheal
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Micheal !
  目录