3

サーバー間でオブジェクトを配布するためにhash_ringパッケージを使用しています。MD5ハッシュに基づいているため、分布は均一になると思います。残念ながらそうではありません。

を使用して生成されたランダムキーを使用していuuid.uuid4()ます。私は、MD5自体が実際に均一な分布を与えることを確認しました。ただし、を使用して配布してhash_ring.HashRingいる場合、ほとんどのバケットと最も少ないバケットの間で20〜30％の違いがあります。

  • hash_ringいくつかの設定を微調整することで、分布の均一性を改善できますか？
  • Pythonでコンシステントハッシュを行うための他の良い選択肢はありますか？

分布の均一性をテストするために使用したコード：

ring = hash_ring.HashRing(range(8))
for _ in range(10):
     counters = [0]*8
     for _ in range(100000):
         counters[ring.get_node(str(uuid.uuid4()))] += 1
     print counters

印刷されたもの：

[11115, 11853, 14033, 11505, 13640, 12292, 12851, 12711]
[11164, 11833, 14024, 11562, 13365, 12302, 13002, 12748]
[11354, 11756, 14017, 11583, 13201, 12231, 13135, 12723]
[11182, 11672, 13936, 11441, 13563, 12240, 13129, 12837]
[11069, 11866, 14045, 11541, 13443, 12249, 12894, 12893]
[11196, 11791, 14158, 11533, 13517, 12319, 13039, 12447]
[11297, 11944, 14114, 11536, 13154, 12289, 12990, 12676]
[11250, 11770, 14145, 11657, 13340, 11960, 13161, 12717]
[11027, 11891, 14099, 11615, 13320, 12336, 12891, 12821]
[11148, 11677, 13965, 11557, 13503, 12309, 13123, 12718]

比較のために、MD5を使用してコンシステントハッシュを直接実行しました。

for _ in range(10):
    counters = [0]*8
    for _ in range(100000):
        counters[int(hashlib.md5(str(uuid.uuid4())).hexdigest(),16)%8] += 1
    print counters

はるかに良い結果が得られます：

[12450, 12501, 12380, 12643, 12446, 12444, 12506, 12630]
[12579, 12667, 12523, 12385, 12386, 12445, 12702, 12313]
[12624, 12449, 12451, 12401, 12580, 12449, 12562, 12484]
[12359, 12543, 12371, 12659, 12508, 12416, 12619, 12525]
[12425, 12526, 12565, 12732, 12381, 12481, 12335, 12555]
[12514, 12576, 12528, 12294, 12658, 12319, 12518, 12593]
[12500, 12471, 12460, 12502, 12637, 12393, 12442, 12595]
[12583, 12418, 12428, 12311, 12581, 12780, 12372, 12527]
[12395, 12569, 12544, 12319, 12607, 12488, 12424, 12654]
[12480, 12423, 12492, 12433, 12427, 12502, 12635, 12608]
4

1 に答える 1

9

ハッシュリングは、エントリ数が変更されたときにマッピングを維持するために、md5テストコードの「イブネス」を犠牲にします。http://www.lexemetech.com/2007/11/consistent-hashing.htmlを参照してください。したがって、表示される違いは、uuid4やエラーによるものではなく、ライブラリがテストとは異なるアルゴリズムを使用しているためです。

md5コードのビンの数を変更した場合は、モジュラー除算（% 8）を変更する必要があり、突然（ほぼ）すべてのマッピングが変更されます。 コンシステントハッシュはこれを回避します。そのため、同じ「明らかに均一な」アプローチを使用することはできません。

一貫性アプローチの欠点は、完全に均一ではないことです（ビンに入れるオブジェクトのハッシュではなく、ビンのハッシュに依存するため、「均等」になることはありません。さらにオブジェクトを追加することを期待してください）。ただし、リング上のポイントの数を増やすことで、つまりコードで使用される「レプリカ」の数を増やすことで、均一性を高めることができます。

したがって、最終的なAPIがhttp://amix.dk/blog/viewEntry/19367に示されているものと一致すると仮定すると、に大きな値を設定するだけですreplicas（2倍にするか、1を追加するだけです。すでにかなりフラットです）。

更新：もう少し調べてみました。このブログ投稿http://amix.dk/blog/post/19369で、最新のコードに加えられた変更について説明しています。3つよりも多くのレプリカを使用しているようです（コードを完全には理解していません、申し訳ありません）。また、現在はよく知られている「標準」実装に基づいているようです。

于 2011-08-22T18:23:57.957 に答える