认识缓存之memcached【3】分布式部署

wera00 2014-08-13

    就像memcached章节【1】中“典型应用”结构图中表示的那样,很多时候1台memcached服务器根本不能满足我们的要求,需要布置多台memcached服务器。这个时候就需要我们解决如何将数据保存到多台memcached服务器上。有两种解决方案:第一种是普通Hash分布;第二种是一致性Hash分布。

一、普通Hash分布

1、普通hash分布,hash算法如下:

function mHash($key){
    $md5 = substr(md5($key), 0, 10);
    $seed = 33;//这是典型的time 33 hash算法
    $hash = 0;

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

    首先通过md5把key处理成一个32位字符串,取其前10字符。在经过Hash算法处理成一个整数并返回,然后映射到其中一台memcached服务器。

2、使用方法

    假设有两台memcached服务器,可以通过下面方式映射:

$servers = array(
    array("host"=>"192.168.1.1", "port"=>11211),
    array("host"=>"192.168.1.2", "port"=>11211)
);

$key = "key";
$value="value";

$sc = $servers[mhash($key) % 2];

$memcached = new Memcached($sc);
$memcached->set($key,$value);

    这样得到的就是其中一台服务器的配置,利用这个配置连接memcached服务器。这样就完成了分布式部署。取数据跟保存数据的方法一样,差别就是把set改为get指令就可以了。

二、一致性hash分布

    在服务器数量不发生变化的时候,普通hash分布可以很好地运作。当服务器数量发生变化时,问题就会出现。例如:增加一台服务器时,同一个key经过hash之后,与服务器取模的结果跟没增加服务器之前的结果不一样,这就导致之前保存的数据丢失。为了把丢失的数据减到最少,可以采取一致性hash分布算法解决。

    一致性Hash算法的6个步骤,如下:

    ①将一个三十二位整数(即0~2^32-1)想象成一个环,将0作为圆环的头,2^32-1作为圆环的尾,把它连接起来,就成为一个环。

    ②通过Hash函数把key处理成整数。例如把4个key(key1~key4)通过Hash函数处理成整数:

       $key1 = mHash("key1");

       $key2 = mHash("key2");

       $key3 = mHash("key3");

       $key4 = mHash("key4");

    把key处理成整数之后,就可以在换种找到一个位置与之对应。

    ③把memcached映射到环上,使用Hash函数处理服务器所使用的IP地址。例如:有三台服务器,分别使用(192.168.1.1,192.168.1.2,192.168.1.3)使用下面的方法映射到环上:

      $server1 = mHash("192.168.1.1");

      $server2 = mHash("192.168.1.2");

      $server3 = mHash("192.168.1.3");

   经过上面几个步骤,我们把数据的key和服务器映射到同一个环上。

    ④把数据映射到服务器上。沿着圆环顺时针方向的key触发,直到遇到一个服务器为止,把key对应的数据保存到这个服务器上。根据上面的方法,一次类推,将所有的key保存到server中。

    ⑤移除服务器。考虑一下,如果现在server2服务器崩溃了,那么受到影响的仅是那些沿着server2逆时针出发遇到下一个服务器之间的数据。

    ⑥添加服务器。在考虑一下,如果现在需要添加1台服务器server4,用之前的方法把它映射到环上。这时受影响的是沿着server4逆时针出发直到下一个服务器之间的数据,会把这部分数据保存到server4上。

   下面是一致性hash算法整体结构图:

认识缓存之memcached【3】分布式部署
三、一致性hash算法实现

<?php
class FlexHash{
	//保存服务器列表
	private $serverList = array();
	//记录服务器列表是否已经排序
	private $isSorted = FALSE;
	/**
	 * 添加一个服务器到服务器列表中
	 * @param String $server
	 * @return boolean
	 */
	function addServer($server){
		$hash = mHash($server);
		if(!isset($this->serverList[$hash])){
			$this->serverList[$hash] = $server;
		}
		$this->isSorted = FALSE;
		return true;
	}
	/**
	 * 从服务器列表中删除一个服务器
	 * @param string $server
	 * @return boolean
	 */
	function removeServer($server){
		$hash = mHash($server);
		if(isset($this->serverList[$hash])){
			unset($this->serverList[$hash]);
		}
		$this->isSorted = false;
		return true;
	}
	/**
	 * 从服务器列表中找到一个适合的服务器存放数据
	 * @param unknown_type $key
	 * @return unknown|multitype:
	 */
	function lookup($key){
		$hash = mHash($key);
		if(!$this->isSorted){
			krsort($this->serverList,SORT_NUMERIC);
			$this->isSorted = true;
		}
		foreach ($this->serverList as $pos=>$server){
			if($hash>=$pos) return  $server;
		}
		return $this->serverList[count($this->serverList)-1];
	}
	/**
	 * 自定义的time 33 hash算法
	 * @param unknown_type $key
	 * @return boolean
	 */
	private function mHash($key){
	    $md5 = substr(md5($key), 0, 10);
	    $seed = 33;//这是典型的time 33 hash算法
	    $hash = 0;
	
	    for($i=0;$i<10;$i++){
	        $hash = $hash * $seed + ord($md5{$i});
	        $i++;
	    }
	    return $hash & 0x7FFFFFFF;
	}
}

相关推荐