上層應用的基石：分佈式協議

故障模式

故障發生和檢測的方式對於許多算法都很重要。以下是最常用的：

故障停止

故障停止意味着如果節點出現問題，每個人都能知道並檢測到它，並能從穩定的存儲中恢復狀態。這在理論和協議上都是簡單的模式，但在實踐中卻很難實現（在某些情況下甚至是不可能的）

崩潰故障

崩潰故障意味着，如果節點或代理出現問題，它就會崩潰，然後再也不會回來。你要麼永遠正確，要麼永遠遲到。這在理論上比故障停止更容易設計（但操作起來非常麻煩，因爲冗餘是遊戲的名字，永遠都是）。

遺漏故障

遺漏故障意味着你必須給出符合協議的正確結果，否則就永遠無法回答。

性能故障

性能故障則假定，在發送信息內容方面遵守協議的同時，也有可能延遲發送結果。

拜占庭式的失敗

拜占庭故障意味着任何事情都可能出錯（包括有人故意用壞軟件冒充好軟件來破壞協議）。有一類特殊的可檢測認證的拜占庭故障，它至少會限制你不能僞造來自其他節點的其他信息，但這只是可選項。拜占庭模式是最糟糕的。

常見的實際故障模式

在實踐中，當你從計算機科學轉向工程學時，你會發現故障類型更加多樣化，但也可以映射到任何理論模型。

1、網絡分裂

有些節點可以互相通話，但有些節點卻無法與其他節點聯繫。一個常見的例子是，基於美國的網絡可以在內部正常通信，基於歐盟的網絡也可以，但兩者都無法互相通話

2、非對稱網絡分裂

節點組之間的通信是不對稱的。例如，假設美國網絡可以向歐盟網絡發送信息，但歐盟網絡卻無法作出迴應。這種情況在使用 TCP 時比較少見（儘管以前也發生過），而在使用 UDP 時則可能很常見。

3、腦裂

許多系統處理故障的方法是保持多數系統繼續運行。當網絡分裂的雙方都認爲自己是領導者，並開始做出相互衝突的決定時，就會出現分裂腦。

4、超時

超時尤其棘手，因爲它們是非確定性的。它們只能從一端觀察到，而且你永遠不知道最終被解釋爲失敗的超時是否真的是失敗，或者只是由於網絡、硬件或 GC 暫停造成的延遲。有時，如果信息已被看到，重傳就不安全了（即它不是冪等的），而超時基本上使人無法知道重傳是否安全：信息是否已被執行、丟棄，還是仍在傳輸中或在某個緩衝區中？

5、排序導致的報文丟失

一般情況下，使用 TCP 和碰撞往往意味着很少有報文在系統間丟失，但經常出現的情況包括節點宕機（或軟件崩潰）幾秒鐘，在此期間錯過了一條不會重複的信息在不同節點之間臨時接收更新。例如，服務 A 在總線（無論是 Kafka 還是 RMQ）上發佈的消息最終可能被服務 B 讀取、轉換或執行並重新發布，而服務 C 有可能先於 A 讀取 B 的更新，從而造成因果關係問題。

6、時鐘漂移

並非所有系統上的所有時鐘都能正確同步（即使使用 NTP），而且同步速度也會不同。使用時間戳對事件進行排序幾乎肯定會產生錯誤，如果時間戳來自多臺計算機，錯誤就會更多。

7、客戶端是系統的一部分

一個非常常見的誤區是忘記了參與分佈式系統的客戶端也是系統的一部分。如果客戶端無法理解其接收到的事件或數據，服務器端的一致性就不一定有多大價值。對於數據庫客戶端來說，這一點尤其隱蔽，因爲它們在進行非瞬時事務處理時會超時，而且無法知道是否可以再次嘗試。

8、從多個備份恢復

單個備份很容易處理。多重備份會遇到一個問題，即一致切割（高級視圖）和分佈式快照，這意味着並非所有備份都是在同一時間進行的，這會帶來不一致性，可被視爲數據損壞。

如何解決故障和失敗

共識

這是分佈式系統的核心問題之一：系統中的所有節點或代理如何就一個值達成一致？它之所以如此重要，是因爲如果能就一個值達成一致，就能做很多事情。

選擇一個非常有用的值，最常見的例子就是選出一個執行決策的領導者的名字，這樣你就不用再建立更多的共識了，因爲共識太痛苦了。

關於什麼是共識，存在各種說法，包括每個人都完全同意？(強）還是隻是多數？(t-resilient），以及在各種同步或失敗模型中提出同樣的問題。

需要注意的是，雖然像 Paxos 這樣的經典協議會使用領導者來確保一致性，並在保持一致的同時加快執行速度，但很多系統都會放棄這些要求。

細節閱讀

CAP 定理

CAP 定理在很長一段時間內都只是一個猜想，但在 2000 年代初得到了證明，從而產生了許多最終一致的數據庫。

分佈式系統有三個特性：

從理論上講，你可以得到一個既可用又一致的系統，但這隻適用於完美網絡上的同步模型。這種情況並不存在，因此在實際應用中，P 總是存在的。

CAP 定理的基本原理是，在給定 P 的情況下，你必須選擇 A（繼續接受寫入並可能損壞數據）或 C（停止接受寫入以保存數據，並宕機）。

論文：

冪等性

冪等性非常重要，需要有自己的條目。閒置意味着，當信息被多次查看、重發或重放時，它們對系統的影響不會與只發送一次時有什麼不同。

常見的策略是讓每條信息都能引用以前看過的信息，這樣就可以定義一個排序來防止重播舊信息，設置唯一的 ID（如事務 ID）和一個存儲空間來防止重播事務，等等。

論文

狀態機複製

這是一個理論模型，根據該模型，如果給定相同的狀態序列並對其進行相同的操作（不考慮各種非確定性），所有狀態機最終都會得到相同的結果。這個模型對於大多數可靠的系統都至關重要，因爲這些系統都會嘗試以相同的順序向所有子系統重放所有事件，從而確保所有地方的數據集都是可預測的。這通常是通過選擇一個領導者來實現的；所有的寫入都通過領導者完成，所有的跟隨者都會得到系統的一致複製狀態，使他們最終成爲領導者，或將自己的狀態扇形擴展到其他參與者。基於狀態的複製在概念上可能比狀態機複製更簡單，其理念是，如果只複製狀態，最終就能得到狀態！問題是，要做到快速高效非常困難。如果你的狀態有幾兆兆字節那麼大，你可不想每次操作都要重新發送。常見的方法包括對數據進行拆分、散列和分塊，以檢測變化並只發送變化的部分（想想 rsync）；用梅克爾樹 merkle trees 來檢測變化；或者對源代碼打補丁。

信息傳遞定義

信息可以按不同順序發送零次或多次。下面介紹一些術語來定義它們：

順序控制

總排序是指所有信息只有一種嚴格的排序和比較方式，就像 3 總是大於 2 一樣。

部分排序意味着某些信息可以與某些信息進行比較，但不一定是所有信息。例如，我可以決定，對密鑰 k1 的所有更新可以相互之間有一個總順序，但獨立於對密鑰 k2 的更新。因此，在所有密鑰的所有更新之間存在部分順序，因爲 k1 的更新與 k2 的更新沒有任何信息關聯。

因果順序指的是，所有依賴於其他信息的信息都是在這些信息之後收到的（你不可能在瞭解一個用戶之前就知道他的頭像）。它是部分順序的一種特殊類型。

沒有 "最佳" 排序，每種排序都提供了不同的可能性，並伴隨着不同的成本、優化和相關故障模式。

一致性模型

有幾十種不同級別的一致性，維基百科、彼得 - 貝利斯（Peter Bailis）的相關論文或凱爾 - 金斯伯裏（Kyle Kingsbury）的相關文章都對它們進行了概述

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/ppgaeDyauqe2YInasnYTOA

猜你喜歡