緩存路由（一緻性Hash）算法Java版實作

負載均衡之緩存路由(一緻性Hash)算法Java實作

  分布式系統中負載均衡的問題時候可以使用Hash算法讓固定的一部分請求落到同一台伺服器上，這樣每台伺服器固定處理一部分請求（并維護這些請求的資訊），起到負載均衡的作用。比如說分布式緩存，既然是緩存，就沒有必要去做一個所有機器上的資料都完全一樣的緩存叢集，而是應該設計一套好的緩存路由工具類，是以一緻性Hash算法就是以而誕生了。

  衡量一個一緻性Hash算法最重要的兩個特征：

①平衡性：平衡性是指哈希的結果能夠盡可能分布到所有的緩沖中去，這樣可以使得所有的緩沖空間都得到利用。

②單調性：單調性是指如果已經有一些資料通過哈希配置設定到了相應的機器上，又有新的機器加入到系統中。哈希的結果應能夠保證原有的資料要麼還是呆在它所在的機器上不動，要麼被遷移到新的機器上，而不會遷移到舊的其他機器上。

  業界常用的兩種一緻性Hash算法，一種是不帶虛拟節點的Hash算法，另外一種是帶虛拟節點的Hash算法。

  下面的代碼就是不帶虛拟節點的一緻性Hash算法，原理稍後分析：

import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.SortedMap;
import java.util.TreeMap;
import java.util.UUID;
import org.apache.commons.lang.StringUtils;

/**
 * 一緻性Hash算法
 * */
public class ConsistentHashWithoutVirtualNode {
    /**
     * 伺服器節點資訊
     * */
    private static SortedMap<Integer, String> nodeMap = new TreeMap<>();
    //伺服器配置資訊(可配置)
    private static String[] servers = {"192.168.56.120:6379",
                                       "192.168.56.121:6379", 
                                       "192.168.56.122:6379",
                                       "192.168.56.123:6379", 
                                       "192.168.56.124:6379"};
    
    /**
     * 初始化
     * */
    static{
        for(int i=0; i< servers.length; i++){
            nodeMap.put(getHash(servers[i]), servers[i]);
        }
        System.out.println("Hash環初始化完成!");
    }
    
     /**
     * 經典的Time33 hash算法
     * */
    public static int getHash(String key) {
        if(StringUtils.isEmpty(key)) 
            return 0;
        try{
            MessageDigest digest = MessageDigest.getInstance("MD5");
            key = new String(digest.digest(key.getBytes()));
        }catch(NoSuchAlgorithmException e){
            e.printStackTrace();
        }
        int hash = 5381;
        for (int i = 0; i < key.length(); i++) {
            int cc = key.charAt(i);
            hash += (hash << 5) + cc;
        }
        return hash<0 ? -hash : hash;
    }
    
    /**
     * 緩存路由算法
     * */
    public static String getServer(String key){
        int hash = getHash(key);
        //得到大于該Hash值的所有Map
        SortedMap<Integer, String> subMap = nodeMap.tailMap(hash);
        if(subMap.isEmpty()){
            int index = nodeMap.firstKey();
            System.out.printf("%s被路由到節點[%s]\n", key, nodeMap.get(index));
            return nodeMap.get(index);
        }else{
            int index = subMap.firstKey();
            System.out.printf("%s被路由到節點[%s]\n", key, nodeMap.get(index));
            return nodeMap.get(index);
        }      
    }
    
    /**
     * 使用UUID模拟随機key
     * */
    public static void main(String[] args) {
        for(int i=0; i<20; i++){
            String str = UUID.randomUUID().toString();
            getServer(str);
        }
    }  
}
           

  首先，針對平衡性，我們需要選擇一個好的Hash函數，我們選擇的Hash算法是業界内比較出名的Time33 Hash算法，這個你們可以百度一下。但是Time33 Hash算法有一個弊端，那就是對于兩個key差不多的字元串來說，他們生成的Hash值很接近，是以我們的解決辦法就是在生成Hash值之前先用MD5算法取一次資訊指紋。

  nodeMap是用來儲存伺服器節點資訊的SortedMap（key是hash值，value是伺服器節點資訊）; servers是伺服器的配置資訊；使用static靜态代碼塊初始化nodeMap儲存節點資訊。

  緩存路由算法是核心代碼，大概思想是先計算key的hash值，然後用hash值找到nodeMap中的所有鍵值大于該hash值的鍵值對，如果找到，取鍵值對最小的那個鍵值對的值作為路由結果；如果沒有找到鍵值對的鍵大于該hash值的鍵值對，那麼就取nodeMap裡鍵值對的鍵最小的那個值作為路由結果。

  接下來，我們使用UUID生成随機字元串測試一下吧，測試結果如下：

  但是這種不帶虛拟節點的路由算法有個問題，在增減機器時會使舊的資料大量“失效”，也稱為命中率下降。

  于是我們選擇把一個機器分為很多個虛拟節點，并且使這些虛拟節點交叉的分散在一個hash環上，經過改良後的代碼如下：

import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.SortedMap;
import java.util.TreeMap;
import java.util.UUID;
import org.apache.commons.lang.StringUtils;

public class ConsistentHashWithVirtualNode {
    /**
     * 虛拟節點資訊
     * key:hash值
     * value:真實節點+"&"+序号
     * */
    private static SortedMap<Integer, String> virtualNodeMap = new TreeMap<>();
    //單機虛拟節點
    private static final int VIRTUAL_NODE_NUM = 5;
    //伺服器配置資訊(可配置)
    private static String[] servers = {"192.168.56.120:6379",
                                       "192.168.56.121:6379", 
                                       "192.168.56.122:6379",
                                       "192.168.56.123:6379", 
                                       "192.168.56.124:6379"};
    
    /**
     * 初始化
     * */
    static{
        for(int i=0; i< servers.length; i++){
            for(int j=0; j<VIRTUAL_NODE_NUM; j++){
                String virtualNodeName = servers[i] + "&" + j;
                virtualNodeMap.put(getHash(virtualNodeName), virtualNodeName);
            }
        }
        System.out.println("帶虛拟節點的Hash環初始化完成!");
        
    }
    
     /**
     * 經典的Time33 hash算法
     * */
    public static int getHash(String key) {
        if(StringUtils.isEmpty(key)) 
            return 0;
        try{
            MessageDigest digest = MessageDigest.getInstance("MD5");
            key = new String(digest.digest(key.getBytes()));
        }catch(NoSuchAlgorithmException e){
            e.printStackTrace();
        }
        int hash = 5381;
        for (int i = 0; i < key.length(); i++) {
            int cc = key.charAt(i);
            hash += (hash << 5) + cc;
        }
        return hash<0 ? -hash : hash;
    }
    
    /**
     * 緩存路由算法
     * */
    public static String getServer(String key){
        int hash = getHash(key);
        //得到大于該Hash值的所有Map
        SortedMap<Integer, String> subMap = virtualNodeMap.tailMap(hash);
        if(subMap.isEmpty()){
            int index = virtualNodeMap.firstKey();
            System.out.printf("%s被路由到虛拟節點[%s]真實節點[%s]\n", key, virtualNodeMap.get(index), 
                    virtualNodeMap.get(index).substring(0, virtualNodeMap.get(index).indexOf("&")));
            return virtualNodeMap.get(index).substring(0, virtualNodeMap.get(index).indexOf("&"));
        }else{
            int index = subMap.firstKey();
            System.out.printf("%s被路由到虛拟節點[%s]真實節點[%s]\n", key, virtualNodeMap.get(index), 
                    virtualNodeMap.get(index).substring(0, virtualNodeMap.get(index).indexOf("&")));
            return virtualNodeMap.get(index).substring(0, virtualNodeMap.get(index).indexOf("&"));
        }      
    }
    
    /**
     * 使用UUID模拟随機key
     * */
    public static void main(String[] args) {
        for(int i=0; i<20; i++){
            String str = UUID.randomUUID().toString();
            getServer(str);
        }
    }
    
}
           

  虛拟節點的大緻思想之這樣的，使用真實節點+"&"+序号（序号的範圍是0到單台伺服器所需的虛拟節點個數VIRTUAL_NODE_NUM）作為虛拟節點的值，核心代碼如上面截圖所示。

  接下來，我們還是使用UUID生成随機字元串測試一下吧，測試結果如下：

  好的，大功告成，以上就是關于一緻性Hash路由算法的全部内容。PS：以上代碼有删減，僅提取了其中的核心代碼。如果喜歡我的内容的話，歡迎轉發，謝謝。

  歡迎大家關注我的微信公衆号"Java架構師養成記"，不定期分享各類面試題、采坑經曆。