Python 哈希环分布不均匀，有哪些一致性哈希替代方案？

Question

我正在使用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]

Answer 1

哈希环牺牲了你md5测试代码的“均匀性”，以便在条目数量变化时保持映射关系。你可以查看这个链接：http://www.lexemetech.com/2007/11/consistent-hashing.html。所以你看到的差异并不是因为uuid4，也不是因为出错，而是因为这个库使用了和你测试时不同的算法。

如果你在md5代码中改变了箱子的数量，你就需要改变模运算（也就是% 8），这样几乎所有的映射都会改变。一致性哈希避免了这种情况。这就是为什么它不能使用你那种“显然均匀”的方法。

一致性方法的缺点是它并不是完全均匀的（它依赖于箱子的哈希值，而不是你放入箱子的对象的哈希值，所以当你添加更多对象时，你不会得到预期的“均匀分布”）。不过，你可以通过增加环上的点数来提高均匀性——也就是增加代码中使用的“副本”数量。

所以假设最终的API和这个链接中展示的相匹配：http://amix.dk/blog/viewEntry/19367，只需为replicas设置一个更大的值（可以试着翻倍，或者仅仅加1——你已经相当平坦了）。

---

更新：我再查了一下，这篇博客文章http://amix.dk/blog/post/19369描述了最新代码的变化。看起来它确实使用了超过3个副本（我不太理解代码，抱歉），而且似乎现在是基于一个众所周知的“标准”实现。