找回密码
 立即注册

QQ登录

只需一步,快速开始

查看: 1752|回复: 0
打印 上一主题 下一主题

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

[复制链接]

2536

主题

2536

帖子

7532

积分

论坛元老

Rank: 8Rank: 8

积分
7532
跳转到指定楼层
楼主
发表于 2018-2-14 05:41:30 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式

            本文实例讲述了PHP实现的一致性哈希算法。分享给大家供大家参考,具体如下:
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
{
}
希望本文所述对大家PHP程序设计有所帮助。
            
            
您可能感兴趣的文章:
  • PHP实现通过Luhn算法校验信用卡卡号是否有效
  • PHP中实现Bloom Filter算法
  • PHP四种基本排序算法示例
  • php实现猴子选大王问题算法实例
  • php编写的抽奖程序中奖概率算法
  • PHP排序算法类实例
  • php算法实例分享
  • PHP常用的排序和查找算法
  • php实现的农历算法实例
  • PHP抽奖算法程序代码分享
  • php经典算法集锦
  • PHP实现的蚂蚁爬杆路径算法代码
            
  • 分享到:  QQ好友和群QQ好友和群 QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友
    收藏收藏
    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    用户反馈
    客户端