Redis集群：一致性哈希
一、Redis集群的使用
我們在使用Redis的時候，為了保證Redis的高可用，提高Redis的讀寫性能，最簡單的方式我們會做主從復(fù)制，組成Master-Master或者M(jìn)aster-Slave的形式，或者搭建Redis集群，進(jìn)行數(shù)據(jù)的讀寫分離，類似于數(shù)據(jù)庫的主從復(fù)制和讀寫分離。如下所示：??
同樣類似于數(shù)據(jù)庫，當(dāng)單表數(shù)據(jù)大于500W的時候需要對其進(jìn)行分庫分表，當(dāng)數(shù)據(jù)量很大的時候（標(biāo)準(zhǔn)可能不一樣，要看Redis服務(wù)器容量）我們同樣可以對Redis進(jìn)行類似的操作，就是分庫分表。
假設(shè)，我們有一個社交網(wǎng)站，需要使用Redis存儲圖片資源，存儲的格式為鍵值對，key值為圖片名稱，value為該圖片所在文件服務(wù)器的路徑，我們需要根據(jù)文件名查找該文件所在文件服務(wù)器上的路徑，數(shù)據(jù)量大概有2000W左右，按照我們約定的規(guī)則進(jìn)行分庫，規(guī)則就是隨機(jī)分配，我們可以部署8臺緩存服務(wù)器，每臺服務(wù)器大概含有500W條數(shù)據(jù)，并且進(jìn)行主從復(fù)制，示意圖如下：
由于規(guī)則是隨機(jī)的，所有我們的一條數(shù)據(jù)都有可能存儲在任何一組Redis中，例如上圖我們用戶查找一張名稱為”a.png”的圖片，由于規(guī)則是隨機(jī)的，我們不確定具體是在哪一個Redis服務(wù)器上的，因此我們需要進(jìn)行1、2、3、4，4次查詢才能夠查詢到（也就是遍歷了所有的Redis服務(wù)器），這顯然不是我們想要的結(jié)果。還有可能是同一份數(shù)據(jù)可能被存在不同的機(jī)器上而造成數(shù)據(jù)冗余，第二個是有可能某數(shù)據(jù)已經(jīng)被緩存但是訪問卻沒有命中，因為無法保證對相同key的所有訪問都被發(fā)送到相同的服務(wù)器。
有了解過的小伙伴可能會想到，隨機(jī)的規(guī)則不行，可以使用類似于數(shù)據(jù)庫中的分庫分表規(guī)則：按照Hash值、取模、按照類別、按照某一個字段值等等常見的規(guī)則就可以出來了！好，按照我們的主題，我們就使用Hash的方式。
為了解決這個問題，我們可以使用簡單的hash算法，比如
h = Hash(key) % 3
這里的hash作用是將輸入的key，轉(zhuǎn)換成一個整數(shù)，然后對3取余數(shù)，所以計算出來的結(jié)果只有0，1，2三個數(shù)字，并且相同的key每次計算出來的結(jié)果肯定是相同的
假設(shè)我們有N臺機(jī)器，現(xiàn)在我們把上面的公式抽象，就是
h = Hash(key) % N
現(xiàn)在我們解決了隨機(jī)存放帶來的兩個問題，看起來似乎不錯，但是大家想一下，如果N臺機(jī)器里面，萬一有一臺機(jī)器X掛了，會出現(xiàn)什么樣的情況。
首先掛了的這臺機(jī)器X無論是存放還是獲取操作，都是會失敗的，所以一般監(jiān)控系統(tǒng)檢測到有機(jī)器掛了，肯定會把這臺機(jī)器摘除出去，機(jī)器數(shù)就從N臺減到了N-1臺，那么X后面的機(jī)器就需要序號減1，并且計算公式需要調(diào)整成
h = Hash(key) % (N-1)
?
我們再來假設(shè)另外一種情況，現(xiàn)在有N臺機(jī)器提供服務(wù)，但是已經(jīng)支持不下去了，所以新增了一臺機(jī)器，那么計算公式需要調(diào)整成
h = Hash(key) % (N+1)
?
大家發(fā)現(xiàn)上面有什么問題沒有，就是每次有機(jī)器掛了，或者新增機(jī)器的時候，都需要調(diào)整計算公式，這會導(dǎo)致大量的緩存命中不了，我們把這個叫做容錯性和擴(kuò)展性不強(qiáng)，怎么解決這個問題？
我們來看看一致性hash是怎么做的
?一致性hash
一個設(shè)計良好的分布式哈希方案應(yīng)該具有良好的單調(diào)性，即服務(wù)節(jié)點(diǎn)的增減不會造成大量哈希重定位。一致性哈希算法就是這樣一種哈希方案。最早是1997年由麻省理工大學(xué)提出的。
簡單來說，一致性哈希將整個哈希值空間組織成一個虛擬的圓環(huán)，如假設(shè)某哈希函數(shù)H的值空間為0 - 232-1（即哈希值是一個32位無符號整形），整個哈?？臻g環(huán)如下：
?
整個空間按順時針方向組織。0和232-1在零點(diǎn)中方向重合。
下一步將各個服務(wù)器使用H進(jìn)行一個哈希，具體可以選擇服務(wù)器的ip或主機(jī)名作為關(guān)鍵字進(jìn)行哈希，這樣每臺機(jī)器就能確定其在哈希環(huán)上的位置，這里假設(shè)將上文中三臺服務(wù)器使用ip地址哈希后在環(huán)空間的位置如下：
?
接下來使用如下算法定位數(shù)據(jù)訪問到相應(yīng)服務(wù)器：將數(shù)據(jù)key使用相同的函數(shù)H計算出哈希值h，通根據(jù)h確定此數(shù)據(jù)在環(huán)上的位置，從此位置沿環(huán)順時針“行走”，第一臺遇到的服務(wù)器就是其應(yīng)該定位到的服務(wù)器。
例如我們有A、B、C、D四個數(shù)據(jù)對象，經(jīng)過哈希計算后，在環(huán)空間上的位置如下：
?
根據(jù)一致性哈希算法，數(shù)據(jù)A會被定為到Server 1上，D被定為到Server 3上，而B、C分別被定為到Server 2上。
一致性hash的容錯性與可擴(kuò)展性
下面分析一致性哈希算法的容錯性和可擴(kuò)展性?，F(xiàn)假設(shè)Server 3宕機(jī)了：
?
可以看到此時A、C、B不會受到影響，只有D節(jié)點(diǎn)被重定位到Server 2。一般的，在一致性哈希算法中，如果一臺服務(wù)器不可用，則受影響的數(shù)據(jù)僅僅是此服務(wù)器到其環(huán)空間中前一臺服務(wù)器（即順著逆時針方向行走遇到的第一臺服務(wù)器）之間數(shù)據(jù)，其它不會受到影響。
下面考慮另外一種情況，如果我們在系統(tǒng)中增加一臺服務(wù)器Memcached Server 4：
?
此時A、D、C不受影響，只有B需要重定位到新的Server 4。一般的，在一致性哈希算法中，如果增加一臺服務(wù)器，則受影響的數(shù)據(jù)僅僅是新服務(wù)器到其環(huán)空間中前一臺服務(wù)器（即順著逆時針方向行走遇到的第一臺服務(wù)器）之間數(shù)據(jù)，其它不會受到影響。
綜上所述，一致性哈希算法對于節(jié)點(diǎn)的增減都只需重定位環(huán)空間中的一小部分?jǐn)?shù)據(jù)，具有較好的容錯性和可擴(kuò)展性。
8. 一致性hash的虛擬節(jié)點(diǎn)
一致性哈希算法在服務(wù)節(jié)點(diǎn)太少時，容易因為節(jié)點(diǎn)分部不均勻而造成數(shù)據(jù)傾斜問題。例如我們的系統(tǒng)中有兩臺服務(wù)器，其環(huán)分布如下：
?
此時必然造成大量數(shù)據(jù)集中到Server 1上，而只有極少量會定位到Server 2上。為了解決這種數(shù)據(jù)傾斜問題，一致性哈希算法引入了虛擬節(jié)點(diǎn)機(jī)制，即對每一個服務(wù)節(jié)點(diǎn)計算多個哈希，每個計算結(jié)果位置都放置一個此服務(wù)節(jié)點(diǎn)，稱為虛擬節(jié)點(diǎn)。具體做法可以在服務(wù)器ip或主機(jī)名的后面增加編號來實(shí)現(xiàn)。例如上面的情況，我們決定為每臺服務(wù)器計算三個虛擬節(jié)點(diǎn)，于是可以分別計算“Memcached Server 1#1”、“Memcached Server 1#2”、“Memcached Server 1#3”、“Memcached Server 2#1”、“Memcached Server 2#2”、“Memcached Server 2#3”的哈希值，于是形成六個虛擬節(jié)點(diǎn)：
?
同時數(shù)據(jù)定位算法不變，只是多了一步虛擬節(jié)點(diǎn)到實(shí)際節(jié)點(diǎn)的映射，例如定位到“Memcached Server 1#1”、“Memcached Server 1#2”、“Memcached Server 1#3”三個虛擬節(jié)點(diǎn)的數(shù)據(jù)均定位到Server 1上。這樣就解決了服務(wù)節(jié)點(diǎn)少時數(shù)據(jù)傾斜的問題。在實(shí)際應(yīng)用中，通常將虛擬節(jié)點(diǎn)數(shù)設(shè)置為32甚至更大，因此即使很少的服務(wù)節(jié)點(diǎn)也能做到相對均勻的數(shù)據(jù)分布。
?
再來一把，這是最通俗的一致性hash解釋！
?
?網(wǎng)站為了支撐更大的用戶訪問量，往往需要對用戶訪問的數(shù)據(jù)做cache,服務(wù)機(jī)群和負(fù)載均衡來專門處理緩存，負(fù)載均衡的算法很多，輪循算法、哈希算法、最少連接算法、響應(yīng)速度算法等，hash算法是比較常用的一種，它的常用思想是先計算出一個hash值，然后使用 CRC余數(shù)算法將hash值和機(jī)器數(shù)mod后取余數(shù)，機(jī)器的編號可以是0到N-1(N是機(jī)器數(shù))，計算出的結(jié)果一一對應(yīng)即可。
? ? ? ?緩存最關(guān)鍵的就是命中率這個因素，如果命中率非常低，那么緩存也就失去了它的意義。如采用一般的CRC取余的hash算法雖然能達(dá)到負(fù)載均衡的目的，但是它存在一個嚴(yán)重的問題，那就是如果其中一臺服務(wù)器down掉，那么就需要在計算緩存過程中將這臺服務(wù)器去掉，即N臺服務(wù)器，目前就只有N-1臺提供緩存服務(wù)，此時需要一個rehash過程，而reash得到的結(jié)果將導(dǎo)致正常的用戶請求不能找到原來緩存數(shù)據(jù)的正確機(jī)器，其他N-1臺服務(wù)器上的緩存數(shù)據(jù)將大量失效，此時所有的用戶請求全部會集中到數(shù)據(jù)庫上，嚴(yán)重可能導(dǎo)致整個生產(chǎn)環(huán)境掛掉.
? ? ? ?舉個例子，有5臺服務(wù)器，編號分別是0(A)，1(B)，2(C)，3(D)，4(E) ?，正常情況下,假設(shè)用戶數(shù)據(jù)hash值為12，那么對應(yīng)的數(shù)據(jù)應(yīng)該緩存在12%5=2號服務(wù)器上，假設(shè)編號為3的服務(wù)器此時掛掉，那么將其移除后就得到一個新的0(A)，1(B)，2(C)，3(E)(注：這里的編號3其實(shí)就是原來的4號服務(wù)器)服務(wù)器列表，此時用戶來取數(shù)據(jù)，同樣hash值為12,rehash后的得到的機(jī)器編號12%4=0號服務(wù)器，可見，此時用戶到0號服務(wù)器去找數(shù)據(jù)明顯就找不到，出現(xiàn)了cache不命中現(xiàn)象，如果不命中此時應(yīng)用會從后臺數(shù)據(jù)庫重新讀取數(shù)據(jù)再cache到0號服務(wù)器上，如果大量用戶出現(xiàn)這種情況，那么后果不堪設(shè)想。同樣，增加一臺緩存服務(wù)器，也會導(dǎo)致同樣的后果。
? ? ? ?可以有一種設(shè)想，要提高命中率就得減少增加或者移除服務(wù)器rehash帶來的影響，那么有這樣一種算法么?Consistent hashing算法就是這樣一種hash算法，簡單的說，在移除/添加一個 cache 時，它能夠盡可能小的改變已存在 key 映射關(guān)系，盡可能的滿足單調(diào)性的要求。
1．環(huán)形Hash空間
? ? ? ?按照常用的hash算法來將對應(yīng)的key哈希到一個具有2^32個桶的空間中，即0~(2^32)-1的數(shù)字空間中?？梢詫⑦@些數(shù)字頭尾相連，想象成一個閉合的環(huán)形。如下圖:
2．把數(shù)據(jù)（key）通過一定的hash算法處理后映射到環(huán)上
? ? ? 現(xiàn)在將object1、object2、object3、object4四個對象通過特定的Hash函數(shù)計算出對應(yīng)的key值，然后散列到Hash環(huán)上。如下圖：
? ? ? Hash(object1) = key1；
? ? ? Hash(object2) = key2；
? ? ? Hash(object3) = key3；
? ? ? Hash(object4) = key4；
3．將機(jī)器通過hash算法映射到環(huán)上
? ? ? 在采用一致性哈希算法的分布式集群中將新的機(jī)器加入，其原理是通過使用與對象存儲一樣的Hash算法將機(jī)器也映射到環(huán)中（一般情況下對機(jī)器的hash計算是采用機(jī)器的IP或者機(jī)器唯一的別名作為輸入值），然后以順時針的方向計算，將所有對象存儲到離自己最近的機(jī)器中。
? ? ? 假設(shè)現(xiàn)在有NODE1，NODE2，NODE3三臺機(jī)器，通過Hash算法得到對應(yīng)的KEY值，映射到環(huán)中，其示意圖如下：
? ? ? ?Hash(NODE1) = KEY1;
? ? ? ?Hash(NODE2) = KEY2;
? ? ? ?Hash(NODE3) = KEY3;
? ? ? ?通過上圖可以看出對象與機(jī)器處于同一哈?？臻g中，這樣按順時針轉(zhuǎn)動object1存儲到了NODE1中，object3存儲到了NODE2中，object2、object4存儲到了NODE3中。在這樣的部署環(huán)境中，hash環(huán)是不會變更的，因此，通過算出對象的hash值就能快速的定位到對應(yīng)的機(jī)器中，這樣就能找到對象真正的存儲位置了。
4．機(jī)器的刪除與添加
? ? ? ?普通hash求余算法最為不妥的地方就是在有機(jī)器的添加或者刪除之后會照成大量的對象存儲位置失效，這樣就大大的不滿足單調(diào)性了。下面來分析一下一致性哈希算法是如何處理的。
? ? ? ?1. 節(jié)點(diǎn)（機(jī)器）的刪除
? ? ? ?以上面的分布為例，如果NODE2出現(xiàn)故障被刪除了，那么按照順時針遷移的方法，object3將會被遷移到NODE3中，這樣僅僅是object3的映射位置發(fā)生了變化，其它的對象沒有任何的改動。如下圖：
? ? ? ?2. 節(jié)點(diǎn)（機(jī)器）的添加?
? ? ? ?如果往集群中添加一個新的節(jié)點(diǎn)NODE4，通過對應(yīng)的哈希算法得到KEY4，并映射到環(huán)中，如下圖：
? ? ? ?通過按順時針遷移的規(guī)則，那么object2被遷移到了NODE4中，其它對象還保持這原有的存儲位置。通過對節(jié)點(diǎn)的添加和刪除的分析，一致性哈希算法在保持了單調(diào)性的同時，還是數(shù)據(jù)的遷移達(dá)到了最小，這樣的算法對分布式集群來說是非常合適的，避免了大量數(shù)據(jù)遷移，減小了服務(wù)器的的壓力。
5．平衡性
? ? ? ?根據(jù)上面的圖解分析，一致性哈希算法滿足了單調(diào)性和負(fù)載均衡的特性以及一般hash算法的分散性，但這還并不能當(dāng)做其被廣泛應(yīng)用的原由，因為還缺少了平衡性。下面將分析一致性哈希算法是如何滿足平衡性的。
? ? ? ?hash算法是不保證平衡的，如上面只部署了NODE1和NODE3的情況（NODE2被刪除的圖），object1存儲到了NODE1中，而object2、object3、object4都存儲到了NODE3中，這樣NODE3節(jié)點(diǎn)由于承擔(dān)了NODE2節(jié)點(diǎn)的數(shù)據(jù)，所以NODE3節(jié)點(diǎn)的負(fù)載會變高，NODE3節(jié)點(diǎn)很容易也宕機(jī)，這樣依次下去可能造成整個集群都掛了。
? ? ? ?在一致性哈希算法中，為了盡可能的滿足平衡性，其引入了虛擬節(jié)點(diǎn)。“虛擬節(jié)點(diǎn)”（ virtual node ）是實(shí)際節(jié)點(diǎn)（機(jī)器）在 hash 空間的復(fù)制品（replica），一實(shí)際個節(jié)點(diǎn)（機(jī)器）對應(yīng)了若干個“虛擬節(jié)點(diǎn)”，這個對應(yīng)個數(shù)也成為“復(fù)制個數(shù)”，“虛擬節(jié)點(diǎn)”在 hash 空間中以hash值排列。即把想象在這個環(huán)上有很多“虛擬節(jié)點(diǎn)”，數(shù)據(jù)的存儲是沿著環(huán)的順時針方向找一個虛擬節(jié)點(diǎn)，每個虛擬節(jié)點(diǎn)都會關(guān)聯(lián)到一個真實(shí)節(jié)點(diǎn)。
? ? ? ? 圖中的A1、A2、B1、B2、C1、C2、D1、D2都是虛擬節(jié)點(diǎn)，機(jī)器A負(fù)載存儲A1、A2的數(shù)據(jù)，機(jī)器B負(fù)載存儲B1、B2的數(shù)據(jù)，機(jī)器C負(fù)載存儲C1、C2的數(shù)據(jù)。由于這些虛擬節(jié)點(diǎn)數(shù)量很多，均勻分布，因此不會造成“雪崩”現(xiàn)象。
?
? ? ? 使用虛擬節(jié)點(diǎn)的思想，為每個物理節(jié)點(diǎn)（服務(wù)器）在圓上分配100～200個點(diǎn)。這樣就能抑制分布不均勻，最大限度地減小服務(wù)器增減時的緩存重新分布。用戶數(shù)據(jù)映射在虛擬節(jié)點(diǎn)上，就表示用戶數(shù)據(jù)真正存儲位置是在該虛擬節(jié)點(diǎn)代表的實(shí)際物理服務(wù)器上。
? ? ? 下面有一個圖描述了需要為每臺物理服務(wù)器增加的虛擬節(jié)點(diǎn)。
? ? ? x軸表示的是需要為每臺物理服務(wù)器擴(kuò)展的虛擬節(jié)點(diǎn)倍數(shù)(scale)，y軸是實(shí)際物理服務(wù)器數(shù)，可以看出，當(dāng)物理服務(wù)器的數(shù)量很小時，需要更大的虛擬節(jié)點(diǎn)，反之則需要更少的節(jié)點(diǎn)，從圖上可以看出，在物理服務(wù)器有10臺時，差不多需要為每臺服務(wù)器增加100~200個虛擬節(jié)點(diǎn)才能達(dá)到真正的負(fù)載均衡。
總結(jié)
以上是生活随笔為你收集整理的Redis集群：一致性哈希的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Redis集群：redis cluste
- 下一篇： Redis:redis入门