一貫性ハッシュ：データ全体を再配置することなく、サーバーの追加・削除を行う

データを分割する最も簡単な方法は、鍵のハッシュ値をノード数で割り、その余りを用いることです。これは、3ノードのクラスターに4台目のノードを追加するまでは完璧に機能します。しかし、4台目を追加すると、ほぼすべての鍵の位置が入れ替わってしまい、クラスターはデータ全体をネットワーク経由で転送しなければならなくなります。

すべてを円の上に並べる

一貫性ハッシュでは、キーとサーバーの両方を同じ空間（円のようなもの）にハッシュ化します。各キーは、その位置から時計回りに進んだときに最初に遭遇するサーバーに割り当てられます。

サーバーを1台追加しても、その直前にあるセグメントにのみ影響が及ぶ――つまり、データのほぼすべてではなく、平均して1/nのデータのみが影響を受ける。サーバーを1台削除する場合も同様で、そのサーバーが担当していた部分のみが次のサーバーに移行する。

偏った分布の問題とその対処法

マシン数が少ないと、リング上の配置が不均一になり、あるマシンが他のマシンの数倍もの長い弧を描いてしまうことがあります。これを解決する標準的な方法は「仮想ノード」です。つまり、各物理マシンをリング上の数百カ所の異なる位置にハッシュ化します。大数の法則により、分布が均一になります。

仮想ノードの便利な点は、高性能なマシンほど多くの位置を割り当てられること——実際の処理能力に応じて負荷を分散できる点です。

それに出会った場所

分散キャッシュ、分散キーバリューデータベース、エッジサーバーを選択するコンテンツ配信ネットワーク、および、同一ユーザーが常に同じサーバーに接続されるようにするための負荷分散。

お使いのシステムが1台だけであり、今後もずっと1台だけのままであるなら、これを構築しないでください。これはスケーラビリティの問題を解決するものであり、その問題が実際に存在する場合にのみ、導入する価値があります。