PHP实现一致性哈希(hash)分布式算法
一致性hash算法，是一种特殊的hash算法，旨在解决当node数（如存储图片的服务器数量）变化时候，尽量少数据的迁移。
场景：
如果要设计一套KV存储的系统，用户PUT一个key和value，存储到系统中，并且提供用户根据key来GET对应的value。要求随着用户规模变大，系统是可以水平扩展的，主要要解决以下几个问题。
- 系统是一个集群，包含很多节点，如何解决用户数据的存储问题？保证用户的数据尽可能平均分散到各个节点上。
- 如果用户量增长，需要对集群进行扩容，扩容完成后如何解决数据重新分布？保证不会出现热点数据节点。
原理：
由于hash算法结果一般为unsigned int型，因此对于hash函数的结果应该均匀分布在*[0,2^32-1]*区间，如果我们把一个圆环用2^32 个点来进行均匀切割，首先按照hash(key)函数算出服务器(节点)的哈希值， 并将其分布到0～2^32的圆环上。
用同样的hash(key)函数求出需要存储数据的键的哈希值，并映射到圆环上。然后从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个服务器 (节点)上。key1、key2、key3和server1、server2通过hash都能在这个圆环上找到自己的位置，并且通过顺时针的方式来将 key定位到server。按上图来说，key1和key2存储到server1，而key3存储到server2。如果新增一台server，hash 后在key1和key2之间，则只会影响key1(key1将会存储在新增的server上)，其它不变。
<?php
class FlexiHash
{
protected $_node = [];
protected $_virtualNode = 100;
protected $_position = [];
/**
* 生成hash
* 原理：hash(i) = hash(i-1) * 33 + str[i]
*/
public function cHash($str){
// return sprintf('%u',crc32($str));
$hash = 0;
for ($i=0; $i < 32; $i++) {
$hash = ($hash << 5) + $hash + ord(md5($str){$i});
}
return $hash & 0x7FFFFFFF;
}
/**
* 添加节点
*/
public function addNode($node){
if(isset($this->_node[$node])) return;
for($i = 0; $i < $this->_virtualNode; $i++){
$pos = $this->cHash($node.'_'.$i);
$this->_position[$pos] = $node;
$this->_node[$node][] = $pos;
}
$this->sortPos();
}
/**
* 查找节点
*/
public function lookup($key){
$point = $this->cHash($key);
//先取环上最小的一个节点
$node = current($this->_position);
//循环获取相近节点
foreach ($this->_position as $key => $value) {
if($point <= $key){
$node = $value;
break;
}
reset($this->_position);
}
return $node;
}
/**
* 删除节点
*/
public function delNode($node){
if(!isset($this->_node[$node])) return;
//删除虚拟节点
foreach ($this->_node as $key => $value) {
unset($this->_position[$value]);
}
//删除节点
unset($this->_node[$node]);
}
/**
* 排序
*/
public function sortPos(){
ksort($this->_position,SORT_REGULAR);
}
}
//示例:
$flexiHash = new FlexiHash();
for ($i=1;$i<10;$i++) {
$flexiHash->addNode('192.167.1.'.$i);
}
for ($i=1;$i<20;$i++){
echo "保存 key".$i." 到 server :".$flexiHash->lookup('key'.$i) . '<br />';
}