简单图解一致性哈希实现

我们以分布式缓存这个场景来演示一致性哈希问题

1. 常规哈希分桶时的问题:

如上图所示, 缓存一个文件, 如果只是按 hash(key) % 机器数量 这种方式进行分桶, 一旦需要扩充机器, 那么之前所有的缓存 key 将全部失效, 造成缓存击穿这种情况, 那么如何解决这种问题呢?

2. 一致性哈希

一致性哈希一样是取模, 不过是取 0~2^32-1 这个区间的, 我们给他图形化成一个圆, 数据以顺时针方向递增, 如下图:

将缓存服务器分布在这个圆上, 一旦流量进来, 也是以相同的计算出哈希值给分布在这个圆上, 如下图:

这样一来, 如果新增缓存服务的话, 产生影响的也只是某个区间中的数据, 如图:

3. 哈希分布不均匀

哈希也有个老生常谈的问题, 数据分布不均匀, 容易造成流量集中在某几台服务器上, 比如下面的情况:

这样一来, 服务器 A 将承载绝大部分流量的缓存工作, 服务器 B/C 的资源并没有充分利用上

为了解决这个问题, 服务分区的时候使用的是虚拟节点, 以求均匀分布在整个"环"上, 然后再维护一个虚拟节点和实体的中间层, 如图:

以上就是一致性哈希的基本原理了