这个女生说：弄懂本文前，你所知道的区块链可能都是错的

在共识算法中，系统中的进程分别担任这三种角色：

• 提议者(Proposers)——也称作领导者(Leader)，发出请求或信息
• 决策者(Acceptors)——接收提议者的请求，输出响应值的进程
• 学习者(Learners)——系统中的其他进程，获得系统决定的终止值

定义一个共识算法的过程，通常有以下三个步骤：

第一步，选择

在所有进程中选择一个领导者。

领导者提出下一个有效的输出值。

第二步，投票

无故障的进程接收领导者的输出值，经过验证，把它当作下一个有效值提出。

第三步，决策

所有非故障的进程必须达成共识，以此决定正确的最终值，具体根据所有进程的投票数是否达到预设值。

否则，重复步骤一、二、三，再来一次。

这里需要注意，各种共识算法在一些细节上有所区别，比如：

• 术语(例如：回合、阶段、轮次)
• 处理投票的程序
• 决定最终值的标准(例如：有效性条件)

上面是共识算法定义的一般过程，满足定义中的一般条件，我们就可以构建一种算法，从而创建一个能够达成共识的分布式系统。

好像很简单的样子，有木有?

FLP 不可能性(FLP impossibility)

还差得远呢，我们要面对的最大的难题就是——FLP 不可能性(FLP impossibility)

首先回顾一下同步系统和异步系统的区别:

• 同步环境——信息传输所用时间是固定的
• 异步环境——信息传输所用时间无法预估

这个区别很重要。

在同步环境中，我们可以设定信息传输所需的最大时间，允许系统中的不同节点轮流提出新的事务，然后投票确定一项，跳过没有提出事务的节点。这种环境中，达成共识是可能的。

但是，如果想在同步环境中操作，就需要一个信息风险可控的环境，比如说在一个配备原子钟的数据中心，现实中很难操作。

原子钟：一种高精度计时装置，利用原子吸收或释放能量时发出的电磁波来计时，精度可达每 2000 万年误差 1 秒。

然而异步环境中，信息传输时间是不固定的，如果有某个进程出故障的话，实现终止将非常困难。

这种情况，被正式称为“FLP 不可能性结果”。

其中，FLP 是 Fischer、Lynch、Patterson 这三位学者名字组合的简写。

他们在 1985 年发表过这样一篇论文——《分布式共识的达成毁于一个出错的进程》，论文指出——在一个异步系统中，即使只有一个进程出错，那么分布式共识就无法达成。因为进程出错的时间是随机的，，如果恰巧在共识达成的时候，那么就枉费工夫了。

对于分布式计算领域来说，这无疑令人沮丧。尽管如此，科学家们仍在继续努力寻找规避 FLP 不可能性的方法。目前有两种：

• 方法一：使用同步假设
• 方法二：使用不确定性

四、一些基本的共识算法

方法一：使用同步假设

FLP 不可能性原理表明，在异步传输系统中，如果一个系统无法终止，那么就不能达成共识。

但是，如果不知道异步信息传输所需的时间，那该如何保证每个非故障进程都会决定一个输出值呢?

需要明确的是，这一发现并不代表共识无法达成，而是在异步传输环境中不能在固定的时间内达成。那就是说共识在某些时段还是可以达成的，只不过我们无法确定这个时间点。

解决这个问题的一种方法是使用超时。如果系统迟迟无法在一个值上终止，就等待一个超时，然后重新开始一轮运算。

这需要一些共识算法来支撑，其中的比较出名的是 Paxos 和 Raft。

Paxos算法

Paxos 是由 Leslie Lamport 在上世纪 90 年代提出的，这是第一个实用的容错共识算法，它已被谷歌和亚马逊(Amazon)等互联网巨头用于构建分布式服务。

Paxos 的工作机制如下：

阶段1：准备请求(prepare request)

• 提议者选择一个新的提议版本号 n，然后向决策者发送 “prepare request”。
• 如果决策者接收到这个 prepare request(“prepare”,n)，如果 n 大于任何他们已经回应过的 prepare request 的版本号，决策者就会发出 (“ack,” n, n’, v’) 或 (“ack,” n, ^ , ^)。
• 决策者的答复是保证不接受任何版本号小于 n 的提议。
• 决策者把已接收到的最高版本号的提议中的值 v 作为建议值。否则，他们用 ^ 回应。

（编辑：源码网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!