分散式系統之 Replication

02-01

這是 Designing Data-Intensive Applications 第五章的學習筆記，主要講各種 Replication 方式。

Replication 的原因：

Availability ：一個節點掛了其他節點還能工作
Scalability：讀請求可以走 follower
Latency：可以讀物理距離較近的節點，降低 latency

但是同樣的數據放多份就會有 consistency 問題

Replication 按複製方式，可以分為

Synchronous
Asynchronous

按 Leader 可以分為

Single-Leader
Multi-Leader
Leaderless:

Single-Leader Replication

一個 replica 作為 leader，所有的寫操作都要先經過 leader
其他的 replica 作為 follower，讀操作可以經由 leader 或 follower
一個寫操作過來時，leader 除了寫在自己的本地存儲，還會把對應的操作寫在 replication log，其他的 follower 通過這個 log 保持數據與 leader 一致

Sync vs. Async

上圖中，follower 1 is sync, follower 2 is async.

sync

pros: 可以保證 followr 的數據和 leader 的一致，且 leader 掛了的情況下也不丟數據
cons: 如果這個 follower 掛了 (這裡的掛了也可能只是暫時的網路原因)，leader 會 block，可用性較低

async

pros: follower 掛了 leader 可以繼續處理，可用性較高
cons: client 可能讀到 stale 數據，而且由於 follower 沒有完整的 leader 的數據， leader 掛了的情況下數據可能會丟

semi-synchronous

上面兩種方案的折中，一個 follower sync，其他 follower async，這樣首先可以保證 sync follower 有完整的數據副本，leader 掛了數據不會丟。

Node Failure

Follower failure: Catch-up recovery, 基本思想如下：

master 生成 snapshot 給 follower，follower 先恢復 snapshot
follower 請求同步 snapshot 對應 LSN 後的日誌
如果 follower 原本就有數據，只是由於網路中斷/暫時掛機，沒有落後 leader 太多，可以直接日誌複製

Leader failure: Failover

大致流程

確定 leader failed，往往使用 timeout
Leader election
設置整個系統的其他 node 使用新 leader，老 leader 恢復後也要變成 follower

Failover 有許多細節

如果採用的是 async 複製，新 leader 沒有之前老 leader 的部分數據，如果之後老 leader 恢復了，老 leader 的那部分數據咋辦，最簡單的是老 leader 無腦同步新 leader 的數據，丟棄自己的，但這樣整個系統會有丟數據和數據不一致的風險。
split brain 問題
timeout 時長的設置，過低的 timeout 會導致無意義的 failover

Replication Logs

Replication logs 本質是通過狀態機進行複製，根據 log 的內容不同，可以分為如下幾種：

Statement-based replication: 記錄任何寫請求，對 RDBMS 來說，就是 SQL，follower 執行 log中對應的 SQL。但並不是所有語句都是 deterministic。
Write-ahead log (WAL) shipping: 使用底層存儲引擎的 log，但這個就跟底層存儲引擎耦合了。
Logical (row-based) log replication: replication log 記錄的是改變後的數據而不是改變的命令。MySQL 的 binlog 使用這種。

Replication Lag

如果是 asynchronous follower, 從 follower 中讀數據是 eventual consistency.

Read Your Own Write

一個違背 read-your-own-write 的情況

read your own write 的一些實現方法

對可能會被用戶更新的數據走 leader，其他走 follower，e.g. 用戶讀自己的 profile 頁走 leader，讀其他用戶的 profile 也走 follower
記錄上次更新時間，時間窗口小於一定值的走 leader

Monotonic Reads

一個違反 monotonic read 的情況

一個解決 monotonic read 的方法就是讀同一個副本

Consistent Prefix Reads

其實就是違反了因果序，只有在 partition 的情況下才會發生，一個違反 consistent prefix read 的例子

一個解決 consistent prefix read 的簡單方法就是有因果順序的寫同一個 partition

Multi-Leader Replication

multi-leader 往往用在

multi datacenter
client with offline operation (e.g. git)
collaborative editing (e.g. google doc)

multi-leader 類似上面 Consistent Prefix Reads 一樣，會碰過寫操作因果序的問題。

Leaderless Replication

前面的帶 leader 的複製方式都是 client 發送寫請求到 leader，follower 通過 replication log 同步。leader 的作用就是為了保證 write 請求的順序，之後的讀請求可以直接向一個follower 發讀請求。

在 Leaderless (Dynamo-style) 的資料庫中，client 直接發寫請求到多個 replicas，之後讀的時候，也發送讀請求到多個 replicas。

leaderless replication 往往採用如下兩種方法補償，使得數據最終保持一致

Read repair：由於 client 會從多個副本讀數據，它可以發現哪個副本的數據是老的，可以用 client 把從其他副本里讀到的新數據寫到那個是老數據的副本
開一個守護進程負責數據的補償

假設有 n 個節點，客戶端讀寫請求會發往 n 個節點，寫請求要求保證 w 個成功返回，讀請求要求保證 r 個成功返回，w + r > n 可以盡量滿足不會讀到老數據，常見的選擇是 n 為奇數, w=r=(n+1)/2。這麼做要求你能分辨讀到的多份數據裡面，哪份是最新的。（通過使用 version number 實現）

即使 w + r > n，還是有一定可能讀到 stale data

很多實現的 quorum 是 sloppy quoram，
如果兩個 write 是並發的，沒法知道先後
寫成功的節點數量小於 w，這次寫請求失敗，但寫成功的節點不會回滾

基於 quorum consistency 的系統往往用於那些能容忍最終一致性的應用。

Write Conflict

Multi-leader / Leaderless 由於沒有一個單獨的節點確定寫順序，可能會出現 write conflict.

檢測 write conflict：檢測兩個對同一個 key 的修改操作是否有 happen before 的關係，如果沒有，則認為 write conflict。檢測的方法有 Vector Clock。

解決 write conflict 的方式有

conflict avoidance: 根本上避免衝突的產生，比如對 key 按某種規則劃分，特定 key 只能到特定 leader
last write wins：key 更新帶上 timestamp，選取 timestamp 大的數據。由於機器間時鐘有偏差，這種方式會丟數據
把衝突記錄下來，讓應用代碼解決（應用代碼有更多的信息解決衝突）