從2PC和容錯共識算法讨論zookeeper中的Create請求

最近在讀《資料密集型應用系統設計》，其中談到了zookeeper對容錯共識算法的應用。這讓我想到之前參考的zookeeper學習資料中，誤将容錯共識算法寫成了2PC（兩階段送出協定），是以準備以此文對共識算法和2PC做梳理和區分，也希望它能幫助像我一樣對這兩者有誤解的同學。

1. 2PC（兩階段送出協定）

兩階段送出 (two-phase commit) 協定是一種用于實作 跨多個節點的原子事務（分布式事務）送出 的算法。它能確定所有節點送出或所有節點中止，并在某些資料庫内部使用，也以 XA事務 的形式在分布式服務中使用。

在 Java EE 中，XA事務使用 JTA(Java Transaction API) 實作。

2PC的實作

2PC包含 準備階段 和 送出階段 兩個階段，需要借助 協調者（事務管理器，如阿裡巴巴的Seata） 來實作，參與分布式事務的資料庫節點為 參與者。當分布式服務中的節點準備送出時，協調者開始 準備階段：發送一個 準備請求 到每個節點，詢問它們是否能夠送出，然後協調者會跟蹤參與者的響應

• 如果所有參與者都回答"是"，表示它們已經準備好送出，那麼協調者在 送出階段 發出 送出請求，分布式事務送出
• 如果任意一個參與者回答"否"，則協調者在 送出階段 中向所有節點發送 中止請求，分布式事務復原

上圖是2PC送出成功的情況，我們來詳述下過程：

1. 當服務啟動一個分布式事務時，它會向協調者請求一個事務ID，此事務ID是全局唯一的
2. 在每個參與者上啟動單節點事務，每個單節點事務會持有這個全局事務 ID。所有的讀寫都是在這些單節點事務中各自完成的。如果在這個階段出現任何問題（節點崩潰或請求逾時），則協調者或任何參與者都可以中止
3. 當應用準備送出時，對應準備階段：協調者向所有參與者發送一個 準備請求，同樣也持有全局事務 ID 。如果任意一個請求失敗或逾時，則協調者向所有參與者發送針對該事務 ID 的 中止請求，即2PC送出中止的情況
4. 參與者收到 準備請求 時，需要確定在任意情況下都可以送出事務。這包括将所有事務資料寫入磁盤（出現故障，電源故障，或硬碟空間不足都不能是稍後拒絕送出的理由）以及檢查是否存在任何沖突或違反限制。通過向協調者回答 “是”，節點承諾這個事務一定可以不出差錯地送出。也就是說：參與者沒有實際送出，同時放棄了中止事務的權利
5. 當協調者收到所有 準備請求 的答複時，會就 送出或中止事務 作出明确的決定（隻有在 所有參與者 投贊成票的情況下才會送出），這裡對應送出階段。協調者必須把這個送出或中止事務的決定 寫到磁盤上的事務日志中，記錄為 送出點（commit point）。如果它随後崩潰，能通過送出點進行恢複
6. 一旦協調者的決定已經儲存在事務日志中，送出或中止請求會發送給所有參與者。如果這個請求失敗或逾時，協調者 必須永遠保持重試，直到成功為止，對于已經做出的決定，協調者不管需要多少次重試它都必須被執行

2PC協定中有兩個關鍵的 不歸路 需要注意：

• 一旦協調者做出決定，這一決定是不可撤銷的
• 參與者投票 “是” 時，它承諾它稍後肯定能夠送出（盡管協調者可能仍然選擇放棄），即使參與者在此期間崩潰，事務也需要在其恢複後送出，而且由于參與者投了贊成，它不能在恢複後拒絕送出

這些承諾保證了2PC的 原子性。

協調者失效的情況

如果 協調者失效 并且所有參與者都收到了準備請求并投了是，那麼參與者什麼都做不了隻能等待，而且這種情況 解決方案 是等待協調者恢複或資料庫管理者介入操作來送出或復原事務，當然如果在生産期間這需要承擔運維壓力。

是以，協調者在向參與者發送送出或中止請求 之前，将其送出或中止決定寫入磁盤上的事務日志（送出點）。這樣就能在協調者發生崩潰恢複後，通過讀取其事務日志來确定所有 存疑事務 的狀态，任何在協調者事務日志中沒有送出記錄的事務都會被終止。是以兩階段送出在第二階段（送出階段）存在阻塞等待協調者恢複的情況，是以兩階段送出又被稱為 阻塞原子送出協定。

番外：3PC

三階段送出協定也是應用在分布式事務送出中的算法，它的提出是為了解決兩階段送出協定中存在的阻塞問題。它分為 CanCommit階段、PreCommit階段 和 DoCommit階段，通過引入 參與者逾時判斷機制 來解決2PC中存在的參與者依賴協調者的送出請求而阻塞導緻的資源占用等問題。

上圖為在DoCommit階段，參與者判斷 DoCommit請求 逾時情況的流程圖，我們詳述下它的避免阻塞的流程

1. 服務在每個參與者上啟動單節點事務，當參與者準備送出時，對應CanCommit階段，協調者會向所有參與者發送 CanCommit請求，如果任意一個請求失敗或逾時，則協調者會向所有參與者發送針對該事務的 中止請求，執行事務復原
2. 當協調者收到所有CanCommit請求的答複時，如果全是“是”那麼則進入PreCommit階段，否則發送中止請求，執行事務復原
3. 進入PreCommit階段後，協調者會向所有參與者發送 PreCommit請求，同樣還是如果存在請求失敗或逾時，會發送中止請求執行事務復原
4. 協調者收到所有PreCommit請求的答複時，如果全是“是”那麼則進入DoCommit階段，否則發送中止請求，執行事務復原
5. 進入DoCommit階段後，協調者會向所有參與者發送 DoCommit請求，注意這裡，如果某個參與者沒有收到該請求，它預設認為協調者會發送送出請求，那麼便本地執行送出事務，進而避免阻塞

3PC雖然解決了2PC中存在的阻塞問題，但是也引入了新的問題：

• 如果協調者在DoCommit階段回複的是中止請求，那麼逾時節點自顧自地送出事務就會發生資料不一緻的情況
• 通訊次數增加和實作相對複雜

3PC使原子送出協定變成非阻塞的，但是3PC 假定網絡延遲和節點響應時間有限，在大多數具有無限網絡延遲和程序暫停的實際系統中，它 并不能保證原子性。非阻塞原子送出需要一個 完美的故障檢測器 來以可靠的機制判斷一個節點是否已經崩潰，而在無限延遲的網絡中，逾時并不是一種可靠的故障檢測機制，因為即使節點沒有崩潰也會因為網絡延遲而逾時，出于這個原因，2PC仍然被使用，盡管存在協調者故障的問題。

2. 容錯共識算法

容錯共識算法用于 節點間資料同步，保證各個副本間資料的一緻性和叢集的高可用。它的通常形式是一個或多個節點可以 提議（propose） 某些值，而共識算法 決定（decides） 采用其中的某個值，并讓這些節點就提議達成一緻。共識算法必須具備如下性質：

• 一緻同意：沒有兩個節點的決定不同
• 完整性：沒有節點決定兩次
• 有效性：如果節點決定了v值，那麼v由該節點所提議
• 終止性：由所有未崩潰的節點來最終決定值

終止性實質上是說：容錯共識算法不能簡單地永遠閑坐着等待，而是需要根據大多數節點來達成一項決定，是以終止屬性也暗含着 不超過一半的節點崩潰或不可達 的資訊。

一緻同意和完整性是共識的 核心思想，即所有節點決定了相同的結果并且決定後不能改變主意。

容錯共識算法在節點叢集内部都以某種形式使用一個上司者，并定義了一個 紀元編号（epoch number） 來確定在每個時代中，上司者都是唯一的。每當現任上司當機時，節點間會開始一場投票，來選出一個新的上司，每次選舉被賦予一個新的紀元編号（全序且單調遞增），如果有兩個不同時代的上司者之間出現沖突（腦裂問題），那麼帶有更高紀元編号的上司者說了算。上司者每想要做出的每一個決定，都必須将提議值發送給其他節點，并等待 法定人數 的節點響應并贊成提案。法定人數通常（但不總是）由多數節點組成（一般為過半），隻有在沒有發現任何帶有更高紀元編号的上司者的情況下，一個節點才會投票贊成提議。

容錯共識算法的局限性

1. 節點在做出決定之前對提議進行投票的過程是一種同步複制
2. 共識系統總是需要有 法定人數 的節點存活來保證運轉
3. 大多數共識算法假定參與投票的節點是固定的集合，這意味着你不能簡單的在叢集中添加或删除節點
4. 共識系統通常依靠 逾時 來檢測失效的節點，在網絡延遲高度變化的環境中，特别是在地理上散布的系統，經常發生一個節點由于暫時的網絡問題，錯誤地認為上司者已經失效。雖然這種錯誤不會損害安全屬性，但頻繁的上司者選舉會導緻糟糕的性能表現，是以共識算法對網絡問題比較敏感，而在面對不可靠的網絡相關的共識算法研究仍在進展中

3. 2PC和容錯共識算法的差別

1. 負責解決的問題不同：2PC解決的是分布式事務的一緻性，各個節點存儲的資料各有不同，目标側重于保證事務的ACID；容錯共識算法解決的是節點副本間資料的一緻性和保證叢集的高可用，節點間存儲的資料完全一緻，目标側重于資料的複制和同步
2. 每個提議通過要求的參與節點數不同：2PC要求 所有的參與者表決成功 才通過；容錯共識算法隻需要 遵循基于法定人數的表決 即可，這也是容錯共識算法 終止屬性（由所有未崩潰的節點來決定最終值） 的展現
3. 叢集的高可用保證：2PC的協調者不是通過選舉産生的，而是單獨部署并人為指定的元件，是以它沒有選主機制，不具備高可用性；應用容錯共識算法的叢集上司者是通過選舉機制來指定的，并且在發生異常情況時（主節點當機）能夠選出新的上司者，并進入一緻的狀态，以此來保證叢集的高可用

4. zookeeper中的一次Create請求

一些資料中會提到zookeeper在執行CRUD請求時，使用的是2PC，而 實際上它使用的是容錯共識算法。我們以Create請求的流程為例（如下圖），來加深和記憶這一知識

1. 用戶端發 create 請求到 Leader，即使請求沒落到 Leader 上，那麼其他節點也會将寫請求轉發到 Leader
2. Leader 會先發一個 提議（proposal）請求給各個 Follower，且自己将資料寫到本地檔案
3. Follower 叢集收到 proposal 請求後會将資料寫到本地檔案，寫成功後傳回給 Leader 一個 ack回複
4. Leader 發現收到 ack 回複的數量為 法定人數（過半，包含目前 Leader 節點）時，則送出一個 commit 請求給各個 Follower 節點。發送 commit 請求就代表該資料在叢集内同步情況沒有問題，并且 可以對外提供通路 了，此時Leader會把資料寫到記憶體中
5. Follower 收到 commit 請求後也會将資料寫到各自節點的記憶體中，同時Leader會将資料發給 Observer叢集，通知 Observer叢集 将資料寫到記憶體

作者：方圓想當圖靈

連結：https://juejin.cn/post/7244085299835715645