大咖说 | 胡志琳：分布式系统概述

本期参与交流的技术大咖是：胡志琳

胡志琳，资深系统研发，清华大学直博，曾系统设计并实现某重点军工项目的关键设备，曾就职于滴滴出行等知名互联网公司。

热衷于区块链系统的理论研究和工程实现，熟练掌握Bitcoin、Ethereum和EOS等区块链技术。

主要负责分布式系统共识算法的分析、设计与研发，以及密码学和零知识证明等在实际业务中应用落地。

了解分布式系统，读这一遍文章就足够了。

1、分布式系统概述

分布式系统是由一组通过网络进行通信、为了完成共同任务而协调工作的大量计算机节点组成的系统。单个节点的故障（进程crash、断电、磁盘损坏）是个小概率事件，但整个系统的故障率会随节点的增加而指数级增加，网络通信也可能出现断网、高延迟的情况。在这种一定会出现的“异常”情况下，分布式系统还是需要继续稳定的对外提供服务，即需要较强的容错性。

分布式系统需要大量机器协作，面临诸多的挑战：

第一，异构的机器与网络：分布式系统中的机器，配置不一样，其上运行的服务也可能由不同的语言、架构实现，因此处理能力也不一样；节点间通过网络连接，而不同网络运营商提供的网络的带宽、延时、丢包率又不一样。

第二，普遍的节点故障：虽然单个节点的故障概率较低，但节点数目达到一定规模，出故障的概率就变高了。分布式系统需要保证故障发生的时候，系统仍然是可用的，这就需要监控节点的状态，在节点故障的情况下将该节点负责的计算、存储任务转移到其他节点。

第三，不可靠的网络：节点间通过网络通信，而网络是不可靠的。可能的网络问题包括：网络分割、延时、丢包、乱序。

总而言之，分布式的挑战来自不确定性，不确定计算机什么时候crash、断电，不确定磁盘什么时候损坏，不确定每次网络通信要延迟多久，也不确定通信对端是否处理了发送的消息。而分布式的规模放大了这个不确定性，所以有诸多的分布式理论、协议来保证在这种不确定性的情况下，系统还能继续正常工作。

2、分布式系统理论

基本可行性原理FLP、CAP

基本共识算法Paxos、BFT、Zyzzyva、Quorum

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

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

共识的基本定义：

系统n个节点，其中最多有f个崩溃，最少有n-f个节点是好的。节点i从vi开始，所有节点必须从全部输入值中选择一个值作为决策值，并且满足下面的条件：

1、一致性，所有好节点的决策值必须相同；

2、有效性，选择出的决策值必须是某个节点的输入值；

3、可终止性，所有好节点在有限时间内结束决策过程；

共识的不可能性：

分布式系统理理论——FLP

对于异步系统，节点崩溃错误是非常致命的，哪怕只有一个节点崩溃也不可能达成共识。即异步系统下不存在确定性的容错共识算法，即使对于布尔型输入值也如此。

相关引理和定理

1、如果f>=1，至少存在一组输入值V，使得相应的初始配置C0是二价的。

2、如果一个系统是在一个二价的配置中，这个系统必须在有限的时间内达到一个关键配置，否则这个系统就永远不不能达成共识。

3、如果一个配置树包含一个关键配置，单个节点的崩溃必然会导致一个二价叶子节点，也就是说单个节点崩溃阻碍了了算法达成一致。

相关定理

当f>0时，不存在一个确定的算法总能在异步模型下达成共识。

分布式系统理理论——CAP

CAP 原理最早由 Eric Brewer 在 2000 年，ACM 组织的一个研讨会上提出猜想，后来 2002年年Lynch 等人进行了证明。分布式计算系统不可能同时确保一致性（Consistency）、可用性（Availability）和分区容忍性（Partition），设计中往往需要弱化对某个特性的保证。

一致性（Consistency）：任何操作应该都是原子的，发生在后面的事件能看到前面事件发生导致的结果，注意这里指的是强一致性；

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

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

分布式系统算法——Paxos

相关引理

1、客户端发送一个提案(t,c)，如果提案被存储在过半数服务器上，则称此提案被选中；如果已经存在一个提案被选中，则后续每一个提案(t',c')=(t,c)将始终成立；

2、如果一个命令c被某些服务器器执行，那么所有的服务器最终将执行命令c；

相关历史

1988-1996，萌芽期，开端的两片论文被提出；

1996-2007，花团簇锦发展，提升Paxos性能，符合不同应用的需要；

2006-， 硕果累累，配置管理、数据库备份，例如：Chubby\ZppKeeper等；

分布式系统算法——BFT

一个可能呈现任意行为的节点称为拜占庭，任意行为意味着“所有能想象到的事情”。

在一个存在拜占庭节点的系统中达成共识，称为拜占庭协定。如果一个算法可以在存在f个拜占庭节点的情况下正确工作，则称该算法为f-可适用。

拜占庭有效性

1、任何输入有效性；2、正确输入有效性；3、全部相同有效性；4、中值有效性；

拜占庭相关定理

若一个有n个节点的网络中存在f>=n/3个拜占庭节点，则该网络不能达成拜占庭协定。

拜占庭相关历史

1980，EIG算法复杂度和节点数量呈指数关系；其他的拜占庭算法，国王算法、皇后算法，这些算法要么复杂度高，要么容忍错误少。

PBFT是Practical Byzantine Fault Tolerance的缩写，意为实用拜占庭容错算法。该算法是Miguel Castro (卡斯特罗)和Barbara Liskov（利斯科夫）在1999年提出来的，解决了原始拜占庭容错算法效率不高的问题，将算法复杂度由指数级降低到多项式级，使得拜占庭容错算法在实际系统应用中变得可行。

其他的共识算法：

Zyzzyva，设计思想是在好的节点上快速运行，在遇到错误的时候慢下来修复。

Quorum，引入网格仲裁系统、B-网格、f-掩盖网格仲裁和不透明仲裁系统。

多算法性能比较：

1、POW，比特币的交易输出现状是7笔每秒，能支持上万个节点。

2，PBFT的交易输出是1000笔每秒量级的，但是不可扩展，超过64个节点基本认为不可用。

3，改进的BFT算法Zyzzyva的输出是10k笔每秒量级的，这个算法是可扩展的。与PBFT相比，它对恶意节点数量更敏感，恶意节点多的时候延迟会比PBFT高。

比特币的安全假设是恶意节点的算力少于全网一半，PBFT和Zyzzyva是恶意节点数量少于1/3，而实际上在恶意节点增加的情况下，Zyzzyva的延迟会很高。

参考文献：

1、什么是分布式系统，如何学习分布式系统 https://www.cnblogs.com/xybaby/p/7787034.html

2、《区块链核心算法解析》 Roger Wattenhofer