一致性hash算法有哪些重要性

本篇內(nèi)容介紹了“一致性hash算法有哪些重要性”的有關(guān)知識(shí)，在實(shí)際案例的操作過(guò)程中，不少人都會(huì)遇到這樣的困境，接下來(lái)就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

一致性hash算法是個(gè)啥？相信很多老牌程序員都不太清楚，為什么？因?yàn)樗饕糜?a title="負(fù)載均衡" target="_blank" href="http://kemok4.com/slb/">負(fù)載均衡，解決數(shù)據(jù)相對(duì)一致性問(wèn)題的。一般公司搞個(gè)哈希、輪詢、權(quán)重都了不得了，用什么一致性哈希算法，但一致性哈希算法是個(gè)啥，有點(diǎn)追求的產(chǎn)品經(jīng)理還是要了解的。

nginx里面有個(gè)哈希算法，這個(gè)哈希算法的使用場(chǎng)景大概是，我的某一個(gè)客戶端要一直連到特定后端服務(wù)器上，不許變，變了就會(huì)出錯(cuò)，如此可以解決我們實(shí)際場(chǎng)景中一些問(wèn)題，比如：session問(wèn)題，redis緩存數(shù)據(jù)存儲(chǔ)等等。

如果用于緩存場(chǎng)景，普通哈希算法邏輯大概是這樣的，如果有10臺(tái)緩存服務(wù)器，客戶端 1數(shù)據(jù)存儲(chǔ)在1節(jié)點(diǎn)（1模除10）客戶端2數(shù)據(jù)存儲(chǔ)在2節(jié)點(diǎn)上......客戶端11存儲(chǔ)在1節(jié)點(diǎn)上，以此類推。但忽然有一天，有一臺(tái)機(jī)器老化了，你的總服務(wù)器個(gè)數(shù)變成了9，可想而知，再次做取模運(yùn)算，可能原來(lái)的數(shù)據(jù)已經(jīng)不在，可能你會(huì)說(shuō)，沒(méi)關(guān)系啊，數(shù)據(jù)庫(kù)里面還有一份呢？重新加載下就Ok啦，是的（沒(méi)見(jiàn)識(shí)），如果對(duì)于上億級(jí)流量場(chǎng)景，可能就會(huì)發(fā)生緩存擊穿問(wèn)題，導(dǎo)致一連串的崩潰。

這時(shí)就輪到一致性hash算法上場(chǎng)了，其實(shí)一致性hash算法思想和實(shí)現(xiàn)非常簡(jiǎn)單，每每想到一致性哈希算法，大家都應(yīng)該想到這個(gè)環(huán)（不知道怎么回事，每當(dāng)我看到這個(gè)環(huán)，總是想到張衡的地震儀）。

實(shí)現(xiàn)該算法的大致思路如下：

1、構(gòu)造一個(gè)哈希環(huán)

2、把服務(wù)器對(duì)應(yīng)的節(jié)點(diǎn)映射到哈希環(huán)上

3、客戶端請(qǐng)求，順時(shí)針找到該哈希環(huán)上的服務(wù)器節(jié)點(diǎn)

如此，足矣！這么簡(jiǎn)單的邏輯，用代碼實(shí)現(xiàn)下吧，首先需要構(gòu)造一個(gè)哈希環(huán)，哈希環(huán)看起來(lái)比較抽象，如何實(shí)現(xiàn)？找下規(guī)律發(fā)現(xiàn)哈希環(huán)上放的是一個(gè)KV數(shù)據(jù)對(duì)，key是哈希，value是對(duì)應(yīng)的服務(wù)器，而且是順序的，自然就想到了SortedMap。

SortedMap<Integer, String> sortedMap = new TreeMap<Integer, String>(); 但哈希函數(shù)如何實(shí)現(xiàn)呢？這個(gè)就比較有意思了，這里不過(guò)多介紹哈希函數(shù)的生成過(guò)程，反正你應(yīng)該選擇一個(gè)分布相對(duì)均勻、區(qū)間盡可能大的哈希函數(shù)，建議采用ketama或者FNV1_32，F(xiàn)NV代碼實(shí)現(xiàn)如下：

        final int p = 16777619;
        int hash = (int) 2166136261L;
        for (int i = 0; i < str.length(); i++)
            hash = (hash ^ str.charAt(i)) * p;
        hash += hash << 13;
        hash ^= hash >> 7;
        hash += hash << 3;
        hash ^= hash >> 17;
        hash += hash << 5;

        // 如果算出來(lái)的值為負(fù)數(shù)則取其絕對(duì)值  
        if (hash < 0)
            hash = Math.abs(hash);
        return hash;
    }

那么現(xiàn)在如何把服務(wù)器節(jié)點(diǎn)映射哈希環(huán)中呢？且看如下代碼實(shí)現(xiàn)：

 for (int i = 0; i < servers.length; i++) {
            int hash = FNVHash(servers[i]);
            sortedMap.put(hash, servers[i]);
}```

當(dāng)然客戶端請(qǐng)求過(guò)來(lái)只需要計(jì)算客戶端的哈希值，順時(shí)針旋轉(zhuǎn)找到對(duì)應(yīng)的服務(wù)端節(jié)點(diǎn)即可，如下為代碼實(shí)現(xiàn)：

```private static String getServer(String key) {
    //得到該key的hash值  
    int hash = FNVHash(key);
    //得到大于該Hash值的所有Map  
    SortedMap<Integer, String> subMap = sortedMap.tailMap(hash);
    if (subMap.isEmpty()) {
        //如果沒(méi)有比該key的hash值大的，則從第一個(gè)node開(kāi)始  
        Integer i = sortedMap.firstKey();
        //返回對(duì)應(yīng)的服務(wù)器  
        return sortedMap.get(i);
    } else {
        //第一個(gè)Key就是順時(shí)針過(guò)去離node最近的那個(gè)結(jié)點(diǎn)  
        Integer i = subMap.firstKey();
        //返回對(duì)應(yīng)的服務(wù)器  
        return subMap.get(i);
    }
}

總結(jié)來(lái)說(shuō)，假設(shè)有k個(gè)節(jié)點(diǎn)，數(shù)據(jù)的取值范圍就是[0, n]，我們把[0,n]劃分為m個(gè)區(qū)間，m遠(yuǎn)遠(yuǎn)大于k，那么每個(gè)機(jī)器就負(fù)責(zé)m/k個(gè)區(qū)間。這樣如果有將幾個(gè)小區(qū)間的數(shù)據(jù)遷移到新區(qū)間上，既保證了數(shù)據(jù)的一致性，也保證了數(shù)據(jù)的均衡。簡(jiǎn)單來(lái)說(shuō)，先根據(jù)機(jī)器IP生成哈希值，當(dāng)客戶端數(shù)據(jù)key進(jìn)來(lái)時(shí)，進(jìn)行哈希操作，落到圓環(huán)中的某一點(diǎn)，順時(shí)針旋轉(zhuǎn)落到第一個(gè)節(jié)點(diǎn)上。

這個(gè)時(shí)候你可能會(huì)發(fā)現(xiàn)一個(gè)問(wèn)題，如果說(shuō)節(jié)點(diǎn)過(guò)于稀疏，那么很可能所有數(shù)據(jù)都落到一個(gè)節(jié)點(diǎn)上，導(dǎo)致數(shù)據(jù)傾斜，這個(gè)時(shí)候可以考慮虛擬節(jié)點(diǎn)。虛擬節(jié)點(diǎn)的添加實(shí)現(xiàn)也非常簡(jiǎn)單，大致思路是構(gòu)造哈希環(huán)的過(guò)程中使用虛擬節(jié)點(diǎn)，取出虛擬節(jié)點(diǎn)，最后找到對(duì)應(yīng)的真實(shí)節(jié)點(diǎn)即可。

“一致性hash算法有哪些重要性”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！