分布式共识历史简介

秒速五厘米 2022-09-02 07:49 391阅读 0赞

历史：1988年，Liskov发文指出了主从备份的算法，而Leslie Lamport在1989年才提出了Paxos这个名词。但是知道1998年才正式发表。而Liskov团队后来在1999年提出了风靡一时的PBFT（使用的拜占庭容错算法）算法。

paxos是分布式共识算法的灵魂，以至于谷歌在08发表的大数据经典论文《The Chubby lock service for loosely-coupled distributed systems》中直接指出“所有异    步共识的协议，其本质核心都是Paxos”

目标：分布式系统中有n个节点，其中还最多有f个节点可能崩溃，也就是说又n-f个节点是好的。节点i发送一个消息，使得这个消息，被大多数节点接收，并且满足：

一致性：所有好节点的决策相同。

可终止性：所有好节点在有限的时间内结束决策过程。

有效性：选择出的决策之必须是某个节点的输入值。

FLP原理：在网络可靠，存在节点失效（ 即便只有一个） 的最小化异步模型系统

中，不存在一个可以解决一致性问题的确定性算法。

基于此我们在工程上需要多次尝试，获取最终一致性和多数情况下的一致性，而CAP理论告诉我们工程上的界限。

CAP理论：一个分布式系统最多只能同时满足一致性（Consistency）、可用性（Availability）和分区容错性（Partition tolerance）这三项中的两项。

共识算法：

拜占庭容错（BFT） Byzantine Fault Tolerance，非拜占庭容错（CFT） Crash Fault Tolerance

CFT认为机器可能宕机，网络可能异常，但是所有信息真实可信。BFT在CFT的基础上，认为出错的机器是可能说谎的。 CFT模型容错需要至少2f+1台机器，BFT模型容错需要至少3f+1台机器

BFT代表的算法：PBFT（基于两阶段提交的算法）POW（工作流证明算法）XFT（ Cross Fault Tolerance）

CFT代表的算法：Paxos，Raft及其变种

拜占庭问题：

在一个网络中，存在一些呈现任意行为的节点（包括谎报，沉默，串谋），且只有f个节点是坏的，即存在总数n>=3f+1，如果一个算法在这种情况下，可用，满足一致性，可终止性，有效性，则称之为有效的算法。

证明：

若提案人不是叛变者，提案人发送一个提案出来，收到的叛变者可以宣称收到的是相反的命令。则对于第三个人（忠诚者）会收到两个相反的消息，无法判断谁是叛变者，则系统无法达到一致。

若提案人是叛变者，发送两个相反的提案分别给另外两人，另外两人都收到两个相反的消息，无法判断究竟谁是叛变者，则系统无法达到一致。

更一般的，当提案人不是叛变者，提案人提出提案信息 1，则对于合作者来看，系统中会有 N - F 份确定的信息 1，和 F 份不确定的信息（可能为 0 或 1，假设叛变者会尽量干扰一致的达成），N − F > F，即 N > 2F 情况下才能达成一致。

当提案人是叛变者，会尽量发送相反的提案给 N - F 个合作者，从收到 1 的合作者看来，系统中会存在 (N - F)/2 个信息 1，以及 (N - F)/2 个信息 0；从收到 0 的合作者看来，系统中会存在 (N - F)/2 个信息 0，以及 (N - F)/2 个信息 1；

另外存在 F − 1 个不确定的信息。合作者要想达成一致，必须进一步的对所获得的消息进行判定，询问其他人某个被怀疑对象的消息值，并通过取多数来作为被怀疑者的信息值。这个过程可以进一步递归下去。

关于典型共识共识的容错算法：

paxos算法：分布式中没有恶意节点的情况，在两阶段提交中，通过保持最大的提案号来确保提案通过，每次只要超过半数即可。

PBFT （拜占庭容错算法）：通过预准备（提交提案），准备（各个节点收到提案进行广播），提交（各节点收到一定的请求，则进行提交）。

具体为预准备阶段，主节点提案请求 携带提案编号广播消息，准备阶段各个节点收到消息，验证提案号后发送准备消息，接收其他节点的准备消息，且接收数量>=2f+1节点数量，本节点进入准备阶；提交阶段，主节点广播commit请求。此算法可以在N>=3F+1时保持正确

raft算法：类似于多主从结构，选举出leader再进行两阶段提交。其他节点作为follower遵守leader的决定。Follower变身candidate 选举为Leader，由leader进行操作，同步到Follower。

典型应用：redis3.0，在redis集群中，分片确定每个主从结构管理哪个区域的key-value集合。在A主从中

n个从节点选出一个主节点来进行数据的插入操作，自己则同步执行主节点的操作。一起接受读的压力，使用主节点来进行写的操作。

区块链共识机制：

POW算法：

使用算力证明，破解Hash问题，谁到答案，谁先获得优先记录权益。当掌握全网超过一半算力的时候，可以发动51%攻击。

POS算法：

它是Pow的一种升级共识机制，根据每个节点所占代币的比例和时间，等比例的降低挖矿难度，从而加快找随机数的速度

DPOS算法：

DPOS与POS原理相同，只是选了一些“人大代表”，以EOS为例，选举出30个记账节点，21个为记账节点，剩下9个为备用节点，由21个节点进行记账，一旦某个节点不能行使职责，则剩下9个去替代它的位置。

分布式共识历史简介

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关 python 简介与发展历史

相关宇宙历史简介（地址纪元）

相关 Python简介、历史及优缺点

相关 Python简介、历史及优缺点

相关分布式基础(6)-分布式共识之Paxos、Raft算法

相关分布式共识算法之Raft算法

相关分布式共识历史简介

相关区块链常见共识机制简介

相关 Dojo历史简介

相关 Windows系统历史版本简介