负载均衡算法：一致性哈希

名词解释

哈希：即将输入数据利用同一个函数映射到一个固定范围内，因此最后一步一般是求模运算 一致性：在范围发生变动之后，同一个数据的哈希值不会发生改变

扩容

当数据量过于庞大，导致无法进行存储的时候，需要进行扩容，扩容包含垂直扩容和水平扩容 水平扩容新增服务器，让每个服务器分担的数据降低 垂直扩容则增强一个服务器的性能，从而能够容纳更多数据

为什么要一致性哈希

水平扩容就产生了一个问题，如何分配到达的数据，换句话说，如何让每一台服务器上的负载尽量保持平衡 好的哈希算法能尽量避免负载不均衡的问题，因为在好的哈希算法能够将不同的数据映射到不同的值，因此在分配数据的时候取用户数据的主键进行哈希，根据哈希值分配不同服务器即可 然而，一旦发生了水平扩容，那么意味着哈希范围变大，如原来有个用户IP的哈希值是u1%N，此时新增了M台机器，导致哈希值变为u1%(N+M)，这就导致服务器需要根据用户进行大规模的数据迁移。由于一个映射值的改变就要改动整个数据部署，这不科学

一致性哈希算法

设置一个非常大的范围，如INT_MAX，绝对超过服务器可能有的数量 那么怎么寻址呢？ 从这篇博客中 。=，一致性哈希将数据组织成一个环，每次映射得到一个哈希值之后如果命中了服务器的key如B这个用户，那么直接访问这台服务器，如果没能命中，那就顺着环往前找，这样一来如论增加多少台服务器，哈希范围都能保持一致。 从图中，我们可以得知，服务器在环中可以划分为[D0, D1] ... [D(n-1), D(0)]n个区间，为了方便阐述，假设现在没有任何优化的寻址方法，按每个区间内的哈希值会找到该区间的右端点服务器作为目标

那么一致性哈希意味着完全不需要重新移动数据吗？

并不是，当服务器数量更改的时候，环的范围虽然没变，但是相应区间内的 主要从下面 2 个方向去考虑的 当服务器宕机的时候，区间要进行合并，如第k台服务器宕机，那么[D(k-1), D(k)], [D(k), D(k+1)]将合并为[D(k-1), D(k+1)]，此时[D(k-1), D(k)]区间内的所有节点都需要移动数据到D(k+1)中 当新增节点的时候（或者宕机恢复） ，一个区间就要进行拆分，如在两个服务器之间插入了第k个服务器，那么在[D(k-1),D(k)]的数据就需要重新寻址 一致性哈希所解决的问题其实是整体数据迁移，即如果存在大量服务器，那么服务器的增减只会让对应区间的数据进行迁移，从而节省资源

一致性哈希负载不均衡问题

问题描述：如果服务器不多，而且在环上分布很密集，举个极端的例子，就是只有两台服务器，那么由于是向后寻址，那么会导致只要哈希值不落在两个服务器的区间内，数据就会全都落在第一个服务器中。 直观解决：最直观的解决方案就是均分区间，但是这样明显不可行，因为每加入或者删除一个节点，都会导致一次换位。 解决：一致性 Hash 算法引入了虚拟节点的机制，每台服务器都会进行多次哈希，得到多个哈希值，从而让一个服务器在环上能够对应多个节点，以这种方式增加每个节点管理的区间 每当哈希值命中某个服务器的虚拟节点，就会进行第二次map，将虚拟节点映射到本机地址。 从参考博客中得知，实际实现的时候，通常将虚拟节点数设置为32甚至更大，因此即使很少的服务节点也能做到相对均匀的数据分布，这是Dubbo负载均衡的实现

总结

一致性哈希解决的是大规模数据迁移问题 一致性哈希不能完全避免数据重新寻址问题，只是将问题复杂度大大降低 一致性哈希最好对服务器进行多次哈希得到不同哈希值，从而均衡负载

参考