学步园

来自http://blog.csdn.net/mayongzhan/archive/2009/06/25/4298834.aspx

<?php<br /> /**<br /> * Flexihash - A simple consistent hashing implementation for PHP.<br /> *<br /> * The MIT License<br /> *<br /> * Copyright (c) 2008 Paul Annesley<br /> *<br /> * Permission is hereby granted, free of charge, to any person obtaining a copy<br /> * of this software and associated documentation files (the "Software"), to deal<br /> * in the Software without restriction, including without limitation the rights<br /> * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell<br /> * copies of the Software, and to permit persons to whom the Software is<br /> * furnished to do so, subject to the following conditions:<br /> *<br /> * The above copyright notice and this permission notice shall be included in<br /> * all copies or substantial portions of the Software.<br /> *<br /> * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR<br /> * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,<br /> * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE<br /> * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER<br /> * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,<br /> * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN<br /> * THE SOFTWARE.<br /> *<br /> * @author Paul Annesley<br /> * @link http://paul.annesley.cc/<br /> * @copyright Paul Annesley, 2008<br /> * @comment by MyZ (http://blog.csdn.net/mayongzhan)<br /> */<br /> /**<br /> * A simple consistent hashing implementation with pluggable hash algorithms.<br /> *<br /> * @author Paul Annesley<br /> * @package Flexihash<br /> * @licence http://www.opensource.org/licenses/mit-license.php<br /> */<br /> class Flexihash<br /> {<br /> /**<br /> * The number of positions to hash each target to.<br /> *<br /> * @var int<br /> * @comment 虚拟节点数,解决节点分布不均的问题<br /> */<br /> private $_replicas = 64;<br /> /**<br /> * The hash algorithm, encapsulated in a Flexihash_Hasher implementation.<br /> * @var object Flexihash_Hasher<br /> * @comment 使用的hash方法 : md5,crc32<br /> */<br /> private $_hasher;<br /> /**<br /> * Internal counter for current number of targets.<br /> * @var int<br /> * @comment 节点记数器<br /> */<br /> private $_targetCount = 0;<br /> /**<br /> * Internal map of positions (hash outputs) to targets<br /> * @var array { position => target, ... }<br /> * @comment 位置对应节点,用于lookup中根据位置确定要访问的节点<br /> */<br /> private $_positionToTarget = array();<br /> /**<br /> * Internal map of targets to lists of positions that target is hashed to.<br /> * @var array { target => [ position, position, ... ], ... }<br /> * @comment 节点对应位置,用于删除节点<br /> */<br /> private $_targetToPositions = array();<br /> /**<br /> * Whether the internal map of positions to targets is already sorted.<br /> * @var boolean<br /> * @comment 是否已排序<br /> */<br /> private $_positionToTargetSorted = false;<br /> /**<br /> * Constructor<br /> * @param object $hasher Flexihash_Hasher<br /> * @param int $replicas Amount of positions to hash each target to.<br /> * @comment 构造函数,确定要使用的hash方法和需拟节点数,虚拟节点数越多,分布越均匀,但程序的分布式运算越慢<br /> */<br /> public function __construct(Flexihash_Hasher $hasher = null, $replicas = null)<br /> {<br /> $this->_hasher = $hasher ? $hasher : new Flexihash_Crc32Hasher();<br /> if (!empty($replicas)) $this->_replicas = $replicas;<br /> }<br /> /**<br /> * Add a target.<br /> * @param string $target<br /> * @chainable<br /> * @comment 添加节点,根据虚拟节点数,将节点分布到多个虚拟位置上<br /> */<br /> public function addTarget($target)<br /> {<br /> if (isset($this->_targetToPositions[$target]))<br /> {<br /> throw new Flexihash_Exception("Target '$target' already exists.");<br /> }<br /> $this->_targetToPositions[$target] = array();<br /> // hash the target into multiple positions<br /> for ($i = 0; $i < $this->_replicas; $i++)<br /> {<br /> $position = $this->_hasher->hash($target . $i);<br /> $this->_positionToTarget[$position] = $target; // lookup<br /> $this->_targetToPositions[$target] []= $position; // target removal<br /> }<br /> $this->_positionToTargetSorted = false;<br /> $this->_targetCount++;<br /> return $this;<br /> }<br /> /**<br /> * Add a list of targets.<br /> * @param array $targets<br /> * @chainable<br /> */<br /> public function addTargets($targets)<br /> {<br /> foreach ($targets as $target)<br /> {<br /> $this->addTarget($target);<br /> }<br /> return $this;<br /> }<br /> /**<br /> * Remove a target.<br /> * @param string $target<br /> * @chainable<br /> */<br /> public function removeTarget($target)<br /> {<br /> if (!isset($this->_targetToPositions[$target]))<br /> {<br /> throw new Flexihash_Exception("Target '$target' does not exist.");<br /> }<br /> foreach ($this->_targetToPositions[$target] as $position)<br /> {<br /> unset($this->_positionToTarget[$position]);<br /> }<br /> unset($this->_targetToPositions[$target]);<br /> $this->_targetCount--;<br /> return $this;<br /> }<br /> /**<br /> * A list of all potential targets<br /> * @return array<br /> */<br /> public function getAllTargets()<br /> {<br /> return array_keys($this->_targetToPositions);<br /> }<br /> /**<br /> * Looks up the target for the given resource.<br /> * @param string $resource<br /> * @return string<br /> */<br /> public function lookup($resource)<br /> {<br /> $targets = $this->lookupList($resource, 1);<br /> if (empty($targets)) throw new Flexihash_Exception('No targets exist');<br /> return $targets[0];<br /> }<br /> /**<br /> * Get a list of targets for the resource, in order of precedence.<br /> * Up to $requestedCount targets are returned, less if there are fewer in total.<br /> *<br /> * @param string $resource<br /> * @param int $requestedCount The length of the list to return<br /> * @return array List of targets<br /> * @comment 查找当前的资源对应的节点,<br /> * 节点为空则返回空,节点只有一个则返回该节点,<br /> * 对当前资源进行hash,对所有的位置进行排序,在有序的位置列上寻找当前资源的位置<br /> * 当全部没有找到的时候,将资源的位置确定为有序位置的第一个(形成一个环)<br /> * 返回所找到的节点<br /> */<br /> public function lookupList($resource, $requestedCount)<br /> {<br /> if (!$requestedCount)<br /> throw new Flexihash_Exception('Invalid count requested');<br /> // handle no targets<br /> if (empty($this->_positionToTarget))<br /> return array();<br /> // optimize single target<br /> if ($this->_targetCount == 1)<br /> return array_unique(array_values($this->_positionToTarget));<br /> // hash resource to a position<br /> $resourcePosition = $this->_hasher->hash($resource);<br /> $results = array();<br /> $collect = false;<br /> $this->_sortPositionTargets();<br /> // search values above the resourcePosition<br /> foreach ($this->_positionToTarget as $key => $value)<br /> {<br /> // start collecting targets after passing resource position<br /> if (!$collect && $key > $resourcePosition)<br /> {<br /> $collect = true;<br /> }<br /> // only collect the first instance of any target<br /> if ($collect && !in_array($value, $results))<br /> {<br /> $results []= $value;<br /> }<br /> // return when enough results, or list exhausted<br /> if (count($results) == $requestedCount || count($results) == $this->_targetCount)<br /> {<br /> return $results;<br /> }<br /> }<br /> // loop to start - search values below the resourcePosition<br /> foreach ($this->_positionToTarget as $key => $value)<br /> {<br /> if (!in_array($value, $results))<br /> {<br /> $results []= $value;<br /> }<br /> // return when enough results, or list exhausted<br /> if (count($results) == $requestedCount || count($results) == $this->_targetCount)<br /> {<br /> return $results;<br /> }<br /> }<br /> // return results after iterating through both "parts"<br /> return $results;<br /> }<br /> public function __toString()<br /> {<br /> return sprintf(<br /> '%s{targets:[%s]}',<br /> get_class($this),<br /> implode(',', $this->getAllTargets())<br /> );<br /> }<br /> // ----------------------------------------<br /> // private methods<br /> /**<br /> * Sorts the internal mapping (positions to targets) by position<br /> */<br /> private function _sortPositionTargets()<br /> {<br /> // sort by key (position) if not already<br /> if (!$this->_positionToTargetSorted)<br /> {<br /> ksort($this->_positionToTarget, SORT_REGULAR);<br /> $this->_positionToTargetSorted = true;<br /> }<br /> }<br /> }</p> <p>/**<br /> * Hashes given values into a sortable fixed size address space.<br /> *<br /> * @author Paul Annesley<br /> * @package Flexihash<br /> * @licence http://www.opensource.org/licenses/mit-license.php<br /> */<br /> interface Flexihash_Hasher<br /> {<br /> /**<br /> * Hashes the given string into a 32bit address space.<br /> *<br /> * Note that the output may be more than 32bits of raw data, for example<br /> * hexidecimal characters representing a 32bit value.<br /> *<br /> * The data must have 0xFFFFFFFF possible values, and be sortable by<br /> * PHP sort functions using SORT_REGULAR.<br /> *<br /> * @param string<br /> * @return mixed A sortable format with 0xFFFFFFFF possible values<br /> */<br /> public function hash($string);<br /> }</p> <p>/**<br /> * Uses CRC32 to hash a value into a signed 32bit int address space.<br /> * Under 32bit PHP this (safely) overflows into negatives ints.<br /> *<br /> * @author Paul Annesley<br /> * @package Flexihash<br /> * @licence http://www.opensource.org/licenses/mit-license.php<br /> */<br /> class Flexihash_Crc32Hasher<br /> implements Flexihash_Hasher<br /> {<br /> /* (non-phpdoc)<br /> * @see Flexihash_Hasher::hash()<br /> */<br /> public function hash($string)<br /> {<br /> return crc32($string);<br /> }<br /> }</p> <p>/**<br /> * Uses CRC32 to hash a value into a 32bit binary string data address space.<br /> *<br /> * @author Paul Annesley<br /> * @package Flexihash<br /> * @licence http://www.opensource.org/licenses/mit-license.php<br /> */<br /> class Flexihash_Md5Hasher<br /> implements Flexihash_Hasher<br /> {<br /> /* (non-phpdoc)<br /> * @see Flexihash_Hasher::hash()<br /> */<br /> public function hash($string)<br /> {<br /> return substr(md5($string), 0, 8); // 8 hexits = 32bit<br /> // 4 bytes of binary md5 data could also be used, but<br /> // performance seems to be the same.<br /> }<br /> }</p> <p>/**<br /> * An exception thrown by Flexihash.<br /> *<br /> * @author Paul Annesley<br /> * @package Flexihash<br /> * @licence http://www.opensource.org/licenses/mit-license.php<br /> */<br /> class Flexihash_Exception extends Exception<br /> {<br /> }