分散式 transaction 和共識 (Distributed Transactions and Consensus)
共識是分散式計算中重要的基礎問題，目標是 讓所有節點一致同意某些事情，共識會用在這 2 種情形上面：
- Leader election 在 single-leader 資料庫中，成為 leader 需要所有節點同意，如此就能在節點故障時，避免不好的 failover 發生（形成 split brain 情況）。
- Atomic commit 若資料庫能支援多節點的 transaction，我們會就可能會面臨有些節點 commit 成功，有些節點 commit 失敗的情形，如果我們要維持 transaction 原子性，勢必要讓所有節點同意 transaction 的結果才行，這個共識問題就是 atomic commit 問題。
首先要來介紹 二階段 commit (two-phase commit)，一個常用來解決 atomic commit 問題的共識演算法。
Atomic Commit and Two-Phase Commit (2PC)
從單一節點到分散式 atomic commit
ACID 的原子性，能使資料庫避免一半成功的結果，這在 多物件更新 情況上尤為重要。
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 跟 Serializability Isolation 的二階段鎖不一樣喔，別搞混了。
協調者的工作就是在階段 1 發生 prepare request 給所有的節點（也稱為參與者）問它們是否準備好要 commit 了沒，依據節點們的回答，階段 2 會有兩個不同任務：
- 當所有的參與者都回 yes ，協調者就會發送 commit request 給所有節點。
- 若有任一節點回 no，協調者就會發送 abort request 給所有節點。
承諾制度 (A system of promises)
誠如之前講過的 分散式系統鬼故事，prepare 或 commit request 都有機會遺失，所以接下來就來細看 二階段 commit 究竟為什麼可以做到所有節點同意某種結果。
- 當應用系統開始一個分散式 transaction 時，它會從協調者要求一個唯一的 transaction ID。
- 每一個參與者節點都使用該 transaction ID 開始一個 transaction，所有讀取跟寫入都在該單一節點上完成，若在此階段有任何錯誤發生，協調者或任一參與者都能中止 (abort)。
- 當應用系統準備要 commit，協調者發送 prepare request 到每一個參與者中，並標註該 transaction ID，若有任何 request 失敗或 timeout，協調者就發送 abort request 到所有參與者中。
- 當參與者節點接收 prepare request ，它要做好是否能 commit 的確認，包含寫入 transaction 資料到硬碟、檢查資料是否有衝突或違反限制；當它回覆 yes 給協調者，代表參與者放棄中止 transaction 的權利，但還沒實際 commit。
- 當協調者接收到所有參與者的回覆，協調者能做 commit 或 abort 的決定，協調者必須把它的決定寫到 transaction log 裡（當故障時可知道自己的決定是什麼），這稱為 commit point。
- 一旦協調者的決定寫入到硬碟上了，相對應的 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 。
Fault-Tolerant Consensus
共識問題通常可以公式化成：一個或多個節點可以提議，然後共識演算法從其提議中做決定。
舉個訂飛機座位的例子，當數個客戶同時訂購該班機的最後一個位子，每一個節點都接收到客戶的 request 了，算法就要決定哪個客戶能訂到座位。
所以一個共識算法必須安全的提供以下幾個屬性：
- 統一協議 (Uniform agreement) 沒有任二個節點有不同決定。
- 正當 (Integrity) 沒有節點決定 2 次。
- 有效 (Validity) 如果一個節點決定為 v，那麼 v 就某個節點的提議。
- 終止 (Termination) 每一個最終沒故障的節點都會決定一些東西出來。
統一協議 和 正當 屬性是共識算法中的核心；有效 屬性是為了避免做出無效的決定；而 終止 屬性則是為了系統容錯而存在，若有節點故障，其他節點必定也能做出決定，當然若所有節點故障，任何演算法都不能決定任何事情，因此，終止 屬性是假設在少於一半的節點故障或無法連接。
另外，今天講的共識演算法也是假設系統不會有之前討論過的 拜占庭錯誤 (Byzantine Faults)，因為它可能會破壞協定的安全屬性。
但實際上是有方法可解啦，看 李永樂老師 的說明影片就對了。
共識算法和全局順序廣播 (Consensus algorithms and total order broadcast)
已知好的容錯共識演算法有 Viewstamped Replication (VSR)、Paxos、Raft 和 Zab，它們之間並不完全一樣，今天我們只討論它們共通的 high-level 想法。
許多共識演算法實際上不直接用上一小節描述的定義，取而代之的是，它們決定一系列的值，使它們成為 全局順序廣播 (total order broadcast) 算法，全局順序廣播的訊息只被交付一次且在所有的節點順序相同，細想一下的話，這等同於執行數回合的共識，在每一回合中，節點提議它們想發送的下一條訊息，然後決定下一條要被新增至全局順序的訊息為何：
- 由於 統一協議 屬性，所有節點決定交付相同順序的訊息。
- 由於 正當 屬性，訊息不重複。
- 由於 有效 屬性，訊息不會被破壞，也不會憑空捏照。
- 由於 終止 屬性：訊息不會遺失。
Single-leader 數據複製和共識 (single-leader replication and consensus)
以前提過的 single-leader 類型 replication 資料庫，leader 負責所有的寫入，然後以相同的順序發給 follower 節點，這聽起來是不是很像全局順序廣播！？
那麼，為了避免 split brain 問題，我們需要共識算法，而共識算法等於全局順序廣播，而全局順序廣播又很像 single-leader 類型的 replication 資料庫，single-leader 又可能會發生 split brain 問題………
我們如何擺脫這個難題？
紀元號和法定人數 (Epoch numbering and quorums)
到目前為止所有討論過的共識協定都有在內部使用某種形式的 leader，但它們並不保證 leader 是唯一，相反地，它們提供一個較弱的保證：它定義了 紀元號 (epoch number)。
Paxos 稱為 ballot number，Viewstamped Replication 稱為 view number ，Raft 稱為 term number。
每次只要認為 leader 死亡時，演算法就會開始在節點中選出新的 leader，選出 leader 時會一起給一個逐步增加的紀元號，若有 2 個不同的 leader 衝突發生，則由有較大的紀元號的 leader 勝出。
在 leader 決定任何事情之前，它必須檢查有沒有其他 leader 有更大的紀元號，那麼領導者該怎麼知道它有沒有被趕走呢？它必須從 quorum (法定人數) 節點們收集投票，當 leader 要決定事情時，它需要發送它的提議給其他節點，然後看 quorum 節點們是否同意該提議，只有當節點 不知道 有更高紀元號的 leader 時，節點才會投票贊成提議。
所以這裡會有 2 回合的投票，一次是選 leader，第二次是投 leader 的提議，這裡有個重點是這 2 次的投票的 quorum 節點必須重疊：如果一個提議成功，則最少其中之一節點也必須參與在最近一次的 leader 選舉之中。
因此，如果提議的投票沒有透露出任一更高紀元號的 leader 時，當前的 leader 可以做出沒有更高紀元號的選舉行為發生，它就可以知道自己擁有領導權，能安全地做決定。
共識的極限
首先是每次的提議都要投票，這樣就跟 同步化數據複製 (synchronous replication) 一樣，但現在資料庫為了效能通常都會選擇 異步化數據複製 (asynchronous replication)。
再者共識算法需要嚴格的多數才能進行，意味者起碼要 3 個節點。
最後就是共識算法通常是依靠 timeout 去檢測故障節點，在高網路延遲的環境下，尤其是不同地區的分散式系統，有可能會發生誤會 leader 死亡的狀況，太常發生時對效能是個傷害。
協調服務 (Coordination Services)
像 Apache ZooKeeper 類型的專案通常會被描述為：”分散式 key-values 儲存” 或者 “負責協調和配置服務”，那為什麼 ZooKeeper 要實現共識演算法？它跟其他資料庫又有什麼不同？今天就來了解下 ZooKeeper 做為協調服務能用在哪些地方。
用在分散式系統上
ZooKeeper 不是一般用途的資料庫，它通常是其他資料庫需要依賴的背景服務，像 Hbase、Hadoop YARN 和 Kafka (2.8 前) 等等，它被設計為處理很小量的 meta 資料，也因此資料能完全存在記憶體中，資料也會透過 全局順序廣播 (total order broadcast) 複製到其他節點上，除了全局順序廣播外，ZooKeeper 也能幫助我們建立分散式系統：
- 線性化原子操作 (Linearizable atomic operations) 使用 原子比較並交換 (atomic compare-and-set) 操作，你能實現鎖：若多個操作並發發生，只有一個操作能成功。 另外分散式鎖也能用來實現 lease (租約)，它會有過期時間，以便在用戶端故障能也能釋放。
- 操作的全局排序 (Total ordering of operations) 一樣在 Trouble with Distributed Systems – Truth and Lies 提過，我們會用 擊劍令牌 (Fencing token) 來避免用戶端操作的衝突，而擊劍令牌就是每次在獲取鎖時會增加的數字，而 ZooKeeper 的 zxid 和 cversion 就能充當 token，因為它能提供每個操作一個單調遞增的 transaction ID。
- 錯誤檢測 (Failure detection) 用戶端能在 ZooKeeper 上維護一個長時間的 session，當節點的 heartbeats 未發送或 timeout 時，ZooKeeper 可宣佈該節點死亡，釋放所有該節點占用的鎖（ZooKeeper 稱之為 ephemeral nodes)。
- 改變通知 (Change notifications) 用戶端能監控 ZooKeeper 的資料變化，當它發生改變時，會通知所有註冊的節點們；所以節點會知道有誰加入叢集，或者有哪此節點死亡。
以上功能除了 線性化原子操作 需要用到共識算法外，其他功能造就了 ZooKeeper 很適合用在分散式系統的協調作用上。
用在節點工作分配上
首先是用在 leader 選舉上，除了 single-leader 資料庫以外，leader 也能用於安排 job 的時程或者需要類似角色安排工作的系統。
再者是用在分區資源管理（資料庫、訊息系統、檔案儲存或分散式角色系統等等），透過 ZooKeeper 能幫忙你在新節點加入或故障時做 分區再平衡 (rebalancing partitions) 。
最後是用在共識投票上，只要固定節點數（通常是 3 或 5 台）的 ZooKeeper 就能實現上千台節點的多數決投票。
用在服務發現上
服務發現 (service discovery)，透過 ZooKeeper 或 Consul，能讓用戶端透過服務名稱找到實際可提供服務的 IP，服務只要透過服務註冊完，就能讓其他服務找到。
結論
這幾天介紹許多有關分散式系統的研究理論，包含 線性一致性 (Linearizability)、全局順序廣播、共識演算法、2PC、Lamport Timestamp 等等，雖然這些都有點難以理解，但它們都是實務上你曾看過的分散式系統中的詞彙，這裡應該算是個入門吧，幫助工程師多多少少有一些些了解，有能力的話再去看看那些相關原文吧。
