1.阅读各算法原版论文
2.查阅各算法是否有官网信息
3.头有点疼, 要好好研究下这些
导读: 拜占庭将军问题
在很久很久以前,拜占庭是东罗马帝国的首都。
那个时候罗马帝国国土辽阔,为了防御目的,因此每个军队都分隔很远,
将军与将军之间只能靠信使传递消息。
在打仗的时候,拜占庭军队内所有将军必需达成一致的共识,才能更好地赢得胜利。
但是,在军队内有可能存有叛徒,扰乱将军们的决定。
这时候,在已知有成员不可靠的情况下,
其余忠诚的将军需要在不受叛徒或间谍的影响下达成一致的协议。
莱斯利·兰伯特(Leslie Lamport)通过这个比喻,表达了计算机网络中所存在的一致性问题。
这个问题被称为拜占庭将军问题。
>>>>>>>>>>>>>>>>> 解决方案 <<<<<<<<<<<<<<<<<
分布式共识算法
>>>>>>>>>>>>>>>>> <<<<<<<<<<<<<<<<<
1.概述
一致性是分布式领最重要的问题。
一致性不代表结果的正确与否,而是分布式系统的多个物理节点的处理结果对外呈现的状态一致与否。
例如所有节点都达成失败状态也是一种一致性。
#共识与一致性的区别
一致性描述的是结果状态,共识则是一种手段。达成某种共识并不意味保障了一致性。
#共识算法分类
1.CFT(Crash Fault Tolerance):
不伪造信息的非拜占庭错误,代表算法是Paxos、Raft,特点是性能好,容忍不超过一半的故障节点。
2.BFT(Byzantine Fault Tolerance):
伪造信息的拜占庭错误,特点是性能差,容忍不超过1/3的故障节点。两类代表:
>> PBFT(Practical Byzantine Fault Tolerance)确定性系列算法:
一旦达成共识不可逆转,就是最终结果。
>> PoW概率算法:
共识是临时的,随着时间推移或变化,共识结果被推翻的概率越来越小,成为最终结果。
3.特殊的:XFT(Cross Fault Torelrance)等算法
可以提供类似CFT的处理性能,并能在大多数节点正常工作时提供BFT保障。
2.raft 一致性算法
Raft 算法是一种简单易懂的共识算法。
它依靠 状态机 和 主从同步 的方式,在各个节点之间实现数据的一致性。
Raft的两个核心要点:
1.选取主节点
2.同步数据
2.1 raft算法选主流程
Raft算法在选择主节点的过程中,也是通过多个节点之间的投票竞争。
#Raft算法为节点定义了三种角色:
1.Leader(主节点)
2.Follower(从节点)
3.Candidate(参与投票竞争的节点)
Raft算法-选举Leader流程.png
2.2 raft算法的数据同步过程
Raft算法-数据同步(写)流程.png2.3 raft算法的应用
1.etcd
2.consul
3.redis
raft参考资源
https://raft.github.io/ (ratf官网)
http://thesecretlivesofdata.com/raft/ (raft动画演示)
https://raft.github.io/raft.pdf (raft论文)
https://blog.csdn.net/qq_36561697/article/details/88550398 (raft论文翻译)
https://www.infoq.cn/article/coreos-analyse-etcd/ (etcd中的raft)
3.paxos算法
3.3 raft算法的应用
1.zookeeper(用了ZAB协议, 是paxos算法的实现)
2.google的Chubby
参考资源
https://www.cnblogs.com/dennyzhangdd/p/6497606.html (系列算法)
https://www.jdon.com/artichect/raft.html
https://www.imooc.com/article/details/id/28738 (拜占庭将军问题及其方案)
网友评论