/**
* flexihash - a simple consistent hashing implementation for php.
*
* the mit license
*
* copyright (c) 2008 paul annesley
*
* permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "software"), to deal
* in the software without restriction, including without limitation the rights
* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the software, and to permit persons to whom the software is
* furnished to do so, subject to the following conditions:
*
* the above copyright notice and this permission notice shall be included in
* all copies or substantial portions of the software.
*
* the software is provided "as is", without warranty of any kind, express or
* implied, including but not limited to the warranties of merchantability,
* fitness for a particular purpose and noninfringement. in no event shall the
* authors or copyright holders be liable for any claim, damages or other
* liability, whether in an action of contract, tort or otherwise, arising from,
* out of or in connection with the software or the use or other dealings in
* the software.
*
* @author paul annesley
* @link http://paul.annesley.cc/
* @copyright paul annesley, 2008
* @comment by myz (http://blog.csdn.net/mayongzhan)
*/
/**
* a simple consistent hashing implementation with pluggable hash algorithms.
*
* @author paul annesley
* @package flexihash
* @licence http://www.opensource.org/licenses/mit-license.php
*/
class flexihash
{
/**
* the number of positions to hash each target to.
*
* @var int
* @comment 虚拟节点数,解决节点分布不均的问题
*/
private $_replicas = 64;
/**
* the hash algorithm, encapsulated in a flexihash_hasher implementation.
* @var object flexihash_hasher
* @comment 使用的hash方法 : md5,crc32
*/
private $_hasher;
/**
* internal counter for current number of targets.
* @var int
* @comment 节点记数器
*/
private $_targetcount = 0;
/**
* internal map of positions (hash outputs) to targets
* @var array { position => 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 _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
{
}
以上就介绍了一致性hash - php，包括了Exception方面的内容，希望对PHP教程有兴趣的朋友有所帮助。
