?如今使用的幾乎所有軟件都是分布式系統(tǒng)的一部分，手機(jī)上的應(yīng)用程序與托管在云中的服務(wù)一起工作，托管服務(wù)本身就是大規(guī)模的分布式系統(tǒng)，通常運(yùn)行在遍布全球的機(jī)器上，大數(shù)據(jù)系統(tǒng)和大規(guī)模數(shù)據(jù)庫(kù)分布在許多機(jī)器上，大多數(shù)科學(xué)計(jì)算和機(jī)器學(xué)習(xí)系統(tǒng)在多個(gè)處理器上并行工作，即使是傳統(tǒng)的桌面操作系統(tǒng)以及諸如電子表格和文字處理器之類的應(yīng)用程序也在與分布式后端服務(wù)緊密集成。分布式系統(tǒng)中，多臺(tái)不可靠的機(jī)器并行運(yùn)行，通過(guò)具有任意延遲的網(wǎng)絡(luò)鏈路彼此發(fā)送消息。怎么能確信這些系統(tǒng)在混亂的情況下能夠做到我們想要的呢？

構(gòu)建正確的分布式系統(tǒng)并不新鮮，一個(gè)傳統(tǒng)的解決辦法是通過(guò)保證內(nèi)存一致性來(lái)降低這種復(fù)雜性，即確保以受控的方式訪問(wèn)內(nèi)存(堆變量、數(shù)據(jù)庫(kù)等)。然而，用于實(shí)施這些機(jī)制的分布式協(xié)議卻通常阻礙了分布式系統(tǒng)的高性能、可伸縮性和可用性。

一、分布式協(xié)議的相關(guān)問(wèn)題

通過(guò)分布式協(xié)議，自治的且松耦合的機(jī)器能夠共同決定如何控制基本行為，包括對(duì)共享內(nèi)存的訪問(wèn)順序。這些協(xié)議在分布式計(jì)算中被廣泛引用，一些著名的技術(shù)包括paxos和兩階段提交(2PC)協(xié)議等等。

?1、高昂的協(xié)調(diào)成本

不幸的是，分布式協(xié)議的成本可能使它們難以最終落地實(shí)施。分布式系統(tǒng)高伸縮性的第一個(gè)原則可能就是將一致性機(jī)制降到最低，并移出關(guān)鍵路徑，或者將其隱藏在系統(tǒng)很少訪問(wèn)的角落，然后讓應(yīng)用程序開(kāi)發(fā)人員難以獲得使用它們的許可。

實(shí)際上，問(wèn)題不在于分布式協(xié)議難以實(shí)施，而是因?yàn)榉植际絽f(xié)議可以減緩或停止分布式服務(wù)中的計(jì)算。這些協(xié)議的延遲很高，大約為10ms-100ms。依賴于這些協(xié)議的大規(guī)模系統(tǒng)并不意味著要在應(yīng)用程序的快速路徑中使用。另外，分布式協(xié)議的延遲問(wèn)題也會(huì)轉(zhuǎn)化為微觀層面的問(wèn)題，多服務(wù)器的鍵值存儲(chǔ)可能在花費(fèi)90% 的時(shí)間在等待協(xié)調(diào)。

2、程序一致性

傳統(tǒng)的一致性研究主要集中在線性度和沖突序列化上，這些屬性通過(guò)限制沖突的內(nèi)存訪問(wèn)順序來(lái)保證內(nèi)存的一致性。這掩蓋了一個(gè)根本問(wèn)題，即是否需要協(xié)調(diào)來(lái)保持程序的一致性。從整體上解決這個(gè)問(wèn)題，是否從程序的語(yǔ)義上支持呢？

在現(xiàn)實(shí)中，十字路口的紅綠燈相對(duì)于分布式協(xié)議，但如果有了立交橋或者隧道就相當(dāng)于無(wú)需分布式協(xié)議就實(shí)現(xiàn)了目標(biāo)。其核心是，通過(guò)巧妙地控制進(jìn)入地圖上道路重疊的關(guān)鍵區(qū)域的順序，并不能找到更好的解決方案。解決方案是設(shè)計(jì)道路以避免對(duì)協(xié)調(diào)的需要。然而，并非所有的問(wèn)題都有這樣的解決方案。對(duì)于任何給定的計(jì)算問(wèn)題，如何知道它是否需要分布式協(xié)議以保持程序的一致性呢？

3、死鎖檢測(cè)

在傳統(tǒng)的數(shù)據(jù)庫(kù)系統(tǒng)中，死鎖檢測(cè)器通過(guò)分析一個(gè)有向圖來(lái)識(shí)別這樣的“等待”周期，在有向圖中，節(jié)點(diǎn)表示事務(wù)，而邊表示一個(gè)事務(wù)在鎖隊(duì)列上等待另一個(gè)事務(wù)。死鎖是一個(gè)穩(wěn)定的屬性是：等待周期中的事務(wù)無(wú)法取得進(jìn)展，因此所有的邊都將無(wú)限期地持續(xù)下去。

在分布式數(shù)據(jù)庫(kù)的有向圖中，等待圖的“本地”視圖只包含全局等待圖中邊的一個(gè)子集。在這種情況下，本地死鎖檢測(cè)器如何協(xié)同工作來(lái)識(shí)別全局死鎖呢？為了識(shí)別這種分布式死鎖，每臺(tái)計(jì)算機(jī)與其他計(jì)算機(jī)交換其邊的副本，以積累有關(guān)全局有向圖的更多信息。任何時(shí)候，一臺(tái)機(jī)器在接收到的信息中觀察到一個(gè)循環(huán)，它就可以在該循環(huán)上的事務(wù)中聲明一個(gè)死鎖。

在這種分布式計(jì)算中，可能會(huì)擔(dān)心由于延遲或重新排序的消息而導(dǎo)致的暫時(shí)性錯(cuò)誤。本地檢測(cè)器是否必須與其他機(jī)器協(xié)調(diào)以確保觀測(cè)到是死鎖呢？額外的事實(shí)只能導(dǎo)致檢測(cè)額外的周期: 每臺(tái)機(jī)器的輸出隨著輸入單調(diào)增長(zhǎng)。最后，如果所有的邊最終在所有機(jī)器之間共享，那么機(jī)器就會(huì)同意基于完整圖形的結(jié)果。

4、垃圾收集

分布式系統(tǒng)中的垃圾收集器必須在分布式內(nèi)存引用圖中標(biāo)識(shí)不可到達(dá)的對(duì)象。垃圾收集的工作方式是識(shí)別與系統(tǒng)運(yùn)行時(shí)的“根”斷開(kāi)連接的組件。一旦圖中組件與根的連接被刪除，該組件中的對(duì)象將不會(huì)被重新引用。

在分布式系統(tǒng)中，對(duì)對(duì)象的引用可以跨越機(jī)器，參考圖的局部視圖只包含全局圖中邊的一個(gè)子集，多個(gè)本地垃圾收集器如何協(xié)同工作來(lái)識(shí)別真正不可訪問(wèn)的對(duì)象呢？機(jī)器可能有一個(gè)本地對(duì)象，但不知道該對(duì)象是否連接到根，同樣，每臺(tái)機(jī)器與其他機(jī)器交換圖中邊的副本，以積累關(guān)于圖的更多信息。

本地收集器能夠自主地判斷并回收垃圾嗎？在這里確實(shí)需要分布式協(xié)議來(lái)協(xié)調(diào)的！機(jī)器必須在聲明一個(gè)對(duì)象不可訪問(wèn)之前，確保它已經(jīng)聽(tīng)到了所有需要聽(tīng)到的內(nèi)容。要知道它已經(jīng)聽(tīng)到了所有的聲音，唯一的方法是與所有其他機(jī)器協(xié)商，以確定這一事實(shí)。協(xié)商的一個(gè)標(biāo)志是即使在沒(méi)有數(shù)據(jù)依賴關(guān)系的情況下也需要進(jìn)行通信。

二、一致性問(wèn)題的核心抽象

如果存在一個(gè)分布式系統(tǒng) ，程序不需要協(xié)商就可以計(jì)算出一致的輸出，那么這個(gè)計(jì)算問(wèn)題就是無(wú)協(xié)調(diào)的，無(wú)需使用分布式協(xié)議來(lái)實(shí)現(xiàn)一致性。那么，無(wú)需協(xié)調(diào)的邊界是什么呢？

分布式協(xié)議的使用和內(nèi)在需求之間是有區(qū)別的，前者是實(shí)現(xiàn)選擇的結(jié)果，后者是計(jì)算問(wèn)題的屬性。因此，希望關(guān)注程序一致性： 盡管可能出現(xiàn)消息和計(jì)算之間的競(jìng)爭(zhēng)條件，但實(shí)現(xiàn)是否產(chǎn)生期望的結(jié)果呢 ？

那么，一致性問(wèn)題的核心可否是程序的邏輯單調(diào)性呢？簡(jiǎn)單的說(shuō)，當(dāng)且僅當(dāng)一個(gè)問(wèn)題具有邏輯單調(diào)性，才具有一致的、無(wú)協(xié)調(diào)的分布式實(shí)現(xiàn)。相比之下，非單調(diào)性問(wèn)題是在所有的信息已經(jīng)到達(dá)之前，不能繼續(xù)運(yùn)行，這時(shí)必須通過(guò)分布式協(xié)議實(shí)現(xiàn)一致性。或者說(shuō)，具有邏輯單調(diào)性的問(wèn)題，其輸出只取決于輸入的內(nèi)容，而不取決于輸入到達(dá)的順序。

1、程序的一致性

分布式系統(tǒng)給程序帶來(lái)了顯著的非確定性，包括不同步的并行性、不可靠的組件和具有不可預(yù)知延遲的網(wǎng)絡(luò)。因此，一個(gè)分布式程序可以在給定的輸入上展示大量可能的行為。

在非確定性消息傳遞的場(chǎng)景中，如果單臺(tái)機(jī)器上的一個(gè)操作對(duì)任何非確定性排序和一組輸入請(qǐng)求產(chǎn)生相同的輸出響應(yīng)集，則該操作是具有程序一致性。程序一致性可以應(yīng)用于單個(gè)操作、數(shù)據(jù)流中的組件，甚至是整個(gè)分布式程序。

與傳統(tǒng)的內(nèi)存一致性屬性(如可線性化)不同，程序一致性對(duì)近因概念(例如，讀并不保證返回最新發(fā)出的寫請(qǐng)求的結(jié)果)或操作順序(例如，寫并不保證在所有副本上以相同的順序應(yīng)用)沒(méi)有要求或承諾。如果應(yīng)用具有程序一致性，則在內(nèi)存或存儲(chǔ)級(jí)別上的任何此類異常都不會(huì)影響應(yīng)用程序的結(jié)果。

對(duì)于分布式系統(tǒng)來(lái)說(shuō)，程序一致性是一個(gè)強(qiáng)大而寬松的正確性標(biāo)準(zhǔn)。它排除了由于競(jìng)爭(zhēng)和不確定性而導(dǎo)致的應(yīng)用級(jí)不一致性，同時(shí)允許在實(shí)踐中防止代價(jià)高的不確定性排序操作的計(jì)時(shí)。例如，電商平臺(tái)的購(gòu)物車功能，客戶通過(guò) Web 瀏覽器請(qǐng)求在線購(gòu)物車中添加和刪除項(xiàng)，是一個(gè)邏輯單調(diào)性的過(guò)程，最終的購(gòu)物車內(nèi)容可以通過(guò)跨節(jié)點(diǎn)統(tǒng)一 Added 集、跨節(jié)點(diǎn)統(tǒng)一 Deleted 集并計(jì)算結(jié)果的集合差來(lái)確定。但是，付賬的流程不具備程序一致性。

2、二分布式系統(tǒng)的可計(jì)算性模型

分布式計(jì)算中的每個(gè)機(jī)器都支持一些計(jì)算的本地模型，跨機(jī)器的數(shù)據(jù)分區(qū)，以及機(jī)器隨時(shí)間進(jìn)行通信的能力，大約可以抽象為一個(gè)轉(zhuǎn)換器網(wǎng)絡(luò)。簡(jiǎn)單地說(shuō)，關(guān)系型轉(zhuǎn)換器是一個(gè)事件驅(qū)動(dòng)的服務(wù)器，內(nèi)存是關(guān)系數(shù)據(jù)庫(kù)，每個(gè)轉(zhuǎn)換器運(yùn)行一個(gè)順序事件的循環(huán)。

• 提取并處理一批無(wú)序的請(qǐng)求，以在本地關(guān)系中插入和刪除記錄，而請(qǐng)求可能來(lái)自其他機(jī)器或特殊的輸入關(guān)系。
• 查詢本地關(guān)系來(lái)計(jì)算應(yīng)該發(fā)送到某個(gè)地方，以便將處理的請(qǐng)求記錄。
• 將查詢結(jié)果作為要處理的請(qǐng)求發(fā)送到網(wǎng)絡(luò)中的相關(guān)機(jī)器，在事件循環(huán)的下一個(gè)迭代中被消化，結(jié)果也可以“發(fā)送”到一個(gè)特殊的輸出。

在這個(gè)計(jì)算模型中，每臺(tái)機(jī)器上的狀態(tài)通過(guò)記錄集(即關(guān)系)來(lái)表示，而消息則通過(guò)插入或從接收機(jī)器上的關(guān)系中刪除的記錄來(lái)表示。每臺(tái)計(jì)算機(jī)上的計(jì)算是通過(guò)事件循環(huán)每次迭代中對(duì)當(dāng)前局部關(guān)系的邏輯查詢來(lái)指定的。

3、邏輯單調(diào)性

經(jīng)典的數(shù)據(jù)庫(kù)查詢語(yǔ)言包括關(guān)系演算和代數(shù)、 SQL、數(shù)據(jù)模型都是基于一階邏輯的，大多數(shù)常見(jiàn)的表達(dá)式是單調(diào)的，而語(yǔ)法則揭示了潛在的非單調(diào)表達(dá)式。因此，具有邏輯單調(diào)性的程序是符合轉(zhuǎn)化器的網(wǎng)絡(luò)，其中每臺(tái)機(jī)器的查詢只使用單調(diào)語(yǔ)法。

有了一個(gè)計(jì)算模型 ，以及程序一致性和邏輯單調(diào)性的定義，在單調(diào)的關(guān)系轉(zhuǎn)化器網(wǎng)絡(luò)中，很容易表明任何機(jī)器最終將攝取并發(fā)送一組確定性的消息并生成確定性的輸出。在執(zhí)行期間的任何時(shí)候，任何機(jī)器輸出的消息都構(gòu)成最終輸出的有效子集。

直觀地看，數(shù)據(jù)流消息是那些組裝其組件不在同一位置的數(shù)據(jù)的消息。為了隔離協(xié)調(diào)消息，在程序啟動(dòng)時(shí)將網(wǎng)絡(luò)中的機(jī)器之間的數(shù)據(jù)進(jìn)行分區(qū)。在程序的執(zhí)行過(guò)程中，每一個(gè)起始點(diǎn)都會(huì)產(chǎn)生一個(gè)消息模式。如果一個(gè)程序需要在所有可能的分區(qū)下發(fā)送消息，那么它就包含協(xié)調(diào)。在每個(gè)分區(qū)中發(fā)送的消息與數(shù)據(jù)流無(wú)關(guān); 它是一個(gè)協(xié)調(diào)消息。

單調(diào)性問(wèn)題不僅是無(wú)需協(xié)調(diào)問(wèn)題，而且是那些不需要網(wǎng)絡(luò)成員知識(shí)的問(wèn)題。

三、現(xiàn)實(shí)中的一致性實(shí)現(xiàn)

Brewer 的 CAP 理論非正式地指出，一個(gè)系統(tǒng)只能表現(xiàn)出以下三個(gè)屬性中的兩個(gè): 一致性、可用性和分區(qū)容忍性。CAP 只有在我們假設(shè)有問(wèn)題的系統(tǒng)需要執(zhí)行程序時(shí)才有效，并沒(méi)有指出是否有特定的程序可以同時(shí)具有這三個(gè)屬性！

如果分布式系統(tǒng)滿足程序一致性，對(duì)屬于邏輯單調(diào)性的問(wèn)題實(shí)際上可以同時(shí)滿足 CAP 的三個(gè)性質(zhì)，而非單調(diào)問(wèn)題則不能。

傳統(tǒng)編程語(yǔ)言將世界建模為一組命名變量，它們的值隨時(shí)間而變化，賦值使最終程序狀態(tài)依賴于輸入的到達(dá)順序。函數(shù)式編程長(zhǎng)期以來(lái)一直提倡使用不可變變量，這些變量在計(jì)算過(guò)程中被限制只能取一個(gè)值。一個(gè)不可變變量是一個(gè)簡(jiǎn)單的單調(diào)模式，不可變變量泛化為不可變的數(shù)據(jù)結(jié)構(gòu)，使得不可變樹、列表和圖的編程更加實(shí)用。基于單調(diào)邏輯的編程模式在分布式存儲(chǔ)系統(tǒng)的設(shè)計(jì)中很常見(jiàn)。

CRDT為基于單調(diào)邏輯的編程模式提供了一個(gè)面向?qū)ο蟮目蚣埽ǔＳ糜跔顟B(tài)復(fù)制的場(chǎng)景。CRDT 是一種抽象的數(shù)據(jù)類型，其可能的內(nèi)部狀態(tài)構(gòu)成一個(gè)網(wǎng)格，并根據(jù)網(wǎng)格的相關(guān)偏序單調(diào)地演化。CRDT以一種面向?qū)ο蟮囊暯?，利用交換性實(shí)現(xiàn)了并發(fā)性下的確定性。這可以追溯到在 Linux 內(nèi)核上的工作，crt 的一個(gè)問(wèn)題是它們的保證只適用于單個(gè)對(duì)象。交換性的好處已經(jīng)擴(kuò)展到可組合的庫(kù)和編程語(yǔ)言，局部的、以狀態(tài)為中心的保證可以被驗(yàn)證并自動(dòng)組成全局的、面向結(jié)果的、程序級(jí)的保證。

對(duì)于非單調(diào)邏輯的問(wèn)題必然需要分布式系統(tǒng)中的各組件協(xié)調(diào)，需要通過(guò)分布式協(xié)議來(lái)實(shí)現(xiàn)，將分布式協(xié)議從關(guān)鍵路徑轉(zhuǎn)移到后臺(tái)任務(wù)需要一定的編程能力和創(chuàng)造力。簡(jiǎn)而言之，基于單調(diào)邏輯性的編程不是構(gòu)建高效分布式系統(tǒng)的唯一途徑，但作為識(shí)別不確定性的分析框架很有用，這樣我們就可以創(chuàng)造性地處理分布式系統(tǒng)的一致性問(wèn)題。

四、小結(jié)

CAP 定理確定了在一般分布式系統(tǒng)中不可能實(shí)現(xiàn)的事情。實(shí)際上，我們需要明確那些可以實(shí)現(xiàn)的東西，以及如何在最小化復(fù)雜性和成本的同時(shí)實(shí)現(xiàn)分布式系統(tǒng)的一致性。

如果一個(gè)問(wèn)題是單調(diào)的，那么它就無(wú)需通過(guò)分布式協(xié)議的協(xié)商來(lái)保證一致性。任何非單調(diào)問(wèn)題的程序都需要運(yùn)行時(shí)強(qiáng)制協(xié)調(diào)以確保結(jié)果的一致性。?