前言

伴隨著系統流量的增大，出現了應用叢集。在 Redis 中為了保證 Redis 的高可用也為 Redis 搭建了叢集對資料進行分槽存放。在 Mysql資料庫要儲存的量達到一個很高的地步的時候，我們會對資料庫進行分庫分表操作。OK，到這兒先假設我們不知道什麼是叢集、什麼是分庫分表，下面我們先來看一個數據庫水平切分演變的例子。

假設我們的系統中有一張會員表 customer_info， 我們的系統剛開始無人問津，我們在一個單個的資料庫中放這張表，所有的會員記錄都插入到這個資料庫的這張表中，這沒什麼問題，是一個很正常且合理的操作。某段時間，我們的系統突然火爆了起來，註冊會員激增，達到了千萬級別並且還在快速增長，這時候所有的使用者請求資料都會請求這張表，毫無疑問資料庫的壓力很大，於是可能會經常發生宕機事件，給系統造成了很大影響。為了解決這件事情，我們將單張表的資料切分到多個伺服器上去，每個伺服器具有相應的庫與表，只是表中資料不同。這樣做能夠有效的緩解單機資料庫的壓力和系統的效能瓶頸。

看完了這個例子，我們對水平拆分資料庫有了一個大致的印象，其實就是把很多的資料按照一定的規則存放在不同的伺服器上，然後查詢的時候能夠根據存放的時候的規則去找到前面存放的資料。那麼我們要說的一致性雜湊演算法，其實就是解決了這裡面的 存取規則 的問題，有了這個一致性雜湊演算法，我們能夠準確的知道我們要取的資料落在哪個機器的哪個資料庫中。

1. 簡單雜湊

還是上面水平拆分資料庫的例子，假設我們現在不知道什麼一致性雜湊什麼叢集分槽，就讓我們自己想的話，我們可以很容器的想到 java 中的 HashMap 的原理，它透過計算了一個 key 的雜湊值，然後拿這個雜湊值對底層陣列取模就得到了一個雜湊桶，如果資料存在的話，就一定在這個雜湊桶裡，否則就不存在。類似的可以想到，假設我們的 customer_info 我們可以按照使用者id去分庫分表，假設此時存在水平的三個庫表，如下，我們分別稱之為節點D1、節點D2、節點D0：

分庫分表的時候，使用者 A 的記錄落在了 D1 機器，使用者 B 的記錄落在了 D2 機器，使用者 C 的機器落在了 D0 機器上，使用者 A 要存在哪條資料庫上的計算過程是使用者 A 的會員 id 的雜湊值對 3 取模，因為現在只有 3 臺機器，虛擬碼： A_id。hash（） % / 3，使用者 B 和使用者 C 依次類推。如下圖所示：

這好像很方便的解決了存取規則的

問題，我們來分析一波：

假設我們的系統使用者量又激增了，我們就需要再加一些機器，此時我們再計算雜湊值的時候，取模不再是對 3 取模了，而是對 4 進行取模了，之前 A_id。hash（） % / 3 = 1，而現在 A_id。hash（） % / 4 = ？ 這個值很大機率不會是 1，所以這就會出現使用者明明存在記錄但是卻查不到的情況，這就問題很大了，如果要解決這個問題只能在機器節點數量變化的時候對資料重新雜湊，這代價就有點大了。所以，我們需要想辦法讓這種情況不發生，這種情況發生的根本是雜湊演算法本身的特性導致的，直接使用取模的話這是無法避免的。所以就有了一致性雜湊。

2. 一致性雜湊

上面透過資料庫的例子介紹了雜湊演算法，然後也分析了它的劣勢，當機器數量發生變動的時候，幾乎所有的資料都會移動（不移動的應該是運氣比較好吧前後取模都是同一個值），這個代價很大。此時的問題從水平如何拆分變成了，當增加或者刪除節點時，對於大多數記錄，保證原來分配到的某個節點，現在仍然應該分配到那個節點，將資料遷移量的降到最低，這就是一致性雜湊要做的事情。在這裡我們不指定是資料庫還是什麼，反正都是分散式儲存節點。

2.1 一致性雜湊

一致性 Hash 演算法也是使用取模的思想，只是，剛才描述的取模法是對節點數量進行取模，而一致性Hash演算法是對 2^32 取模，什麼意思呢？簡單來說，一致性Hash演算法將整個雜湊值空間組織成一個虛擬的圓環，如假設某雜湊函式H的值空間為0-2^32-1（即雜湊值是一個32位無符號整形），整個雜湊環如下，從 0 ~ 2^32-1 代表的分別是一個個的節點，這個環也叫雜湊環。如下圖所示：

然後我們將我們的節點進行一次雜湊，按照一定的規則，比如按照 ip 地址的雜湊值，讓節點落在雜湊環上。比如此時我們可能得到了如下圖的環：

然後就是需要透過資料 key 找到對應的伺服器然後儲存了，我們約定，透過資料 key 的雜湊值落在雜湊環上的節點，如果命中了機器節點就落在這個機器上，否則落在順時針直到碰到第一個機器。如下圖所示 ： A 的雜湊值落在了 D2 節點的前面，往下找落在了 D2 機器上，D的雜湊值 在 D1 節點的前面，往下找到了 D1 機器，B的雜湊值剛好落在了D1 節點上，其它依次類推。如下圖所示：

2.2 一致性雜湊的分析

一致性雜湊主要就是解決當機器減少或增加的時候，大面積的資料重新雜湊的問題，主要從下面 2 個方向去考慮的，當節點宕機時，資料記錄會被定位到下一個節點上，當新增節點的時候 ，相關區間內的資料記錄就需要重新雜湊。

2.2.1 某節點宕機

我們假設上圖中的 節點 D2 因為一些原因宕機了，可以看到，只有資料 A 的記錄需要重新重新定位儲存到節點 D1 上，因為 D1 是 D2 的下一個節點，其它的資料都沒有被影響到，此時被影響的僅僅是 圖中的 D0-D2 這段區間的記錄，也就是之前落在 D2 上的資料現在都要落到 D1 上面了。如下圖所示

2.2.2 新增節點

我們假設我們需要增加一臺機器，也就是增加一個節點D4，如下圖所示，這個節點落在 D2-D1 之間，按照上述的雜湊環上的雜湊值落在節點的規則，那麼此時之前落在 D2 到 D4 之間的資料都需要重新定位到新的節點上面了，而其它位置的資料是不需要有改變的。

2.3 一致性雜湊的資料傾斜問題

一致性Hash演算法在服務節點太少時，容易因為節點分佈不均勻而造成資料傾斜（被快取的物件大部分集中快取在某一臺伺服器上）問題。比如只有 2 臺機器，這 2 臺機器離的很近，那麼順時針第一個機器節點上將存在大量的資料，第二個機器節點上資料會很少。如下圖所示，D0 機器承載了絕大多數的資料：

2.4 虛擬節點解決資料傾斜問題

為了避免出現數據傾斜問題，一致性 Hash 演算法引入了虛擬節點的機制，也就是每個機器節點會進行多次雜湊，最終每個機器節點在雜湊環上會有多個虛擬節點存在，使用這種方式來大大削弱甚至避免資料傾斜問題。同時資料定位演算法不變，只是多了一步虛擬節點到實際節點的對映，例如定位到“D1#1”、“D1#2”、“D1#3”三個虛擬節點的資料均定位到 D1 上。這樣就解決了服務節點少時資料傾斜的問題。在實際應用中，通常將虛擬節點數設定為32甚至更大，因此即使很少的服務節點也能做到相對均勻的資料分佈。這也是 Dubbo 負載均衡中有一種一致性雜湊負載均衡的實現思想。

2.5 一致性雜湊的應用案例

一致性雜湊用到的地方很多，特別是中介軟體裡面，比如 Dubbo 的負載均衡也有一種策略是一致性雜湊策略，使用的就是虛擬節點實現的。Redis 叢集中也用到了相關思想但是沒有用它而是根據實際情況改進了一下。而對於儲存資料的節點水平切分的時候它的作用就更不可代替了。and so on···

3. Redis 叢集分槽的實現

Redis 叢集並沒有直接使用一致性雜湊，而是使用了雜湊槽 （slot） 的概念，Redis 沒有直接使用雜湊演算法 hash（），而是使用了crc16校驗演算法。槽位其實就是一個個的空間的單位。其實雜湊槽的本質和一致性雜湊演算法非常相似，不同點就是對於雜湊空間的定義。一致性雜湊的空間是一個圓環，節點分佈是基於圓環的，無法很好的控制資料分佈，可能會產生資料傾斜問題。而 Redis 的槽位空間是自定義分配的，類似於Windows盤分割槽的概念。這種分割槽是可以自定義大小，自定義位置的。Redis 叢集包含了 16384 個雜湊槽，每個 Key 經過計算後會落在一個具體的槽位上，而槽位具體在哪個機器上是使用者自己根據自己機器的情況配置的，機器硬碟小的可以分配少一點槽位，硬碟大的可以分配多一點。如果節點硬碟都差不多則可以平均分配。所以雜湊槽這種概念很好地解決了一致性雜湊的弊端。

另外在容錯性和擴充套件性上與一致性雜湊一樣，都是對受影響的資料進行轉移而不影響其它的資料。而雜湊槽本質上是對槽位的轉移，把故障節點負責的槽位轉移到其他正常的節點上。擴充套件節點也是一樣，把其他節點上的槽位轉移到新的節點上。

需要注意的是，對於槽位的轉移和分派，Redis叢集是不會自動進行的，而是需要人工配置的。所以Redis叢集的高可用是依賴於節點的主從複製與主從間的自動故障轉移。

圖

文

：程式設計之魅

排版：96編輯器