一致性Hash算法

分布式和集群

分布式一定是集群，集群不一定是分布式。

分布式

分布式是将一个系统的功能进行拆分之后的多个实例。把一个系统拆分为多个子系统，每个子系统负责各自的部分功能，独立部署，各司其职。

集群

多个实例共同工作，最简单、最常见的集群时把一个应用复制多份部署。

一致性Hash算法

为什么使用Hash算法

Hash算法较多的应用在数据存储和查找领域，最经典的就是Hash算法。查询效率高，如果哈希算法设计得好，则Hash表的数据查询时间复杂度接近于O(1)。

常见的数据查询方式

遍历查找法

即直接对这组数据进行for循环遍历查找指定的数据。

二分查找

前提是查询的这组数据是顺序排列的，那就可以在排序之后进行折半查找。

直接寻址法

直接将这组数据和数组的下标绑定在一起，查找的时候，直接array[n]就取出了数据。
优点：查询效率高
缺点：浪费空间。如果这组数据为：1，5，7，6，4，12306，则按照直接寻址法，就需要定义长度为12307的数组，但是只存储零星的几个数据，其他位置空间都浪费着。
如果这组数据为：1，1，1，2，3，3，3，4，5，最大值为5，比如开辟了6个空间，也无法存储所有的数据。

hash值取模法

计算数据的Hash值，并进行结果与总数据长度的取模，得到数据在数组中合理的存储位置。如果出现hash冲突的情况，则通过拉链法在数组的指定下标位置纵向放置一个链表。这种方式就是Hash表的查询方式。
Hash表的查询效率高不高取决于Hash算法，如果Hash算法能够让数据平均分布，则就能够节省空间并能够提供查询效率。

Hash算法的应用场景

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

请求的负载均衡

比如Nginx的ip_hash策略
Nginx的ip_hash策略可以在客户端ip不变的情况下，将其发出的请求始终路由到同一个目标服务器上，实现会话粘滞，避免处理session共享的问题。

如果没有ip_hash策略，那么如何实现会话粘滞 (1) 可以维护一张映射表，存储客户端ip或者sessionId与具体服务器的映射关系: 缺点：在客户端很多的情况下，映射表会非常大，浪费内存空间；客户端上下线，目标服务器上下线，都会导致重新维护映射表，映射表的维护成本大。 (2) 使用Hash算法，对ip地址或者sessionId进行计算哈希值，哈希值再与服务器数量进行取模运算，得到的值就是当前请求应该被路由到的服务器编号。 如此，同一个客户端ip发送过来的请求就可以路由到同一个目标服务器，实现会话粘滞。

分布式存储

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

普通Hash算法存在的问题

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

一致性Hash算法

一致性Hash算法思路

首先有一条直线，直线的开头和结尾分别定为 1 和 2^32-1 （直线上的每个地方相当于一个地址）；
对于这样的一条直线，设计构成为一个圆环形成的闭环，这样的一个闭环就是Hash环。
我们将服务器的ip地址或者主机名求hash值然后对应到hash环上；同时，针对客户端用户，也根据它的ip地址进行hash求值，对应到环上某个位置。
然后按照顺时针的方向，查找距离客户端最近的服务器节点，来确定客户端路由到哪个服务器进行处理。

此时，如果服务器3下线，原来路由到服务器3的客户端则会重新路由到服务器4，对于其他的客户端就没有影响。
所以，一致性hash算法，会将请求的迁移影响达到最小，这样的算法对于分布式集群来说是非常合适的，避免了大量的请求迁移。在服务器集群进行缩容和扩容，影响迁移的客户端相对会少。

一致性hash算法存在的问题及解决方案

• 数据请求倾斜的问题

在一致性hash算法服务器节点太少时，容易因为节点的分布不均匀导致数据倾斜的问题。例如系统中只有两台服务器，可能会导致节点2只负责非常小的一段，大量的客户端落在了节点1上。

• 解决方案

一致性hash算法引入虚拟节点的机制。即对每一个服务节点计算多个hash，每个计算结果位置都放置一个此服务节点，成为虚拟节点。
具体做法可以在服务器ip后面增加编号来实现。比如，可以在每台服务器计算三个虚拟节点，于是分别计算： 节点1IP#1，节点1IP#2，节点1IP#3；节点2IP#1，节点2IP#2，节点2IP#3 的hash值，于是形成六个虚拟节点，当客户端被路由到虚拟节点的时候其实就是被路由到该虚拟节点所对应的真实节点。

手写实现一致性Hash算法

普通Hash算法实现

/**
* 普通Hash算法实现
*/
public class GeneralHash {
     public static void main(String[] args) {
         // 定义客户端IP
         String[] clients = new String[]{"10.78.12.3","113.25.63.1","126.12.3.8"};
         // 定义服务器数量
         int serverCount = 5;// (编号对应0，1，2)
         // hash(ip)%node_counts=index
         //根据index锁定应该路由到的tomcat服务器
         for(String client: clients) {
             int hash = Math.abs(client.hashCode());
             int index = hash%serverCount;
             System.out.println("客户端：" + client + " 被路由到服务器编号为：" + index);
         }
     }
}

一致性Hash算法实现（不含虚拟节点）

import java.util.SortedMap;
import java.util.TreeMap;
public class ConsistentHashNoVirtual {
     public static void main(String[] args) {
     //step1 初始化：把服务器节点IP的哈希值对应到哈希环上
     // 定义服务器ip
     String[] tomcatServers = new String[]{"123.111.0.0","123.101.3.1","111.20.35.2","123.98.26.3"};
     SortedMap<Integer,String> hashServerMap = new TreeMap<>();
     for(String tomcatServer: tomcatServers) {
         // 求出每⼀个ip的hash值，对应到hash环上，存储hash值与ip的对应关系
         int serverHash = Math.abs(tomcatServer.hashCode());
         // 存储hash值与ip的对应关系
         hashServerMap.put(serverHash,tomcatServer);
     }
     //step2 针对客户端IP求出hash值
     // 定义客户端IP
     String[] clients = new String[]{"10.78.12.3","113.25.63.1","126.12.3.8"};
     for(String client : clients) {
         int clientHash = Math.abs(client.hashCode());
         //step3 针对客户端,找到能够处理当前客户端请求的服务器（哈希环上顺时针最近）
         // 根据客户端ip的哈希值去找出哪⼀个服务器节点能够处理（）
         SortedMap<Integer, String> integerStringSortedMap =
         hashServerMap.tailMap(clientHash);
          if(integerStringSortedMap.isEmpty()) {
             // 取哈希环上的顺时针第⼀台服务器
             Integer firstKey = hashServerMap.firstKey();
              System.out.println("==========>>>>客户端：" + client + " 被路由到服务器：" 
                                + hashServerMap.get(firstKey));
          } else {
             Integer firstKey = integerStringSortedMap.firstKey();
             System.out.println("==========>>>>客户端：" + client + " 被路由到服务器：" 
                                + hashServerMap.get(firstKey));
         }
     }
  }
}

一致性Hash算法实现（包含虚拟节点）

import java.util.SortedMap;
import java.util.TreeMap;
public class ConsistentHashWithVirtual {
     public static void main(String[] args) {
         //step1 初始化：把服务器节点IP的哈希值对应到哈希环上
         // 定义服务器ip
         String[] tomcatServers = new String[]{"123.111.0.0","123.101.3.1","111.20.35.2","123.98.26.3"};
         SortedMap<Integer,String> hashServerMap = new TreeMap<>();
         // 定义针对每个真实服务器虚拟出来⼏个节点
         int virtaulCount = 3;
         for(String tomcatServer: tomcatServers) {
             // 求出每⼀个ip的hash值，对应到hash环上，存储hash值与ip的对应关系
             int serverHash = Math.abs(tomcatServer.hashCode());
             // 存储hash值与ip的对应关系
             hashServerMap.put(serverHash,tomcatServer);
             // 处理虚拟节点
             for(int i = 0; i < virtaulCount; i++) {
                 int virtualHash = Math.abs((tomcatServer + "#" +i).hashCode());
                 hashServerMap.put(virtualHash,"----由虚拟节点"+ i + "映射过来的请求："
                                   + tomcatServer);
            }
         }
         //step2 针对客户端IP求出hash值
         // 定义客户端IP
         String[] clients = new String[]{"10.78.12.3","113.25.63.1","126.12.3.8"};
         for(String client : clients) {
             int clientHash = Math.abs(client.hashCode());
             //step3 针对客户端,找到能够处理当前客户端请求的服务器（哈希环上顺时针最近）
             // 根据客户端ip的哈希值去找出哪⼀个服务器节点能够处理（）
             SortedMap<Integer, String> integerStringSortedMap = hashServerMap.tailMap(clientHash);
             if(integerStringSortedMap.isEmpty()) {
                 // 取哈希环上的顺时针第⼀台服务器
                 Integer firstKey = hashServerMap.firstKey();
                 System.out.println("==========>>>>客户端：" + client + " 被路由到服务器：" 
                                    + hashServerMap.get(firstKey));
             } else {
                 Integer firstKey = integerStringSortedMap.firstKey();
                 System.out.println("==========>>>>客户端：" + client + " 被路由到服务器：" 
                                    + hashServerMap.get(firstKey));
             }
         }
     }
}

Nginx配置一致性Hash负载均衡策略

负载均衡器的介绍

ngx_http_upstream_consistent_hash 模块是一个负载均衡器，使用一个内部的一致性Hash算法来选择合适的后端节点。
该模块可以根据配置参数采取不同的方式将请求均匀映射到后端机器。
consistent_hash $remote_addr : 可以根据客户端ip映射。
consistent_hash $request_uri : 根据客户端请求的uri映射。
consistent_hash $arg : 根据客户端携带的参数进行映射。

下载与使用

(1) github 下载nginx一致性hash负载均衡模块：https://github.com/replay/ngx_http_consistent_hash
(2) 将下载的压缩包上传到nginx服务器，并解压
(3) 我们已经变异安装过nginx，此时进入当前的nginx的源码目录，执行如下命令：

/configure —add-module=/root/ngx_http_consistent_hash-master
make
make install

(4) 在nginx.conf文件中配置

upstream testServer {
        consistent_hash $remote_addr;
    server 127.0.0.1:8080;
    server 127.0.0.1:8081;
}