Raft为什么是更易理解的分布式一致性算法资源-CSDN下载

版权申诉

一致性算法

分布式一致性协议

70 浏览量 2023-10-14 07:42:55 上传评论收藏 762KB DOCX 举报

资源推荐

资源详情

资源评论

Raft 为什么是更易理解的分布式一致性算法

一致性问题可以算是分布式领域的一个圣殿级问题了，关于它的研究可以回溯到几十年前。

拜占庭将军问题

Leslie Lamport 在三十多年前发表的论文《拜占庭将军问题》（参考[1]）。

拜占庭位于如今的土耳其的伊斯坦布尔，是东罗马帝国的首都。由于当时拜占庭罗马帝国国

土辽阔，为了防御目的，因此每个军队都分隔很远，将军与将军之间只能靠信差传消息。在

战争的时候，拜占庭军队内所有将军必需达成一致的共识，决定是否有赢的机会才去攻打

敌人的阵营。但是，在军队内有可能存有叛徒和敌军的间谍，左右将军们的决定又扰乱整体

军队的秩序，在进行共识时，结果并不代表大多数人的意见。这时候，在已知有成员不可靠

的情况下，其余忠诚的将军在不受叛徒或间谍的影响下如何达成一致的协议，拜占庭问题就

此形成。拜占庭假设是对现实世界的模型化，由于硬件错误、网络拥塞或断开以及遭到恶意

攻击，计算机和网络可能出现不可预料的行为。

Lamport 一直研究这类问题，发表了一系列论文。但综合总结一下就是回答下面三个问题：

1.类似拜占庭将军这样的分布式一致性问题是否有解？

2.如果有解的话需要满足什么样的条件？

3.在特定前提条件的基础上，提出一种解法。

前两个问题 Lamport 在论文《拜占庭将军问题》已经回答，而第三个问题在后来的论文

《The Part-Time Parliament》中提出了一种算法并命名为 Paxos。这篇论文使用了大量的数

学证明，而我基本就看不懂了（数学符号都认不全-｡-;），考虑到大家理解起来都比较困难，

后来 Lamport 又写了另外一篇论文《Paxos Made Simple》完全放弃了所有数学符号的证明，

使用纯英文的逻辑推导。我勉强逐字看了一遍，然后感觉若有所悟，但你问我搞懂了吗，我

的标准应该还是没懂。对我来说理解一个算法有个明确的标准，就是真的懂了会在头脑里能

将算法映射为代码，而看完后面一篇论文仅仅是若有所悟还达不到能映射为代码的清晰度。

虽然 Lamport 认为 Paxos 很 simple，但也许只是针对他的头脑而言。事实是大家理解起来

都还是很困难，所以 Raft 就是建立在希望得到一个更易于理解的 Paxos 算法的替代品。把

可理解性作为算法的主要目标之一，从论文题目就可看出来《In Search of an Understandable

Consensus Algorithm》。

在进入正题前，我想起一个旧故事可以很直观的感受对一个问题不同的思维视角在可理解性

上的差异。

不同视角的可理解性

依稀记得大约在二十年前，我还在读初中时在一本可能大概叫《数学中的发散思维》（不能

很清晰记得书名了）的书中看到这么一个有趣的问题。

甲乙两人轮流在一张圆桌上平放黑白围棋子，每次放一子，棋子不许重叠，谁先没有地方放

就输。

请问怎样放才能赢？

这个问题有两层意思，第一，有没有一种放法保证必赢？第二，如果有怎么证明？这里先停

顿下，思考十秒钟。

剩余6页未读，继续阅读

内容反馈

版权申诉

小小哭包

粉丝: 2097

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip