一致性Hash在缓存中的使用

1. 一致性Hash与redis集群的区别         

   redis集群  有主从的划分，主挂了可以从抵上；从再挂则集群无法使用
   
   一致性Hash 挂一个或者两个都是无所谓      各redis之间是完全独立的

    

2.  一致性Hash的实践

   package home.spring.boot.hash;
   
   import java.util.HashMap;
   import java.util.Map;
   import java.util.SortedMap;
   import java.util.TreeMap;
   
   public class ConsistentHashingWithoutVirtualNode {
   
       /**
        * 集群地址列表
        */
       private static String[] groups = {
           "192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111", "192.168.0.3:111", "192.168.0.4:111"
       };
   
       /**
        * 用于保存Hash环上的节点
        */
       private static SortedMap<Integer, String> sortedMap = new TreeMap<>();
   
       /**
        * 初始化，将所有的服务器加入Hash环中
        */
       static {
           for (String group : groups) {   // 使用红黑树实现，插入效率比较差，但是查找效率极高
               int hash = HashUtil.getHash(group);
               System.out.println("[" + group + "] launched @ " + hash);
               sortedMap.put(hash, group);
           }
       }
   
       /**
        * 计算对应的widget加载在哪个group上
        *
        * @param widgetKey
        * @return
        */
       private static String getServer(String widgetKey) {
           int hash = HashUtil.getHash(widgetKey);
           SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);   // 只取出所有大于该hash值的部分而不必遍历整个Tree
           if (subMap == null || subMap.isEmpty()) {
               return sortedMap.get(sortedMap.firstKey());  // hash值在最尾部，应该映射到第一个group上
           }
           return subMap.get(subMap.firstKey());
       }
   
       public static void main(String[] args) {
           Map<String, Integer> resMap = new HashMap<>();  // 生成随机数进行测试
           for (int i = 0; i < 100000; i++) {
               Integer widgetId = (int)(Math.random() * 10000);
               String server = getServer(widgetId.toString());
               if (resMap.containsKey(server)) {
                   resMap.put(server, resMap.get(server) + 1);
               } else {
                   resMap.put(server, 1);
               }
           }
           resMap.forEach(
               (k, v) -> {
                   System.out.println("group " + k + ": " + v + "(" + v/1000.0D +"%)");
               }
           );
       }
   }

    下面是增加了虚拟节点

   package home.spring.boot.hash;
   
   import java.util.*;
   
   public class ConsistentHashingWithVirtualNode {
       /**
        * 集群地址列表
        */
       private static String[] groups = {
           "192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111",
           "192.168.0.3:111", "192.168.0.4:111"
       };
   
       /**
        * 真实集群列表
        */
       private static List<String> realGroups = new LinkedList<>();
   
       /**
        * 虚拟节点映射关系
        */
       private static SortedMap<Integer, String> virtualNodes = new TreeMap<>();
   
       private static final int VIRTUAL_NODE_NUM = 1000;
   
       static {
           realGroups.addAll(Arrays.asList(groups));   // 先添加真实节点列表
           for (String realGroup: realGroups) {              // 将虚拟节点映射到Hash环上
               for (int i = 0; i < VIRTUAL_NODE_NUM; i++) {
                   String virtualNodeName = getVirtualNodeName(realGroup, i);
                   int hash = HashUtil.getHash(virtualNodeName);
                   System.out.println("[" + virtualNodeName + "] launched @ " + hash);
                   virtualNodes.put(hash, virtualNodeName);
               }
           }
   
           System.out.println(virtualNodes);
       }
   
       private static String getVirtualNodeName(String realName, int num) {
           return realName + "&&VN" + String.valueOf(num);
       }
   
       private static String getRealNodeName(String virtualName) {
           return virtualName.split("&&")[0];
       }
   
       private static String getServer(String widgetKey) {
           int hash = HashUtil.getHash(widgetKey);
           // 只取出所有大于该hash值的部分而不必遍历整个Tree
           SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);
           String virtualNodeName;
           if (subMap == null || subMap.isEmpty()) {
               // hash值在最尾部，应该映射到第一个group上
               virtualNodeName = virtualNodes.get(virtualNodes.firstKey());
           }else {
               virtualNodeName = subMap.get(subMap.firstKey());
           }
           return getRealNodeName(virtualNodeName);
       }
   
       public static void main(String[] args) {
   
           Map<String, Integer> resMap = new HashMap<>();  // 生成随机数进行测试
   
           for (int i = 0; i < 100000; i++) {
               Integer widgetId = i;
               String group = getServer(widgetId.toString());
               if (resMap.containsKey(group)) {
                   resMap.put(group, resMap.get(group) + 1);
               } else {
                   resMap.put(group, 1);
               }
           }
   
           resMap.forEach(
               (k, v) -> {
                   System.out.println("group " + k + ": " + v + "(" + v/100000.0D +"%)");
               }
           );
       }
   }