- 浏览: 81776 次
- 性别:
- 来自: 北京
文章分类
最新评论
<?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 */ /** * 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 引用传递、引用返回和取消引用以及unset
2011-11-06 15:23 3101原文出处:http://hi.baidu.com/kashif ... -
php加速 PHP APC 浅析
2011-10-11 00:02 1171原文出自:http://www.perfgeeks.co ... -
CentOS源码安装Apache+PHP+MySQL
2011-05-20 23:18 25111.安装Apache CentOS源码安装Apache2 ... -
php命令行程序中让用户进行输入
2011-04-13 14:27 898<?php if(!defined("STD ... -
改自QeePHP的开发框架
2011-04-02 12:44 1134QeePHP是一个很不错的PHP开源框架。之前在小公司一直使用 ... -
session过期时间过长引发的性能问题
2011-02-24 11:42 1914同样的程序,连接同一个数据库,但测试服务器上比我本机要跑得慢, ... -
php正则表达式验证中文
2011-02-18 18:28 8671./^[\x{4e00}-\x{9fa5}]+$/u 2./ ... -
丢失的一小时
2010-12-18 20:25 994同样的时间段,在不同的时区下,转换成秒以后居然会不相等。 d ...
相关推荐
在分布式系统中,常常需要使用缓存,而且通常是集群,访问缓存和添加缓存都需要一个 hash 算法来寻找到合适的 Cache 节点。但,通常不是用取余hash,而是使用我们今天的主角—— 一致性 hash 算法。
一致性哈希,consistent hashing。 算法入门必备 清晰版本,非扫描。
本文将会从实际应用场景出发,介绍一致性哈希算法(Consistent Hashing)及 其在分布式系统中的应用。首先本文会描述一个在日常开发中经常会遇到的问题 场景,借此介绍一致性哈希算法以及这个算法如何解决此问题;接...
如果没有找到,则取整个环的第个节点。测试结果测试代码是整理的,主体法没有变分布平均性测试:测试随机成的众多key是否会平均分布到各个结点上测试结果如下:最上是参
响的虚拟节点包括c31,c22,c11(顺时针查找到第个节点),这3个虚拟节点分别对应机器c3,c2,c1。即新加的台机器,同时影响到原有的3台机器。理想情况下
跳跃一致哈希计算 甚至服务器之间的数据分布也非常重要:另一个重要方面是能够... 关于一致性哈希,使用的算法是谷歌的论文“A Fast, Minimal Memory, Consistent Hash Algorithm”中提出的Jump Consistent Hashing。
本文实例讲述了PHP实现的一致性哈希算法。分享给大家供大家参考,具体如下: <?php /** * Flexihash - A simple consistent hashing implementation for PHP. * * The MIT License * * Copyright (c) 2008 ...
摘要视图订阅登录 | 注册算法艺术(8)1004760次第1338名90篇16篇4篇595条一致性hash算法 - consistent hashing - s
php-consistent-hasha good php consistent hash helper,一个用php写的一致性hash 助手,主要用于解决internet中的热点(hot spot)问题特性平衡性(Balance):平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去,...
致性哈希算法在1997年由麻省理工学院提出(参见扩展阅读[1]),设计目标是为了解决因特网中的热点(Hot spot)问题,初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题,使得DHT可以在P2P环境中...
一致性哈希算法是分布式系统中常用的算法,为什么要用这个算法? 比如:一个分布式存储系统,要将数据存储到具体的节点(服务器)上, 在服务器数量不发生改变的情况下,如果采用普通的hash再对服务器总数量取模的...
在《基于一致性hash算法(consistent hashing)的使用详解》一文中已经介绍了一致性hash的基本原理,本文将会对其具体实现细节进行描述,并用c++语言对一致性hash进行了简单的实现
针对MR过程的减少阶段,提出了一种虚拟分区一致性哈希(VPCH)算法,以实现工作分配的权衡。 根据结果,使用我们的方法可以减少带有或不带有MJR(mapreduce.job.reduce.slowstart.completedmaps)参数集的任务...
Consistent Hashing based Key-Value Memory Storage基于的分布式内存键值存储——CHKV。目前的定位就是作为 Cache,DataBase 的功能先不考虑。系统设计NameNode : 维护 DataNode节点 列表,用心跳检测 DataNode...
环一致散列跳转一致哈希集合一致哈希磁悬浮一致性哈希 (第3.4节)粗略设计注意事项从与Karger等人成一直线的圆圈开始N个节点可以复制R次以改善分片分布。 复制的节点称为虚拟节点。 分片复制节点的散列在cicle上成...
RedisJumphash提供了非常快速的一致性哈希函数,以使用Redis构建分布式系统。 用法 JUMPHASH <key> 成功调用将返回给定密钥的存储桶。 它不需要任何存储。 如果您更改存储桶的数量,该算法将保证需要的重定位次数...
该存储库提供了常用分布式技术的演示,例如一致性哈希,分布式锁,分布式事务,领导者选举等。 技术 模块 地位 评论 一致性哈希 一致性哈希 完毕 分散式锁 分布式锁 正在做 分散式交易 分布式交易 完毕 共识算法 ...
一致的散列 一致性哈希是用于存储数据多个实例的算法和数据结构。 在这个项目中,我们的工作标题在此期间 信号处理 散列 网络