PHP 版的一致性hash算法

今天看豆瓣的架构PPT，其中有谈到Consistent Hashing的算法，网上搜了下，发现这方面的介绍也不算多。

通常比较常用的使用地方就是memcache分布式的时候，例如我有三台memcache，那么普通的hash算法，直接用你要取的key的hash值模取memcache的数量。

server = hash(key) mod server num;

但是如果要增加一台，那么将会有大量的缓存信息失效。所以更好的办法Consistent Hashing.

Consistent hashing算法：环状结构。虚拟节点来替换实体节点被分配到环状某一位置上（根据处理能力不同可以将一个实体节点映射到多个虚拟节点上）。主键为key的节点position = hash(key),在环上按照顺时针查找value大于position的第一个虚拟节点，由它对应的实体节点处理。下图中k就优先由虚拟节点 B来处理。

按照我的理解方式 就是将所有的cache服务器的标识分别hash到的值分布到0-pow(2,32)中. 然后将你要取的key的hash值进行比较。取第一个大于key的hash值的服务器。 如果从0-pow(2,32)也没有找到，那么则取最小hash值的服务器。

例如 上图中， 服务器 a 的hash值 为 1, b的hash值为 10, c的hash值为20, 我们取 key K 的hash值为5的位置，发现key K 大于 a 小于 b ， 那么key k就存放于服务器b上, 如果 我们取 key x 的hash值为30的位置，发现 a,b,c三个服务器的hash值都小于 key x的hash值 ， 那么 我们取 a 服务器作为存放服务器。

这样的存放方法，只会影响你最后一台服务器存放的key.而不会像取模方法的全局影响。

当然这样取key的效率就没有取模的高了，至于采用哪种方法，还是要根据你当前业务的规模来选择的。

另附上简单的算法

<?php

function consistent_hash_key($key,$servers){
   if(empty($servers)){
       return false;
   }
   $hash_serv = array();
   $hash_key = sprintf("%un",crc32($key));
   foreach ($servers as $server){
       $hash_serv[sprintf("%u",crc32($server))] = $server;
   }
  
   ksort($hash_serv,SORT_REGULAR);
  
   if(count($hash_serv) == 1){
       return array_pop($hash_serv);
   }
   $maxHash = pow(2,32);
   foreach ($hash_serv as $k => $v){
       if($hash_key < $k){
           return $v;
       }
   }
   return array_shift($hash_serv);
}

for ($i=0;$i<100;$i++){
   echo consistent_hash_key('s:'.$i,array('a','b','c','d','e'))."t".consistent_hash_key('s:'.$i,array('a','b','c','d','e','f'))."n";
?>