系统设计-一致性hash

本文参考了深入浅出一致性Hash原理

1、为什么要设计一致性hash

负载均衡在有状态情况下，怎么堆转发机器？比如用户uid=a的所有请求必须转发到某个服务器b上。

采用哈西表做一个映射，把用户ID和机器ID一一对应起来。但这个时候我们面临一个问题：普通的余数hash（hash(比如用户id)%服务器机器数）算法伸缩性很差，当新增或者下线服务器机器时候，服务器机器数发生改变，用户id与服务器的映射关系会大量失效。一致性hash则利用hash环对其进行了改进。

 

2、一致性Hash的原理

假设有4台服务器，地址为ip1,ip2,ip3,ip4。

• 一致性hash是首先计算四个ip地址对应的hash值hash(ip1),hash(ip2),hash(ip3),hash(ip3)，把这四个值连成一个环如下图：

• 当用户在客户端进行请求时候，首先根据hash(用户id)计算路由规则（hash值），然后在hash环上的位置顺时针找距离最近的ip作为路由ip.

• 某一个服务器挂了的时候，该服务器原来的用户请求会被其他服务器处理，而其它用户的请求对应的处理服务器不变。新增某一个服务器的时候，新增的服务器顺时针最近的服务器的一部分请求会被新增的服务器所替代。

 

3、一致性Hash的问题及解决方案

一致性hash可以做到每个服务器都进行处理请求，但是不能保证每个服务器处理的请求的数量大致相同，这样称为一致性hash的倾斜。如下图：

3.1 虚拟节点

当服务器节点比较少的时候会出现上节所说的一致性hash倾斜的问题，一个解决方法是多加机器，但是加机器是有成本的，那么就加虚拟节点，比如上面三个机器，每个机器引入1个虚拟节点后的一致性hash环的图如下，其中ip1-1是ip1的虚拟节点，ip2-1是ip2的虚拟节点，ip3-1是ip3的虚拟节点：

3.2 均衡的一致性hash

但是如果生成虚拟节点的算法不够好，情况虽然相比没有引入虚拟节点前均衡性有所改善，但是并不均衡。均匀一致性hash的目标是如果服务器有N台，客户端的hash值有M个，那么每个服务器应该处理大概M/N个用户的。也就是每台服务器负载尽量均衡。

                       （a）不均衡的一致性Hash                                                                   （b）均衡的一致性Hash