当前位置： 正文

Memcache分布式布置方案–一致性Hash分布机制PHP实现

04-08 PHP 486

一致性Hash分布简介
在服务器数量不发生改变时，普通的Hash分布可以很好地运作。当服务器的数量发生改变时，问题就出来了，试想，增加一台服务器时，同一个key经过Hash之后，与服务器取模的结果跟没增加服务器之前的结果会不一样，这就导致之前保存的数据丢失。为了把丢失的数据减少到最少，可以采用一致性hash算法。

一致性hash算法分为6个步骤：

步骤1：

将一个32位整数0~2^32 -1想象成一个环，将0作为圆环的头，2^32 -1作为圆环的尾，把它连接起来。当然这只是想象。
在这里插入图片描述

步骤2：

通过Hash函数把key处理成整数。

function mHash($key){
    $md5 = substr(md5($key),0,8);
    $seed = 31;
    $hash = 0;
   for($i = 0; $i < 8; $i++){
        $hash = $hash*$seed + ord($md5{$i});
        $i++;
    }
    return $hash & 0x7FFFFFFF;

}

$key1 = mHash("key1");
$key2 = mHash("key2");
$key3 = mHash("key3");
$key4 = mHash("key4");

把key处理成整数后，就可以在环中找到一个位置与之对应图

步骤3：

把memcached群映射到环上，使用Hash函数处理服务器所使用的IP地址。

假如有3台服务器，分别使用IP（127.0.0.1），IP（127.0.0.2），IP（127.0.0.3），使用下面的方法映射到环上。

$server1 = mHash("127.0.0.1");
$server2 = mHash("127.0.0.2");
$server3 = mHash("127.0.0.3");

步骤4：把数据映射 到服务器上

沿着环顺时针方向的key出发，知道遇到下一个服务器为止，把key对应的数据保存到这个服务器上。根据上面的方法，key4和key3保存到server2上，key2保存到server1上，key1保存到server3上。

步骤5：移除服务器

考虑一下，如果server2服务器崩溃了，那么受最大影响的仅是沿着server2逆时针出发直到下一个服务器之间的数据，也就是映射到server2上的那些数据。然后依照规则，将server2服务器上的数据移植下一个服务器上即可。

在上例中，需要进行变动的有key3和key4对应的数据，把这些数据重新映射到server1上即可。

步骤6：添加服务器。

再考虑一下，如果要添加一个服务器server4，用之前的方法把它映射到key3和key4之间，这时受到的影响是沿着server4逆时针出发直至遇到下一个服务器之间的数据，把这些数据重新映射到server4上即可。

在这里仅需要变动的只有key4对应的数据，将其重新映射到server4上即可。

使用PHP实现一致性Hash分布算法的代码如下：（注：个人理解所编写，并不权威）

<?php
class FlexiHash
{
    private $serverList = array();//保存服务器列表
    private $isSorted = FALSE;//记录服务器列表是否已经排过序
/*添加服务器*/
function addServer($server){
    $hash = $this->mHash($server);

    if(!isset($this->serverList[$hash])){
        $this->serverList[$hash] = $server;
    }

    $this->isSorted = FALSE;
    return TRUE;
}

/*移除服务器*/
function removeServer($server){

    $hash = $this->mHash($server);

    if(isset($this->serverList[$hash])){
        unset($this->serverList[$hash]);//unset只是销毁了某个变量，并不会重建数组索引
    }

    $this->isSorted = FALSE;
    return TRUE;
}

/*根据值查找所在服务器*/
function lookup($key){
    $hash = $this->mHash($key);
    /*将数组按键由小到大排序*/
    if(!$this->isSorted) {
        ksort($this->serverList);
        $this->isSorted = TRUE;
    }
    /*由于数组是按键由小到大排列的，如果$hash小于等于数组的键，则返回该键的value，即服务器IP*/
    foreach($this->serverList as $pos => $server) { 
        if($hash <= $pos) {
            return $server;
        }
    }
    /*如果上述遍历没有找到合适的值，则返回第一个*/
    return $this->serverList[current(array_keys($this->serverList))];
}

/*hash函数*/
function mHash($key){
    $md5 = substr(md5($key),0,8);
    $seed = 31;
    $hash = 0;

    for($i = 0; $i < 8; $i++){
    $hash = $hash*$seed + ord($md5{$i});
        $i++;
    }
    return $hash & 0x7FFFFFFF;
}

}
?>

测试代码：

<?php
class FlexiHash
{
    private $serverList = array();//保存服务器列表
    private $isSorted = FALSE;//记录服务器列表是否已经排过序
/*添加服务器*/
function addServer($server){
    $hash = $this->mHash($server);

    if(!isset($this->serverList[$hash])){
        $this->serverList[$hash] = $server;
    }

    $this->isSorted = FALSE;
    return TRUE;
}

/*移除服务器*/
function removeServer($server){

    $hash = $this->mHash($server);

    if(isset($this->serverList[$hash])){
        unset($this->serverList[$hash]);//unset只是销毁了某个变量，并不会重建数组索引
    }

    $this->isSorted = FALSE;
    return TRUE;
}

/*根据值查找所在服务器*/
function lookup($key){
    $hash = $this->mHash($key);
    /*将数组按键由小到大排序*/
    if(!$this->isSorted) {
        ksort($this->serverList);
        $this->isSorted = TRUE;
    }
    /*由于数组是按键由小到大排列的，如果$hash小于等于数组的键，则返回该键的value，即服务器IP*/
    foreach($this->serverList as $pos => $server) { 
        if($hash <= $pos) {
            return $server;
        }
    }
    /*如果上述遍历没有找到合适的值，则返回第一个*/
    return $this->serverList[current(array_keys($this->serverList))];
}

/*hash函数*/
function mHash($key){
    $md5 = substr(md5($key),0,8);
    $seed = 31;
    $hash = 0;

    for($i = 0; $i < 8; $i++){
    $hash = $hash*$seed + ord($md5{$i});
        $i++;
    }
    return $hash & 0x7FFFFFFF;
}

}
?>

运行结果如下：

注：关于哈希算法，读者可以自己编写自己的，也可以运用PHP自带函数或方法。

例如：一个比较简单的

echo sprintf('%u',crc32("test"));

一致性hash分布优化
上述方法的缺点如下：

服务器算出的mhash()，并不均匀，就会出现，数据分配不均的现象。
移除一个服务器后，会将此服务器的数据，全部转移至下一个服务器，并不能将其分担给其余服务器。
解决方法：

创建若干的虚拟节点，这样，done掉一台服务器的话，数据会近似均匀的分给其他几台服务器。

实现方式：

<?php
class FlexiHash
{
    private $serverList = array();//保存服务器虚拟节点
    private $isSorted = FALSE;//记录服务器列表是否已经排过序
    protected $_mul = 64;//每台服务器分成64个虚节点


    /*添加服务器*/
    function addServer($server){
        for($i=0; $i<$this->_mul; $i++) {
            $node = $server.'-'.$i;//给虚节点起名字
            if(!isset($this->serverList[$this->mHash($node)])){
                $this->serverList[$this->mHash($node)] = $server;
            }
        }
        $this->isSorted = FALSE;
        return TRUE;
    }

    /*移除服务器的所有虚拟节点*/
    function removeServer($server){
        foreach($this->serverList as $key=>$value) {
            if($this->serverList[$key] == $server){
                unset($this->serverList[$key]);
            }
        }
        $this->isSorted = FALSE;
        return TRUE;
    }

    /*根据值查找所在服务器*/
    function lookup($key){
        $hash = $this->mHash($key);
        /*将数组按键由小到大排序*/
        if(!$this->isSorted) {
            ksort($this->serverList);
            $this->isSorted = TRUE;
        }
        /*由于数组是按键由小到大排列的，如果$hash小于等于数组的键，则返回该键的value，即服务器IP*/
        foreach($this->serverList as $pos => $server) { 
            if($hash <= $pos) {
                return $server;
            }
        }
        /*如果上述遍历没有找到合适的值，则返回第一个*/
        return $this->serverList[current(array_keys($this->serverList))];
    }

    /*hash函数*/
    function mHash($key){
        $md5 = substr(md5($key),0,8);
        $seed = 31;
        $hash = 0;

        for($i = 0; $i < 8; $i++){
            $hash = $hash*$seed + ord($md5{$i});
            $i++;
        }
        return $hash & 0x7FFFFFFF;
    }

    function getAllServers(){
        return $this->serverList;
    }

}
?>

测试：

<?php
$hserver = new FlexiHash();

$hserver -> addServer("127.0.0.1");
$hserver -> addServer("127.0.0.2");
$hserver -> addServer("127.0.0.3");
$hserver -> addServer("127.0.0.4");
$hserver -> addServer("127.0.0.5");

echo "save key1 in server: " . $hserver->lookup("key1")."<br>";
echo "save key2 in server: " . $hserver->lookup("key2")."<br>";

echo "=============================="."<br>";

$hserver->removeServer("127.0.0.1");

echo "save key1 in server: " . $hserver->lookup("key1")."<br>";
echo "save key2 in server: " . $hserver->lookup("key2")."<br>";

echo "=============================="."<br>";

$hserver->addServer("127.0.0.1");

echo "save key1 in server: " . $hserver->lookup("key1")."<br>";
echo "save key2 in server: " . $hserver->lookup("key2")."<br>";

echo "=============================="."<br>";


//var_dump($hserver->getAllServers());
?>

微信公众号
手机浏览(小程序)
0
分享到：

猜你喜欢

laravel Apache 伪静态
PHP

08-14 1677
《PPT从零基础到高手快速掌握PPT的各种应用场合》视频教程 – 〖官方精品资源〗 – 珊瑚贝 –
服务器开发|运维|后端

07-10 1982免费
go语言开发文档
服务器开发|运维|后端

06-20 1719
Hyperf 的AOP 面向切面编程实战
PHP

05-06 1514
用php找出字符串中连续重复次数最多的字符，你有方法吗？
面试题/算法&算力分析

05-06 2137
AOP 面向切面编程
PHP

04-30 2151
没有账号？ 忘记密码？