场景
随着数据量的增大，现在很多单机服务器压力也在逐渐增大，到某一阶段撑不住了，一般情况下都会考虑集群，或者分片处理。分片的话就会考虑到一个问题怎么确定某一个key值对应的服务器或者片的位置。一般情况下都是几种方式来处理，之后会讲到几种hash算法的优缺点，在这之前首先了解一下一致性的几个原则。
均衡性(Balance)
平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。
单调性(Monotonicity)
单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲区加入到系统中，那么哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲区中去，而不会被映射到旧的缓冲集合中的其他缓冲区。（这段翻译信息有负面价值的，当缓冲区大小变化时一致性哈希(Consistent hashing)尽量保护已分配的内容不会被重新映射到新缓冲区。）
一、求余
求余算是我们一般情况下比较常见的hash算法，例如假设我们有5台服务器，然后我们把对应的key与5求余，得到的数就是我们对应服务器的下标。这种方式比较常见，比如数据库分表等有些会才用这种方式去处理。但是这种方式有一个明显的缺点，那就是不利于扩展，假设我们有一台服务器挂掉了，或者我们要新增加一台服务器，这个时候，求余的基数就发生了改变，那么很大一部分数据都会受到影响。这明显不符合单调性，当然也有解决办法，那就是每次增加服务器都是成倍增加，然后新的数据可以对应映射到新的服务器上，老的数据不变。当然这样成本比较高。
二、环形hash空间（hash环）
考虑通常的 hash 算法都是将 value 映射到一个 32 为的 key 值，也即是 0~2^32-1 次方的数值空间；我们可以将这个空间想象成一个首（ 0 ）尾（ 2^32-1 ）相接的圆环，如下面图 1 所示的那样。
然后我们把服务器节点映射到对应hash数值空间中，一般情况可以根据服务器ip地址+端口号的方式hash。然后我们把key按照同样的hash算法一样映射到hash环上，接下来要考虑的就是如何将对象映射到 cache 服务器上去了。在这个环形空间中，如果沿着顺时针方向从对象的 key 值出发，直到遇见一个 cache ，那么就将该对象存储在这个 cache 上，因为对象和 cache 的 hash 值是固定的，因此这个 cache 必然是唯一和确定的。
前面讲过，通过 hash 然后求余的方法带来的最大问题就在于不能满足单调性，当 cache 有所变动时， cache 会失效，进而对后台服务器造成巨大的冲击，现在就来分析分析 consistent hashing 算法。
移除 cache
考虑假设 cache B 挂掉了，根据上面讲到的映射方法，这时受影响的将仅是那些沿 cache B 逆时针遍历直到下一个 cache （ cache C ）之间的对象，也即是本来映射到 cache B 上的那些对象。
添加 cache
再考虑添加一台新的 cache D 的情况，假设在这个环形 hash 空间中， cache D 被映射在对象 object2 和 object3 之间。这时受影响的将仅是那些沿 cache D 逆时针遍历直到下一个 cache （ cache B ）之间的对象（它们是也本来映射到 cache C 上对象的一部分），将这些对象重新映射到 cache D 上即可。
如此一来，如果我们对服务器进行增减，只会影响到少部分服务器，并不会对导致大量的缓存都命中到其他服务器上去。但是缺点的话就是，如果我们服务器数量不多，有可能恰好服务器hash出来对应环上的位置某一个跟其他节点离的较远，而其他的相对间隔较近，这就会导致服务器上缓存分布不均匀。
三、虚拟节点
为了解决实体节点数据分布不均匀的问题，我们可以采用增加虚拟节点的方式来应对，例如我们有10台实体服务器，我们可以为每台服务器设置1000个虚拟服务器，然后将虚拟服务器也按照对应的hash算法映射到hash环中，然后缓存key找到对应的虚拟服务器节点，再由虚拟服务器与实习服务器映射关系找到对应实体服务器。
<?php
// 一致性哈希算法
class ConsistentHashing
{
protected $nodes = array(); //真实节点
protected $position = array(); //虚拟节点
protected $mul = 64; // 每个节点对应64个虚拟节点
/**
* 把字符串转为32位符号整数
*/
public function hash($str)
{
return sprintf('%u', crc32($str));
}
/**
* 核心功能
*/
public function lookup($key)
{
$point = $this->hash($key);
//先取圆环上最小的一个节点,当成结果
$node = current($this->position);
// 循环获取相近的节点
foreach ($this->position as $key => $val) {
if ($point <= $key) {
$node = $val;
break;
}
}
reset($this->position); //把数组的内部指针指向第一个元素，便于下次查询从头查找
return $node;
}
/**
* 添加节点
*/
public function addNode($node)
{
if(isset($this->nodes[$node])) return;
// 添加节点和虚拟节点
for ($i = 0; $i < $this->mul; $i++) {
$pos = $this->hash($node . '-' . $i);
$this->position[$pos] = $node;
$this->nodes[$node][] = $pos;
}
// 重新排序
$this->sortPos();
}
/**
* 删除节点
*/
public function delNode($node)
{
if (!isset($this->nodes[$node])) return;
// 循环删除虚拟节点
foreach ($this->nodes[$node] as $val) {
unset($this->position[$val]);
}
// 删除节点
unset($this->nodes[$node]);
}
/**
* 排序
*/
public function sortPos()
{
ksort($this->position, SORT_REGULAR);
}
}
// 测试
$con = new ConsistentHashing();
$con->addNode('a');
$con->addNode('b');
$con->addNode('c');
$con->addNode('d');
$key1 = 'www.zhihu.com';
$key2 = 'www.baidu.com';
$key3 = 'www.google.com';
$key4 = 'www.testabc.com';
echo 'key' . $key1 . '落在' . $con->lookup($key1) . '号节点上！<br>';
echo 'key' . $key2 . '落在' . $con->lookup($key2) . '号节点上！<br>';
echo 'key' . $key3 . '落在' . $con->lookup($key3) . '号节点上！<br>';
echo 'key' . $key4 . '落在' . $con->lookup($key4) . '号节点上！<br>';
