理解一致性哈希算法

Question

我最近几天一直在研究PHP的一致性哈希算法。我想更好地理解一致性哈希的工作原理，以便在即将进行的项目中使用它。对我来说，似乎Flexihash是唯一易于理解的纯PHP实现，因此我从中做出了一些笔记。

我自己创建了一个小算法，试图理解它的工作原理，并使其尽可能快地运行。令我惊讶的是，我的算法与Flexihash相比速度非常快，这让我想知道我的实现方式是否存在缺陷，或者我是否没有掌握整个概念的重要部分。

以下是速度差异列表，包含100万个连续键（0到1,000,000）的迭代。每个节点显示实际散列到该特定节点的键数。

Flexihash:
 Time: 269 seconds
Speed: 3714 hashes/sec

 node1: 80729
 node2: 88390
 node3: 103623
 node4: 112338
 node5: 79893
 node6: 85377
 node7: 80966
 node8: 134462
 node9: 117046
node10: 117176

My implementation:
 Time: 3 seconds
Speed: 265589 hashes/sec

 node1: 100152
 node2: 100018
 node3: 99884
 node4: 99889
 node5: 100057
 node6: 100030
 node7: 99948
 node8: 99918
 node9: 100011
node10: 100093

这是我目前实现的哈希算法。

class Base_Hasher_Consistent
{
    protected $_nodes;

    public function __construct($nodes=NULL)
    {
        $this->_nodes = array();

        $node_count = count($nodes);
        $hashes_per_node = (int)(PHP_INT_MAX / $node_count);

        $old_hash_count = 0;

        foreach($nodes as $node){
            if(!($node == $nodes[$node_count-1])){
                $this->_nodes[] = array(
                    'name' => $node,
                    'begin' => $old_hash_count,
                    'end' => $old_hash_count + $hashes_per_node - 1
                );

                $old_hash_count += $hashes_per_node;
            }else{
                $this->_nodes[] = array(
                    'name' => $node,
                    'begin' => $old_hash_count,
                    'end' => PHP_INT_MAX
                );
            }
        }
    }

    public function hashToNode($data_key,$count=0)
    {
        $hash_code = (int)abs(crc32($data_key));

        foreach($this->_nodes as $node){
            if($hash_code >= $node['begin']){
                if($hash_code <= $node['end']){
                    return($node['name']);
                }
            }
        }
    }
}

我是否遗漏了什么，还是说这个算法确实比Flexihash更快？另外，我了解Flexihash支持查找多个节点，所以我不确定这是否有任何关系。

我只想要一些确认，以确保我理解了一致性哈希的工作原理，或者可能是一些真正讲解得很好的文章链接。

谢谢！

- EstelS

---

http://en.wikipedia.org/wiki/Consistent_hashing - Denis de Bernardy

您没有使用副本。 - Ivan Rysev

Answer 1

EstelS说：

我只想得到一些关于一致性哈希算法的确认，或者是一些真正解释它的文章的链接。

这是一篇优秀的文章，它让我写了Flexihash： http://www.tomkleinpeter.com/2008/03/17/programmers-toolbox-part-3-consistent-hashing/

我已经很久没有看过这段代码了——你的代码可能快得多。速度从来不是我的关注点。但也有可能你的代码完全不同 :)

另请参见GitHub上rs的这个提交，声称使用二分查找可以提高70倍的速度。如果有人能确认它是好的，我会合并它。

干杯！ 保罗

- Paul Annesley

---

那篇文章太棒了！！我一直在努力理解它，这是我看过的最好的解释。 - PlanetUnknown

Answer 2

你是想了解crc32的工作原理，还是只是想知道如何编写一个好的“桶”实现呢？

你的“桶”实现看起来不错。如果你只是这样做，可能会更快：

$bucket_index = floor($hash_code / $hashes_per_node);
return $this->_nodes[$bucket_index]['name'];

你写的“算法”只是创建了$nodes个桶，并确定了$data_key应该放在哪个桶中。实际使用的哈希算法是crc32，如果你正在做桶操作，这可能不是一个理想的算法。

如果你想知道crc32是如何工作以及为什么哈希是一致的，请在维基百科或其他地方查找。据我所知，不存在不一致的哈希算法，因此所有哈希算法都是一致的。

哈希算法的一个特征是它可以生成非常不相似的哈希值，即使数据键相似。这对于crc32来说是正确的，因为crc32旨在检测较小的更改。但它不能保证生成的哈希值是“良好分布”的。由于你正在做桶操作，你需要一个具有特定属性的哈希算法，它可以在整个光谱上生成哈希值。对于crc32，它可能只是巧合地运行得非常好。我建议使用md5。

- Halcyon

---

我想知道如何编写一个好的“桶”实现。我一直在想象32位空间中crc32哈希可以映射到一个无形的环，然后将每个节点分配给该环的相等大小的切片。这种思考方式有效吗？此外，您能否举例说明如何使用md5作为哈希而不是crc32，因为md5应该具有更好的密钥分布？ - EstelS

你的Flexihash有一个解决方案，但我不确定是否完全同意。请注意它返回一个字符串，但你可以使用hexdec()函数将其转换为整数。https://github.com/pda/flexihash/blob/master/classes/Flexihash/Md5Hasher.php - Halcyon