一致性哈希

基础知识

热点(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个节点？、

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

实现

参考

思考题

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