我最近几天一直在研究PHP的一致性哈希算法。我想更好地理解一致性哈希的工作原理,以便在即将进行的项目中使用它。对我来说,似乎Flexihash是唯一易于理解的纯PHP实现,因此我从中做出了一些笔记。
我自己创建了一个小算法,试图理解它的工作原理,并使其尽可能快地运行。令我惊讶的是,我的算法与Flexihash相比速度非常快,这让我想知道我的实现方式是否存在缺陷,或者我是否没有掌握整个概念的重要部分。
以下是速度差异列表,包含100万个连续键(0到1,000,000)的迭代。每个节点显示实际散列到该特定节点的键数。
我自己创建了一个小算法,试图理解它的工作原理,并使其尽可能快地运行。令我惊讶的是,我的算法与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支持查找多个节点,所以我不确定这是否有任何关系。
我只想要一些确认,以确保我理解了一致性哈希的工作原理,或者可能是一些真正讲解得很好的文章链接。
谢谢!