转载自:http://hi.baidu.com/fdwm_lx/blog/item/fe46344e11517705b3de054c.html
在大型web应用中,缓存可算是当今的一个标准开发配置了。在大 规模的缓存应用中,应运而生了分布式缓存系统。分布式缓存系统的基本原理,大家也有所耳闻。key-value如何均匀的分散到集群中?说到此,最常规的 方式莫过于hash取模的方式。比如集群中可用机器适量为N,那么key值为K的的数据请求很简单的应该路由到hash(K) mod N对应的机器。的确,这种结构是简单的,也是实用的。但是在一些高速发展的web系统中,这样的解决方案仍有些缺陷。随着系统访问压力的增长,缓存系统不 得不通过增加机器节点的方式提高集群的相应速度和数据承载量。增加机器意味着按照hash取模的方式,在增加机器节点的这一时刻,大量的缓存命不中,缓存 数据需要重新建立,甚至是进行整体的缓存数据迁移,瞬间会给DB带来极高的系统负载,设置导致DB服务器宕机。那么就没有办法解决hash取模的方式带来的诟病吗?看下文。
一致性哈希(Consistent Hashing):
选择具体的机器节点不在只依赖需要缓存数据的key的hash本身了,而是机器节点本身也进行了hash运算。
(1) hash机器节点
首先求出 机器节点的hash值(怎么算机器节点的hash?ip可以作为hash的参数吧。。当然还有其他的方法了),然后将其分布到0~2^32的一个圆环上 (顺时针分布)。如下图所示:
集群中有 机器:A , B, C, D, E五台机器,通过一定的hash算法我们将其分布到如上图所示的环上。
(2)访问方式
如果有一 个写入缓存的请求,其中Key值为K,计算器hash值Hash(K), Hash(K) 对应于图 – 1环中的某一个点,如果该点对应没有映射到具体的某一个机器节点,那么顺时针查找,直到第一次找到有映射机器的节点,该节点就是确定的目标节点,如果超过 了2^32仍然找不到节点,则命中第一个机器节点。比如 Hash(K) 的值介于A~B之间,那么命中的机器节点应该是B节点(如上图 )。
(3)增加节点的处理
如上图 – 1,在原有集群的基础上欲增加一台机器F,增加过程如下:
计算机器 节点的Hash值,将机器映射到环中的一个节点,如下图:
增加机器 节点F之后,访问策略不改变,依然按照(2)中的方式访问,此时缓存命不中的情况依然不可避免,不能命中的数据是hash(K)在增加节点以前落在C~F 之间的数据。尽管依然存在节点增加带来的命中问题,但是比较传统的 hash取模的方式,一致性hash已经将不命中的数据降到了最低。
Consistent Hashing最大限度地抑制了hash键的重新分布。另外要取得比较好的负载均衡的效果,往往在服务器数量比较少的时候需要增加虚拟节点来保证服务器能 均匀的分布在圆环上。因为使用一般的hash方法,服务器的映射地点的分布非常不均匀。使用虚拟节点的思想,为每个物理节点(服务器)在圆上分配 100~200个点。这样就能抑制分布不均匀,最大限度地减小服务器增减时的缓存重新分布。用户数据映射在虚拟节点上,就表示用户数据真正存储位置是在该 虚拟节点代表的实际物理服务器上。
下面有一个图描述了需要为每台物理服务器增加的虚拟节点。
x轴表示的是需要为每台物理服务器扩展的虚拟节点倍数(scale),y轴是实际物理服务器数,可以看出,当物理服务器的数量很小时,需要更大的虚 拟节点,反之则需要更少的节点,从图上可以看出,在物理服务器有10台时,差不多需要为每台服务器增加100~200个虚拟节点才能达到真正的负载均衡。
-----------------
一致性hash,假设本来应该落在B点的数据,在A,B之间加一台机器,平均有一半的数据会无效。并且A到加的机器点上的数据在B上已经没有用,怎么去清 理。随着机器的越来越多,不命中的概率也会越来越多。
虽然说最常用的hash取模不可避免的需要做数据迁移,但是可以选择时间点,比如半夜两点。这个时候访问肯定会很少。
--
如果是C、A之间加入节点B,那原来落在CB之间的数据不再找A,而是找B了,这部分数据在A确实是失效。但你说的这个是纯理论。实际中加入B节点之 后,CB间的数据(原来命中A上)会逐渐保存到B上(而不是不命中的时候什么都不做),同时A上的数据随着新到数据增加,原来那部分失效数据通过LRU算 法将逐渐淘汰掉。所以我觉随着机器增加,不命中的概率不会大幅波动。
事实上,一致性hash就是用来解决存储节点增加导致的命中降低问题的。
实际例子:日本mixi也是逐渐增加到200台以上的memcached服务器集群,用的就是这种方法,并没有你说的问题。
分享到:
相关推荐
在分布式系统中,常常需要使用缓存,而且通常是集群,访问缓存和添加缓存都需要一个 hash 算法来寻找到合适的 Cache 节点。但,通常不是用取余hash,而是使用我们今天的主角—— 一致性 hash 算法。
一致性哈希,consistent hashing。 算法入门必备 清晰版本,非扫描。
一致性哈希 consistent-hash Implementing Consistent Hashing in Kotlin Java Kotlin实现的一致性哈希工具 简单示例 val a = HostPortPhysicalNode("A", "192.169.1.1", 8080) val b = HostPortPhysicalNode("B", ...
跳跃一致哈希计算 甚至服务器之间的数据分布也非常重要:另一个重要方面是能够... 关于一致性哈希,使用的算法是谷歌的论文“A Fast, Minimal Memory, Consistent Hash Algorithm”中提出的Jump Consistent Hashing。
第一次提出一致性哈希环的论文,说的是比较好的,稍微有点英语基础的,应该都可以看懂。在分布式,缓存流行的今天,确实是不错的充电利器。
libconhash is a consistent hashing libraray, which can be compiled both on Windows and Linux platform. High performance, easy to use, and easy to scale according to node's processing capacity.
本文将会从实际应用场景出发,介绍一致性哈希算法(Consistent Hashing)及 其在分布式系统中的应用。首先本文会描述一个在日常开发中经常会遇到的问题 场景,借此介绍一致性哈希算法以及这个算法如何解决此问题;接...
响的虚拟节点包括c31,c22,c11(顺时针查找到第个节点),这3个虚拟节点分别对应机器c3,c2,c1。即新加的台机器,同时影响到原有的3台机器。理想情况下
如果没有找到,则取整个环的第个节点。测试结果测试代码是整理的,主体法没有变分布平均性测试:测试随机成的众多key是否会平均分布到各个结点上测试结果如下:最上是参
一致的散列这是一致性哈希的简单JavaScript实现。 有关一致性哈希的更多信息,请参见。安装使用以下命令安装依赖项: $ npm install 用法var ConsistentHashing = require ( './consistent_hashing' ) ;var node...
一致性哈希和有界负载的一致性哈希的Golang实现。 一致的哈希示例 package main import ( "log" "github.com/lafikl/consistent" ) func main () { c := consistent . New () // adds the hosts to the ring ...
功能弹性伸缩,提供控制面板,管理员可以增加和删除Redis节点Redis运行状态监控,报警Redis故障或者网络故障的灾难应对原理consistent-hashing一致性hashzookeeper保持一致性和监听文章测试如果您愿意捐助一下项目,...
php-consistent-hasha good php consistent hash helper,一个用php写的一致性hash 助手,主要用于解决internet中的热点(hot spot)问题特性平衡性(Balance):平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去,...
一致性哈希修正了CARP使用的简单哈希算法带来的问题,使得DHT可以在P2P环境中真正得到应用。主要用于分布式缓存的实现比如弹性伸缩(动态扩容)redis存储节点的增加和减少的时候,可以把需要迁移和hash()值的变化量...
一致性哈希示例 一个简单的项目,展示了一致性哈希的工作原理
Consistent Hashing based Key-Value Memory Storage基于的分布式内存键值存储——CHKV。目前的定位就是作为 Cache,DataBase 的功能先不考虑。系统设计NameNode : 维护 DataNode节点 列表,用心跳检测 DataNode...
本文实例讲述了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
环一致散列跳转一致哈希集合一致哈希磁悬浮一致性哈希 (第3.4节)粗略设计注意事项从与Karger等人成一直线的圆圈开始N个节点可以复制R次以改善分片分布。 复制的节点称为虚拟节点。 分片复制节点的散列在cicle上成...
在《基于一致性hash算法(consistent hashing)的使用详解》一文中已经介绍了一致性hash的基本原理,本文将会对其具体实现细节进行描述,并用c++语言对一致性hash进行了简单的实现