動的リバランス

リバランスとは、既存のデータとサービス責任を現在の配置から目標の配置へ調整することです。トリガーには、スケールアウト、スケールイン、ホットスポット、および障害復旧が含まれます。これには「何を移動するか」「いつターゲットサービスに切り替えるか」「障害発生時に何に基づいて復旧するか」という3つの問題が関与します。

「一貫性ハッシュは所属先をわずかにしか変更しない」というのは、最初の質問の一部にしか答えていません。移行は、ルーティングテーブルを変更してファイルをコピーするだけではありません。コピーの間、ビジネスデータは継続的に変更され、古いクライアントは引き続き元の位置にリクエストを送信する可能性があります。

移行の粒度：固定パーティション、動的分割、トークン範囲

例えば、1000個の等しいサイズのパーティションが元々10台のマシンに均等に配置されていたとします。新しいマシンが1台追加された場合、各元のマシンから9個のパーティションを移動させることができます。その結果、元のノードはそれぞれ91個、新しいノードは90個になり、合計は依然として1000個です。すべてのパーティションを連続して再番号付けする必要はありません。移動対象のパーティションの所有者を更新するだけで十分です。

これは等しいサイズを想定した教育用の例です。実際のスケジューリングでは、バイト量、読み書き速度、ディスク容量、障害ドメインも考慮する必要があり、パーティション数だけで平均化することはできません。ホットスポットを解消するためには、純粋な容量均衡よりも多くの移行が必要になることもあります。

分割と移行は異なります：分割は論理境界を変更し、移行は配置位置を変更します。1つのパーティションが2つに分割されても、元のマシン上にそのまま残すことができます。境界が安定してから、そのうちの1つを移動します。メタデータはレプリケーションされたコントロールプレーンによって管理できるため、必ずしも単一の障害耐性のない中心ノードに依存する必要はありません。

なぜ「先にコピーしてからルーティングを変更する」だけでは不十分なのか

コピー開始時に x=1 であり、コピー中にユーザーが x を 2 に変更したとします。もしターゲットにコピーされるのがスナップショット内の 1 のみであれば、ルーティングを切り替えた後に古い値が読み取られてしまいます。新旧のノードに同時に書き込む場合、旧ノードは成功し新ノードがタイムアウトした場合、両方の位置で依然として不整合が発生する可能性があります。

正しいプロトコルは、以下の質問に答える必要があります：どのログがこの更新を記録しているか？ターゲットはどの位置から補完するか？タイムアウト再試行は重複して適用されるか？スナップショット内の古いレコードが先に到着した新しい値を上書きしないか？削除はどのように同期されるか？これらの問題は、「二重書き込みでデータ消失を保証する」という一言で片付けることはできません。

推論可能な単一書き込み者移行プロトコル

以下では、ソース S、ターゲット T、およびバージョン付きルーティングを用いて一般的な設計を記述します。システムが移行状態を永続的に記録し、書き込み権限を制約できると仮定します。これはすべてのデータベースが採用している固定実装ではありません。

スナップショットはログの境界に対応しなければならない

一貫性のあるスナップショットを取得し、ログ位置 L0 を特定します。スナップショットはその境界までの状態をカバーし、増分はそれ以降の変更をカバーします。ターゲットはまずスナップショットをロードしてから増分をリプレイするか、信頼できるバージョンルールでマージし、古いスナップショットが新しい更新を上書きしないようにします。ログの保持期間は十分に長くする必要があります。そうしないと、ターゲットが追いつく前に必要な増分が回収され、スナップショットを再構築せざるを得なくなります。

リプレイには、回復可能な位置と冪等性セマンティクスが必要です。同じバージョンへの重複書き込みは識別可能である必要があります。削除は、ログイベントや tombstone などの形式で伝播しなければならず、ターゲットがレコードを見ていないからといって、削除がすでに同期されていると見なしてはいけません。

ターゲットコピーがギャップと遅延スナップショットを拒否する方法

スナップショットが位置 10 に対応し、状態が {x:1,y:9} であるとします。その後、ログ 11 で x が 2 に変更され、12 で y が削除されます。以下では、これが Watch のように他のキーのバージョンをスキップできるものとは異なり、専用で位置が連続したパーティションログであると仮定します。各適用はデータと位置の両方を同時に公開します。実際のストレージでは、トランザクションまたは回復プロトコルを使用してこのアトミック関係を維持する必要があります。

class Target:
    def __init__(self):
        self.position = None
        self.data = {}

    def install_snapshot(self, position, data):
        if self.position is not None:
            raise ValueError("このタスクはすでにスナップショットをインストールしており、増分後の状態を上書きできません")
        self.data, self.position = dict(data), position

    def replay(self, position, operation, key, value=None):
        if self.position is None:
            raise ValueError("まずスナップショットを完全にインストールしてください")
        if position <= self.position:
            return False  # 同じタスク、同じログIDにおける履歴のリプレイ
        if position != self.position + 1:
            raise ValueError("ログにギャップがあります。スキップできません")
        updated = dict(self.data)
        if operation == "put":
            updated[key] = value
        elif operation == "delete":
            updated.pop(key, None)
        else:
            raise ValueError("不明なログタイプ")
        self.data, self.position = updated, position
        return True

target = Target()
target.install_snapshot(10, {"x": 1, "y": 9})
assert target.replay(11, "put", "x", 2)
assert not target.replay(11, "put", "x", 2)
try:
    target.replay(13, "put", "z", 3)
except ValueError:
    pass
assert target.position == 11 and "z" not in target.data
assert target.replay(12, "delete", "y")
assert target.data == {"x": 2}
try:
    target.install_snapshot(10, {"x": 1, "y": 9})
except ValueError:
    pass
assert target.data == {"x": 2} and target.position == 12

このモデルは、「スナップショットの完全なインストール後にのみリプレイを開始する」という直列戦略を採用しています。したがって、12 の削除は、このタスク内の古いスナップショットを防ぐために永遠に tombstone を保持する必要はありません。古いスナップショットのインストール自体が拒否されているためです。もし無順序ブロックと増分の並列マージを許可する場合、x の巻き戻しや y の復活を防ぐために、より細かなバージョンルールが必要です。

同じ position は、不変のログレコードの1つだけに該当する必要があります。実際のシステムでは、移行タスクID、ソースログID、スナップショットチェックサム、および範囲を検証する必要があり、別のタスクの位置 11 を処理済みとして扱ってはなりません。例では位置はメモリ内のみで、プロセスまたはディスクのクラッシュはシミュレートされていません。永続的な実装では、「position は 12 に達したが、削除はまだ保存されていない」という状態が残らないことを確実にする必要があります。

データの追従後、書き込み権限の引継ぎが必要

「ターゲットの遅延がゼロである」のは、ある時点での観察に過ぎません。ソースは次の瞬間にも新しい書き込みを受け付ける可能性があるため、明確な切り替えバリア Lcut が必要であり、古い書き込み者が制約のない成功する書き込みを生成できないように保証する必要があります。

単純な実装では、切り替えウィンドウ中にこの範囲への新しい書き込みを一時的にブロックし、受け付けられた操作の完了を待ち、ターゲットが Lcut まで適用してから新しいルーティングバージョンを公開します。より複雑な実装では、転送、ログプロトコル、またはレプリケーショングループの再構成によって中断時間を短縮できますが、それでも古い書き込みが漏れないことを証明する必要があります。

エポックは権限の世代です。リクエストに古いバージョンが含まれている場合、サーバーはプロトコルに基づいて拒否または転送を行うべきです。クライアントがキャッシュを更新するだけでは、復旧後もマスターであると認識し続ける古いプロセスを隔離するには不十分です。権限チェックは、実際に書き込みを受け付けるリソースの境界で実施されなければなりません。

「先ほど追従した」と「バリア後に追従した」には1回の書き込みの差がある

t1 でソースとターゲットの両方が 12 であると観察されたとします。t2 でソースがログ 13 を受け付け、t3 でコントローラが t1 の観察に基づいて直接ルーティングを切り替えた場合、ターゲットはすでに成功した 13 を欠落します。ラグゼロは瞬間的な写真であり、その後の書き込みを禁止するバリアとして機能することはできません。

有効なバリアを確立する鍵は、古い権限による新しい書き込みの受け付けを先に停止し、すでに受け付けられた在途操作を処理することです。これにより、増加し続けることのない Lcut を得ることができます。最後に受け付けられた操作が 13 である場合、ターゲットは 13 まで追従しなければなりません。以前ソースの末尾 12 まで追従していたからといって、早期に有効化することはできません。この短時間の書き込み拒否ウィンドウは、この単純化されたプロトコルが明確な引継ぎ境界を得るために支払う可用性のコストです。

ルーティングの公開にはアトミックな決定があり、クライアントは同時に更新されない

メタデータ内に明確な所有権切り替えポイントが存在する場合でも、クライアント、プロキシ、およびロングコネクションが新しい状態を認識するタイミングは異なります。そのため、古いエントリポイントは遷移動作を行う必要があり、ネットワーク全体のルーティングが瞬時に一貫すると仮定してはいけません。リダイレクトと転送は回数を制限する必要があり、2つのノードがお互いを指し合ってループを形成しないようにします。

コピーの移行は、投票メンバーを直接置き換えることを意味しません。Raft などのレプリケーショングループは、独自のメンバーシップ変更プロトコルを使用して quorum の安全性を保証する必要があります。移行ツールは、それ自体が新しいコピーに完全な権限があることを宣言するために、それを迂回することはできません。

先ほど追従したからといって、今すぐ切り替えられるわけではない

ターゲットを先に追従させ、ソースに1回書き込むことで、「ラグゼロの後に再び遅れる」という反例を構築できます。フリーズボタンには、受け付けの停止と在途書き込みの完了が含まれ、固定された Lcut を得ます。これはクライアントがルーティングキャッシュを更新するものではありません。新しい所有者を公開する前に、古い権限がすでに隔離され、ターゲットがバリアをカバーしていることを同時に満たす必要があり、切り替え後も古いソースを有効な書き込みエントリポイントとして扱ってはなりません。

障害復旧：永続状態が次のステップを決定する

切り替え前には通常、移行を停止してソースサービスを維持できます。切り替え後、ターゲットが新しい書き込みを受け付けている場合、古いコピーを直接有効化して「ロールバック」として使用することはできません。ターゲットの新しい変更を同期し、権限を再引継ぎする必要があります。

容量とレートリミット：追従は新增分よりも速くなければならない

スナップショットサイズを D、有効なレプリケーション帯域幅を b とします。圧縮やその他のボトルネックを考慮しない場合、フルデータフェーズには少なくとも D/b が必要です。その後、バックログが B あり、増分の発生率が r、ターゲットの有効適用率が a である場合、安定したレートでの単純化されたモデルでは、追従には約 B/(a-r) 必要です。ただし、a>r という条件があります。a≤r の場合、待っているだけでは追いつけません。

したがって、レートリミットはネットワークだけを見てはいけません。ディスクレイテンシ、ライト増幅、CPU、ログ保持スペース、ターゲット適用率、およびフロントエンドリクエストのテールレイテンシも監視する必要があります。スケジューリングは並列移行範囲を制限し、障害復旧用の容量を予約し、サービス指標が悪化すると一時停止する必要があります。すべてのシナリオで1台ずつスケールアウトする必要はありません。並列度はリソース予算とプロトコルの制限によって決定されるべきです。

Redis Cluster：一時的な転送と所属変更の区別

Redis Cluster は 16384 個のハッシュスロットを使用し、スロットとノードのマッピングは変化することがあります。移行に関連するクライアントプロトコルにおいて、ASK はこのリクエストを一時的に指定されたノードで実行する必要があることを示し、ASKING と組み合わせて使用されます。これは、そのスロットの長期ルーティングを直接新しいノードに変更することを要求するものではありません。MOVED は、スロットの所属に関する認識を更新すべきであることを示します。これは、移行中の一時的なサービス位置と安定したルーティングを混同してはならないことを示しています。Redis Cluster 仕様

以下の純粋なルーティングモデルを使用して、2種類の応答を区別します。スロット 8 は当初 S にキャッシュされています。ASK を受け取ったときは、このリトライ計画のみを生成し、MOVED を受け取った場合にのみ安定したスロットキャッシュを更新します。

routes = {8: "S"}

def redirected(kind, slot, target):
    if kind == "ASK":
        return target, True   # ターゲット接続上で ASKING を実行し、このリクエストを送信
    if kind == "MOVED":
        routes[slot] = target
        return target, False
    raise ValueError("サポートされていないリダイレクトタイプです")

assert redirected("ASK", 8, "T") == ("T", True)
assert routes[8] == "S"  # 次の独立したリクエストは依然として S を最初に試行
assert redirected("MOVED", 8, "T") == ("T", False)
assert routes[8] == "T"

ASKING は接続上での1回限りの許可であり、1つの接続で ASKING を送信し、プールから別の接続を取得して元のリクエストを送信することはできません。実際のクライアントは、2つのコマンドが同じ接続上で正しく連携されることを保証し、リダイレクト回数と全体のデッドラインを処理する必要があります。ここではスロットキャッシュの変化のみをシミュレートしており、接続プール、コマンド実行、または全スロットテーブルの更新は実装されていません。後者は MOVED 後に一般的に使用される更新方法です。ASK とクライアントルーティングセマンティクス

この例はルーティング引継ぎを理解するためのものであり、Redis が上記の完全なスナップショットとログ移行フローを採用していることを意味するものではありません。

続きを読む：一貫性ハッシュ、シャーディング戦略、障害検出。

参考

• Redis Cluster 仕様：スロット、移行、およびクライアントリダイレクト。
• Raft 論文：レプリケーショングループメンバーシップ変更の安全性。

Keywords: リバランス, リシャーディング, スナップショット, ログ追従, フェンシング, エポック, ルーティング, ASK, MOVED