JAVA实现一致性Hash算法

介绍

一致性Hash算法是实现负载均衡的一种策略，后续会写如何实现负载均衡

一致哈希是一种特殊的哈希算法。

在使用一致哈希算法后，哈希表槽位数（大小）的改变平均只需要对 K/n个关键字重新映射，其中K是关键字的数量， n是槽位数量。

然而在传统的哈希表中，添加或删除一个槽位的几乎需要对所有关键字进行重新映射。

强哈希

考虑到单服务器不能承载，因此使用了分布式架构，最初的算法为 hash() mod n, hash()通常取用户ID，n为节点数。

此方法容易实现且能够满足运营要求。缺点是当单点发生故障时，系统无法自动恢复。同样不也不能进行动态增加节点。

优缺点

强哈希可以将数据均匀的打散到节点上。但是如果新增/删除节点呢？显然会发生大量的节点移动才能继续使用该算法，因此缺点是该算法与节点数目强耦合。

当node数发生变化的时候，hash item所对应的node发生剧烈变化，而发生变化的成本就是我们需要在node数发生变化的时候迁移数据。因而诞生了弱哈希

弱哈希

为了解决单点故障，使用 hash() mod (n/m)

这样任意一个用户都有 m 个服务器备选，可由 client 随机选取。

由于不同服务器之间的用户需要彼此交互，所以所有的服务器需要确切的知道用户所在的位置。

因此用户位置被保存到 memcached 中。当一台发生故障，client 可以自动切换到对应 backup，由于切换前另外 1 台没有用户的 session，因此需要 client 自行重新登录。

• 好处

他比强哈希的好处是：解决了单点问题。

• 缺点

但存在以下问题：负载不均衡，尤其是单台发生故障后剩下一台会压力过大；不能动态增删节点；节点发生故障时需要 client 重新登录

因而出现了一致性hash,一致性 hash 算法适用于动态变化的 Cache 环境。

一致性Hash算法

一致性哈希算法有多种具体的实现，包括 Chord 算法，KAD 算法等实现，以上的算法的实现都比较复杂。

这里介绍一种网上广为流传的一致性哈希算法的基本实现原理，感兴趣的同学可以根据上面的链接或者去网上查询更详细的资料。

一致性哈希算法的基本实现原理是将机器节点和key值都按照一样的hash算法映射到一个0~2^32的圆环上。

当有一个写入缓存的请求到来时，计算 Key 值 k 对应的哈希值 Hash(k)，如果该值正好对应之前某个机器节点的 Hash 值，则直接写入该机器节点， 如果没有对应的机器节点，则顺时针查找下一个节点，进行写入，如果超过 2^32 还没找到对应节点，则从0开始查找(因为是环状结构)。

如图 1 所示:

图 1 中 Key K 的哈希值在 A 与 B 之间，于是 K 就由节点B来处理。

另外具体机器映射时，还可以根据处理能力不同，将一个实体节点映射到多个虚拟节点。

经过一致性哈希算法散列之后，当有新的机器加入时，将只影响一台机器的存储情况，

例如新加入的节点H的散列在 B 与 C 之间，则原先由 C 处理的一些数据可能将移至 H 处理， 而其他所有节点的处理情况都将保持不变，因此表现出很好的单调性。

而如果删除一台机器，例如删除 C 节点，此时原来由 C 处理的数据将移至 D 节点，而其它节点的处理情况仍然不变。

而由于在机器节点散列和缓冲内容散列时都采用了同一种散列算法，因此也很好得降低了分散性和负载。

而通过引入虚拟节点的方式，也大大提高了平衡性。

缺点

一致性Hash算法的缺点在于节点的插入可能并不是均匀的，节点在hash后在环上并不一定分布均匀，导致了每个节点实际占据换上的区间大小不一定相近，因此节点分布不够均匀

改进

基于虚拟节点的一致性哈希

一台物理服务器，虚拟成若干个虚拟节点，随机分布在环上，压力近似均衡分摊。如有三台物理服务器，每台物理服务器虚拟出150个虚拟节点，随机分配在Hash环上的150个位置上。最后可使三台物理服务器近似均摊压力。当增加一台服务器时，先虚拟150个节点，然后散落在哈希环上。

上图中的例子是有四台物理主机，每台物理主机虚拟成三个节点来保证节点近似均匀分布。

通过测试，每台物理服务的虚拟节点在120到200之间，均衡性更好。

缺点

该方法缺点在于存储虚拟节点信息需要额外空间。

重映射改进

在OpenStack的Swift组件中，使用了一种比较特殊的方法来解决分布不均的问题，改进了这些数据分布的算法，将环上的空间均匀的映射到一个线性空间，这样，就保证分布的均匀性。

这篇好文章是转载于：学新通技术网