背景分析

在分布式组件下，我们都会碰到这种场景，需要将一条信息路由到多个节点（分布式的核心特点：水平扩展）中的其中一个，而且根据场景不同，又需要划分如下两种类型：

  1. 一种是无状态，如负载均衡：nginx的http请求负载均衡、dubbo的rpc请求，
  2. 一种是有状态，如数据分片：分布式数据库、分布式缓存、分布式消息队列。

    常见的负载均衡算法

  1. 随机/带权重随机：简单无状态，均衡性好，支持权重处理。
  2. 轮询/带权重轮询：需要记住上一轮轮询状态，均衡性好，支持权重处理。
  3. 最低活跃度：需要维护每个节点的请求处理能力，调整分配给其的请求数量，。
  4. 哈希取模：有状态，均衡性好，而且还可以根据业务需要对hash对象进行指定，比如在一些有状态的集群节点下，根据ip或userid进行散列可以保证同一个用户能请求到同一个节点，能获取到相应session数据（虽然很不推荐这么做，应该用分布式主键来存储session）。

  5. 一致性哈希：有状态，但对于hash算法下，n的变化会导致大部分请求散列结果完全不一样（虽然在无状态的情况没啥问题，但还是如上所述，如果存在这种情况），一致性哈希可以保证绝大部分的请求依然能散列到原节点上。根据一致性哈希的原理，原来应该散列到挂掉的节点上会顺时针找到离该节点最近的一个节点上去。但这种处理会导致下一个节点请求量增大（如果不稳定的话继续挂就会导致请求雪崩），所以基于此，可以对一致性哈希算法增加虚拟节点的优化。

    常见的数据分片算法

  6. 首先我们分析，数据分片和负载均衡场景的区别是什么，最大的区别就是数据分片是有状态的，而负载均衡是无状态的（不考虑服务器节点有状态的情况），所以天然要求同一个请求一定要路由到同一个节点上，所以上述的随机、轮询、最低活跃度等等算法，是肯定不能用于数据分片的。

  7. 范围分片
    1. ID范围方式：固定1~100000放节点1，100001~200000放节点2 …，优点是受节点变化的影响较小，比如节点2挂了就影响它自己上面的10w条数据，而不影响其他节点的数据继续读写。缺点是ID天然带有的递增和时间顺序上带来的热点请求倾斜问题（还有一种时间范围分片一样这个问题）。
    2. ID取模方式：id % n，优点是业务随机性比较好，解决了上述缺点，缺点也正好相反，n一旦变化，会影响绝大部分数据的读写。
  8. 哈希取模：和id取模一样，只不过是将主键值换成了哈希值。
  9. 一致性哈希：优缺点和上述负载均衡场景下的一致性哈希一样，但是区别在于，数据分片场景的核心就是数据，就是有状态的，所以非常适合用一致性哈希的。

    两种场景的选择总结

    综上，对于负载均衡算法的选择，尤其在当前devops运维环境下，节点的性能一般是没有差异的，此外我也不推荐节点有状态，所以我们一般只需要关注均衡性，所以最推荐的算法就是随机算法（是dubbo的默认算法）和轮询算法（也是nginx默认算法）。
    对于数据分片算法的选择，因为是有状态的，所以我们要关注更多业务和运维上的稳定性和成本，业务上也就是上面提到的不能因为业务热点导致请求或数据倾斜。运维上也就是节点的删除和新增带来的重新分resharding成本不要太高，另外还考虑节点宕机带来的业务影响面尽量小，以上三个考虑就对应排除了上述前三个方式，所以最推荐的算法就是一致性哈希（虚拟节点优化版）算法。 :::info 扩展：一致性哈希算法的java代码实现一致性哈希算法 :::