分散式 transaction 和共識 (Distributed Transactions and Consensus)

共識是分散式計算中重要的基礎問題，目標是 讓所有節點一致同意某些事情，共識會用在這 2 種情形上面：

• Leader election

  在 single-leader 資料庫中，成為 leader 需要所有節點同意，如此就能在節點故障時，避免不好的 failover 發生（形成 split brain 情況）。

• Atomic commit

  若資料庫能支援多節點的 transaction，我們會就可能會面臨有些節點 commit 成功，有些節點 commit 失敗的情形，如果我們要維持 transaction 原子性 (Day 1)，勢必要讓所有節點同意 transaction 的結果才行，這個共識問題就是 atomic commit 問題。

首先要來介紹 二階段 commit (two-phase commit)，一個常用來解決 atomic commit 問題的共識演算法。

Atomic Commit and Two-Phase Commit (2PC)

從單一節點到分散式 atomic commit

ACID 的原子性 (Day 1)，能使資料庫避免一半成功的結果，這在多物件更新 (Day 2) 情況上尤為重要。

transaction 執行在單一資料庫節點上時，當使用者詢問資料庫是他們想 commit transaction，資料庫為了讓 transaction 更有耐用性，它會先預寫 log 到硬碟上，然後再寫入 commit 記錄到硬碟上，如果資料庫在過程中故障，transaction 就能在節點重啟時從 log 中恢復狀態。

因此，單一資料庫節點的 transaction commit 的關鍵是依賴在資料寫入硬碟的順序上，若 commit 記錄在故障前成功寫入到硬碟上，就可視為成功 commit ，在此之前，transaction 都有機會中止。

那麼，多節點怎麼辦呢？因為原子性的關係，我們無法只發送 commit 訊息到各節點上就好了（因為有些可能失敗），所以要透過某種機制協調 & 強制的讓所有節點都 commit 成功。

二階段 commit (two-phase commit)

二階段 commit 是一個實現多節點原子 transaction commit 的算法，能確保所有節點都 commit 或 中止 transaction，二階段 commit 的基礎流程如下圖 9-9，讓 commit 的過程拆分成二階段，且多了一個新的元件角色：協調者 (coordinator)。

二階段 commit 跟 Day 6 的二階段鎖不一樣喔，別搞混了。

協調者的工作就是在階段 1 發生 prepare request 給所有的節點（也稱為參與者）問它們是否準備好要 commit 了沒，依據節點們的回答，階段 2 會有兩個不同任務：

• 當所有的參與者都回 yes ，協調者就會發送 commit request 給所有節點。
• 若有任一節點回 no，協調者就會發送 abort request 給所有節點。

承諾制度 (A system of promises)

因為 Day 8 ~ Day 13 講過的鬼故事，prepare 或 commit request 都有機會遺失，所以接下來就來細看 二階段 commit 究竟為什麼可以做到所有節點同意某種結果。

1. 當應用系統開始一個分散式 transaction 時，它會從協調者要求一個唯一的 transaction ID。
2. 每一個參與者節點都使用該 transaction ID 開始一個 transaction，所有讀取跟寫入都在該單一節點上完成，若在此階段有任何錯誤發生，協調者或任一參與者都能中止 (abort)。
3. 當應用系統準備要 commit，協調者發送 prepare request 到每一個參與者中，並標註該 transaction ID，若有任何 request 失敗或 timeout，協調者就發送 abort request 到所有參與者中。
4. 當參與者節點接收 prepare request ，它要做好是否能 commit 的確認，包含寫入 transaction 資料到硬碟、檢查資料是否有衝突或違反限制；當它回覆 yes 給協調者，代表參與者放棄中止 transaction 的權利，但還沒實際 commit。
5. 當協調者接收到所有參與者的回覆，協調者能做 commit 或 abort 的決定，協調者必須把它的決定寫到 transaction log 裡（當故障時可知道自己的決定是什麼），這稱為 commit point。
6. 一旦協調者的決定寫入到硬碟上了，相對應的 request 就會發生給所有參與者，如果 request 失敗或 timeout，協調者會 一直重試 直到成功，這也意味者沒有回頭路了；如果參與者在此時故障，該 transaction 也會在節點恢復時 commit。

因此，這個協定包含 2 個無法回頭的關鍵點：

• 當參與者投給 yes，它就是保證它之後一定能 commit （雖然協調者可能選擇 abort）。
• 一旦協調者做決定了，這決定不可撤回。

這些承諾確保了 二階段 commit 的原子性。

協調者故障

如果協調者在發送 prepare request 前故障，參與者可以安全的中止 transaction，但是一旦參與者接收到了 prepare request 共投了 yes，它就不能單方面中止，它必須等待協調者給它 commit 或 abort 的訊息，如果協調者故障或網路延遲，該參與者什麼也不能做，只能等待，這個狀態的參與者稱為 in doubt 或 uncertain。

這個情況如下圖 9-10，協調者決定 commit 並成功發送 commit request 給 Database 2， 但在發送給 Database 1 前故障了，所以 Database 1 不知道發生什麼狀況只能等待。

原則上，參與者節點可以跟其他參與者節點互相溝通問結果，但那不在 二階段 commit 協定的範疇。

這唯一的解決方法就是協調者節點要恢復，所以協調者才會寫它的決定在 transaction log 中，以防從故障中恢復並檢測所有在 in-dobut 的參與者節點，當協調者節點恢復時，協調者 log 中所有沒有 commit 記錄的 transaction 將會中止，所以，2PC 的 commit point 可被歸在常規的協調者單一節點上 atomic commit 。