提高软件系统性能的重要途径之一就是支持并发编程，尤其是在使用多核架构时。在全球数据库、云计算和区块链应用程序中，并发对于实现容错和分布式服务也至关重要。然而，掌握并发性一直是一项艰巨的挑战。并发编程是困难的，同时处理许多可能任务的非确定性行为，包括故障、操作系统、共享内存架构和异步。并发执行和顺序执行理解并发计算的主要方法是将并发域中的问题转换为顺序域中更简单的问题。这是另一个权衡，也是连接两个领域的桥梁。首先，可以并发访问的对象或服务只有在进程顺序访问对象时才会执行所需的行为。因此，串行计算可用于指定共享对象，例如经典数据结构（队列、堆栈和列表）、可读取或修改的寄存器或数据库事务。这使得理解对象正在实现什么变得容易，而不会像真正的并发计算那样困难或不自然。其次，串行计算为高效、可扩展和容错的并发对象提供了实现技术。锁是对共享数据和并发控制/服务协议的独占访问，复制数据的协议以相同的顺序在本地执行对象操作，可靠的通信协议如原子广播可用于进程之间的通信，分布式数据结构，Commit协议如区块链可以确保原子性属性。常用的技术包括时间戳、投票共识、成员组关系和故障检测器，由进度条件指定以保证操作实际执行。桥在并发执行和串行执行之间建立连接。它强制执行安全属性，通过这些属性，并发执行看起来就像在一些顺序交织中串行执行对象上的调用操作一样。一致性条件定义了对象操作的并发调用，然后可以根据它们的顺序规范对其进行测试。进化的历史是这样的，从互斥体开始，然后在消息系统上实现读/写寄存器，最后通过强同步机制实现任意对象，以及区块链高度可扩展和防篡改的方式。互斥并发的出现是为了有效地利用顺序执行计算机，它一次只能执行一条指令，使用户认为他们的程序正在通过操作系统并发运行。一旦并发运行的程序开始相互影响，就会出现危机。那时候并发编程没有任何概念基础，程序错误百出，也会导致程序行为不一致。1965年，Dijkstra发现部分代码的互斥锁是编程的一个基本概念，从而开启了并发编程之路。锁定互斥体/代码算法由过程调用组成，例如acquire()和release()用于一段称为临界区的代码。通常它执行的环境是异步的，其中进程的速度是任意的并且彼此独立。互斥锁算法保证了两个属性。没有两个进程同时执行关键互斥体。如果一个或多个进程调用并发执行的acquire()操作，则只有一个进程调用并执行临界区。锁不会阻止某些进程永远无法进入关键部分的特定场景。互斥算法假设两个进程p1和p2共享三个读写原子寄存器F1、F2和L，初始F1和F2是关闭的，L不需要初始化。两个进程都可以读取所有寄存器。原子寄存器是指对寄存器的读写操作是顺序进行的。当进程p1调用acquire()时，它首先设置自己的标志，从而表明它正在竞争，然后在L中写入自己的名字，表明它是这个寄存器的最后写入者。接下来，进程p1反复读取所有寄存器，直到看到F1或F2的标志不是p1，或者p1不再是LAST的最后写入者。发生这种情况时，p1终止调用，运行release()。互斥量是第一个通过顺序思维掌握并发编程的机制，导致开始为并发计算提供科学的基础概念，例如竞争条件和原子性的概念。使用锁来控制对数据的访问（例如，两阶段锁）是并发控制的起源。当从资源开始到对象时，临界区是对按顺序指定性质的物理资源（例如磁盘、打印机、处理器）的封装，然后使用锁来保护简单数据（例如文件）的并发访问。然而，当临界区开始用于封装更通用的共享对象时，就需要一种新的方法。数据不是物理资源，共享对象不同于物理对象。它不需要独占访问，一个进程可以读取文件数据，而另一个进程可以同时修改它。无需使用互斥量就可以对纯数字对象进行并发计算，并且操作可以及时重叠。此外，互斥锁不能用于在存在异步和进程崩溃的情况下具体化对象。如果一个进程在其临界区内崩溃，其他进程就无法判断它是崩溃了还是访问对象的速度太慢了。在发生并发访问以共享数据的情况下，需要一致性条件来定义哪些并发操作被认为是正确的。从外部观察者的角度来看，所有操作都必须按顺序执行。这就是SequentialConsistency/Services的概念，它从1976年开始就被用于数据库场景，以保证事务看起来是自动执行的。然而，顺序一致性/服务是不可组合的。线性化（或原子性）的强一致性条件要求操作的总顺序遵守非重叠操作的顺序。基于消息系统读写寄存器最基本的共享对象是读写寄存器。在共享内存中，简单寄存器只允许一个进程写入而另一个进程可以读取，而写多读（MWMR）寄存器允许每个进程写入和每个进程读取。分布式消息系统通常支持并广泛接受共享内存的抽象，它提供了单处理器概念的自然翻译并简化了编程任务。在可靠的异步消息传递系统上构建原子读/写寄存器相对容易，但如果进程可能崩溃，则需要更复杂的算法：Analgorithmforatomicread/writeregistersonasystemofnasynchronousmessage-passing进程，其中最多少于n/2个进程可能会崩溃。当n/2个进程崩溃时，不可能构建原子读/写寄存器。这样的算法说明了降低并发性对顺序执行的重要性。它的设计原则是每个写入的值都有一个标识符，每个进程既是客户端又是服务器。构造的多写多读（MWMR）寄存器——R，任何进程都可以读写寄存器。在客户端，进程P可以调用操作R.write(v)将值v写入REG，并调用R.read()获取其当前值。在服务器端，进程P管理两个局部变量：本地实现R-i和Timestamp-i（包含由序列号和进??程ID组成的时间戳）。时间戳构成了R-i中持有值v的“身份”，即这个值是当时这个进程写入的，任意两个时间戳都按照字典序排列。进程P向所有进程广播查询，等待大多数进程的确认，即投票仲裁，这意味着读写寄存器R具有原子性。当进程P调用R.write(v)时，它首先创建一个令牌，用于标识此写入操作调用生成的查询/响应消息。然后，它针对大多数进程本地的变量Timestamp-j中保存的最高序列号执行查询/响应模式。完成后，进程P计算一个时间戳ts，该时间戳ts将与它要写入R的值v相关联。最后，进程P启动第二个查询/响应模式，其中(v,ts)被广播到所有进程。收到投票仲裁员的相关确认后，终止本次操作。在服务器端，其他进程在写入操作的第一阶段收到进程P发送的WRITER消息，并发回一个确认，其中包含与它保存在R-i中的新值相关联的序列号。当在写入操作的第二阶段接收到进程P发送的WRITER消息时，如果接收到的时间戳比存储在时间戳中的时间戳新，则这些进程更新实现本地数据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个进程的共识对象，例如一致数为2的Set对象或堆栈对象。复制并发堆栈的状态机可以通过使用互斥锁执行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可能包含一组交易。因此，与任何其他对象一样，Ledger对象可以使用拜占庭容错状态机的复制算法来实现。相反，分类帐可以用作通用结构，一个由具有转换函数的状态机定义的对象。为此，x包含一个在进程调用append(x)时应用于状态机的转换。对象的状态是通过read()获得的，它返回一系列操作，这些操作顺序附加到账本，然后从对象的初始状态开始在本地应用。显然，read()操作返回了一个已应用于状态机的命令列表，保证了列表被篡改的可能性。加密哈希在区块链实现中用于将每条记录链接到前一条记录。任何人都可以添加块并读取区块链。与通过串行计算掌握并发性的传统算法相反，参与者不必事先知道，可以随时间变化，甚至可以是匿名的。从某种意义上说，它是一个开放的分布式数据库，没有可信的权威节点，数据本身分布在参与者之间。在状态机复制的框架下，比特币的区块链实现相对简单。从概念上讲，它基于随机共识，其中多个进程在想要同时添加一个块时参与抽签。每个进程在0到某个大整数K之间随机选择一个数，得到一个小于K的数的进程获胜，有权追加自己需要的块。这为通过串行思维控制并发的范例引入了一个新思路，即在更快的状态机复制和暂时的一致性丢失之间进行权衡。总结在分布式系统中，最终一致性被广泛部署以实现数据的高可用性，最终所有对数据项的访问都会返回最后更新的值。在区块链中，区块链末端的分叉暂时违反了分类账对象的一致性，以通过放松管理并发的串行控制来获得好处。然而，由于需要将所有交易排序在单个列表中，区块链存在性能瓶颈，这有助于探索部分有序列表，例如基于有向无环图的Tangle或Hashgraph。CAP定理形式化了通过顺序推理掌握并发的方法的基本限制，顺序推理是可用性成本的替代方法。只要只有少数程序可能失败，系统就会继续运行，保持其一致性保证。此外，基于串行计算的并发方法有一个基本限制，并非所有并发问题都有顺序规范。事实上，今天我们没有好的工具来构建高效、可扩展和可靠的并发系统。
