背景

在业务开发中，为了减轻数据库访问压力以及提高访问速度，一般会使用缓存。有n台缓存服务器时，一种常用的负载均衡的方式是使用hash(key) mod n来选择缓存服务器，用取模路由会存在什么问题呢？

1. 可拓展性，不能做到平滑扩（缩）容，比如从4台扩容到5台时，最理想的方式是旧的4台机器每台分摊1/20流量到第五台机器，最终每台机器流量由1/4变成1/5，实际上按照目前的取模路由规则，hash(key)中只有mod 20=[0,3]的key(20%)访问到旧的缓存服务器,80%的缓存都失效了，缓存失效意味着流量会直接穿透到后端数据库，前端平均调用耗时加大，大流量对数据库冲击可能会使数据库宕机，数据库以及上层逻辑服务都可能一段时间内不可用
2. 容错性，假设还是4台缓存服务器，如果节点0宕机了，那我们需要将故障机器流量转移，那如何转移呢？按照3台机器来路由？那还是会出现问题1，把节点0的流量全部引到节点1？那节点1是否有冗余的处理能力来消耗节点0的请求呢？如果没有，那节点1也可能会由于请求加倍导致不可用

为了解决上述问题，引入了一致性hash算法

一致性hash实现

维基百科：一致哈希将每个对象映射到圆环边上的一个点，系统再将可用的节点机器映射到圆环的不同位置。查找某个对象对应的机器时，需要用一致哈希算法计算得到对象对应圆环边上位置，沿着圆环边上查找直到遇到某个节点机器，这台机器即为对象应该保存的位置。 当删除一台节点机器时，这台机器上保存的所有对象都要移动到下一台机器。添加一台机器到圆环边上某个点时，这个点的下一台机器需要将这个节点前对应的对象移动到新机器上。 更改对象在节点机器上的分布可以通过调整节点机器的位置来实现。

如上图，是一个简单的一致性hash环，o5,o1会请求到机器node0，o2会请求到node1，o3会请求到node2,o4会请求到node3

当扩容新增节点node4时，(hash1,hash4]的请求都会选择node4，只有这部分对象的流量会有变化

当机器故障或者缩容时，那就把机器从hash环上移除，如上，(hash4,hash2]之间的流量就会请求到node3

这似乎看起来已经解决取模路由带来的扩展性和容错性问题，但是仔细观察下上述扩容缩容图片，会发现流量其实是不均匀的，扩容缩容都并没有把流量平均分摊到集群上别的节点，并没有实现负载均衡，那么应该如何改进呢？

这时候我们引入虚拟节点这个概念，也就是把一个实体节点分成一组虚拟节点，分散在hash环上，通过虚拟节点找到实体节点，如下图4，8个虚拟节点其实都对应同一个物理节点

这时候，最初的机器集群有4个实体节点，每个实体节点有8个虚拟节点，每个虚拟节点负责1/32 hash环流量，扩容一个节点时，增加8个虚拟节点，交错分布在hash环上，每个虚拟节点负责1/40 hash环，旧机器的部分流量会被分摊到新的节点上，如图5 v100,v101之间插入一个新的虚拟节点vnew，vnew就会分担部分v101的流量，这样就可以做到新增一个实体节点分摊所有旧的节点的流量

如果虚拟节点太少，还是会存在流量不够均匀的情况，这时候我们只需要把虚拟节点数调大就好了

测试验证

仅介绍扩容测试，缩容，节点故障类似

• hash环初始化

• 路由

• 测试样例

• 测试结果

总结

通过一致性hash算法+虚拟节点就可以实现一个健壮的缓存系统，做到平滑扩容，负载均衡，在真实现网环境中，还会存在不同的机器节点处理能力不同，也就是按照一定的权重比例来请求，比如4个节点权重是1：2：3：3，只需要调整虚拟节点的数量就可以做到了