如何理解分佈式領導者複製算法模型

點擊上方小坤探遊架構筆記可以訂閱哦

在前面數據複製原理文章我們已經瞭解到數據複製是建立無共享存儲架構下, 存儲系統每個節點通過網絡連接都持有一份自己完整且相同的數據副本. 而數據複製的難點在於處理複製數據的變更. 數據複製算法主要有基於 Leader-Based Replication、Multi-Leader Replication 以及 Leaderless Replication 三種方式, 因篇幅內容比較多, 今天樣結合《Designing Data-Intensive Applications》一書來聊聊前兩種領導者數據複製算法原理.

Leader-Based Replication

這個時候我們採用其中的一種機制, 即多個 Replica 中選擇其中一個作爲接收客戶端的寫入並將數據複製到其他 Replica, 這就是我們的 Leader-Based Replication 機制, 我們也稱之爲基於領導者複製算法, 也會稱之爲主從複製算法模型. 那麼其工作流程如下:

而基於上述的複製算法模型, 結合之前的數據複製原理, 我們的 Leader-Based Replication 落地實現又產生以下幾種架構的變種, 即:

基於單領導者複製模型, 我們更關注前面所講的複製方式, 爲什麼呢? 既然數據複製是建立在網絡連接情況下來進行數據同步, 那麼必然存在數據一致性問題. 而數據一致性可以基於之前高可用架構設計的一致性決策框架來輔助我們進行決策. 如果我要實現強一致性, 那麼我的複製方式模型至少需要是同步複製方式, 這個時候我們可以採用全量同步、鏈式同步以及半同步複製方式進行決策, 這個時候我們的同步複製方式對數據一致性的影響轉向爲時效性與性能上的 Trade-Off 問題.

怎麼理解呢? 如果我追求寫性能且同時需要保證讀己之所寫的線性一致性, 那麼我就採用單領導者複製的主備方式, 即讀寫都是走 leader 節點, follower 節點都是備份.

如果我想提升讀性能又要保證讀己之所寫, 那麼我就只能降低寫性能, 因爲我寫入數據必須要等待 leader 向 follower 節點同步複製才響應給客戶端, 這個時候客戶端僅從 leader 進行讀寫, 從同步 follower 進行讀操作, 其他 follower 節點不接收讀請求. 這個時候就改變了架構本質, 從主從架構將爲部分主備架構.

同樣地, 如果我業務層面允許降低一致性要求, 那麼我就基於 BASE 理論考慮實現最終一致性, 那麼這個時候我可以採用異步數據複製方式. 然而異步數據同步會帶來一個新的問題, 那就是存在數據丟失, 因爲異步存在無限延遲, 我們無法知道對應的數據是不是真的同步到 follower 節點, 如果此時 follower, 那麼當 leader 發生故障時重新從 follower 節點之間進行選舉就會發現 follower 節點數據缺失了 leader 節點上的數據.

對於這種情況, 如果是緩存系統並緩存是基於 sessionId 維度緩存, 那麼我們可以直接採用異步複製, 但如果是重要數據, 那麼就不能直接採用異步複製方式, 而是需要在異步複製基礎增加可靠性保證的機制, 或者是切換爲部分同步機制.

可見基於單領導複製算法模型, 我們會面臨數據丟失以及一致性問題, 具體要取決於業務層面對上述兩類故障類型的容忍程度.

但是它還存在一個主要缺點, 那就是存在單點寫故障問題, 因爲只有一個 leader 數據副本負責接受數據的寫入, 所有的操作都必須經過它, 如果由於任何原因, 比如存在網絡分區導致無法連上 leader 數據副本, 那麼客戶端將無法向數據庫寫入數據. 那麼有什麼解決方案呢?

Multi-Leader Replication

基於 Leader-Based 複製模型的一種自然擴展是允許多個數據副本節點接受寫入操作, 即 Multi-Leader Replication, 當僅新增加一個 Leader 數據副本的時候, 我們有時也會稱之爲雙主複製模型, 即 Master-Master Replication.

對於多主複製模型, 我們更多常見是做異地多活架構, 一般在單數據中心做多主複製模型比較少, 因爲單數據中心做多主複製模型相比多數據中心多主複製模型的複雜度基本差不多, 絕不會因爲是單數據中心而讓架構的複雜度變少, 而且最重要的一點是單數據中心無法容忍數據中心級別甚至區域級別的故障, 因此採用多數據中心相比單數據中心有更高的可用性, 能夠容忍數據中心甚至是區域級別的故障問題.

多數據中心多主複製架構如下: 我們的數據庫多個 Replica 分佈在不同的數據中心, 而且每個數據中心都有一個自己的 leader 節點, 用於接收客戶端的寫入請求, 並基於寫入請求向其他數據中心進行異步數據複製, 如下:

那麼單領導者複製能否也部署多數據中心呢? 其實也可以, 我們可以對比下多數據中心多主複製以及多數據中心單主複製之間的差異:

在我們實際落地過程中, 我們的存儲雙主模型存在 2 種演進的架構變化, 其他基本也是基於這兩種模式進行改造演化而來. 第一種也就是我們每個數據中的數據 leader 副本節點是將數據異步複製到其他數據中心, 即:

第二種是我們基於客戶端採取的雙寫模型, 其中定時數據同步是可選的, 可以思考下爲啥是可選的, 試想下如果是基於請求的 sessionId 維度緩存, 那麼我們其實也可以是不做數據同步的, 即:

除了上述的場景, 雙寫爲啥需要定時同步呢? 我們肯定是想消除數據一致性, 即反熵, 同時防止數據丟失, 而且如果其中一個 IDC 不可用, 那麼我的雙寫也需要增加可靠性保證, 比如持久化寫入日誌, 比如 WAL 機制, 當 IDC 恢復的時候直接從另一個 IDC 通過日誌 Lag 以及 Offset 同步增量數據.

寫入衝突問題

對於多數據中心的雙主複製模型, 最大的問題我想很容易想到就是數據一致性以及寫衝突問題. 相比單主模型複雜度要高很多, 關於一致性其實我們有一個之前高可用架構一致性決策框架, 但框架是輔助工具而不是解決方案, 在這裏我們如果是要做強一致性且是多數據副本的情況下, 那麼需要採用共識算法來解決.

不僅如此, 我們選擇的共識算法決策還要結合我們對業務層面理解並採用對應的一致性模型綜合考慮得出. 而寫衝突也會影響我們的數據一致性, 而這種一致性我想我們應該要識別出來, 它是在我們的 FLP 定理是一個安全性屬性問題, 即 Safety 屬性.

寫衝突就是多數據中心相互獨立能夠接收相同字段不同的值寫入導致數據要進行持久化時無法進行判斷該以什麼爲準. 比如用戶 1 將頁面標題從 A 改爲 B，而用戶 2 同時將標題從 A 改爲 C。每個用戶的更改都在其本地領導者節點上成功應用。然而，當這些更改異步複製時，就會檢測到衝突. 如下:

第一種方式異步變更爲同步複製, 那就意味着需要等待寫入操作複製到所有的副本, 然而如果這樣做那還不如直接採用單主複製架構, 因爲這種方式直接將原本支持多個副本寫入又間接改成單個副本寫入.

第二種方式避免衝突. 如何避免? 就是實現邏輯上的單領導複製模型, 其實就是將這個改造爲邏輯分區架構, 每個數據中心都有一份全量的數據, 比如南方以及東南地區走 IDC-1, 北方以及西部區域都走 IDC-2; 又或者按照範圍分區, 或者是 hash 分區等等, 這樣實現不同用戶有不同的數據中心歸屬的地方. 保證同一個用戶不論如何請求都只會路由到在本地數據中心執行.

第三種方式是存儲系統層面自動解決, 比如基於時間戳按最後寫入優先 (LWW) 或者編號較高或者較低者爲準寫入, 但存在數據丟失風險. 在前面我們講述了不可靠時鐘帶來的問題. 關於這種我們需要了解對應存儲系統的複製模型以及衝突解決機制. 一般我們是不能太依賴於存儲系統來幫助我們解決所有的事情.

關於自動衝突解決方案, 業界也有一些研究方向可以參考:

第四種是自定義衝突解決邏輯, 即取決於我們業務應用場景, 即採用編寫代碼邏輯來解決, 也就是我們可以通過寫入檢測到複製日誌與寫入數據衝突並通知衝突處理程序保存多個版本, 然後當讀取時返回多個版本給用戶讓用戶解決衝突.

多主複製數據傳播路徑

如果我們把雙主複製模型擴展到多主複製模型, 那麼這個每個 leader 需要將其寫入操作發送到其他數據中心的 leader, 即數據複製通信路徑. 那麼在多主複製模型中存在以下 3 種通信路徑, 我們可以採用複製拓撲結構來進行描述如下:

對於 Star 以及 Circular 拓撲結構, 一次寫入操作可能需要經過幾個節點才能到達所有副本節點, 因此節點需要轉發它們從其他節點收到的數據變更. 但是爲防止無限複製循環, 每個節點都被賦予一個唯一標識符, 比如節點自身的 ID, 那麼在複製日誌中每次寫入操作都標記有它所經過的所有節點標識符. 這樣當一個節點接收到其他節點數據變更日誌帶有自身的標識將自動忽略, 表示已處理過.

對於 Star 以及 Circular 還存在一個問題是如果僅有一個節點發生故障就有可能中斷整個複製日誌流, 因此需要手動配置繞過故障節點. 而對於 All-to-All 拓撲結構則容錯性更好可以沿着不同的路徑進行傳播, 避免單點故障.

但是對於 All-to-All 結構, 也存在一個數據跳躍問題, 即下面的 leader 節點更新到數據 value=2, 但是由於網絡延遲原有的 value=1 還未同步到 leader2, 也就是還未進行 insert 動作就操作了 update 導致數據出錯, 也許這裏出錯可能過一會再做重試可以解決.

但是如果這裏的 insert 是改成 update 操作呢, 那麼這個時候 leader2 節點就會執行 update 更新數據導致數據錯亂, 在這裏我們識別會存在一個一致性前綴讀, 也就是存在因果關係, 那麼這個時候我們可以考慮採用版本向量來標記每個操作的順序, 其中版本向量具備單調且唯一性, 這個時候我們複製數據更新就可以通過重試 + 版本向量解決數據衝突問題.

至此我們已介紹多主複製模型, 可以看到實現這樣的複製模型要考慮的點不僅僅是數據一致性問題, 還需要考慮寫入衝突以及消息傳播結構, 在共識算法中實現消息傳播的協議就是我們熟悉的 Gossip 協議. 通過 Gossip 協議來修復我們的數據一致性問題. 同時 Gossip 協議也將是接下來解決我們無領導複製模型數據一致性的重要手段. 關於無領導複製模型留着下次再講.

總結

今天主要講述基於領導者複製算法模型及其可能存在的問題, 當我們要基於存儲系統做高可用數據複製架構的時候, 那麼我們就需要關注對應的複製算法模型優缺點以及可能帶來的複雜度問題, 這樣當我們落地的時候就能過結合對應的存儲系統文檔更加全面地去測試我們的存儲系統, 以確保它能夠提供具備我們認爲的保障.

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

猜你喜歡