一致性Hash

业务场景

在分布式框架 SpringCloud-Ribbon 中有多种负载均衡策略：

1. 随机访问策略。系统随机访问，缺点：可能造成服务器负载压力不均衡，俗话讲就是撑的撑死，饿的饿死。
2. 轮询策略。请求均匀分配，如果服务器有性能差异，则无法实现性能好的服务器能够多承担一部分。
3. 权重轮询策略。权值需要静态配置，无法自动调节，不适合对长连接和命中率有要求的场景。
4. Hash取模策略。不稳定，如果列表中某台服务器宕机，则会导致路由算法产生变化，由此导致命中率的急剧下降。
5. ...

Ribbon默认使用轮询到服务列表中选取一个实例，但是现在我们需要的是一个根据请求中的某个key进行Hash之后来实现同一个key每次只会访问到同一个实例的功能，Ribbon并没有提供这种实现方式，下面就需要用到自定义一致性hash来实现这个功能

什么是一致性Hash？

一致性哈希算法在1997年由麻省理工学院的Karger等人在解决分布式Cache中提出的，设计目标是为了解决因特网中的热点(Hot spot)问题，初衷和CARP十分类似。一致性哈希修正了CARP使用的简单哈希算法带来的问题，使得DHT可以在P2P环境中真正得到应用。

特性

• 容错性
• 拓展性
• 平衡性（Balance）：哈希的结果尽可能分布到所有节点中
• 单调性（Monotonicity）：如果一些内容已经分派到了响应的节点中，此时又有新的节点加入，Hash结果应能够保证原有分派的内容可以被映射到新的节点中去，而不会被映射到旧的节点中去。比如求余Hash（object % N）无法满足单调性
• 平滑性（Smoothness）：服务节点数目平滑改变和负载的平滑改变一致

一致性 Hash 算法

一致性hash之前是hash取模，hash取模的方式增加或删除了一个节点时，所有的 Key 都需要重新计算，显然并不完善，而采用一致性哈希可以解决所有的 Key 都需要重新计算的问题。

一致 Hash 算法核心是将所有的哈希值构成一个环，范围在 0 ~ 2^32-1。 然后将各个节点Hash之后到这个环上，可以用节点的 IP、hostname 等唯一字段作为 Key 进行 hash(key)，散列之后如下：

之后将请求定位到对应的节点上，使用同样的 hash 函数 将 Key 也映射到这个环上。

这样按照顺时针方向就可以把 key1 定位到 Node1节点，key2 定位到 Node2节点，key3 定位到 Node3节点，这样既可实现一个ip每次都只访问同一节点

容错性

一致性 Hash有很好的容错性支持，现在假设Node1、Node4节点挂了

那么请求依然会根据顺时针方向，key3 保持不变，key1、key2、key4 被重新映射到了 Node2。这样就很好的保证了容错性，当一个节点挂掉时只会影响到少部分的数据。

扩展性

当我们新增一个节点时

在 Node1 和 Node3 之间新增了一个节点 Node4 ，这时受影响的数据只有 Key4，其余数据保持不变，完美保证其拓展性。

虚拟节点

目前为止该算法依然存在问题，当节点较少时会出现数据分布不均匀的情况：

当只有很少例如两个节点时会导致大部分数据都在 N1 节点，只有少量的数据在 N2 节点。

为了解决这个问题，一致哈希算法引入了虚拟节点。将每一个节点都进行多次 hash，生成多个节点放置在环上称为虚拟节点:

计算时可以在 IP 后加上编号来生成哈希值。这样只需要在原有的基础上多一步由虚拟节点映射到实际节点的步骤即可让少量节点也能满足均匀性。

实践

以上皆为理论概述，下面来实现在Spring Cloud 中根据用户请求中某个字段进行哈希后每次只访问同一个节点的功能

        
1
2
        // 新增 Ribbon 实现类


      

总结

一致性hash解决了增减服务器导致的大量震荡问题

REF

• 一致性哈希