コンシステントハッシュを図解：ハッシュリング、仮想ノード、リバランス

hash(key) % 10 でキャッシュを 10 台のサーバーに分散しているとします。トラフィックが増えて 11 台目のサーバーを追加すると、ヒット率が急落します。ほぼすべてのキーが別のサーバーに対応するようになり、キャッシュがあらゆる場所で同時に冷え、背後のデータベースが負荷をまるごと受けることになるからです。コンシステントハッシュ（consistent hashing）は、まさにこれを防ぐためにあります。

この記事では、ハッシュリングと仮想ノードを図で解説し、その効果を測り、コンパクトな実装を示します。さらに、実際のシステムで出会う代替手段である rendezvous hashing、jump hash、Maglev、固定ハッシュスロットと比較します。

剰余ハッシュが破綻する理由

server = hash(key) % N では、対応付けが N に依存します。N を変えると、キーが同じ場所にとどまるのは、両方の値でハッシュの余りが同じになる場合だけで、それはまれです。100 万個のキーで簡単なシミュレーションをすると、次のようになります。

理想は 1/11、つまり約 9.1% です。新しいサーバーが公平な取り分を受け持ち、ほかは何も動かないのが理想です。リングはこれに近づきます。残る差は、新しいサーバーのトークンが平均よりやや大きい弧に落ちることから生じます。

キャッシュにとっては、ヒット率が一時的に下がるだけで済むか、コールドスタートになるかの違いです。シャーディングされたデータベースや状態を持つワーカー群にとっては、データの 10 分の 1 を移すか、ほぼすべてを移すかの違いです。

ハッシュリング

コンシステントハッシュは、Karger らが 1997 年に Web キャッシュ向けに考案したもので、サーバーとキーの両方を同じ円形のハッシュ空間に写像します。たとえば 0 から 2^64 - 1 までの整数で、最大値の次は 0 に戻ります。

1. 各サーバーの名前をハッシュし、リング上の位置を決めます。
2. 各キーをハッシュし、リング上の位置を決めます。
3. キーの位置から時計回りに進みます。最初に出会ったサーバーがそのキーの所有者です。

サーバーを追加すると 1 つの位置に置かれ、そのサーバーは直前のサーバーと自分の間にあるキーだけを引き継ぎます。それ以外のキーはそのままです。サーバーを外すと、そのキーは時計回りで次のサーバーに引き渡されます。ほかは何も変わりません。

仮想ノード：偏りを直す

サーバーごとに位置が 1 つだけだと、サーバー間の弧はランダムで不均等になり、リングの大部分を持つサーバーもあれば、ごく一部しか持たないサーバーも出てきます。10 台のサーバーで同じシミュレーションをすると、その差がわかります。

解決策は、cache-a#0、cache-a#1 のような名前をハッシュして、各サーバーに仮想ノード（トークン）と呼ばれる多数の位置を与えることです。仮想ノードには、ほかにも 2 つの利点があります。

• 重み付け。 メモリが 2 倍のサーバーには、トークンを 2 倍与えます。
• 穏やかな障害。 サーバーが落ちると、その多数の小さな弧はさまざまな後続サーバーに引き継がれます。そのため、負荷が隣の 1 台に倍増してのしかかるのではなく、クラスター全体に分散します。

代償は、より大きなルックアップテーブルと、メンバーシップが変わったときに移すメタデータの増加です。Cassandra はこのトレードオフを実際に示しています。デフォルトでノードあたり 256 個のトークンを使っていましたが、バージョン 4.0 でデフォルトが 16 に下がりました。この 16 個は、ランダムではなく均等に配置するトークン割り当てアルゴリズムと組み合わせて使われます。

小さな実装

リングは、ソート済みのトークン位置のリストと二分探索でできています。

import bisect
import hashlib

def hash64(value: str) -> int:
    # MD5 for spread, not security; any well-mixed hash works
    return int.from_bytes(hashlib.md5(value.encode()).digest()[:8], "big")

class HashRing:
    def __init__(self, servers, vnodes=100):
        self.vnodes = vnodes
        self.points = []   # sorted token positions
        self.owners = {}   # position -> server
        for server in servers:
            self.add(server)

    def add(self, server):
        for i in range(self.vnodes):
            p = hash64(f"{server}#{i}")
            bisect.insort(self.points, p)
            self.owners[p] = server

    def remove(self, server):
        for i in range(self.vnodes):
            p = hash64(f"{server}#{i}")
            self.points.remove(p)
            del self.owners[p]

    def lookup(self, key: str) -> str:
        i = bisect.bisect_right(self.points, hash64(key)) % len(self.points)
        return self.owners[self.points[i]]

ルックアップのコストは、トークン数 T に対して O(log T) です。本番向けの実装では、トークンの衝突にも対処し、すべてのクライアントが同じメンバーシップの見え方を持つようにします。サーバーリストが異なる 2 つのクライアントは、キーの置き場所について食い違うからです。

リング上のレプリケーション

ストレージシステムは、ルーティングだけでなく配置にもリングを使います。Amazon の Dynamo 論文では、各キーを、その位置から時計回りに進んで最初に出会う N 台の異なるサーバー（preference list）に保存し、すでにリストにあるサーバーの追加トークンは飛ばします。N = 3 なら、サーバーを 1 台失っても、そのサーバーが持っていたものはすべて、リング上の隣接サーバーに 2 つずつコピーが残ります。

同じ「時計回りに進み、重複を飛ばす」という考え方は、ラックやゾーンにも広げられます。レプリカが異なる障害ドメインにまたがるまでトークンを飛ばせばよいのです。

出会うことになる代替手段

Jump consistent hash は、シャードに番号が振られ、増える一方のシャーディングストレージに向いています。Rendezvous hashing は、ルックアップごとの O(N) が問題にならない小さなサーバー群に向いています。ハッシュスロットは、自動配置の代わりに、オペレーターが制御する明示的な移動を選ぶ方式で、データベースではこちらを好むチームが多くあります。

ホットキーと負荷の上限

コンシステントハッシュが均等にするのはキーであって、トラフィックではありません。有名ユーザーやバズった商品は、やはり 1 台のサーバーに集中します。Consistent hashing with bounded loads は、各サーバーの負荷を平均より一定の割合だけ高い値で頭打ちにし、あふれた分を時計回りで次のサーバーに回します。HAProxy は hash-balance-factor の設定でこれを実装しています。本当にホットなキーには、そのキーのレプリケーション、リクエストの集約、あるいは手前に置く小さなローカルキャッシュが依然として必要です。

運用上の落とし穴

• ハッシュ関数やトークン方式を変更すると、剰余ハッシュとまったく同じように、すべてが再配置されます。移行作業として扱いましょう。
• メンバーシップは一貫させる必要があります。 サーバーリストは、調整サービスやロードバランサーの設定のような単一の情報源から配布し、一度に変更します。
• 不安定なサーバーはチャーンを生みます。 数分ごとにヘルスチェックに失敗するサーバーは、キーを行ったり来たりさせます。外したり戻したりする前にヒステリシスを設けましょう。
• 新しいサーバーはコールドな状態で始まります。 新しいキャッシュノードはすぐに担当分のリクエストを受けます。バックエンドがキャッシュミスを吸収できないなら、ウォームアップするか、重みを徐々に上げましょう。

ハッシュリングの図

図の読み方は次のとおりです。

• 円はハッシュ空間です。 位置は時計回りに増え、一番上で最大値が 0 に戻ります。
• 色付きのトークンは仮想ノードです。色ごとに 1 台のサーバーを表し、各サーバーはリング上に散らばった複数のトークンを持ちます。
• キーはハッシュの位置にあり、矢印は時計回りに、そのキーを所有するトークンを指しています。
• 破線のトークンは、追加中のサーバー D のものです。 所有者が変わるのは、D のトークンのすぐ反時計回り側にあるキーだけです。
• 凡例と Markdown ブロックは、サーバーと、上のシミュレーションで得た移動数を示しています。

ハッシュ方式をわかりやすく描く

• 表ではなくリングを描きます。 時計回りの規則は視覚的なものです。ルックアップテーブルでは、なぜ一部のキーだけが動くのかが見えません。
• トークンをサーバーごとに色分けし、凡例を添えます。トークンからサーバーへ 1 本ずつエッジを引く必要はありません。
• メンバーシップの変化を見せます。 静的なリングはルーティングを説明しますが、サーバーが 1 台加わるリングは、この手法の要点そのものを説明します。
• 実際の数値を横に添えます。 移動したキーの数と負荷の分散です。図よりも数値のほうが人を納得させます。

コンシステントハッシュは、このブログのシステム設計記事のあちこちに登場します。データの配置ではデータベースシャーディング図、スティッキーなルーティングではロードバランサー図、分散キャッシュではキャッシュ戦略図を参照してください。

Archboard で作る

1. Google または GitHub でサインインし、図を作成します。
2. リングとして、基本パックの大きな 楕円 の図形を追加します。
3. リング上にトークンとして小さな 楕円 の図形を追加し、サーバーごとに色分けします。サーバー A、B、C に 2 つずつ、新しいサーバー D には破線のものを 2 つ置きます。
4. 凡例として、リングの横にデータパックの Redis ノードを 4 つ縦に並べ、それぞれのトークンと同じ色にします。
5. キーを基本パックの テキスト ラベルとしてリング上に置き、所有トークンへ短い矢印を引きます。
6. キーの移動数と負荷の数値を書いた基本パックの Markdown ブロックを追加します。

この例で使うダイアグラムノードは 14 個で、Free プランの範囲に収まります。

よくある質問

コンシステントハッシュはどんな問題を解決しますか？ サーバーを追加したり外したりしても、ほとんどのキーを同じサーバーにとどめます。剰余ハッシュではサーバー数を変えるとほぼすべてのキーが再マッピングされますが、コンシステントハッシュでは移動するのはキーの約 1/N だけです。

コンシステントハッシュの仮想ノードとは何ですか？ 物理サーバー 1 台を、異なる名前でリング上に何度も配置したものです。位置が増えるほど弧が均等になり、容量に応じてサーバーに重みを付けられ、障害が起きたサーバーの負荷を多数のサーバーに分散できます。

サーバーごとに仮想ノードはいくつ必要ですか？ クラスターの規模で均等に分散できるだけの数です。今回のシミュレーションでは、10 台構成でサーバーあたり 100 個にすると、最も負荷の高いサーバーを平均の 7% 以内に収められました。Cassandra 4.0 以降のように、より賢いトークン割り当てを持つシステムでは、はるかに少ない数で済みます。

Redis Cluster はコンシステントハッシュですか？ リングという意味では違います。Redis Cluster はキーを 16,384 個の固定ハッシュスロットに対応付け、スロットをノードに割り当てます。データを移すことは、スロットを明示的に移すことを意味します。

コンシステントハッシュと rendezvous hashing の違いは何ですか？ どちらも、メンバーシップが変わったときに移動するキーは約 1/N です。Rendezvous hashing はキーごとに全サーバーのスコアを計算して最大のものを選ぶため、リングは不要ですが、ルックアップごとに O(N) のコストがかかります。

無料で始める — 1 シート、クレジットカード不要。