共计 4116 个字符，预计需要花费 11 分钟才能阅读完成。
分布式一致性问题实质上能够从两个维度来意识：一是如何就某一个值达成统一的决策；二是如何就一系列间断的值达成统一的程序决策。很显然，如果咱们可能找到问题一的解决方案，那么问题二也就迎刃而解了。上面咱们就从一个生存中的小问题来动手，看看如何去设计一个正当的算法来解决问题一。
有这样一个家庭，由 6 个成员组成，别离是爸爸妈妈、爷爷奶奶、姐姐和一个 3 岁的弟弟。这一天，大家要线上决定一下今天出游时，弟弟戴什么色彩的帽子。因为此时 5 位家长分处在不同的中央（分布式系统），因而只能通过微信来交换（局部同步网络）。咱们尝试通过这样一个案例来分析一个最简略的共识问题。
单点故障
既然目标是要做出一个统一的决策，最简略的形式就是找出一个公信度最高的人，由他负责给出一个决策，大家都批准即可。比方，咱们始终抉择妈妈的决策，因为平时都是妈妈负责弟弟的着装。可是如果每次决策都须要期待妈妈的提案的话，不免有时候妈妈的手机会不在线，比方在坐飞机的时候手机开了航行模式。因而，始终抉择一个人来做决定是不行的。这种因为一个参与方就导致整个集群呈现阻塞的状况就是典型的单点故障问题。
多数遵从少数
既然由一个人来做决策不牢靠，最容易想到的一个解决方案就是：多数遵从少数。即每次决策都至多失去半数以上人的批准才能够通过。当然，这里咱们不思考有人乱投票，即向不同人发送不一样的投票（拜占庭谬误）。以以后的场景为例，5 集体当中须要至多 3 集体承受（accept）同一个提案能力表明该提案值被选定（chosen）。并且咱们须要保障一旦某个提案值被选定了，就不可能在后续呈现另外一个提案值也被选定。
注：这里的选定（chosen）是全局视角的，而承受（accept）是单个人的视角的，即同一个人可能会承受屡次提案，然而整个群体最终只能选定一个提案值。
▲场景 1
首先仍旧给出一个最简略的计划，为了可能实现最终的决策，咱们规定每个人必须承受他收到的第一个提案，这样也能够调动起大家的踊跃心，如果想要本人的提案通过就必须疾速想出一种色彩并收回提案。
然而，这种计划可能导致一种无奈实现决策的窘境。如上图所示，爸爸提出了红色帽子，感觉比拟正能量！并及时将提案私戳给了妈妈，妈妈也欣然接受。简直同一时间，爷爷提出了蓝色帽子，感觉比拟复旧！并及时将提案私戳给了奶奶，奶奶也欣然接受。而姐姐认为绿色比拟时尚，然而等她将音讯发送进来后，发现大家都曾经有了本人的抉择。最终造成了 2 -2- 1 的场面，没有哪个提案可能达到半数以上（>=3）。因而，咱们发现，如果想要最终实现决策，有些人可能要承受多个不同的提案。
▲场景 2
既然如此，咱们再思考如下计划，即每个人都承受他收到的所有提案。
这次，咱们只思考有两个人发动了提案，别离是爸爸的红色提案和姐姐的绿色提案。如果爸爸的提案曾经取得了 3 票的批准达到了选定状态，随后姐姐才发动提案，依据每个人都承受所有提案的准则，绿色提案最终也可能达到选定状态。显然，这种计划违反了唯一性的准则，如果始终这样运行上来可能最终也没法选定一个提案值。
此时，咱们发现一个问题，即爸爸的红色提案既然当时曾经达到了选定状态，那么咱们能够让姐姐在提案之前确认下所有人的状态，如果曾经有半数节点对某个提案值达成了共识（即达到了选定状态），那么姐姐就能够进行收回提案，或者再收回一个蕴含雷同提案值的提案来保障唯一性。这样是否就可能解决问题了呢？
▲场景 3
场景 2 中的问题仍然存在，如上图所示，如果爸爸和姐姐别离当时确认了下所有人的状态都处在未投票的状态，并顺次收回了各自的提案，因为爸爸是别离私戳的，因而音讯有肯定的提早，而姐姐间接拉了一个群聊一次性告诉给了爷爷和奶奶，因而姐姐的提案先于爸爸的提案达到选定状态，稍后等爸爸的提案告诉到了妈妈和爷爷的时候，他们又该如何决策呢？
通过下面的问题，咱们发现，为了避免整个决策进入到一种无奈终止的状态，咱们还须要通过某种形式对提案进行排序，从而回绝一些旧的、有效的提案，并及时地向提案者反馈本人承受的提案值，防止提案者始终发动雷同的提案。也就是说，如果爷爷在收到爸爸的提早提案时，可能晓得先前曾经存在一个更新的提案（姐姐的提案）并回绝旧提案，同时告知爸爸曾经承受了姐姐的绿色提案的话，就能够避免出现多种提案达到选定状态的窘境。
例如，咱们能够别离为 5 集体调配一系列提案号，提案号按如下规定递增：
同时做如下规定：
一条提案由提案值 color 和提案号 seqNo 组成，可示意为(color, seqNo)
每个人记录下本人收到的最大提案号，并回绝提案号比它更小的提案
当提案者收到一个曾经被承受的提案时，必须无条件承受该提案，否则有可能陷入有限提案的循环
每个提案都须要分为两阶段来实现，别离为当时询问阶段（Prepare）与最终确认阶段（Accept），其中询问阶段用来确定一个序号值 seqNo 并及时检测出是否曾经存在被承受的提案值，确认阶段用来确定一个提案值 color。
场景 1 的解决方案比较简单，即在肯定工夫内无奈收到大多数人的批准音讯（异步网络）之后，尝试用新的提案号再发动一次提案，直到某次提案音讯可能胜利传达到大多数人（同步网络）后，即可实现决策。
上面咱们来看一下如何解决场景 2 与场景 3。
注：下图中，以 P n 示意当时询问音讯，询问其余节点是否承受提案号 n；以 R(v, n)示意响应音讯，告知提案者以后曾经承受的最大提案号和提案值；以 A(v, n)示意最终确认音讯，通知其余节点尝试最终确认一个提案值 v，其提案号为 n。
场景 2 解决方案
对于曾经达成选定状态的提案，咱们能够保障后续的提案不会笼罩原先的提案值。
此时提案决策流程如下：
爸爸应用提案号 1 发动询问
爸爸、妈妈、爷爷都批准提案号 1，并且反馈以后未接管任何提案值，提案号默认为 0（空投票）
因为收到了大多数人（>=3）的批准，爸爸收回最终确认音讯给到了大多数人，提案号为 1，提案值为红色，此时红色其实曾经达到选定状态
姐姐应用提案号 5 发动询问
因为提案必须通过至多 3 人批准，而任选 3 人必然与此前批准爸爸提案的人群有交加（例如爷爷），因而处在交集中的人可能及时反馈之前曾经批准的提案，即 1 号红色提案，其余人还是反馈空投票
姐姐在等到大多数人的反馈后果之后，发现此前曾经有提案被其他人批准了，抉择提案号最高的那个提案值（红色），笼罩本人的提案值（绿色）
姐姐收回最终确认音讯，提案号为 5，提案值为红色
最终所有人都承受了红色提案，尽管提案号可能不尽相同
场景 3 解决方案
对于未达成选定状态的提案，如果有新的提案提出，最终选定的提案值可能有两种状况。
第一种状况是新提案者可能发现旧的提案值，最终会选定旧的提案值。
第二种状况是新提案者不可能发现旧的提案值，最终会选定新的提案值。
场景 3 - 1 解决方案
新提案者可能发现旧的提案值，最终会选定旧的提案值。
此时提案决策流程如下：
爸爸应用提案号 1 发动询问
爸爸、妈妈、爷爷都批准提案号 1，并且反馈以后未接管任何提案值，提案号默认为 0（空投票）
因为收到了大多数人（>=3）的批准，爸爸收回最终确认音讯，然而因为音讯提早的起因，最终确认音讯只发送到了爸爸、爷爷。妈妈提早承受了该音讯，因而红色其实并未达到选定状态
姐姐应用提案号 5 发动询问
因为提案必须通过至多 3 人批准，而如果此时选中的 3 人中凑巧有一人承受过爸爸的最终确认音讯（例如爷爷），他会立刻反馈之前曾经批准的提案，即 1 号红色提案，其余人还是反馈空投票
姐姐在等到大多数人的反馈后果之后，发现此前曾经有提案被其他人批准了，抉择提案号最高的那个提案（红色），笼罩本人的提案值（绿色）
姐姐收回最终确认音讯，提案号为 5，提案值为红色
妈妈提早接管到了爸爸的最终确认音讯，因为没有收到提案号更大的提案，因而也承受了红色提案
最终所有人都承受了红色提案，尽管提案号可能不尽相同
场景 3 - 2 解决方案
新提案者不可能发现旧的提案值，最终会选定新的提案值。
此时提案决策流程如下：
爸爸应用提案号 1 发动询问
爸爸、妈妈、爷爷都批准提案号 1，并且反馈以后未接管任何提案值，提案号默认为 0（空投票）
因为收到了大多数人（>=3）的批准，爸爸收回最终确认音讯，然而因为音讯提早的起因，最终确认音讯只发送到了爸爸、妈妈。爷爷提早承受了该音讯，因而红色其实并未达到选定状态
姐姐应用提案号 5 发动询问
因为提案必须通过至多 3 人批准，而如果此时选中的 3 人中凑巧都没有人承受过爸爸的最终确认音讯，那么姐姐会收到 3 集体反馈的空投票
因为收到了大多数人（>=3）的批准，姐姐收回最终确认音讯给到了大多数人，提案号为 5，提案值为绿色，此时绿色其实曾经达到选定状态
妈妈提早接管到了爸爸的最终确认音讯，因为之前曾经承受了提案号更大的提案，因而拒接爸爸的旧提案值，并将新提案值及时反馈给爸爸
爸爸在收到拒接响应音讯后，会尝试从头开始从新发动提案，最终抉择绿色提案
最终所有人都承受了绿色提案，尽管提案号可能不尽相同
总结
总结一下，为了可能让决策最终可能收敛，其实咱们曾经显式或者隐式地做了一些束缚：
1. 每个人的手机须要实时在线（即不能呈现宕机、掉线等的非拜占庭谬误）并且任意一条微信音讯都能够在肯定时延内收到（同步网络模型），当呈现网络断开的场景时，可能会导致共识无奈达成
2. 每个人都须要严格依照上述规定进行提案 / 投票，不能有胡乱提案 / 投票的动作（拜占庭行为）
下面其实就是使用了经典分布式一致性算法 Paxos 的原理。然而 Paxos 解决的仅仅是一个最根本的共识的问题，即在非拜占庭的同步网络环境下，如何就一个决策值达成统一。如果零碎进入了异步网络环境呢（例如妈妈的手机都没信号了）？如果呈现了拜占庭节点呢（例如爷爷成心向爸爸投票红色，向姐姐投票绿色）？当咱们将这一系列的问题思考进去之后，整个问题就变得复杂的多了。
好在前人曾经给咱们提供了十分多的实践根底，为了应答不同的问题，曾经呈现了十分多优良的共识算法。大家感兴趣的话，前面会有具体的共识算法分类介绍，为大家全面地展现不同场景下共识算法的抉择与衡量。
增加小助手桔子（18458407117）退出技术交换群，欢迎您和咱们共享观点，共论区块链的有限将来～
作者简介
端豪
趣链科技根底平台部共识算法钻研小组
