第五章節：學習要點

[kylemocode]

• DB 的 Replication 主要還是在 Durability, Avaliablity, Latency 之間做一個權衡取捨
• 讀寫分離又可以分為一主多從(single-leader)、多主(muti-leader)、無主 (leaderless)，在權衡這些方法中會遇到許多關於衝突、一致性、延遲的問題，要解決這些問題分別有許多演算法與模式
• 關於無主複製的法定人數： 更一般地說，如果有 n 個副本，每個寫入必須由 w 個節點確認才能被認為是成功的，並且我們必須至少為每個讀取查詢 r 個節點。 。只要 w + r > n ，我們可以預期在讀取時能獲得最新的值，因為 r 個讀取中至少有一個節點是最新的。遵循這些 r 值和 w 值的讀寫稱為 法定人數（quorum）的讀和寫。你可以認為，r 和 w 是有效讀寫所需的最低票數。

[at7211]

（這一篇資訊量好多......待更新）

• 討論如何備份/複製資料，主要目的有這些
  • 機器 shutdown 的時候系統也要 work → high availability
  • 網路中斷也要 work → disconnected operation
  • 地理因素 → latency
  • 個人認為最主要的因素，因為網路應用大部分的時候需求都是讀大於寫，多開些 replication 可以幫忙分散讀的負擔 → scalability
• 最重要的是為了要讓主複資料一致性，這就牽涉到了
  • 如何設計複製的方法
    • single-leader/muti-leader/leaderless replication
  • 這同步的過程會延伸遇到什麼問題（寫入衝突， 複製延時導致資料不一致……..etc)
  • 如何解決這些問題的辦法，其中光是 replication lag 就有以下對應方式
    • Read-after-write consistency
    • Monotonic reads
    • Consistent prefix reads
• Version vectors 是很好處理 replication 之間 conflict 的問題

[jxiu0129]

1. 現有的分散式系統，DB 間的複製主流分法有三種方式
   • 單主
   • 多主
   • 無主
2. 每種複製方式都有延遲問題，此書提到的例子
   • 讀己之寫
   • 單調讀
   • 一致字 prefix
3. 無主複製的一些重點
   • 法定人數一制性
   • 寬鬆的法定人數
   • 提示移交

[0x171-0]

🥲 不好意思有點多...我再慢慢修改收斂...

5.1 領導者與追隨者

為什麼需要複製？

• 減少延遲：地理接近
• 容忍故障與斷網：提高可用
• 可伸縮性：提高吞吐

複製副本的難點

• 什麼是副本(replica)？
  • 存儲數據拷貝的每個節點
• 如何確保副本一致？
  • 同步變更 change？
  • 失敗處理 fail？
  • 如何處理延遲？

複製的架構與配置

分布式數據庫：三種架構

• 單主 single leader
• 多主 multi leader
• 無主 leaderless

分布式數據庫：3 種複製的方式

• 同步 synchronously
  • 作法：主庫會等待從庫響應
  • 優點：能保證一致
  • 缺點：慢
• 異步 asynchronously
  • 作法
    • 主庫不會等待從庫響應
    • 最終一致性
    • 通常基于领导者的复制都配置为完全异步
  • 複製延遲
  • 優點
    • 快
    • 不會因為從庫故障而阻塞
  • 缺點：操作丟失
• 半同步（semi-synchronous）
  • 單一從庫同步，其餘異步

節點間同步的方法

• 鏈式複製（chain replication）
• 共識（consensus）

基於領導者複製 leader-based replication

• 組成

  • 主庫: 只能從該庫寫入
  • 從庫: 只能讀取
    • 類型
      • 热备（hot standby）: 是能接受客户端读请求的副本
      • 温备（warm standby）: 只是追随领导者，但不处理客户端的任何查询

• 如何設置新從庫？

  • 生成主庫快照
  • 將快照複製到新節點
  • 從庫拉取慨照之後的更新日誌並趕上

複製日誌 replication log

步驟

• 主庫產出複製日誌（replication log）
• 從庫拉取日志並趕上

類型

• 基於語句複製

  • 實現方式
    • 主庫記錄每個語句請求並傳送給從庫
  • 可能造成問題的點
    • 自增列（auto increment）
    • 有副作用的语句
    • 非确定性函数（nondeterministic）

• 傳輸預寫式日誌（WAL）

  • 缺點
    • 版本相容性低：複製與儲存引擎緊密耦合

• 邏輯日誌複製（基於行）

  • 應用 : - MySQL 的二進位制日誌
  • 優點 : 版本、引擎相容性高：複製與儲存引擎鬆耦合

• 基於觸發器日誌

  • 優點: 靈活
  • 缺點 : 容易出錯、開銷大

節點故障的應對方法

• 從庫失效：追趕日誌

• 主庫失效：故障切换 failover

  • 步驟
    • 判斷主庫失效
      • Timeout
    • 選擇新主庫
      • 选举过程（主库由剩余副本以多数选举产生）
      • 事先設定控制器节点（controller node）
    • 重新配置客户端
  • 可能的問題
    • 重複分配主鍵
    • 超時的時間設定不恰當，
      • 太長導致恢復時間過程，
      • 太短導致不必要的切換
    • 脑裂 (split brain)
      • 兩個以上節點誤以為自己是主庫
      • 衝突解決機制
        • 檢測到存在兩個主節點時主動關閉一個
    • 舊主庫最後操作丟失

---

5.2 複製延遲的問題 & 解法

讀己之寫 read-your-writes

• 問題 : 以為自己沒更新或操作失敗，但其實有

• 解法 : 使用採用讀己之寫一致性（read-your-writes consistency）

• 作法

  • 對自己修改的內容總是從主庫讀取
  • 禁止讀取滯後主庫超過一定時間的資料
  • 時間可以依客戶更新的時間戳判斷，不應讀取更新時間於該時間戳之前的資料

單調讀 monotonic reads

• 問題 : 時光倒流（moving backward in time）
• 作法 : 確保客戶總是從同一個節點進行讀取（可以透過客戶 ID 散列進行副本的選擇）

一致性前綴

• 問題 :
  • 預知，違反因果律，回答比問題更先出現
  • 容易在分區（partitioned） 或 分片（sharded）中產生
• 解法: 一致性前綴
• 作法
  • 寫入順序 = 讀取順序
  • 確保任何因果相關的內容，都寫入相同分區

---

5-3. 多主複製

• 單點複製的問題

  • 主庫故障或斷線就無法寫入

• 什麼是多主複製？

  • 每個分區都有一個主庫

• 應用場景

  • 運維多個數據中心
  • 需要離線操作的客戶端
    • 協同編輯(很像多主，但事實上是單主)

衝突&處理衝突的方法

什麼是衝突？

• 操作衝突
• 邏輯衝突

檢測方法

• 單主同步檢測
• 多主異步檢測

避免方法

• 確保單一主庫寫入

• 單一用戶單一數據中心

• 使用鎖定編輯

收斂方法

• 最後寫入勝利

• 自定義解決邏輯

  • 寫時執行-自定義函數
  • 讀時執行-用戶自行解決

• 自動解決衝突

  • 無沖突復制數據類型（Conflict-free replicated datatypes，CRDT）
  • 可合並的持久數據結構（Mergeable persistent data structures）
  • 操作轉換（operational transformation）

複製拓墣 replication topology

用來描述寫入操作從一個節點傳播到另一個節點的通信路徑。如果你有兩個主庫

種類

• 全部到全部 all-to-all
  • 缺點
    • 順序錯誤
    • 解法: 版本向量 version vectors
• 環形拓撲（circular topology）
• 星形拓墣 Star Topology

作法

• 每個節點都有獨特標誌符，防止無限循環

---

5-4. 無主複製

What is 無主複製？

• 允許任何副本直接接受來自客戶端的寫入或由一個協調者節點代表客戶寫入

面對節點故障的方法

故障節點重新上線後如何趕上？

• 讀修復（Read repair）
• 反熵過程（Anti-entropy process）

操作成功判斷的公式

• 公式說明

  • 如果有 n 個副本，每個寫入必須由 w 個節點確認才能被認為是成功的，並且我們必須至少為每個讀取查詢 r 個節點。
  • r 值和 w 值的讀寫稱為 法定人數（quorum）

• 常見公式

  • $w + r > n$
  • $w = r = (n + 1) / 2$（向上取整）
  • $w = n$ 和 $r = 1$ 適用寫少讀多的狀況

• 可用性的判斷

• 侷限性

  • 較小的 w 和 r 更有可能會讀取到陳舊的數據
  • 即使在 $w + r > n$ 的情況下，也可能存在返回陳舊值的邊緣情況

• 寬鬆法定移交

監控陳舊度

• 處理併發衝突的方法
  • 最後寫入勝利
  • 捕獲前後今生的關係
  • 合併寫入值
  • 版本向量

[AK4codee]

複製資料的好處

• 減少延遲
• 提高可用性
• 提高讀取吞吐量

如何確保資料完整複製到副本上

• 只有主庫接受寫入，寫入的資料變更會發送給所有從庫 - 複製日誌（replication log） 或 變更流（change stream）。從庫會依照日誌來更新相對應資料數據
• 同步複製與非同步複製：向使用者回應寫入結果（成功/失敗）後，複製資料至其他從庫為非同步，不需等待期回應
• 複製日誌
  • 針對資料庫操作的執行命令，包含 INSERT、UPDATE 或 DELETE
  • 傳輸預寫式日誌
  • 邏輯日誌複製

處理寫入衝突

• 給每個寫入唯一 key，依照更新時間或 ID 排序作為篩選，可能導致資料遺失
• 將多方寫入值合併、連接
• 記錄寫入衝突，並寫出可以處理衝突的方法

[Parkerhiphop]

WHY？ 為什麼要分佈到多台機器上？

1. 可伸縮性 伸縮可以接受讀請求的機器數量。
   • 資料量
   • 讀取負載
   • 寫入負載
2. 容錯 / 高可用性
   • 一臺故障時，另一臺可以接管。
3. 延遲 得資料與使用者在地理上接近
   • 在全球範圍部署多個伺服器
   • 每個使用者可以從地理上最近的資料中心獲取服務
   • 避免等待網路資料包穿越半個世界

     HOW? 使用 Replication 在多台機器上保留相同資料的副本

     Replication 的困難之處在於處理複製資料的 變更（change） 三種主要的 Replication Algo

4. Single Leader
5. Multiple Leader
6. Leaderless
   • 比較
     1. Single Leader 實作起來單純，不用處理 node 的衝突
     2. Mulitple & Leaderless 則能更好地處理「Faulty Node」、「Network Interruption」、「Latency Spikes」
        • 代價：很難推理、一致性很弱

          Replication 延遲時的一致性模型

7. Read-after-write consistency
   • 使用者應該總是能看到自己提交的資料
8. Monotonic Reads
   • 使用者在看到某個時間點的資料後
     • 他們不應該再看到該資料在更早時間點的情況
9. Consistent Prefix Reads
   • 使用者應該看到資料處於一種具有因果意義的狀態
     • 如，按正確的順序看到一個問題和對應的回答

[JimmyFUFU]

• 當 read write loading 大到超過單一機器可以承受的流量就需要多機器的支援，同時需要兼顧 application 和資料的 High availability、Scalability、Latency，單主、多主、無主三種複製方法都各有優缺點，不同 application 的業務邏輯應該會有最適合它的策略
• replication topology circular topology: 有順序問題，容易造成單點故障，mysql 支援 star topology: 有順序問題，容易造成單點故障 all-to-all topology: 最常見，可避免單點故障但有可能會有因每個節點網路快慢而有資料插入順序的問題，可透過 version vectors 解決
• version vectors 版本向量 通過各個節點對資料修改的歷史．來比較新舊數據，最主要可以解決資料 conflict 的問題，各節點可以有自己的邏輯時間，並不要求每個節點的資料ㄧ致

[samwu4166]

複製要點:

• 使得資料與使用者在地理上接近（從而減少延遲） => 可以想像 CDN 就是複製很多 Static file 到不同地理位置的節點
• 即使系統的一部分出現故障，系統也能繼續工作（從而提高可用性）=> 資料的 Replication 來達到 Availability
• 伸縮可以接受讀請求的機器數量（從而提高讀取吞吐量） => 也是應付高流量下的 Availability

主要的三種方法:

1. Leaderless
2. Multi Leader
3. Single Leader

有 Leader 的主要寫入機器常稱為 Master, 而 Follower 則是 Slave, 所以才會常聽到 Master-Slave, Dual Master ... etc.

同步複製和非同步複製是設計系統很重要的議題，常見的問題及是在分散式設計下的 FB 要怎麼在最短的時間內把 Post 散步到世界上的 Read-Slave 中。

然後設定 Master 完全一樣的 Replica 通常會用 DB Snapshot 的方式實作，每次快照會去 Catch up 到最新的進度。而在失效處理的方面上，從庫會比較簡單的多，就從當機到啟動那段時間的進度需要追趕，不過如果是主庫死掉那就會讓整個系統爛掉，所以才衍生出 Dual Master 這種架構，這時候另一台的 Master 幾乎就是 100% replica of Master 而且通常只提供 Read-only 或是什麼服務都不提供。

為了達到 【寫後讀一致性（read-after-write consistency）】，比較簡單的就是使用者自己的檔案都從主庫讀取，但是如果大部分的 Read 請求都是從瀏覽自己資料，就是重新設計一下規則或是 Request routing ... etc. 另外要避免 【時光倒流】的方法則是對使用者讀的 Slave 進行雜湊分區，避免在多次讀取中讀到很多不一樣的 Slave。

[taco0929]

• 單主多從：
  • 避免一資料庫毀損而導致服務失敗：追趕恢復、故障切換
  • 時光倒流 -> 單調讀
  • 複製延遲 -> 讀己之寫
• 多主數據庫
  • 比單主數據庫減少更多的寫入時間
  • 可容忍故障與單一數據庫停機
  • 可容忍網路延遲
  • 應用：日曆、行事曆等
• 自動衝突解決
  • 無衝突複製數據類型
  • 可合併的持久數據結構
  • 操作轉換

[kkshyu]

1. 不要隨便挑戰 multi-master
2. 離線操作問題等價於多主複製問題，協同操作問題則是等價於單主同步操作問題
3. 盡可能讓應用層無須擔心資料庫複製問題

PS. 無主複製幾乎看不懂是正常的嗎ＸＤ