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

本文实例讲述了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
{
}

希望本文所述对大家PHP程序设计有所帮助。

本页内容版权归属为原作者,如有侵犯您的权益,请通知我们删除。
下面这个正则验证用户名的方法原则是这样的用户名必须是由字母带数字带定划线组成了,下面一起来看看例子吧. 1.检查用户名 是否符合规定“两位以上的字母,数字,或者下划线”,代码如下: /** * 检查用户名是否符合规定 * * @param STRING $username 要检查的用户名 * @return TRUE or FALSE */ function is_username($username) { $strlen = strlen($username); if (!preg_match("/^[

php验证码生成代码 - 2015-11-13 17:11:08

验证码通常是用来安全保证我们网站注册或登录不被注入的,但为了更安全我们通常会生成一些混合验证码了,下面一起来看看例子. 在我们开发登录模块或者是论坛的灌水模块的时候,为了防止恶意提交,需要用到验证码,验证码就是用来区分人和机器的一种手段,当然这种手段不是万无一失,但总归会起到一些作用. 验证码的实现需要GD库的支持,没有开启GD库的童鞋需开启GD库,其实验证码的制作和使用非常的简单,仅仅只是需要4个步骤就可以搞定:创建验证码底图,显示验证码内容,增加干扰元素,输出验证码,下面我们来进行步骤拆分: 第一步:

php验证手机号码 - 2015-11-13 15:11:46

大家都应该有这个常识,中国的手机号码都是以数字“1”开头,然后利用“0~9”10个数字组成的11位数字组合,那么我们的验证规则肯定要根据这个思路来写。 根据上面的简单思路,我们便可以写下以下的验证代码,代码如下: ?php //本代码仅仅是提供一些思路 //距离实际应用还有一些距离 $mobile = '15858588585'; //下面的1便是手机的第一位数字必须为数字1 //[0-9]指后面的数字均为0~9的数字 //{9}这中间的9指的是手机号码除了第一位数外,其他要重复10次,刚好就是11位数了

php+mysql实现无限级分类 - 2015-11-13 15:11:46

项目思路分析: 一个PHP项目要用到分类,但不确定分几级,所以就想做成无限级分类。 一开始想是按以前一样,数据库建4个值,如下: id: 自增 | pid: 父类ID | xid: 排序ID | classname: 分类名称 后来想到这种在读取数据时和修改时比较不方便,而且在产品读取时尤其不便,于时改成了以下的方案: 在Mysql的表中新增了一个字段,现 数据库 如下: 表名 w_faqclass: id: 自增 | pid: 父类ID | xid: 排序ID | classname: 分类名称 | r

分享10段PHP常用代码 - 2015-11-13 14:11:31

本文汇集PHP开发中经常用到的十段代码,包括Email、64位编码和解码、解压缩、64位编码、解析JSON等,希望对您有所帮助。 1、使用PHP Mail函数发送Email $to = "viralpatel.net@gmail.com"; $subject = "VIRALPATEL.net"; $body = "Body of your message here you can use HTML too. e.g.

Thinkphp无限级分类代码 - 2015-11-13 14:11:12

本篇就一点一点教大家写一个无限级分类出来,其实掌握一个知识,最主要的是要掌握无限级分类的逻辑,那么写起来就很容易的多了。 首先看数据库表:xp_cate 控制器:CateAction.class.php ?phpclass CateAction extends Action{function index(){$cate=M('Cate');$list=$cate-field("id,name,pid,path,concat(path,'-',id) as bpath")-order('bpath')-se

2款PHP无限级分类实例代码 - 2015-11-13 04:11:02

本文章总结了两款PHP无限级分类实现程序代码,有需要学习的朋友可参考一下。 主要思路: 首先看第三行和第四行,父类ID(PARENTID)的值是1,表示属于id=1这个类的子类,而,一,二两行因为是一级分类,没有上级分类,所以父类ID(PARENTID)的值是0,表示初级分类,依次类推便实现了无限级分类。最终的效果是: ├一级分类A ├─┴二级分类A ├─┴二级分类B ├一级分类B 然后就是程序,这里以PHP作为描述语言,可以很方便的改成其他语言,因为原理相似,就是一个递归而已。 ?php$dbhost
PHP用mb_string函数库处理与windows相关中文字符 昨天想批处理以前下载的一堆文件,把文件里的关键内容用正则匹配出来,集中处理。在操作文件时遇到一个问题,就是windows操作系统中的编码问题。 我们都知道windows中(当然是中文版),文件名和文件内容等编码都是gbk,而我们在开发过程中,IDE里的编码则是UTF-8,(这里不讨论为什么等等问题, 只考虑怎么把编码转变成一样的)所以导致我写的UTF-8编码的正则模式字符串中的中文在gbk编码的文件中并不能正确匹配。 一开始,我并没有什么办
set_error_handler() 函数设置用户自定义的错误处理函数。该函数用于创建运行时期间的用户自己的错误处理方法。该函数会返回旧的错误处理程序,若失败,则返回 null。 下面来看一些例子。 set_error_handler() PHP从4.1.0开始提供了自定义错误处理句柄的功能函数set_error_handler(),但很少数脚本编写者知道。set_error_handler这个函数可以很好地防止错误路径泄露,当然还有其它更多的作用。 1.可以用来屏蔽错误。 出现错误一来会把一些信息暴漏

php实现Session存储到Redis - 2015-11-12 17:11:37

对于大访问量的站点使用默认的Session 并不合适,我们可以将其存入数据库、或者使用Redis KEY-VALUE数据存储方案 首先新建一个session表 CREATE TABLE `sessions` ( `sid` char(40) NOT NULL, `updatetime` int(20) NOT NULL, `data` varchar(200) NOT NULL, UNIQUE KEY `sid` (`sid`) USING HASH) ENGINE=MEMORY DEFAULT CHAR