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


  转载请注明: 随便韶韶 Raft算法

 上一篇
超越“双十一” | ebay支付核心账务系统架构演进之路 超越“双十一” | ebay支付核心账务系统架构演进之路
原文地址 ebay支付新一代核心账务系统FAS(Financial Accounting System)自今年3月上线以来,帮助全球百万卖家处理交易合计超百亿条,日均实时处理线上千万支付流量,每日payout金额超千万美元。系统上线至今稳
2020-11-11
下一篇 
如果 Safari 做不到对,快有何用? 如果 Safari 做不到对,快有何用?
一个困扰了一周的 bug2016 年的一天,当我们发现 iPhone 上的浏览器不能正确通过我们的 CDN 鉴权后,我们花了数天的时间来 debug。简单来说当时的情况是,我们需要同时上传 3 个文件,我们会用用户 token 来换 3 个
2020-10-29
  目录