コンシステントハッシュを使う際の仮想ノード数の決め方
コンシステントハッシュ法は便利なアルゴリズムだが、注意点がある。
仮想ノード数をいくつにするかという問題で、仮想ノード数が多ければ多いほどファイルは均一に分散するというわけではないという事実だ。
多数のキャッシュオブジェクトをいくつかのキャッシュコンテナにコンシステントハッシュ法で分散させるとしよう。キャッシュオブジェクトの個数を 10000 個、キャッシュコンテナの個数を 10 とすると、キャッシュコンテナあたりの平均キャッシュオブジェクト保有数は 1000 個だ。
果たして、あるハッシュアルゴリズムでは、どのくらいの仮想ノード数で、どのくらい均一に分散するのだろう？
MD5 でのテスト
下記グラフは、横軸が仮想ノード数、縦軸が1キャッシュコンテナあたりの平均キャッシュオブジェクト保有数に対する標準偏差の割合だ。
従って、縦軸は 0 に近ければ近いほど均一に分散することを表す。
ハッシュアルゴリズムは MD5。ある仮想ノード数では 30 回の試行をしている。
見ての通り、グラフは滑らかではない。このグラフでは仮想ノード数が 86 あたりが最もバラつきが少ない。
160程度の仮想ノード数を選んでも、80台前半より偏りが出やすいのだ！
