動的リバランス

クラスターのスケールアウトやノード障害時に、データは旧配置から新配置へ移行する必要があります。優れたリバランスは、必要な最小限のデータのみを移行し、読み書きを中断しません——一貫性ハッシュのバーチャルノードにより、このプロセスは分散化されます。

概要

一貫性ハッシュとシャーディング戦略は、「データをノードにどのように分散させるか」を解決します。しかし、クラスターのスケールアウト（ノード追加）やスケールイン（ノード障害/オフライン）が発生すると、データは旧配置から新配置へ移行する必要があります——これがリバランス（rebalancing）です。悪いリバランス方案では、必要以上の大量のデータを移行したり、移行中にサービス拒否（DoS）状態に陥ったりする可能性があります。優れたリバランスは必要な最小限のデータのみを移行し、⁠読み書きを中断しません⁠。

3つのリバランス戦略

固定パーティション: シンプルだが粗雑

ノード数をはるかに超える数のパーティションを事前に作成します（例: ノード1つあたり100パーティション、10ノードで合計1000パーティション）。パーティション数は不変です。ノードを追加すると、各旧ノードから一部のパーティションを新ノードへ割り当てます。

ノード追加前: Node-1: [p1..p100],  Node-2: [p101..p200], ... Node-10: [p901..p1000]
ノード追加後: Node-1: [p1..p90],   Node-2: [p91..p180],  ... Node-11(新): [p901..p990]

• 移行粒度: パーティション単位（N個のキーを一括で移動）。キー単位ではありません。
• 欠点: パーティションサイズとノード数が強く結合されている⁠——初期推定がずれた場合（パーティションが大きすぎたり小さすぎたり）、後から調整が困難です。また、パーティション数は静的であるため、データ量の増加に応じて分割できません。

Redis Clusterはこの方案を採用しています: 16384個の固定スロット。

動的パーティション: データの増加に伴いパーティションが分割

各パーティションにサイズ上限（例: 10GB）を設定し、これを超過すると2つの新しいパーティションに分割されます。ノード数が増減すると、パーティション全体が新ノードへ移行します——固定パーティションと同様ですが、パーティション数自体が動的です。

パーティション p3 が 10GB に到達 → p3a と p3b に分割（それぞれ約 5GB）
移行が必要 → p3a 全体を新ノードへ移動

• 利点: パーティション数は総データ量に比例するため、固定パーティションのような「事前に多すぎたり少なすぎたりする」という問題が発生しません。
• 代償: パーティションのメタデータ（どのパーティションがどのノードにあるか、どのパーティションが分割中か）を追跡するための集中型コーディネーターが必要です。HBaseはこの方案を採用しています。

一貫性ハッシュ + バーチャルノード: 分散型リバランス

一貫性ハッシュでは、各物理ノードが複数のバーチャルノード（vnode、例: ノードあたり約100個）に対応し、これらはハッシュリング全体に分散されます。ノードを追加すると、新ノードがリングに挿入され、自身のvnodeがカバーするトークン範囲（隣接ノードのvnodeから一部を割り当て）を引き継ぎます。ノードを削除すると、そのvnodeに対応する範囲は隣接するvnodeが引き継ぎます。

ノード N11（v1101..v1200 の vnode を持つ）をリングに追加:
  元のトークン [5000, 5200] は N3 の v303 にあった
  現在 v1101 が [5000, 5200] をカバー → この範囲は N3 から N11 へ移行
  新ノードの範囲内にあるキーのみを移行し、他のキーは移動しない

• 最小限の移行量⁠: 新vnodeの範囲内に落ちるキーのみを移行し、パーティション全体を移動しません。
• 分散型⁠: 各ノードはGossipプロトコルを通じてグローバルなルーティングテーブルを知っており、コーディネーターに依存せずに、自身がどの範囲を引き継ぐべきかを独自に計算します。
• 代償: 移行粒度は単一vnodeがカバーする範囲であるため、ホットスポット（特定のvnodeの範囲にデータが偏る）が発生する可能性があります——解決策はvnode数の動的調整または負荷に応じたvnodeの分割⁠（Cassandraのvirtual node splitting）です。

移行のエンジニアリング: 中断なくデータを移動する方法

どの戦略であっても、実際のデータ移動プロセスにはいくつかの一般的なプラクティスがあります。

ダブルライト（二重書き込み）による移行

移行期間中、新旧両方のノードがその範囲に対する書き込みを同時に受け付けます⁠：

1. メタデータ更新: 範囲 [5000, 5200] を N3 から N11 へ移行
2. 移行期間: 読み書きは引き続き N3 へ送信され、N3 は新しい書き込みデータをストリーミングで N11 へ転送
3. N11 が完了シグナルを受信 → メタデータ更新: [5000, 5200] は N11 の所有物となった
4. 以降の読み書きは直接 N11 へ送信

ダブルライトにより、移行中でも書き込みの消失を防ぎます：新ノードが完全に準備できていなくても、旧ノードがサービスを提供し続けます。Cassandraの nodetool move / decommission がこの方式を採用しています。

スロットルと優先度

データ移行はネットワークとI/Oを消費します——業務ピーク時にフルスピードで移行すると、通常の要求が遅延したり失敗したりする可能性があります：

• スロットル⁠: 移行帯域幅を制限する（例: Cassandraの stream_throughput_outbound_megabits_per_sec）。
• オフピーク移行⁠: 手動でトリガーし、低負荷時に実行する。
• 増分再同期⁠: まずフルスナップショットを転送し、移行期間中に発生した新しい書き込みを転送する（MySQLのbinlog追従に類似）。

一貫性に関する落とし穴

移行期間中、1つのデータのN個のレプリカが新旧の配置を跨ぐ可能性があります——一部のレプリカは旧ルーティングに従い、一部は新ルーティングに従います。解決策はデータを先に移行し、ルーティングメタデータを切り替えることです（アトミックな切り替えであり、レプリカごとに切り替えるわけではありません）。あるいは、Cassandraのように、読み取り時に新旧両方の場所からデータを取得する方法もあります（移行期間中は短時間、二重ルーティングが存在します）。

トレードオフと失敗パターン

• 全量再分散⁠: ノードを1つ追加するたびにすべてのキーを再ハッシュする → 移行量 = 全データ/N で、無意味な移行が大量に発生します。一貫性ハッシュまたは固定パーティション + パーティション移動を常に使用してください。
• ホットスポットvnode: 特定のvnodeがカバーする範囲にデータが偏り、移行時にボトルネックとなる → vnodeのサイズを監視し、動的に分割する。
• 移行中のデータ消失⁠: ルーティングを先に切り替えてからデータを移動する → 常にデータを先に移動し、ルーティングをアトミックに切り替える。
• 移行嵐⁠: 一度に多数のノードを追加し、同時に移行が発生してクラスターが押しつぶされる → ノードを1つずつ追加し、毎回リバランスが完了するのを待ってから次のノードを追加する（Cassandra推奨）。

参考文献

• 論文⁠: "Dynamo" (一貫性ハッシュによるリバランス, 2007)

Keywords: rebalancing, 固定パーティション, 動的パーティション, hash ring, virtual node, vnode, データ移行, 最小移行量, ダブルライト移行, 漸進的移行, スロットル, atomic routing switch, hotspot vnode