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

構建正確的分布式系統并不新鮮，一個傳統的解決辦法是通過保證內存一致性來降低這種復雜性，即確保以受控的方式訪問內存(堆變量、數據庫等)。然而，用于實施這些機制的分布式協議卻通常阻礙了分布式系統的高性能、可伸縮性和可用性。

一、分布式協議的相關問題

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

?1、高昂的協調成本

不幸的是，分布式協議的成本可能使它們難以最終落地實施。分布式系統高伸縮性的第一個原則可能就是將一致性機制降到最低，并移出關鍵路徑，或者將其隱藏在系統很少訪問的角落，然后讓應用程序開發人員難以獲得使用它們的許可。

實際上，問題不在于分布式協議難以實施，而是因為分布式協議可以減緩或停止分布式服務中的計算。這些協議的延遲很高，大約為10ms-100ms。依賴于這些協議的大規模系統并不意味著要在應用程序的快速路徑中使用。另外，分布式協議的延遲問題也會轉化為微觀層面的問題，多服務器的鍵值存儲可能在花費90% 的時間在等待協調。

2、程序一致性

傳統的一致性研究主要集中在線性度和沖突序列化上，這些屬性通過限制沖突的內存訪問順序來保證內存的一致性。這掩蓋了一個根本問題，即是否需要協調來保持程序的一致性。從整體上解決這個問題，是否從程序的語義上支持呢？

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

3、死鎖檢測

在傳統的數據庫系統中，死鎖檢測器通過分析一個有向圖來識別這樣的“等待”周期，在有向圖中，節點表示事務，而邊表示一個事務在鎖隊列上等待另一個事務。死鎖是一個穩定的屬性是：等待周期中的事務無法取得進展，因此所有的邊都將無限期地持續下去。

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

在這種分布式計算中，可能會擔心由于延遲或重新排序的消息而導致的暫時性錯誤。本地檢測器是否必須與其他機器協調以確保觀測到是死鎖呢？額外的事實只能導致檢測額外的周期: 每臺機器的輸出隨著輸入單調增長。最后，如果所有的邊最終在所有機器之間共享，那么機器就會同意基于完整圖形的結果。

4、垃圾收集

分布式系統中的垃圾收集器必須在分布式內存引用圖中標識不可到達的對象。垃圾收集的工作方式是識別與系統運行時的“根”斷開連接的組件。一旦圖中組件與根的連接被刪除，該組件中的對象將不會被重新引用。

在分布式系統中，對對象的引用可以跨越機器，參考圖的局部視圖只包含全局圖中邊的一個子集，多個本地垃圾收集器如何協同工作來識別真正不可訪問的對象呢？機器可能有一個本地對象，但不知道該對象是否連接到根，同樣，每臺機器與其他機器交換圖中邊的副本，以積累關于圖的更多信息。

本地收集器能夠自主地判斷并回收垃圾嗎？在這里確實需要分布式協議來協調的！機器必須在聲明一個對象不可訪問之前，確保它已經聽到了所有需要聽到的內容。要知道它已經聽到了所有的聲音，唯一的方法是與所有其他機器協商，以確定這一事實。協商的一個標志是即使在沒有數據依賴關系的情況下也需要進行通信。

二、一致性問題的核心抽象

如果存在一個分布式系統 ，程序不需要協商就可以計算出一致的輸出，那么這個計算問題就是無協調的，無需使用分布式協議來實現一致性。那么，無需協調的邊界是什么呢？

分布式協議的使用和內在需求之間是有區別的，前者是實現選擇的結果，后者是計算問題的屬性。因此，希望關注程序一致性： 盡管可能出現消息和計算之間的競爭條件，但實現是否產生期望的結果呢 ？

那么，一致性問題的核心可否是程序的邏輯單調性呢？簡單的說，當且僅當一個問題具有邏輯單調性，才具有一致的、無協調的分布式實現。相比之下，非單調性問題是在所有的信息已經到達之前，不能繼續運行，這時必須通過分布式協議實現一致性。或者說，具有邏輯單調性的問題，其輸出只取決于輸入的內容，而不取決于輸入到達的順序。

1、程序的一致性

分布式系統給程序帶來了顯著的非確定性，包括不同步的并行性、不可靠的組件和具有不可預知延遲的網絡。因此，一個分布式程序可以在給定的輸入上展示大量可能的行為。

在非確定性消息傳遞的場景中，如果單臺機器上的一個操作對任何非確定性排序和一組輸入請求產生相同的輸出響應集，則該操作是具有程序一致性。程序一致性可以應用于單個操作、數據流中的組件，甚至是整個分布式程序。

與傳統的內存一致性屬性(如可線性化)不同，程序一致性對近因概念(例如，讀并不保證返回最新發出的寫請求的結果)或操作順序(例如，寫并不保證在所有副本上以相同的順序應用)沒有要求或承諾。如果應用具有程序一致性，則在內存或存儲級別上的任何此類異常都不會影響應用程序的結果。

對于分布式系統來說，程序一致性是一個強大而寬松的正確性標準。它排除了由于競爭和不確定性而導致的應用級不一致性，同時允許在實踐中防止代價高的不確定性排序操作的計時。例如，電商平臺的購物車功能，客戶通過 Web 瀏覽器請求在線購物車中添加和刪除項，是一個邏輯單調性的過程，最終的購物車內容可以通過跨節點統一 Added 集、跨節點統一 Deleted 集并計算結果的集合差來確定。但是，付賬的流程不具備程序一致性。

2、二分布式系統的可計算性模型

分布式計算中的每個機器都支持一些計算的本地模型，跨機器的數據分區，以及機器隨時間進行通信的能力，大約可以抽象為一個轉換器網絡。簡單地說，關系型轉換器是一個事件驅動的服務器，內存是關系數據庫，每個轉換器運行一個順序事件的循環。

• 提取并處理一批無序的請求，以在本地關系中插入和刪除記錄，而請求可能來自其他機器或特殊的輸入關系。
• 查詢本地關系來計算應該發送到某個地方，以便將處理的請求記錄。
• 將查詢結果作為要處理的請求發送到網絡中的相關機器，在事件循環的下一個迭代中被消化，結果也可以“發送”到一個特殊的輸出。

在這個計算模型中，每臺機器上的狀態通過記錄集(即關系)來表示，而消息則通過插入或從接收機器上的關系中刪除的記錄來表示。每臺計算機上的計算是通過事件循環每次迭代中對當前局部關系的邏輯查詢來指定的。

3、邏輯單調性

經典的數據庫查詢語言包括關系演算和代數、 SQL、數據模型都是基于一階邏輯的，大多數常見的表達式是單調的，而語法則揭示了潛在的非單調表達式。因此，具有邏輯單調性的程序是符合轉化器的網絡，其中每臺機器的查詢只使用單調語法。

有了一個計算模型 ，以及程序一致性和邏輯單調性的定義，在單調的關系轉化器網絡中，很容易表明任何機器最終將攝取并發送一組確定性的消息并生成確定性的輸出。在執行期間的任何時候，任何機器輸出的消息都構成最終輸出的有效子集。

直觀地看，數據流消息是那些組裝其組件不在同一位置的數據的消息。為了隔離協調消息，在程序啟動時將網絡中的機器之間的數據進行分區。在程序的執行過程中，每一個起始點都會產生一個消息模式。如果一個程序需要在所有可能的分區下發送消息，那么它就包含協調。在每個分區中發送的消息與數據流無關; 它是一個協調消息。

單調性問題不僅是無需協調問題，而且是那些不需要網絡成員知識的問題。

三、現實中的一致性實現

Brewer 的 CAP 理論非正式地指出，一個系統只能表現出以下三個屬性中的兩個: 一致性、可用性和分區容忍性。CAP 只有在我們假設有問題的系統需要執行程序時才有效，并沒有指出是否有特定的程序可以同時具有這三個屬性！

如果分布式系統滿足程序一致性，對屬于邏輯單調性的問題實際上可以同時滿足 CAP 的三個性質，而非單調問題則不能。

傳統編程語言將世界建模為一組命名變量，它們的值隨時間而變化，賦值使最終程序狀態依賴于輸入的到達順序。函數式編程長期以來一直提倡使用不可變變量，這些變量在計算過程中被限制只能取一個值。一個不可變變量是一個簡單的單調模式，不可變變量泛化為不可變的數據結構，使得不可變樹、列表和圖的編程更加實用。基于單調邏輯的編程模式在分布式存儲系統的設計中很常見。

CRDT為基于單調邏輯的編程模式提供了一個面向對象的框架，通常用于狀態復制的場景。CRDT 是一種抽象的數據類型，其可能的內部狀態構成一個網格，并根據網格的相關偏序單調地演化。CRDT以一種面向對象的視角，利用交換性實現了并發性下的確定性。這可以追溯到在 Linux 內核上的工作，crt 的一個問題是它們的保證只適用于單個對象。交換性的好處已經擴展到可組合的庫和編程語言，局部的、以狀態為中心的保證可以被驗證并自動組成全局的、面向結果的、程序級的保證。

對于非單調邏輯的問題必然需要分布式系統中的各組件協調，需要通過分布式協議來實現，將分布式協議從關鍵路徑轉移到后臺任務需要一定的編程能力和創造力。簡而言之，基于單調邏輯性的編程不是構建高效分布式系統的唯一途徑，但作為識別不確定性的分析框架很有用，這樣我們就可以創造性地處理分布式系統的一致性問題。

四、小結

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

如果一個問題是單調的，那么它就無需通過分布式協議的協商來保證一致性。任何非單調問題的程序都需要運行時強制協調以確保結果的一致性。?