干货预警：分布式系统核心问题

无聊预警：本文又长又干，又没有图

<hr>一致性问题

一致性问题是分布式领域最重要、最基础的问题。

一致性/Consistency,是说在有多个服务节点的情况下，执行一些列操作，在约定协议的保障下，使得他们对外的处理结果，能达到一定程度的协同。

规范的说，理想的分布式系统一致性应该满足：

第一点很容易理解

第二点看似容易，但是隐藏了一些潜在信息。算法考虑的是任意的情形，凡事一旦推广到任意情形，就往往有一些惊人的结果。例如现在就剩一张票了，中关村和西单的电影院也分别刚确认过这张票的存在，然后两个电影院同时来了一个顾客要买票，从各自“观察”看来，自己的顾客都是第一个到的……怎么能达成结果的共识呢？记住我们的唯一秘诀：核心在于需要把两件事情进行排序，而且这个顺序还得是大家都认可的。

第三点看似绕口，但是其实比较容易理解，即达成的结果必须是节点执行操作的结果。仍以卖票为例，如果两个影院各自卖出去一千张，那么达成的结果就是还剩八千张，决不能认为票售光了。

做过分布式系统的读者应该能意识到，绝对理想的强一致性（Strong Consistency）代价很大。除非不发生任何故障，所有节点之间的通信无需任何时间，这个时候其实就等价于一台机器了。实际上，越强的一致性要求往往意味着越弱的性能。

一般的，强一致性（Strong Consistency）主要包括下面两类：

顺序一致性：限制了各进程内指令的偏序关系，但不在进程间按照物理时间进行全局排序

线性一致性：在顺序一致性前提下加强了进程间的操作排序，形成唯一的全局顺序

强一致的系统往往比较难实现。很多时候，人们发现实际需求并没有那么强，可以适当放宽一致性要求，降低系统实现的难度。例如在一定约束下实现所谓最终一致性（Eventual Consistency），即总会存在一个时刻（而不是立刻），系统达到一致的状态，这对于大部分的 Web 系统来说已经足够了。这一类弱化的一致性，被笼统称为弱一致性（Weak Consistency）。

共识算法

实践中，要保障系统满足不同程度的一致性，往往需要通过共识算法来达成。

共识算法解决的是分布式系统对某个提案（Proposal），大部分节点达成一致意见的过程。

理论上，如果分布式系统中各个节点都能保证以十分强大的性能（瞬间响应、高吞吐）无故障的运行，则实现共识过程并不复杂，简单通过多播过程投票即可。

很可惜的是，现实中这样“完美”的系统并不存在，如响应请求往往存在时延、网络会发生中断、节点会发生故障、甚至存在恶意节点故意要破坏系统。

一般地，把故障（不响应）的情况称为“非拜占庭错误”，恶意响应的情况称为“拜占庭错误”（对应节点为拜占庭节点）。
常见算法

对于非拜占庭错误的情况，已经存在不少经典的算法，包括 Paxos（1990 年）、Raft（2014 年）及其变种等。这类容错算法往往性能比较好，处理较快，容忍不超过一半的故障节点。

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

此外，XFT（Cross Fault Tolerance，2015 年）等最近提出的改进算法可以提供类似 CFT 的处理响应速度，并能在大多数节点正常工作时提供 BFT 保障。

Algorand 算法（2017 年）基于 PBFT 进行改进，通过引入可验证随机函数解决了提案选择的问题，理论上可以在容忍拜占庭错误的前提下实现更好的性能（1000+ TPS）。

FLP不可能原理

FLP 不可能原理告诉我们，不要浪费时间，去试图为异步分布式系统设计面向任意场景的共识算法。

异步：导致我们无法判断某个消息迟迟没有被响应是哪里出了问题（节点故障还是传输故障？）

学术研究，往往考虑地是数学和物理意义上理想化的情形，很多时候现实世界要稳定得多（感谢这个世界如此鲁棒！）。例如，上面例子中描述的最坏情形，每次都发生的概率其实并没有那么大。工程实现上某次共识失败，再尝试几次，很大可能就成功了。

科学告诉你什么是不可能的；工程则告诉你，付出一些代价，可以把它变成可行。

这就是科学和工程不同的魅力。FLP 不可能原理告诉大家不必浪费时间去追求完美的共识方案，而要根据实际情况设计可行的工程方案。

那么，退一步讲，在付出一些代价的情况下，共识能做到多好？

回答这一问题的是另一个很出名的原理：CAP 原理。

CAP原理

该原理被认为是分布式系统领域的重要原理之一，深刻影响了分布式计算与系统设计的发展。

CAP 原理：分布式系统无法同时确保一致性（Consistency）、可用性（Availability）和分区容忍性（Partition），设计中往往需要弱化对某个特性的需求。

一致性、可用性和分区容忍性的具体含义如下：

CAP 原理认为，分布式系统最多只能保证三项特性中的两项特性。

比较直观地理解，当网络可能出现分区时候，系统是无法同时保证一致性和可用性的。要么，节点收到请求后因为没有得到其它节点的确认而不应答（牺牲可用性），要么节点只能应答非一致的结果（牺牲一致性）。

由于大部分时候网络被认为是可靠的，因此系统可以提供一致可靠的服务；当网络不可靠时，系统要么牺牲掉一致性（多数场景下），要么牺牲掉可用性。

注意：网络分区是可能存在的，出现分区情况后很可能会导致发生“脑裂”现象。

关键就在于网络，网络大部分情况是可靠的，但也总是不可靠的。

所以，cap可以简单理解为，因为网络总会出故障，当网络故障时，我们保一致性，还是要可用性。

要可用性：例如网站静态页面内容、实时性较弱的查询类数据库等，简单分布式同步协议如 Gossip，以及 CouchDB、Cassandra 数据库等，都为此设计。

要一致性：对结果一致性很敏感的应用，例如银行取款机，当系统故障时候会拒绝服务。MongoDB、Redis、MapReduce 等为此设计。Paxos、Raft 等共识算法，主要处理这种情况。在 Paxos 类算法中，可能存在着无法提供可用结果的情形，同时允许少数节点离线。

ACID 原则与多阶段提交

ACID，即 Atomicity（原子性）、Consistency（一致性）、Isolation（隔离性）、Durability（持久性）四种特性的缩写。

ACID 原则描述了分布式数据库需要满足的一致性需求，同时允许付出可用性的代价。

与 ACID 相对的一个原则是 eBay 技术专家 Dan Pritchett 提出的 BASE（Basic Availability，Soft-state，Eventual Consistency）原则。BASE 原则面向大型高可用分布式系统，主张牺牲掉对强一致性的追求，而实现最终一致性，来换取一定的可用性。
两阶段提交

对于分布式事务一致性的研究成果包括著名的两阶段提交算法（Two-phase Commit，2PC）和三阶段提交算法（Three-phase Commit，3PC）。

两阶段提交算法，其基本思想十分简单，既然在分布式场景下，直接提交事务可能出现各种故障和冲突，那么可将其分解为预提交和正式提交两个阶段，规避冲突的风险。

在此过程中任何步骤出现问题（例如预提交阶段有执行者回复预计无法完成提交），则需要回退。

两阶段提交算法因为其简单容易实现的优点，在关系型数据库等系统中被广泛应用。当然，其缺点也很明显。整个过程需要同步阻塞导致性能一般较差；同时存在单点问题，较坏情况下可能一直无法完成提交；另外可能产生数据不一致的情况（例如协调者和执行者在第二个阶段出现故障）。
三阶段提交

三阶段提交针对两阶段提交算法第一阶段中可能阻塞部分执行者的情况进行了优化。具体来说，将预提交阶段进一步拆成两个步骤：尝试预提交和预提交。

完整过程如下：

其实，无论两阶段还是三阶段提交，都只是一定程度上缓解了提交冲突的问题，并无法一定保证系统的一致性。首个有效的算法是后来提出的 Paxos 算法。

Paxos 算法

Paxos 问题是指分布式的系统中存在故障（crash fault），但不存在恶意（corrupt）节点的场景（即可能消息丢失或重复，但无错误消息）下的共识达成问题。这也是分布式共识领域最为常见的问题。

Paxos 是首个得到证明并被广泛应用的共识算法，其原理类似两阶段提交算法，进行了泛化和扩展，通过消息传递来逐步消除系统中的不确定状态。zookeeper中有使用。

作为后来很多共识算法（如 Raft、ZAB 等）的基础，Paxos 算法基本思想并不复杂。
基本原理

算法中存在三种逻辑角色的节点，在实现中同一节点可以担任多个角色。

基本思路类似两阶段提交：

多个提案者先要争取到提案的权利（得到大多数接受者的支持）；

成功的提案者发送提案给所有人进行确认，得到大部分人确认的提案成为批准的结案。
Raft 算法

Paxos 算法虽然给出了共识设计，但并没有讨论太多实现细节，也并不重视工程上的优化，因此后来在学术界和工程界出现了一些改进工作，包括 Fast Paxos、Multi-Paxos，Zookeeper Atomic Broadcast（ZAB）和 Raft 等。这些算法重点在于改进执行效率和可实现性。

Raft 算法的主要设计思想与 ZAB 类似，通过先选出领导节点来简化流程和提高效率。实现上分解了领导者选举、日志复制和安全方面的考虑，并通过约束减少了不确定性的状态空间。

算法包括三种角色：领导者（Leader）、候选者（Candidate）和跟随者（Follower），每个任期内选举一个全局的领导者。领导者角色十分关键，决定日志（log）的提交。每个日志都会路由到领导者，并且只能由领导者向跟随者单向复制。

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

此外，领导者会定期向所有跟随者发送心跳消息，跟随者如果发现心跳消息超时未收到，则可以认为领导者已经下线，尝试发起新的选举过程。
拜占庭问题

拜占庭是古代东罗马帝国的首都，由于地域宽广，假设其守卫边境的多个将军（系统中的多个节点）需要通过信使来传递消息，达成某些一致决定。但由于将军中可能存在叛徒（系统中节点出错），这些叛徒将向不同的将军发送不同的消息，试图干扰共识的达成。

拜占庭问题即讨论在此情况下，如何让忠诚的将军们能达成行动的一致。

在大多数的分布式系统中，拜占庭的场景并不多见。然而在特定场景下存在意义，例如允许匿名参与的系统（如比特币），或是出现欺诈可能造成巨大损失的情况。

根据 FLP 不可能原理，这个问题无通用解。

拜占庭问题之所以难解，在于任何时候系统中都可能存在多个提案（因为提案成本很低），并且在大规模场景下要完成最终确认的过程容易受干扰，难以达成共识。

比特币网络在设计时使用了 PoW（Proof of Work）的概率型算法思路，从如下两个角度解决大规模场景下的拜占庭容错问题。

首先，限制一段时间内整个网络中出现提案的个数（通过工作量证明来增加提案成本）；其次是丢掉最终确认的约数，约定好始终沿着已知最长的链进行拓展。共识的最终确认是概率意义上的存在。这样，即便有人试图恶意破坏，也会付出相应的经济代价（超过整体系统一半的工作量）。

后来的各种 PoX 系列算法，也都是沿着这个思路进行改进，采用经济博弈来制约攻击者。

干货预警：分布式系统核心问题

浏览过的版块