使用一致性哈希解决哈希分片负载均衡的扩展性问题

声明：本文的图全部源于：小林coding

上来咱先说，一致性哈希是应对分布式系统的算法

假设有一个负载均衡问题，也就是大批流量来请求，那怎么分配这些流量？

随机？还是挨个轮询？

这都可以，甚至不同机器的配置不同，可以根据配置分配权重，然后分发流量

但是流量可以如此，数据呢？有亿级数据，如何拆分，使得访问请求不会造成数据库崩掉？

通常来讲可以范围分片或者哈希分片，将数据拆分到不同的存储节点上去。假定选择ID，那有可能热点数据集中到同一张表里了，没起到分摊访问数据库流量的作用。哈希分片确实是一种可以均匀分散数据到不同节点上的算法。举个例子：

但哈希分片有一个致命问题，那就是扩展性不好，假设新增节点或者删除节点都要重新计算全部数据的哈希索引，也就是全量数据迁移：

解决方案也有，那就是一致性哈希，一致哈希算法是对 2^32 进行取模运算，是一个固定的值。可以想象有一个圈，存储节点做哈希，比如根据节点的 IP 地址进行哈希。然后数据也做哈希，然后顺时针找到的第一个存储节点就是这个数据被分到的存储节点：

这样不论是新增节点还是删除节点都可以只迁移部分数据了：

这样虽然解决了扩展性问题，但是难保会有存储节点映射不均匀的情况发生：

引入更多节点就可以把这个圆环更好的分割了，那么就可以将数据均匀的分散了，可是我们没有那么多机器啊，怎么增多存储节点？
答案就是引入虚拟节点，映射到圆环上的是虚拟节点，而每个真实节点可以被若干虚拟节点映射到：

当某个真实节点被移除时，该节点的多个虚拟节点均会移除。

还可以为硬件配置更好的节点增加权重，比如对权重更高的节点增加更多的虚拟机节点。