軟件系統性能的提升的重要方法之一是支持并發性編程，尤其是采用多核體系結構的時候。在全局數據庫、云計算和區塊鏈應用程序中，并發性對于實現容錯和分布式服務也是至關重要的。然而，對并發性的掌握一直是令人畏懼的挑戰之一。并發編程是困難的，要同時處理許多可能任務的非確定性行為，包括故障、操作系統、共享內存架構和異步。

并發執行與順序執行

理解并發計算的主要方法就是將并發域中的問題轉換為順序域中更簡單的問題，這又是一種權衡，也是一個連接兩個領域的橋梁。

首先，可以并發訪問的對象或服務，只有在進程依次訪問對象的情況下，才會執行期望的行為。因此，串行計算可以用來指定共享對象，例如經典的數據結構(隊列、堆棧和列表)、可讀取或修改的寄存器或數據庫事務。這使得理解正在實現的對象變得容易，而不像真正的并發計算那樣困難或不自然。

其次，串行計算為高效、可伸縮和容錯的并發對象提供了實現的技術。鎖是對共享數據和并發控制/服務協議的獨占訪問，復制數據的協議以相同的順序在本地執行對象操作，可靠的通信協議如原子廣播可以用于進程之間的通信，分布式數據結構，如區塊鏈的提交協議可以確保原子性屬性。常用的技術包括時間戳、投票共識、成員組關系和故障檢測器，由進度條件來指定，以保證實際執行操作。

橋接器在并發執行和串行執行之間建立連接。它強制執行安全屬性，通過這些屬性，并發執行看起來好像是在某些順序交織中串行執行對象上的調用操作。一致性條件定義了對象操作的并發調用，然后可以根據其順序規范進行測試。

演變的歷史是這樣的，從互斥鎖開始，然后在消息傳遞系統上實現讀/寫寄存器，最后是通過強大的同步機制實現任意對象，以及區塊鏈的高度可擴展性和防篡改的方式。

互斥鎖

并發的出現是為了有效地利用順序執行的計算機，順序執行的計算機一次只能執行一條指令，讓用戶認為他們的程序通過操作系統同時運行。

一旦并發運行的程序開始相互交互，危機就會浮現，當時的并發編程沒有任何概念基礎，程序錯誤百出，還會并會導致程序行為的不一致。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 定理形式化了通過順序推理掌握并發性方法的一個基本限制，另一種選擇是可用性成本。只要只有少數程序可能失敗，該系統就會繼續運作，并維護其一致性保障。

另外，基于串行計算的并發性方法有一個基本的限制，并非所有并發問題都有順序規范。事實上，如今我們也沒有好的工具來構建高效、可伸縮和可靠的并發系統。