ITDSD- 3. 分布式软件工程概述

引言

这是分布式系统设计入门 (ITDSD) 系列的第三篇文章。本文简要介绍了分布式工程在理论上的基本概念、发展历史和现状，以及未来的发展方向。让我们了解一下为什么我们要学习分布式工程，分布式工程在计算机科学中的地位以及分布式工程需要解决的问题。您可以点击下面的链接找到前三篇文章。

• Web服务的分布式方法
• 分布式系统设计入门 - 1. 微服务架构中的拆分
• 分布式系统设计入门 - 2. 微服务架构拆分实践

历史

分布式工程是一门实践工程科学。因此，与其他工程项目一样，也会出现实践先于理论的现象。ARPANET[1]，被认为是第一个分布式系统，诞生于 20 世纪 60 年代末的美国。从 20 世纪 50 年代到 60 年代，受曼哈顿计划的影响，计算机理论迎来了“大爆炸”时代。在那个时代，我们今天使用的大部分计算机理论都被发明了出来。作为一个新学科，当年的绝大多数科学家都是刚毕业，正值壮年。如今，他们大多已年迈，有的科学家已经去世。在此，我们向所有为计算机理论做出贡献的科学家致敬。

Carl Hewitt 于 1973 年发明了 Actor 模型 [2]。该模型试图在计算机网络中建立与现实对应的虚拟对象，并建立它们之间的关系。计算机网络中的虚拟对象负责处理由现实场景产生的请求。Actor 模型对后来的面向对象语言和面向对象数据库产生了深远的影响。它是按照产品功能划分计算机软件模块的重要理论基础。

1979 年，Lamport 提出了顺序一致性理论 [3]。一致性理论最初应用于系统设计。它主要在硬件和计算机系统中发挥作用。在此期间，科学家们试图找到一种方法来在多个硬件中维护数据一致性，因此各种一致性理论应运而生。

分布式计算原理研讨会 (PODC) 于 1982 年正式成立 [4]。这标志着分布式技术已经成为一个独立的研究方向。

1985 年，Fischer、Lynch 和 Paterson 三位科学家发表了 FLP 定理 [5]。该定理证明了在异步通信中不可能达成绝对共识。但随后在 1988 年，Lynch、Dwork 和 Stockmeyer 发表了一篇题为“部分同步下的共识”的文章 [6]。这使得人们对分布式系统的可靠性和稳定性感到困惑。如果分布式系统是一个不稳定的系统，那么构建在它之上的软件系统也是一个不稳定的系统。寻找一个稳定分布式系统的算法成为一个新问题。考虑到当时硬件爆炸式发展的背景。硬件系统的不稳定性确实让科学家们心神不宁。

1985 年，Mohan 和 Bruce Lindsay 发明了两阶段提交协议 [7]。这是已知最早的用于在分布式系统中通过投票来维护一致性的协议。

1986 年，分布式工程领域的一项重要工业实践被启动，即 Erlang 语言的诞生 [8]。显然，爱立信等不了科学家们关于分布式系统是否稳定的争论。全球大量的电话交换机急需一个大型分布式系统进行处理。它由 Joe Armstrong、Robert Virding 和 Mike Williams 开发。Joe Armstrong 已于去年（2019 年 4 月 20 日）去世，在此致以敬意。

1989 年，Lamport 提出了颇具争议的 Paxos 协议 [9]。该协议以希腊 Paxos 岛上虚构的立法系统命名。由于该论文更像一个故事，因此被拒稿。直到 1998 年，该论文才被正式发表。

一致性哈希 [10] 一词最早出现在 Karger 于 1997 年发表的论文中。尽管 Teradata 在 1986 年开发的分布式数据中已经使用了这项技术。

1998 年，Eric Brewer 提出了 CAP 定理，描述了一致性、可用性和分区之间的关系 [11]。但在他的文章 [12] 中，他试图将其描述为一种软件设计标准。而且似乎没有一种操作方法可以实现这一原则。

2001 年，由 Freenet、gnutella、BitTorrent 和 Napster 等 P2P 软件驱动的 DHT 技术得到了广泛应用 [13]。它最初来源于 Ian Clarke 的一篇未在任何期刊上发表的论文 [14]。DHT 技术在 P2P 和分布式内存数据库中起着重要作用。

2005 年，Lambert 发明了改进的 Paxos 算法 Fast Paxos。这是 Paxos 算法首次被用作应用代码的一个版本。

2013 年，在参考 Paxos 算法的基础上发明了 RAFT 算法 [15]。在 2011 年之前，已经发布了一个与 RAFT 算法相似的 ZAB 算法。ZAB 算法用于 ZooKeeper。ZooKeeper 是分布式系统中用于提供系统配置信息的节点。由于 ZooKeeper 在分布式系统中得到广泛应用，因此 RAFT 算法变得流行起来。

2019 年，我发明了 AP&RP 方法来解决多任务系统的边界划分问题。相关论文 [16] 于 4 月发表。

分布式数据库有着曲折的历史。这里我们将重点关注 [17]。在 20 世纪 60 年代初，DBMS 是基于硬盘的键值数据库。这种数据库很快演变成了分布式架构。在 70 年代关系型 DBMS 兴起后，数据库技术从分布式架构转向了集中式架构 [18]。在此期间，与硬件的快速发展有着密切的关系。2000 年之后，随着 NoSQL 运动的兴起，数据库开始发展为键值分布式系统。

1999 年，Google 公司的 Sanjay Ghemawat [19] 和 Jeff Dean [20] 等工程师推动了一系列分布式工程实践。包括 MapReduce、Google File System、Bigtable 等。这直接促进了大数据、内存数据库和微服务等分布式技术的工业化。为分布式工程的工业化做出了巨大贡献。

需要解决的分布式问题

我们可以看到，分布式研究中有许多问题。分布式工程的核心问题是什么？我同意 Borowsky、Elizabeth、Gafni、Eli 在 1993 年的论文 [21] 中的说法：“**在各种模型下，可解与不可解的分布式任务之间的界限划分是分布式计算理论的圣杯。**”

也就是说，分布式软件工程需要解决的核心问题是：**任何软件系统能否被分布式，如何进行分布式，以及分布式后的结果是什么？** 在本文之前，这个问题没有答案。也就是说，分布式在那之前仅仅是一个研究方向。过去，没有已知的方法可以解决分布式工程的核心问题。本文仅提供了解决核心问题的方法论。分布式已经从一个研究方向转变为一门工程。

答案是：任何软件系统能否被分布式，如何进行分布式，以及分布式后的结果是什么。首先，应该对软件系统进行分类。我们将软件系统分为四类。它们是单任务计算 (Single-Sask-Computing)、多任务计算 (Multitask-Computing)、单任务计算与共享数据集 (Single-Task-Computing&Sharing-Data-Sets) 以及多任务计算与共享数据集 (Multitask-Computing&sharing-Data-Sets)。这种分类涉及三个概念。第一个任务是离散数学所表达的程序逻辑。它包含一个或多个计算步骤。计算是指计算单元完成了程序逻辑的操作。共享数据集是指每个任务完成后生成的数据，无论是为下次执行保留还是供其他任务共同使用。对于这四种情况，我们进行如下分析。

1. 单任务计算 (Single-Task-Computing)。最容易理解，例如计算 π 的生成。该算法是否可以分布式是一个数学概念。已知只有少数数学算法可以进一步细化为分布式。
2. 多任务计算 (Multitask-Computing)。可以理解为多个数学算法的同时执行。也就是说，我们传统上将计算机进程彼此分离。这种完全隔离的计算机进程是可以被分布式的。例如，一台硬件上的计算机系统可以被理解为一个广义的分布式系统。
3. 单任务计算与共享数据集 (Single-Task-Computing&Sharing-Data-Sets)。这种情况在集成电路或控制器中更为常见。例如，车辆速度传感器收集速度数据，并使用速度数据更新显示屏。这种情况不能进一步细化为分布式。但广义地说，这种情况与第二种情况相同。对于多个单任务计算与共享数据集协同工作的场景，也可以将其视为一个广义的分布式系统。
4. 最后一种情况，多任务计算与共享数据集 (Multitasking-Computing&Sharing-Data-Sets)，是我们通常在异步网络中称之为的软件系统。使用 AP&RP 方法，我们可以清楚地指出这种情况是否可以分布式，如何进行分布式，以及分布式后的结果是什么。Actor 模型也是面向对象模型或按产品功能划分的方法。它们不具备判断是否可分布式或如何可分发的能力。不同的划分方案需要不断尝试，以确定它们是否会导致数据冲突。直到找到一个错误较少的划分方案，才可能给出分布式结果。同样的一致性哈希表也没有提供任何答案。一致性哈希通常使用最大冗余的方法来尝试覆盖所有可能的分割结果。

到目前为止，我们知道任何给定软件系统的第一类和第三类要么不能分布式，要么在极少数特定情况下可以分布式。第二类是天然的分布式架构。最后，第四类可以通过 AP&RP 解决分布式问题。至此，我们给出了解决核心问题的方法论。

分布式系统的稳定性

分布式系统的稳定性通常被称为可用性。FLP 定理首先指出分布式系统是一个非常不稳定的系统。这包括困扰科学家们的著名停机问题 [22]。

通过进一步观察，分为硬件和软件问题，这里我们首先从硬件的角度。硬件是否稳定遵循另一个规则：浴盆曲线 [23]。每种硬件都经历一个从不稳定到稳定再到老化的过程。假设分布式系统中有 n 个硬件组件。每个硬件的平均损坏概率为 x，这由基本概率公式决定。任何服务器在集群中损坏的概率为 x1*x2*x3…*xn。因此，我们得到定理 1。

定理 1. 分布式系统的整体不稳定性随着硬件的增加而增加。

也就是说，损坏的概率随着分布式集群的增加而增加。从另一个角度看，随着分布式集群的增加，任何硬件损坏都会导致集群总损坏面积的减少，即集群的损坏面积将减少到 1/n。因此，我们得到定理 2。

定理 2. 分布式系统的损坏面积随着硬件的增加而减小。

所以，不用再担心分布式集群的稳定性了！而为什么不稳定性增加了呢？因为它们转化为损坏面积的减少。所以我们需要做的是减少集群中的顺序依赖性，即不可替代的层级关系。避免任何单点服务中断导致损坏面积进一步扩大。有趣的是，这与现代企业管理体系非常相似。因此，我们得到定理 3。

定理 3. 层级关系及其不可替代性会扩大损坏区域。

软件和硬件问题非常相似。为了提高代码的可重用性，软件在软件工程中引入了大量的层级关系。这种层级关系也随着软件的分布式而投影到分布式系统中。相同的硬件分布式规则适用于软件。因此，我们可以得到分布式系统损坏的定理。

定理 4：分布式系统中任何单点的层级关系、不可替代性以及最终影响的区域决定了损坏的区域。

为了减少分布式系统中的任何单点损坏，会造成更多的损坏。我们需要减少分布式系统中的层级关系以及任何单点的不可替代性。但是我们知道，接收消息的系统服务是不可替代的。否则，将创建新的原子关系。也就是说，接收两个相同消息的不同处理结果在系统中将无法协调。因此，最小的损坏区域与分布式系统中接收消息的最小服务单元相同。

分布式系统中的一致性

FLP 定理证明了在分布式系统中不存在绝对的一致性。我认为这是基于能量守恒的一个简单推论。即信息的传播具有方向性和能量消耗。信息从任何源到任何目的地都需要能量消耗，并遵循能量守恒定律。因此，信息传播的时间不能为零。所以，这个传播过程的描述包含了顺序一致性和基于时间 t 的一致性 [24]。它们都描述了相同的情况。基于简单的概率原理，参与此传播的硬件越少，能量消耗和时间越少，损坏的概率就越低。相反，越不可靠，即越容易发生不一致。也就是说，在能量守恒方面，不存在绝对的一致性。任何系统的“一致性”评估都基于其坐标系中的比较结果。例如，广域网比局域网不稳定，局域网比硬件不稳定。因此，建立一个分布式精度评估系统更有意义。

结论

计算机理论中的分布式工程是一个非常年轻的学科。随着摩尔定律进入减速期，硬件发展放缓。加上互联网行业的爆发，软件系统变得越来越复杂。分布式工程迎来了难得的历史机遇。目前，由于软件系统的产品逻辑和分布式架构之间的混淆，软件系统的开发、二次开发和维护成本非常高。企业需要雇佣大量的开发人员来控制软件系统。我估计，随着产品逻辑与架构的分离，开发工作量将初步减少一半。并大大减少二次开发的工程量和维护成本。总的来说，企业的开发成本比现在可以降低约 95%。这将极大地降低传统企业进入互联网的门槛，并将大量开发人员从繁重的维护工作中解放出来。可以预见，在不久的将来，互联网行业将再次迎来爆发期。大量的工具被开发出来用于分布式软件的开发。真正的分布式操作系统也应运而生。目前分布式工程仍然非常薄弱。中国大陆有八所大学仍在进行分布式研究。随着分布式工程实践性的发展。分布式技术的普及和标准化还需要大量的工作。我希望看到更多的学者、更多的开发者、更多的公司和组织投入到分布式工程中。

参考文献

1. https://en.wikipedia.org/wiki/Distributed_computing
2. https://en.wikipedia.org/wiki/Actor_model
3. https://en.wikipedia.org/wiki/Consistency_model#Sequential_consistency
4. https://dl.acm.org/citation.cfm?id=800220&picked=prox
5. https://en.wikipedia.org/wiki/Dijkstra_Prize
6. Dwork, Cynthia; Lynch, Nancy; Stockmeyer, Larry (April 1988). "Consensus in the Presence of Partial Synchrony" (PDF). Journal of the ACM. 35 (2): 288–323. CiteSeerX 10.1.1.13.3423. doi:10.1145/42282.42283.
7. C. Mohan, Bruce Lindsay (1985): "Efficient commit protocols for the tree of processes model of distributed transactions",ACM SIGOPS Operating Systems Review, 19(2),pp. 40-52 (April 1985)
8. https://en.wikipedia.org/wiki/Erlang_(programming_language)
9. https://en.wikipedia.org/wiki/Paxos_(computer_science)
10. https://en.wikipedia.org/wiki/Consistent_hashing
11. https://en.wikipedia.org/wiki/CAP_theorem
12. https://www.infoq.com/articles/cap-twelve-years-later-how-the-rules-have-changed
13. https://en.wikipedia.org/wiki/Distributed_hash_tabl
14. Ian Clarke. A distributed decentralised information storage and retrieval system. Unpublished report, Division of Informatics, University of Edinburgh, 1999.
15. https://en.wikipedia.org/wiki/Raft_(computer_science)
16. Sun shuo.”Distributed Method of Web Services”. https://codeproject.org.cn/Articles/3335097/Distributed-Method-of-Web-Services
17. https://en.wikipedia.org/wiki/Database
18. R.A. Davenport. Distributed database technology−asurvey. Computer Networks, 2(3):155–167, 1978.
19. https://en.wikipedia.org/wiki/Sanjay_Ghemawat
20. https://en.wikipedia.org/wiki/Jeff_Dean_(computer_scientist)
21. Borowsky, Elizabeth; Gafni, Eli (1993). "Generalized FLP impossibility result for t-resilient asynchronous computations". P 25th Annual ACM Symposium on Theory of Computing. ACM. pp. 91–100.
22. https://en.wikipedia.org/wiki/Halting_problem
23. https://en.wikipedia.org/wiki/Bathtub_curve
24. Seth Gilbert, Nancy Lynch. "Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services". ACM SIGACT News, v.33 n.2, June 2002 [doi>10.1145/564585.564601]