3

Memcachedは、分散コンシステントハッシュを使用して、キーを配置するサーバーを選択しますが、どのハッシュアルゴを使用して、サーバー選択にKetamaアルゴが適用される最終ハッシュに文字列キーをマッピングします。そして、同じようなキーを異なるサーバーに拡散するのに、そのアルゴリズムはどれほど優れているのでしょうか。

4

1 に答える 1

7

hash.cのソースコードによると、memcachedは次のアルゴリズムを使用します。

ここで使用されているハッシュ関数は、1996年のBobJenkinsによるものです。

http://burtleburtle.net/bob/hash/doobs.html

「BobJenkins著、1996年。bob_jenkins@ burtleburtle.net。このコードは、プライベート、教育、または商用のいずれの方法でも使用できます。無料です。」

ボブ・ジェンキンスのウェブサイトから：

現在使用しているものよりも高速で徹底的なハッシュテーブルルックアップ用の新しいハッシュ関数を提供します。また、それがより徹底的であることを確認する方法も提供します。

また、彼の要件は次のとおりです。

  • キーは、整列されていない可変長バイト配列です。
  • キーがそのような配列である場合があります。
  • 独立したハッシュ関数のセットが必要になる場合がありました。
  • キーの平均長は8バイトから200バイトの範囲でした。
  • キーは、文字列、数字、ビット配列、または奇妙なものである可能性があります。
  • テーブルのサイズは、2の累乗を含めて何でもかまいません。
  • ハッシュは古いものより高速でなければなりません。
  • ハッシュは良い仕事をしなければなりません。

..。

その場合、実際の要件は、優れたハッシュ関数が、ユーザーが実際に使用するキーのハッシュ値を均一に分散する必要があることです。

To get back to your other question, he measured the ability of the algorithm to uniformly distribute hash values, so I would presume that the hash does a good job at spreading similar keys to different servers. If you have concerns, the code is isolated so you should be able to run your own tests.

于 2012-05-03T15:29:56.093 に答える