一致性哈希

基础知识

  • 热点(Hot spot)问题:
  • 分布式哈希:
  • 一致性

简介

一致哈希 是一种特殊的哈希算法。
在使用一致哈希算法后,哈希表槽位数(大小)的改变平均只需要对$K/n$个关键字重新映射,
其中$K$是关键字的数量,$n$是槽位数量。
然而在传统的哈希表中,添加或删除一个槽位的几乎需要对所有关键字进行重新映射

历史

一致哈希是1997年由MIT的Karger提出的一种分布式哈希(DHT)实现算法,设计目标是为了解决因特网中的热点(Hot spot) 问题,初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题,使得分布式哈希(DHT)可以在P2P环境中真正得到应用。

一致性哈希算法(Consistent Hashing)是分布式系统中常用的算法。比如,一个分布式的存储系统,要将数据存储到具体的节点上,如果采用普通的hash方法,将数据映射到具体的节点上,如key%N,key是数据的key,N是机器节点数,如果有一个机器加入或退出这个集群,则所有的数据映射都无效了,如果是持久化存储则要做数据迁移,如果是分布式缓存,则其他缓存就失效了。
因此,引入了一致性哈希算法:

把数据用hash函数(如MD5),映射到一个很大的空间里,如图所示。数据的存储时,先得到一个hash值,对应到这个环中的每个位置,如k1对应到了图中所示的位置,然后沿顺时针找到一个机器节点B,将k1存储到B这个节点中。

如果B节点宕机了,则B上的数据就会落到C节点上,如下图所示:

这样,只会影响C节点,对其他的节点A,D的数据不会造成影响。然而,这又会造成一个“雪崩”的情况,即C节点由于承担了B节点的数据,所以C节点的负载会变高,C节点很容易也宕机,这样依次下去,这样造成整个集群都挂了。

为此,引入了“虚拟节点”的概念:即把想象在这个环上有很多“虚拟节点”,数据的存储是沿着环的顺时针方向找一个虚拟节点,每个虚拟节点都会关联到一个真实节点,如下图所使用:

图中的A1、A2、B1、B2、C1、C2、D1、D2都是虚拟节点,机器A负载存储A1、A2的数据,机器B负载存储B1、B2的数据,机器C负载存储C1、C2的数据。由于这些虚拟节点数量很多,均匀分布,因此不会造成“雪崩”现象。

加虚拟节点解决数据均衡的问题

1.使用虚拟节点后,但是当我增加物理节点后,环中的虚拟节点是否要增加,如果把他应用在mysql上,数据迁移是否会很困难?

2.在使用虚拟节点时,比如5个物理节点,每个物理节点虚拟出1024个虚节点,按道理hash环有5120个节点,但是使用kemata哈希虚拟环时,有些节点key的哈希结果相同,导致hash环中少于5120个节点?、

有一个问题,如果使用虚拟节点,某台机器每次宕机再恢复后都需要迁移数据。这样是否反而更麻烦了。

实现

参考

思考题

  • 一致性哈希只是分布式场景下的应用吗?单机能用吗?单机怎样实现哈希的一致性?