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

    就像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算法整体结构图：

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