一致性HASH演算法筆記

title: 一致性HASH演算法筆記
comments: true
toc: true
categories:

• 分布式方案
  tags:
• 一致性HASH
• HASH演算法
  date: 2020-12-29 02:09:47

? 散列演算法（Hash Algorithm），又稱哈希演算法，雜湊演算法，是一種從任意檔案中創造小的數字「指紋」的方法，也可以理解為空間映射函式，是從一個非常大的取值空間映射到一個非常小的取值空間，由于不是一對一的映射，Hash 函式轉換后不可逆，意思是不可能通過逆操作和 Hash 值還原出原始的值，在互聯網環境中有非對稱加密、檔案簽名、Hash表尋址演算法等應用，

Hash演算法型別

直接尋址法：按照該值作為三列地址進行查找，

除留余數法（資料取模法）：對該值按照散串列的長度來取余，

處理Hash沖突時的方法：

? 開放尋址法：沖突后向前或者向后尋找空位作為當前地址，

? 再散列法：準備多個散列函式，沖突后使用其他散列函式計算，

? 拉鏈法：沖突后，將沖突的資料放到一個鏈表中，

Hash演算法在分布式環境中的應用

• 請求的負載均衡（如nginx的ip_hash策略）

  Nginx負載均衡的經典應用就是通過ip地址或者sessionid進行計算哈希值，哈希值與服務器數量進行取模運算，得到的值就是當前請求應該被路由到的服務器編號，如此，同一個客戶端ip發送過來的請求就可以路由到同一個目標服務器，實作會話粘滯，

  如果不使用hash演算法，就需要非常維護非常大的映射表，造成記憶體浪費，且服務器上下線后不利于維護，

• 分布式存盤

  比如Redis集群模式下，資料應該存盤在哪個redis應用里呢？通過Hash演算法就可以解決這個問題，

普通HASH演算法帶來的資料遷移問題

? 在普通HASH演算法下，，如果hash表擴容/縮容，所有的資料均需要重新計算一遍來確定尋址位置，在大量資料的環境下，這會帶來很多問題，比如Nginx下的ip_hash負載均衡策略，它的目的是將同一個客戶端的請求路由到同一臺服務器上，當服務器擴容或者縮容時，使用普通hash演算法則使得所有客戶端重新計算路由的服務器編號，大量的客戶端session失效，這在互聯網環境下是難以接受的，

一致性HASH演算法

? 有一條直線，直線開頭和結尾分別定為為1和2的32次方減1，這相當于一個地址，

? 對于這樣一條線，彎過來構成一個圓環形成倍訓，這樣的一個圓環稱為hash環，

? 我們把服務器的ip或者主機名求hash值然后對應到hash環上，那么針對客戶端用戶，也根據它的ip進行hash求值，對應到環上某個位置，然后如何確定一個客戶端路由到哪個服務器處理呢？按照順時針方向找最近的服務器節點，比如服務器A在hash環上對應的值為100，服務器B在hash環上對應的值為200，那么經過hash計算后值為大于100小于200的均路由到服務器B上，

1. 當服務下線時

   ? 會按照順時針將請求路由至下一個服務器，

2. 當服務上線時

   ? 會將當前節點逆時針至上一臺服務器的請求路由至本服務器，

總的來說Hash環按照服務器的數量劃分成了不同的段，每臺服務器負責一段，增減服務器均只影響部分資料，具有良好的容錯性和擴展性，

? 但分段也造成了資料傾斜問題，即負載不均衡的問題，有的服務器器不堪重負，有的服務器資源閑置浪費，這就需要我們盡可能的使服務器分布均衡，當我們的服務器節點較少時，可以采用填充虛擬節點的方式來平衡分段，具體的做法是給每個虛擬節點分配一個真實的物理節點，當請求到虛擬節點時，路由至附帶的真實節點，

一致性HASH演算法的簡單實作

不含虛擬節點

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的哈希值去找出哪?個服務器節點能夠處理（）| tailMap回傳大于等于Key的map
            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));
            }
        }
    }
}

計算結果：

==========>>>>客戶端：10.78.12.3 被路由到服務器：111.20.35.2
==========>>>>客戶端：113.25.63.1 被路由到服務器：123.98.26.3
==========>>>>客戶端：126.12.3.8 被路由到服務器：111.20.35.2

含有虛擬節點

public class ConsistentHashWithVirtual {

    // 定義服務器ip
    public static final String[] TOMCAT_SERVERS = new String[]{"123.111.0.0", "123.101.3.1", "111.20.35.2", "123.98.26.3"};
    // 定義客戶端IP
    public static final String[] CLIENT_IPS = new String[]{"10.78.12.3", "113.25.63.1", "126.12.3.8"};
    // 定義針對每個真實服務器虛擬出來?個節點
    public static final int VIRTAUL_COUNT = 3;

    public static void main(String[] args) {

        //step1 初始化：把服務器節點IP的哈希值對應到哈希環上
        SortedMap<Integer, String> hashServerMap = new TreeMap<>();
        for (String tomcatServer : TOMCAT_SERVERS) {

            // 求出每?個ip的hash值，對應到hash環上，存盤hash值與ip的對應關系
            int serverHash = Math.abs(tomcatServer.hashCode());

            // 存盤hash值與ip的對應關系
            hashServerMap.put(serverHash, tomcatServer);
            // 處理虛擬節點
            for (int i = 0; i < VIRTAUL_COUNT; i++) {
                int virtualHash = Math.abs((tomcatServer + "#" + i).hashCode());
                hashServerMap.put(virtualHash, "----由虛擬節點" + i + "映射過來的請求：" + tomcatServer);
            }
        }

        //step2 針對客戶端IP求出hash值
        for (String client : CLIENT_IPS) {

            int clientHash = Math.abs(client.hashCode());

            //step3 針對客戶端,找到能夠處理當前客戶端請求的服務器（哈希環上順時針最近）
            // 根據客戶端ip的哈希值去找出哪?個服務器節點能夠處理（）| tailMap回傳大于等于Key的map
            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));
            }
        }
    }
}

計算結果：

==========>>>>客戶端：10.78.12.3 被路由到服務器：111.20.35.2
==========>>>>客戶端：113.25.63.1 被路由到服務器：----由虛擬節點2映射過來的請求：111.20.35.2
==========>>>>客戶端：126.12.3.8 被路由到服務器：----由虛擬節點0映射過來的請求：123.101.3.1