コンシステントハッシュを使う際の仮想ノード数の決め方

コンシステントハッシュ法は便利なアルゴリズムだが、注意点がある。
仮想ノード数をいくつにするかという問題で、仮想ノード数が多ければ多いほどファイルは均一に分散するというわけではないという事実だ。

多数のキャッシュオブジェクトをいくつかのキャッシュコンテナにコンシステントハッシュ法で分散させるとしよう。キャッシュオブジェクトの個数を 10000 個、キャッシュコンテナの個数を 10 とすると、キャッシュコンテナあたりの平均キャッシュオブジェクト保有数は 1000 個だ。

果たして、あるハッシュアルゴリズムでは、どのくらいの仮想ノード数で、どのくらい均一に分散するのだろう？

MD5 でのテスト

下記グラフは、横軸が仮想ノード数、縦軸が1キャッシュコンテナあたりの平均キャッシュオブジェクト保有数に対する標準偏差の割合だ。
従って、縦軸は 0 に近ければ近いほど均一に分散することを表す。
ハッシュアルゴリズムは MD5。ある仮想ノード数では 30 回の試行をしている。

見ての通り、グラフは滑らかではない。このグラフでは仮想ノード数が 86 あたりが最もバラつきが少ない。
160程度の仮想ノード数を選んでも、80台前半より偏りが出やすいのだ！

SHA-1 でのテスト

さて、次に SHA-1 で見てみよう。ハッシュアルゴリズム以外の条件は上記 MD5 でのテストと同様。

MD5 よりは若干滑らかであるように見えるが、それでも全体的には波打って見える。

まとめ

今回はハッシュ関数に整数を渡して分散させたが、ソフトウェアによってハッシュ関数に渡す値は変わるだろう。
そのため、コンシステントハッシュ法で仮想ノード数を決める際は適当に決めるのではなく、事前に計算して最適な値を決定すること。