Python hash_ring 分布不均匀，什么是一致的哈希替代方案？

Question

我正在使用 hash_ring package用于在服务器之间分发对象。我假设分布是均匀的，因为它基于 MD5 哈希。不幸的是，情况并非如此。

我使用的是使用 uuid.uuid4() 生成的随 secret 钥。我已经证实，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]

Answer 1

散列环牺牲了 md5 测试代码的“均匀性”，以在条目数发生变化时维护映射。见http://www.lexemetech.com/2007/11/consistent-hashing.html .所以您看到的差异不是因为 uuid4，也不是因为错误，而是因为该库使用了与您的测试不同的算法。

如果您更改了 md5 代码中的 bin 数量，则需要更改模块化划分(% 8)，突然间(几乎)所有映射都会发生变化。 consistent 哈希避免了这种情况。这就是为什么它不能使用与您相同的“明显统一”的方法。

一致性方法的缺点是它不是完全统一的(它取决于垃圾箱的哈希值，而不是你放入垃圾箱中的对象的哈希值，所以你不会得到“晚上出去” “当你添加更多对象时你会期望)。但是您可以通过增加环上的点数来提高一致性 - 通过增加代码中使用的“副本”的数量。

所以假设最终的 api 与 http://amix.dk/blog/viewEntry/19367 处显示的相匹配只需为 replicas 设置一个更大的值(尝试将其加倍，甚至只加 1 - 你已经很平坦了)。

---

更新:我环顾四周，这篇博文http://amix.dk/blog/post/19369描述对最新代码所做的更改。它看起来确实使用了比 3 个更多的副本(我不完全理解代码，抱歉)而且它现在似乎基于众所周知的“标准”实现。