Memcached分布式布置方案-

发布时间:2017-3-28 10:30:03编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"Memcached分布式布置方案-",主要涉及到Memcached分布式布置方案-方面的内容,对于Memcached分布式布置方案-感兴趣的同学可以参考一下。

http://lib.csdn.net/article/16/46895?knId=407


一致性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;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
$key1 = mHash("key1");
$key2 = mHash("key2");
$key3 = mHash("key3");
$key4 = mHash("key4");
  • 1
  • 2
  • 3
  • 4

把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");
  • 1
  • 2
  • 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;
    }

}
?>
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64

测试代码:

<?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>";
?>
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28

运行结果如下:

示例

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

例如:一个比较简单的

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

一致性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;
    }

}
?>
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68

测试:

<?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());
?>
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31

运行结果:

示例

再看服务器的分布情况:

示例



上一篇:ThreadLocal的理解
下一篇:android string.xml 添加特殊字符,如多个空格等

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款