--- title: 動的リバランス url: https://doc.liz6.com/ja/distributed-systems/04-partitioning-and-routing/03-dynamic-rebalancing locale: ja area: distributed-systems tags: - distributed-systems - partitioning-and-routing date: 2026-06-30 modified: 2026-07-16 description: クラスターのスケールアウトやノード障害時に、データは旧配置から新配置へ移行する必要があります。優れたリバランスは、必要な最小限のデータのみを移行し、読み書きを中断しません——一貫性ハッシュのバーチャルノードにより、このプロセスは分散化されます。 --- # 動的リバランス > クラスターのスケールアウトやノード障害時に、データは旧配置から新配置へ移行する必要があります。優れたリバランスは、必要な最小限のデータのみを移行し、読み書きを中断しません——一貫性ハッシュのバーチャルノードにより、このプロセスは分散化されます。 ## 概要 [一貫性ハッシュ](/distributed-systems/04-partitioning-and-routing/01-consistent-hashing.md)と[シャーディング戦略](/distributed-systems/04-partitioning-and-routing/02-sharding-strategies.md)は、「データをノードにどのように分散させるか」を解決します。しかし、クラスターのスケールアウト（ノード追加）やスケールイン（ノード障害/オフライン）が発生すると、データは**旧配置から新配置へ移行**する必要があります——これがリバランス（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はこの方案を採用しています。 ### 一貫性ハッシュ + バーチャルノード: 分散型リバランス [一貫性ハッシュ](/distributed-systems/04-partitioning-and-routing/01-consistent-hashing.md)では、各物理ノードが複数のバーチャルノード（vnode、例: ノードあたり約100個）に対応し、これらはハッシュリング全体に分散されます。ノードを追加すると、新ノードがリングに挿入され、自身のvnodeがカバーするトークン範囲（隣接ノードのvnodeから一部を割り当て）を引き継ぎます。ノードを削除すると、そのvnodeに対応する範囲は隣接するvnodeが引き継ぎます。 ``` ノード N11（v1101..v1200 の vnode を持つ）をリングに追加: 元のトークン [5000, 5200] は N3 の v303 にあった 現在 v1101 が [5000, 5200] をカバー → この範囲は N3 から N11 へ移行 新ノードの範囲内にあるキーのみを移行し、他のキーは移動しない ``` - **最小限の移行量**: 新vnodeの範囲内に落ちるキーのみを移行し、パーティション全体を移動しません。 - **分散型**: 各ノードは[Gossipプロトコル](/distributed-systems/05-members-and-discovery/02-gossip-protocol.md)を通じてグローバルなルーティングテーブルを知っており、コーディネーターに依存せずに、自身がどの範囲を引き継ぐべきかを独自に計算します。 - 代償: 移行粒度は単一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*