場景

最近要在應(yīng)用中做一層內(nèi)存緩存來加快系統(tǒng)的響應(yīng)匕荸。但是由于數(shù)據(jù)量較大，單臺Server無法Load全量數(shù)據(jù)篱竭，所以考慮使用哈希的方式進行分片存儲在Server的內(nèi)存中坑傅，接入消息隊列進行內(nèi)存數(shù)據(jù)的淘汰脚牍。

原系統(tǒng)調(diào)用關(guān)系簡化圖如下：

系統(tǒng)調(diào)用圖

無論應(yīng)用服務(wù)一[下面簡稱服務(wù)一]是以何種方式(HTTP/RPC)去請求應(yīng)用服務(wù)二[下面簡稱服務(wù)二].都會經(jīng)過一層負載均衡.而現(xiàn)在我們要做內(nèi)存緩存,實際上就是去自己實現(xiàn)一套負載均衡算法來實現(xiàn)應(yīng)用一對特定的請求key,去訪問特定的應(yīng)用二的機器.

在這里我們忽略跨機房,權(quán)重等問題.只考慮選定目標(biāo)主機的策略,即哈希函數(shù).在分布式緩存中,考量一個哈希函數(shù)是否優(yōu)秀,通常可以用三個指標(biāo)來確定:

1. 平衡性(Balance)：緩存機器使用率越高越好
2. 單調(diào)性(Monotonicity)：上線/下線機器對緩存命中率的影響越小越好
3. 分散性(Spread)：一個緩存key,存在于機器中的數(shù)量越少越好.(>=1)

接下來,我們看一下常見的兩種哈希函數(shù).在這個場景下的表現(xiàn).

簡單哈希

假定有十臺Server,我們給每臺Server編號0~9.通過對請求key進行哈希,隨后余10,得到對應(yīng)的數(shù),即為對應(yīng)Server的編號.抽象成公式:

H = hash(key) % 10

這種方式的哈希函數(shù),在平衡性(十臺server全部用上),分散性(每個key對應(yīng)一臺機器)上都很優(yōu)秀,但是在單調(diào)性上,卻表現(xiàn)不佳.下面通過一個demo程序,來看一下.

public class Demo {

    public static void main(String[] args) {
        testAfterAddOneServerHitRate();
    }

    public static void testAfterAddOneServerHitRate() {
        List<String> serverList = Lists.newArrayList("192.168.1.1", 
                "192.168.1.2", "192.168.1.3",
                "192.168.1.4", "192.168.1.5", "192.168.1.6", "192.168.1.7",
                "192.168.1.8", "192.168.1.9", "192.168.1.10");
        // serverList多了一臺之后.
        serverList.add("192.168.1.11");
        Map<String, Integer> serverHitCount = new HashMap<>(10);
        Map<String, Integer> serverMissCount = new HashMap<>(10);
        //假定哈希空間為0~2^31-1
        for (int i = 0; i < Integer.MAX_VALUE; i++) {
            String targetServerBefore = serverList.get(i % 10);
            String targetServerNow = serverList.get(i % 11);
            if (targetServerNow.equals(targetServerBefore)) {
                plusOneToMapKey(serverHitCount, targetServerNow);
            } else if (!"192.168.1.11".equals(targetServerNow)) {
                plusOneToMapKey(serverMissCount, targetServerNow);
            }
        }

        System.out.println(serverHitCount);
        System.out.println(serverMissCount);
    }

    private static void plusOneToMapKey(Map<String, Integer> map, String key) {
        if (map.containsKey(key)) {
            map.put(key, map.get(key) + 1);
        } else {
            map.put(key, 1);
        }
    }
}

執(zhí)行結(jié)果為:

當(dāng)新增一臺機器后,原server0~server9上的90%的緩存已經(jīng)不能路由到原來緩存這個數(shù)據(jù)的機器.所以這種取模的哈希算法,雖然簡單,但是在分布式系統(tǒng)中,上線下線機器是在所難免的.在這種情況下緩存的大量失效是無法接收的.

一致性哈希

一致性哈希算法設(shè)計思路:

1. 將整個哈希值空間組織成一個虛擬的圓環(huán).假定某哈希函數(shù)的值空間為0~2^31-1,Java中int類型的正值范圍.整個哈希環(huán)如下.

   
   

2. 我們將服務(wù)器的列表,通過哈希函數(shù),哈希到圓環(huán)上.

   
   

3. 我們將緩存key,也同樣映射到緩存空間

   
   

命中規(guī)則

緩存key,順時針移動,找到的第一臺服務(wù)器,就是該緩存key對應(yīng)緩存存在的機器.

指標(biāo)分析

1. 平衡性: 由于在一個環(huán)上,所有的機器都會存儲一定量的緩存數(shù)據(jù)
2. 單調(diào)性: 當(dāng)有Server02下線的時候,只有Server01和Server02中間的緩存數(shù)據(jù)會遷移到Server03,而其他緩存數(shù)據(jù)并不會沒任何移動.單調(diào)性良好.
3. 分散性: 每個緩存key都會存儲在一臺機器中.

存在問題

當(dāng)我們的服務(wù)器較少的時候,可能會這種情況:

可能大量的緩存,會命中到Server02.因為Server01~02之間的空隙很大.這樣實際上三臺機器的負載就會很不均勻.至于有多不均勻,我們可以運行一段Demo程序來看看結(jié)果.

全部采用實節(jié)點的Demo

public class Demo {

    public static void main(String[] args) {
        pureServerList();
    }

    public static void pureServerList(){
        Hash hash = new MurmurHash();
        List<String> serverList = Lists.newArrayList("192.168.1.1", "192.168.1.2", "102.168.1.3");
        TreeMap<Integer, String> hashCircle = new TreeMap<>();
        serverList.forEach(item -> hashCircle.put(hash.hash(item) & 0x7fffffff, item));
        Map<String, Integer> counter = Maps.newHashMap();
        for (int i = 0; i < Integer.MAX_VALUE ; i++) {
            Integer serverHash = hashCircle.ceilingKey(i);
            if (serverHash == null) {
                serverHash = hashCircle.firstKey();
            }
            String server = (hashCircle.get(serverHash));
            if (counter.containsKey(server)) {
                counter.put(server, counter.get(server) + 1);
            } else {
                counter.put(server, 1);
            }
        }
        System.out.println(counter);
    }
}

代碼說明:

1. 由于要找到比指定哈希值大的第一個key,則使用TreeMap(紅黑樹)這種結(jié)構(gòu),實現(xiàn)簡單,并且效率良好.
2. 對哈希值進行了 & 0x7fffffff 操作,是因為哈希值可能為負.而我們的哈希空間,設(shè)定為大于等于0

程序運行結(jié)果:

由結(jié)果我們可以看到三臺機器,實際上有一臺能映射到的機會非常少.為了解決這個問題,我們可以通過引入虛擬節(jié)點來進行解決伍玖。

虛擬節(jié)點的引入

虛擬節(jié)點.故名思議.我們可以為我們的每個服務(wù)器模擬多個節(jié)點,使得更多的機器可以落在哈希環(huán)上.通過這種方式來讓我們的key,可以落的均勻.最簡單的辦法.就是在ip后面添加#00,#01這種方式.如下圖.

下面我們再寫一段程序,看看引入虛擬節(jié)點后的key的分布情況.

public class Demo {

    public static void main(String[] args) {
        virtualServerList();
    }

    public static void virtualServerList(){
        Hash hash = new MurmurHash();
        List<String> serverList = Lists.newArrayList("192.168.1.1", "192.168.1.2", "102.168.1.3");
        List<String> vServerList = Lists.newArrayList();
        for (String str : serverList) {
            for (int i = 0; i < 1024; i++) {
                vServerList.add(((str + "#" + i)));
            }
        }
        TreeMap<Integer, String> hashCircle = new TreeMap<>();
        vServerList.forEach(item -> hashCircle.put(hash.hash(item) & 0x7fffffff, item));
        Map<String, Integer> counter = Maps.newHashMap();
        for (int i = 0; i < Integer.MAX_VALUE ; i++) {
            Integer serverHash = hashCircle.ceilingKey(i);
            if (serverHash == null) {
                serverHash = hashCircle.firstKey();
            }
            String server = (hashCircle.get(serverHash)).split("#")[0];
            if (counter.containsKey(server)) {
                counter.put(server, counter.get(server) + 1);
            } else {
                counter.put(server, 1);
            }
        }
        System.out.println(counter);
    }
}

代碼說明:

1. 每個節(jié)點,分成1024個虛擬節(jié)點

程序運行結(jié)果:

通過使用虛擬節(jié)點這種方式,我們的key已經(jīng)可以均勻的落在各臺機器上了.

總結(jié)

目前一致性哈希基本成為了分布式系統(tǒng)組件的標(biāo)準(zhǔn)配置剿吻，例如Memcached的各種客戶端都提供內(nèi)置的一致性哈希支持,值得我們學(xué)習(xí)與使用.

參考資料

《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》
《一致性哈希算法及其在分布式系統(tǒng)中的應(yīng)用》
《每天進步一點點——五分鐘理解一致性哈希算法(consistent hashing)》