# 分散式資料庫—容錯 怎麼在分散式環境中建立容錯的資料庫叢集。 [文本於此](https://evan361425.github.io/feedback/n-applications/distributed-ft/) note: 我們從前四次分享「如何處理競賽狀況」時就一直提起：分散式資料庫沒辦法有效容錯。這次，我們終於要來談談分散式資料庫要怎麼容錯了！我們先來談談單台機器的容錯機制，再來帶出分散式系統的容錯機制。 ----  note: 對應用程式開發人員來說，他可以很簡單的在異動前告知資料庫我要使用「交易」的機制，以此來滿足資料的一致性和容錯性。 但是我們前面提了「複製延遲」很輕易就可以破壞這一系列的保證。同時，我們也要問問自己，如何讓開發人員使用和「交易」相似的方式來讓開發人員不需要在寫程式的時候還要思考分散式叢集會有的邊際狀況？ ----  note: 那分散式資料庫又該做什麼？在開始前，我們先前情提要一下。 ---- - 網路 - *錯序*、*遺失*、*延遲*、*重複* - 時鐘 - *不准*、*跳時*、*閏秒* - 執行序 - *延宕* note: 上次提了分散式環境的困境，告訴我們哪些路是不能走的。 若有興趣對網路想要有更深的了解，可以看： - [網路怎麼傳](http://evan361425.github.io/essay/web/network-routing/) - [網路傳了什麼](http://evan361425.github.io/essay/web/network-details/) :::info 即使單台機器也會受到執行序的延宕，但是單台機器的延宕代表所有程序都會被延宕，所以他並不會認知到自己被延宕了（除非檢查時間）。但是到了分散式系統時，執行序的延宕就代表有一節點突然無法運作，這時其他節點仍能正常運作。隔了三十秒之後，該節點恢復正常了，這時就可能造成不同節點的錯誤認知，例如複權（split brain）。 ::: ---- 暫時的錯誤狀態會成為永久 note: 我們有提到很多 NoSQL 宣稱最終一致性是必然的，然而最終一致性雖然可以讓狀態達到最終的一致性，但是當你從（暫時的）錯誤狀態作出任何判斷並執行異動時，相對應的錯誤異動就成為「正確的」異動，並永久的影響資料庫的狀態。 例如帳號註冊時，檢查帳號是否註冊過：因為應用程式從資料庫得到的資訊是帳號沒被註冊過，所以允許註冊，這時就會讓這種暫時的錯誤狀態成為永久的錯誤狀態。 因爲這異於一般的開發環境（通常我們存取程式碼中的變數時，都期望得到的值是最新的狀態），所以這會增加應用程式開發的負擔，每此設計時都要仔細設想各種狀況。而且這種東西很難得到保證：我這樣做就一定沒錯。 ---- 高一致性 v.s. 高可用性和效能 note: 當我們讓分散式資料庫擁有高一致性，就會犧牲高可用性和高效能，所以在開始講分散式的容錯系統前，需要先有個認知：**我不一定需要這些東西**。 在衍生資料的系列中（本系列叫做分散式系統），我們會提一個資料庫叢集的架構，這個架構就是試著鬆弛這個權衡：同時擁有高一致性和高可用性。 ---- 什麼是一致性？ note: 最後，我們重新確認一下名詞的定義。 - 單一節點中，一致性代表並行請求造成的競賽狀況的處理。 - 分散式系統中，一致性代表如何維持多台資料庫到相似的狀態。 --- **有哪些容錯方式**  note: 這次報告會談主要三件事，線性系統、因果關係和共識演算法。 ---- ## 線性系統 想像一下單一領袖 note: 處理機制其實就是讓叢集執行得像是線性系統，而先前的單一領袖複製方式其實就很像這個東西。 問題是，單一領袖的領袖從何而來？如果領袖是從管理者（人類）決定的話就代表需要 24 小時輪班來監控這個領袖的健康狀態，然而我們可能僅能透過網路的監控系統去檢查，這監控系統很可能是不穩定的。如果我們要自動化，那就一樣需要共識演算法。 名詞： - linearizability - strict serializability - strong one-copy serializability - atomic consistency - strong consistency - immediate consistency - external consistency ---- ### 鴿舍理論  note: 滿足鴿舍理論並不代表符合線性系統，他不能保證叢集的狀態一致，就算你滿足最好的狀況：三台都異動成功，你仍然會發生狀態錯誤的問題。 ---- - 高成本 - 好理解 note: 線性系統是高成本的而且很可能是不能容錯的（想想單一領袖），但是線性系統卻可以很簡單的幫助我們理解共識演算法要做的事。 --- ## 因果關係 他和線性系統差在哪 note: 因果關係不是線性系統。在因果關係的系統中，我們不會說 *異動A* 早於 *異動B*，而是說 *異動B* 依賴於 *異動A*。這樣的關係異於線性系統。 ----  note: 在單台資料庫中有可能發生圖上右邊的並行異動請求的模式，這時就會出現狀況。我們之前提說透過快照隔離，賦予每個請求當下的版本，讓他只允許取得當下版本的資訊。而這中間的賦予順序就是幫助我們得到因果關係。 相對而言，線性系統中右上方的 `Read A` 就會出現在下面的請求之前。也就是因果關係並不會阻止並行的請求，但是他會幫助我們釐清請求和請求之間的關係也因此因果關係並不強於線性關係。 ---- ### 和全域順序的關係 因果關係會賦予全域順序嗎？ note: 因果關係並不是全域順序，他可能在兩個節點間得到一個一樣的版本，例如節點 A 得到版本 123，節點 B 也得到版本 123。 但是這並不會造成問題，因為只有相依的請求才有賦予順序的必要。若兩個請求沒有關係，那麼給予他們相同的數字也沒什麼關係。想想現在南極正有一陣風吹起，我們不會說我先動南極的風才動的，因為這比較沒有意義。 ---- ### 可以實作嗎  note: 當要異動某個值時，我們需要紀錄：是否這個新的異動來自於先前的狀態。所以我們需要一個類似*版本向量*的東西。當要做異動時，應用程式需要傳給資料庫當初他在讀取時的版本，資料庫就可以透過版本確定這個先前讀取的資料是否已經過時（stale）。舉例來說，資料庫擁有版本一的狀態，當被請求要異動到版本三時，需要等待版本二的異動被執行（類似於序列化快照隔離中，資料庫透過了解某些異動請求之間的因果關係來並免發生資料不一致）。 目前，賦予順序是線性系統之外[最強的一致性](https://www.cs.tau.ac.il/~mad/publications/podc2015-replds.pdf)，並且可以維持效能和可用性。但仍是開放研究，並未投入線上環境且有些問題需要處理（例如若要求每個資料都紀錄因果關係，這個量會很大而且不符合 OLTP 的模式：大量讀取小量異動）： - [Challenges to Adopting Stronger Consistency at Scale](https://www.usenix.org/system/files/conference/hotos15/hotos15-paper-ajoux.pdf) - [Causality Is Expensive](http://www.bailis.org/blog/causality-is-expensive-and-what-to-do-about-it/) 一些資料庫嘗試在滿足因果關係時，給予效能和可用性 - [Stronger Semantics for Low-Latency Geo-Replicated Storage](https://www.usenix.org/system/files/conference/nsdi13/nsdi13-final149.pdf) - [SwiftCloud](http://arxiv.org/abs/1310.3107) - [Bolt-on](http://db.cs.berkeley.edu/papers/sigmod13-bolton.pdf) --- ## 全域順序 因果關係之外還有什麼方式？ note: 然而上述的方式會需要紀錄大量的版本，而且實際應用程式基本上都是拉取很多資料而異動一部份資料，這樣版本的資訊會很龐大而失準。 也許我們可以替每一個異動都加上版本（也就是全域的順序），只要每個叢集內的資料庫遵循著這個版本去執行，就能確保他的因果關係。這就好像單一領袖的資料叢集都會遵守領袖的異動順序，我們現在把這個概念套用在多領袖/無領袖的叢集上。 ---- - 各個資料庫產自己的版本（例如前綴 ID） - 時間戳記 - 各個資料庫使用範圍內的版本 note: 有哪寫不能保證因果順序的方式？ ---- **Lamport 時間戳記**  note: Lamport 在早期明確訂立了「因果關係」和「全域順序」在分散式系統的重要性。他於 1978 年的[論文](https://www.microsoft.com/en-us/research/uploads/prod/2016/12/Time-Clocks-and-the-Ordering-of-Events-in-a-Distributed-System.pdf)是目前分散式系統相關論文中最多引用次數的論文之一。 不過這個方式在建立使用者帳號這個場景並不怎麼適用。 Lamport 時間戳記（序列化時間戳記）運作原理是每個節點和每個請求者做任何請求時都會攜帶最大的計數，當節點遇到比自己的計數還高的值時，則更新自己的計數，以此來確保全域的順序。 但是如果兩個並行的請求分別在不同節點做使用者的註冊（就會像 `c=6` 時那個樣子），各節點不知道對方目前正在處理使用者的註冊，所以這個全域順序並沒辦法幫助我們避免註冊兩個重複的使用者。 要讓 _序列化時間戳記_ 成功避免重複，就需要在節點處理異動請求時去和其他節點確認：*我正要執行「計數為六」的異動，請你的計數加一*。當其他節點再執行相同的異動（例如註冊同一個使用者帳號）時，因為他的計數是七，而他又知道計數六的異動正在執行相似的請求，於是他就拒絕執行計數七的異動。 :::info _序列化時間戳記_（vector clock）容易和 _版本向量_ （version vector）混淆。 - 前者是用於獲得全域順序的方式 - 後者是避免並行處理的相互影響（每次異動該值，會增加他的版本，但這版本不是全域的） ::: ---- ### 全域順序廣播 total order broadcast note: 我們了解因果關係在分散式系統的重要，也提了一些可以幫助我們得到因果關係的方式而全域順序廣播就是其一。 剛剛我們提到節點通知大家：*我正要執行「計數為六」的異動，請你的計數加一*。這個做法就叫全域順序廣播。通常都是第三方管理這個順序，例如 ZooKeeper、etcd。 :::success ZooKeeper 不是在做共識演算法嗎？ 有[論文](https://cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf)證明全域順序廣播和共識演算法是一樣的，待會我們提共識演算法的時候會再回到這主題。 ::: --- ### 提供哪些保證 - 成功送訊息到節點 - 訊息是按照順序被執行的 note: 全域順序廣播保證兩件事情： - 成功送訊息到節點 - 當網路等問題導致節點失能，就會嘗試直到他成功為止 - 訊息是按照順序被執行的 分散式資料庫在做複製的時候，若能保持相同順序進行複製，那資料庫將擁有最正確的資料，我們可以把他想像成 append-only 的日誌。他也能滿足我們之前提過很強的一致性：序列化一致性，因為異動都被照著順序執行了。 這聽起來很像單一領袖在做的事情，但是讓單一領袖不被採用的原因是當請求的量超過一台機器能負荷的時候該怎麼辦？當領袖失能時該怎麼辦？ ----  note: 他也能用來被實踐於圍欄鎖（fencing token）中的遞增編號。 ---- ### 和線性系統的關係 線性系統可以透過全域順序廣播達成 note: 線性系統比全域順序廣播更為嚴謹，全域順序廣播確保異動執行的順序，但卻不保證異動送過去的順序。除此之外，線性系統要求讀取到的值就是最新狀態，然而全域順序廣播通常不會限制讀取的順序。 但是線性系統是可以建立在全域順序廣播之上的。 > 但是線性系統比全域順序廣播[更易](http://courses.csail.mit.edu/6.852/08/papers/CT96-JACM.pdf)實作出來。 ---- **怎麼達成？**  note: 想像之前我們在討論競賽狀況時的住院醫生申請休假：休假的邏輯是先取得目前值班住院醫生人數，並於應用程式中檢查數量是否大於一，若大於則允許休假，反之則拒絕。 同一時間兩個醫生請求休假，就會造成兩個醫師都休假成功。 怎麼依上述例子（想簡單一點就是註冊帳號的例子）完成分散式的一致性（線性系統）？ - 在一個抽象日誌（透過全域順序廣播達成）附加（append）一個請求：我要讀現在住院醫生的人數 - 向這個日誌取得剛剛請求的編號 `id1` - 做任何得到這個值的邏輯判斷 - 發出另一個預先請求（並不會執行，僅作宣告）：我要讓這個住院醫生休假 - 取得剛剛預先請求的編號 `idn` - 確保 `id1` 和 `idn` 間所有請求都被執行（`id(n-1)` 很可能會比 `idn` 晚來） - 執行請求 `idn`，並再附加至抽象日誌中 ---- ### 讀取時的線性系統 note: 若要讓讀取的請求達成線性系統，可以有幾種做法： - 把讀取請求放進抽象日誌中，確保讀取請求之前的所有請求都被執行（[etcd](https://etcd.io/docs/) 採用這做法） - 確保抽象日誌中當下最新的請求被執行，再執行讀取（[ZooKeeper](https://zookeeper.apache.org/doc/current/zookeeperInternals.html#sc_quorum) 採用這做法） 反過來說，全域順序廣播也可以透過線性系統達成，不過這裡就不贅述了。 ---- **小節** - v.s. 序列化時間戳記 - v.s. 共識演算法 - v.s. 線性 increment-and-get note: 我們再回頭比較一下 *全域順序廣播* 和 *序列化時間戳記*，全域順序廣播下的節點會監聽這個廣播，並確保照著順序執行異動。 序列化時間戳記就是讓各節點得到一個共有的序列化戳記，但是不保證並行請求之間的衝突，因為並行的請求並沒有相依性。 前面我們有提全域順序廣播就是在實踐共識演算法，我們也知道全域順序廣播和線性系統是可以相互實踐出來的。 也就是一個分散式系統若能實踐線性的 increment-and-get（用來遞增「順序」），就能實踐出全域順序廣播。 有[論文](http://courses.csail.mit.edu/6.852/08/papers/CT96-JACM.pdf)在講這三件事：全域順序廣播、分散式系統下線性 increment-and-get、共識演算法，都是在處理一樣的事，如果我們有一個演算法能解決任一樣，就能一同解決所有問題。 --- ## 共識演算法 note: 在開始講共識演算法之前，我們花了很多時間去釐清很多事情的關係（線性系統、因果關係、全域順序廣播）和理解一些背景知識（網路、時鐘、資料庫等等）。 這也是為什麼共識演算法這麼難的原因，並不是因為他的實作很困難，而是他需要有很多背景知識才能讓我們對於他要處理的東西有所概念。 共識演算法的概念很單純：讓各個節點同意某一個結果。但是若對這些背景知識不了解，會讓你錯誤的實作（coding）這些演算法。 ---- ### 應用 - 領袖選舉 - 全域順序廣播 - 分散式鎖（圍欄鎖） - 分散式交易機制 - 偵測系統 - 獨立限制 note: - 分散式交易機制，當多個資料庫執行相同的異動（透過全域順序廣播/共識演算法）時，有幾個資料庫拒絕該次異動（因為狀態不允許，如重複註冊使用者，或節點失能），需要讓其他已經執行異動的節點復原（abort）。 - 偵測機制，當有節點失能時需要有人判定其失能，或者偵測目前有哪些服務正在線上，若只有單一節點做判斷就很容易出錯。 - 獨立限制，例如使用者註冊帳號 ---- ### 實作 - 2PC(3PC) with XA - 共識演算法 note: 實作主要有兩種，2PC 和共識演算法。 ---- #### 2PC  note: 2PC 可以說是一種共識演算法，但是一般不會稱它為共識演算法，而直接稱其為 2PC，因為他不滿足一些特性。 > 大部分關聯式資料叢集都有實作 2PC。 以單一節點的資料庫為例，當請求進來時不會馬上異動資料，而是先寫進日誌（WAL）中，之後再執行這次異動。這麼做的好處是可以避免執行到一半機器重開機時可以復原。 當狀況變成分散式系統時也是一樣。有一個協調者（coordinator）發送異動請求，確保異動被收到（prepare，phase 1）之後就會進行提交（commit，phase 2）。 有點像結婚時，牧師問夫妻是否同意時雙方回答：我願意（prepare），之後牧師就會同意這場婚禮（commit）。 除了第二階段之外，任何一段發生意外時，協調者都可以放棄本次異動。但是當事情進行到第二階段時（也就是大家都同意這次異動時）所有節點都必須完成這次異動，**不論發生什麼事**。對於節點的角度來說，當他在第一階段回答：準備好了時，他就必須等到協調者的回應，不管是放棄或提交，**不論發生什麼事**。 總結一下做法： - 協調者發送異動請求 - 節點預作異動請求，檢查是否能處理該請求（例如使用者帳號申請是否 uniqueness） - 協調者確認每個節點都能處理 - 這之前任一節點無法回應或拒絕請求都會讓所有節點放棄該異動 - 協調者紀錄各節點的結果（提交或者放棄）並決定最終結果 - 協調者通知各節點結果，且在確保各節點都收到結果之前會一直嘗試通知並拒絕任何新的相關異動請求 > 上述提到的「決定」代表一旦各節點或協調者決定了每個結論（提交或者放棄）就不能再更改。 ---- **當 2PC 發生意外時**  note: 當發生意外時，不論協調者或著節點都必須停止運作直到確認接收到「放棄」或「提交」。這就讓分散式系統的高可用性和效能完全失能。 3PC 相較於 2PC 則不會讓節點或協調者停止運作，但是需要一個服務偵測系統，告訴協調者現在哪個節點停止運作了，但是服務偵測系統無法完美偵測錯誤（例如他對節點的網路中斷了，但是節點和節點仍可以正常溝通）導致這個系統失靈，所以即使 2PC 會有協調者失能時的狀況需要處理，但仍有很多資料庫叢集實作他。 ---- #### 協調者變成資料叢集的一環 note: 如果提交過程中有一部份資料庫沒有成功送出提交訊息，這些資料庫就會停止所有相關資料的異動（或甚至整個資料庫停止異動）。為什麼要這麼硬？這就是會了達成一致性的犧牲，如果資料庫準備好了但尚未進行提交而允許其他異動時，就會讓多台資料庫的狀態無法達成一致。 這時就會發現其實協調者是資料庫叢集的一環，當協調者中止時，對資料庫叢集來說是一個很重大的傷害，這也降低了我們預期的高可用性。但是大部分協調者的實作都不支援高可用性（多節點）。 有時協調者會被實作於應用程式中（透過 SDK 等等），這也讓應用程式從原本的無狀態變成有狀態。這種錯誤認知會造成很多維運上的意外，例如沒有正確 Auto Scaling 等等。 有時協調者的資料（異動是否提交的結論）遺失了，或者因任何狀況導致協調者長時間無法運作，資料庫中通常都會有個 API （heuristic decision）允許不透過協調者直接告知資料庫是否要提交，這就是用來避免這個狀況的發生。但是資料庫是否要提交是需要到各個節點確認各自的運作狀態來決定的，不這麼做的好很可能會有一些資料庫是「提交」而一些是「放棄」。 ---- #### XA eXtended Architecture note: XA（eXtended Architecture）是一種介面，這個介面讓 2PC 允許在異質的應用程式間擁有相同的構通橋樑。 例如資料庫和寄送郵件的應用程式。 --- ### 共識演算法 - Zab (ZooKeeper) - [Raft](https://raft.github.io) (etcd) - [Paxos](https://martinfowler.com/articles/patterns-of-distributed-systems/paxos.html) (Google Spanner, ...) - ... note: 一般我們在提共識演算法時，都是指上述這幾種，他們都會有一些特性異於 2PC，我們待會就會談。 不過這裡要講的是這些共識演算法都會得到一個[結論](http://courses.csail.mit.edu/6.852/08/papers/CT96-JACM.pdf)：多數決才能保證共識。也就是五個節點中，需要有三個節點同一這個結果。 > 有人做了一些[比較](http://arxiv.org/abs/1309.5671)。 不僅是實作，要使用這些共識演算法提供者本身就不容易了，所以有類似 [Apache Curator](https://curator.apache.org) 透過高維度的類別來幫助開發者使用 Apache ZooKeeper。 ---- - 一致性 - 唯一性 - 合法性 - 容錯性 note: 這些共識演算法需要滿足上述四個條件。 - 一致性，所有節點最終的結果是一樣的 - 唯一性，所有節點最終的結果只有一個 - 合法性，任一結果都是某一節點提出的 - 容錯性，任一節點的失能不影響其他節點決定 2PC 就是沒有容錯性，協調者不能失能。前面我們講的多數決也代表任一共識演算法的前提都是僅有少於半數的節點失能。 :::info 這些共識演算法其實內部機制和 2PC 很像，你可以把每個節點都當成協調者，他們可以提案、決定等等。 這個概念稱為 *世代數*（epoch number, ballot number, view number, term number），也就是確保每一次共識都有一組（多個）協調者，而兩次共識的協調者是獨立或不一樣的。 ::: ---- #### 應用 > 節點 `10.1.1.23` 是分區 7 的領袖 note: ZooKeeper/etcd/.. 和一般的資料庫不太一樣，他們不是用來儲存線上異動資料的資料庫，相反的，通常他們能儲存的量都很小（足夠被放進記憶體裡面）而這個小型資料庫叢集也通常不會太多節點（3~5 個），避免共識的過程太耗時。 通常他儲存的資料會是：節點 `10.1.1.23` 是分區 7 的領袖，這種不容易變動但卻是很重要的資料。所以 ZooKeeper/etcd/.. 的資料叢集很可能會用來服務一組比他們還要大很多的叢集（例如上百個資料庫節點） ---- #### 討論一下共識演算法 - v.s. 全域順序廣播 - 效能 - 動態群組 - 系統外 note: *全域順序廣播* 就是一直重複執行共識演算法，確保每個節點都能按照相同順序去執行異動請求。 因為每次異動請求都需要同步確認各節點的決定，所以效能不會好，除此之外當網路不穩定時（多個資料中心分散在不同場域）就很容易讓整個共識群組一直在重新選擇新的領袖。 另外，共識是需要多數決的，當有新的節點進來這個群組，多數決的數量就會被改變。這種動態群組（dynamic membership）也是一個需要被解決的問題（開放研究）。 效能問題和固定節點問題讓很多資料叢集選擇不使用共識演算法。 除此之外，通常我們會在資料庫叢集之外建立一個共識演算法群組，這種系統外的架構，很可能會讓整體架構變得複雜。 --- ## 總結 分散式系統的容錯就是透過全域順序來維持因果關係。 note: 我們暸解了分散式資料庫面臨什麼狀況（網路延遲等等），並且順著思路往下走，知道要解決這個問題其實就是需要一個線性執行異動的系統。 雖然線性系統能很好的幫助我們理解該如何處理分散式系統的共識，但是線性系統是很耗成本的，我們退而求其次，改採賦予因果關係這條路。 賦予因果關係就是要替每一組異動請求加上他的來源，幫助資料庫決定這個請求該不該執行。他不像線性系統要求所有編號都是獨立的，就像版本控制的圖一樣，我們可以有多個分支代表並行請求，最後再合併起來，當合併錯誤時，就放棄（或嘗試修復並再發出一個分支）那些小分支。 我們提到了全域順序廣播的實踐和其與共識演算法的關係。而共識演算法其實就是讓分散式系統變成一個[序列化狀態機](https://www.microsoft.com/en-us/research/publication/time-clocks-ordering-events-distributed-system/) 這章其實統合了前面所有分散式資料庫的內容。我們先前快速帶過了複製延遲但沒有提到當分區要做全域類型的搜尋（例如平均使用者年齡）時他可能會遇到的競賽狀況。在這一章都重新打開布幕讓我們一虧裡面實際會面臨的狀況和解法。 這章雖然不像前面在講資料倉儲的時候那麼多數學的感覺，但是卻是最難的一部份，因為你要把前面所學到的所有東西整合在一起去思考。單台資料庫他面臨了什麼問題？他透過什麼方式解決？當解決完之後，放在分散式資料資料庫時為什麼會失靈？分散式資料庫又透過什麼樣抽象程度的角度去解決這件事？ 看完這次分享之後，你會發現其實大部分文字還是著重在理解上述的問題，而不是實際展示或說明某某演算法的實作和邏輯（理解完某某演算法的實作之後，隔幾個月之後很可能就會忘記實際內容，畢竟你需要反覆理解維運這些實作的機會真的很少，在限制學習時間的情況下，我更傾向於理解在解決問題時其背後的抽象層面），因為當你看完實作之後，你可能會有個結論：喔喔喔，共識演算法是讓一群節點得到一個共識，那然後呢？，我個人認為比較難的部分是去理解所謂「因果關係」在分散式系統的重要性，也就是全域順序廣播如何幫助我們避免分散式系統的邊際狀況。 ---- ### 衍生資料 - 批次處理，Hadoop、Spark、... - 串流處理，Event Sourcing、... - 整合