在 Cluster 架構中，除了 Master Slave 架構外，還有多 Master 架構，該架構主要解決：

• 資料量大到單台資料庫無法負荷，例如記憶體或 CPU 不夠
• 寫入請求量大，需要分流到不同 Server 處理

為解決上述問題要用 Data Sharding 技術，如同 Table Partition 將資料分散到不同 B+Tree 檔案，Data Sharding 也採用類似策略將資料依照 Sharding Key 分散到不同的資料庫。

那什麼是好的 Sharding 策略？

好的 Sharding 策略需滿足：

• 資料均勻分散到不同資料庫
• 新增刪除節點時能降低需移動的資料數

而滿足上述條件且廣泛用於許多資料庫的策略為 Consistent Hashing。

什麼是 Consistent Hashing？

Consistent Hashing 利用 Hash Function 將 sharing key 轉成 hash value，但不是透過取餘數方式分配資料，而是建立一個環狀的空間，將資料分配到該空間中。

(圖來源：https://blog.algomaster.io/p/consistent-hashing-explained)

如上圖， Hash Function 產生 Value 的範圍為 0~2³²-1，將 0 與 2³²-1 相連形成一個環，把資料庫用不同數字代表，並放在環中，而獲得資料的 Hash Value 後順時針尋找，第一個遇到的資料庫就是該資料的歸屬。

但如果 Hash Function 無法平均分散 Hash Value 呢？

Consistent Hash 使用 Virtual Node 的概念，一個資料庫可負責環中不同區段資料，即便 Hash Function 產生的 Value 都坐落在某些區段也能分散到不同資料庫儲存。

(圖來源：https://blog.algomaster.io/p/consistent-hashing-explained)

此外當 Cluster 新增或刪除節點時，只會影響部分區段的資料：

新增 S5 資料庫後，只需將 D 資料從 S2 移動到 S5，其他都不動。

(圖來源：https://blog.algomaster.io/p/consistent-hashing-explained)

同樣刪除也是，除了移動數量少的優點外，資料搬移範圍是可控且可預測的，這在需要動態擴展的 Cluster 架構中是非常大的優勢！

(圖來源：https://blog.algomaster.io/p/consistent-hashing-explained)

Consistent 也並非完美，他的缺點有：

• 資料隨機分散在不同 DB，不像 Range 策略相同區段資料在同個 DB，範圍查詢效能差
• 需使用 Binary Search 在環中查詢到資料對應的 DB，時間複雜度為 O(LogN)，比取餘數的 O(1) 慢

分配好資料到不同 DB 後，Client 如何找到正確的資料庫？

第一種方式可透過集中式 Proxy Server 導流，Proxy Sever 會從外部資料庫獲取 Sharding Metadata，而該資料透過 Cluster DB 寫入。

Sharding Metadata 包含：

• 分片策略（如：Consistent Hashing 或 Range）
• DB 的連線資訊與狀態

儲存 Sharding Metadata 的資料庫需具備：

• 即時一致性，確保所有 Proxy Server 能同時拿到相同的 Metadata
• 有資料備份且能 Auto Failed Over，避免單點故障
  而 etcd 和 zookeeper 具備上述兩點要求，其採用類似 Raft 共識演算法，由一個 Leader 主要負責修改請求，並即時同步修改給所有 Follower，確認Follower 都接收到才會 Commit 修改內容，如果 Leader 故障，可由眾多 Follower 中選出一個新的 Leader。

集中式的優點 是一致性強、運維與更新方便，缺點是會增加一層網路傳輸、增加延遲和單點故障風險，不過 Proxy Server 也可水平擴展。

第二種方式為分散式架構中，每個資料庫都有一份 Sharding Metadata，透過網路協定互相同步，不依賴外部儲存元件，也無需 proxy，Client 可向任一 DB 拉取 Metadata 內容，直接獲取資料位置並發送請求。

例如 Cassandra 透過 Gossip 網路協議，一傳十，十傳百將 Sharding Metadata 廣播給所有 DB，優點是 Client 直連降低延遲，資料分散降低風險，缺點沒有即時一致性，可能導致短暫資料錯誤且實作和維運較複雜。

當 Cluster 發生節點異動時，如何進行 ReSharding？

節點動態擴展時，需要移動資料到新節點，稱為 ReSharding，而 ReSharding 過程必須：

• 不影響線上讀寫
• 搬移有問題時要能 Rollback

Offline 搬移安全簡單，但會影響線上讀寫，所以必須 Online 搬移，同時處理全量與增量同步：

• 全量同步：當前資料 Snapshot 複製過來。
• 增量同步：複製 Snapshot 的過程，資料也不斷在變更，因此異動紀錄也需要同步

假設使用 ShardingSphere 來建立 MySQL Data Sharding 的 Cluster，Resharding 時會用 primary key 分段全量同步，和使用 binlog 增量同步。

資料搬移完後要更新 Sharding Metadata 啟動新 Routing 規則，此時就像部署新的服務一樣，若發現問題要能 Rollback。

但 Rollback 又要把資料搬移回來嗎？

首先 Sharding Metadata 有版本跟狀態，例如 Cluster 剛加入新 DB 時，狀態可是同步中，同步完後更新狀態為啟用，但為了 Rollback 後資料不會出問題，我們可以加一個切換中的過渡狀態。

在該狀態底下，寫入採用 Dual Write，同時寫入舊 DB 跟 新 DB，這樣當新 DB 出問題，Rollback 成舊 DB 時不需要搬資料回來，資料也不會有遺失，而讀取使用 Read Fallback，當新 DB 讀取不到資料時，會往舊 DB 讀取，若 Read Fallback 比例很高，就代表資料搬移到新 DB 出問題，要 Rollback Sharding Metadata。