PHP实现的一致性哈希算法完整实例

<?php
/**
 * 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 < $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
{
}