# 分布式集群架构场景化解决方案(一)-一致性Hash算法
[TOC]
## 普通Hash算法与Hash算法使用场景
Hash算法，比如说在安全加密领域MD5、SHA等加密算法，在数据存储和查找方面有Hash表等, 以上都应用到了Hash算法。
**为什么需要使用Hash算法?**
Hash算法较多的应用在数据存储和查找领域，最经典的就是Hash表，它的查询效率非常高，其中的哈希算法如果设计的比较ok的话，那么Hash表的数据查询时间复杂度可以接近于O(1)
**Hash算法的主要场景**
- 请求的负载均衡（比如nginx的ip_hash策略）Nginx的IP_hash策略可以在客户端ip不变的情况下，将其发的请求始终路由到同⼀个目标服务器上，实现会话粘滞，避免处理session共享问题
- 分布式存储-分布式数据存储方案中最为重要的一点就是数据分片，也就是所谓的 Sharding。以分布式内存数据库Redis为例,将数据分片存储在三台服务器上,将key使用hash算法进行计算,判断应当存储在哪一台服务器上,减轻单个Redis服务的压力
**普通Hash算法的问题**
普通Hash算法存在⼀个问题，以ip_hash为例，假定下载用户ip固定没有发生改变，现在tomcat3出现了问题，down机了，服务器数量由3个变为了2个，之前所有的计算都需要重新计算
如果在真实生产情况下，后台服务器很多台，客户端也有很多，那么影响是很大的，缩容和扩容都会存在这样的问题，大量用户的请求会被路由到其他的⽬标服务器处理，用户在原来服务器中的会话都会丢失
## ⼀致性Hash算法
⼀致性哈希算法思路如下：
开头和结尾分别定为为1和2的32次方减一,构成一个环,每个服务端节点的IP地址进行求值并且对应到Hash环上,针对客户端的用户,也根据它的IP进行Hash求值,这样对应到环上的某个位置,顺时针找到最近的服务器节点就是它应当访问的服务器节点
使用一致性算法的话,假如一个服务器3下线,那么原来路由到3的客户端重新会路由到服务器4,这样只需要迁移一部分原有应该访问到服务器3的请求到服务器4上面,降低了迁移请求造成的影响
同样,增加一个服务器也会将请求的迁移降低到最低
### 一致性Hash算法的缺点
如上面所述,每一台服务器负责一段,对于节点的增减有很方便的扩展下和容错性
**缺点**:
当一致性哈希算法在服务节点太少时,容易因为节点分布不均匀导致数据倾斜问题,大量数据都传递到了一台服务器,导致服务器压力过大
**解决方案**:
为了解决这种问题,一致性Hash算法引入了虚拟节点的方案,针对每一个服务节点计算多个Hash,每个计算结果未知都放置一个此服务节点,称为虚拟节点
具体做法:
在服务器的IP或者主机名或者用于计算的Key值后面增加编号来实现,例如每台服务器可以扩展成三个节点,就可以计算"节点1的IP#1","节点1的IP#2","节点1的IP#3","节点2的IP#1","节点2的IP#2","节点2的IP#3",这样就相当于将两个Hash节点扩展成了6个Hash节点,并且路由到虚拟节点时也是实际节点去处理的,这样就避免了我们所说的数据倾斜问题
## 手写一致性算法实现
```java
public class ConsistentHashMain {
private static int virtualNode = 3;
public static void main(String[] args) {
//服务端的IP
String[] serverIps = new String[]{"10.20.169.61","10.20.168.209","10.20.165.20"};
//使用排序Map,这样的话可以取到最近的那个节点
SortedMap<Integer,String> hashServerMap = new TreeMap<>();
for (String server : serverIps) {
for (int i = 0; i < virtualNode; i++) {
//对原有节点IP进行编号
String tempServer = server + "#" +i;
//hash值只取正值
Integer hashCode = Math.abs(tempServer.hashCode());
hashServerMap.put(hashCode,"虚拟节点"+i+"指向的->"+ server);
}
}
//模拟客户端的请求IP
String[] clientIps = new String[]{"127.0.0.1","10.53.214.22","20.23.241.23","112.55.22.24","22.55.22.24"};
for (String clientIp : clientIps) {
//获取客户端的IP的Hash值
Integer hashCode = Math.abs(clientIp.hashCode());
//取出比该值更大的Map数据
SortedMap<Integer, String> tailMap = hashServerMap.tailMap(hashCode);
//如果为空,则直接取原来的第一个节点
if (tailMap.isEmpty()) {
Integer key = hashServerMap.firstKey();
String value = hashServerMap.get(key);
System.out.println("客户端IP:"+clientIp+"分发到了服务器的节点:"+value);
}else{
//否则取顺时针第一个节点
Integer key = tailMap.firstKey();
String value = hashServerMap.get(key);
System.out.println("客户端IP:"+clientIp+"分发到了服务器的节点:"+value);
}
}
}
}
```
分布式集群架构场景化解决方案(一)-一致性Hash算法