仮想ノードを用いたコンシステントハッシュリングの実装方法とは？

問題とスコープ

文字列キーを物理ノードにルーティングするためのリングを実装します。APIは addNode(nodeId, weight)、removeNode(nodeId)、および getNode(key) です。ノードは weight × V 個の仮想トークンを受け取ります。ここで、V は設定されたベースカウントです。決定論的な64ビットハッシュ抽象化を使用し、衝突を安全に処理し、キーから時計回りで最初の有効なトークンを返します。リングが空の場合、getNode はノードなしを返します。

これはコーディング問題であり、完全なメンバーシップやレプリケーションのサービスではありません。メンバーシップの更新は呼び出し側によって直列化されることを前提としています。解答では、ノードの参加や削除がなぜ近隣のキー区間のみを変更するのか、そしてその特性が機能しなくなる状況（ホットキーや不適切に選択されたハッシュなど）を説明する必要があります。

面接官がテストしていること

PracHubはこれを、addNode、removeNode、getNode、仮想ノードのバランシング、衝突処理、および計算量分析を含むDoorDashのソフトウェアエンジニア技術スクリーニングの質問として記録しています。最近のDoorDashの公開面接記録でも、ラウンドロビンロードバランサーの修正とコンシステントハッシュの実装について説明されています。

評価されるシグナルは、実行可能なデータ構造設計です。ソートされたルックアップ、安定したトークン識別性、重複に対して安全な更新、明確な不変条件、ラップアラウンドやメンバーシップ変更に対するテストなどが含まれます。MITの原著論文では、有用な特性としてバランス（balance）と単調性（monotonicity）が定義されています。割り当ては合理的に均等であるべきであり、バケットを追加しても、古いバケットに残ることができるキーを再マッピングすべきではありません。

回答前の明確化のための質問

ノードIDは一意であり、再起動後も安定していますか？ 1つの物理ノードに属するトークンを正確に削除するには、安定したIDが必要です。
weight は整数ですか？この回答では正の整数を想定しています。小数のキャパシティには正規化されたトークンバジェットが必要です。
メンバーシップの更新はルックアップと並行して行われますか？その場合は、イミュータブルなスナップショットを公開するか、読み取り/書き込みロックを追加します。以下のコードでは更新が直列化されていると仮定します。
レプリケーションは必要ですか？基本APIは1つの所有者を返します。R個の異なる後続ノードを返すのは、障害ルールや重複トークンルールを伴うフォローアップ質問です。
どのようなハッシュ関数が利用可能ですか？この課題では決定論的かつ一様であるものとして扱いますが、実環境の選択肢では衝突と敵対的入力の検証が必要です。

30秒の回答フレームワーク

「(token, virtualNodeId, physicalNodeId) レコードをソートされた順序で保存します。ノードの追加により weight × V 個の決定論的トークンが挿入され、削除時にはそれらのトークンが正確に削除されます。ルックアップではキーをハッシュ化し、その位置またはそれ以降にある最初のトークンを二分探索し、インデックス0にラップアラウンドします。不変条件は、すべてのトークンが1つの有効な物理ノードにマップされ、各キーが時計回りで最初のトークンを所有することです。ルックアップは O(log M)、更新は O(V·weight·log M) であり、衝突、ラップアラウンド、重複更新、削除、空のリング、およびキーの再マッピングをテストします。」

ステップバイステップの詳細な回答

1. 表現形式と不変条件の選択

仮想トークンの数を M とします。レコードのソート済み配列と、物理ノードIDからその生成されたトークンレコードへのマップを保持します。ソート済み配列によりルックアップが下限探索（lower-bound search）になり、逆引きマップにより一致するプレフィックスをスキャンする代わりに正確な削除が可能になります。

不変条件は以下の通りです：

トークンは (hash, tokenId) でソートされている。
すべてのトークンは1つの登録された物理ノードを参照する。
キーは時計回りで最初のトークンにマップされ、リングの境界でラップアラウンドする。
物理ノードのトークンセットは、その安定したID、インデックス、および設定されたカウントからのみ生成される。

2次的な tokenId によるタイブレークにより、同一のハッシュ値が決定論的になります。これは衝突が不可能であると偽るものではありません。

2. 仮想トークンを決定論的に生成する

ノード n と仮想インデックス i について、n + "#" + i のバイト列をハッシュ化します。weight × V 個のインデックスを生成します。したがって、重みが大きいほど期待値としてより多くの区間を所有します。固定のハッシュ実装を使用し、V と重みポリシーをリングのスナップショットとともに永続化します。これらを変更するとキーが無言で再マッピングされます。

実装では、O(log M) の挿入と削除のために平衡木を使用できます。面接に適したソート済み配列は不変条件を明確に保ちます。バッチでのメンバーシップ更新では、配列を繰り返しシフトするのではなく、一度だけ再構築することができます。

3. ルックアップと更新の実装

python

from bisect import bisect_left

class ConsistentHashRing:
    def __init__(self, virtuals_per_weight, hash64):
        self.v = virtuals_per_weight
        self.hash64 = hash64
        self.tokens = []  # (hash, token_id, node_id)
        self.by_node = {}

    def add_node(self, node_id, weight=1):
        if weight <= 0 or node_id in self.by_node:
            raise ValueError("invalid or duplicate node")
        owned = []
        for i in range(weight * self.v):
            token_id = f"{node_id}#{i}"
            owned.append((self.hash64(token_id), token_id, node_id))
        self.by_node[node_id] = owned
        self.tokens.extend(owned)
        self.tokens.sort()

    def remove_node(self, node_id):
        owned = self.by_node.pop(node_id, None)
        if owned is None:
            return False
        owned_ids = {token_id for _, token_id, _ in owned}
        self.tokens = [t for t in self.tokens if t[1] not in owned_ids]
        return True

    def get_node(self, key):
        if not self.tokens:
            return None
        h = self.hash64(key)
        i = bisect_left(self.tokens, (h, "", ""))
        return self.tokens[i if i < len(self.tokens) else 0][2]

このコードは、重複するノードを呼び出し側のエラーとして扱い、存在しないノードの削除をno-op（何もしない）として扱います。本番環境では、通常、更新時に新しいスナップショットを構築してアトミックに公開し、リーダーが中途半端に更新されたリングを観測しないようにします。

4. 計算量と再マッピング動作の導出

M = V × sum(weight) の場合、ルックアップは呼び出しあたり O(log M) かつ O(1) の追加空間です。配列実装の挿入と削除は、ソートとフィルタリングにより O(M + K log M) です（K は変更されたノードのトークン数）。平衡木を使用すると更新は O(K log M) に削減されます。メモリは O(M) です。

ノードが追加されると、その仮想トークンの直前にある区間のキーのみがそのノードに移動します。ノードが削除されると、それらの区間は時計回りで次の所有者に移動します。これが剰余ハッシュに対する単調性の利点であり、剰余ハッシュでは N を変更するとほとんどのキーが再マッピングされます。仮想ノードは分散を低減しますが、単一のホットキーや偏ったワークロードを解決することはできません。

質の高い模範解答

「リングをソートされた (hash, tokenId, nodeId) レコードと、ノードIDからそのレコードへのマップとして表現します。addNode は決定論的な weight × V 個の仮想トークンを作成し、removeNode はそれらのレコードを正確に削除します。getNode は下限探索を使用し、ラップアラウンドします。不変条件は、すべてのキーが時計回りで最初の有効なトークンを所有し、(hash, tokenId) が衝突を決定論的に解決することです。ルックアップは O(log M) です。ソート済み配列では更新が O(M + K log M) になり、木構造を使用すれば O(K log M) にできます。空および1ノードのリング、ラップアラウンド、重複ID、衝突、削除、重み付き分散、およびメンバーシップ変更後に再マッピングされるキーの割合をテストします。」

よくある間違い

hash(key) % N を使用する → ノード数を変更するとほとんどのキーが再マッピングされる → 時計回りで次のトークンを探索する。
衝突が発生しないと仮定する → 同一のハッシュにより所有権が不安定になる → 決定論的なトークンIDでタイブレークする。
再起動ごとにランダムなトークンを生成する → すべてのキーが予期せず移動する → 安定したノードIDとインデックスからトークンを導出する。
ノード名のプレフィックスのみで削除する → 類似したIDによって誤ったレコードが削除される可能性がある → 明示的な逆引きマップとトークンIDを保持する。
仮想ノードがホットスポットを排除すると主張する → 単一の人気キーは依然として1つの所有者をターゲットにする → レプリケーション、負荷に応じたルーティング、またはホットキー対策を個別の要件として追加する。
空の場合や重複ケースを無視する → 境界でルックアップや更新の不変条件が破綻する → コーディング前に戻り値とエラーの動作を定義する。

フォローアップと回答

3つのレプリカを返すにはどうしますか？

所有者から時計回りに走査し、3つ見つかるまで重複しない物理ノードIDを収集します。すでに選択されたノードに属する追加の仮想トークンはスキップします。有効なノードが3つ未満の場合は、利用可能なセットと明示的な不足分を返します。

単一の例ではなく分布をテストするにはどうしますか？

固定されたキーのコーパスを生成し、各ノードのシェアと最大最小比を測定してから、ノードの追加と削除の後に繰り返します。リグレッションを再現できるようにハッシュシードを固定しておきます。

ノードのキャパシティが変更された場合はどうなりますか？

古いトークンセットを削除し、新しい重みを使用して新しいセットを追加し、1つのスナップショットを公開します。変更されたトークンに隣接する区間のみが移動することを期待しますが、移行中の負荷を監視します。

剰余ハッシュの方がシンプルなのはどのような場合ですか？

メンバーシップが固定されているか、完全なリバランスが許容される場合、剰余ハッシュの方がコードが短く、多くの場合高速です。コンシステントハッシュは、メンバーシップが変化し、再マッピングのコストが重要である場合にその複雑さに見合う価値を発揮します。