一致性哈希算法

image image image image

对于redis、memcached这些分布式缓存系统，需要将数据均匀的分布到缓存服务器集群的不同机器上，就需要使用对缓存的数据的key做hash值计算， 然后在将hash值除以服务器节点的数量取模计算出数据需要落到那台服务器节点上。这种算法很简单，也可以实现数据的均匀分布， 但是，增加或者减少数据节点的时候会导致所有缓存数据失效。

例如，有三台Redis，对于每次的访问都可以通过计算hash来求得hash值。如公式 h=hash(key)%3，我们把Redis编号设置成0,1,2来保存对应hash计算出来的值，h的值等于Redis对应的编号。

例如10条数据，3个节点，如果按照取模的方式，那就是h=hash(key)%4

node a: 0,3,6,9

node b: 1,4,7

node c: 2,5,8

当增加一个节点的时候，数据分布就变更为

node a:0,4,8

node b:1,5,9

node c: 2,6

node d: 3,7

因而，数据3,4,5,6,7,8,9在增加节点的时候，都需要做搬迁，成本太高。

image image image

1、首先，我们把全量的缓存空间当做一个环形存储结构。环形空间总共分成2^32个缓存区，在Redis中则是把缓存key分配到16384个slot中。

2、每个缓存key都可以通过hash算法转化为一个32位的二进制数，也就是对应着环形空间的某一个缓存区。我们把所有的缓存key映射到环形空间的不同位置。

3、每一个Redis集群缓存节点（Shard）也遵循同样的hash算法，一般采用ip做hash，映射到环形空间中。

4、如何让key和节点对应起来呢？很简单，每一个key的顺时针方向最近节点，就是key所归属的存储节点。如图所示。

image image image

1.增加节点

当缓存集群的节点有所增加的时候，整个环形空间的映射仍然会保持一致性哈希的顺时针规则，所以有一小部分key的归属会受到影响。

image

有哪些key会受到影响呢？图中加入了新节点node4，处于node1和node2之间，按照顺时针规则，从node1到node4之间的缓存不再归属于node2，而是归属于新节点node4。因此受影响的key只有key2。

image

最终把key2的缓存数据从node2迁移到node4，就形成了新的符合一致性哈希规则的缓存结构。

2.删除节点

当缓存集群的节点需要删除的时候（比如节点挂掉），整个环形空间的映射同样会保持一致性哈希的顺时针规则，同样有一小部分key的归属会受到影响。

image

有哪些key会受到影响呢？图中删除了原节点node3，按照顺时针规则，原本node3所拥有的缓存数据就需要“托付”给node3的顺时针后继节点node1。因此受影响的key只有key4。

image

最终把key4的缓存数据从node3迁移到node1，就形成了新的符合一致性哈希规则的缓存结构。

image

例如，我们的的系统有两台Redis，分布的环位置如下图所示：

image

这会产生一种情况，Redis4的hash范围比Redis3的hash范围大，导致数据大部分都存储在Redis4中，数据存储不平衡。

为了解决这种数据存储不平衡的问题，一致性哈希算法引入了虚拟节点机制，即对每个节点计算多个哈希值，每个计算结果位置都放置在对应节点中，这些节点称为虚拟节点。

具体做法可以在服务器IP或主机名的后面增加编号来实现，例如上面的情况，可以为每个服务节点增加三个虚拟节点，于是可以分为 RedisService1#1、 RedisService1#2、 RedisService1#3、 RedisService2#1、 RedisService2#2、 RedisService2#3，具体位置如下图所示：

image

对于数据定位的hash算法仍然不变，只是增加了虚拟节点到实际节点的映射。例如，数据C保存到虚拟节点Redis1#2，实际上数据保存到Redis1中。这样，就能解决服务节点少时数据不平均的问题。在实际应用中，通常将虚拟节点数设置为32甚至更大，因此即使很少的服务节点也能做到相对均匀的数据分布。

image image

你学会了吗？给我点个赞吧