仅仅把 Memcached 服务器集群地址通过一致性哈希转映射在圆环上，可能会出现数据不能均匀地分配给各台 Memcached 服务器。
解决方案是引入虚拟节点，就是把每个映射在圆环上的服务器地址（物理节点）转变成更多的（注：关于虚拟节点的个数参考①）虚拟节点。
修改 Memcached 笔记与总结（6）PHP 实现 Memcached 的一致性哈希分布算法 中的代码：
类 consistentHash 增加私有的成员属性：$position，以键值形式保存所有虚拟节点的哈希值（键）和对应的服务器（值）的一维数组
结构如下：
array(
1589449412 => '192.168.1.1'
2566189294 => '192.168.1.1'
4025729144 => '192.168.1.2'
2135743977 => '192.168.1.2'
139193727 => '192.168.1.3'
1522140696 => '192.168.1.3'
)
私有成员属性 $serverList 修改为 以二维数组保存服务器列表和每一个服务器下虚拟节点的哈希值，结构如下：
array(
'192.168.1.1' => array(
0 => 1589449412,
1 => 700064338
),
'192.168.1.2' => array(
0 => 1559997597,
1 => 737975307
)
)
私有成员属性 isSorted 修改为 记录虚拟节点哈希值列表是否已经排列过序
addServer 方法的实现：
public function addServer($server, $nodesNum = 25){
if (isset($this->serverList[$server])) {
return;
}
//增加虚拟节点，默认每个物理节点变成25个虚拟节点
for($i = 0; $i < $nodesNum; $i++){
$hash = $this->_hash($server.'-'.$i);//计算虚拟节点的Hash值
$this->position[$hash] = $server;
$this->serverList[$server][] = $hash;
}
//此时虚拟节点表发生了变化，因此标识为FALSE
$this->isSorted = FALSE;
return TRUE;
}
removeServer 方法的实现：
public function removeServer($server){
if (!isset($this->serverList[$server])) {
return;
}
//循环position数组，如果要删除的服务器的值等于position数组某个元素的值，则删除该元素
foreach($this->position as $k=>$v){
if($server == $v){
unset($this->position[$k]);
}
}
unset($this->serverList[$server]);
$this->isSorted = FALSE;
return TRUE;
}
lookup 方法的实现：
public function lookup($key){
//计算出服务器的Hash值
$hash = $this->_hash($key);
//判断服务器列表是否排过序
if (!$this->isSorted) {
//倒序排列（把虚拟节点列表转换成逆时针圆环）
krsort($this->position, SORT_NUMERIC);
$this->isSorted = TRUE;
}
//遍历虚拟节点列表，找到合适的服务器并返回
foreach($this->position as $server_hash=> $server){
if ($hash >= $server_hash) return $server;
}
return end($this->position);
}
完整代码：
<?php
//把字符串转换为整数
interface hash{
public function _hash($str);
} interface distribute{
//在当前的服务器列表中找到合适的服务器存放数据
public function lookup($key); //添加一个服务器到服务器列表中
public function addServer($server); //从服务器列表中删除一个服务器
public function removeServer($server);
} class consistentHash implements hash, distribute{ private $serverList = array();//以二维数组保存服务器列表和每一个服务器下虚拟节点的哈希值
private $position = array();//以键值形式保存所有虚拟节点的哈希值（键）和对应的服务器（值）的一维数组
private $isSorted = FALSE; //记录虚拟节点哈希值列表是否已经排列过序 public function _hash($str){
return sprintf('%u', crc32($str));//把字符串转成32为无符号整数
} public function lookup($key){
//计算出服务器的Hash值
$hash = $this->_hash($key); //判断服务器列表是否排过序
if (!$this->isSorted) {
//倒序排列（把虚拟节点列表转换成逆时针圆环）
krsort($this->position, SORT_NUMERIC);
$this->isSorted = TRUE;
} //遍历虚拟节点列表，找到合适的服务器并返回
foreach($this->position as $server_hash=> $server){
if ($hash >= $server_hash) return $server;
}
return end($this->position);
} public function addServer($server, $nodesNum = 25){ if (isset($this->serverList[$server])) {
return;
} //增加虚拟节点，默认每个物理节点变成25个虚拟节点
for($i = 0; $i < $nodesNum; $i++){
$hash = $this->_hash($server.'-'.$i);//计算虚拟节点的Hash值
$this->position[$hash] = $server;
$this->serverList[$server][] = $hash;
} //此时虚拟节点列表发生了变化，因此标识为FALSE
$this->isSorted = FALSE;
return TRUE;
} public function removeServer($server){ if (!isset($this->serverList[$server])) {
return;
} //循环position数组，如果要删除的服务器的值等于position数组某个元素的值，则删除该元素
foreach($this->position as $k=>$v){
if($server == $v){
unset($this->position[$k]);
}
} unset($this->serverList[$server]); $this->isSorted = FALSE;
return TRUE;
}
} $hashserver = new consistentHash(); $hashserver->addServer('192.168.1.1');
$hashserver->addServer('192.168.1.2');
$hashserver->addServer('192.168.1.3');
$hashserver->addServer('192.168.1.4');
$hashserver->addServer('192.168.1.5'); echo 'save key1 on server:',$hashserver->lookup('key1'),'<br />';
echo 'save key2 on server:',$hashserver->lookup('key2'),'<br /><br />'; $hashserver->removeServer('192.168.1.2');
echo 'save key1 on server:',$hashserver->lookup('key1'),'<br />';
echo 'save key2 on server:',$hashserver->lookup('key2'),'<br /><br />'; $hashserver->addServer('192.168.1.6');
echo 'save key1 on server:',$hashserver->lookup('key1'),'<br />';
echo 'save key2 on server:',$hashserver->lookup('key2'),'<br /><br />';
输出：
save key1 on server:192.168.1.2
save key2 on server:192.168.1.1 save key1 on server:192.168.1.3
save key2 on server:192.168.1.1 save key1 on server:192.168.1.6
save key2 on server:192.168.1.1
参考：