博客最近有好久没更新了。放假之前忙期末，然后又忙手头上的项目，再后来就过年了。后面打算更新快起来，也算是对自己学习的一个督促和巩固。另外，祝大家新年快乐，猴年大吉！

什么是一致性哈希(可以跳过第一段)

一致性哈希算法在1997年由麻省理工学院提出，它具备一些特性：均衡性、单调性、分散性。这些性质就我个人理解而言，所谓均衡性是说，对于不同的值，哈希的结果能比较均衡的分散于可能的结果集合里头；单调性是指，当结果集合扩展的时候，之前的映射关系可以有改变，但是这种改变只能是旧映射关系的结果变到新扩展的结果集合里头而不是映射到其他旧的结果集里头；分散性是有上一条而来的，因为分布式环境中不同的机器可能存在结果集合同步的情况，那这样映射关系可能不同，也就是说同一个值的哈希在不同机器上结果不同应该尽量避免，分散性的定义就是这种情况发生的严重程度，显然分散性越低越好。

那么我们使用的时候可以简单的认为，通过一致性哈希，可以把不同的值很均匀地映射到结果集合里头。例如PHP中的函数crc32。它会把给的字符串hash成一个32比特位的值，也就是说通过crc32可以将给的值映射到 $( 0 ～ 2^{32}-1 )$ 之间。关于PHP中的hash具体可见此处：php.net/manual/zh/function.hash.php

分布式memcached会遇到的问题

如果只有一个memcached server用来缓存数据，那么很好说，存是它，取也是它。可是现在单台不够用了，那么首先想到的肯定就是多来几台扛住。那么，这么多数据该如何存取，如何均衡地利用好这几台服务器，同时保证其中某一台down掉了，其他的依然能够正常工作，同时mission比例越小越好，down掉的服务器的压力转移到其他服务器越均衡越好。

最容易想到的莫过于取模值了。假设服务器为N台,比如从1开始，那么数据想办法弄个编号，比如从1开始设为id，那么数据在哪台存取使用如下规则(事实上可以理解成一种简单的哈希)：计算 $( X = id\%N )$ (当然了，N在实际中是正常运行的可用服务器)得到的X当做是该数据使用的服务器编号。乍一看好像这种方式还不错，但是实际上并不可取。具体可见下图：

down掉一台memcached server前后对比图

可见，虽然说压力的确依然是分散的，但是数据有很多都mission了。比如5号数据本来在server 2，但是down一台后，算出来得在server 1取用了，也就是说类似的因为一台down掉有很多其他服务器的数据都“失效了”。在down一台之后，只有某个数据的编号取模N和N-1相等，数据才不会失效，那么比例是多少呢？很简单，以最小公倍数 $( N*(N-1) )$ 为周期，每个周期里面只有前面 $(N-2)$ 个数符合这个关系,那么结果是： $( \frac{(N-2)}{N(N-1)} )$ ,并且还要再扣除在down掉的那台机器上的，结果平均下来约是： $( \frac{(N-2)}{N(N-1)} * \frac{N-1}{N} )$ 化简得到 $( \frac{N-2}{N^2} )$ ,比如有6台memcached服务器，采用这种分布式方式，那么down一台，正常数据的比例约是：11.11% ，而且服务器越多的时候这个比例越小情况也就越严重，显然这种方式不可取。那么应该如何去解决呢？

一致性哈希的运用

如果运用一致性hash，那么就可以很好地解决这个问题。可以把哈希结果集合想象成一个环，环上从０一直增长到 $(2^{32}-1)$ ，而对值进行哈希就是映射到环上的一个点。可以想到的是，可以先根据服务器编号，把现有的服务器映射到环上的各个点(数字大小)，然后根据要存取的key，把它也通过哈希映射到换上，然后顺时针去找（数字越来越大的方向去找），第一个碰到的服务器就认为是这个数据应该要取用的服务器。这么说可能不太直观，可以看下面的左图：

memcached一致性哈希分布式算法图

可见这样保证了均衡性，同时如果一台down掉，数据有效比例是 $( \frac{N-1}{N} )$ ，也就是说只有down掉的那台数据失效了，其他的不受影响，然而这种方式缺点也很明显，down掉的那一台压力全部转移到了顺时针的下一台。那...怎么办？其实可以这么搞，每台服务器都“虚拟”出很多分散的点来，这些点都代表那一台服务器。那么这样就能够克服这种压力不分散的问题了（如上图右图所示）。

可能存在的其他问题(顺便提一下)

缓存无底洞现象

增加服务器数量，效率无明显提升甚至是略有下降。往往是因为数据存取没有组织好，比如用户Ａ的数据有三项a_age,a_sex,a_name，假设只有一台服务器的时候，只用建立一个连接，多台的时候key哈希之后分散在三台服务器了，从而得建立三个连接。用户多了之后多建立的连接也是很大的开销。那么这种情况也有解决办法，比如可以通过哈希相同前缀的方式解决，用户a的数据都通过hash('a_')得到，用户b的则通过hash('_b')得到，这样就不会形成多的连接了。

永久性数据被踢现象

memcached的数据在slab占慢之后会提出数据，这种删除采用的是LRU机制。那么即使是永久性数据，如果取用的比较少，热数据进来的又比较多，那很有可能就被踢掉了。解决嘛，自然是永久数据和其他数据分开放了(往往非永久性数据用的更频繁)。

利用一致性哈希原理的memcached分布式算法的PHP实现

可见于github: github.com/Quarkay/StudyProgramming/tree/master/Blog/MemcachedConsistentHash

配置文件 config.php
<?php

/**
 * Data: 2016.02
 * Author: Quarkay blog: www.quarkay.com
 */

//memcached服务器配置
return array(
    'server1' => array('208.78.96.193','11211'),
    'server2' => array('208.78.96.193','11211'),
    'server3' => array('208.78.96.193','11211'),
);

?>
主体实现 MemcachedProxy.php
<?php

/**
 * Data: 2016.02
 * Author: Quarkay blog: www.quarkay.com
 */

interface MemcachedServerManage{
    public function addServer();
    public function delServer($serverName);
    public function checkServer($serverName);
}

interface MemcachedService{
    public function get($key);
    public function add($key,$value,$expire);
    public function delete($key);
    // 还有set,replace,...就不一一写了...
}


class MemcachedProxy implements MemcachedServerManage,MemcachedService{

    private $serverList = array(); //服务器列表，格式：hash值=>服务器编号
    private $config = null;  //存配置信息

    public function __construct(){
        $this->config = include('config.php');
        $this->addServer();
    }

    public function get($key)
    {
        return $this->getServerObj($key)->get($key);
    }

    public function add($key, $value, $expire = 0)
    {
        return $this->getServerObj($key)->add($key,$value,$expire);
    }

    public function delete($key)
    {
        return $this->getServerObj($key)->delete($key);
    }

    /**
     * 应用文中提到的一致性哈希原理取用相应服务器
     * @param $key
     * @return memcachedObj or die
     */
    protected function getServerObj($key){

        $value = $this->consistantHash($key);

        foreach($this->serverList as $k=>$serverName){
            if($k>=$value){
                if($obj = $this->checkServer($serverName)){
                    return $obj;
                }
            }
        }

        while($serverName = current($this->serverList)){
            if($obj = $this->checkServer($serverName)){
                return $obj;
            }
            $this->delServer($serverName);
            next($this->serverList);
        }

        die('无可用memcached server!');
    }

    //添加配置的服务器信息到列表(初始化操作)
    public function addServer(){
        foreach($this->config as $serverName=>$serverInfo){
            for($i=1;$i<=64;$i++){
                $tmpKey = $this->consistantHash($serverName.$i);
                $this->serverList[$tmpKey] = $serverName;
            }
        }
        ksort($this->serverList);
    }

    //从列表里删除(认为不可用的)服务器
    public function delServer($serverName){
        foreach($this->serverList as $key=>$value){
            if($value == $serverName){
                unset($this->serverList[$key]);
            }
        }
    }

    /**
     * 检测服务器是否可用
     * @param $serverName
     * @return bool|memcachedObj
     */
    public function checkServer($serverName){
        $serverInfo = $this->getServerInfo($serverName);
        $memObj = @memcache_connect($serverInfo[0], (int)$serverInfo[1]);
        if(!$memObj){
            $this->delServer($serverName);
        }
        return $memObj?$memObj:false;
    }

    //获取由服务器编号获取服务器配置信息
    protected function getServerInfo($serverName){
        if(array_key_exists($serverName,$this->config)){
            return $this->config[$serverName];
        }else{
            return false;
        }
    }

    //获取一致性hash得到的值
    protected function consistantHash($str){
        return sprintf("%u",crc32($str));
    }
}

?>
测试 test.php
<?php

/**
 * Data: 2016.02
 * Author: Quarkay blog: www.quarkay.com
 */

include('MemcachedProxy.php');

$mem = new MemcachedProxy();

$mem->get('a');
$mem->add('b',array('a'=>0),0);
$mem->delete('b');
$mem->get('d');
$mem->get('e');

?>