9張圖，帶你了解一致性哈希原理

假設我們現在做一個簡單的檔案快取服務，由于檔案數過多，我們先使用3臺機器用來存盤檔案，

為了由檔案名（假設檔案名稱不重復）能得到存盤的機器，考慮先對檔案名做hash運算，接著對3取余，得到的余數即為所在機器的編號，

這套系統運行了很久，后來檔案數量慢慢增多，3臺機器存不下了，現在我們考慮擴充到4臺，

這個時候，我們的演算法更新為hash(檔案名)%5，

那么使用該演算法獲取abc.txt檔案所在的快取機器時，在其hash值為10的時候，將會映射到0號機器上，而之前是存盤在1號機器上的，這個時候就會重新將檔案存盤到0號機器上，或者將1號機器上的檔案遷移到0號機器上，

因此，增加了兩臺機器后，導致了快取失效，

我們使用代碼來大致確定一下快取失效的比例：

    public static void main(String[] args) {
        //快取失效計數
        int count = 0;
        //假設一共有10000份檔案
        for (int i = 0; i < 10000; i++) {
            //檔案名稱
            String fileName = "file#" + i;
            int hashCode = fileName.hashCode();
            //原來的存盤位置
            int oldSite = hashCode % 3;
            //增加兩臺機器后，現在的存盤位置
            int newSite = hashCode % 5;

            if (oldSite != newSite) {
                count++;
            }
        }

        System.out.println(count);
    }

運行后發現，超過80%的快取都會失效，

也就是說，無論是增加機器還是減少機器，都會使得快取大面積的失效，這是我們不愿意見到的結果，那么有沒有一種新的演算法呢？

一致性哈希演算法，就應運而生了，該演算法可以使得增級訓器時，大幅度減少失效的快取數量，

首先這里有個圓，你可以看做是從0到2^32-1頭尾相連的環，

我們先對一臺機器的ip做哈希運算，再對2^32取模，即hash(ip)%2^32，得到了數字肯定在環上，

假設我們使用的哈希演算法得到的哈希值回傳值是int型別，則本身相當于已經取過模，

因此我們標記出三臺機器在環上的位置

這個時候，需要將檔案映射到環上，使用一樣的哈希函式，即hash(檔案名)，假設這里有4個檔案，我們在環上標記出檔案的位置，

那現在怎么確定檔案在哪臺機器上存盤呢？

很簡單，從當前檔案開始，順時針找到第一個機器，即為檔案的存盤位置，

假設這個時候機器2宕機，我們將機器2從環上移除，觀察一下檔案3的變化

當機器2宕機時，檔案3將重新指向機器3，

也就是說，當機器2宕機時，原本映射到機器1與機器2之間位置的檔案，將會被重新映射到機器3，

因此，一致性哈希能夠大幅度降低快取失敗的范圍，不至于“牽一發而動全身”，

不知道大家有沒有看出來，在上圖中，幾臺機器在環上的分布比較均勻，這是一種非常理想的情況，

然而現實可能并不是這樣，假設3臺機器經過映射后，彼此之間非常靠近，

當機器數量特別少的時候，經過映射后，節點在環上分布不均勻，導致大部分檔案全部落在同一臺機器上，也就是存在資料傾斜問題，

如圖所示，4個檔案全部存盤在了機器1上，倘若有一天，機器1承載不住大量的檔案訪問掛了，這些檔案將會立即轉移到機器2上，機器2同樣也會承載不住，最后就會造成整個系統的連鎖崩潰，

既然問題的根本在于機器數量少，那我們可以增加機器啊！

但機器是一種實際存在的物理資源，不可能說增加就增加，老板也不讓啊！

這個時候，我們可以復制現有的物理機器，形成一些虛擬節點，通過以物理節點的ip加上后綴序號來實作，

當虛擬節點以同樣的演算法映射到環上之后，檔案1最終將會落到機器2上，

理論上，虛擬節點越多，越能做到相對的均勻分布，

下面以代碼的形式，來驗證一下，

public class Main {

    //真實節點
    private static final String[] ipArray = new String[]{"192.168.1.1", "192.168.1.2", "192.168.1.3", "192.168.1.4"};
    //哈希環(哈希值->真實節點ip)
    private static final TreeMap<Long, String> circle = new TreeMap<>();

    //指定倍數初始化哈希環
    private static void initCircle(int mul) {
        //映射真實節點
        for (String ip : ipArray) {
            circle.put(hash(ip), ip);
            //按照倍數映射虛擬節點
            for (int i = 1; i <= mul; i++) {
                String virtual = ip + "#" + i;
                circle.put(hash(virtual), ip);
            }
        }
    }

    //獲取指定檔案存盤的機器ip
    private static String getIpByFileName(String fileName) {
        long hash = hash(fileName);
        Long higherKey = circle.higherKey(hash);
        if (higherKey == null) {
            //回傳哈希環中的第一個ip
            return circle.get(circle.firstKey());
        }
        //回傳比檔案名稱的哈希值大的最小ip
        return circle.get(higherKey);
    }

    //統計落在每個節點上的檔案總數(ip->檔案總數)
    private static Map<String, Long> count(long fileCount) {
        //(ip,檔案總數)
        Map<String, Long> map = new HashMap<>();

        for (long i = 1; i <= fileCount; i++) {
            String ip = getIpByFileName("file#" + i);
            Long ipCount = map.get(ip);
            map.put(ip, (ipCount == null ? 0 : ipCount) + 1);
        }

        return map;
    }

    //列印各個ip存盤的檔案數占總數的百分比
    private static void print(int fileCount) {
        Map<String, Long> map = count(fileCount);

        for (String ip : ipArray) {
            Long ipCountL = map.get(ip);
            long ipCount = ipCountL == null ? 0 : ipCountL;

            double result = ipCount * 100 / (double) fileCount;
            //保留一位小數
            String format = String.format("%.1f", result);
            System.out.println(ip + ":" + format + "%");
        }
    }

    // 32位的 Fowler-Noll-Vo 哈希演算法
    // https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function
    private static Long hash(String key) {
        final int p = 16777619;
        long hash = 2166136261L;
        for (int idx = 0, num = key.length(); idx < num; ++idx) {
            hash = (hash ^ key.charAt(idx)) * p;
        }
        hash += hash << 13;
        hash ^= hash >> 7;
        hash += hash << 3;
        hash ^= hash >> 17;
        hash += hash << 5;

        if (hash < 0) {
            hash = Math.abs(hash);
        }
        return hash;
    }

    public static void main(String[] args) {
        //初始化哈希環
        initCircle(1000000);
        //檔案總數10000個
        print(10000);
    }

}

當倍數為0時：

192.168.1.1:0.0%
192.168.1.2:0.0%
192.168.1.3:100.0%
192.168.1.4:0.0%

相當于沒有虛擬節點，可以看到極度不均勻，傾斜嚴重，

當倍數為100時：

192.168.1.1:28.4%
192.168.1.2:22.4%
192.168.1.3:34.6%
192.168.1.4:14.6%

傾斜改善了！但仍然不滿足

當倍數為10000時：

192.168.1.1:24.6%
192.168.1.2:25.9%
192.168.1.3:23.3%
192.168.1.4:26.3%

基本上算是比較均勻了

大膽點，我們把倍數調到1百萬，檔案數也調到1百萬

192.168.1.1:25.0%
192.168.1.2:24.9%
192.168.1.3:25.0%
192.168.1.4:25.1%

可見所有檔案在各個機器上分布得非常均勻！