深入理解一致性 Hash 和虛擬節點

    在分佈式系統中架構中我們經常提到一致性哈希算法，那麼什麼是一致性哈希算法，爲什麼需要一致性哈希算法呢？

1、爲什麼需要一致性哈希算法

    假設現在有三臺緩存服務器（緩存服務器 A、緩存服務器 B、緩存服務器 C），現在將數據預熱到這三臺服務器，我們可以使用負載均衡的方法將數據緩存到服務器上，如下圖所示：

    通過負載均衡的方式可以把數據均勻的分發到三臺緩存服務器上，在讀取緩存的熱點數據就存在一定的困難（因爲不清楚數據被緩存在那臺服務器上），讀取數據的過程如下所示：

    通過輪詢緩存服務器的方式讀取緩存的熱點數據，此時效率就非常的低了，接口的響應時間也會變長，從而導致用戶的體驗非常差。

    負載均衡的方案致命的缺點是無法快速的定位數據在哪臺服務器上，導致需要輪詢服務器來獲取數據，爲了解決這個痛點便提出使用 Hash 算法。Hash 算法的預熱數據的流程如下圖：

    將數據的 key 計算一個 hash 值，然後將這個 hash 值和服務器的臺數取模，取模之後的結果就決定當前的數據存放在哪臺服務器上。獲取數據的流程如下：

    讀取數據的時候，將數據 key 同樣方式獲取 hash 值，然後將 hash 值與服務器的臺數取模來定位數據在哪臺服務器上。但是 hash 法也存在一個嚴重的缺陷，假設現在增加 / 減少服務器數據量，如下圖所示：

    我們繼續使用：hash（key）% 服務器數量，來定位數據在哪臺服務器就存在問題了，因爲服務器數量變化導致原先數據定位不準，如下所示：

    假設現在有大量的請求打進來，由於命中緩存服務上沒有數據，請求都落到了資源服務器上，由於資源服務器瞬間壓力過大可能會導致服務崩潰。

    hash 隨着服務器的數量變化（增加或減少），定位服務上的緩存的數據位置也會變動，就會導致無法獲取數據的問題。爲了解決這個問題便提出了一致性 hash 算法。

2、一致性 hash 和虛擬節點

    一致性 hash 算法是對 2^32 方取模，從 0-2^32 方計數形成一個圓環，我們稱這個圓環爲 hash 環。

    通過 hash(服務器的 ip) % 2^32 = X；通過這個 X 值可以定位服務器在圓環上的位置。

    如何確定數據存放在哪個服務器上呢？如下圖所示：

    如上的數據 A，我們可以使用 hash(數據 A) % 2^32 = LA；通過 LA 可以定位數據 A 在圓環上的位置，然後順時針方便找距離數據 A 最近的服務器，發現是服務器 A，那麼我們將數據 A 存放到服務器 A 上。同理數據 B 也是存放在服務器上 A 上。

    讀取數據也是同樣按照 hash 算法取模的方式來定位服務器，通過這樣的方式可以很快地定位數據在哪臺服務器上。如下所示：

    假設現在服務器 C 下線了，如下所示：

    此時數據 A 定位是沒有問題，數據 C 從原先的服務器 C 上定位到服務器 A 上，數據 C 是無法獲取到的。換句話講，雖然服務器 C 下線了，但是隻是部分數據異常，不會使得整個服務集羣數據錯亂，數據異常的部分如下所示：

    假設現在增加了一臺機器 D，那麼也只會導致部分數據出現錯亂，如下圖所示：

    此時我們只需要將錯亂的這一部分數據遷移到服務器 D 上可以實現數據的同步了。理想狀態下，一致性 hash 是很完美的，但是在極端的情況下由於離散型差的問題導致服務器都集中分佈在一起，如下圖所示：

此時數據又剛好落在服務器 C 和服務器 A 之間的區域上，如下圖所示：

    這樣就導致所有的數據壓力都到了服務器 A 上，服務器 B 和服務器 C 就是一個擺設了作用了。如果服務器 A 掛了，那麼整個緩存就失效了，這個就是 hash 環的傾斜問題。爲了解決 hash 環傾斜問題，於是便引入了虛擬節點，也就是把真實的服務器通過虛擬化的方式複製一些節點出來成爲虛擬虛擬節點。如下圖所示：

    通過虛擬節點的加入就不會導致所有的數據都到一臺機器中，同時虛擬節點越多，緩存數據越均勻。

總結：

（1）一致性 hash 常用於負載均衡、分佈式緩存分區、數據庫分庫分表等場景。

（2）爲防止服務器上的數據傾斜問題，通常增加虛擬節點的方式來讓數據更加均勻的分佈在機器上。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/FkO6oNInmHA_IzysZcMVkg