php memcached 一致性hash

<?php
/**
 * 一致性hahs實現類
 * 
 */
class FlexiHash{
/**
 * var int
 * 虛擬節點
 */
private $_replicas = 200;
/**
 * 使用hash方法
 */
private $_hasher = null;
/**
 * 真實節點計數器
 * 
 */
private $_targetCount = 0;
/**
 * 位置對應節點，用戶lookup中根據位置確定要訪問的節點
 */
private $_positionToTarget = array();
/**
 * 節點對應位置，用于刪除節點
 */
private $_targetToPositions = array();
/**
 * 是否已排序
 */
private $_positionToTargetSorted = false;
/**
 * @ $hasher hash方法
 * @ $replicas 虛擬節點的個數
 * 
 * 確定要使用的hash方法和虛擬的節點數，虛擬節點越多，分布越均勻，但程序的分布式運算越慢
 */
public function __construct(FlexiHash_Hasher $hasher=null, $replicas = null){
// hash方法
$this->_hasher = $hasher?$hasher: new FlexiHash_Crc32Hasher();
// 虛擬節點的個數
if (!empty($replicas)){
$this->_replicas = $replicas;
}
}
/**
 * 增加節點，根據虛擬節點數，把節點分布到更多的虛擬位置上
 */
public function addTarget($target){
if (isset($this->_targetToPositions[$target])) {
throw new FlexiHash_Exception("Target $target already exists.");
}
$this->_targetToPositions[$target] = array();
for ($i = 0; $i < $this->_replicas; $i++) {
// 根據規定的方法hash
$position = $this->_hasher->hash($target.$i);
// 虛擬節點對應的真實的節點
$this->_positionToTarget[$position] = $target;
// 真實節點包含的虛擬節點
$this->_targetToPositions[$target][] = $position;
}
$this->_positionToTargetSorted = false;
// 真實節點個數
$this->_targetCount++;
return $this;
}
/**
 * 添加多個節點
 * 
 */
public function addTargets($targets){
foreach ($targets as $target){
$this->addTarget($target);
}
return $this;
}
/**
 * 移除某個節點
 * 
 */
public function removeTarget($target){
if (!isset($this->_targetToPositions[$target])){
throw new FlexiHash_Exception("target $target does not exist\n");
}
foreach($this->_targetToPositions[$target] as $position){
unset($this->_positionToTarget[$position]);
}
unset($this->_targetToPositions[$target]);
$this->_targetCount--;
return $this;
}
/**
 * 獲取所有節點
 * 
 */
public function getAllTargets(){
return array_keys($this->_targetToPositions);
}
/**
 * 根據key查找hash到的真實節點
 * 
 */
public function lookup($resource){
$targets = $this->lookupList($resource, 1);
if (empty($targets)){
throw new FlexiHash_Exception("no targets exist");
}
return $targets[0];
}
/**
 * 查找資源存在的節點
 * 
 * 描述:根據要求的數量，返回與$resource哈希后數值相等或比其大并且是最小的數值對應的節點，若不存在或數量不夠，則從虛擬節點排序后的前一個或多個
 */
public function lookupList($resource, $requestedCount){
if (!$requestedCount) {
throw new FlexiHash_Exception('Invalid count requested');
}
if (empty($this->_positionToTarget)) {
return array();
}
// 直接節點只有一個的時候
if ($this->_targetCount == 1 ){
return array_unique(array_values($this->_positionToTarget));
}
// 獲取當前key進行hash后的值
$resourcePosition = $this->_hasher->hash($resource);
$results = array();
$collect = false;
$this->_sortPositionTargets();
// 查找與$resourcePosition 相等或比其大并且是最小的數
foreach($this->_positionToTarget as $key => $value){
if (!$collect && $key > $resourcePosition){
$collect = true;
}
if ($collect && !in_array($value, $results)){
$results[] = $value;
}
// 找到$requestedCount 或個數與真實節點數量相同
if (count($results) == $requestedCount || count($results) == $this->_targetCount){
return $results;
}
}
// 如數量不夠或者未查到，則從第一個開始，將$results中不存在前$requestedCount-count($results)，設置為需要的節點
foreach ($this->_positionToTarget as $key => $value){
if (!in_array($value, $results)){
$results[] = $value;
}
if (count($results) == $requestedCount || count($results) == $this->_targetCount){
return $results;
}
}
return $results;
}
/**
 * 根據虛擬節點進行排序
 */
private function _sortPositionTargets(){
if (!$this->_positionToTargetSorted){
ksort($this->_positionToTarget, SORT_REGULAR);
$this->_positionToTargetSorted = true;
}
}
}// end class
/**
 * hash方式
 */
interface FlexiHash_Hasher{
public function hash($string);
}
class FlexiHash_Crc32Hasher implements FlexiHash_Hasher{
public function hash($string){
return sprintf("%u",crc32($string));
}
}
class FlexiHash_Md5Hasher implements FlexiHash_Hasher{
public function hash($string){
return substr(md5($string), 0, 8);
}
}
class FlexiHash_Exception extends Exception{
}
$runData['BEGIN_TIME'] = microtime(true);
$key="lihuibin";
for($i=0;$i<10;$i++) {
$targetsArray = array(
"127.0.0.1:11211",
"127.0.0.1:11212",
"127.0.0.1:11213",
"127.0.0.1:11214",
#"127.0.0.1:11218"
);
$flexiHashObj = new FlexiHash(new FlexiHash_Crc32Hasher(),1);
$result = $flexiHashObj->addTargets($targetsArray);
$key=$key."$i";
$targets = $flexiHashObj->lookup($key);
var_dump($targets);
#$key = md5(mt_rand());
#$targets = $flexiHashObj->lookup($key);
#var_dump($targets);
}
echo "一致性hash:";
var_dump(number_format(microtime(true) - $runData['BEGIN_TIME'],6));
exit;
$runData['BEGIN_TIME'] = microtime(true); 
$m= new Memcache;
$m->connect('127.0.0.1', 11211); 
for($i=0;$i<10000;$i++) {
$key = md5(mt_rand());
$b = $m->set($key, time(), 0, 10);
}
echo "單臺機器:";
var_dump(number_format(microtime(true) - $runData['BEGIN_TIME'],6));
?>