=================================================================================================================
第一种实现方法
=================================================================================================================
serverList[$hash])) {
$this->serverList[$hash] = $server;
}
$this->isSorted = false;
return true;
}
/**
* 移除服务器
* @param string $server
* @return boolean
*/
function removeServer($server)
{
$hash = mHash2($server);
if (isset($this->serverList[$hash])) {
unset($this->serverList[$hash]);
}
$this->isSorted = false;
return true;
}
/**
* 根据$key逆时针查找相邻的服务器
* @param string $key
* @return string
*/
function lookup($key)
{
$hash = mHash2($key);
// 对服务器列表逆排序
if (!$this->isSorted) {
krsort($this->serverList, SORT_NUMERIC);
$this->isSorted = true;
$this->serverKeys = array_keys($this->serverList);
}
// 查找相邻的数据
foreach ($this->serverList as $pos => $server) {
if ($hash >= $pos) return $server;
}
// 找不到，返回最后一个
return $this->serverList[$this->serverKeys[count($this->serverList) – 1]];
}
}
$st = gettimeofday(1);
$hserver = new FlexiHash();
$hserver->addServer(‘192.168.1.1’);
$hserver->addServer(‘192.168.1.2’);
$hserver->addServer(‘192.168.1.3’);
$hserver->addServer(‘192.168.1.4’);
$hserver->addServer(‘192.168.1.5’);
$hserver->addServer(‘192.168.1.6’);
echo “
";
for($i=0; $i < 10000; $i++) { $t = $hserver->lookup('key'.$i);
$arr[] = $t;
}
print_r($arr);
echo gettimeofday(1) - $st;=================================================================================================================
第二种实现方法
=================================================================================================================
target, ... }
* @comment 位置对应节点,用于lookup中根据位置确定要访问的节点
*/
private $_positionToTarget = array();/**
* Internal map of targets to lists of positions that target is hashed to.
* @var array { target => [ position, position, ... ], ... }
* @comment 节点对应位置,用于删除节点
*/
private $_targetToPositions = array();/**
* Whether the internal map of positions to targets is already sorted.
* @var boolean
* @comment 是否已排序
*/
private $_positionToTargetSorted = false;/**
* Constructor
* @param object $hasher Flexihash_Hasher
* @param int $replicas Amount of positions to hash each target to.
* @comment 构造函数,确定要使用的hash方法和需拟节点数,虚拟节点数越多,分布越均匀,但程序的分布式运算越慢
*/
public function __construct(Flexihash_Hasher $hasher = null, $replicas = null) {
$this->_hasher = $hasher ? $hasher : new Flexihash_Crc32Hasher();
if (!empty($replicas)) {
$this->_replicas = $replicas;
}
}/**
* Add a target.
* @param string $target
* @chainable
* @comment 添加节点,根据虚拟节点数,将节点分布到多个虚拟位置上
*/
public function addTarget($target) {
if (isset($this->_targetToPositions[$target])) {
throw new Flexihash_Exception("Target '$target' already exists.");
}$this->_targetToPositions[$target] = array();
// hash the target into multiple positions
for ($i = 0; $i < $this->_replicas; $i++) {
$position = $this->_hasher->hash($target . $i);
$this->_positionToTarget[$position] = $target; // lookup
$this->_targetToPositions[$target] []= $position; // target removal
}$this->_positionToTargetSorted = false;
$this->_targetCount++;return $this;
}/**
* Add a list of targets.
* @param array $targets
* @chainable
*/
public function addTargets($targets) {
foreach ($targets as $target) {
$this->addTarget($target);
}return $this;
}/**
* Remove a target.
* @param string $target
* @chainable
*/
public function removeTarget($target) {
if (!isset($this->_targetToPositions[$target])) {
throw new Flexihash_Exception("Target '$target' does not exist.");
}foreach ($this->_targetToPositions[$target] as $position) {
unset($this->_positionToTarget[$position]);
}unset($this->_targetToPositions[$target]);
$this->_targetCount--;
return $this;
}/**
* A list of all potential targets
* @return array
*/
public function getAllTargets() {
return array_keys($this->_targetToPositions);
}/**
* Looks up the target for the given resource.
* @param string $resource
* @return string
*/
public function lookup($resource) {
$targets = $this->lookupList($resource, 1);
if (empty($targets)) {
throw new Flexihash_Exception('No targets exist');
}
return $targets[0];
}/**
* Get a list of targets for the resource, in order of precedence.
* Up to $requestedCount targets are returned, less if there are fewer in total.
*
* @param string $resource
* @param int $requestedCount The length of the list to return
* @return array List of targets
* @comment 查找当前的资源对应的节点,
* 节点为空则返回空,节点只有一个则返回该节点,
* 对当前资源进行hash,对所有的位置进行排序,在有序的位置列上寻找当前资源的位置
* 当全部没有找到的时候,将资源的位置确定为有序位置的第一个(形成一个环)
* 返回所找到的节点
*/
public function lookupList($resource, $requestedCount) {
if (!$requestedCount) {
throw new Flexihash_Exception('Invalid count requested');
}// handle no targets
if (empty($this->_positionToTarget)) {
return array();
}// optimize single target
if ($this->_targetCount == 1) {
return array_unique(array_values($this->_positionToTarget));
}// hash resource to a position
$resourcePosition = $this->_hasher->hash($resource);$results = array();
$collect = false;$this->_sortPositionTargets();
// search values above the resourcePosition
foreach ($this->_positionToTarget as $key => $value) {
// start collecting targets after passing resource position
if (!$collect && $key > $resourcePosition) {
$collect = true;
}// only collect the first instance of any target
if ($collect && !in_array($value, $results)) {
$results []= $value;
}// return when enough results, or list exhausted
if (count($results) == $requestedCount || count($results) == $this->_targetCount) {
return $results;
}
}// loop to start - search values below the resourcePosition
foreach ($this->_positionToTarget as $key => $value) {
if (!in_array($value, $results)) {
$results []= $value;
}// return when enough results, or list exhausted
if (count($results) == $requestedCount || count($results) == $this->_targetCount) {
return $results;
}
}// return results after iterating through both "parts"
return $results;
}public function __toString() {
return sprintf(
'%s{targets:[%s]}',
get_class($this),
implode(',', $this->getAllTargets())
);
}// ----------------------------------------
// private methods/**
* Sorts the internal mapping (positions to targets) by position
*/
private function _sortPositionTargets() {
// sort by key (position) if not already
if (!$this->_positionToTargetSorted) {
ksort($this->_positionToTarget, SORT_REGULAR);
$this->_positionToTargetSorted = true;
}
}}
/**
* Hashes given values into a sortable fixed size address space.
*
* @author Paul Annesley
* @package Flexihash
* @licence http://www.opensource.org/licenses/mit-license.php
*/
interface Flexihash_Hasher {/**
* Hashes the given string into a 32bit address space.
*
* Note that the output may be more than 32bits of raw data, for example
* hexidecimal characters representing a 32bit value.
*
* The data must have 0xFFFFFFFF possible values, and be sortable by
* PHP sort functions using SORT_REGULAR.
*
* @param string
* @return mixed A sortable format with 0xFFFFFFFF possible values
*/
public function hash($string);}
/**
* Uses CRC32 to hash a value into a signed 32bit int address space.
* Under 32bit PHP this (safely) overflows into negatives ints.
*
* @author Paul Annesley
* @package Flexihash
* @licence http://www.opensource.org/licenses/mit-license.php
*/
class Flexihash_Crc32Hasher
implements Flexihash_Hasher {/* (non-phpdoc)
* @see Flexihash_Hasher::hash()
*/
public function hash($string) {
return crc32($string);
}}
/**
* Uses CRC32 to hash a value into a 32bit binary string data address space.
*
* @author Paul Annesley
* @package Flexihash
* @licence http://www.opensource.org/licenses/mit-license.php
*/
class Flexihash_Md5Hasher
implements Flexihash_Hasher {/* (non-phpdoc)
* @see Flexihash_Hasher::hash()
*/
public function hash($string) {
return substr(md5($string), 0, 8); // 8 hexits = 32bit// 4 bytes of binary md5 data could also be used, but
// performance seems to be the same.
}}
/**
* An exception thrown by Flexihash.
*
* @author Paul Annesley
* @package Flexihash
* @licence http://www.opensource.org/licenses/mit-license.php
*/
class Flexihash_Exception extends Exception {
}$st = gettimeofday(1);
$hserver = new FlexiHash(null,1);
$addTargets = array(
'192.168.1.1',
'192.168.1.2',
'192.168.1.3',
'192.168.1.4',
'192.168.1.5',
'192.168.1.6',
);
$hserver->addTargets($addTargets);echo "
";
for($i=0; $i < 10000; $i++) { $t = $hserver->lookup('key'.$i);
$arr[] = $t;
}print_r($arr);
echo gettimeofday(1) - $st;
Chinese 
English