面試官:Hash一致性算法是如何解決數據傾斜問題的

不多說,有圖有真相

面試官:Hash一致性算法是如何解決數據傾斜問題的

然後來看重點呀,hash一致性算法

簡介

一致性Hash是一種特殊的Hash算法,由於其均衡性、持久性的映射特點,被廣泛的應用於負載均衡領域,如nginx和memcached都採用了一致性Hash來作為集群負載均衡的方案。

本文將介紹一致性Hash的基本思路,並討論其在分佈式緩存集群負載均衡中的應用。同時也會進行相應的代碼測試來驗證其算法特性,並給出和其他負載均衡方案的一些對比。


一致性Hash算法簡介

在瞭解一致性Hash算法之前,先來討論一下Hash本身的特點。普通的Hash函數最大的作用是散列,或者說是將一系列在形式上具有相似性質的數據,打散成隨機的、均勻分佈的數據。

比如,對字符串abc和abcd分別進行md5計算,得到的結果如下:

面試官:Hash一致性算法是如何解決數據傾斜問題的

可以看到,兩個在形式上非常相近的數據經過md5散列後,變成了完全隨機的字符串。負載均衡正是利用這一特性,對於大量隨機的請求或調用,通過一定形式的Hash將他們均勻的散列,從而實現壓力的平均化。(當然,並不是只要使用了Hash就一定能夠獲得均勻的散列,後面會分析這一點。)

舉個例子,如果我們給每個請求生成一個Key,只要使用一個非常簡單的Hash算法Group = Key % N來實現請求的負載均衡,如下:


面試官:Hash一致性算法是如何解決數據傾斜問題的

(如果將Key作為緩存的Key,對應的Group儲存該Key的Value,就可以實現一個分佈式的緩存系統,後文的具體例子都將基於這個場景)

不難發現,這樣的Hash只要集群的數量N發生變化,之前的所有Hash映射就會全部失效。如果集群中的每個機器提供的服務沒有差別,倒不會產生什麼影響,但對於分佈式緩存這樣的系統而言,映射全部失效就意味著之前的緩存全部失效,後果將會是災難性的。

一致性Hash通過構建環狀的Hash空間代替線性Hash空間的方法解決了這個問題,如下圖:

面試官:Hash一致性算法是如何解決數據傾斜問題的

整個Hash空間被構建成一個首尾相接的環,使用一致性Hash時需要進行兩次映射。

第一次,給每個節點(集群)計算Hash,然後記錄它們的Hash值,這就是它們在環上的位置。

第二次,給每個Key計算Hash,然後沿著順時針的方向找到環上的第一個節點,就是該Key儲存對應的集群。

分析一下節點增加和刪除時對負載均衡的影響,如下圖:

面試官:Hash一致性算法是如何解決數據傾斜問題的

可以看到,當節點被刪除時,其餘節點在環上的映射不會發生改變,只是原來打在對應節點上的Key現在會轉移到順時針方向的下一個節點上去。增加一個節點也是同樣的,最終都只有少部分的Key發生了失效。不過發生節點變動後,整體系統的壓力已經不是均衡的了,下文中提到的方法將會解決這個問題。


問題與優化

最基本的一致性Hash算法直接應用於負載均衡系統,效果仍然是不理想的,存在諸多問題,下面就對這些問題進行逐個分析並尋求更好的解決方案。


數據傾斜

如果節點的數量很少,而hash環空間很大(一般是 0 ~ 2^32),直接進行一致性hash上去,大部分情況下節點在環上的位置會很不均勻,擠在某個很小的區域。最終對分佈式緩存造成的影響就是,集群的每個實例上儲存的緩存數據量不一致,會發生嚴重的數據傾斜。


緩存雪崩

如果每個節點在環上只有一個節點,那麼可以想象,當某一集群從環中消失時,它原本所負責的任務將全部交由順時針方向的下一個集群處理。例如,當group0退出時,它原本所負責的緩存將全部交給group1處理。這就意味著group1的訪問壓力會瞬間增大。設想一下,如果group1因為壓力過大而崩潰,那麼更大的壓力又會向group2壓過去,最終服務壓力就像滾雪球一樣越滾越大,最終導致雪崩。


引入虛擬節點

解決上述兩個問題最好的辦法就是擴展整個環上的節點數量,因此我們引入了虛擬節點的概念。一個實際節點將會映射多個虛擬節點,這樣Hash環上的空間分割就會變得均勻。

同時,引入虛擬節點還會使得節點在Hash環上的順序隨機化,這意味著當一個真實節點失效退出後,它原來所承載的壓力將會均勻地分散到其他節點上去。

如下圖:

面試官:Hash一致性算法是如何解決數據傾斜問題的

代碼測試

現在我們嘗試編寫一些測試代碼,來看看一致性hash的實際效果是否符合我們預期。

首先我們需要一個能夠對輸入進行均勻散列的Hash算法,可供選擇的有很多,memcached官方使用了基於md5的KETAMA算法,但這裡處於計算效率的考慮,使用了FNV1_32_HASH算法,如下:

<code>public class HashUtil {
    /**
     * 計算Hash值, 使用FNV1_32_HASH算法
     * @param str
     * @return
     */
    public static int getHash(String str) {
        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;

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

實際使用時可以根據需求調整。

接著需要使用一種數據結構來保存hash環,可以採用的方案有很多種,最簡單的是採用數組或鏈表。但這樣查找的時候需要進行排序,如果節點數量多,速度就可能變得很慢。

針對集群負載均衡狀態讀多寫少的狀態,很容易聯想到使用二叉平衡樹的結構去儲存,實際上可以使用TreeMap(內部實現是紅黑樹)來作為Hash環的儲存結構。

先編寫一個最簡單的,無虛擬節點的Hash環測試:

<code>public class ConsistentHashingWithoutVirtualNode {    /**
     * 集群地址列表
     */    private static String[] groups = {        "192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111",        "192.168.0.3:111", "192.168.0.4:111"    };    /**
     * 用於保存Hash環上的節點
     */    private static SortedMap sortedMap = new TreeMap<>();    /**
     * 初始化,將所有的服務器加入Hash環中
     */    static {        // 使用紅黑樹實現,插入效率比較差,但是查找效率極高        for (String group : groups) {            int hash = HashUtil.getHash(group);            System.out.println("[" + group + "] launched @ " + hash);            sortedMap.put(hash, group);        }    }    /**
     * 計算對應的widget加載在哪個group上
     *
     * @param widgetKey
     * @return
     */    private static String getServer(String widgetKey) {        int hash = HashUtil.getHash(widgetKey);        // 只取出所有大於該hash值的部分而不必遍歷整個Tree        SortedMap subMap = sortedMap.tailMap(hash);        if (subMap == null || subMap.isEmpty()) {            // hash值在最尾部,應該映射到第一個group上            return sortedMap.get(sortedMap.firstKey());        }        return subMap.get(subMap.firstKey());    }    public static void main(String[] args) {        // 生成隨機數進行測試        Map resMap = new HashMap<>();        for (int i = 0; i  {                System.out.println("group " + k + ": " + v + "(" + v/1000.0D +"%)");            }        );    }}/<code>

生成10000個隨機數字進行測試,最終得到的壓力分佈情況如下:

<code>[192.168.0.1:111] launched @ 8518713[192.168.0.2:111] launched @ 1361847097[192.168.0.3:111] launched @ 1171828661[192.168.0.4:111] launched @ 1764547046group 192.168.0.2:111: 8572(8.572%)group 192.168.0.1:111: 18693(18.693%)group 192.168.0.4:111: 17764(17.764%)group 192.168.0.3:111: 27870(27.87%)group 192.168.0.0:111: 27101(27.101%)/<code>

可以看到壓力還是比較不平均的,所以我們繼續,引入虛擬節點:

<code>public class ConsistentHashingWithVirtualNode {    /**
     * 集群地址列表
     */    private static String[] groups = {        "192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111",        "192.168.0.3:111", "192.168.0.4:111"    };    /**
     * 真實集群列表
     */    private static List realGroups = new LinkedList<>();    /**
     * 虛擬節點映射關係
     */    private static SortedMap virtualNodes = new TreeMap<>();    private static final int VIRTUAL_NODE_NUM = 1000;    static {        // 先添加真實節點列表        realGroups.addAll(Arrays.asList(groups));        // 將虛擬節點映射到Hash環上        for (String realGroup: realGroups) {            for (int i = 0; i < VIRTUAL_NODE_NUM; i++) {                String virtualNodeName = getVirtualNodeName(realGroup, i);                int hash = HashUtil.getHash(virtualNodeName);                System.out.println("[" + virtualNodeName + "] launched @ " + hash);                virtualNodes.put(hash, virtualNodeName);            }        }    }    private static String getVirtualNodeName(String realName, int num) {        return realName + "&&VN" + String.valueOf(num);    }    private static String getRealNodeName(String virtualName) {        return virtualName.split("&&")[0];    }    private static String getServer(String widgetKey) {        int hash = HashUtil.getHash(widgetKey);        // 只取出所有大於該hash值的部分而不必遍歷整個Tree        SortedMap subMap = virtualNodes.tailMap(hash);        String virtualNodeName;        if (subMap == null || subMap.isEmpty()) {            // hash值在最尾部,應該映射到第一個group上            virtualNodeName = virtualNodes.get(virtualNodes.firstKey());        }else {            virtualNodeName = subMap.get(subMap.firstKey());        }        return getRealNodeName(virtualNodeName);    }    public static void main(String[] args) {        // 生成隨機數進行測試        Map resMap = new HashMap<>();        for (int i = 0; i  {                System.out.println("group " + k + ": " + v + "(" + v/100000.0D +"%)");            }        );    }}/<code>

這裡真實節點和虛擬節點的映射採用了字符串拼接的方式,這種方式雖然簡單但很有效,memcached官方也是這麼實現的。將虛擬節點的數量設置為1000,重新測試壓力分佈情況,結果如下:

<code>group 192.168.0.2:111: 18354(18.354%)group 192.168.0.1:111: 20062(20.062%)group 192.168.0.4:111: 20749(20.749%)group 192.168.0.3:111: 20116(20.116%)group 192.168.0.0:111: 20719(20.719%)/<code>

可以看到基本已經達到平均分佈了,接著繼續測試刪除和增加節點給整個服務帶來的影響,相關測試代碼如下:

<code>private static void refreshHashCircle() {
    // 當集群變動時,刷新hash環,其餘的集群在hash環上的位置不會發生變動
  virtualNodes.clear();
    for (String realGroup: realGroups) {
      for (int i = 0; i < VIRTUAL_NODE_NUM; i++) {
           String virtualNodeName = getVirtualNodeName(realGroup, i);
            int hash = HashUtil.getHash(virtualNodeName);
            System.out.println("[" + virtualNodeName + "] launched @ " + hash);
            virtualNodes.put(hash, virtualNodeName);
        }
    }
}
private static void addGroup(String identifier) {
  realGroups.add(identifier);
    refreshHashCircle();
}

private static void removeGroup(String identifier) {
    int i = 0;
    for (String group:realGroups) {
      if (group.equals(identifier)) {
          realGroups.remove(i);
        }
        i++;
    }
    refreshHashCircle();
}/<code>

測試刪除一個集群前後的壓力分佈如下:

<code>running the normal test.group 192.168.0.2:111: 19144(19.144%)group 192.168.0.1:111: 20244(20.244%)group 192.168.0.4:111: 20923(20.923%)group 192.168.0.3:111: 19811(19.811%)group 192.168.0.0:111: 19878(19.878%)removed a group, run test again.group 192.168.0.2:111: 23409(23.409%)group 192.168.0.1:111: 25628(25.628%)group 192.168.0.4:111: 25583(25.583%)group 192.168.0.0:111: 25380(25.38%)/<code>

同時計算一下消失的集群上的Key最終如何轉移到其他集群上:

<code>[192.168.0.1:111-192.168.0.4:111] :5255[192.168.0.1:111-192.168.0.3:111] :5090[192.168.0.1:111-192.168.0.2:111] :5069[192.168.0.1:111-192.168.0.0:111] :4938/<code>

可見,刪除集群后,該集群上的壓力均勻地分散給了其他集群,最終整個集群仍處於負載均衡狀態,符合我們的預期,最後看一下添加集群的情況。

壓力分佈:

<code>running the normal test.group 192.168.0.2:111: 18890(18.89%)group 192.168.0.1:111: 20293(20.293%)group 192.168.0.4:111: 21000(21.0%)group 192.168.0.3:111: 19816(19.816%)group 192.168.0.0:111: 20001(20.001%)add a group, run test again.group 192.168.0.2:111: 15524(15.524%)group 192.168.0.7:111: 16928(16.928%)group 192.168.0.1:111: 16888(16.888%)group 192.168.0.4:111: 16965(16.965%)group 192.168.0.3:111: 16768(16.768%)group 192.168.0.0:111: 16927(16.927%)/<code>

壓力轉移:

<code>[192.168.0.0:111-192.168.0.7:111] :3102[192.168.0.4:111-192.168.0.7:111] :4060[192.168.0.2:111-192.168.0.7:111] :3313[192.168.0.1:111-192.168.0.7:111] :3292[192.168.0.3:111-192.168.0.7:111] :3261/<code>

綜上可以得出結論,在引入足夠多的虛擬節點後,一致性hash還是能夠比較完美地滿足負載均衡需要的。

優雅縮擴容

緩存服務器對於性能有著較高的要求,因此我們希望在擴容時新的集群能夠較快的填充好數據並工作。但是從一個集群啟動,到真正加入並可以提供服務之間還存在著不小的時間延遲,要實現更優雅的擴容,我們可以從兩個方面出發:

1. 高頻Key預熱

負載均衡器作為路由層,是可以收集並統計每個緩存Key的訪問頻率的,如果能夠維護一份高頻訪問Key的列表,新的集群在啟動時根據這個列表提前拉取對應Key的緩存值進行預熱,便可以大大減少因為新增集群而導致的Key失效。

具體的設計可以通過緩存來實現,如下:

面試官:Hash一致性算法是如何解決數據傾斜問題的

不過這個方案在實際使用時有一個很大的限制,那就是高頻Key本身的緩存失效時間可能很短,預熱時儲存的Value在實際被訪問到時可能已經被更新或者失效,處理不當會導致出現髒數據,因此實現難度還是有一些大的。

2. 歷史Hash環保留


回顧一致性Hash的擴容,不難發現新增節點後,它所對應的Key在原來的節點還會保留一段時間。因此在擴容的延遲時間段,如果對應的Key緩存在新節點上還沒有被加載,可以去原有的節點上嘗試讀取。

舉例,假設我們原有3個集群,現在要擴展到6個集群,這就意味著原有50%的Key都會失效(被轉移到新節點上),如果我們維護擴容前和擴容後的兩個Hash環,在擴容後的Hash環上找不到Key的儲存時,先轉向擴容前的Hash環尋找一波,如果能夠找到就返回對應的值並將該緩存寫入新的節點上,找不到時再透過緩存,如下圖:

面試官:Hash一致性算法是如何解決數據傾斜問題的


這樣做的缺點是增加了緩存讀取的時間,但相比於直接擊穿緩存而言還是要好很多的。優點則是可以隨意擴容多臺機器,而不會產生大面積的緩存失效。


談完了擴容,再談談縮容。

3. 熔斷機制


縮容後,剩餘各個節點上的訪問壓力都會有所增加,此時如果某個節點因為壓力過大而宕機,就可能會引發連鎖反應。因此作為兜底方案,應當給每個集群設立對應熔斷機制來保護服務的穩定性。


4. 多集群LB的更新延遲


這個問題在縮容時比較嚴重,如果你使用一個集群來作為負載均衡,並使用一個配置服務器比如ConfigServer來推送集群狀態以構建Hash環,那麼在某個集群退出時這個狀態並不一定會被立刻同步到所有的LB上,這就可能會導致一個暫時的調度不一致,如下圖:

面試官:Hash一致性算法是如何解決數據傾斜問題的

如果某臺LB錯誤地將請求打到了已經退出的集群上,就會導致緩存擊穿。解決這個問題主要有以下幾種思路:

緩慢縮容,等到Hash環完全同步後再操作。可以通過監聽退出集群的訪問QPS來實現這一點,等到該集群幾乎沒有QPS時再將其撤下。 - 手動刪除,如果Hash環上對應的節點找不到了,就手動將其從Hash環上刪除,然後重新進行調度,這個方式有一定的風險,對於網絡抖動等異常情況兼容的不是很好。 - 主動拉取和重試,當Hash環上節點失效時,主動從ZK上重新拉取集群狀態來構建新Hash環,在一定次數內可以進行多次重試。

對比:HashSlot

瞭解了一致性Hash算法的特點後,我們也不難發現一些不盡人意的地方:

  • 整個分佈式緩存需要一個路由服務來做負載均衡,存在單點問題(如果路由服務掛了,整個緩存也就涼了)
  • Hash環上的節點非常多或者更新頻繁時,查找性能會比較低下

針對這些問題,Redis在實現自己的分佈式集群方案時,設計了全新的思路:基於P2P結構的HashSlot算法,下面簡單介紹一下:

5. 使用HashSlot

類似於Hash環,Redis Cluster採用HashSlot來實現Key值的均勻分佈和實例的增刪管理。

首先默認分配了16384個Slot(這個大小正好可以使用2kb的空間保存),每個Slot相當於一致性Hash環上的一個節點。接入集群的所有實例將均勻地佔有這些Slot,而最終當我們Set一個Key時,使用CRC16(Key) % 16384來計算出這個Key屬於哪個Slot,並最終映射到對應的實例上去。

那麼當增刪實例時,Slot和實例間的對應要如何進行對應的改動呢?

舉個例子,原本有3個節點A,B,C,那麼一開始創建集群時Slot的覆蓋情況是:

<code>節點A 0-5460
 節點B 5461-10922
 節點C 10923-16383/<code>

現在假設要增加一個節點D,RedisCluster的做法是將之前每臺機器上的一部分Slot移動到D上(注意這個過程也意味著要對節點D寫入的KV儲存),成功接入後Slot的覆蓋情況將變為如下情況:

<code>節點A 1365-5460
 節點B 6827-10922
 節點C 12288-16383
 節點D 0-1364,5461-6826,10923-12287/<code>

同理刪除一個節點,就是將其原來佔有的Slot以及對應的KV儲存均勻地歸還給其他節點。

6. P2P節點尋找


現在我們考慮如何實現去中心化的訪問,也就是說無論訪問集群中的哪個節點,你都能夠拿到想要的數據。其實這有點類似於路由器的路由表,具體說來就是:

每個節點都保存有完整的HashSlot - 節點映射表,也就是說,每個節點都知道自己擁有哪些Slot,以及某個確定的Slot究竟對應著哪個節點。

無論向哪個節點發出尋找Key的請求,該節點都會通過CRC(Key) % 16384計算該Key究竟存在於哪個Slot,並將請求轉發至該Slot所在的節點。

總結一下就是兩個要點:映射表內部轉發,這是通過著名的Gossip協議來實現的。

最後我們可以給出Redis Cluster的系統結構圖,和一致性Hash環還是有著很明顯的區別的:

面試官:Hash一致性算法是如何解決數據傾斜問題的

對比一下,HashSlot + P2P的方案解決了去中心化的問題,同時也提供了更好的動態擴展性。但相比於一致性Hash而言,其結構更加複雜,實現上也更加困難。

而在之前的分析中我們也能看出,一致性Hash方案整體上還是有著不錯的表現的,因此在實際的系統應用中,可以根據開發成本和性能要求合理地選擇最適合的方案。總之,兩者都非常優秀,至於用哪個、怎麼用,就是仁者見仁智者見智的問題了。


分享到:


相關文章: