コンシステントハッシング — ノードを足しても引っ越しは最小

たくさんのデータを複数のサーバーに分けて預けるとき、どのサーバーに置くかを決める素朴な方法が ハッシュ値 % サーバー台数 です。ところがこれには弱点があります。サーバーを1台足したり減らしたりすると、割り算の余りがほぼ全部変わり、ほとんどのデータが引っ越しになってしまうのです。

そこで登場するのが コンシステントハッシング。サーバーもデータも1つの輪(リング)の上に置き、各データは時計回りで最初に出会ったサーバーが担当します。こうするとノードを増減しても、影響を受けるのは輪のひと区間ぶんのデータだけ。下の図1で「ノードを追加」を押して、何個のキーが引っ越すか見てみてください。

なぜ引っ越しが少なくて済むのか

リング上では、各ノードは「自分の手前の区間」だけを担当しています。新しいノードを輪のどこかに差し込むと、変化するのは差し込んだ位置から手前のノードまでの区間だけ。それ以外のキーは、これまでと同じノードに時計回りで吸い込まれるのでびくともしません。図1で「% 台数」方式と並べると、追加1回で数個しか動かない側と、ほぼ全部が動く側の差が一目で分かります。

実際の分散キャッシュ(memcached のクライアントや一部の DB・ロードバランサ)はこの仕組みを使い、サーバー追加・故障時のキャッシュ総崩れ(全部が一斉に取り直しになる事態)を防いでいます。さらに実務では、1台のサーバーをリング上の複数の点(仮想ノード)として置き、担当範囲の偏りをならす工夫も加えられます。図1のノードが輪の上で偏ると担当数も偏るのと同じ問題への対処です。

まとめ

コンシステントハッシングは「輪の上に並べ、時計回りで最初のノードが担当する」だけの仕掛けで、ノードの増減時に動くデータを輪のひと区間ぶんに抑えます。素朴な「% 台数」方式がほぼ全件を引っ越させてしまうのと比べ、追加・故障に強い —— だからスケールするキャッシュや分散ストレージの土台として使われています。図1でノードを足したり消したりして、動くキーの少なさを確かめてみてください。