数据查找一般有一下方法

  • 【顺序查找法】遍历判断是否相等。效率不高
  • 【二分查找】排序再折半查找。效率不高
  • 【直接寻址法】定义一个数组，数组⻓度大于等于最大的数据值，从下标判断数据是否存在。效率高，但浪费空间
  • 【开放寻址法】定义一个存储数组，对值取模作为下标，从下标判断数据是否存在。会导致Hash冲突
  • 【拉链法】在开放寻址法的基础上，Hash相同的位置，存放一个链表
  • …

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

普通Hash算法

普通Hash算法存在一个问题，以ip_hash为例，假定下载用户ip固定没有发生改变，服务器缩容或者扩容，之前所有的求模都需要重新计算。影响非常大。

  1. public static void main(String[] args) {
  2.     // 定义客户端IP
  3.     String[] clients = new String[]{"10.78.12.3","113.25.63.1","126.12.3.8"};
  5.     // 定义服务器数量
  6.     int serverCount = 5;// (编号对应0，1，2)
  8.     // hash(ip)%node_counts=index
  9.     //根据index锁定应该路由到的tomcat服务器
  10.     for(String client: clients) {
  11.         int hash = Math.abs(client.hashCode());
  12.         int index = hash%serverCount;
  13.         System.out.println("客户端：" + client + " 被路由到服务器编号为：" + index);
  14.     }
  15. }

一致性Hash算法

我们将所有服务器的ip或者主机名求hash，并放在一个圆环上，对客户端ip进行hash计算，按照顺时针方向找最近的服务器节点，如下图
一致性Hash算法 - 图3

缩容
一致性Hash算法 - 图4

假如将服务器3下线，服务器3下线后，原来路由到3的客户端重新路由到服务器4，对于其他客户端没有 影响只是这一小部分受影响(请求的迁移达到了最小，这样的算法对分布式集群来说非常合适的，避免 了大量请求迁移 )

扩容
一致性Hash算法 - 图5

增加服务器5之后，原来路由到3的部分客户端路由到新增服务器5上，对于其他客户端没有影响只是这 一小部分受影响(请求的迁移达到了最小，这样的算法对分布式集群来说非常合适的，避免了大量请求 迁移 )

一致性Hash算法实现

  1. public static void main(String[] args) {
  2.     //step1 初始化：把服务器节点IP的哈希值对应到哈希环上
  3.     // 定义服务器ip
  4.     String[] tomcatServers = new String[]{"123.111.0.0","123.101.3.1","111.20.35.2","123.98.26.3"};
  6.     SortedMap<Integer,String> hashServerMap = new TreeMap<>();
  9.     for(String tomcatServer: tomcatServers) {
  10.         // 求出每一个ip的hash值，对应到hash环上，存储hash值与ip的对应关系
  11.         int serverHash = Math.abs(tomcatServer.hashCode());
  12.         // 存储hash值与ip的对应关系
  13.         hashServerMap.put(serverHash,tomcatServer);
  15.     }
  18.     //step2 针对客户端IP求出hash值
  19.     // 定义客户端IP
  20.     String[] clients = new String[]{"10.78.12.3","113.25.63.1","126.12.3.8"};
  21.     for(String client : clients) {
  22.         int clientHash = Math.abs(client.hashCode());
  23.         //step3 针对客户端,找到能够处理当前客户端请求的服务器（哈希环上顺时针最近）
  24.         // 根据客户端ip的哈希值去找出哪一个服务器节点能够处理（）
  25.         SortedMap<Integer, String> integerStringSortedMap = hashServerMap.tailMap(clientHash);
  26.         if(integerStringSortedMap.isEmpty()) {
  27.             // 取哈希环上的顺时针第一台服务器
  28.             Integer firstKey = hashServerMap.firstKey();
  29.             System.out.println("==========>>>>客户端：" + client + " 被路由到服务器：" + hashServerMap.get(firstKey));
  30.         }else{
  31.             Integer firstKey = integerStringSortedMap.firstKey();
  32.             System.out.println("==========>>>>客户端：" + client + " 被路由到服务器：" + hashServerMap.get(firstKey));
  33.         }
  34.     }
  35. }

一致性哈希算法在服务节点太少时，容易因为节点分部不均匀而造成数据倾斜问题。例如系统中 只有两台服务器，其环分布如下，节点2只能负责非常小的一段，大量的客户端请求落在了节点1上，这就是数据(请求)倾斜问题

一致性Hash+虚拟节点

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

  1. public static void main(String[] args) {
  2.     //step1 初始化：把服务器节点IP的哈希值对应到哈希环上
  3.     // 定义服务器ip
  4.     String[] tomcatServers = new String[]{"123.111.0.0","123.101.3.1","111.20.35.2","123.98.26.3"};
  6.     SortedMap<Integer,String> hashServerMap = new TreeMap<>();
  9.     // 定义针对每个真实服务器虚拟出来几个节点
  10.     int virtaulCount = 3;
  13.     for(String tomcatServer: tomcatServers) {
  14.         // 求出每一个ip的hash值，对应到hash环上，存储hash值与ip的对应关系
  15.         int serverHash = Math.abs(tomcatServer.hashCode());
  16.         // 存储hash值与ip的对应关系
  17.         hashServerMap.put(serverHash,tomcatServer);
  19.         // 处理虚拟节点
  20.         for(int i = 0; i < virtaulCount; i++) {
  21.             int virtualHash = Math.abs((tomcatServer + "#" + i).hashCode());
  22.             hashServerMap.put(virtualHash,"----由虚拟节点"+ i  + "映射过来的请求："+ tomcatServer);
  23.         }
  25.     }
  28.     //step2 针对客户端IP求出hash值
  29.     // 定义客户端IP
  30.     String[] clients = new String[]{"10.78.12.3","113.25.63.1","126.12.3.8"};
  31.     for(String client : clients) {
  32.         int clientHash = Math.abs(client.hashCode());
  33.         //step3 针对客户端,找到能够处理当前客户端请求的服务器（哈希环上顺时针最近）
  34.         // 根据客户端ip的哈希值去找出哪一个服务器节点能够处理（）
  35.         SortedMap<Integer, String> integerStringSortedMap = hashServerMap.tailMap(clientHash);
  36.         if(integerStringSortedMap.isEmpty()) {
  37.             // 取哈希环上的顺时针第一台服务器
  38.             Integer firstKey = hashServerMap.firstKey();
  39.             System.out.println("==========>>>>客户端：" + client + " 被路由到服务器：" + hashServerMap.get(firstKey));
  40.         }else{
  41.             Integer firstKey = integerStringSortedMap.firstKey();
  42.             System.out.println("==========>>>>客户端：" + client + " 被路由到服务器：" + hashServerMap.get(firstKey));
  43.         }
  44.     }
  45. }