总结一致性哈希(Consistent Hashing)

在大型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个虚拟节点才能达到真正的负载均衡。

 

 

 

评论

18 楼 aixiangct 2011-10-13  

您好
   如果是C、A之间加入节点B，那原来落在CB之间的数据不再找A，而是找B了，这部分数据在A确实是失效。
   在数据水平迁移的过程中，如果发生已迁移到B的数据再迁移后发生改变，A上修改了那部分数据，即产生脏数据的问题，应该如何解决呀？望不吝赐教

17 楼 抛出异常的爱 2010-04-25  

xiaoyu 写道

我一直都有一个疑问：就是一旦某台cache server崩溃了（数据量大，或者访问量大）。 数据迁移到下一个节点，导致下一个节点挂掉，如此下去，最后所有崩溃。

这个就不如固定的点的好。

这个也是理论上的。
cache客户端使用非同步方式上传数据
cache客户端使用超时失败策略检索数据
cache中的object是软引用或是虚引用。
所以在访问大时会出现大量GC，
使客户端命中失败，节点不会挂掉。
作过700次秒的多线程访问

16 楼 xiaoyu 2010-04-20  

我一直都有一个疑问：就是一旦某台cache server崩溃了（数据量大，或者访问量大）。 数据迁移到下一个节点，导致下一个节点挂掉，如此下去，最后所有崩溃。

这个就不如固定的点的好。

15 楼 thinkingzhu 2010-04-20  

虚拟节点跟hash算法可以把哈希失效减到最小,相对与普通hash方法数据迁移时的问题,还是可以接收的....
当然 也是相对来说,如果系统缓存数据量比较稳定,简单的hash取模方法也是十分合适的.

14 楼 mshijie 2010-04-01  

seraphim871211 写道

J-catTeam 写道

seraphim871211 写道

J-catTeam 写道

1.一致性hash仅仅是为了不去做数据迁移,但是随之机器的增加会越来越不可用。而且本身的消耗也会增大

这个的依据是什么？

你好
一致性hash，假设本来应该落在B点的数据，在A，B之间加一台机器，平均有一半的数据会无效。并且A到加的机器点上的数据在B上已经没有用，怎么去清理。随着机器的越来越多，不命中的概率也会越来越多。
虽然说最常用的hash取模不可避免的需要做数据迁移，但是可以选择时间点，比如半夜两点。这个时候访问肯定会很少。
不对的请指教

如果是C、A之间加入节点B，那原来落在CB之间的数据不再找A，而是找B了，这部分数据在A确实是失效。但你说的这个是纯理论。实际中加入B节点之后，CB间的数据（原来命中A上）会逐渐保存到B上（而不是不命中的时候什么都不做），同时A上的数据随着新到数据增加，原来那部分失效数据通过LRU算法将逐渐淘汰掉。所以我觉随着机器增加，不命中的概率不会大幅波动。

事实上，一致性hash就是用来解决存储节点增加导致的命中降低问题的。
实际例子：日本mixi也是逐渐增加到200台以上的memcached服务器集群，用的就是这种方法，并没有你说的问题。

我觉得上述情况不一定会出现。如果节点A的数据因为过期失效后，被淘汰。新数据也会继续插入到A上，数据的key是hash得到的。不会因为是新数据就会插入到后续的节点上。从统计上来说，数据的分布还是平均的。为了进一步避免数据分布不均匀可以使用虚拟节点，不一定要一台物理机器对应一个key。

13 楼 J-catTeam 2010-03-28  

cx6445 写道

J-catTeam 写道

seraphim871211 写道

J-catTeam 写道

seraphim871211 写道

J-catTeam 写道

1.一致性hash仅仅是为了不去做数据迁移,但是随之机器的增加会越来越不可用。而且本身的消耗也会增大

这个的依据是什么？

你好
一致性hash，假设本来应该落在B点的数据，在A，B之间加一台机器，平均有一半的数据会无效。并且A到加的机器点上的数据在B上已经没有用，怎么去清理。随着机器的越来越多，不命中的概率也会越来越多。
虽然说最常用的hash取模不可避免的需要做数据迁移，但是可以选择时间点，比如半夜两点。这个时候访问肯定会很少。
不对的请指教

如果是C、A之间加入节点B，那原来落在CB之间的数据不再找A，而是找B了，这部分数据在A确实是失效。但你说的这个是纯理论。实际中加入B节点之后，CB间的数据（原来命中A上）会逐渐保存到B上（而不是不命中的时候什么都不做），同时A上的数据随着新到数据增加，原来那部分失效数据通过LRU算法将逐渐淘汰掉。所以我觉随着机器增加，不命中的概率不会大幅波动。

事实上，一致性hash就是用来解决存储节点增加导致的命中降低问题的。
实际例子：日本mixi也是逐渐增加到200台以上的memcached服务器集群，用的就是这种方法，并没有你说的问题。

谢谢 ·我只是单纯从理论上做了解释，并没有考虑到很多实际情况。

不觉得有矛盾吗？如果一个问题理论上就不能解决，但实际上是解决了，那肯定是我们对理论理解有偏差。

通常的状态是理论上可以解决，但是由于各种实际情况才会解决不了。

不觉得有多大矛盾哈,我说的理论上的缺陷，那位朋友说的对理论上缺陷的在实际中扩展和解决

12 楼 cx6445 2010-03-28  

J-catTeam 写道

seraphim871211 写道

J-catTeam 写道

seraphim871211 写道

J-catTeam 写道

1.一致性hash仅仅是为了不去做数据迁移,但是随之机器的增加会越来越不可用。而且本身的消耗也会增大

这个的依据是什么？

你好
一致性hash，假设本来应该落在B点的数据，在A，B之间加一台机器，平均有一半的数据会无效。并且A到加的机器点上的数据在B上已经没有用，怎么去清理。随着机器的越来越多，不命中的概率也会越来越多。
虽然说最常用的hash取模不可避免的需要做数据迁移，但是可以选择时间点，比如半夜两点。这个时候访问肯定会很少。
不对的请指教

如果是C、A之间加入节点B，那原来落在CB之间的数据不再找A，而是找B了，这部分数据在A确实是失效。但你说的这个是纯理论。实际中加入B节点之后，CB间的数据（原来命中A上）会逐渐保存到B上（而不是不命中的时候什么都不做），同时A上的数据随着新到数据增加，原来那部分失效数据通过LRU算法将逐渐淘汰掉。所以我觉随着机器增加，不命中的概率不会大幅波动。

事实上，一致性hash就是用来解决存储节点增加导致的命中降低问题的。
实际例子：日本mixi也是逐渐增加到200台以上的memcached服务器集群，用的就是这种方法，并没有你说的问题。

谢谢 ·我只是单纯从理论上做了解释，并没有考虑到很多实际情况。

不觉得有矛盾吗？如果一个问题理论上就不能解决，但实际上是解决了，那肯定是我们对理论理解有偏差。

通常的状态是理论上可以解决，但是由于各种实际情况才会解决不了。

11 楼 J-catTeam 2010-03-24  

lishuaibt 写道

楼上的小伙子不错  很谦虚啊 赞一个 javaeye啥时候整体氛围能这样啊。。。

我相信会好的。哈哈

10 楼 lishuaibt 2010-03-24  

楼上的小伙子不错  很谦虚啊 赞一个 javaeye啥时候整体氛围能这样啊。。。

9 楼 J-catTeam 2010-03-24  

seraphim871211 写道

J-catTeam 写道

seraphim871211 写道

J-catTeam 写道

1.一致性hash仅仅是为了不去做数据迁移,但是随之机器的增加会越来越不可用。而且本身的消耗也会增大

这个的依据是什么？

你好
一致性hash，假设本来应该落在B点的数据，在A，B之间加一台机器，平均有一半的数据会无效。并且A到加的机器点上的数据在B上已经没有用，怎么去清理。随着机器的越来越多，不命中的概率也会越来越多。
虽然说最常用的hash取模不可避免的需要做数据迁移，但是可以选择时间点，比如半夜两点。这个时候访问肯定会很少。
不对的请指教

如果是C、A之间加入节点B，那原来落在CB之间的数据不再找A，而是找B了，这部分数据在A确实是失效。但你说的这个是纯理论。实际中加入B节点之后，CB间的数据（原来命中A上）会逐渐保存到B上（而不是不命中的时候什么都不做），同时A上的数据随着新到数据增加，原来那部分失效数据通过LRU算法将逐渐淘汰掉。所以我觉随着机器增加，不命中的概率不会大幅波动。

事实上，一致性hash就是用来解决存储节点增加导致的命中降低问题的。
实际例子：日本mixi也是逐渐增加到200台以上的memcached服务器集群，用的就是这种方法，并没有你说的问题。

谢谢 ·我只是单纯从理论上做了解释，并没有考虑到很多实际情况。

8 楼 langyu 2010-03-24  

最直接的解决方法是，对于每一个key，在最优情况下，都能找到同一台机器，在这台机器存在的情况下。那可以通过这台机器一个惟一的值同key关联，关联性可再做分析

7 楼 seraphim871211 2010-03-24  

J-catTeam 写道

seraphim871211 写道

J-catTeam 写道

1.一致性hash仅仅是为了不去做数据迁移,但是随之机器的增加会越来越不可用。而且本身的消耗也会增大

这个的依据是什么？

你好
一致性hash，假设本来应该落在B点的数据，在A，B之间加一台机器，平均有一半的数据会无效。并且A到加的机器点上的数据在B上已经没有用，怎么去清理。随着机器的越来越多，不命中的概率也会越来越多。
虽然说最常用的hash取模不可避免的需要做数据迁移，但是可以选择时间点，比如半夜两点。这个时候访问肯定会很少。
不对的请指教

如果是C、A之间加入节点B，那原来落在CB之间的数据不再找A，而是找B了，这部分数据在A确实是失效。但你说的这个是纯理论。实际中加入B节点之后，CB间的数据（原来命中A上）会逐渐保存到B上（而不是不命中的时候什么都不做），同时A上的数据随着新到数据增加，原来那部分失效数据通过LRU算法将逐渐淘汰掉。所以我觉随着机器增加，不命中的概率不会大幅波动。

事实上，一致性hash就是用来解决存储节点增加导致的命中降低问题的。
实际例子：日本mixi也是逐渐增加到200台以上的memcached服务器集群，用的就是这种方法，并没有你说的问题。

6 楼 J-catTeam 2010-03-23  

seraphim871211 写道

J-catTeam 写道

1.一致性hash仅仅是为了不去做数据迁移,但是随之机器的增加会越来越不可用。而且本身的消耗也会增大

这个的依据是什么？

你好
一致性hash，假设本来应该落在B点的数据，在A，B之间加一台机器，平均有一半的数据会无效。并且A到加的机器点上的数据在B上已经没有用，怎么去清理。随着机器的越来越多，不命中的概率也会越来越多。
虽然说最常用的hash取模不可避免的需要做数据迁移，但是可以选择时间点，比如半夜两点。这个时候访问肯定会很少。
不对的请指教

5 楼 seraphim871211 2010-03-23  

J-catTeam 写道

1.一致性hash仅仅是为了不去做数据迁移,但是随之机器的增加会越来越不可用。而且本身的消耗也会增大

这个的依据是什么？

4 楼 J-catTeam 2010-03-22  

1.一致性hash仅仅是为了不去做数据迁移,但是随之机器的增加会越来越不可用。而且本身的消耗也会增大
2.LZ最后一段是你写上去的

3 楼 xlongbuilder 2010-03-22  

case0079 写道

传统的方式下，可以用嵌套HASH来解决。

我觉得如果自己要做分布式的话，必须要解决均匀分布的问题，

要是没拼错的话
hosting hash 貌似不错

2 楼 case0079 2010-03-22  

传统的方式下，可以用嵌套HASH来解决。

我觉得如果自己要做分布式的话，必须要解决均匀分布的问题，

1 楼 langyu 2010-03-22  

Memcached客户端就采用这种算法解决分布式问题