本文為 Design Data Intensive Applications 的書摘 + 個人心得。
Rebalancing Partitions
每經過一段時間，資料庫可能會因為以下幾件事情改變：
- 為了想提高查詢的吞吐量，所以你加了 CPU。
- 資料的大小增加了，所以你需要加更多記憶體。
- 一台機器或某幾個資料硬碟壞了，其他的機器得接手它們的工作。
這些改變都會需要將資料和 request 從一個節點移到另一個節點上，這個過程稱之為 rebalancing。
不管你採用何種 partition schema，rebalancing 起碼得達成以下需求：
- rebalancing 之後，負載 (資料、讀取和寫入需求) 應該要能平均分散之各台節點上。
- rabalancing 過程中，資料庫應能正常處理讀取和寫入。
- 最小化資料在節點間的搬移，減少網路和硬碟 IO。
所以接下來會講做 rebalancing 時有哪些策略。
Strategies for Rebalancing
Fixed number of partitions
這個方法需首先先在每台節點上固定 partition 數量，舉例來說假設叢集有 10 台節點，我們可以指定 partition 的量為 1000 個，如此每台節點大約會有 100 個 partition，然後當節點增加時，這個新的節點會去每一台節點中 偷 一些 partition 回來，直到整個叢集的 partition 分佈變平均為止，這個過程如下圖。
這個 rebalancing 策略被使用在 Riak, Elasticsearch, Couchbase 和 Voldemort。
這裡最大的難處就是如何在一開始就選一個對的 partiton 數量，資料會隨時間比例的成長，如果 partition 設很大，做 rebalancing 或節點從掛掉到恢復都是昂貴的，但 partition 設很小，每個 partition 又容易 overhead。
Dynamic partitioning
如果資料使用 key-range partition，固定的 parition 數量會非常不方便，容易發生邊界錯誤，這就會導至這些資料都只流到一個 partition 裡，然後其他 partition 就空了。
所以使用 key-range partition 的 HBase 和 RethinkDB 就使用 dynamic partition，當 partition 的資料大小成長到某個門檻值後，它會分裂成 2 個差不多一半大小的 partition，反過來說資料大小小於某個門檻值，它會合併鄰近的 partition，這個過程很像 B-Tree and comparing LSM-Trees 提到過的 B-Trees。
dynamic partitioning 的好處就是它能隨著整體的資料量做 partition 調整，資料不大時使用小量的 partition 是很有效率的，但要留意的是，當你新建資料庫時，初期你的資料量小所以只會有 1 個 partition，然後其他節點就會閒置了，為了減輕這個狀況，HBase 和 MongoDB 允許設定初始的 partition 數量 (也稱 pre-spiling )。
最後 dynamic partitioning 也適合用在 hash-partitoin 上。
Partitioning proportionally to nodes
上面講的 fixed number partition 和 dynamic partitioning 的 partitoin 數量都是跟資料大小成正比，也就是說，這 2 個策略都跟每個節點該放多少個 partition 無關。
第三個 partition 的策略是用在 Cassandra 和 Ketama，partition 的數量是跟節點數量成正比，換句話說就是每個節點的 partition 數量會固定，這個方法會保持每個 partition 的大小是相對穩定的。
當一個新節點加入時，它會隨機選固定數量的 partition 做 split。
Operations: Automatic or Manual Rebalancing
最後一個要探討的問題是該自動還手動做 rebalancing？
全自動 rebalancing 或許很方便，但它是不可預測的，rebalancing 是很昂貴的操作，因為它需要 rerouting request 和在節點搬移大量資料，一不小心可能會網路過載和影響 request 的 performance。
自動 rebalancing 也可能會造成意想不到的危害，舉例來說一個節點過載了然後回覆變慢，其他節點可能會認為它已掛掉，然後自動 rebalancing 會開始作業，把負載 (資料、讀取和寫入需求) 從過載節點轉到其他節點上，進而造成過載節點工作量更重，然後大家一起掛掉。
所以，書中建議手動執行，雖然比自動慢，但更能避免意外。
Request Routing
partitioning 的最後一個段落想講的問題：如果我想寫入或讀取 foo 這個 key，我該連哪個節點？
我們稱這個一般化的問題為 service discovery (服務發現) ，其實這個問題其實不只資料庫會遇到，只要是分散式系統都會有，尤其想以 high availability (高可用性) 為目標的系統。
我們有 3 個 routing 方法回答 client 這個問題，如下圖：
- 讓 client 隨便連一個節點 (ex: 用 round-robin load balancer)，然後如果剛好中了就直接查該節點，要不就 forward 到對的節點，然後在 pass 該節點的結果回去。
- 建一個 routing tier ，然後用它負責接所有想知道 partition 在哪個節點上的 request。
- client 有能力知道他該去哪裡，然後直接連該節點，這個方法需要 client 知道每個節點各被分派了哪些 partition。
Ok，現在有個新問題是，要怎麼讓這 3 個 routing 方法知道節點被分派了哪些 partition？
許多分散式系統都會依賴一個協調服務像 ZookKeeper 來幫助它們追蹤叢集的 metadata，如下圖所示，每個節點需要跟 ZooKeeper 註冊並告知它 partition 的資訊，然後由它教上面講的 3 個 routing 方法，也就是黑色線的部份。
最常見用 ZooKeeper 來當 partition 分配管理的就是 Kafka, HBase 了，我們公司開發的數據系統也是使用 ZooKeeper 做 service discovery，只是現在會慢慢轉移到 Consul 上了。
另外，Cassandra 使用了不同的方法，他們使用 gossip protocol 來傳播節點中所有的叢集變化，request 來的時候會送到任一節點，然後在 forward 到對的節點 (等於圖 6-7 的方法 1)，這個模型的好處就是不需要依賴一個外部的服務。
