借 redis cluster 集群，聊一聊集群中數據分布演算法

• 2019 年 12 月 13 日
• 筆記

Redis Cluster 集群中涉及到了數據分布問題，因為 redis cluster 是多 master 的結構，每個 master 都是可以提供存儲服務的，這就會涉及到數據分布的問題，在新的 redis 版本中採用的是虛擬槽分區技術來解決數據分布的問題，關於什麼是虛擬槽分區技術我們後面會詳細的介紹。在集群中除了虛擬槽分區技術之外，還有幾種數據分布的演算法，比如哈希演算法，一致性哈希演算法，這篇文章我們就來一起聊一聊這幾種數據分布演算法。

因為是集群，所以我們需要一個大前提，在這篇文章中假設 redis cluster 集群中有三台 master，我們需要存儲的數據集為：[{id:1,"name":"1"},{id:2,name:"2"},{id:3,name:"3"},{id:4,name:"4"},{id:5:"name":"5"},{id:6,"name":"6"}]，在這個大前提下，我們來聊一聊集群中的數據分布演算法。

哈希演算法

哈希演算法在分散式架構中應用廣泛，不僅僅是數據存儲，還有負載均衡等應用上有用的比較多，哈希演算法的思想非常簡單，也許你知道 HashMap 的哈希函數，哈希演算法跟 HashMap 一樣，也是通過一個哈希函數得到某一個數字，然後根據數字找到相應的伺服器。哈希演算法的哈希函數比較簡單，一般是根據某個key的值或者key 的哈希值與當前可用的 master節點數取模，根據取模的值獲取具體的伺服器。哈希演算法服務結構模型圖如下圖所示：

用我們前面假設的數據，利用哈希演算法來實驗一把，加深我們對哈希演算法在分散式中的應用的理。我們假設哈希演算法中的哈希函數為「id % master 節點數」，結果為 0 的數據存放到 server1 伺服器上，結果為 1 的數據存放到 server2 伺服器上，結果為 2 的數據存放到 server3 伺服器上。

所以經過哈希演算法之後，id=3、id=6 的數據與 master 節點數取模為 0 （3%3=0,6%3=0），所以這兩個數據會存放到 server1 伺服器 ，以此類推，id=1、id=4 的數據將存放到 server2 伺服器中，id=2、id=5 的數據將存放到 server3 上，這時候伺服器存儲數據如下圖所示：

這就是哈希演算法在分散式中的作用，比較簡單，可以看出只要你哈希函數設計的好，數據在各個伺服器上是比較均勻分布的，但是哈希演算法有一個致命的缺點：擴展性特別的差，比如我們的集群中，伺服器server3 宕機了，這時候集群中可用的機器只有兩台了，這樣哈希函數就變成了id % 2了，這就會導致一個問題，所有的數據需要重新計算，找到新的存儲節點，每次有伺服器宕機或者添加機器時，都需要進行大量的數據遷移，這會使得系統的可用性、穩定性變差。

一致性哈希演算法

一致性哈希演算法可以說是哈希演算法的升級版，解決了哈希演算法擴展性差的問題，一致性哈希演算法跟哈希演算法不一樣，一致性哈希演算法會將伺服器和數據都通過哈希函數映射到一個首尾相連的哈希環上，存儲節點映射可以根據 ip 地址來進行哈希取值，數據映射到哈希環上後按照順時針的方向查找存儲節點，即從數據映射在環上的位置開始，順時針方向找到的第一個存儲節點，那麼他就存儲在這個節點上。

我們使用一致性哈希演算法來存儲我們的數據，我畫了一張圖來模擬一致性哈希演算法可能出現的結果：

我們先來解讀一下這張圖，按照一致性哈希演算法的規則，數據沿著順時針的方向查找數據，那麼 id=4 的數據存放在 server1 伺服器，id=2 的數據存放在伺服器 server2 上，id=3、id=1、id=5、id=6 的數據都存放在伺服器 server3 上，如果你比較敏感的話，也許你就會發現一致性哈希演算法的不足之處， 從圖中可以看出，我們六條數據分布不均勻，並不是每台伺服器存儲 2 條數據，而且差距好像還有點大，這裡我們就要來說一說一致性哈希演算法的缺點：一致性哈希演算法會會造成數據分布不均勻的問題或者叫做數據傾斜問題，就像我們圖中那樣，數據分布不均勻可能會造成某一個節點的負載過大，從而宕機。造成數據分布不均勻有以下兩種情況：

• 第一：哈希函數的原因，經過哈希函數之後伺服器在哈希環上的分布不均勻，伺服器之間的間距不相等，這樣就會導致數據不均勻。
• 第二：某伺服器宕機了，後繼節點就需要承受原本屬於宕機機器的數據，這樣也會造成數據不均勻。

前面我們提到過一致性哈希演算法解決了哈希演算法中擴展性差的問題，這個怎麼理解呢？我們來看看，在一致性哈希演算法中當有存儲節點加入或者退出時，只會影響應該該節點的後繼節點，舉個例子說明一下，例如我們要在伺服器server3 和服務 server2 之間加入了一個伺服器存儲節點 server4，只會對伺服器server3 造成影響，原本存儲到伺服器server3 上的數據有一部分會落入到伺服器 server4 上，對伺服器 server1 和 server2 並沒有任何影響，這樣就不會進行大量的數據遷移，擴展性就變強了。

帶有限負載的一致性哈希演算法

因為一致性哈希演算法的數據分布不均勻的問題，Google 在 2017 年提出了帶有限負載的一致性哈希演算法來解決這個問題，帶有限負載的一致性哈希演算法思想比較簡單，給每個存儲節點設置了一個存儲上限值來控制存儲節點添加或移除造成的數據不均勻，當數據按照一致性哈希演算法找到相應的存儲節點時，要先判斷該存儲節點是否達到了存儲上限；如果已經達到了上限，則需要繼續尋找該存儲節點順時針方向之後的節點進行存儲。

我們利用帶有限負載的一致性哈希演算法來改進上面的數據存儲，我們限定每台伺服器節點存儲的數據上限為 2 ，數據插入的順序就按照 ID 大小的順序，同樣我也畫了一張模擬圖：

一起來分析一下這張圖，因為我們的添加順序是按照 id 大小的順序，所以前四個數據都沒有問題，這時候的伺服器都沒有超過最高負載數量，id=5 的數據落在了伺服器server2 和伺服器server3 之間，本應該是存儲在伺服器server3 上，但是由於此時的伺服器server3 上已經存儲了 id=1、id=3 的數據達到了最高限定，因此 id=5 的數據會沿著順時針的方向繼續往下尋找伺服器，下一個伺服器就是server1，此時的伺服器server1 就存儲了 id=4 的數據並沒有達到上限，所以 id=5 的數據就會存儲在伺服器server1，id=6 的數據同樣的道理。這樣就利用帶有限負載的一致性哈希演算法解決了一致性哈希演算法中數據分布不均勻的問題。

帶虛擬節點的一致性哈希演算法

帶有限負載的一致性哈希演算法也有一個問題，那就是每台伺服器的性能配置可能存在不一樣，如果規定數量過小的話，對於配置高的伺服器來說有點浪費，這是因為伺服器之間可能存在差異，叫做伺服器之間的異構性，為了解決伺服器之間的異構性問題，引入了一種叫做帶虛擬節點的一致性哈希演算法，帶虛擬節點的一致性哈希演算法核心思想是：根據每個節點的性能為每個節點劃分不同數量的虛擬節點，並將這些虛擬節點映射到哈希環中，然後再按照一致性哈希演算法進行數據映射和存儲。

為了演示帶虛擬節點的一致性哈希演算法，我們先做一個假設伺服器server3是配置最差的，所以我們以伺服器server3 為基準，伺服器server2 是伺服器server3 的兩倍，伺服器server1 是伺服器server3 的三倍，有了這個前提之後，我們就可以來建立虛擬節點，我們假設伺服器server3 的虛擬節點為伺服器server3_1，伺服器server2 就有兩個虛擬節點伺服器server2_1、伺服器server2_2，伺服器server1 有三個虛擬節點 伺服器server1_1、伺服器server1_2、伺服器server1_3。我還是跟前面一樣畫了一張模擬圖：

落到虛擬節點上的數據都會存到對應的物理伺服器上，所以通過帶虛擬節點的一致性哈希演算法後，數據存儲結果為：數據id=2、id=3、id=5 的數據都會存儲到伺服器server1 上，id=1 的數據將會存儲到伺服器server2 上，數據 id=4、id=6 都會存放到伺服器server3上。

虛擬節點可以讓配置好的伺服器存儲更多的數據，這樣就解決了系統異構性的問題，同時由於大量的虛擬節點的存在

在數據遷移時數據會落到不同的物理機上，這樣就減小了數據遷移時某台伺服器的分擔壓力，能夠保證系統的穩定性。

虛擬槽分區

虛擬槽分區是 redis cluster 中默認的數據分布技術，虛擬槽分區巧妙地使用了哈希空間，使用分散度良好的哈希函數把所有數據映射到一個固定範圍的整數集合中，這個整數定義為槽（slot），而且這個槽的個數一般遠遠的大於節點數。

在 redis cluster 中有16384（0~16383）個槽，會將這些槽平均分配到每個 master 上，在存儲數據時利用 CRC16 演算法，具體的計算公式為：slot=CRC16（key）/16384 來計算 key 屬於哪個槽。在我們的集群環境中，一個 key 的存儲或者查找過程，可能如下圖所示：

虛擬槽分區解耦了數據與節點的關係，通過引入槽，讓槽成為集群內數據管理和遷移的基本單位，簡化了節點擴容和收縮難度，你只需要關注數據在哪個槽，並不需要關心數據在哪個節點上。所以虛擬槽分區可以說比較好的兼容了數據均勻分布和擴展性的問題。

以上就是我要分享關於集群中數據分布的技術，希望本文的內容對大家的學習或者工作能帶來一定的幫助，感謝大家的支援

最後

目前互聯網上很多大佬都有數據分布相關文章，如有雷同，請多多包涵了。原創不易，碼字不易，還希望大家多多支援。若文中有所錯誤之處，還望提出，謝謝。

原文發佈於微信公眾號 -平頭哥的技術博文（id：pingtouge_java） 作者：平頭哥，學會伺機而動，實現彎道超車 ZjYyMjU2OWMyMTA3?x-oss-process=image/format,png)