分散式系統之 Partition

02-02

這是 Designing Data-Intensive Applications 第六章的學習筆記，主要講 Partition。

Partitioning 方案

Partitioning by Key Range

pros:

每個 shard 內都可以保持 sorted，適合範圍查詢

cons:

不好均分，特定 access pattern 會導致 hot spot。比如按照 timestamp 劃分，寫入時採用當前時間會導致所有寫入都在一個 Partition。

Partitioning by Hash of Key

pros:

數據均分，不容易產生 hot spot。但一定的 access pattern 還是可能導致 hot spot 的產生，比如按 user id 做 hash，大 V 所在的 partition 就是 hot spot。

cons：

沒法做範圍查詢

Secondary Index

Partitioning Secondary Indexes by Document

每個 partition 都維護了自己的二級索引

pros:

每個 partition 都維護了自己的二級索引，這樣寫只要寫一份

cons:

二級索引查詢需要查所有 partition

Partitioning Secondary indexes by Term

對於二級索引需要的 key，類似 primary key 一樣，用 range / hash 的方式做 partition。比如下圖中，color a-r 開頭的在一個 partition 0，s-z 的在 partition 1，make A-F 在 partition 0，make G-Z 在 partition 1.

pros:

讀操作知道需要讀哪幾個 partition，不需要向所有 partition 都發送讀請求。

cons:

一個寫操作可能會影響多個 partition，對應需要更新這些 partition 的索引。

Rebalancing Partitions

hash mod N: 實現起來簡單粗暴，但一個 node 的增減 (N 變化) 會導致大量 key 移動。一個簡單的優化是將 N 保持不變，與具體節點數解耦。這樣新加入節點只要從之前的節點拿幾個 partition 過來就行，不會導致大量 key 移動。

Dynamic partitioning: 會根據一定 partition 上 key 過多/多少，split / merge

Request Routing

除了簡單的 hash mod N 方案，其他都有一個問題：client 如果知道哪個 key 在哪個 partition 上？

這個問題的常見幾種解決方案：

發往任意一個節點，如果這個節點有 client 需要的 partition，響應 client 的請求，如果沒有，則把請求轉發到其他節點
把請求發往一個 proxy，這個 proxy 決定把請求轉發到哪個節點。
client 知道哪個 partition 在哪個 node

每種方案都繞不過一個問題：當 partition 改變的時候(rebalancing partition)，對應幾種方案的 node，proxy，client 怎麼感知這種變化。

這是一個服務發現的問題（本質上又是一個 consesus 問題），一般都依賴 zookeeper，etcd 實現。