一致性Hash分析

Hash算法应用场景

Hash算法在很多分布式集群产品中都有应用，比如分布式集群架构Redis、Hadoop、ElasticSearch，Mysql分库分表，Nginx负载均衡等

• 主要的应用场景归纳起来两个

1. 请求的负载均衡(比如nginx的ip_hash策略)

Nginx的IP_hash策略可以在客户端ip不变的情况下，将其发出的请求始终路由到同一个目标服务器上，实现会话粘滞，避免处理session共享问题 ,我们可以对ip地址或者sessionid进行计算哈希值，哈希值与服务 器数量进行取模运算，得到的值就是当前请求应该被路由到的服务器编号，如此，同一个客户端ip发送 过来的请求就可以路由到同一个目标服务器，实现会话粘滞。

2. 分布式存储

以分布式内存数据库Redis为例,集群中有redis1，redis2，redis3 三台Redis服务器那么,在进行数据存储时,存储<key1,value1>数据时，针对key进行hash处理 hash(key1)%3=index, 使用余数index锁定存储的具体服务器节点

普通Hash算法存在的问题

• 普通Hash算法存在一个问题，以ip_hash为例，假定下载用户ip固定没有发生改变，有三台tomcat服务器，其中一台出现 了问题，down机了，服务器数量由3个变为了2个，之前所有的求模都需要重新计算，如下图
  
• 如果在真实生产情况下，后台服务器很多台，客户端也有很多，那么影响是很大的，缩容和扩容都会存 在这样的问题，大量用户的请求会被路由到其他的目标服务器处理，用户在原来服务器中的会话都会丢 失。

一致性Hash算法

• 一致性哈希算法思路如下:
  
• 首先有一条直线，直线开头和结尾分别定为为1和2的32次方减1，这相当于一个地址，对于这样一条 线，弯过来构成一个圆环形成闭环，这样的一个圆环称为hash环。我们把服务器的ip或者主机名求 hash值然后对应到hash环上，那么针对客户端用户，也根据它的ip进行hash求值，对应到环上某个位 置，然后如何确定一个客户端路由到哪个服务器处理呢?按照顺时针方向找最近的服务器节点，如下图
  
• 假如将服务器3下线，服务器3下线后，原来路由到3的客户端重新路由到服务器4，对于其他客户端没有 影响只是这一小部分受影响(请求的迁移达到了最小，这样的算法对分布式集群来说非常合适的，避免 了大量请求迁移 )
  
• 增加服务器5之后，原来路由到3的部分客户端路由到新增服务器5上，对于其他客户端没有影响只是这 一小部分受影响(请求的迁移达到了最小，这样的算法对分布式集群来说非常合适的，避免了大量请求 迁移 )
  

1. 如前所述，每一台服务器负责一段，一致性哈希算法对于节点的增减都只需重定位环空间中的一小 部分数据，具有较好的容错性和可扩展性。但是，一致性哈希算法在服务节点太少时，容易因为节点分部不均匀而造成数据倾斜问题。例如系统中 只有两台服务器，其环分布如下左边，节点2只能负责非常小的一段，大量的客户端请求落在了节点1上，这就是数据(请求)倾斜问题

2. 为了解决这种数据倾斜问题，一致性哈希算法引入了虚拟节点机制，即对每一个服务节点计算多个哈希，每个计算结果位置都放置一个此服务节点，称为虚拟节点。

3. 具体做法可以在服务器ip或主机名的后面增加编号来实现。比如，可以为每台服务器计算三个虚拟节 点，于是可以分别计算 “节点1的ip#1”、“节点1的ip#2”、“节点1的ip#3”、“节点2的ip#1”、“节点2的 ip#2”、“节点2的ip#3”的哈希值，于是形成六个虚拟节点，当客户端被路由到虚拟节点的时候其实是被 路由到该虚拟节点所对应的真实节点，如下图右边部分。

本文地址：https://blog.csdn.net/rzpy_qifengxiaoyue/article/details/107578731