认识缓存之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; } }