• 一句话描述

将数值key使用相同的函数H计算出哈希值h,根据h确定key在环上的位置，“顺时针”行走遇到的第一台服务器就是需要定位的服务器。

不带虚拟节点的一致性Hash算法

  1. ● 一句话描述
  2. 将数值key使用相同的函数H计算出哈希值h,根据h确定key在环上的位置，“顺时针”行走遇到的第一台服务器就是需要定位的服务器。
  3. ● 特性
  4.   ○ 容错性
  5.   ○ 扩展性
  6. ● Hash算法的选择
  7.   ○ Hash算法一般不自己写，采用现成的；
  8.   ○ 参考 http://www.alloyteam.com/2017/05/hash-functions-introduction/
  9. ● 数据倾斜问题
  10.   ○ 增加虚拟节点；
  11. ● 应用场景
  12.   ○ 分布式缓存中有实践；
  13.   ○ 优点：减少数据迁移时的大量ID变动,提升性能；
  14. ● 面试
  15.   ○ 一致性哈希算法在分布式场景中的应用
  16.   ○ 漫画：什么是一致性哈希
  17. ● 一致性Hash基于Java的实现
  18.   ○ https://www.cnblogs.com/yiwangzhibujian/p/7090471.html
  19.   ○ 对一致性Hash算法，Java代码实现的深入研究
  23. 不带虚拟节点的一致性Hash算法
  24. public class ConsistentHashingWithoutVirtualNode {
  26.     /**
  27.      * 待添加入Hash环的服务器列表
  28.      */
  29.     private static String[] servers = {"192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111",
  30.             "192.168.0.3:111", "192.168.0.4:111"};
  32.     /**
  33.      * key表示服务器的hash值，value表示服务器的名称
  34.      */
  35.     private static SortedMap<Integer, String> sortedMap = new TreeMap<Integer, String>();
  37.     /**
  38.      * 程序初始化，将所有的服务器放入sortedMap中
  39.      */
  40.     static {
  41.         for (int i = 0; i < servers.length; i++) {
  42.             int hash = getHash(servers[i]);
  43.             System.out.println("[" + servers[i] + "]加入集合中, 其Hash值为" + hash);
  44.             sortedMap.put(hash, servers[i]);
  45.         }
  46.         System.out.println();
  47.     }
  49.     public static void main(String[] args) {
  50.         String[] nodes = {"127.0.0.1:1111", "221.226.0.1:2222", "10.211.0.1:3333"};
  51.         for (int i = 0; i < nodes.length; i++) {
  52.             System.out.println("[" + nodes[i] + "]的hash值为" +
  53.                     getHash(nodes[i]) + ", 被路由到结点[" + getServer(nodes[i]) + "]");
  54.         }
  55.     }
  57.     /**
  58.      * 使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法，最终效果没区别
  59.      */
  60.     private static int getHash(String str) {
  61.         final int p    = 16777619;
  62.         int       hash = (int) 2166136261L;
  63.         for (int i = 0; i < str.length(); i++) { hash = (hash ^ str.charAt(i)) * p; }
  64.         hash += hash << 13;
  65.         hash ^= hash >> 7;
  66.         hash += hash << 3;
  67.         hash ^= hash >> 17;
  68.         hash += hash << 5;
  70.         // 如果算出来的值为负数则取其绝对值
  71.         if (hash < 0) { hash = Math.abs(hash); }
  72.         return hash;
  73.     }
  75.     /**
  76.      * 得到应当路由到的结点
  77.      */
  78.     private static String getServer(String node) {
  79.         // 得到带路由的结点的Hash值
  80.         int hash = getHash(node);
  81.         // 得到大于该Hash值的所有Map
  82.         SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);
  83.         // 第一个Key就是顺时针过去离node最近的那个结点
  84.         Integer i = subMap.firstKey();
  85.         // 返回对应的服务器名称
  86.         return subMap.get(i);
  87.     }
  88. }
  91. 带虚拟节点的一致性Hash算法
  92. public class ConsistentHashingWithVirtualNode
  93. {
  94.     /**
  95.      * 待添加入Hash环的服务器列表
  96.      */
  97.     private static String[] servers = {"192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111",
  98.             "192.168.0.3:111", "192.168.0.4:111"};
  100.     /**
  101.      * 真实结点列表,考虑到服务器上线、下线的场景，即添加、删除的场景会比较频繁，这里使用LinkedList会更好
  102.      */
  103.     private static List<String> realNodes = new LinkedList<String>();
  105.     /**
  106.      * 虚拟节点，key表示虚拟节点的hash值，value表示虚拟节点的名称
  107.      */
  108.     private static SortedMap<Integer, String> virtualNodes =
  109.             new TreeMap<Integer, String>();
  111.     /**
  112.      * 虚拟节点的数目，这里写死，为了演示需要，一个真实结点对应5个虚拟节点
  113.      */
  114.     private static final int VIRTUAL_NODES = 5;
  116.     static
  117.     {
  118.         // 先把原始的服务器添加到真实结点列表中
  119.         for (int i = 0; i < servers.length; i++) { realNodes.add(servers[i]); }
  121.         // 再添加虚拟节点，遍历LinkedList使用foreach循环效率会比较高
  122.         for (String str : realNodes)
  123.         {
  124.             for (int i = 0; i < VIRTUAL_NODES; i++)
  125.             {
  126.                 String virtualNodeName = str + "&&VN" + String.valueOf(i);
  127.                 int hash = getHash(virtualNodeName);
  128.                 System.out.println("虚拟节点[" + virtualNodeName + "]被添加, hash值为" + hash);
  129.                 virtualNodes.put(hash, virtualNodeName);
  130.             }
  131.         }
  132.         System.out.println();
  133.     }
  135.     /**
  136.      * 使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法，最终效果没区别 
  137.      */
  138.     private static int getHash(String str)
  139.     {
  140.         final int p = 16777619;
  141.         int hash = (int)2166136261L;
  142.         for (int i = 0; i < str.length(); i++) { hash = (hash ^ str.charAt(i)) * p; }
  143.         hash += hash << 13;
  144.         hash ^= hash >> 7;
  145.         hash += hash << 3;
  146.         hash ^= hash >> 17;
  147.         hash += hash << 5;
  149.         // 如果算出来的值为负数则取其绝对值
  150.         if (hash < 0) { hash = Math.abs(hash); }
  151.         return hash;
  152.     }
  154.     /**
  155.      * 得到应当路由到的结点
  156.      */
  157.     private static String getServer(String node)
  158.     {
  159.         // 得到带路由的结点的Hash值
  160.         int hash = getHash(node);
  161.         // 得到大于该Hash值的所有Map
  162.         SortedMap<Integer, String> subMap = 
  163.                 virtualNodes.tailMap(hash);
  164.         // 第一个Key就是顺时针过去离node最近的那个结点
  165.         Integer i = subMap.firstKey();
  166.         // 返回对应的虚拟节点名称，这里字符串稍微截取一下
  167.         String virtualNode = subMap.get(i);
  168.         return virtualNode.substring(0, virtualNode.indexOf("&&"));
  169.     }
  171.     public static void main(String[] args)
  172.     {
  173.         String[] nodes = {"127.0.0.1:1111", "221.226.0.1:2222", "10.211.0.1:3333"};
  174.         for (int i = 0; i < nodes.length; i++) {
  175.             System.out.println("[" + nodes[i] + "]的hash值为" +
  176.                     getHash(nodes[i]) + ", 被路由到结点[" + getServer(nodes[i]) + "]");
  177.         }
  178.     }
  179. }

面试选备：一致性Hash算法 - 图1

带虚拟节点的一致性Hash算法

  1. ● 一句话描述
  2. 将数值key使用相同的函数H计算出哈希值h,根据h确定key在环上的位置，“顺时针”行走遇到的第一台服务器就是需要定位的服务器。
  3. ● 特性
  4.   ○ 容错性
  5.   ○ 扩展性
  6. ● Hash算法的选择
  7.   ○ Hash算法一般不自己写，采用现成的；
  8.   ○ 参考 http://www.alloyteam.com/2017/05/hash-functions-introduction/
  9. ● 数据倾斜问题
  10.   ○ 增加虚拟节点；
  11. ● 应用场景
  12.   ○ 分布式缓存中有实践；
  13.   ○ 优点：减少数据迁移时的大量ID变动,提升性能；
  14. ● 面试
  15.   ○ 一致性哈希算法在分布式场景中的应用
  16.   ○ 漫画：什么是一致性哈希
  17. ● 一致性Hash基于Java的实现
  18.   ○ https://www.cnblogs.com/yiwangzhibujian/p/7090471.html
  19.   ○ 对一致性Hash算法，Java代码实现的深入研究
  23. 不带虚拟节点的一致性Hash算法
  24. public class ConsistentHashingWithoutVirtualNode {
  26.     /**
  27.      * 待添加入Hash环的服务器列表
  28.      */
  29.     private static String[] servers = {"192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111",
  30.             "192.168.0.3:111", "192.168.0.4:111"};
  32.     /**
  33.      * key表示服务器的hash值，value表示服务器的名称
  34.      */
  35.     private static SortedMap<Integer, String> sortedMap = new TreeMap<Integer, String>();
  37.     /**
  38.      * 程序初始化，将所有的服务器放入sortedMap中
  39.      */
  40.     static {
  41.         for (int i = 0; i < servers.length; i++) {
  42.             int hash = getHash(servers[i]);
  43.             System.out.println("[" + servers[i] + "]加入集合中, 其Hash值为" + hash);
  44.             sortedMap.put(hash, servers[i]);
  45.         }
  46.         System.out.println();
  47.     }
  49.     public static void main(String[] args) {
  50.         String[] nodes = {"127.0.0.1:1111", "221.226.0.1:2222", "10.211.0.1:3333"};
  51.         for (int i = 0; i < nodes.length; i++) {
  52.             System.out.println("[" + nodes[i] + "]的hash值为" +
  53.                     getHash(nodes[i]) + ", 被路由到结点[" + getServer(nodes[i]) + "]");
  54.         }
  55.     }
  57.     /**
  58.      * 使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法，最终效果没区别
  59.      */
  60.     private static int getHash(String str) {
  61.         final int p    = 16777619;
  62.         int       hash = (int) 2166136261L;
  63.         for (int i = 0; i < str.length(); i++) { hash = (hash ^ str.charAt(i)) * p; }
  64.         hash += hash << 13;
  65.         hash ^= hash >> 7;
  66.         hash += hash << 3;
  67.         hash ^= hash >> 17;
  68.         hash += hash << 5;
  70.         // 如果算出来的值为负数则取其绝对值
  71.         if (hash < 0) { hash = Math.abs(hash); }
  72.         return hash;
  73.     }
  75.     /**
  76.      * 得到应当路由到的结点
  77.      */
  78.     private static String getServer(String node) {
  79.         // 得到带路由的结点的Hash值
  80.         int hash = getHash(node);
  81.         // 得到大于该Hash值的所有Map
  82.         SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);
  83.         // 第一个Key就是顺时针过去离node最近的那个结点
  84.         Integer i = subMap.firstKey();
  85.         // 返回对应的服务器名称
  86.         return subMap.get(i);
  87.     }
  88. }
  91. 带虚拟节点的一致性Hash算法
  92. public class ConsistentHashingWithVirtualNode
  93. {
  94.     /**
  95.      * 待添加入Hash环的服务器列表
  96.      */
  97.     private static String[] servers = {"192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111",
  98.             "192.168.0.3:111", "192.168.0.4:111"};
  100.     /**
  101.      * 真实结点列表,考虑到服务器上线、下线的场景，即添加、删除的场景会比较频繁，这里使用LinkedList会更好
  102.      */
  103.     private static List<String> realNodes = new LinkedList<String>();
  105.     /**
  106.      * 虚拟节点，key表示虚拟节点的hash值，value表示虚拟节点的名称
  107.      */
  108.     private static SortedMap<Integer, String> virtualNodes =
  109.             new TreeMap<Integer, String>();
  111.     /**
  112.      * 虚拟节点的数目，这里写死，为了演示需要，一个真实结点对应5个虚拟节点
  113.      */
  114.     private static final int VIRTUAL_NODES = 5;
  116.     static
  117.     {
  118.         // 先把原始的服务器添加到真实结点列表中
  119.         for (int i = 0; i < servers.length; i++) { realNodes.add(servers[i]); }
  121.         // 再添加虚拟节点，遍历LinkedList使用foreach循环效率会比较高
  122.         for (String str : realNodes)
  123.         {
  124.             for (int i = 0; i < VIRTUAL_NODES; i++)
  125.             {
  126.                 String virtualNodeName = str + "&&VN" + String.valueOf(i);
  127.                 int hash = getHash(virtualNodeName);
  128.                 System.out.println("虚拟节点[" + virtualNodeName + "]被添加, hash值为" + hash);
  129.                 virtualNodes.put(hash, virtualNodeName);
  130.             }
  131.         }
  132.         System.out.println();
  133.     }
  135.     /**
  136.      * 使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法，最终效果没区别 
  137.      */
  138.     private static int getHash(String str)
  139.     {
  140.         final int p = 16777619;
  141.         int hash = (int)2166136261L;
  142.         for (int i = 0; i < str.length(); i++) { hash = (hash ^ str.charAt(i)) * p; }
  143.         hash += hash << 13;
  144.         hash ^= hash >> 7;
  145.         hash += hash << 3;
  146.         hash ^= hash >> 17;
  147.         hash += hash << 5;
  149.         // 如果算出来的值为负数则取其绝对值
  150.         if (hash < 0) { hash = Math.abs(hash); }
  151.         return hash;
  152.     }
  154.     /**
  155.      * 得到应当路由到的结点
  156.      */
  157.     private static String getServer(String node)
  158.     {
  159.         // 得到带路由的结点的Hash值
  160.         int hash = getHash(node);
  161.         // 得到大于该Hash值的所有Map
  162.         SortedMap<Integer, String> subMap = 
  163.                 virtualNodes.tailMap(hash);
  164.         // 第一个Key就是顺时针过去离node最近的那个结点
  165.         Integer i = subMap.firstKey();
  166.         // 返回对应的虚拟节点名称，这里字符串稍微截取一下
  167.         String virtualNode = subMap.get(i);
  168.         return virtualNode.substring(0, virtualNode.indexOf("&&"));
  169.     }
  171.     public static void main(String[] args)
  172.     {
  173.         String[] nodes = {"127.0.0.1:1111", "221.226.0.1:2222", "10.211.0.1:3333"};
  174.         for (int i = 0; i < nodes.length; i++) {
  175.             System.out.println("[" + nodes[i] + "]的hash值为" +
  176.                     getHash(nodes[i]) + ", 被路由到结点[" + getServer(nodes[i]) + "]");
  177.         }
  178.     }
  179. }

面试选备：一致性Hash算法 - 图2