軟件系統(tǒng)性能的提升的重要方法之一是支持并發(fā)性編程，尤其是采用多核體系結(jié)構(gòu)的時候。在全局數(shù)據(jù)庫、云計算和區(qū)塊鏈應(yīng)用程序中，并發(fā)性對于實現(xiàn)容錯和分布式服務(wù)也是至關(guān)重要的。然而，對并發(fā)性的掌握一直是令人畏懼的挑戰(zhàn)之一。并發(fā)編程是困難的，要同時處理許多可能任務(wù)的非確定性行為，包括故障、操作系統(tǒng)、共享內(nèi)存架構(gòu)和異步。

并發(fā)執(zhí)行與順序執(zhí)行

理解并發(fā)計算的主要方法就是將并發(fā)域中的問題轉(zhuǎn)換為順序域中更簡單的問題，這又是一種權(quán)衡，也是一個連接兩個領(lǐng)域的橋梁。

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

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

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

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

互斥鎖

并發(fā)的出現(xiàn)是為了有效地利用順序執(zhí)行的計算機，順序執(zhí)行的計算機一次只能執(zhí)行一條指令，讓用戶認為他們的程序通過操作系統(tǒng)同時運行。

一旦并發(fā)運行的程序開始相互交互，危機就會浮現(xiàn)，當(dāng)時的并發(fā)編程沒有任何概念基礎(chǔ)，程序錯誤百出，還會并會導(dǎo)致程序行為的不一致。1965年，Dijkstra 發(fā)現(xiàn)部分代碼的互斥鎖是編程的一個基本概念，從而打開了并發(fā)編程的道路。

鎖

互斥鎖/代碼算法包含了進程調(diào)用類似acquire ()和 release ()的代碼，這些代碼用于稱為臨界區(qū)的一段代碼。通常執(zhí)行它的環(huán)境是異步的，其中進程速度是任意的，彼此獨立?；コ怄i算法保證了兩個性質(zhì)。

• 沒有兩個進程同時執(zhí)行臨界互斥鎖。
• 如果一個或多個進程調(diào)用并發(fā)執(zhí)行的 acquire ()操作，則只有一個進程調(diào)用并執(zhí)行臨界區(qū)。

鎖并不能防止出現(xiàn)某些進程永遠不能進入臨界區(qū)的特定場景。

互斥鎖算法

假設(shè)兩個進程 p1和 p2共享三個讀/寫原子寄存器，F(xiàn)1、 F2和 L，最初的 F1和F2是關(guān)閉的，而 L不需要初始化。這兩個進程都可以讀取所有寄存器。原子寄存器味著寄存器上的讀寫操作是按順序執(zhí)行的。

當(dāng)進程 p1 調(diào)用 acquire ()時，它首先設(shè)置自己的標(biāo)志，從而表明它在競爭，然后在 L中寫入自己的名字，表明它是這個寄存器的最后一個寫入者。接下來，進程p1重復(fù)讀取所有寄存器，直到它看到 F1或F2的標(biāo)志不是p1， 或者p1不再是 LAST 的最后一個寫入者。當(dāng)這種情況發(fā)生時，p1終止它的調(diào)用，操作 release ()。

互斥鎖是通過順序思維掌握并發(fā)編程的第一種機制，導(dǎo)致了開始為并發(fā)計算提供了科學(xué)的基礎(chǔ)概念，例如競爭條件和原子性的概念。使用鎖控制對數(shù)據(jù)的訪問(例如，兩階段鎖) ，是并發(fā)控制的起源。

從資源到對象

開始的時候，臨界區(qū)是物理資源的封裝使用，物理資源本身的性質(zhì)是按順序指定的(例如，磁盤、打印機、處理器)，然后使用鎖來保護對簡單數(shù)據(jù)(如文件)的并發(fā)訪問。然而，當(dāng)臨界區(qū)開始被用來封裝更一般的共享對象，就需要新的處理方法了。

數(shù)據(jù)不是物理資源，共享對象不同于物理對象。它不需要獨占訪問，一個進程可以讀取一個文件的數(shù)據(jù)，而另一個進程可以并發(fā)地修改它。無需使用互斥鎖即可實現(xiàn)純數(shù)字對象的并發(fā)計算成為可能，操作可以在時間上重疊。

此外，在存在異步和進程崩潰的情況下，互斥鎖不能用于實現(xiàn)對象。如果一個進程在它的臨界區(qū)內(nèi)崩潰，那么其他進程無法判斷它是崩潰了還是只是速度太慢，從而無法訪問該對象。

在發(fā)生并發(fā)訪問以共享數(shù)據(jù)的情況下，需要一個一致性條件來定義哪些并發(fā)操作被認為是正確的。從外部觀察者的角度來看，所有的操作都必須顯示為順序執(zhí)行。這就是循序一致性/服務(wù)的概念 ，自1976年以來一直在數(shù)據(jù)庫場景中使用，以保證事務(wù)看起來是自動執(zhí)行的。但是，循序一致性/服務(wù)是不可組合的。線性化(或原子性)的強一致性條件要求操作的總順序遵守非重疊操作的順序。

基于消息系統(tǒng)的讀寫寄存器

最基本的共享對象就是讀/寫寄存器。在共享內(nèi)存中，簡單的寄存器支持只有一個進程可以寫，另一個進程可以讀，而多寫多讀(MWMR)寄存器則支持每個進程都可以寫，每個進程都可以讀。

分布式消息系統(tǒng)通常支持共享內(nèi)存的抽象，并得到了廣泛接受，這種抽象提供了單處理器概念的自然轉(zhuǎn)換，并簡化了編程任務(wù)。在可靠的異步消息傳遞系統(tǒng)上構(gòu)建原子讀/寫寄存器相對容易，但如果進程可能崩潰，則需要更復(fù)雜的算法：

• 一種在 n 個異步消息進程系統(tǒng)上實現(xiàn)原子讀/寫寄存器的算法，其中最多小于n/2的進程可能崩潰。
• 不可能在 n/2的進程崩潰時構(gòu)建原子讀/寫寄存器。

這樣的算法說明了減少并發(fā)對順序執(zhí)行的重要性，其設(shè)計原則是每個寫入的值都有一個標(biāo)識，每個進程既是客戶端又是服務(wù)器，構(gòu)建的多寫多讀(MWMR)寄存器——R，任何進程都可以讀寫寄存器。在客戶端，進程P可以調(diào)用操作 R.write (v)在 REG 中寫一個值 v，R.read ()以獲取其當(dāng)前值。在服務(wù)器端，進程P管理兩個本地變量: 本地實現(xiàn) R-i和 Timestamp-i (包含由序列號和進程標(biāo)識組成的時間戳)。時間戳構(gòu)成了在 R-i 中保存值 v 的“標(biāo)識”,也就是說，這個值在此時是由這個進程寫入的，任何兩個時間戳完全是按照它們的字典序排序的。

進程 P向所有進程廣播查詢，并等待大多數(shù)進程的確認即投票仲裁，這就意味著讀/寫寄存器 R具有原子性屬性。

當(dāng)流程P調(diào)用 R.write (v)時，它首先創(chuàng)建一個標(biāo)記，該標(biāo)記將標(biāo)識由此寫操作調(diào)用生成的查詢/響應(yīng)消息。然后，它執(zhí)行查詢/響應(yīng)模式，了解在大多數(shù)進程的本地變量 Timestamp-j 中保存的最高序列號。完成后，進程P計算時間戳 ts，這個時間戳將與它要在 R中寫入的值 v 相關(guān)聯(lián)。最后，進程P啟動第二個查詢/響應(yīng)模式，在該模式中將(v，ts)廣播給所有進程。當(dāng)它從投票仲裁者收到相關(guān)的確認時，才會終止這一操作。

在服務(wù)器端，其他進程在寫操作的第一階段接收進程P發(fā)送的 WRITE R 消息，并發(fā)送回一個確認，該確認帶有與它在 R-i 中保存的新值相關(guān)的序列號。當(dāng)在寫操作的第二階段接收到由進程P發(fā)送的 WRITE R消息時，如果接收到的時間戳比保存在時間戳中的時間戳更新，這些進程就會更新實現(xiàn)本地數(shù)據(jù) R-i，并且，在所有情況下，它都會發(fā)送回P和確認，因此 ，P終止了它的寫操作。

因此，調(diào)用進程P與值 v 相關(guān)聯(lián)的時間戳大于在P發(fā)出寫操作之前的寫操作時間戳。此外，雖然并發(fā)寫操作可以將相同的序列號與它們的值關(guān)聯(lián)，但是這些值具有不同的有序時間戳。異步消息系統(tǒng)中實現(xiàn)原子讀/寫寄存器也是串行計算在抽象層上的使用。

并發(fā)對象

讀/寫寄存器是一種特殊的對象。一般來說，一個對象是由進程可以調(diào)用的一組操作定義的，當(dāng)這些操作按順序調(diào)用時，對象的行為預(yù)先定義好的。這些可以用狀態(tài)機或一組順序標(biāo)識來表示。因此，可以使用串行計算中常見的數(shù)據(jù)結(jié)構(gòu)(如隊列和堆棧)來定義并發(fā)對象。

在許多使用串行計算的并發(fā)編程(包括狀態(tài)機復(fù)制)中，其核心是協(xié)議問題。一個常見的基礎(chǔ)抽象是一致性對象。如果， C是一個一致性對象，進程P調(diào)用操作 C.propose (v)一次，則最終返回一個值 v’。C的這個順序規(guī)范是由以下屬性定義的：

• 如果調(diào)用返回 v，則存在 C.propose (v)；
• 不返回兩個不同的值；
• 如果一個進程調(diào)用 C.propose (v)并且沒有崩潰，那么該操作將返回一個值。

在異步或者易崩潰的環(huán)境中，所有對象并不相同。一致性對象是最強大的，因為它們可以用來實現(xiàn)由串行計算定義的任何對象。其他對象，如隊列或堆棧具有中等強度，它們不能由只使用讀/寫寄存器進行通信的異步進程實現(xiàn)。這些實現(xiàn)要求進程調(diào)用的任何操作必須返回，無需等待。

在存在異步通信和進程崩潰的情況下，對象同步能力的一種測量方法是它的共識數(shù)量。如果對象 o 的共識數(shù)是整數(shù) n，那么，從任意數(shù)量的對象 o 和原子讀/寫寄存器實現(xiàn) n 個進程的一致性對象，例如，Set 對象或堆棧對象的共識數(shù)為2。

狀態(tài)機復(fù)制

并發(fā)堆棧可以通過使用互斥鎖執(zhí)行 pop ()和 push ()操作來實現(xiàn)。但是，如果進程崩潰，這種策略將不起作用。狀態(tài)機復(fù)制機制是通過異步進程通信實現(xiàn)的一種通用方法。其基本思想是讓進程在并發(fā)調(diào)用的順序上達成一致，然后每個進程在本地模擬串行計算的狀態(tài)機。

假設(shè)把To-broadcast 抽象為分布式計算中的一個原語，它確保所有正確的進程以相同的順序接收消息。進程調(diào)用 Tobroadcast (m) ，向所有其他進程發(fā)送消息 m，那么，進程在收到完全有序的消息時執(zhí)行 Todeliver ()。在基于串行計算的并發(fā)編程中，To-broadcast 是一個普遍的概念，這種通信抽象促進了基于串行計算并發(fā)對象的構(gòu)建。

對于基于 To-broadcast 的狀態(tài)機復(fù)制而言，每個進程Px都有一個對象的拷貝狀態(tài)，To-broadcast 抽象用于確保所有進程Px 對其對象 o 的本地狀態(tài)采用相同的操作序列。實現(xiàn)協(xié)商一致的 To-broadcast，如果調(diào)用進程在調(diào)用期間沒有崩潰，則所有流程都會收到 m，如果流程的任意子集收到 m。算法的核心是后臺任務(wù)，一個進程會一直等待, 會對消息進行排序。

區(qū)塊鏈中的并發(fā)計算

在區(qū)塊鏈網(wǎng)絡(luò)中，所有參與者都可以擁有自己的分類賬副本。它們中的任何一個都可以在分類賬中附加一個記錄，然后在幾分鐘甚至幾秒鐘內(nèi)反映在所有副本中。使用加密技術(shù)，存儲在分類賬中的記錄可以保持防篡改性。

區(qū)塊鏈中典型的分布式分類賬，是特定賬本對象的一個拜占庭式容錯復(fù)制實現(xiàn)。賬本對象有兩個操作，read ()和 append ()。它的串行計算是由一個塊列表定義的，可以在列表的末尾添加一個塊 x，操作 append (x) ，而 read ()返回整個列表。在加密貨幣的情況下，x 可能包含一組交易。

因此，和任何其他對象一樣，賬本對象可以使用拜占庭容錯狀態(tài)機的復(fù)制算法來實現(xiàn)。相反，分類帳可以作為一個通用結(jié)構(gòu)，是一個具有轉(zhuǎn)換函數(shù)的狀態(tài)機定義的對象 o。為此，當(dāng)進程調(diào)用 append (x)時，x 包含一個應(yīng)用于狀態(tài)機的轉(zhuǎn)換。對象的狀態(tài)通過 read ()獲得，該調(diào)用返回被順序附加到分類賬中的操作序列，然后從對象的初始狀態(tài)開始在本地應(yīng)用它們。

顯然，read ()操作返回已應(yīng)用到狀態(tài)機的命令列表，保證了列表防篡改的可能性，區(qū)塊鏈的實現(xiàn)中使用加密散列將每個記錄鏈接到前一個記錄。

任何人都可以附加塊并讀取區(qū)塊鏈。與通過串行計算掌握并發(fā)性的傳統(tǒng)算法相反，參與者不必事先知道，可以隨時間變化，甚至可能是匿名的。在某種意義上，就是一個開放的分布式數(shù)據(jù)庫，沒有信任的權(quán)威節(jié)點，數(shù)據(jù)本身分布在參與者之間。

在狀態(tài)機復(fù)制的框架下，比特幣的區(qū)塊鏈實現(xiàn)相對簡單。從概念上講，它建立在隨機共識的基礎(chǔ)上，每當(dāng)幾個進程想要同時添加一個區(qū)塊時，它們就參與抽簽。每個進程在0和某個大整數(shù)K之間選擇一個隨機數(shù)，得到小于K的數(shù)字的進程獲勝，并有權(quán)追加其所需的區(qū)塊。這為通過串行思維控制并發(fā)性的范例引入了一個新的想法，在更快的狀態(tài)機復(fù)制和暫時的一致性缺失之間進行權(quán)衡。

小結(jié)

在分布式系統(tǒng)中，最終一致性被廣泛地部署以實現(xiàn)高可用性數(shù)據(jù)，最終所有對該數(shù)據(jù)項的訪問都將返回最后更新的值。在區(qū)塊鏈中，通過放松控制并發(fā)性的串行控制可以獲得的好處，區(qū)塊鏈末端的分支暫時違反了分類賬對象的一致性。盡管如此，區(qū)塊鏈還是受到了性能瓶頸的困擾，因為它需要將所有的交易排序在一個單一的列表中，這促進了部分有序列表的探索，例如基于有向無環(huán)圖的Tangle 或 Hashgraph。

CAP 定理形式化了通過順序推理掌握并發(fā)性方法的一個基本限制，另一種選擇是可用性成本。只要只有少數(shù)程序可能失敗，該系統(tǒng)就會繼續(xù)運作，并維護其一致性保障。

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