共识问题有哪些

1、共识代表了一种依赖技术和协议的共同协商的机制。共识可以被用来认可网络节点的身份，同时实现一整套分布式系统之间提出的互相支持的规则。共识在数据验证、可信存储和较高的数据安全性上尤为重要。

2、共识的一个重要挑战是确保节点的收益与各自的参与相当。不同一致性协议提供了选择，但也伴随着一系列技术上的挑战和威胁，包括黑客攻击、节点故障等，也会极大地影响网络的总体可靠性。

3、另一个共识问题是，分布式系统可能会进入不一致状态和偏离共识机制的结果。当发生冲突时，不同网络节点的计算结果可能出现偏差。引入经典的冲突检测和决议算法可以检测和解决这类问题，但这仍然需要大量的复杂性来实现。

4、冗余已经被证明是共识系统中不可或缺的一部分。它是保护共识系统免受意外失败和有意恶意攻击的方法，这些攻击可能会导致失败，毀坏或窃取数据。攻击者可以攻击一个共识系统来**其共识，获取其他人的私有数据，或者篡改网络中的交易数据。

5、了解参与方之间的真实身份也是共识系统中的重要任务。参与节点必须被适当认证并拥有可信的识别令牌，以确保参与方身份的真实性。如果一个节点不可信，那么它就会**此共识机制，导致数据的损坏或丢失。

6、覆盖分布式网络中的所有节点也是一个重要考虑因素。网络中的每个节点都需要参与共识以保证其一致性，但在巨大的网络中，维护这种共识可能是一个巨大的挑战，涉及向大量节点传输数据、确保节点的安全性以及准确和可靠地广播数据。

7、节点访问授权对维护共识也是一个显著的挑战。访问权限是共识系统的核心，但它也可能会限制其安全性和功能，如果参与的方不能参与消息传播，共识系统就可能失败。为了避免这种情况，网络中的每个节点都必须拥有确定和**的访问权限，以及使用准确、可信和可靠而且容易检查的识别机制。

8、随着网络规模的扩大，区块链节点的进行冗余和可用性也是一项重要考量。确保节点间可靠性的同时，也需要确保节点的安全和可用性。这通常要求将区块链节点分片，以提高网络拓扑和保护性等方面的管理性能，但又不会损害共识机制和分布式应用程序，甚至程序的正确性。

网上很多讨论 paxos 或 raft 的博客使用“分布式一致性协议”或者“分布式一致性算法”这样的字眼，虽然在汉语中“达成共识”和“达成一致”是一个意思，但是必须要说明在这里讨论的是 consensus 问题，使用“共识”来表达更清晰一些。而 CAP 定理中的 C 和数据库 ACID 的 C 才是真正的“一致性”—— consistency 问题，尽管这两个 C 讨论的也不是同一个问题，但在这里不展开。

为了规范和清晰表达，在讨论 consensus 问题的时候统一使用“共识”一词。

时间线

注：在早些的文献中，共识（consensus）也叫做协商（agreement）。

共识问题

那么共识问题到底是什么呢？举个生活中的例子，小明和小王出去聚会，小明问：“小王，我们喝点什么吧？”小王：“喝咖啡怎么样？”小明：“好啊，那就来杯咖啡。”

在上面的场景中，小王提议喝一杯咖啡，小明表示同意，两人就“喝杯咖啡”这个问题达成共识，并根据这个结果采取行动。这就是生活中的共识。

在分布式系统中，共识就是系统中的多个节点对某个值达成一致。共识问题可以用数学语言来描述：一个分布式系统包含 n 个进程 {0, 1, 2,..., n-1}，每个进程都有一个初值，进程之间互相通信，设计一种算法使得尽管出现故障，进程们仍协商出某个不可撤销的**决定值，且每次执行都满足以下三个性质：

• 终止性（Termination）：所有正确的进程**都会认同某一个值。
• 协定性（Agreement）：所有正确的进程认同的值都是同一个值。
• 完整性（Integrity），也称作有效性（Validity）：如果正确的进程都提议同一个值，那么所有处于认同状态的正确进程都选择该值。

完整性可以有一些变化，例如，一种较弱的完整性是认定值等于某些正确经常提议的值，而不必是所有进程提议的值。完整性也隐含了，**被认同的值必定是某个节点提出过的。

为什么要达成共识？

我们首先介绍分布式系统达成共识的动机。

在前文中，我们已经了解到分布式系统的几个主要难题：

• 网络问题
• 时钟问题
• 节点故障问题

**篇提到共识问题的文献来自于 lamport 的 "Time, Clocks and the Ordering of Events in a Distributed System"，尽管它并没有明确的提出共识(consensus)或者协商(agreement)的概念。论文阐述了在分布式系统中，你无法判断事件 A 是否发生在事件 B 之前，除非 A 和 B 存在某种依赖关系。由此还引出了分布式状态机的概念。

Raft 算法的状态机

在分布式系统中，共识就常常应用在这种多副本状态机（Replicated state machines），状态机在每台节点上都存有副本，这些状态机都有相同的初始状态，每次状态转变、下个状态是什么都由相关进程共同决定，每一台节点的日志的值和顺序都相同。每个状态机在“哪个状态是下一个需要处理的状态”这个问题上达成共识，这就是一个共识问题。

**，这些节点看起来就像一个单独的、高可靠的状态机。Raft 的论文提到，使用状态机我们就能克服上述三个问题：

• 满足在所有非拜占庭条件下确保安全（不会返回错误结果），包括网络延迟、分区、丢包、重复和重排序。
• 不依赖于时序。
• 高可用。只要集群中的大部分节点正常运行，并能够互相通信且可以同客户端通信，这个集群就**可用。因此，拥有5个节点的集群可以容忍其中的2个节点失败。假使通过停掉某些节点使其失败，稍后它们会从**化存储的状态进行恢复，并重新加入到集群中。

不仅如此，达成共识还可以解决分布式系统中的以下经典问题：

• 互斥（Mutual exclusion）：哪个进程进入临界区访问资源？分布式锁？
• 选主（Leader election）：在单主复制的数据库，需要所有节点就哪个节点是领导者达成共识。如果一些由于网络故障而无法与其他节点通信，可能会产生两个领导者，它们都会接受写入，数据就可能会产生分歧，从而导致数据不一致或丢失。
• 原子提交（Atomic commit）：跨多节点或跨多分区事务的数据库中，一个事务可能在某些节点上失败，但在其他节点上成功。如果我们想要维护这种事务的原子性，必须让所有节点对事务的结果达成共识：要么**提交，要么**中止/回滚。

总而言之，在共识的帮助下，分布式系统就可以像单一节点一样工作——所以共识问题是分布式系统最基本的问题。

系统模型

在考虑如何达成共识之前，需要考虑分布式系统中有哪些可供选择的计算模型。主要有以下几个方面：

网络模型：

• 同步（Synchronous）：响应时间是在一个固定且已知的有限范围内。
• 异步（Asynchronous）：响应时间是**的。

故障类型：

• Fail-stop failures：节点突然宕机并停止响应其它节点。
• Byzantine failures：源自“拜占庭将军问题” ，是指节点响应的数据会产生无法预料的结果，可能会互相矛盾或**没有意义，这个节点甚至是在“说谎”，例如一个被黑客入侵的节点。

消息模型：

• 口头消息(oral messages)：消息被转述的时候是可能被篡改的。
• 签名消息(signed messages)：消息被发出来之后是无法**的，只要被篡改就会被发现。

作为最常见的，我们将分别讨论在同步系统和异步系统中的共识。在同步通信系统中达成共识是可行的(下文将会谈论这点)，但是，在实际的分布式系统中同步通信是不切实际的，我们不知道消息是故障了还是延迟了。异步与同步相比是一种更通用的情况。一个适用于异步系统的算法，也能被用于同步系统，但是反过来并不成立。

异步与同步相比是一种更通用的情况

让我们先从异步的情况开始。

异步系统中的共识

FLP 不可能（FLP Impossibility）

早在 1985 年，Fischer、Lynch 和 Paterson （FLP）在 "Impossibility of Distributed Consensus with One Faulty Process" 证明了：在一个异步系统中，即使只有一个进程出现了故障，也没有算法能保证达成共识。

简单来说，因为在一个异步系统中，进程可以随时发出响应，所以没有办法分辨一个进程是速度很慢还是已经崩溃，这不满足终止性（Termination）。详细的证明已经超出本文范围，不在细述。

此时，人们意识到一个分布式共识算法需要具有的两个属性：安全性(safety)和活性(liveness)。安全性意味着所有正确的进程都认同同一个值，活性意味着分布式系统**会认同某一个值。每个共识算法要么牺牲掉一个属性，要么放宽对网络异步的假设。

虽然 FLP 不可能定理听着让人望而生畏，但也给后来的人们提供了研究的思路——不再尝试寻找异步通信系统**识问题**正确的解法。FLP 不可能是指无法确保达成共识，并不是说如果有一个进程出错，就**无法达成共识。这种不可能的结果来自于算法流程中最坏的结果：

• 一个**异步的系统
• 发生了故障
• **，不可能有一个确定的共识算法。

针对这些最坏的情况，可以找到一些方法，尽可能去绕过 FLP 不可能，能满足大部分情况下都能达成共识。《分布式系统：概念与设计》提到一般有三种办法：

1. 故障屏蔽（Fault masking）
2. 使用故障检测器（Failure detectors）
3. 使用随机性算法（Non-Determini**）

1、故障屏蔽（Fault masking）

既然异步系统中无法证明能够达成共识，我们可以将异步系统转换为同步系统，故障屏蔽就是**种方法。故障屏蔽假设故障的进程**会恢复，并找到一种重新加入分布式系统的方式。如果没有收到来自某个进程的消息，就一直等待直到收到预期的消息。

例如，两阶段提交事务使用**存储，能够从崩溃中恢复。如果一个进程崩溃，它会被重启（自动重启或由管理员重启）。进程在程序的关键点的**存储中保留了足够多的信息，以便在崩溃和重启时能够利用这些数据继续工作。换句话说故障程序也能够像正确的进程一样工作，只是它有时候需要很长时间来执行一个恢复处理。

故障屏蔽被应用在各种系统设计中。

2、使用故障检测器（Failure detectors）

将异步系统转换为同步系统的第二个办法就是引入故障检测器，进程可以认为在超过**时间没有响应的进程已经故障。一种很常见的故障检测器的实现：超时（timeout）。

但是，这种办法要求故障检测器是**的。如果故障器不**的话，系统可能放弃一个正常的进程；如果超时时间设定得很长，进程就需要等待（并且不能执行**工作）较长的时间才能得出出错的结论。这个方法甚至有可能导致网络分区。

解决办法是使用“不**”的故障检测器。Chanadra 和 Toueg 在 "The weakest failure detector for solving consensus" 中分析了一个故障检测器必须拥有的两个属性：

• **性（Completeness）：每一个故障的进程都会被每一个正确的进程怀疑。
• **性（Accuracy）：正确的进程没有被怀疑。

同时，他们还证明了，即使是使用不可靠的故障检测器，只要通信可靠，崩溃的进程不超过 N/2，那么共识问题是可以解决的。我们不需要实现 Strong Completeness 和 Strong Accuracy，只需要一个**弱故障检测器（eventually weakly failure detector），该检测器具有如下性质：

• **弱**性（eventually weakly complete）：每一个错误进程**常常被一些正确进程怀疑；
• **弱**性（eventually weakly accurate）：经过某个时刻后，至少一个正确的进程从来没有被其它正确进程怀疑。

该论文还证明了，在异步系统中，我们不能只依靠消息来实现一个**弱故障检测器。但是，实际的故障检测器能够根据观察到的响应时间调节它的超时值。如果一个进程或者一个到检测器的连接很慢，那么超时值就会增加，那么错误地怀疑一个进程的情况将变得很少。从实用目的来看，这样的弱故障检测器与理想的**弱故障检测器**接近。

3、使用随机性算法(Non-Determini**)

这种解决不可能性的技术是引入一个随机算法，随机算法的输出不仅取决于外部的输入，还取决于执行过程中的随机概率。因此，给定两个**相同的输入，该算法可能会输出两个不同的值。随机性算法使得“敌人”不能有效地阻碍达成共识。

和传统选出领导、节点再协作的模式不同，像区块链这类共识是基于哪个节点最快计算出难题来达成的。区块链中每一个新区块都由本轮最快计算出数学难题的节点添加，整个分布式网络持续不断地建设这条有时间戳的区块链，而承载了最多计算量的区块链正是达成了共识的主链（即累积计算难度**）。

比特币使用了 PoW（Proof of Work）来维持共识，一些其它加密货币（如 DASH、NEO）使用 PoS（Proof of Stake），还有一些（如 Ripple）使用分布式账本（ledger）。

但是，这些随机性算法都无法严格满足安全性(safety)。攻击者可以囤积巨量算力，从而控制或影响网络的大量正常节点，例如控制 50% 以上网络算力即可以对 PoW 发起女巫攻击（Sybil Attack）。只不过前提是攻击者需要付出一大笔资金来囤积算力，实际中这种风险性很低，如果有这么强的算力还不如直接挖矿赚取收益。

同步系统中的共识

上述的方法 1 和 2，都想办法让系统比较“同步”。我们熟知的 Paxos 在异步系统中，由于活锁的存在，并没有**解决共识问题（liveness不满足）。但 Paxos 被广泛应用在各种分布式系统中，就是因为在达成共识之前，系统并没有那么“异步”，还是有极大概率达成共识的。

Dolev 和 Strong 在论文 "Authenticated Algorithms for Byzantine Agreement" 中证明了：同步系统中，如果 N 个进程中最多有 f 个会出现崩溃故障，那么经过 f 1 轮消息传递后即可达成共识。

Fischer 和 Lynch 的论文 "A lower bound for the time to assure interactive consistency" 证明了，该结论同样适用于拜占庭故障。

基于此，大多数实际应用都依赖于同步系统或部分同步系统的假设。

同步系统中的拜占庭将军问题

Leslie Lamport、Robert Shostak 和 Marshall Pease 在 "拜占庭将军问题（The Byzantine General’s Problem)" 论文中讨论了 3 个进程互相发送未签名（口头的）的消息，并证明了只要有一个进程出现故障，就无法满足拜占庭将军的条件。但如果使用签名的消息，那么 3 个将军中有一个出现故障，也能实现拜占庭共识。

Pease 将这种情况推广到了 N 个进程，也就是在一个有 f 个拜占庭故障节点的系统中，必须总共至少有 3f 1 个节点才能够达成共识。即 N >= 3f 1。

虽然同步系统下拜占庭将军问题的确存在解，但是代价很高，需要 O(N^(f 1) ) 的信息交换量，只有在那些安全威胁很严重的地方使用（例如：航天工业）。

PBFT 算法

PBFT(Practical Byzantine Fault Tolerance) 算法顾名思义是一种实用的拜占庭容错算法，由 Miguel Castro 和 Barbara Liskov 发表于 1999 年。

算法的主要细节不再展开。PBFT 也是通过使用同步假设保证活性来绕过 FLP 不可能。PBFT 算法容错数量同样也是 N >= 3f 1，但只需要 O(n^2 ) 信息交换量，即每台计算机都需要与网络中其他所有计算机通讯。

虽然 PBFT 已经有了**的改进，但在大量参与者的场景还是不够实用，不过在拜占庭容错上已经作出很重要的突破，一些重要的思想也被后面的共识算法所借鉴。