今天我們聊個知識點為什么Redis使用哈希槽而不是一致性哈希。

先看文章大綱，提前了解本期內(nèi)容

圖片

往期回顧

之前小許用圖文并茂的方式用一期內(nèi)容讓大家快速了解了一致性哈希算法，看過的朋友應(yīng)該還有印象，沒看過的朋友可以點擊這里看一遍《五分鐘了解一致性哈希算法》。

看明白這篇一致性哈希算法基礎(chǔ)，會對本期內(nèi)容有更好的認(rèn)識和對比性。

這里我們再簡單回顧下：

一致性哈希算法就很好地解決了分布式系統(tǒng)在擴(kuò)容或者縮容時，發(fā)生過多的數(shù)據(jù)遷移的問題。

算法是對 2^32 進(jìn)行取模運算的結(jié)果值虛擬成一個圓環(huán)，環(huán)上的刻度對應(yīng)一個 0~2^32 - 1 之間的數(shù)值。

通過虛擬節(jié)點的方式很好的處理了數(shù)據(jù)不平衡問題。

圖片

不同的計算方式

不知道朋友們記不記得Redis Cluster的實現(xiàn)，也是用了Hash的方式將鍵值按照一定算法分配到各個節(jié)點的，但是卻沒有使用一致性哈希算法，而是引入了哈希槽的概念!

這是為什么呢？????

我們先看下一致性哈希和哈希槽在計算上的區(qū)別

圖片

圖中A、B、C表示的是三個節(jié)點，k1和k2表示的是key：

?? 一致性哈希是經(jīng)過 hash() 函數(shù)計算后對 2^32 取模的值虛擬成一個圓環(huán)

?? 哈希槽是將每個key通過CRC16計算得到一個16bit的值，然后16bit值再對16384取模來決定放置哪個槽

雖說在計算方式上有區(qū)別，好像都解決了數(shù)據(jù)均衡的問題，應(yīng)該都是不錯的選擇。

OK，本文將先對Redis集群節(jié)點增減時如何進(jìn)行哈希槽的分配進(jìn)行分享，再回過頭看為什么Redis 集群沒有使用一致性hash，而是引入了哈希槽的概念的原因究竟是什么！

Redis Cluster集群

Redis集群是一種分布式數(shù)據(jù)庫方案，通過服務(wù)器分片技術(shù)進(jìn)行數(shù)據(jù)管理，我們來對它進(jìn)行一個歸納總結(jié)。

哈希槽

集群將數(shù)據(jù)劃分為 16384 （2^14）個槽位（哈希槽），每個Redis服務(wù)節(jié)點分配了一部分槽位，因為槽位的信息存儲于每個節(jié)點中，客戶端請求的key通過CRC16校驗后對16384取模來決定放置哪個槽，這樣也就定位到指定的節(jié)點中。

圖片

上圖中 key 【小許】和【code】經(jīng)過 CRC16 計算后再對哈希槽總個數(shù) 16384 取模，得到哈希槽位置分別是在888的節(jié)點A上和10924的節(jié)點C上面。

?? 重點：每個節(jié)點都會記錄哪些槽分配給了自己，哪些槽被分配給了其他節(jié)點

增加節(jié)點

新增一個節(jié)點D，redis cluster的這種做法是從各個節(jié)點的前面各拿取一部分slot(槽)到D上，會變成這樣：

圖片

此時服務(wù)A、B、C、D通過分配各自有了對應(yīng)的哈希槽，新增節(jié)點后集群會自動進(jìn)行哈希槽的重新平均分配，比如上圖中四個節(jié)點中每個節(jié)點的槽位數(shù)是：18384 / 4 = 4096。

當(dāng)然這個你使用命令 【cluster addslots】為每個節(jié)點自定義分配槽的數(shù)量，這里有個特點，如果我們節(jié)點的機(jī)器性能有差異，那就可以為性能好的，配置更多槽位，更好的利用機(jī)器性能。

減少節(jié)點

如果減少一個節(jié)點C，redis cluster同樣會自動進(jìn)行槽數(shù)量的重新計算分配，然后后變成下面樣子：

圖片

刪除節(jié)點C之后，此時服務(wù)A、B節(jié)點中每個節(jié)點的槽位數(shù)是：18384 / 2 = 8192

客戶端訪問節(jié)點數(shù)據(jù)

Redis cluster的主節(jié)點各自負(fù)責(zé)一部分槽，我們來看下來自客戶端的請求的key是如何定位到具體的節(jié)點，然后返回對應(yīng)的數(shù)據(jù)的。

圖片

來自Redis-Cli客戶端的請求連接到的是集群中的任何一個節(jié)點

1. 1. 首先檢查當(dāng)前key是否存在集群中的節(jié)點

• ? 通過CRC16（key）/ 16384計算出slot
• ? 查詢負(fù)責(zé)該slot負(fù)責(zé)的節(jié)點是否存在

2. 1. 在該節(jié)點的話就直接就直接返回key對應(yīng)的結(jié)果
3. 2. 不在該節(jié)點的話，那么會 MOVED重定向（包含槽位和目標(biāo)地址）指引客戶端轉(zhuǎn)向至正確的節(jié)點，并再次發(fā)送之前執(zhí)行的命令

???? 相信你也和小許一樣覺得這種方式弊端很明顯，每次執(zhí)行命令前都可能現(xiàn)在Redis節(jié)點上進(jìn)行MOVED重定向才能找到要執(zhí)行命令的節(jié)點，額外增加了IO開銷。

?? 不過大多數(shù)開發(fā)語言的Redis客戶端都采用 Smart客戶端 支持集群協(xié)議，讓整個訪問就更高效。

我們來看下是如何實現(xiàn)的！

smart客戶端

開發(fā)語言寫的Redis客戶端都會采用Smart客戶端來支持訪問集群。

主要是在內(nèi)部維護(hù)哈希槽--節(jié)點的映射關(guān)系，這樣就可以在Smart客戶端實現(xiàn)鍵到節(jié)點的查找，避免了再進(jìn)行MOVED重定向。

不過第一步還是初始化時會選擇一個運行節(jié)點，初始化槽和節(jié)點映射關(guān)系。

我們看下圖：

圖片

上面我們簡單講了下Redis-Cluster中哈希槽和增刪節(jié)點槽位的轉(zhuǎn)移分配，回歸正題。

?? 為什么Redis是使用哈希槽而不是一致性哈希呢？

有人可能會說是當(dāng)節(jié)點太少時，一致性哈希容易數(shù)據(jù)分布不均勻更容易導(dǎo)致雪崩。

但是看過我開頭分享的一致性哈希文章，通過引入虛擬節(jié)點是基本可以避免這個問題的

如果非要說極限情況，那么Redis哈希槽，也有可能某些hash 區(qū)間的值特別多，然后導(dǎo)致該節(jié)點導(dǎo)訪問過于集中的問題。

拋開這些極端情況，通過上面對哈希槽的總結(jié)，以下這些是更值得信服的回答：

• ? 當(dāng)發(fā)生擴(kuò)容時候，Redis可配置映射表的方式讓哈希槽更靈活，可更方便組織映射到新增server上面的slot數(shù)，比一致性hash的算法更靈活方便。
• ? 在數(shù)據(jù)遷移時，一致性hash 需要重新計算key在新增節(jié)點的數(shù)據(jù)，然后遷移這部分?jǐn)?shù)據(jù)，哈希槽則直接將一個slot對應(yīng)的數(shù)據(jù)全部遷移，實現(xiàn)更簡單
• ? 可以靈活的分配槽位，比如性能更好的節(jié)點分配更多槽位，性能相對較差的節(jié)點可以分配較少的槽位

為什么Redis Cluster哈希槽數(shù)量是16384？

我們知道一致性哈希算法是對2的32次方取模，而哈希槽是對2的14次方取模

?? Redis作者認(rèn)為這樣做不太值得；并且一般情況下一個redis集群不會有超過1000個master節(jié)點，所以16k的槽位是個比較合適的選擇。

Redis作者的回答在這里：why redis-cluster use 16384 slots? · Issue #2576 · redis/redis

圖片

總結(jié)起來主要有以下因素

• ? Redis節(jié)點間通信時，心跳包會攜帶節(jié)點的所有槽信息，它能以冪等方式來更新配置。如果采用 16384 個插槽，占空間 2KB (16384/8);如果采用 65536 個插槽，占空間 8KB (65536/8)。
• ? Redis Cluster 不太可能擴(kuò)展到超過 1000 個主節(jié)點，太多可能導(dǎo)致網(wǎng)絡(luò)擁堵。
• ? 16384 個插槽范圍比較合適，當(dāng)集群擴(kuò)展到1000個節(jié)點時，也能確保每個master節(jié)點有足夠的插槽

這也就是為什么哈希槽的數(shù)量是16384了！