memcache虽然是分布式的应用服务,但分布的原则是由client端的api来决定的,api根据存储用的key以及已知的服务器列表,根据key的hash计算将指定的key存储到对应的服务器列表上。
通常使用的散列方法是根据 key的hash值%服务器数取余数的方法来决定当前这个key的内容发往哪一个memcache服务器。但这样的算法在服务实例本身发生变动的时候,服务列表的变动会造成几乎大部分数据都会需要迁移到另外的服务实例上。这样在大型服务在线时,瞬时对后端数据库/硬盘照成的压力很可能导致整个服务的crash。
在此可以采用一致性哈希(Consistent Hashing)来解决这个问题,处理服务器的选择不再仅仅依赖key的hash本身而是将服务实例(节点)的配置也进行hash运算。
一致性哈希(Consistent Hashing)算法简述如下:
1. 求出每个服务节点的hash,并将其配置到一个0~2^32的圆环(continuum)区间上。
2. 使用同样的方法求出你所需要存储的key的hash,也将其配置到这个圆环(continuum)上。
3. 从数据映射到的位置开始顺时针查找,将数据保存到找到的第一个服务节点上。如果超过2^32仍然找不到服务节点,就会保存到第一个服务节点上。
整个数据的图例:
当增加服务器节点时:
这样做可以最大程度的避免了key在服务节点列表上的重新分布,同时还增加了虚拟服务节点的方法,也就是一个服务节点在环上有多个映射点,这样就能抑制分布不均匀,最大限度地减小服务节点增减时的缓存重新分布。具体来说,只有在圆环上增加服务节点的位置为逆时针方向的第一个服务节点上的键会受到影响。
以下部分为一致性哈希算法的一种PHP实现。
from: http://paul.annesley.cc/
comment: http://blog.csdn.net/mayongzhan/
<?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 (!emptyempty($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 (emptyempty($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 (emptyempty($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 {
}
相关推荐
在分布式系统中,常常需要使用缓存,而且通常是集群,访问缓存和添加缓存都需要一个 hash 算法来寻找到合适的 Cache 节点。但,通常不是用取余hash,而是使用我们今天的主角—— 一致性 hash 算法。
一致性哈希,consistent hashing。 算法入门必备 清晰版本,非扫描。
本文将会从实际应用场景出发,介绍一致性哈希算法(Consistent Hashing)及 其在分布式系统中的应用。首先本文会描述一个在日常开发中经常会遇到的问题 场景,借此介绍一致性哈希算法以及这个算法如何解决此问题;接...
跳跃一致哈希计算 甚至服务器之间的数据分布也非常重要:另一个重要方面是能够... 关于一致性哈希,使用的算法是谷歌的论文“A Fast, Minimal Memory, Consistent Hash Algorithm”中提出的Jump Consistent Hashing。
如果没有找到,则取整个环的第个节点。测试结果测试代码是整理的,主体法没有变分布平均性测试:测试随机成的众多key是否会平均分布到各个结点上测试结果如下:最上是参
响的虚拟节点包括c31,c22,c11(顺时针查找到第个节点),这3个虚拟节点分别对应机器c3,c2,c1。即新加的台机器,同时影响到原有的3台机器。理想情况下
在《基于一致性hash算法(consistent hashing)的使用详解》一文中已经介绍了一致性hash的基本原理,本文将会对其具体实现细节进行描述,并用c++语言对一致性hash进行了简单的实现
本文实例讲述了PHP实现的一致性哈希算法。分享给大家供大家参考,具体如下: <?php /** * Flexihash - A simple consistent hashing implementation for PHP. * * The MIT License * * Copyright (c) 2008 ...
php-consistent-hasha good php consistent hash helper,一个用php写的一致性hash 助手,主要用于解决internet中的热点(hot spot)问题特性平衡性(Balance):平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去,...
一致性哈希修正了CARP使用的简单哈希算法带来的问题,使得DHT可以在P2P环境中真正得到应用。主要用于分布式缓存的实现比如弹性伸缩(动态扩容)redis存储节点的增加和减少的时候,可以把需要迁移和hash()值的变化量...
摘要视图订阅登录 | 注册算法艺术(8)1004760次第1338名90篇16篇4篇595条一致性hash算法 - consistent hashing - s
一致性哈希算法是分布式系统中常用的算法,为什么要用这个算法? 比如:一个分布式存储系统,要将数据存储到具体的节点(服务器)上, 在服务器数量不发生改变的情况下,如果采用普通的hash再对服务器总数量取模的...
Consistent Hashing based Key-Value Memory Storage基于的分布式内存键值存储——CHKV。目前的定位就是作为 Cache,DataBase 的功能先不考虑。系统设计NameNode : 维护 DataNode节点 列表,用心跳检测 DataNode...
针对MR过程的减少阶段,提出了一种虚拟分区一致性哈希(VPCH)算法,以实现工作分配的权衡。 根据结果,使用我们的方法可以减少带有或不带有MJR(mapreduce.job.reduce.slowstart.completedmaps)参数集的任务...
环一致散列跳转一致哈希集合一致哈希磁悬浮一致性哈希 (第3.4节)粗略设计注意事项从与Karger等人成一直线的圆圈开始N个节点可以复制R次以改善分片分布。 复制的节点称为虚拟节点。 分片复制节点的散列在cicle上成...
该存储库提供了常用分布式技术的演示,例如一致性哈希,分布式锁,分布式事务,领导者选举等。 技术 模块 地位 评论 一致性哈希 一致性哈希 完毕 分散式锁 分布式锁 正在做 分散式交易 分布式交易 完毕 共识算法 ...
RedisJumphash提供了非常快速的一致性哈希函数,以使用Redis构建分布式系统。 用法 JUMPHASH <key> 成功调用将返回给定密钥的存储桶。 它不需要任何存储。 如果您更改存储桶的数量,该算法将保证需要的重定位次数...
一致的散列 一致性哈希是用于存储数据多个实例的算法和数据结构。 在这个项目中,我们的工作标题在此期间 信号处理 散列 网络