漫画:什么是拜占庭将军问题?

点击上方“程序员小灰”,选择“置顶公众号”

有趣有内涵的文章第一时间送达!



五分钟学算法漫画:什么是拜占庭将军问题?



五分钟学算法漫画:什么是拜占庭将军问题?



—————  第二天  —————



五分钟学算法漫画:什么是拜占庭将军问题?



五分钟学算法漫画:什么是拜占庭将军问题?



五分钟学算法漫画:什么是拜占庭将军问题?



五分钟学算法漫画:什么是拜占庭将军问题?



五分钟学算法漫画:什么是拜占庭将军问题?



————————————



五分钟学算法漫画:什么是拜占庭将军问题?

五分钟学算法漫画:什么是拜占庭将军问题?



五分钟学算法漫画:什么是拜占庭将军问题?



五分钟学算法漫画:什么是拜占庭将军问题?



什么是拜占庭将军问题?


在很久很久以前,拜占庭是东罗马帝国的首都。那个时候罗马帝国国土辽阔,为了防御目的,因此每个军队都分隔很远,将军与将军之间只能靠信使传递消息。


五分钟学算法漫画:什么是拜占庭将军问题?



在打仗的时候,拜占庭军队内所有将军必需达成一致的共识,才能更好地赢得胜利。但是,在军队内有可能存有叛徒,扰乱将军们的决定。


五分钟学算法漫画:什么是拜占庭将军问题?


这时候,在已知有成员不可靠的情况下,其余忠诚的将军需要在不受叛徒或间谍的影响下达成一致的协议。


莱斯利·兰伯特( Leslie Lamport )通过这个比喻,表达了计算机网络中所存在的一致性问题。这个问题被称为拜占庭将军问题



五分钟学算法漫画:什么是拜占庭将军问题?



五分钟学算法漫画:什么是拜占庭将军问题?



什么是 Raft 算法?


Raft 算法是一种简单易懂的共识算法。它依靠 状态机 主从同步 的方式,在各个节点之间实现数据的一致性。


在学习Raft算法的时候,大家需要了解Raft的两个核心要点:


1.选取主节点


2.同步数据



不难理解,使用主从同步的方式,可以让集群各个节点的数据更新以主节点为准,从而保证了一致性。那么,如何选取主节点呢?


五分钟学算法漫画:什么是拜占庭将军问题?



五分钟学算法漫画:什么是拜占庭将军问题?



五分钟学算法漫画:什么是拜占庭将军问题?



我们的出生,离不开无数小蝌蚪之间的激烈竞争。在竞争的过程中,某个速度最快运气最好的小蝌蚪最终胜出,让我们诞生到了这个世界。


同样道理,Raft算法在选择主节点的过程中,也是通过多个节点之间的投票竞争


说到这里,不得不说一下Raft算法的状态机。Raft算法为节点定义了三种角色:


1.Leader(主节点)

2.Follower(从节点)

3.Candidate(参与投票竞争的节点


让我们来看一看选主的具体流程:


第一步,在最初,还没有一个主节点的时候,所有节点的身份都是Follower。每一个节点都有自己的计时器,当计时达到了超时时间(Election Timeout),该节点会转变为Candidate。



五分钟学算法漫画:什么是拜占庭将军问题?



第二步,成为Candidate的节点,会首先给自己投票,然后向集群中其他所有的节点发起请求,要求大家都给自己投票。



五分钟学算法漫画:什么是拜占庭将军问题?



第三步,其他收到投票请求且还未投票的Follower节点会向发起者投票,发起者收到反馈通知后,票数增加。


五分钟学算法漫画:什么是拜占庭将军问题?



第四步,当得票数超过了集群节点数量的一半,该节点晋升为Leader节点。Leader节点会立刻向其他节点发出通知,告诉大家自己才是老大。收到通知的节点全部变为Follower,并且各自的计时器清零。



五分钟学算法漫画:什么是拜占庭将军问题?



这里需要说明一点,每个节点的超时时间都是不一样的。比如A节点的超时时间是3秒,B节点的超时时间是5秒,C节点的超时时间是4秒。这样一来,A节点将会最先发起投票请求,而不是所有节点同时发起。


为什么这样设计呢?设想如果所有节点同时发起投票,必然会导致大家的票数差不多,形成僵局,谁也当不成老大。


那么,成为Leader的节点是否就坐稳了老大的位置呢?并不是。Leader节点需要每隔一段时间向集群其他节点发送心跳通知,表明你们的老大还活着。



五分钟学算法漫画:什么是拜占庭将军问题?



一旦Leader节点挂掉,发不出通知,那么计时达到了超时时间的Follower节点会转变为Candidate节点,发起选主投票,周而复始……



五分钟学算法漫画:什么是拜占庭将军问题?



五分钟学算法漫画:什么是拜占庭将军问题?



五分钟学算法漫画:什么是拜占庭将军问题?



让我们来看一看数据同步的流程:


第一步,由客户端提交数据到Leader节点。



五分钟学算法漫画:什么是拜占庭将军问题?



第二步,由Leader节点把数据复制到集群内所有的Follower节点。如果一次复制失败,会不断进行重试。



五分钟学算法漫画:什么是拜占庭将军问题?



第三步,Follower节点们接收到复制的数据,会反馈给Leader节点。



五分钟学算法漫画:什么是拜占庭将军问题?



第四步,如果Leader节点接收到超过半数的Follower反馈,表明复制成功。于是提交自己的数据,并通知客户端数据提交成功。



五分钟学算法漫画:什么是拜占庭将军问题?



第五步由Leader节点通知集群内所有的Follower节点提交数据,从而完成数据同步流程。



五分钟学算法漫画:什么是拜占庭将军问题?




共识算法的应用场景?



五分钟学算法漫画:什么是拜占庭将军问题?



五分钟学算法漫画:什么是拜占庭将军问题?



五分钟学算法漫画:什么是拜占庭将军问题?



五分钟学算法漫画:什么是拜占庭将军问题?



五分钟学算法漫画:什么是拜占庭将军问题?



Paxos 算法:

早期的共识算法,由拜占庭将军问题的提出者 Leslie Lamport 所发明。谷歌的分布式锁服务 Chubby 就是以 Paxos 算法为基础。


ZAB 算法:

Zookeeper 所使用的一致性算法,在流程上和 Raft 算法比较接近。


PBFT 算法:

区块链技术所使用的共识算法之一,适用于私有链的共识。



五分钟学算法漫画:什么是拜占庭将军问题?




—————END—————


五分钟学算法漫画:什么是拜占庭将军问题?



喜欢本文的朋友们,欢迎长按下图关注订阅号程序员小灰,收看更多精彩内容

五分钟学算法漫画:什么是拜占庭将军问题?

原文始发于微信公众号(程序员小灰):五分钟学算法漫画:什么是拜占庭将军问题?

本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » 漫画:什么是拜占庭将军问题?

我还会在以下平台发布内容

GitHub 哔哩哔哩