1時間でわからせたコンシステントハッシュで仮想ノードが必要な理由

ConsistentHashing - コンシステント・ハッシュ法

とあるチャットで聞かれて図まで書いて解説したのでもったいないからエントリー化。ちなみにチャットが1時間弱だったのでこういうタイトルにした。

で、Bが消えるとBの責任範囲が全部Dに押し付けられてDがかわいそうでしょ。


Dの仕事が増えるでしょ。Cとか暇そうじゃん!サーバを複数用意しているメリットが薄れてる。みんなが同じくらい働くのが望ましい。


で、Bが1個の点で表現されているから「Bの手前」もDの1個だけで、そのせいで全部Dが引き受けるはめになった。つまり、仕事が細かく分割されてなくて1個の塊だから引き継ぐ人も1人だけで引き継いだ人涙目。あらかじめ仕事を100分割しとけばみんなで分担して肩代わりできて幸せだよね。


だからサーバが5個だけど点は5個じゃなくて500個打とう。それが仮想ノード。

実装はどうするの?という質問に対して

今[IP, Port]で持っているサーバのデータをたとえば[IP, Port, X](0 <= X < 100)にしてからハッシュを計算すれば、1台のサーバにつきハッシュ値が100個できるよね。


一つのサーバにつき異なるハッシュ値が100個ふられればそれでいい。実体はなくていい。あくまでコンシステントハッシュのわっかきざみの時にそうするだけ。


Xの値は保存しておく必要がないよね。アクセスに必要ないから。だからハッシュ値を計算するときに適当な値をくっつけて100個ことなるハッシュ値を作ればいいだけ。


質問:「乱数でいいの?」


乱数だと問い合わせ窓口が複数台になったときに窓口それぞれの刻み方が同じにならないから、シードを共有する必要があるね。

「これがあった方が追加削除のときにいいですよ」ではなくほとんどmustだっていう話

追加削除の話がわかりやすいと思ったので例にしたけど最初のハッシュ値で割り振る段階でそもそもCがさぼり気味じゃない?そしてEが働き過ぎ。


ハッシュ値で振るとランダムに振るようなもんだからばらつきが出てしまう。それを解決するためにはそもそも仮想ノードを100個くらい用意する必要がある。ほとんどmust。


資料の半ばに描いてあるグラフがあるじゃない?
>この実験から、複製を 100 から 200 用意すると妥当なバランスを実現できるといえる。 (標準偏差が平均値の 5-10% 程度になる。)


これはそういうこと


http://b.hatena.ne.jp/entry/http://d.hatena.ne.jp/nishiohirokazu/20090430/1241075459

id:hitotakuchan node数が適度にあってhash関数に偏りがなければmustではない。あと仮想node数を増やすとhop数が増えるからlog2(N)(IPv4なら32個)で十分であるとDynamoの論文には書いてあった(はず)。ルーティングテーブルの管理も大変になる。

スルーしようかと思ったけど勘違いする人が出るとかわいそうだからつっこんでおく。あなたが「仮想ノード」という言葉を使っているかは知らないが、少なくともこのエントリーや結城さんのページに書いてあることを理解していればここでいう「仮想ノード」をいくつ増やしたところでhop数が増えたりルーティングテーブルの管理も大変になったりしないことくらいわかるはず。



すみません。追記が入る前に修正したんですが。。。
ただルーティングテーブルのサイズは大きくなるのは確実だと思います。(これが管理が大変になるかどうかは知らない)
あと、mustであるというのもいいすぎであると思うのと、Dynamoの論文では20個程度で十分に分散しているという実験結果があったので100個というのは多すぎるんじゃないかと思いました。

だからDynamoうんぬんを持ち出す前にまずここで書かれている程度のコンシステントハッシュの仕組みは理解していただかないと…。Dynamoの中でコンシステントハッシュを使っているのはさておき、Dynamoとコンシステントハッシュは「似たもの」じゃないんですよ。「ルーティングテーブルのサイズは大きくなるのは確実」などの勘違いから推測するに、脳内でDHTとかP2Pなんて単語とごたまぜになっているのではないかという感じを受けますが、すくなくともこのエントリーで解説している内容の範囲ではまだハッシュテーブルは分散していないということを理解されていますか?仮想ノードをいくら増やしたところでP2Pのノードを増やした時のような問題が起こるはずがないことを理解されていますか?


以上回答です。が、コメントで本当にいいたかったのは仮想node数の100という数字の根拠についてです。参照先のグラフにあるようにハッシュ関数としてJavaのhashCode()を利用した場合には仮想nodeの総数が1000個辺りで標準偏差が平均値の 5-10% 程度になったわけです。
だとすれば物理ノードが初めから1000個あれば仮想nodeの利用はmustではないはずです。
また参照先でも述べられているようにhashCode()関数は必ずしもよくハッシュ値を空間に分散してくれないようです。つまりよりよい関数を利用すれば仮想nodeの総数が100個辺りで同程度の分散を得られる可能性があります。その場合にも物理ノード数に応じて必要な仮想node数は変わるはずです。
つまり初心者に教える教え方として1つの物理ノードに仮想node数は100個用意するのはmustだというような教え方は良くないと思ったのです。
必要な仮想node数は利用するhash関数、用意する物理ノードなどによって変化しうると教えてあげるべきではないでしょうか?

ああ、なるほど、やっと主張されている内容がわかりました。そういう意味ではmustではないです。特にRFC的な使い方のmustでは絶対にないです。編集前のチャットではそういう誤解が起こらないような流れだったのですが、わかりやすく短くする仮定で誤解を与えてしまったようですね。すみません。また「物理ノードが初めから1000個あれば」という仮定の元での議論にも感知しません。このエントリーが「ConsistentHashing - コンシステント・ハッシュ法」を呼んで「仮想ノードってなんで必要なの?」と言っている人に5個程度の物理ノードで単純に1対1にするとどういうことが起こるのかを解説した文章だという前提条件をご理解ください。