Designing Data-Intensive Applications 讀書筆記 - 第五章 Replication

05-01

這是《Designing Data-Intensive Applications》第五章的讀書筆記，之所以從第五章開始，是因為前四章都是偏向於資料庫、網路基礎知識，從這一章開始（全書的Part II）才真正講如何管理分散式數據。

一、Leader 和 Follower

用戶端寫入的時候，必須先經過 Leader 處理
其它節點是 Follower，Leader 寫入完畢後會通知他們複製數據，保證一致性
客戶端讀的時候，可以隨便讀，但寫的時候只能向 Leader 寫

1.1、同步複製與非同步複製

上圖 Follower1 是同步複製，Follower2 是非同步複製

同步複製：

寫入請求時，Leader 會一直等到所有 Follower 都確認已經寫入後（期間不處理任何寫請求），才向客戶端返回成功

優點：保證強一致性

缺點：如果任何 Follower 掛掉，都會寫失敗，這在大型系統中是不現實的

所以在實際的資料庫中，使用的都是半同步（semi-synchronous），即一個 Follower 是同步的，其它都是非同步；如果同步的那個 Follower 掛了，那麼設置一個新的 Follower 為同步模式

非同步複製：

寫入請求時，Leader 自己寫入成功後就返回，不等待 Follower

優點：可以立刻響應寫入請求，即使所有 Follower 都掛掉了

缺點：可能會導致不一致（告訴客戶端寫入成功了，但實際沒有成功）

現在大部分使用的都是非同步複製

1.2、增加新的 Follower

即如何在集群不斷寫入數據的同時，加入新的 Follower，讓它的數據跟上大部隊

給 Leader 某個時刻的數據做一個快照
把快照複製到新的 Follower 上
新的 Follower 連接上 Leader，告訴它從哪個時刻開始同步數據
直到新 Follower 的數據跟上了 Leader 的步伐（caught up），開始進入工作

1.3、處理節點宕機

Follower 宕機

處理非常簡單，從宕機前的日誌開始和 Leader 同步即可，和增加新的 Follower 步驟差不多

Leader 宕機

檢測 Leader 宕機
選出新的 Leader
把系統配置改為新的 Leader

1.4、日誌複製的實現

1.4.1 基於語句的複製，Statement-based replication

基於語句的複製，比如在 SQL 中複製 INSERT、UPDATE、DELETE 語句到 Follower。

存在一些問題：

NOW()、RANDOM()這樣的函數，沒法基於語句複製，因為每次運行的結果都不一樣
如果語句依賴自增數，或者跟資料庫中現有的數據強相關，那麼必須保證語句執行順序跟 Leader 完全一致，在並發處理多個事務時這一點很難保證
語句有副作用時，可能會導致不一致的出現

上面這些問題有辦法解決，MySQL 5.1 版本之前使用的就是這種複製模式。

1.4.2 預寫式日誌，Write-ahead log (WAL) shipping

本書的第三章討論了日誌結構的儲存引擎的實現（SSTable、LSM-Tree 和 B-Tree），如果是這種儲存引擎，我們可以把它的每一次寫日誌都複製到 Follower 上，這樣可以保證一致性。

PostgreSQL 和 Oracle 就是這樣實現的，缺陷在於，這種複製方式非常底層，每一條 WAL 包含的信息實際上是「向哪一個硬碟 block 寫哪些 bytes」，這就導致 WAL 和儲存引擎強相關，也就是必須保證 Leader 和 Follower 的儲存引擎底層完全一致，導致很難集群進行版本升級。

1.4.3 邏輯日誌複製，Logical (row-based) log replication

把日誌抽象為與底層引擎無關，採用 change data capture，每次有數據更改的時候都記下改了什麼，例如記錄每次寫入的值和行號，MySQL 的 binlog 就是這樣實現的。

二、複製滯後產生的問題

對於單 Leader，多 Follower的架構來說，一般是只能向 Leader 寫，但可以向任何 Follower 讀，這樣可以大大增加讀的性能。

但由於寫操作需要向 Follower 複製，這裡就會產生滯後問題，寫完後立刻讀，有可能會向 Follower 讀到舊的值（因為此時 Leader 可能還沒有同步變化到 Follower 上）。

當然這種不一致的狀態是轉臨時逝的，不會永久存在，也就是所謂的「最終一致性」。

下面是滯後的解決方法

2.1、誰寫的就由誰來讀（Reading Your Own Writes）

具體可以有以下策略：

如果讀的欄位可能已經發生了變化，那麼向 Leader 讀取（因為 Leader 的數據一定是最新的）；
如果讀的欄位距離上一次變更時間很短，那麼向 Leader 讀；
客戶端在讀請求的時候帶上自己最近一次寫操作的時間戳，處理這個讀請求的伺服器看到這個時間戳，就可以知道自己本地的數據是否過時了

2.2、單調讀（Monotonic Reads）

客戶端進行多次讀操作時，這些讀操作可能會分配到不同的 Follower 上，所以可能會發生第一次讀到了數據，然後第二次讀的時候數據又消失了的問題，如下圖 User 2345，第一次在 Follower1 上讀到了評論，第二次在 Follower2 上沒有讀到評論：

所以，客戶端讀到了新的數據，那麼就不能讓它讀到舊數據。最簡單的解決方法就是，把每個客戶端的讀請求都分配到固定的 Follower 上。

2.3、一致性前綴（Consistent Prefix Reads）

由於伺服器之間複製數據可能產生的滯後，數據的時序可能會產生問題。

比如下圖，Mr. Poons 先說了一句話，然後 Mrs. Cake 回復了他，然而對於第三方觀察者而言，他們的對話時序可能是混亂的：

所以只有保證寫入是按照時序的，才能使讀到的數據保持正確的時序。

所以寫入的時候，需要在集群中維護一個全局的時序。

三、多 Leader 複製

單個 Leader 的缺點在於，如果任何因素導致無法連接 Leader，那麼你就無法向資料庫寫入任何數據了，這會讓整個系統非常脆弱，所以我們在一些情境下需要多 Leader 的架構。

3.1、多 Leader 複製的示例

下面是一些多 Leader 架構的示例

3.1.1、多個數據中心

像上圖這種情況，你可以有多個 Leader 分布在不同地方的數據中心，每個數據中心都是一個獨立的集群，它們的 Leader 之間會相互同步數據。

對比一下單 Leader 和多 Leader 的優劣：

性能

單個 Leader 導致只能向一個節點寫入，而多 Leader 能顯著提升讀寫性能

數據中心掛掉時

當有多個數據中心時，其中任何一個數據中心掛掉都不會影響系統對外的服務能力

網路出問題時

單個 Leader 非常依賴集群內部網路的穩定性，而多 Leader 可以容忍暫時的網路問題，因為臨時的網路問題不會影響整個系統的寫入。

3.1.2、可以離線的客戶端

我們可以把一個支持離線運行的客戶端，和伺服器端，視為兩個「數據中心」，比如一些日曆應用，會在本地維護一份數據，直到有網路時，才會和伺服器進行數據同步，這就是一個非同步的多 Leader 架構。

CouchDB 就是為此設計的。

3.1.3、多人協作編輯

像 Etherpad、Google Docs 這樣的應用，允許多人同時編輯同一份文檔，每個人都是一個「Leader」，相互之間同步數據，但這顯然會遇到衝突的問題。

3.2、解決寫衝突

多 Leader 之間同步數據，最大的問題就是如何解決寫衝突。比如下圖中，兩個用戶都修改了文檔的標題，發請求給伺服器，都返回了成功，但直到 Leader 之間進行同步時才發現之前的數據有衝突。

下面是一些解決方法。

3.2.3、同步衝突檢測

單 Leader 不會發生衝突，因為每次寫入都是一個原子化的事務。

多 Leader 如果採用同步的方式檢測衝突，也不會發生衝突。即每次寫入時，都向其它的 Leader 檢查有沒有衝突，如果都沒有衝突，那麼寫入成功。但這樣性能極差，也丟掉了多 Leader 架構的好處，還不如用單個 Leader。

3.2.4、避免衝突

多 Leader 架構避免衝突最簡單的方式就是，讓可能產生衝突的請求，都走向同一個 Leader。比如對於同一項資料的修改，都路由到固定的某個 Leader 上。

這樣做的缺陷在於，集群是不斷變化的，很難做到長期固定，Leader 的變化就會讓這個策略失效。

3.2.5、覆蓋

產生衝突的寫入也可以有先後順序，我們用更新的那個寫入覆蓋之前的。

3.3、多 Leader 的拓撲結構

多 Leader 可以有很多種拓撲結構，環形、星形、全連接形。

全連接形是最符合直覺的，每個 Leader 都和其它所有 Leader 相互交換數據。MySQL 使用的是環形連接。

四、無 Leader 複製

無 Leader 複製完全不需要 Leader 的存在，這種架構中，客戶端可以向多個節點發起寫入請求。

4.1、當有節點掛掉時，如何寫入資料庫

只要保證多個節點寫入成功，那麼客戶端就可以認為寫入成功。

4.1.1、讀取時進行修復

在讀取的時候，可能會存在不一致（因為有部分節點寫入失敗），這時可以發現不一致並且修復它。或者所有節點都定期檢查是否自己的數據跟別人有不一致的地方。

4.1.2、讀寫的 Quorums 機制

簡單地說就是只要從多個節點那裡讀成功，或者寫成功，那麼就可以認為成功了。

具體地說，假設我們有 n 個節點，只要其中 r 個節點讀成功了，那麼就認為讀取操作成功了；其中 w 個節點寫成功了，那麼就認為寫入成功了。

一般來說 n 都取基數，而 r、w 都取 (n + 1) / 2，即過半節點響應成功即可。至少要保證 w + r > n，這樣才能保證至少有 1 個節點能返回最新的數據。

4.2、Quorums 機制的局限性

如果存在並行寫入，那麼集群無法知道寫入的先後順序，因為不存在 Leader。
如果寫的同時還在讀，那麼無法保證讀到的是新值還是舊值。
如果 w > r，那麼可能發生寫入成功的節點數不足 w，寫入失敗，而讀的時候成功數大於 r，這樣就讀到了一個「寫入失敗」的值。

4.3、處理並行的寫入

對於 Leaderless 架構來說，並行的寫入會導致集群數據不一致的問題：

上圖中由於並行的寫入操作到達各個節點的時間順序不一致，導致 Node 2 與別的節點數據不一致。

解決方法如下：

資料庫為每個寫入都標記一個遞增的版本號
客戶端寫入前，先讀取到這個版本號，然後帶上這個版本號再發送寫入請求
資料庫識別這個版本號，根據版本號決定是否寫入、怎麼寫入

上圖中，每個客戶端的寫入請求都會帶上本地的版本號，以便告訴資料庫「要在哪個版本的基礎上進行變更」。本質上就是一個狀態機轉移：

收集完各個客戶端的請求之後，合併寫入的狀態即可。