vlambda博客
学习文章列表

分布式系统中，多个节点间实现请求的负载均衡， 如果部分实例由于一些特殊的原因宕机或者需要扩容，这个时候就涉及到部分请求重新分发的问题。

hash 

hash 算法大家应该很熟悉了，就是将不定长的数据经过计算后输出定长的结果。

如果在分布式系统中使用 传统hash 方法来分发请求，

  server =  hash(key) % n 

这会带来两个问题：

1. 一旦服务器节点数 n 发生伸缩，就需要重新计算 hash ，会大大的消耗服务器性能从而降低整个系统的吞吐量。

2. 可能出现分布不均匀问题，部分节点负载过高，部分节点负载过低。

为了解决传统 hash 方法带来的问题，1997年麻省理工提出了一致性 hash 算法（ 也称hash 环）。

hash 环

通过以下三点解决了服务器节点数动态伸缩导致的大量计算问题。

1. 请求的 key 进行 hash 计算后放入环中；

2. 服务器 ip 进行 hash 计算后放入环中；

3. 将 hash(key) 和 hash(ip)  相同的请求分发到对应的服务器，如果找不到相同的值，则按照顺时针方向找到最近的节点来处理请求。

position = hash(key) % (2^32 ).

这个时候，服务器节点数发生伸缩，只需要重新做部分计算即可。

在0号机器和1号机器间添加新的节点4号机器时，只需要重新计算 k1 和 k2 的hash 即可。

如果发生宕机，假设是2号机器宕机，这个时候执行需要将之前分发在2号机器的k3重新分发到 0号机器即可。

最后，为了解决请求分布不均匀问题，可以为每台服务器增加多个虚拟节点随机hash 到不同的位置 , 环中的服务器节点数越来越多，请求的分发也就越来越均匀。

应用

分布式环境中，比如分布式缓存：redis、memcached 他们的客户端包已经封装了一致性hash算法，比如 jedis。

 值得一提的是， redis 3.0 后当redis 作为数据存储使用时，采用了hash 槽的方式（见之前的文章《》）。

如果觉得文章有用，请 关注、分享、在看， 原创不易，且看且珍惜~