万法皆空，因果不空。
随着摩尔定律碰到瓶颈，越来越多的系统要依靠分布式集群架构来实现海量数据处理和可扩展计算能力。
区块链首先是一个分布式系统。
中央式结构改成分布式系统，碰到的第一个问题就是一致性的保障。
很显然，如果一个分布式集群无法保证处理结果一致的话，那任何建立于其上的业务系统都无法正常工作。
本章将介绍分布式系统中一些核心问题的来源以及相关的工作。
一致性问题
在分布式系统中，一致性(Consistency，早期也叫 Agreement)是指对于系统中的多个服务节点，给定一系列操作，在协议（往往通过某种共识算法）保障下，试图使得它们对处理结果达成某种程度的一致。
如果分布式系统能实现“一致”，对外就可以呈现为一个功能正常的，且性能和稳定性都要好很多的“虚处理节点”。
举个例子，某影视公司旗下有西单和中关村的两个电影院，都出售某电影票，票一共就一万张。那么，顾客到达某个电影院买票的时候，售票员该怎么决策是否该卖这张票，才能避免超售呢？当电影院个数更多的时候呢？
这个问题在人类世界中，看起来似乎没那么难，你看，英国人不是刚靠 投票 达成了“某种一致”吗？
注意：一致性并不代表结果正确与否，而是系统对外呈现的状态一致与否，例如，所有节点都达成失败状态也是一种一致。
挑战
在实际的计算机集群系统（看似强大的计算机系统，很多地方都比人类世界要脆弱的多）中，存在如下的问题：
- 节点之间的网络通讯是不可靠的，包括任意延迟和内容故障；
- 节点的处理可能是错误的，甚至节点自身随时可能宕机；
- 同步调用会让系统变得不具备可扩展性。
要解决这些挑战，愿意动脑筋的读者可能会很快想出一些不错的思路。
为了简化理解，仍然以两个电影院一起卖票的例子。可能有如下的解决思路：
- 每次要卖一张票前打电话给另外一家电影院，确认下当前票数并没超售；
- 两家电影院提前约好，奇数小时内一家可以卖票，偶数小时内另外一家可以卖；
- 成立一个第三方的存票机构，票都放到他那里，每次卖票找他询问；
- 更多……
这些思路大致都是可行的。实际上，这些方法背后的思想，将可能引发不一致的并行操作进行串行化，就是现在计算机系统里处理分布式一致性问题的基础思路和唯一秘诀。只是因为计算机系统比较傻，需要考虑得更全面一些；而人们又希望计算机系统能工作的更快更稳定，所以算法需要设计得再精巧一些。
要求
规范的说，理想的分布式系统一致性应该满足：
- 可终止性（Termination）：一致的结果在有限时间内能完成；
- 共识性（Consensus）：不同节点最终完成决策的结果应该相同；
- 合法性（Validity）：决策的结果必须是其它进程提出的提案。
第一点很容易理解，这是计算机系统可以被使用的前提。需要注意，在现实生活中这点并不是总能得到保障的，例如取款机有时候会是“服务中断”状态，电话有时候是“无法连通”的。
第二点看似容易，但是隐藏了一些潜在信息。算法考虑的是任意的情形，凡事一旦推广到任意情形，就往往有一些惊人的结果。例如现在就剩一张票了，中关村和西单的电影院也分别刚确认过这张票的存在，然后两个电影院同时来了一个顾客要买票，从各自“观察”看来，自己的顾客都是第一个到的……怎么能达成结果的共识呢？记住我们的唯一秘诀：核心在于需要把两件事情进行排序，而且这个顺序还得是大家都认可的。
第三点看似绕口，但是其实比较容易理解，即达成的结果必须是节点执行操作的结果。仍以卖票为例，如果两个影院各自卖出去一千张，那么达成的结果就是还剩八千张，决不能认为票售光了。
带约束的一致性
做过分布式系统的读者应该能意识到，绝对理想的强一致性（Strong Consistency）代价很大。除非不发生任何故障，所有节点之间的通信无需任何时间，这个时候其实就等价于一台机器了。实际上，越强的一致性要求往往意味着越弱的性能。
一般的，强一致性（Strong Consistency）主要包括下面两类：
顺序一致性（Sequential Consistency）：Leslie Lamport 1979 年经典论文《How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs》中提出，是一种比较强的约束，保证所有进程看到的 全局执行顺序（total order）一致，并且每个进程看自身的执行（local order）跟实际发生顺序一致。例如，某进程先执行 A，后执行 B，则实际得到的全局结果中就应该为 A 在 B 前面，而不能反过来。同时所有其它进程在全局上也应该看到这个顺序。顺序一致性实际上限制了各进程内指令的偏序关系，但不在进程间按照物理时间进行全局排序。
线性一致性（Linearizability Consistency）：Maurice P. Herlihy 与 Jeannette M. Wing 在 1990 年经典论文《Linearizability: A Correctness Condition for Concurrent Objects》中共同提出，在顺序一致性前提下加强了进程间的操作排序，形成唯一的全局顺序（系统等价于是顺序执行，所有进程看到的所有操作的序列顺序都一致，并且跟实际发生顺序一致），是很强的原子性保证。但是比较难实现，目前基本上要么依赖于全局的时钟或锁，要么通过一些复杂算法实现，性能往往不高。
目前，高精度的石英钟的漂移率为 
强一致的系统往往比较难实现。很多时候，人们发现实际需求并没有那么强，可以适当放宽一致性要求，降低系统实现的难度。例如在一定约束下实现所谓最终一致性（Eventual Consistency），即总会存在一个时刻（而不是立刻），系统达到一致的状态，这对于大部分的 Web 系统来说已经足够了。这一类弱化的一致性，被笼统称为弱一致性（Weak Consistency）。
莫非分布式领域也有一个测不准原理？这个世界为何会有这么多的约束呢？
共识算法
实际上，要保障系统满足不同程度的一致性，往往需要通过共识算法来达成。
共识算法解决的是对某个提案（Proposal），大家达成一致意见的过程。提案的含义在分布式系统中十分宽泛，如多个事件发生的顺序、某个键对应的值、谁是领导……等等，可以认为任何需要达成一致的信息都是一个提案。
注：实践中，一致性的结果往往还需要客户端的特殊支持，典型地通过访问足够多个服务节点来验证确保获取共识后结果。
问题挑战
实际上，如果分布式系统中各个节点都能保证以十分强大的性能（瞬间响应、高吞吐）无故障的运行，则实现共识过程并不复杂，简单通过多播过程投票即可。
很可惜的是，现实中这样“完美”的系统并不存在，如响应请求往往存在时延、网络会发生中断、节点会发生故障、甚至存在恶意节点故意要破坏系统。
一般地，把故障（不响应）的情况称为“非拜占庭错误”，恶意响应的情况称为“拜占庭错误”（对应节点为拜占庭节点）。
常见算法
针对非拜占庭错误的情况，一般包括 Paxos、Raft 及其变种。
对于要能容忍拜占庭错误的情况，一般包括 PBFT 系列、PoW 系列算法等。从概率角度，PBFT 系列算法是确定的，一旦达成共识就不可逆转；而 PoW 系列算法则是不确定的，随着时间推移，被推翻的概率越来越小。
理论界限
搞学术的人都喜欢对问题先确定一个界限，那么，这个问题的最坏界限在哪里呢？很不幸，一般情况下，分布式系统的共识问题无解。
当节点之间的通信网络自身不可靠情况下，很显然，无法确保实现共识。但好在，一个设计得当的网络可以在大概率上实现可靠的通信。
然而，即便在网络通信可靠情况下，一个可扩展的分布式系统的共识问题的下限是无解。
这个结论，被称为 FLP 不可能性 原理，可以看做分布式领域的“测不准原理”。
FLP 不可能性原理
FLP 不可能原理：在网络可靠，存在节点失效（即便只有一个）的最小化异步模型系统中，不存在一个可以解决一致性问题的确定性算法。
提出该定理的论文是由 Fischer, Lynch 和 Patterson 三位作者于 1985 年发表，该论文后来获得了 Dijkstra（就是发明最短路径算法的那位）奖。
FLP 不可能原理实际上告诉人们，不要浪费时间去为异步分布式系统设计在任意场景下都能实现共识的算法。
理解这一原理的一个不严谨的例子是：
三个人在不同房间，进行投票（投票结果是 0 或者 1）。三个人彼此可以通过电话进行沟通，但经常会有人时不时地睡着。比如某个时候，A 投票 0，B 投票 1，C 收到了两人的投票，然后 C 睡着了。A 和 B 则永远无法在有限时间内获知最终的结果。如果可以重新投票，则类似情形每次在取得结果前发生：（
FLP 原理实际上说明对于允许节点失效情况下，纯粹异步系统无法确保一致性在有限时间内完成。
这岂不是意味着研究一致性问题压根没有意义吗？
先别这么悲观，学术界做研究，考虑的是数学和物理意义上最极端的情形，很多时候现实生活要美好的多（感谢这个世界如此鲁棒！）。例如，上面例子中描述的最坏情形，总会发生的概率并没有那么大。工程实现上多试几次，很大可能就成功了。
科学告诉你什么是不可能的；工程则告诉你，付出一些代价，我可以把它变成可能。
这就是工程的魅力。
那么，退一步讲，在付出一些代价的情况下，我们能做到多少？
回答这一问题的是另一个很出名的原理：CAP 原理。
科学上告诉你去赌场赌博从概率上总会是输钱的；工程则告诉你，如果你愿意接受最终输钱的结果，中间说不定偶尔能小赢几笔呢！？
CAP 原理
CAP 原理最早由 Eric Brewer 在 2000 年，ACM 组织的一个研讨会上提出猜想，后来 Lynch 等人进行了证明。
该原理被认为是分布式系统领域的重要原理。
定义
分布式计算系统不可能同时确保一致性（Consistency）、可用性（Availablity）和分区容忍性（Partition），设计中往往需要弱化对某个特性的保证。
一致性（Consistency）：任何操作应该都是原子的，发生在后面的事件能看到前面事件发生导致的结果，注意这里指的是强一致性；
可用性（Availablity）：在有限时间内，任何非失败节点都能应答请求；
分区容忍性（Partition）：网络可能发生分区，即节点之间的通信不可保障。
比较直观地理解，当网络可能出现分区时候，系统是无法同时保证一致性和可用性的。要么，节点收到请求后因为没有得到其他人的确认就不应答，要么节点只能应答非一致的结果。
好在大部分时候网络被认为是可靠的，因此系统可以提供一致可靠的服务；当网络不可靠时，系统要么牺牲掉一致性（大部分时候都是如此），要么牺牲掉可用性。
应用场景
既然 CAP 不可同时满足，则设计系统时候必然要弱化对某个特性的支持。 弱化一致性
对结果一致性不敏感的应用，可以允许在新版本上线后过一段时间才更新成功，期间不保证一致性。
例如网站静态页面内容、实时性较弱的查询类数据库等，CouchDB、Cassandra 等为此设计。 弱化可用性
对结果一致性很敏感的应用，例如银行取款机，当系统故障时候会拒绝服务。MongoDB、Redis 等为此设计。
Paxos、Raft 等算法，主要处理这种情况。 弱化分区容忍性
现实中，网络分区出现概率减小，但较难避免。某些关系型数据库、ZooKeeper 即为此设计。
实践中，网络通过双通道等机制增强可靠性，达到高稳定的网络通信。
ACID 原则
即 Atomicity（原子性）、Consistency（一致性）、Isolation（隔离性）、Durability（持久性）。
ACID 原则描述了对分布式数据库的一致性需求，同时付出了可用性的代价。
Atomicity：每次操作是原子的，要么成功，要么不执行；
Consistency：数据库的状态是一致的，无中间状态；
Isolation：各种操作彼此互相不影响；
Durability：状态的改变是持久的，不会失效。
一个与之相对的原则是 BASE（Basic Availiability，Soft state，Eventually Consistency），牺牲掉对一致性的约束（最终一致性），来换取一定的可用性。
Paxos 与 Raft
Paxos 问题是指分布式的系统中存在故障（fault），但不存在恶意（corrupt）节点场景（即可能消息丢失或重复，但无错误消息）下的共识达成（Consensus）问题。因为最早是 Leslie Lamport 用 Paxon 岛的故事模型来进行描述而命名。
Paxos
1990 年由 Leslie Lamport 提出的 Paxos 共识算法，在工程角度实现了一种最大化保障分布式系统一致性（存在极小的概率无法实现一致）的机制。Paxos 被广泛应用在 Chubby、ZooKeeper 这样的系统中，Leslie Lamport 因此获得了 2013 年度图灵奖。
故事背景是古希腊 Paxon 岛上的多个法官在一个大厅内对一个议案进行表决，如何达成统一的结果。他们之间通过服务人员来传递纸条，但法官可能离开或进入大厅，服务人员可能偷懒去睡觉。
Paxos 是第一个被证明的共识算法，其原理基于 两阶段提交（[size=12]https://en.wikipedia.org/wiki/ … tocol） 并进行扩展。[/size]
作为现在共识算法设计的鼻祖，以最初论文的难懂（算法本身并不复杂）出名。算法中将节点分为三种类型：
proposer：提出一个提案，等待大家批准为结案。往往是客户端担任该角色；
acceptor：负责对提案进行投票。往往是服务端担任该角色；
learner：被告知结案结果，并与之统一，不参与投票过程。可能为客户端或服务端。
并且，算法需要满足 safety 和 liveness 两方面的约束要求（实际上这两个基础属性是大部分分布式算法都该考虑的）：
safety：保证决议结果是对的，无歧义的，不会出现错误情况。
决议（value）只有在被 proposers 提出的 proposal 才能被最终批准；
在一次执行实例中，只批准（chosen）一个最终决议，意味着多数接受（accept）的结果能成为决议
liveness：保证决议过程能在有限时间内完成。
决议总会产生，并且 learners 能获得被批准（chosen）的决议。
基本过程包括 proposer 提出提案，先争取大多数 acceptor 的支持，超过一半支持时，则发送结案结果给所有人进行确认。一个潜在的问题是 proposer 在此过程中出现故障，可以通过超时机制来解决。极为凑巧的情况下，每次新的一轮提案的 proposer 都恰好故障，系统则永远无法达成一致（概率很小）。
Paxos 能保证在超过 
读者可以试着自己设计一套能达成共识的方案，会发现在满足各种约束情况下，算法自然就会那样设计。
单个提案者+多接收者
如果系统中限定只有某个特定节点是提案者，那么一致性肯定能达成（只有一个方案，要么达成，要么失败）。提案者只要收到了来自多数接收者的投票，即可认为通过，因为系统中不存在其他的提案。
但一旦提案者故障，则系统无法工作。
多个提案者+单个接收者
限定某个节点作为接收者。这种情况下，共识也很容易达成，接收者收到多个提案，选第一个提案作为决议，拒绝掉后续的提案即可。
缺陷也是容易发生单点故障，包括接收者故障或首个提案者节点故障。
以上两种情形其实类似主从模式，虽然不那么可靠，但因为原理简单而被广泛采用。
当提案者和接收者都推广到多个的情形，会出现一些挑战。
多个提案者+多个接收者
既然限定单提案者或单接收者都会出现故障，那么就得允许出现多个提案者和多个接收者。问题一下子变得复杂了。
一种情况是同一时间片段（如一个提案周期）内只有一个提案者，这时可以退化到单提案者的情形。需要设计一种机制来保障提案者的正确产生，例如按照时间、序列、或者大家猜拳（出一个数字来比较）之类。考虑到分布式系统要处理的工作量很大，这个过程要尽量高效，满足这一条件的机制非常难设计。
另一种情况是允许同一时间片段内可以出现多个提案者。那同一个节点可能收到多份提案，怎么对他们进行区分呢？这个时候采用只接受第一个提案而拒绝后续提案的方法也不适用。很自然的，提案需要带上不同的序号。节点需要根据提案序号来判断接受哪个。比如接受其中序号较大（往往意味着是接受新提出的，因为旧提案者故障概率更大）的提案。
如何为提案分配序号呢？一种可能方案是每个节点的提案数字区间彼此隔离开，互相不冲突。为了满足递增的需求可以配合用时间戳作为前缀字段。
此外，提案者即便收到了多数接收者的投票，也不敢说就一定通过。因为在此过程中系统可能还有其它的提案。
两阶段的提交
提案者发出提案之后，收到一些反馈。一种结果是自己的提案被大多数接受了，另一种结果是没被接受。没被接受的话好说，过会再试试。
即便收到来自大多数的接受反馈，也不能认为就最终确认了。因为这些接收者自己并不知道自己刚反馈的提案就恰好是全局的绝大多数。
很自然的，引入了新的一个阶段，即提案者在前一阶段拿到所有的反馈后，判断这个提案是可能被大多数接受的提案，需要对其进行最终确认。
Paxos 里面对这两个阶段分别命名为准备（prepare）和提交（commit）。准备阶段解决大家对哪个提案进行投票的问题，提交阶段解决确认最终值的问题。
准备阶段：
提案者发送自己计划提交的提案的编号到多个接受者，试探是否可以锁定多数接受者的支持。
接受者时刻保留收到过提案的最大编号和接受的最大提案。如果收到的提案号比目前保留的最大提案号还大，则返回自己已接受的提案值（如果还未接受过任何提案，则为空）给提案者，更新当前最大提案号，并说明不再接受小于最大提案号的提案。
提交阶段：
提案者如果收到大多数的回复（表示大部分人听到它的请求），则可准备发出带有刚才提案号的接受消息。如果收到的回复中不带有新的提案，说明锁定成功，则使用自己的提案内容；如果返回中有提案内容，则替换提案值为返回中编号最大的提案值。如果没收到足够多的回复，则需要再次发出请求。
接受者收到接受消息后，如果发现提案号不小于已接受的最大提案号，则接受该提案，并更新接受的最大提案。
一旦多数接受了共同的提案值，则形成决议，成为最终确认的提案。
Raft
Raft 算法是Paxos 算法的一种简化实现。
包括三种角色：leader、candidate 和 follower，其基本过程为：
Leader 选举：每个 candidate 随机经过一定时间都会提出选举方案，最近阶段中得票最多者被选为 leader；
同步 log：leader 会找到系统中 log 最新的记录，并强制所有的 follower 来刷新到这个记录；
注：此处 log 并非是指日志消息，而是各种事件的发生记录。
拜占庭问题与算法
拜占庭问题更为广泛，讨论的是允许存在少数节点作恶（消息可能被伪造）场景下的一致性达成问题。拜占庭算法讨论的是最坏情况下的保障。
中国将军问题
拜占庭将军问题之前，就已经存在中国将军问题：两个将军要通过信使来达成进攻还是撤退的约定，但信使可能迷路或被敌军阻拦（消息丢失或伪造），如何达成一致。根据 FLP 不可能原理，这个问题无解。
拜占庭问题
又叫拜占庭将军（Byzantine Generals Problem）问题，是 Leslie Lamport 1982 年提出用来解释一致性问题的一个虚构模型。拜占庭是古代东罗马帝国的首都，由于地域宽广，守卫边境的多个将军（系统中的多个节点）需要通过信使来传递消息，达成某些一致的决定。但由于将军中可能存在叛徒（系统中节点出错），这些叛徒将努力向不同的将军发送不同的消息，试图会干扰一致性的达成。
拜占庭问题即为在此情况下，如何让忠诚的将军们能达成行动的一致。
对于拜占庭问题来说，假如节点总数为 N，叛变将军数为 F，则当 
例如，
提案人不是叛变者，提案人发送一个提案出来，叛变者可以宣称收到的是相反的命令。则对于第三个人（忠诚者）收到两个相反的消息，无法判断谁是叛变者，则系统无法达到一致。
提案人是叛变者，发送两个相反的提案分别给另外两人，另外两人都收到两个相反的消息，无法判断究竟谁是叛变者，则系统无法达到一致。
更一般的，当提案人不是叛变者，提案人提出提案信息 
当提案人是叛变者，会尽量发送相反的提案给 
另外存在 
Leslie Lamport 证明，当叛变者不超过 
多于 
能确保达成一致的拜占庭系统节点数至少为 4，允许出现 1 个坏的节点。
Byzantine Fault Tolerant 算法
面向拜占庭问题的容错算法，解决的是网络通信可靠，但节点可能故障情况下的一致性达成。
最早由 Castro 和 Liskov 在 1999 年提出的 Practical Byzantine Fault Tolerant（PBFT）是第一个得到广泛应用的 BFT 算法。只要系统中有 
PBFT 算法包括三个阶段来达成共识：Pre-Prepare、Prepare 和 Commit。
新的解决思路
拜占庭问题之所以难解，在于任何时候系统中都可能存在多个提案（因为提案成本很低），并且要完成最终的一致性确认过程十分困难，容易受干扰。但是一旦确认，即为最终确认。
比特币的区块链网络在设计时提出了创新的 PoW（Proof of Work） 算法思路。一个是限制一段时间内整个网络中出现提案的个数（增加提案成本），另外一个是放宽对最终一致性确认的需求，约定好大家都确认并沿着已知最长的链进行拓宽。系统的最终确认是概率意义上的存在。这样，即便有人试图恶意破坏，也会付出很大的经济代价（付出超过系统一半的算力）。
后来的各种 PoX 系列算法，也都是沿着这个思路进行改进，采用经济上的惩罚来制约破坏者。
可靠性指标
很多领域一般都喜欢谈服务可靠性，用几个 9 来说事。这几个 9 其实是粗略代表了概率意义上系统能提供服务的可靠性指标，最初是电信领域提出的概念。
下表给出不同指标下，每年允许服务出现不可用时间的参考值。
指标概率可靠性每年允许不可用时间典型场景一个九90%1.2 个月不可用二个九99%3.6 天普通单点三个九99.9%8.6 小时普通企业四个九99.99%51.6 分钟高可用五个九99.999%5 分钟电信级六个九99.9999%31 秒极高要求七个九99.99999%3 秒N/A八个九99.999999%0.3 秒N/A九个九99.9999999%30 毫秒N/A
一般来说，单点的服务器系统至少应能满足两个九；普通企业信息系统三个九就肯定足够了（大家可以统计下自己企业内因系统维护每年要停多少时间），系统能达到四个九已经是业界领先水平了（参考 AWS）。电信级的应用一般号称能达到五个九，这已经很厉害了，一年里面最多允许五分钟的服务停用。六个九和以上的系统，就更加少见了，要实现往往意味着极高的代价。
那么，该如何提升可靠性呢？有两个思路：一是让系统中的单点变得更可靠；二是消灭单点。
IT 从业人员大都有类似的经验，运行某软系统的机器，基本上是过几天就要重启下的；而运行 Linux 系统的服务器，则可能几年时间都不出问题。另外，普通的家用计算机，跟专用服务器相比，长时间运行更容易出现故障。这些都是单点可靠性不同的例子。可以通过替换单点的软硬件来改善可靠性。
然而，依靠单点实现的可靠性毕竟是有限的，要想进一步的提升，那就只好消灭单点，通过主从、多活等模式让多个节点集体完成原先单点的工作。这可以从概率意义上改善服务的可靠性，也是分布式系统的一个重要用途。
小结
分布式系统领域是计算机科学中十分重要的一个技术领域。
常见的分布式一致性是个古老而重要的问题，无论在学术上还是工程上都存在很高的价值。理想化（各项指标均最优）的解决方案是不存在的。
在现实各种约束条件下，往往需要通过牺牲掉某些需求，来设计出满足特定场景的协议。
其实，工程领域中很多问题的解决思路，都在于如何合理地进行取舍（trade-off）。
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/257193.html