提高软件系统性能的重要方法之一是支持并发编程，特别是在采用多核系统结构时。并发性对于实现容错和分布式服务也至关重要。然而，掌握并发性一直是可怕的挑战之一。并发编程很难同时处理许多可能的任务，包括故障、操作系统、共享内存架构和异步。
并发执行和顺序执行
理解并发计算的主要方法是将并发域中的问题转化为顺序域中更简单的问题，这是连接两个领域的权衡和桥梁。
首先，可以并发访问的对象或服务只能在过程中依次访问对象时执行预期行为。因此，串行计算可用于指定共享对象，如经典数据结构（队列、堆栈和列表）、可读或修改的寄存器或数据库事务。这使得理解正在实现的对象变得容易，而不像真正的并发计算那样困难或不自然。
其次，串行计算为高效、可伸缩、容错的并发对象提供了实现技术。锁是对共享数据和并发控制/服务协议的独家访问。复制数据的协议以相同的顺序在当地执行对象。可靠的通信协议，如原子广播，可用于过程之间的通信和分布式数据结构。例如，区块链提交协议可以确保原子属性。常用的技术包括时间戳、投票共识、成员组关系和故障检测器，由进度条件指定，以确保实际操作。
桥接器在并发执行和串行执行之间建立连接。它强制执行安全属性。通过这些属性，并发执行似乎是串行执行对象在某些顺序交织中的呼叫操作。一致性条件定义了对象操作的并发呼叫，然后可以根据其顺序和规范进行测试。
演变的历史是这样的，从相互排斥开始，然后在信息传输系统上读写寄存器，最后通过强大的同步机制实现任何对象，以及区块链的高可扩展性和防篡改性。
互斥锁
并发的出现是为了有效地利用顺序执行的计算机机。顺序执行的计算机只能一次执行一个指令，让用户认为他们的程序是通过操作系统同时运行的。
一旦并发程序开始相互交互，危机就会出现。当时并发编程没有概念基础，程序错误百出，程序行为不一致。1965年，Dijkstra 发现一些代码的互斥锁是编程的基本概念，从而开辟了并发编程的道路。
锁
互斥锁/代码算法包含类似的过程调用acquire ()和 release ()代码，用于称为临界区域的代码。通常执行它的环境是异步的，进程速度是任意的，是独立的。互斥锁算法保证了两种性质。
临界互斥锁没有同时执行两个过程。
如果调用并发执行一个或多个过程 acquire ()操作时，只调用一个过程并执行临界区域。
锁不能防止某些过程永远无法进入临界区的特定场景。
互斥锁算法
假设两个过程 p1和 p共享三个读写原子寄存器，F1、 F2和 L，最初的 F1和F二是关闭，而 L不需要初始化。所有寄存器都可以读取这两个过程。原子寄存器意味着寄存器上的读写操作是按顺序进行的。
当进程 p1 调用 acquire ()时，它首先设置自己的标志，从而表明它在竞争，然后在 L在寄存器的最后一个写入者中写入自己的名字。接下来，过程p在它看到之前，重复读取所有寄存器 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，然后，在收到完全有序的信息时执行过程 Todeiver ()。在基于串行计算的并发编程中，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点系统性思考
如何进入一个新领域
全栈必备 敏捷估点
一个函数的自白