认识缓存之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算法整体结构图：
三、一致性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;
}
} 