[[434665]]

假設我們現(xiàn)在做一個簡單的文件緩存服務，由于文件數(shù)過多，我們先使用3臺機器用來存儲文件。

為了由文件名(假設文件名稱不重復)能得到存儲的機器，考慮先對文件名做hash運算，接著對3取余，得到的余數(shù)即為所在機器的編號。

​這套系統(tǒng)運行了很久，后來文件數(shù)量慢慢增多，3臺機器存不下了，現(xiàn)在我們考慮擴充到4臺。

這個時候，我們的算法更新為hash(文件名)%5。

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

因此，增加了兩臺機器后，導致了緩存失效。

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

public static void main(String[] args) { 
      //緩存失效計數(shù) 
      int count = 0; 
      //假設一共有10000份文件 
      for (int i = 0; i < 10000; i++) { 
          //文件名稱 
          String fileName = "file#" + i; 
          int hashCode = fileName.hashCode(); 
          //原來的存儲位置 
          int oldSite = hashCode % 3; 
          //增加兩臺機器后，現(xiàn)在的存儲位置 
          int newSite = hashCode % 5; 
 
          if (oldSite != newSite) { 
              count++; 
          } 
      } 
 
      System.out.println(count); 
  } 

​運行后發(fā)現(xiàn)，超過80%的緩存都會失效。

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

一致性哈希算法，就應運而生了。該算法可以使得增減機器時，大幅度減少失效的緩存數(shù)量。

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

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

假設我們使用的哈希算法得到的哈希值返回值是int類型，則本身相當于已經(jīng)取過模。

因此我們標記出三臺機器在環(huán)上的位置

​這個時候，需要將文件映射到環(huán)上，使用一樣的哈希函數(shù)，即hash(文件名)。假設這里有4個文件，我們在環(huán)上標記出文件的位置。

​那現(xiàn)在怎么確定文件在哪臺機器上存儲呢?

很簡單，從當前文件開始，順時針找到第一個機器，即為文件的存儲位置。

​假設這個時候機器2宕機，我們將機器2從環(huán)上移除，觀察一下文件3的變化

​當機器2宕機時，文件3將重新指向機器3。

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

​因此，一致性哈希能夠大幅度降低緩存失敗的范圍，不至于“牽一發(fā)而動全身”。

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

然而現(xiàn)實可能并不是這樣，假設3臺機器經(jīng)過映射后，彼此之間非?？拷?。

​當機器數(shù)量特別少的時候，經(jīng)過映射后，節(jié)點在環(huán)上分布不均勻，導致大部分文件全部落在同一臺機器上，也就是存在數(shù)據(jù)傾斜問題。

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

既然問題的根本在于機器數(shù)量少，那我們可以增加機器啊!

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

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

​當虛擬節(jié)點以同樣的算法映射到環(huán)上之后，文件1最終將會落到機器2上。

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

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

public class Main { 
 
    //真實節(jié)點 
    private static final String[] ipArray = new String[]{"192.168.1.1", "192.168.1.2", "192.168.1.3", "192.168.1.4"}; 
    //哈希環(huán)(哈希值->真實節(jié)點ip) 
    private static final TreeMap<Long, String> circle = new TreeMap<>(); 
 
    //指定倍數(shù)初始化哈希環(huán) 
    private static void initCircle(int mul) { 
        //映射真實節(jié)點 
        for (String ip : ipArray) { 
            circle.put(hash(ip), ip); 
            //按照倍數(shù)映射虛擬節(jié)點 
            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) { 
            //返回哈希環(huán)中的第一個ip 
            return circle.get(circle.firstKey()); 
        } 
        //返回比文件名稱的哈希值大的最小ip 
        return circle.get(higherKey); 
    } 
 
    //統(tǒng)計落在每個節(jié)點上的文件總數(shù)(ip->文件總數(shù)) 
    private static Map<String, Long> count(long fileCount) { 
        //(ip,文件總數(shù)) 
        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存儲的文件數(shù)占總數(shù)的百分比 
    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; 
            //保留一位小數(shù) 
            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) { 
        //初始化哈希環(huán) 
        initCircle(1000000); 
        //文件總數(shù)10000個 
        print(10000); 
    } 
 
} 

 當倍數(shù)為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% 

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

當倍數(shù)為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% 

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

當倍數(shù)為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% 

 基本上算是比較均勻了

大膽點，我們把倍數(shù)調(diào)到1百萬，文件數(shù)也調(diào)到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% 

  可見所有ip下存儲的文件總數(shù)非常均勻!​