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

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

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

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

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

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

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

互斥鎖

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

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

鎖

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

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

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

互斥鎖算法

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

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

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

從資源到對(duì)象

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

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

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

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

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

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

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

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

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

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

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

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

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

并發(fā)對(duì)象

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

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

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

在異步或者易崩潰的環(huán)境中，所有對(duì)象并不相同。一致性對(duì)象是最強(qiáng)大的，因?yàn)樗鼈兛梢杂脕?lái)實(shí)現(xiàn)由串行計(jì)算定義的任何對(duì)象。其他對(duì)象，如隊(duì)列或堆棧具有中等強(qiáng)度，它們不能由只使用讀/寫寄存器進(jìn)行通信的異步進(jìn)程實(shí)現(xiàn)。這些實(shí)現(xiàn)要求進(jìn)程調(diào)用的任何操作必須返回，無(wú)需等待。

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

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

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

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

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

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

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

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

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

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

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

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

小結(jié)

在分布式系統(tǒng)中，最終一致性被廣泛地部署以實(shí)現(xiàn)高可用性數(shù)據(jù)，最終所有對(duì)該數(shù)據(jù)項(xiàng)的訪問都將返回最后更新的值。在區(qū)塊鏈中，通過放松控制并發(fā)性的串行控制可以獲得的好處，區(qū)塊鏈末端的分支暫時(shí)違反了分類賬對(duì)象的一致性。盡管如此，區(qū)塊鏈還是受到了性能瓶頸的困擾，因?yàn)樗枰獙⑺械慕灰着判蛟谝粋€(gè)單一的列表中，這促進(jìn)了部分有序列表的探索，例如基于有向無(wú)環(huán)圖的Tangle 或 Hashgraph。

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

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