1、 情景分析
前一篇博文分析了HashMap源码,HashMap在许多场景中作为存储数据的不二选择。
但是否使用HashMap就能解决所有在空间和时间的均衡问题??
下面考虑使用HashMap的二个极端情景:
原来有 N 台Server,所有数据通过一种 hash 算法(以hash(key)%N为例)映射到 N 台Server 中。
情景一:其中的 M 台服务器失效,那么需要将服务器 M 移除;或者访问量锐减,撤除 M 台服务器
,此时服务器的数量为 (N-M)台,最后,映射公式变成了 hash(key)%(N-M);
情景二:由于访问量加大,需要添加 M 台Server ,这时候 Server 是 (N+M) 台,映射公式变成了 hash(key)%(N+M)。
这两种情景看似只是数学公式上的小差别,但是对于 Server 和 Internet 来说是一个巨大的灾难。
海量的数据重新重新计算hash然后定位到不同的 Server 中,整个过程对Internet的占用也很严重。
这种情况是非常糟糕的。
用专业的说法来总结上述问题:以上hash算法的问题在于容错性和扩展性不好。
所谓容错性是指当系统中某一个或几个服务器变得不可用时,整个系统是否可以正确高效运行;
而扩展性是指当加入新的服务器后,整个系统是否可以正确高效运行。
一个设计良好的分布式哈希方案应该具有良好的单调性,即服务节点的增减不会造成大量哈希重定位。一致性哈希算法就是这样一种哈希方案。
2、 一致性哈希算法算法简述
一致性哈希算法(Consistent Hashing)最早在论文《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》中被提出。简单来说,一致性哈希将整个哈希值空间组织成一个虚拟的圆环,如假设某哈希函数H的值空间为0 – 2^32-1(即哈希值是一个32位无符号整形),整个哈希空间环如下:
整个空间按顺时针方向组织。0和2^32-1在零点中方向重合。
下一步将各个服务器使用Hash进行一个哈希,具体可以选择服务器的ip或主机名作为关键字进行哈希,这样每台机器就能确定其在哈希环上的位置。为了方便讨论,这里假设初始有三台 Server,使用ip地址哈希后在环空间的位置如下:
接下来使用如下算法定位数据访问到相应 Server:将数据key使用相同的函数 Hash 计算出哈希值h,通根据h确定此数据在环上的位置,从此位置沿环顺时针“行走”,第一台遇到的服务器就是其应该定位到的服务器。该解决方案有点像Hash的开放寻址中的线性探测法解决hash冲突的策略。
例如我们有A、B、C、D四个数据对象,经过哈希计算后,在环空间上的位置如下:
根据一致性哈希算法,数据A会被定为到Server 1上,D被定为到Server 3上,而B、C分别被定为到Server 2上。
3、 一致性哈希算法的容错性与可扩展性分析
3.1、下面分析一致性哈希算法的容错性:现假设Server 3挂了(专业一点就是宕机):
可以看到此时A、C、B不会受到影响,只有D节点被重定位到Server 2。一般的,在一致性哈希算法中,如果一台 Server 不可用,则受影响的数据仅仅是此 Server 到其环空间中前一台 Server(即顺着逆时针方向行走遇到的第一台服务器)之间数据,其它不会受到影响。
3.2、分析可拓展性:如果我们在系统中增加一台服务器Memcached Server 4
此时A、D、C不受影响,只有B需要重定位到新的Server 4。一般的,在一致性哈希算法中,如果增加一台 Server ,则受影响的数据仅仅是新 Server 到其环空间中前一台Server (即顺着逆时针方向行走遇到的第一台服务器)之间数据,其它不会受到影响。
综上所述,一致性哈希算法对于节点的增减都只需重定位环空间中的一小部分数据,具有较好的容错性和可扩展性。
4、 虚拟节点
一致性哈希算法在服务节点太少时,容易因为节点分部不均匀而造成数据倾斜问题。例如我们的系统中有两台 server,其环分布如下:
此时必然造成大量数据集中到Server 1上,而只有极少量会定位到Server 2上。为了解决这种数据倾斜问题,一致性哈希算法引入了虚拟节点机制,即对每一个服务节点计算多个哈希,每个计算结果位置都放置一个此服务节点,称为虚拟节点。
具体做法可以在服务器ip或主机名的后面增加编号来实现。例如上面的情况,我们决定为每台服务器计算三个虚拟节点,于是可以分别计算“Memcached Server 1#1”、“Memcached Server 1#2”、“Memcached Server 1#3”、“Memcached Server 2#1”、“Memcached Server 2#2”、“Memcached Server 2#3”的哈希值,于是形成六个虚拟节点:
同时数据定位算法不变,只是多了一步虚拟节点到实际节点的映射,例如定位到“Memcached Server 1#1”、“Memcached Server 1#2”、“Memcached Server 1#3”三个虚拟节点的数据均定位到Server 1上。这样就解决了服务节点少时数据倾斜的问题。在实际应用中,通常将虚拟节点数设置为32甚至更大,因此即使很少的服务节点也能做到相对均匀的数据分布,避免出现雪崩的情况。
5、 总结
在动态分布式缓存系统里哈希算法承担着系统架构上的关键点。 使用分布更合理的算法可以使得多个服务节点间的负载相对均衡,可以最大程度的避免资源的浪费以及服务器过载。 使用一致性哈希算法,可以最大程度的降低服务硬件环境变化带来的数据迁移代价和风险。 使用更合理的配置策略和算法可以使分布式缓存系统更加高效稳定。
简单的一致性哈希算法,可以使用MD5算法来作为hash算法, 对于各个hash算法的比较, 可以参考下面的讨论
http://www.iteye.com/topic/346682
参考资料地址:
http://blog.csdn.net/sparkliang/article/details/5279393
http://en.wikipedia.org/wiki/Consistent_hashing
http://www.jiacheo.org/blog/174
相关推荐
摘要视图订阅登录 | 注册算法艺术(8)1004760次第1338名90篇16篇4篇595条一致性hash算法 - consistent hashing - s
本篇文章对一致性hash算法(consistent hashing)的使用进行了详细的分析介绍。需要的朋友参考下
在分布式系统中,常常需要使用缓存,而且通常是集群,访问缓存和添加缓存都需要一个 hash 算法来寻找到合适的 Cache 节点。但,通常不是用取余hash,而是使用我们今天的主角—— 一致性 hash 算法。
#fly-archflylib创立的各种常见的架构技术内容列表cassandra-demo cassandra数据库的入门编程consistent-hash Java implementation of consistent-hashing基于java的一致性hash的实现一致性hash(consistent-hashing)...
如果没有找到,则取整个环的第个节点。测试结果测试代码是整理的,主体法没有变分布平均性测试:测试随机成的众多key是否会平均分布到各个结点上测试结果如下:最上是参
跳跃一致哈希计算 甚至服务器之间的数据分布也非常重要:另一个重要方面是能够... 关于一致性哈希,使用的算法是谷歌的论文“A Fast, Minimal Memory, Consistent Hash Algorithm”中提出的Jump Consistent Hashing。
响的虚拟节点包括c31,c22,c11(顺时针查找到第个节点),这3个虚拟节点分别对应机器c3,c2,c1。即新加的台机器,同时影响到原有的3台机器。理想情况下
在《基于一致性hash算法(consistent hashing)的使用详解》一文中已经介绍了一致性hash的基本原理,本文将会对其具体实现细节进行描述,并用c++语言对一致性hash进行了简单的实现
本文将会从实际应用场景出发,介绍一致性哈希算法(Consistent Hashing)及 其在分布式系统中的应用。首先本文会描述一个在日常开发中经常会遇到的问题 场景,借此介绍一致性哈希算法以及这个算法如何解决此问题;接...
php-consistent-hasha good php consistent hash helper,一个用php写的一致性hash 助手,主要用于解决internet中的热点(hot spot)问题特性平衡性(Balance):平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去,...
本文实例讲述了PHP实现的一致性Hash算法。分享给大家供大家参考,具体如下: 一致性哈希算法是分布式系统中常用的算法,为什么要用这个算法? 比如:一个分布式存储系统,要将数据存储到具体的节点(服务器)上, 在...
本文实例讲述了PHP实现的一致性哈希算法。分享给大家供大家参考,具体如下: <?php /** * Flexihash - A simple consistent hashing implementation for PHP. * * The MIT License * * Copyright (c) 2008 ...
一致性Hash算法 algorithm.cap algorithm.subset 给一个set打印出所有子集 jdk jdk 知识 jdk.autoboxing 自动装箱拆箱 jdk.longaccumulator 计数器 jdk.threadlocal DateFormatService: 如何线程安全的使用 ...
该存储库提供了常用分布式技术的演示,例如一致性哈希,分布式锁,分布式事务,领导者选举等。 技术 模块 地位 评论 一致性哈希 一致性哈希 完毕 分散式锁 分布式锁 正在做 分散式交易 分布式交易 完毕 共识算法 ...
环一致散列跳转一致哈希集合一致哈希磁悬浮一致性哈希 (第3.4节)粗略设计注意事项从与Karger等人成一直线的圆圈开始N个节点可以复制R次以改善分片分布。 复制的节点称为虚拟节点。 分片复制节点的散列在cicle上成...
Consistent Hashing based Key-Value Memory Storage基于的分布式内存键值存储——CHKV。目前的定位就是作为 Cache,DataBase 的功能先不考虑。系统设计NameNode : 维护 DataNode节点 列表,用心跳检测 DataNode...
RedisJumphash提供了非常快速的一致性哈希函数,以使用Redis构建分布式系统。 用法 JUMPHASH <key> 成功调用将返回给定密钥的存储桶。 它不需要任何存储。 如果您更改存储桶的数量,该算法将保证需要的重定位次数...