一致性哈希算法是分布式系统中常用的算法，为什么要用这个算法？
比如：一个分布式存储系统，要将数据存储到具体的节点（服务器）上， 在服务器数量不发生改变的情况下，如果采用普通的hash再对服务器总数量取模的方法（如key%服务器总数量），如果期间有服务器宕机了或者需要增加服务器，问题就出来了。 同一个key经过hash之后，再与服务器总数量取模的结果跟之前的结果会不一样，这就导致了之前保存数据的丢失。因此，引入了一致性Hash（Consistent Hashing）分布算法
把数据用hash函数（如md5，sha1)，映射到一个圆环上，如上图所示，数据在存储时，先根据hash算法算出key的hash值，对应到这个环中的位置，如k1对应图中所示的位置同，然后沿着顺时针方向找到服务器节点B，然后把k1在存到B这个节点中。
如果B节点宕机了，则B上的数据就会落到C节点上，如下图所示
这样，只会影响C节点，对于其他节点A、D的数据不会造成影响。但是问题来了，这样会造成C节点负载过重的情况，因为C节点承担了B节点的数据，所以C节点容易宕机，这样造成了分布不均匀。
为了解决这个问题，引入了“虚拟节点“的概念：即想象空上环上有很多”虚拟节点“，一个真实的服务器节点对应多个虚拟节点，数据存储的时候沿着环的顺时针方向找到虚拟节点，就找到了对应的真实服务器节点。如下图
图中的A1、A2、B1、B2、C1、C2、D1、D2都是虚拟节点，机器A负载存储A1、A2的数据，机器B负载存储B1、B2的数据，机器C负载存储C1、C2的数据。由于这些虚拟节点数量很多，均匀分布，因此不会造成“雪崩”现象。
一致性哈希算法的PHP实现
下面给出一个接口
/** * 一致性哈希实现接口 * Interface ConsistentHash */ interface ConsistentHash { //将字符串转为hash值 public function cHash($str); //添加一台服务器到服务器列表中 public function addServer($server); //从服务器删除一台服务器 public function removeServer($server); //在当前的服务器列表中找到合适的服务器存放数据 public function lookup($key); }
这个接口分别定义了4个方法，cHash（将字符串处理为hash值）、addServer（增加一台服务器）、removeServer（移除一台服务器）、lookup（找到一台服务器来存储数据）
下面给出一个该接口的具体实现
/** * 具体一致性哈希实现 * author chenqionghe * Class MyConsistentHash */ class MyConsistentHash implements ConsistentHash { public $serverList = array(); //服务器列列表 public $virtualPos = array(); //虚拟节点的位置 public $virtualPosNum = 5; //每个节点对应5个虚节点 /** * 将字符串转换成32位无符号整数hash值 * @param $str * @return int */ public function cHash($str) { $str = md5($str); return sprintf('%u', crc32($str)); } /** * 在当前的服务器列表中找到合适的服务器存放数据 * @param $key 键名 * @return mixed 返回服务器IP地址 */ public function lookup($key) { $point = $this->cHash($key);//落点的hash值 $finalServer = current($this->virtualPos);//先取圆环上最小的一个节点当成结果 foreach($this->virtualPos as $pos=>$server) { if($point <= $pos) { $finalServer = $server; break; } } reset($this->virtualPos);//重置圆环的指针为第一个 return $finalServer; } /** * 添加一台服务器到服务器列表中 * @param $server 服务器IP地址 * @return bool */ public function addServer($server) { if(!isset($this->serverList[$server])) { for($i=0; $i<$this->virtualPosNum; $i++) { $pos = $this->cHash($server . '-' . $i); $this->virtualPos[$pos] = $server; $this->serverList[$server][] = $pos; } ksort($this->virtualPos,SORT_NUMERIC); } return TRUE; } /** * 移除一台服务器（循环所有的虚节点，删除值为该服务器地址的虚节点） * @param $key * @return bool */ public function removeServer($key) { if(isset($this->serverList[$key])) { //删除对应虚节点 foreach($this->serverList[$key] as $pos) { unset($this->virtualPos[$pos]); } //删除对应服务器 unset($this->serverList[$key]); } return TRUE; } }
然后， 我们来测试一下该算法