1 拜占庭将军问题(from 百度百科) 拜占庭将军问题是一个协议问题,拜占庭帝国军队的将军们必须全体一致的决定(数据的一致性)是否攻击某一支敌军。问题是这些将军在地理上是分隔开来的(分布式),并且将军中存在叛徒。叛徒可以任意行动以达到以下目标:欺骗某些将军采取进攻行动;促成一个不是所有将军都同意的决定,如当将军们不希望进攻时促成进攻行动;或者迷惑某些将军,使他们无法做出决定。如果叛徒达到了这些目的之一,则任何攻击行动的结果都是注定要失败的,只有完全达成一致的努力才能获得胜利。
拜占庭假设是对现实世界的模型化,由于硬件错误、网络拥塞或断开以及遭到恶意攻击,计算机和网络可能出现不可预料的行为。拜占庭容错协议必须处理这些失效,并且这些协议还要满足所要解决的问题要求的规范。这些算法通常以其弹性t作为特征,t表示算法可以应付的错误进程数。
很多经典算法问题只有在n ≥ 3t+1时才有解,如拜占庭将军问题,其中n是系统中进程的总数
2 Raft算法 Raft 算法是一种简单易懂的共识算法。它依靠 状态机 和 主从同步 的方式,在各个节点之间实现数据的一致性。
在学习Raft算法的时候,我们需要了解Raft的两个核心要点:
- 选取主节点
- 主从同步数据
人类的出生,离不开无数小蝌蚪之间的激烈竞争。在竞争的过程中,某个速度最快运气最好的小蝌蚪最终胜出,让我们诞生到了这个世界。
同样道理,Raft算法在选择主节点的过程中,也是通过多个节点之间的投票竞争。
说到这里,不得不说一下Raft算法的状态机。Raft算法为节点定义了三种角色:
- Leader(主节点)
- Follower(从节点)
- Candidate(参与投票竞争的节点)
第一步,在最初,还没有一个主节点的时候,所有节点的身份都是Follower。每一个节点都有自己的计时器,当计时达到了超时时间(Election Timeout),该节点会转变为Candidate。
文章图片
第二步,成为Candidate的节点,会首先给自己投票,然后向集群中其他所有的节点发起请求,要求大家都给自己投票
文章图片
第三步,其他收到投票请求且还未投票的Follower节点会向发起者投票,发起者收到反馈通知后,票数增加。
文章图片
第四步,当得票数超过了集群节点数量的一半,该节点晋升为Leader节点。Leader节点会立刻向其他节点发出通知,告诉大家自己才是老大。收到通知的节点全部变为Follower,并且各自的计时器清零。
文章图片
这里需要说明一点,每个节点的超时时间都是不一样的。比如A节点的超时时间是3秒,B节点的超时时间是5秒,C节点的超时时间是4秒。这样一来,A节点将会最先发起投票请求,而不是所有节点同时发起。
为什么这样设计呢?设想如果所有节点同时发起投票,必然会导致大家的票数差不多,形成僵局,谁也当不成老大。
那么,成为Leader的节点是否就坐稳了老大的位置呢?并不是。Leader节点需要每隔一段时间向集群其他节点发送心跳通知,表明你们的老大还活着。
文章图片
一旦Leader节点挂掉,发不出通知,那么计时达到了超时时间的Follower节点会转变为Candidate节点,发起选主投票,周而复始……
文章图片
数据同步 Raft 算法同步数据的方式, 和 XA 二段提交有一些相似
第一步,由客户端提交数据到Leader节点。
文章图片
第二步,由Leader节点把数据复制到集群内所有的Follower节点。如果一次复制失败,会不断进行重试
文章图片
第三步,Follower节点们接收到复制的数据,会反馈给Leader节点。
文章图片
第四步,如果Leader节点接收到超过半数的Follower反馈,表明复制成功。于是提交自己的数据,并通知客户端数据提交成功。
文章图片
第五步,由Leader节点通知集群内所有的Follower节点提交数据,从而完成数据同步流程。
文章图片
共识算法的应用场景? 在用于共享配置和服务发现的 K-V 存储系统 [etcd] 中, 使用的就是 Raft 算法来保证分布式一致性
其他一致性算法 Paxos 算法: 早期的共识算法,由拜占庭将军问题的提出者 Leslie Lamport 所发明。谷歌的分布式锁服务 Chubby 就是以 Paxos 算法为基础。
ZAB 算法: Zookeeper 所使用的一致性算法,在流程上和 Raft 算法比较接近。
PBFT 算法: 区块链技术所使用的共识算法之一,适用于私有链的共识。
参考:
https://www.jianshu.com/p/8e4bbe7e276c
http://www.miaomiaoqi.cn/2019/04/12/%E6%8B%9C%E5%8D%A0%E5%BA%AD%E5%B0%86%E5%86%9B%E9%97%AE%E9%A2%98(Raft%E7%AE%97%E6%B3%95)/
【算法与数据结构|【TIDB】拜占庭将军问题和Raft算法】
推荐阅读
- 数据库|SQL行转列方式优化查询性能实践
- mysql|一文深入理解mysql
- 达梦数据库|DM8表空间备份恢复
- 数据技术|一文了解Gauss数据库(开发历程、OLTP&OLAP特点、行式&列式存储,及与Oracle和AWS对比)
- SqlServer|sql server的UPDLOCK、HOLDLOCK试验
- 谈灾难恢复指标(RTO与RPO是什么鬼())
- RPO与RTO
- 数据库|效率最高的Excel数据导入---(c#调用SSIS Package将数据库数据导入到Excel文件中【附源代码下载】)...