一貫性ハッシュ
キーをサーバーに割り振るハッシュのリングを描き、サーバーを足したり外したりしたときに動くキーの数を、剰余で割り振る方法やランデブーハッシュと比べます。仮想ノードによる負荷の偏りの変化や、複製の置き先も確かめられます。
外側の色の帯は各サーバーが受け持つ範囲（仮想ノードの位置から反時計回りに、1 つ前の仮想ノードまで）、内側の点はキー（300 個だけ表示）です。直前の変更で担当が変わったキーは大きな点で示します。
サーバー（押して足す・外す）
1 台あたりの仮想ノードの数
キーの数
複製を置く台数
hash = 599,759,890（1 周の 14.0% の位置）→ 時計回りで最初の仮想ノードは S2#5。置き先: S2
サーバーを増減したときに動くキー
上のサーバーのボタンで 1 台足すか外すと、それぞれの方法で担当が変わったキーの数を比べます。
サーバーごとのキーの数（負荷の偏り）
破線は平均（2500 個）。いちばん多いサーバーは平均の 1.41 倍、ばらつき（標準偏差 ÷ 平均）は 26.8% です。 かっこ内はリングのうち受け持つ範囲の割合です。仮想ノードが少ないと範囲の広さがばらつきます。
使い方
- サーバーのボタン（S1〜S8）で 1 台ずつ足したり外したりすると、剰余・一貫性ハッシュ・ランデブーハッシュのそれぞれで、担当サーバーが変わったキーの数を比べます。
- リングの図は一貫性ハッシュの割り振りです。仮想ノードの数を変えると、色の帯の細かさと、サーバーごとのキーの数の偏りが変わります。
- 「キーを探す」に文字列を入れると、そのハッシュ値の位置から時計回りにたどって、置き先のサーバーを示します。複製を置く台数を増やすと、続けて出会う別のサーバーも置き先になります。
剰余で割り振る問題
キャッシュや分散データベースでは、キーのハッシュ値をサーバーの台数で割った余りで置き先を決めるのが最も簡単です。しかし台数が 5 台から 6 台に変わると割る数が変わるので、ほとんどのキーの置き先が変わり、キャッシュが一斉に外れたり、大量のデータを移し替えたりすることになります。
一貫性ハッシュ
ハッシュ値の範囲を輪（リング）とみなし、サーバーもハッシュ値でリング上に置きます。キーは自分の位置から時計回りに進んで最初に出会うサーバーの担当です。サーバーを 1 台足しても、新しいサーバーの手前の範囲のキーが移るだけで、ほかのキーは動きません。1 台を 1 か所に置くだけでは受け持つ範囲の広さがばらつくので、1 台を名前を変えて何十〜何百か所に置く「仮想ノード」で偏りをならします。Amazon の Dynamo や Cassandra、memcached のクライアントなどで使われています。
ランデブーハッシュ（HRW）は、キーとサーバーの組ごとにハッシュ値を計算し、いちばん大きいサーバーを選ぶ方法です。リングを持たずに偏りなく、動く量も最小になりますが、1 つのキーの検索でサーバーの台数分のハッシュを計算します。