并发计算中的串行思考

软件系统性能的提升的重要方法之一是支持并发性编程，尤其是采用多核体系结构的时候。在全局数据库、云计算和区块链应用程序中，并发性对于实现容错和分布式服务也是至关重要的。然而，对并发性的掌握一直是令人畏惧的挑战之一。并发编程是困难的，要同时处理许多可能任务的非确定性行为，包括故障、 *** 作系统、共享内存架构和异步。

并发执行与顺序执行

理解并发计算的主要方法就是将并发域中的问题转换为顺序域中更简单的问题，这又是一种权衡，也是一个连接两个领域的桥梁。

首先，可以并发访问的对象或服务，只有在进程依次访问对象的情况下，才会执行期望的行为。因此，串行计算可以用来指定共享对象，例如经典的数据结构(队列、堆栈和列表)、可读取或修改的寄存器或数据库事务。这使得理解正在实现的对象变得容易，而不像真正的并发计算那样困难或不自然。

其次，串行计算为高效、可伸缩和容错的并发对象提供了实现的技术。锁是对共享数据和并发控制/服务协议的独占访问，复制数据的协议以相同的顺序在本地执行对象 *** 作，可靠的通信协议如原子广播可以用于进程之间的通信，分布式数据结构，如区块链的提交协议可以确保原子性属性。常用的技术包括时间戳、投票共识、成员组关系和故障检测器，由进度条件来指定，以保证实际执行 *** 作。

桥接器在并发执行和串行执行之间建立连接。它强制执行安全属性，通过这些属性，并发执行看起来好像是在某些顺序交织中串行执行对象上的调用 *** 作。一致性条件定义了对象 *** 作的并发调用，然后可以根据其顺序规范进行测试。

演变的历史是这样的，从互斥锁开始，然后在消息传递系统上实现读/写寄存器，最后是通过强大的同步机制实现任意对象，以及区块链的高度可扩展性和防篡改的方式。

互斥锁

并发的出现是为了有效地利用顺序执行的计算机，顺序执行的计算机一次只能执行一条指令，让用户认为他们的程序通过 *** 作系统同时运行。

一旦并发运行的程序开始相互交互，危机就会浮现，当时的并发编程没有任何概念基础，程序错误百出，还会并会导致程序行为的不一致。1965年，Dijkstra 发现部分代码的互斥锁是编程的一个基本概念，从而打开了并发编程的道路。

锁

互斥锁/代码算法包含了进程调用类似acquire ()和 release ()的代码，这些代码用于称为临界区的一段代码。通常执行它的环境是异步的，其中进程速度是任意的，彼此独立。互斥锁算法保证了两个性质。

没有两个进程同时执行临界互斥锁。

如果一个或多个进程调用并发执行的 acquire () *** 作，则只有一个进程调用并执行临界区。

锁并不能防止出现某些进程永远不能进入临界区的特定场景。

互斥锁算法

假设两个进程 p1和 p2共享三个读/写原子寄存器，F1、 F2和 L，最初的 F1和F2是关闭的，而 L不需要初始化。这两个进程都可以读取所有寄存器。原子寄存器味着寄存器上的读写 *** 作是按顺序执行的。

当进程 p1 调用 acquire ()时，它首先设置自己的标志，从而表明它在竞争，然后在 L中写入自己的名字，表明它是这个寄存器的最后一个写入者。接下来，进程p1重复读取所有寄存器，直到它看到 F1或F2的标志不是p1， 或者p1不再是 LAST 的最后一个写入者。当这种情况发生时，p1终止它的调用， *** 作 release ()。

互斥锁是通过顺序思维掌握并发编程的第一种机制，导致了开始为并发计算提供了科学的基础概念，例如竞争条件和原子性的概念。使用锁控制对数据的访问(例如，两阶段锁) ，是并发控制的起源。

从资源到对象

开始的时候，临界区是物理资源的封装使用，物理资源本身的性质是按顺序指定的(例如，磁盘、打印机、处理器)，然后使用锁来保护对简单数据(如文件)的并发访问。然而，当临界区开始被用来封装更一般的共享对象，就需要新的处理方法了。

数据不是物理资源，共享对象不同于物理对象。它不需要独占访问，一个进程可以读取一个文件的数据，而另一个进程可以并发地修改它。无需使用互斥锁即可实现纯数字对象的并发计算成为可能， *** 作可以在时间上重叠。

此外，在存在异步和进程崩溃的情况下，互斥锁不能用于实现对象。如果一个进程在它的临界区内崩溃，那么其他进程无法判断它是崩溃了还是只是速度太慢，从而无法访问该对象。

在发生并发访问以共享数据的情况下，需要一个一致性条件来定义哪些并发 *** 作被认为是正确的。从外部观察者的角度来看，所有的 *** 作都必须显示为顺序执行。这就是循序一致性/服务的概念 ，自1976年以来一直在数据库场景中使用，以保证事务看起来是自动执行的。但是，循序一致性/服务是不可组合的。线性化(或原子性)的强一致性条件要求 *** 作的总顺序遵守非重叠 *** 作的顺序。

基于消息系统的读写寄存器

最基本的共享对象就是读/写寄存器。在共享内存中，简单的寄存器支持只有一个进程可以写，另一个进程可以读，而多写多读(MWMR)寄存器则支持每个进程都可以写，每个进程都可以读。

分布式消息系统通常支持共享内存的抽象，并得到了广泛接受，这种抽象提供了单处理器概念的自然转换，并简化了编程任务。在可靠的异步消息传递系统上构建原子读/写寄存器相对容易，但如果进程可能崩溃，则需要更复杂的算法：

一种在 n 个异步消息进程系统上实现原子读/写寄存器的算法，其中最多小于n/2的进程可能崩溃。

不可能在 n/2的进程崩溃时构建原子读/写寄存器。

这样的算法说明了减少并发对顺序执行的重要性，其设计原则是每个写入的值都有一个标识，每个进程既是客户端又是服务器，构建的多写多读(MWMR)寄存器——R，任何进程都可以读写寄存器。在客户端，进程P可以调用 *** 作 R.write (v)在 REG 中写一个值 v，R.read ()以获取其当前值。在服务器端，进程P管理两个本地变量: 本地实现 R-i和 Timestamp-i (包含由序列号和进程标识组成的时间戳)。时间戳构成了在 R-i 中保存值 v 的“标识”,也就是说，这个值在此时是由这个进程写入的，任何两个时间戳完全是按照它们的字典序排序的。

进程 P向所有进程广播查询，并等待大多数进程的确认即投票仲裁，这就意味着读/写寄存器 R具有原子性属性。

当流程P调用 R.write (v)时，它首先创建一个标记，该标记将标识由此写 *** 作调用生成的查询/响应消息。然后，它执行查询/响应模式，了解在大多数进程的本地变量 Timestamp-j 中保存的最高序列号。完成后，进程P计算时间戳 ts，这个时间戳将与它要在 R中写入的值 v 相关联。最后，进程P启动第二个查询/响应模式，在该模式中将(v，ts)广播给所有进程。当它从投票仲裁者收到相关的确认时，才会终止这一 *** 作。

在服务器端，其他进程在写 *** 作的第一阶段接收进程P发送的 WRITE R 消息，并发送回一个确认，该确认带有与它在 R-i 中保存的新值相关的序列号。当在写 *** 作的第二阶段接收到由进程P发送的 WRITE R消息时，如果接收到的时间戳比保存在时间戳中的时间戳更新，这些进程就会更新实现本地数据 R-i，并且，在所有情况下，它都会发送回P和确认，因此 ，P终止了它的写 *** 作。

因此，调用进程P与值 v 相关联的时间戳大于在P发出写 *** 作之前的写 *** 作时间戳。此外，虽然并发写 *** 作可以将相同的序列号与它们的值关联，但是这些值具有不同的有序时间戳。异步消息系统中实现原子读/写寄存器也是串行计算在抽象层上的使用。

并发对象

读/写寄存器是一种特殊的对象。一般来说，一个对象是由进程可以调用的一组 *** 作定义的，当这些 *** 作按顺序调用时，对象的行为预先定义好的。这些可以用状态机或一组顺序标识来表示。因此，可以使用串行计算中常见的数据结构(如队列和堆栈)来定义并发对象。

在许多使用串行计算的并发编程(包括状态机复制)中，其核心是协议问题。一个常见的基础抽象是一致性对象。如果， C是一个一致性对象，进程P调用 *** 作 C.propose (v)一次，则最终返回一个值 v’。C的这个顺序规范是由以下属性定义的：

如果调用返回 v，则存在 C.propose (v)；

不返回两个不同的值；

如果一个进程调用 C.propose (v)并且没有崩溃，那么该 *** 作将返回一个值。

在异步或者易崩溃的环境中，所有对象并不相同。一致性对象是最强大的，因为它们可以用来实现由串行计算定义的任何对象。其他对象，如队列或堆栈具有中等强度，它们不能由只使用读/写寄存器进行通信的异步进程实现。这些实现要求进程调用的任何 *** 作必须返回，无需等待。

在存在异步通信和进程崩溃的情况下，对象同步能力的一种测量方法是它的共识数量。如果对象 o 的共识数是整数 n，那么，从任意数量的对象 o 和原子读/写寄存器实现 n 个进程的一致性对象，例如，Set 对象或堆栈对象的共识数为2。

状态机复制

并发堆栈可以通过使用互斥锁执行 pop ()和 push () *** 作来实现。但是，如果进程崩溃，这种策略将不起作用。状态机复制机制是通过异步进程通信实现的一种通用方法。其基本思想是让进程在并发调用的顺序上达成一致，然后每个进程在本地模拟串行计算的状态机。

假设把To-broadcast 抽象为分布式计算中的一个原语，它确保所有正确的进程以相同的顺序接收消息。进程调用 Tobroadcast (m) ，向所有其他进程发送消息 m，那么，进程在收到完全有序的消息时执行 Todeliver ()。在基于串行计算的并发编程中，To-broadcast 是一个普遍的概念，这种通信抽象促进了基于串行计算并发对象的构建。

对于基于 To-broadcast 的状态机复制而言，每个进程Px都有一个对象的拷贝状态，To-broadcast 抽象用于确保所有进程Px 对其对象 o 的本地状态采用相同的 *** 作序列。实现协商一致的 To-broadcast，如果调用进程在调用期间没有崩溃，则所有流程都会收到 m，如果流程的任意子集收到 m。算法的核心是后台任务，一个进程会一直等待, 会对消息进行排序。

区块链中的并发计算

在区块链网络中，所有参与者都可以拥有自己的分类账副本。它们中的任何一个都可以在分类账中附加一个记录，然后在几分钟甚至几秒钟内反映在所有副本中。使用加密技术，存储在分类账中的记录可以保持防篡改性。

区块链中典型的分布式分类账，是特定账本对象的一个拜占庭式容错复制实现。账本对象有两个 *** 作，read ()和 append ()。它的串行计算是由一个块列表定义的，可以在列表的末尾添加一个块 x， *** 作 append (x) ，而 read ()返回整个列表。在加密货币的情况下，x 可能包含一组交易。

因此，和任何其他对象一样，账本对象可以使用拜占庭容错状态机的复制算法来实现。相反，分类帐可以作为一个通用结构，是一个具有转换函数的状态机定义的对象 o。为此，当进程调用 append (x)时，x 包含一个应用于状态机的转换。对象的状态通过 read ()获得，该调用返回被顺序附加到分类账中的 *** 作序列，然后从对象的初始状态开始在本地应用它们。

显然，read () *** 作返回已应用到状态机的命令列表，保证了列表防篡改的可能性，区块链的实现中使用加密散列将每个记录链接到前一个记录。

任何人都可以附加块并读取区块链。与通过串行计算掌握并发性的传统算法相反，参与者不必事先知道，可以随时间变化，甚至可能是匿名的。在某种意义上，就是一个开放的分布式数据库，没有信任的权威节点，数据本身分布在参与者之间。

在状态机复制的框架下，比特币的区块链实现相对简单。从概念上讲，它建立在随机共识的基础上，每当几个进程想要同时添加一个区块时，它们就参与抽签。每个进程在0和某个大整数K之间选择一个随机数，得到小于K的数字的进程获胜，并有权追加其所需的区块。这为通过串行思维控制并发性的范例引入了一个新的想法，在更快的状态机复制和暂时的一致性缺失之间进行权衡。

小结

在分布式系统中，最终一致性被广泛地部署以实现高可用性数据，最终所有对该数据项的访问都将返回最后更新的值(。在区块链中，通过放松控制并发性的串行控制可以获得的好处，区块链末端的分支暂时违反了分类账对象的一致性。尽管如此，区块链还是受到了性能瓶颈的困扰，因为它需要将所有的交易排序在一个单一的列表中，这促进了部分有序列表的探索，例如基于有向无环图的Tangle 或 Hashgraph。

CAP 定理形式化了通过顺序推理掌握并发性方法的一个基本限制，另一种选择是可用性成本。只要只有少数程序可能失败，该系统就会继续运作，并维护其一致性保障。

另外，基于串行计算的并发性方法有一个基本的限制，并非所有并发问题都有顺序规范。事实上，如今我们也没有好的工具来构建高效、可伸缩和可靠的并发系统。

[关联阅读]

计算机体系结构的一知半解

WebAssembly一知半解

服务可用性的一知半解

DHT算法的一知半解

稳定币的一知半解

NFT 的一知半解

ES的一知半解

数据存储的趣事

NoSQL 之于大数据

从应用架构看大数据

面向AI 的数据生态系统

老曹眼中的面向数据架构

‍tataUFO 大数据 应用实践

基于CRDT的数据最终一致性

web 系统中——结构化数据标记

知新温故，从知识图谱到图数据库

清单管理？面向机器学习中的数据集

Crash?! ——软件崩溃后的数据一致性

华为数据之道 ——  数据分类管理框架和经验

这是你所了解的FaaS ？——无服务计算的10个思考

没有被了解的API？一个老码农眼中的API世界

关于软件开发，都应该知道的10个常识

Crash?! ——软件崩溃后的数据一致性

关于软件研发生产力的误区与思考

远程软件工程师的10个最佳实践

翻译如重构期待您的单元测试

如何提高团队的研发效率呢？

性能，10点系统性思考

如何进入一个新领域

全栈必备 敏捷估点

一个函数的自白