区块链学习之分布式系统核心问题（四）

摘要：区块链系统首先是一个分布式系统，分布式系统的核心问题包括一致性共识一致性问题一致性问题是分布式领域最为基础也是最重要的问题。算法与算法问题是指分布式系统中存在故障，但不存在恶意节点的场景即可能消息丢失或重复，但无错误消息下的共识达成问题。

区块链系统首先是一个分布式系统，分布式系统的核心问题包括一致性、共识

一致性问题是分布式领域最为基础也是最重要的问题。如果分布式系统能实现“一致”，对外就可以呈现为一个完美的、可扩展的“虚拟节点”，相对物理节点具备更优越性能和稳定性。

一致性：早期也叫 agreement ，是指对于分布式系统中的多个服务节点，给定一系列操作，在约定协议的保障下，试图使得它们对处理结果达成“某种程度的认同”。
注： 一致性并不代表结果正确与否，而是系统对外呈现的状态一致与否；例如： 所有节点都达成失败状态也是一种一致

分布式计算机集群系统中，如下几个方面很容易出现问题：

节点之间的网络通信是不可靠的，包括消息延迟、乱序和内容错误等

节点的处理时间无法保障，记过可能出现错误，甚至节点自身可能发生宕机

同步调用可以简化设计，但会严重降低分布式系统的可扩展性，甚至使其退化为单点系统

现代分布式系统处理一致性问题的基础思路： 将可能引发不一致的并行操作进行串行化。

分布式系统达成一致的过程，应该满足：

可终止性： 一致的结果在有限时间内能完成

约同性： 不同几点最终完成决策的记过是相同的

合法性： 决策的结果必须是某个节点提出的提案

事件发生的先后顺序十分重要，这也是解决分布式系统领域很多问题的核心秘诀： 把多件事情进行排序，而且这个顺序还得是大家都认可的。

要实现绝对理想的严格一致性 代价很大。实际上，越强的一致性要求往往会造成越弱的处理性能，以及越差的可扩展性。
一般来讲，强一致性主要包括下面两类：

顺序一致性： 是一种比较强的约束，保证所有进程看到的全局执行顺序一致，并且每个进程看自身的执行顺序跟实际发生顺序一致。顺序一致性实际上限制了各进程内指令的偏序关系，但不在进程间按照物理时间进行全局排序；

线性一致性： 在顺序一致性前提下加强了进程间的操作顺序，形成唯一的全局顺序（系统等价于是顺序执行，所有进程看到的所有操作序列顺序都一致，并且跟实际发生顺序一致），是很强的原子性保证。但是比较难实现，目前基本上要么依赖于全局的时钟或锁，要么通过一些复杂算法实现，性能往往不高。

由于强一致性的系统往往比较难实现，而且很多时候，实际需求并没有那么严格需要强一致性。因此，可以适当地放宽对一致性的要求，从而降低系统实现的难度。例如在一定约束下实现所谓 最终一致性：即总会存在一个时刻（而不是立刻），让系统达到一致的状态。大部分Web系统实现的都是最终一致性。相对强一致性，这一类在某些方面弱化的一致性都笼统称为 弱一致性。

共识在很多时候会与一致性放在一起讨论，严谨地讲，两者的含义并不完全相同。
一致性往往指分布式系统中多个副本对外呈现的数据的状态。而共识则描述了分布式系统中多个节点之间，彼此对某个状态达成一致结果的过程。因此，一致性描述的是结果状态，共识则是一种手段。达成某种共识并不意味着就保障了一致性。

实践中，要保障系统满足不同程度的一致性，核心过程往往需要通过共识算法来达成。共识算法 解决的是对某个提案大家达成一致意见的过程。提案 的含义在分布式系统中十分宽泛，如多个事件发生的顺序、某个键对应的值、谁是领导...等等，可以认为任何可以达成一致的信息都是一个提案。

对于分布式系统来说，各个几点通常都是相同的确定性状态机模型（又称状态机复制问题），从相同初始状态开始接收相同顺序的指令，则可以保证相同的结果状态。因此，系统中多个节点最关键的是对多个事件进行共识，即排序。

现实中，理想的分布式系统并不存在，不同节点之间通信存在延迟，并且任意环节都可能存在故障。
一般地，把出现故障（crash或fail-stop,即不响应）但不会伪造信息的情况称为“非拜占庭错误”或“故障错误”；伪造信息恶意响应的情况称为“拜占庭错误”，对应节点为拜占庭节点。

根据解决的是非拜占庭的普通错误情况还是拜占庭错误情况，共识算法可以分为：

Crash Fault Tolerance(CFT)类算法：经典的算法包括Paxos、Raft及其变种等，这类容错算法往往性能比较好，处理较快，容忍不超过一般的故障节点

Byzantine Fault Tolerance (BFT) 类算法：一般包括PBFT（Practical Byzantine Fault Tolerance）为代表的确定性系列算法、PoW为代表的概率算法等。对于确定性算法，一旦达成对某个结果的共识就不可逆转，即共识是最终结果。而概率类算法，共识结果则是临时的，随着时间推移或某种强化，共识结果被推翻的概率越来越小，称为事实上的最终结果。拜占庭类容错算法往往性能较差，容忍不超过1/3的故障几点。

科学家证明： 即便在网络通信可靠情况下，可扩展的分布式系统的共识问题，其通用解法的理论下限是——没有下限（无解）。
这个结论称为“FLP不可能原理”。该原理可看做分布式领域里的“测不准原理”

FLP不可能原理：在网络可靠，但允许节点失效（即便只有一个）的最小化异步模型系统中，不存在一个可以解决一致性问题的确定性共识算法。

FLP 不可能原理告诉人们，不要浪费时间，去为异步分布式系统设计在任意场景下都能实现共识的算法

在分布式系统中，同步和异步这两个术语存在特殊的含义。
同步：是指系统中的各个几点的时钟误差存在上线；并且消息传递必须在一定时间内完成，否则认为失败；同时各个节点完成处理消息的时间是一定的。对于同步系统，可以很容易地判断消息是否丢失。

异步：指系统中各个节点可能存在较大的时钟差异，同时消息传输时间是任意长的，各几点对消息进行处
理的时间也可能是任意长的，这就造成无法判断某个消息迟迟没有被响应是哪里出了问题（节点故障还是传输故障？现实中的系统往往都是异步系统）

FLP原理实际上说明对于允许节点失效情况下，纯粹异步系统无法确保一致性在有限时间内完成。即便对于非拜占庭错误的前提下，包括Paxos、Raft等算法也都存在无法达成共识的情况，只是在工程实践中这种情况出现的概率很小。

总结：科学告诉你什么是不可能的；工程则告诉你，付出一些代价，可以把它变成可行。那我们在付出一些代价的情况下，共识的达成上，能做到多好？（CAP原理）

CAP 原理被认为是分布式系统领域的重要原理之一

CAP原理：分布式计算系统不可能同时确保以下三个特性：一致性、可用性和分区容忍性，设计中往往需要弱化对某个特性的保证。

一致性： 任何操作应该都是原子的，发生在后面的事件能看到前面事件发生导致的记过，注意这里指的是强一致性。

可用性： 在有限时间内，任何非失败节点都能应答请求

分区容忍性： 网络可能发生分区，即节点之间的通信不可保障

网络分区：网络设备故障导致的网络分裂。比如，存在ABCDE五个节点，AB处于同一子网，BCD处于另外一子网，中间通过交换机相连。若两个子网间的交换机故障了即发生了网络分区，AB和CDE便不能通讯。

CAP 三种特性不可同时得到保障，则设计系统是必然要弱化对某个特性的支持，那么可能出现下面三个应用场景

弱化一致性： 对结果一致性不敏感的应用，可以允许在新版本上线后过一段时间才最终更新成功，期间不保证一致性

弱化可用性： 对结果一致性很敏感的应用,如： 银行取款机

弱化分区容忍性： 现实中，网络分区出现概率较小，但较难完全避免。

ACID 原则指的是： Atomicity （原子性）、Consistency（一致性）、Isolation（隔离性）、Durability（持久性），这四种特性的缩写。ACID 是一种比较出名的描述一致性的原则，通常出现在分布式数据库领域，具体来说，ACID 原则描述了分布式数据库需要满足的一致性需求，同时允许付出可用性的代价。

ACID 特性如下：

Atomicity: 每次操作是原子的，要么成功，要么不执行

Consistency: 数据库的状态是一致的，无中间状态

Isolation: 各种操作彼此之间互相不影响

Durability: 状态的改变是持久的，不会失效

与ACID 相对的一个原则是 BASE （Basic Availability, Soft-state, Eventual Consistency）原则，牺牲掉对一致性的约束（但实现最终一致性），来换取一定的可用性。

Paxos 问题是指分布式系统中存在故障，但不存在恶意节点的场景（即可能消息丢失或重复，但无错误消息）下的共识达成问题。解决 Paxos 问题的算法主要有 Paxos 系列算法和 Raft 算法。

Paxos 是第一个广泛应用的共识算法，其原理基于“两阶段提交”算法并进行泛化和扩展，通过消息传递来逐步取消系统中的不确定状态。是后来不少共识算法设计的基础。

算法的基本原理是将节点点分为三种逻辑角色，在实现上通一个节点可以担任多个角色：

Proposer（提案者）: 提出以个提案，等待大家批准为结案。系统中提案都拥有一个自增的唯一提案号。往往由客户端担任该角色。

Acceptor（接受者）： 负责对提案进行投票，接受提案。往往由服务端担任该角色。

Learner（学习者）： 获取批准结果，并可以帮忙传播，不参与投票过程。可能为客户端或服务端。

算法需要满足 Safety（安全性）和 Liveness（活性）两方面的约束要求。实际上这两个基础属性也是大部分分布式算法都该考虑的：

Safety 约束： 保证决议结果是对的，无歧义的，不会出现错误情况。
1、只有是被Proposers 提出的提案才可能被最终批准。
2、在一次执行中，只批准一个最终决议。被多数接受的结果成为决议

Liveness 约束： 保证决议过程能在有限时间内完成
1、决议总会产生，并且学习者能获得被批准的决议

基本过程：多个提案者首先争取到提案的权利（得到大多数接受者的支持）；得到提案权利的提案者发送提案给所有人进行确认，得到大部分人确认的提案成为批准的结案。

Paxos 能保证在超过一半的节点正常工作时，系统总能以较大概率达成共识。

Paxos 算法可分为两个阶段,准备阶段和提交阶段。准备阶段通过锁来解决对哪个提案内容进行确认的问题，提交极端解决大多数确认最终值的问题。

准备阶段：

提案者发送自己计划提交的提案的编号到多个接收者，试探是否可以锁定多数接收者的支持。

接受者时刻保留收到过提案的最大编号和接受的最大提案。如果收到提案号比目前保留的最大提案号还大，则返回自己已接受的提案值（如果还未接受过任何提案，则为空）给提案者，更新当前最大提案号，并说明不再接受小于最大提案号的提案。

提交阶段：

提案者如果收到大多数的恢复（表示大部分人听到它的请求），则可准备发出带有刚才提案号的接受消息。如果收到的回复中不带有新的提案，说明锁定成功。则使用自己的提案内容；如果返回中有提案内容，则替换提案值为返回中编号最大的提案值。如果没收到足够多的回复，则需要再次发出请求

接受者收到“接受消息”后，如果发现提案号不小于已接受的最大提案号，则接受该提案，并更新接受的最大提案。

一旦多数接受者认同了共同的提案值，则形成决议，称为最终确认。

由Paxos算法（设计并没有考虑到一些优化机制）衍生出了一些不少性能更优化的算法和实现，Raft 算法算是对Multi-Paxos 的重新简化设计和实现。

Raft 算法面向多个决策达成一致的问题，分解了 Leader 选举、日志复制和安全方面的考虑，并通过约束减少了不确定性的状态空间。

Raft 算法包括三种角色： Leader（领导者）、Candidate（候选领导者）和 Follower （跟随者），决策前通过选举一个全局的 leader 来简化后续的决策过程。Leader 角色十分关键，决定日志 （log）的提交。日志只能由 Leader 向 Follower 单向复制。

典型的过程包括以下两个主要阶段：

Leader 选举： 开始所有节点都是 Follower ，在随机超时发生后未收到来自 Leader 或 Candidate 消息，则转变角色未 Candidate,提出选举请求。最后选举阶段中得票超过一半者被选为 Leader； 如果未选出，随机超时后进入新的阶段重试。Leader负责从客户端接受 log,并分发到其他节点。

同步日志： Leader 会找到一系统中日志最新的记录，并强制所有的 Follower 来刷新到这个记录，数据的同步是单向的。

拜占庭问题更为广泛，讨论的是允许存在少数节点作恶（消息可能被伪造）场景下的一致性达成问题。拜占庭容错算法讨论的是在拜占庭情况下对系统如何达成共识。

在拜占庭将军问题之前，就已经存在两将军问题： 两个将军要通过信使来达成进攻还是撤退的约定，但信使可能迷路或被敌军阻拦（消息丢失或伪造），如何达成一致？根据FLP 不可能原理，这个问题无通用解

拜占庭问题又叫拜占庭将军问题，是 Leslie Lamport 等科学家提出用来解释一致性问题的一个虚构模型。
Leslie Lamport 等人证明，当叛变者不超过1/3时，存在有效的拜占庭容错算法（最坏需要F+1轮交互）。繁殖，如果叛变者过多，超过1/3，则无法保证一定能达到一致结果。

拜占庭容错算法是面向拜占庭问题的容错算法，解决的是在网络通信可靠但节点可能伪造消息情况下如何达成共识。

PBFT算法： 基于前人工作进行了优化，首次将拜占庭容错算法复杂度从指数级降低到了多项式级，目前已得到广泛应用。甚至可以在失效节点不超过总数1/3的情况下同时保证 Safety 和 Liveness.

PBFT 算法：采用密码学相关技术（RSA 签名算法、 消息验证编码和摘要）确保消息传递过程无法被篡改和破坏。

PBFT算法过程：

首先通过轮换或随机算法选出某个节点为主节点，此后只要主节点不切换，则成为一个视图（View）

在某个视图中，客户端将请求发送给主节点，主几点负责广播请求到所有其他副本节点

所有节点处理完成请求，将处理结果返回给客户端。客户端检查是否收到了至少f+1个来自不同节点的相同结果，作为最终结果。

主节点广播过程包括三个阶段的处理： 预准备阶段、准备阶段和提交阶段。预准备极端和准备阶段确保在同一个视图内请求发送的顺序正确；准备和提交阶段则确保在不同视图之间的确认请求是保序的。

预准备阶段： 主节点为从客户端收到的请求分配提案编号，然后发出预准备消息<,message>给各副本节点，其中message是客户端的请求消息，digest是消息的摘要

准备阶段： 副本节点收到预准备消息后，检查消息合法，如检查通过则向其他节点发送准备消息,带上自己的id信息，同时接收来自其他节点的准备消息。收到准备消息的节点对消息同样进行合法性检查。验证通过则把这个准备消息写入消息日志中。集齐至少2f+1个验证过得消息才进入准备状态。

提交阶段： 广播commit消息，告诉其他节点某个提案n在视图v里已经处于准备状态。如果集齐至少2f+1个验证过得commit消息，则说明提案通过

拜占庭问题之所以难解，在于任何时候系统中都可能存在多个提案（因为提案成本很低），并且要完成最终一致性确认过程十分困难，容易受干扰。

比特币的区块链网络在设计时提出了创新的 Pow 概率算法思路，针对这两个环节进行了改进。

限制一段时间内整个网络中出现的提案的个数（通过增加提案成本）；

放宽对最终一致性确认的需求，约定好大家都确认并沿着已知最长的链进行拓展。系统的最终确认是概率意义上的存在。这样，即便有人视图恶意破坏，也会付出相应的经济代价（超过整体系统一半的计算力）。

后来的各种PoX系列算法，也是沿着这个思路进行改进，采用经济上的惩罚来制约破坏者。

可靠性（availability），或者说可用性，是描述系统可以提供服务能力的重要指标。高可靠的分布式系统往往需要各种复杂的机制来进行保障。
服务的可用性可以用： 服务承诺、服务指标、服务目标等方面来进行衡量。

一般地，描述系统出现故障的可能性和故障出现后的恢复能力，有两个基础的指标：

MTBF: 平均故障间隔时间，即系统可以无故障允许的预期时间

MTTR: 平均修复时间，即发生故障后，系统可以恢复到正常运行的预期时间

一个高可用的系统应该是具有尽量长的MTBF 和 尽量短的 MTTR

提高系统可靠性有两个基本思路：

让系统中的单个组件都变得更可靠

干脆消灭单点

依靠单点实现的可靠性毕竟是有限的。要想进一步提升，那就只好消灭单点，通过主从、多活等模式让多个节点集体完成原先单点的工作。这可以从概率意义上改善服务对外的整体可靠性，这也是分布式系统的一个重要用途。