Memcached 笔记与总结（7）增加虚拟节点

时间：2022-04-09 20:38:43

仅仅把 Memcached 服务器集群地址通过一致性哈希转映射在圆环上，可能会出现数据不能均匀地分配给各台 Memcached 服务器。

Memcached 笔记与总结（7）增加虚拟节点

解决方案是引入虚拟节点，就是把每个映射在圆环上的服务器地址（物理节点）转变成更多的（注：关于虚拟节点的个数参考①）虚拟节点。

Memcached 笔记与总结（7）增加虚拟节点 

 

修改 Memcached 笔记与总结（6）PHP 实现 Memcached 的一致性哈希分布算法 中的代码：

类 consistentHash 增加私有的成员属性：$position，以键值形式保存所有虚拟节点的哈希值（键）和对应的服务器（值）的一维数组

结构如下：

Memcached 笔记与总结（7）增加虚拟节点Memcached 笔记与总结（7）增加虚拟节点
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' 
)
View Code

 

私有成员属性 $serverList 修改为 以二维数组保存服务器列表和每一个服务器下虚拟节点的哈希值，结构如下：

Memcached 笔记与总结（7）增加虚拟节点Memcached 笔记与总结（7）增加虚拟节点
array(
'192.168.1.1' => array(
0 => 1589449412,
      1 => 700064338 
   ),
  '192.168.1.2' => array(
0 => 1559997597,
      1 => 737975307 
   )
)
View Code

 

私有成员属性 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

 

 

参考：

①Memcached中一致性哈希(Consistent Hashing)的运用

②memcached 之 哈希一致性 和 虚拟节点 分析

 

标签：

相关文章