Webサービスの裏側でサーバーを複数並べるとき、いちばんよく見かけるのは、全サーバーに同じ内容を複製しておき、負荷分散装置（ロードバランサ）がアクセスを適当に振り分ける構成です。どのサーバーも同じものを持っているので、誰が受けても答えられる。データ全体が1台に収まるうちは、これが単純で強いやり方です。
ところが、1台に収まらなくなると話が変わります。分かりやすいのがキャッシュです。毎回データベースに問い合わせると遅いので、一度取り出した答えを高速なサーバーのメモリに覚えさせておく仕組みですが、メモリの量には限りがあります。同じ内容を複製する方式では、サーバーを何台並べても覚えられる量は1台分のまま。量を増やすには、複製ではなく分けて持つしかありません。3台に分ければ容量は3倍——その代わり、複製のときには存在しなかった問題が生まれます。
それが担当決めです。データには user:1001 のような名前（キー）が付いています。あるキーを保存するとき、そして後で読みに来たとき、どちらも同じサーバーに行き着かなければ意味がありません。全キーの置き場所を台帳に記録するやり方は、キーが何億もあると台帳自体が重荷になるので、できればキーを見ただけで担当が計算で決まる決め方が欲しい。
自然に思いつくのは、ハッシュ関数を使う方法です。ハッシュ関数というのは、どんなデータからでも決まった範囲の数値をひとつ作る計算のことで、同じ入力からは必ず同じ数値が出ます。念のため付け加えると、これは「違う入力なら必ず違う数値になる」という意味ではありません。別々のキーが偶然同じハッシュ値を引き当てる「衝突」はあり得ます。ただ今回の用途では、たまたま同じ数値になったキーたちが同じサーバーに置かれるだけなので、衝突があっても仕組みは壊れません。キーのハッシュ値をサーバー台数 n で割った余りを担当番号にすれば、どのキーの置き場所も計算だけで定まる。台帳いらず、計算一発、しかもキーはほぼ均等にばらけます。実際、これで気持ちよく分散できます——台数が変わらないうちは。
1台増やしただけで、ほぼ全部が引っ越す
アクセスが増えてきたので、サーバーを3台から4台にしたとしましょう。担当の決め方は「% 3」から「% 4」に変わります。すると何が起きるか。
同じキー、同じハッシュ値なのに、割る数が変わっただけで余りの答えはほぼ全部変わります。上の例では10個中9個。データは1バイトも変わっていないのに、置き場所だけがそっくり入れ替わってしまうのです。
これはキャッシュにとって致命傷になりえます。置き場所が変わるということは、読みに行った先のサーバーがそのデータを持っていないということ。つまり増設した瞬間、ほぼ全アクセスがキャッシュミスになり、問い合わせが後ろのデータベースへ一斉に流れ込みます。負荷を下げたくてサーバーを足したのに、足した瞬間にいちばん重い負荷がかかる。本末転倒です。データ本体を分けて持つ分散ストレージなら、今度は実データの大移動が走ります。
冷静に考えると、動く必要があるのは全体のおよそ4分の1だけのはずです。新しい1台が受け持つぶんを渡せば、残りの4分の3は今の場所のままでいい。この「新入りに渡すぶんだけ動かして、あとは触らない」を台帳なしでやってのけるのが、今回の主役コンシステント・ハッシュ法です。
担当を「計算式」ではなく「場所」で決める
余り方式の弱点は、担当の決め方そのものの中に台数 n が入っていることです。式に n が入っているから、n が変わるたびに全キーの答えが変わる。そこで発想を変えて、担当の決め方から n を追い出します。
ハッシュ値の範囲（0〜最大値）を、端と端がつながった一周の円盤だと思うことにします。キーは、そのハッシュ値の場所にポツンと置く。そしてここがミソなのですが、サーバーも「サーバー名のハッシュ値」の場所に立てて、キーと同じ円盤に載せてしまうのです。そのうえで、キーの担当はこう決めます——その場所から時計回りに歩いて、最初に出会うサーバー。
決め方はこれだけです。円環の端（0）をまたいでも、そのまま一周続けて歩きます。結果として、各サーバーは「自分の手前の区間」をまるごと受け持つ形になります（図の外側の帯）。
ここで、何を・どんな関数でハッシュするのかも押さえておきます。入力はデータの中身ではなく名前（キー）です。user:1001 というキー文字列、URL、ファイル名——読みに行く時点ではまだ中身を手にしていないのだから、名前から場所が計算できなければ意味がありません。サーバー側も「10.0.0.5:6379」のような名前をハッシュして立てます。関数のほうは、速くて出力がまんべんなくばらけるものなら何でもよく、暗号としての強度は要りません。実際、memcached 向けの ketama は MD5 を、Cassandra は MurmurHash3 という高速ハッシュを使っています（MD5 は偽造への耐性という意味では破られた古い関数ですが、キーをばらまくだけの用途なら今も現役です）。この記事のビジュアライザも FNV-1a という軽量ハッシュで動いています。
この決め方のどこにも「台数 n」が出てこないことに注目してください。キーの位置はキーのハッシュ値だけで、サーバーの位置もサーバー名のハッシュ値だけで決まっていて、ほかのサーバーが何台いようが一切関係ありません。台数が式から消えたことが、次の一手で効いてきます。
増やしても、動くのは「新入りの手前」だけ
では、サーバーDを追加してみます。やることは、Dのハッシュ値の場所に新しい旗を立てるだけです。
変わるのは、Dの手前の区間だけです。この区間にいるキーは、これまで「時計回りで最初のサーバー」がCだったのが、手前にDが割り込んだのでDに変わる。それ以外の場所では、時計回りに歩いて最初に出会うサーバーが以前と同じなので、担当も同じままです。キーもサーバーも誰ひとり場所を動いていない。新しい旗が1本立って、境界がひとつ増えただけなのです。
引っ越すのは新入りが受け持つ区間ぶん、つまり全体のおよそ n 分の 1。さきほど「理想はこれ」と言った形が、そのまま実現しています。サーバーの削除は逆再生で、旗が1本抜けると、その区間を時計回りの次のサーバーが丸ごと引き取ります。故障でサーバーが落ちたときも、その分担が自動的に隣へ流れるだけで、ほかのキーは無傷。サーバーの顔ぶれが変わる前提のシステムと、とことん相性がいい決め方です。
偏りは「分身」でならす ── 仮想ノード
ただし、これで万事解決とはいかないのが現実の面白いところです。旗の立ちどころはハッシュ任せなので、運が悪いと偏ります。
3台がたまたま円環の近い場所に立ってしまうと、1台だけが円盤の大半を受け持つことになります。余り方式なら保証されていた「ほぼ均等」が、場所方式では崩れることがあるわけです。
そこで使われるのが仮想ノードという工夫です。サーバーAを円環上の1点ではなく、「A-1」「A-2」…と名前を変えてハッシュした複数の点——いわば分身——として撒きます。分身が増えるほど担当は細切れに混ざり合い、合計の持ち分はならされていきます。実際のシステムでは1台あたり数十〜数百個の分身を置くのがふつうです。分身にはもうひとつ利点があって、サーバーを追加したときの引っ越し元が特定の1台に集中せず、全員から少しずつ分けてもらう形になります。増減時の引っ越しが約 n 分の 1 で済む性質は、そのまま変わりません。
触って確かめる ── ビジュアライザ
ここまでの話を、実際にサーバーを増減させながら確かめられるビジュアライザを用意しました。60個のキー（●）は最初から最後まで同じもので、方式を切り替えると同じキーたちの担当がどう決まるかが変わります。「＋ サーバー追加」を押すと、直前の操作で引っ越したキーが赤い縁で残るので、余り方式でほぼ全部が赤くなるのと、円環方式で一部の区間だけが赤くなるのを見比べてみてください。手元で試したところ、3台から4台への増設で引っ越したキーは、余り方式が60個中47個（78%）、円環方式は12個（20%）でした。下の比較表には「いまの構成に1台足したら何個動くか」が3方式並ぶので、数字でも確認できます。円環方式で「各サーバーの担当キー数」が偏っていくのを見つけたら、仮想ノードに切り替えてみてください。
うまく表示されないときは、ビジュアライザを別タブで開く 。
どこで使われているか
コンシステント・ハッシュ法は、1997年にMITの研究グループがWebキャッシュの分散のために提案した手法です。いまでは「サーバーの顔ぶれが変わる前提でデータを分散させる」場面の定番になっていて、分散キャッシュ（memcached のクライアント側分散で使われる ketama が有名です）、Amazon DynamoDB や Apache Cassandra といった分散データベースのデータ配置、CDNの振り分けなど、あちこちで動いています。サーバーが日常的に増えたり減ったり故障したりする大規模システムほど、「増減しても境界がひとつ動くだけ」という性質が効いてきます。
もっとも、この円環を自分の手で実装する機会は、巨大サービスの中の人でもなければ多くはありません。ふだんの接点はむしろ、ミドルウェアの中に埋め込まれた形です。Redis Cluster がノード追加時にハッシュスロットを少しだけ動かすのも、Elasticsearch がインデックスをシャードに分けて持つのも、根っこにはここで見た「分けて持つなら、増減で全部を動かさない」という同じ発想があります。キャッシュやログ基盤を2台以上に分けた時点で、実は誰もがこの層に触れているわけです。
シリーズの仲間
このシリーズは「素朴なやり方だと大変そう ── でも隠れた構造を突くと一気に」という気持ちよさで繋がっています。
- 画像を「リネームだけ」で並び替える玉突き方式 … 並び替えのサイクルを、穴（目印）を歩かせてほどく。
- 配列を「その場で」左に回す … 別配列なしで、部分反転だけで回す。
- 配列を「輪」に見立てるリングバッファ … head の目印だけを動かして、先頭削除のシフトを消す。
- カメとウサギで「輪」を見つけるフロイドの循環検出 … 追加メモリ O(1) でループと入口を発見。
- 地図の最短経路を「賢く」探すダイクストラとA★ … 見込みのある候補から確定して、探索を絞る。
今回の「全部作り直しになりそう ── でも場所で決めておけば境界がひとつ動くだけ」も、同じ系譜の気持ちよさです。円環の上を時計回りに歩く姿は、リングバッファやフロイドの「輪の住人」たちともどこか似ています。
なお、このシリーズは筆者がAI（Claude）と対話しながらアルゴリズムを学び、その理解を自分の言葉で整理している学習ノートです。図やインタラクティブデモの制作もAIの力を大きく借りています。本文が素朴な疑問に先回りして答えているのは、そこが実際に筆者のつまずいた場所だからです。
参考文献
- D. Karger, E. Lehman, T. Leighton, R. Panigrahy, M. Levine, D. Lewin, “Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web,” Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC ‘97), pp. 654–663. DOI: 10.1145/258533.258660
- 概説は Wikipedia: Consistent hashing 。
余り方式の「ほぼ全滅」と円環方式の「一区間だけ」は、文章で読むより赤い縁の広がり方を一度見るほうが早いはずです。ぜひ上のビジュアライザでサーバーを増やしたり減らしたりしてみてください。