最近看 Redis Cluster 集群，在 Redis Cluster 集群中涉及到了數(shù)據(jù)分布問題，因?yàn)?Redis Cluster 是多 master 的結(jié)構(gòu)，每個(gè) master 都是可以提供存儲(chǔ)服務(wù)的，這就會(huì)涉及到數(shù)據(jù)分布的問題，所以借這個(gè)機(jī)會(huì)聊一聊分布式中的數(shù)據(jù)分布算法，在新的 redis 版本中采用的是虛擬槽分區(qū)技術(shù)來解決數(shù)據(jù)分布的問題，關(guān)于什么是虛擬槽分區(qū)技術(shù)我們后面會(huì)詳細(xì)的介紹。在分布式集群中除了虛擬槽分區(qū)技術(shù)之外，還有幾種數(shù)據(jù)分布的算法，比如哈希算法，一致性哈希算法，這篇文章我們就來一起聊一聊這幾種數(shù)據(jù)分布算法。

[[285493]]

因?yàn)槭羌?，所以我們需要一個(gè)大前提，在這篇文章中假設(shè) redis cluster 集群中有三臺(tái) master，我們需要存儲(chǔ)的數(shù)據(jù)集為：[{id:1,"name":"1"},{id:2,name:"2"},{id:3,name:"3"},{id:4,name:"4"},{id:5:"name":"5"},{id:6,"name":"6"}]，在這個(gè)大前提下，我們來聊一聊集群中的數(shù)據(jù)分布算法。

哈希算法

哈希算法在分布式架構(gòu)中應(yīng)用廣泛，不僅僅是數(shù)據(jù)存儲(chǔ)，還有負(fù)載均衡等應(yīng)用上有用的比較多，哈希算法的思想非常簡單，也許你知道 HashMap 的哈希函數(shù)，哈希算法跟 HashMap 一樣，也是通過一個(gè)哈希函數(shù)得到某一個(gè)數(shù)字，然后根據(jù)數(shù)字找到相應(yīng)的服務(wù)器。哈希算法的哈希函數(shù)比較簡單，一般是根據(jù)某個(gè)key的值或者key 的哈希值與當(dāng)前可用的 master節(jié)點(diǎn)數(shù)取模，根據(jù)取模的值獲取具體的服務(wù)器。哈希算法服務(wù)結(jié)構(gòu)模型圖如下圖所示： 

哈希算法結(jié)構(gòu)模型圖

用我們前面假設(shè)的數(shù)據(jù)，利用哈希算法來實(shí)驗(yàn)一把，加深我們對哈希算法在分布式中的應(yīng)用的理。我們假設(shè)哈希算法中的哈希函數(shù)為“id % master 節(jié)點(diǎn)數(shù)”，結(jié)果為 0 的數(shù)據(jù)存放到 server1 服務(wù)器上，結(jié)果為 1 的數(shù)據(jù)存放到 server2 服務(wù)器上，結(jié)果為 2 的數(shù)據(jù)存放到 server3 服務(wù)器上。

所以經(jīng)過哈希算法之后，id=3、id=6 的數(shù)據(jù)與 master 節(jié)點(diǎn)數(shù)取模為 0 (3%3=0,6%3=0)，所以這兩個(gè)數(shù)據(jù)會(huì)存放到 server1 服務(wù)器 ，以此類推，id=1、id=4 的數(shù)據(jù)將存放到 server2 服務(wù)器中，id=2、id=5 的數(shù)據(jù)將存放到 server3 上，這時(shí)候服務(wù)器存儲(chǔ)數(shù)據(jù)如下圖所示：

服務(wù)器存儲(chǔ)數(shù)據(jù)

這就是哈希算法在分布式中的作用，比較簡單，可以看出只要你哈希函數(shù)設(shè)計(jì)的好，數(shù)據(jù)在各個(gè)服務(wù)器上是比較均勻分布的，但是哈希算法有一個(gè)致命的缺點(diǎn)：擴(kuò)展性特別的差，比如我們的集群中，服務(wù)器server3 宕機(jī)了，這時(shí)候集群中可用的機(jī)器只有兩臺(tái)了，這樣哈希函數(shù)就變成了id % 2了，這就會(huì)導(dǎo)致一個(gè)問題，所有的數(shù)據(jù)需要重新計(jì)算，找到新的存儲(chǔ)節(jié)點(diǎn)，每次有服務(wù)器宕機(jī)或者添加機(jī)器時(shí)，都需要進(jìn)行大量的數(shù)據(jù)遷移，這會(huì)使得系統(tǒng)的可用性、穩(wěn)定性變差。

一致性哈希算法

一致性哈希算法可以說是哈希算法的升級版，解決了哈希算法擴(kuò)展性差的問題，一致性哈希算法跟哈希算法不一樣，一致性哈希算法會(huì)將服務(wù)器和數(shù)據(jù)都通過哈希函數(shù)映射到一個(gè)首尾相連的哈希環(huán)上，存儲(chǔ)節(jié)點(diǎn)映射可以根據(jù) ip 地址來進(jìn)行哈希取值，數(shù)據(jù)映射到哈希環(huán)上后按照順時(shí)針的方向查找存儲(chǔ)節(jié)點(diǎn)，即從數(shù)據(jù)映射在環(huán)上的位置開始，順時(shí)針方向找到的第一個(gè)存儲(chǔ)節(jié)點(diǎn)，那么他就存儲(chǔ)在這個(gè)節(jié)點(diǎn)上。

我們使用一致性哈希算法來存儲(chǔ)我們的數(shù)據(jù)，我畫了一張圖來模擬一致性哈希算法可能出現(xiàn)的結(jié)果：

一致性算法模擬存儲(chǔ)圖

我們先來解讀一下這張圖，按照一致性哈希算法的規(guī)則，數(shù)據(jù)沿著順時(shí)針的方向查找數(shù)據(jù)，那么 id=4 的數(shù)據(jù)存放在 server1 服務(wù)器，id=2 的數(shù)據(jù)存放在服務(wù)器 server2 上，id=3、id=1、id=5、id=6 的數(shù)據(jù)都存放在服務(wù)器 server3 上，如果你比較敏感的話，也許你就會(huì)發(fā)現(xiàn)一致性哈希算法的不足之處， 從圖中可以看出，我們六條數(shù)據(jù)分布不均勻，并不是每臺(tái)服務(wù)器存儲(chǔ) 2 條數(shù)據(jù)，而且差距好像還有點(diǎn)大，這里我們就要來說一說一致性哈希算法的缺點(diǎn)：一致性哈希算法會(huì)會(huì)造成數(shù)據(jù)分布不均勻的問題或者叫做數(shù)據(jù)傾斜問題，就像我們圖中那樣，數(shù)據(jù)分布不均勻可能會(huì)造成某一個(gè)節(jié)點(diǎn)的負(fù)載過大，從而宕機(jī)。造成數(shù)據(jù)分布不均勻有以下兩種情況：

• 第一：哈希函數(shù)的原因，經(jīng)過哈希函數(shù)之后服務(wù)器在哈希環(huán)上的分布不均勻，服務(wù)器之間的間距不相等，這樣就會(huì)導(dǎo)致數(shù)據(jù)不均勻。
• 第二：某服務(wù)器宕機(jī)了，后繼節(jié)點(diǎn)就需要承受原本屬于宕機(jī)機(jī)器的數(shù)據(jù)，這樣也會(huì)造成數(shù)據(jù)不均勻。

前面我們提到過一致性哈希算法解決了哈希算法中擴(kuò)展性差的問題，這個(gè)怎么理解呢?我們來看看，在一致性哈希算法中當(dāng)有存儲(chǔ)節(jié)點(diǎn)加入或者退出時(shí)，只會(huì)影響應(yīng)該該節(jié)點(diǎn)的后繼節(jié)點(diǎn)，舉個(gè)例子說明一下，例如我們要在服務(wù)器server3 和服務(wù) server2 之間加入了一個(gè)服務(wù)器存儲(chǔ)節(jié)點(diǎn) server4，只會(huì)對服務(wù)器server3 造成影響，原本存儲(chǔ)到服務(wù)器server3 上的數(shù)據(jù)有一部分會(huì)落入到服務(wù)器 server4 上，對服務(wù)器 server1 和 server2 并沒有任何影響，這樣就不會(huì)進(jìn)行大量的數(shù)據(jù)遷移，擴(kuò)展性就變強(qiáng)了。

帶有限負(fù)載的一致性哈希算法

因?yàn)橐恢滦怨Ｋ惴ǖ臄?shù)據(jù)分布不均勻的問題，Google 在 2017 年提出了帶有限負(fù)載的一致性哈希算法來解決這個(gè)問題，帶有限負(fù)載的一致性哈希算法思想比較簡單，給每個(gè)存儲(chǔ)節(jié)點(diǎn)設(shè)置了一個(gè)存儲(chǔ)上限值來控制存儲(chǔ)節(jié)點(diǎn)添加或移除造成的數(shù)據(jù)不均勻，當(dāng)數(shù)據(jù)按照一致性哈希算法找到相應(yīng)的存儲(chǔ)節(jié)點(diǎn)時(shí)，要先判斷該存儲(chǔ)節(jié)點(diǎn)是否達(dá)到了存儲(chǔ)上限;如果已經(jīng)達(dá)到了上限，則需要繼續(xù)尋找該存儲(chǔ)節(jié)點(diǎn)順時(shí)針方向之后的節(jié)點(diǎn)進(jìn)行存儲(chǔ)。

我們利用帶有限負(fù)載的一致性哈希算法來改進(jìn)上面的數(shù)據(jù)存儲(chǔ)，我們限定每臺(tái)服務(wù)器節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)上限為 2 ，數(shù)據(jù)插入的順序就按照 ID 大小的順序，同樣我也畫了一張模擬圖：

帶有限負(fù)載的一致性哈希算法

一起來分析一下這張圖，因?yàn)槲覀兊奶砑禹樞蚴前凑?id 大小的順序，所以前四個(gè)數(shù)據(jù)都沒有問題，這時(shí)候的服務(wù)器都沒有超過最高負(fù)載數(shù)量，id=5 的數(shù)據(jù)落在了服務(wù)器server2 和服務(wù)器server3 之間，本應(yīng)該是存儲(chǔ)在服務(wù)器server3 上，但是由于此時(shí)的服務(wù)器server3 上已經(jīng)存儲(chǔ)了 id=1、id=3 的數(shù)據(jù)達(dá)到了最高限定，因此 id=5 的數(shù)據(jù)會(huì)沿著順時(shí)針的方向繼續(xù)往下尋找服務(wù)器，下一個(gè)服務(wù)器就是server1，此時(shí)的服務(wù)器server1 就存儲(chǔ)了 id=4 的數(shù)據(jù)并沒有達(dá)到上限，所以 id=5 的數(shù)據(jù)就會(huì)存儲(chǔ)在服務(wù)器server1，id=6 的數(shù)據(jù)同樣的道理。這樣就利用帶有限負(fù)載的一致性哈希算法解決了一致性哈希算法中數(shù)據(jù)分布不均勻的問題。

帶虛擬節(jié)點(diǎn)的一致性哈希算法

帶有限負(fù)載的一致性哈希算法也有一個(gè)問題，那就是每臺(tái)服務(wù)器的性能配置可能存在不一樣，如果規(guī)定數(shù)量過小的話，對于配置高的服務(wù)器來說有點(diǎn)浪費(fèi)，這是因?yàn)榉?wù)器之間可能存在差異，叫做服務(wù)器之間的異構(gòu)性，為了解決服務(wù)器之間的異構(gòu)性問題，引入了一種叫做帶虛擬節(jié)點(diǎn)的一致性哈希算法，帶虛擬節(jié)點(diǎn)的一致性哈希算法核心思想是：根據(jù)每個(gè)節(jié)點(diǎn)的性能為每個(gè)節(jié)點(diǎn)劃分不同數(shù)量的虛擬節(jié)點(diǎn)，并將這些虛擬節(jié)點(diǎn)映射到哈希環(huán)中，然后再按照一致性哈希算法進(jìn)行數(shù)據(jù)映射和存儲(chǔ)。

為了演示帶虛擬節(jié)點(diǎn)的一致性哈希算法，我們先做一個(gè)假設(shè)服務(wù)器server3是配置最差的，所以我們以服務(wù)器server3 為基準(zhǔn)，服務(wù)器server2 是服務(wù)器server3 的兩倍，服務(wù)器server1 是服務(wù)器server3 的三倍，有了這個(gè)前提之后，我們就可以來建立虛擬節(jié)點(diǎn)，我們假設(shè)服務(wù)器server3 的虛擬節(jié)點(diǎn)為服務(wù)器server3_1，服務(wù)器server2 就有兩個(gè)虛擬節(jié)點(diǎn)服務(wù)器server2_1、服務(wù)器server2_2，服務(wù)器server1 有三個(gè)虛擬節(jié)點(diǎn) 服務(wù)器server1_1、服務(wù)器server1_2、服務(wù)器server1_3。我還是跟前面一樣畫了一張模擬圖：

落到虛擬節(jié)點(diǎn)上的數(shù)據(jù)都會(huì)存到對應(yīng)的物理服務(wù)器上，所以通過帶虛擬節(jié)點(diǎn)的一致性哈希算法后，數(shù)據(jù)存儲(chǔ)結(jié)果為：數(shù)據(jù)id=2、id=3、id=5 的數(shù)據(jù)都會(huì)存儲(chǔ)到服務(wù)器server1 上，id=1 的數(shù)據(jù)將會(huì)存儲(chǔ)到服務(wù)器server2 上，數(shù)據(jù) id=4、id=6 都會(huì)存放到服務(wù)器server3上。

虛擬節(jié)點(diǎn)可以讓配置好的服務(wù)器存儲(chǔ)更多的數(shù)據(jù)，這樣就解決了系統(tǒng)異構(gòu)性的問題，同時(shí)由于大量的虛擬節(jié)點(diǎn)的存在 在數(shù)據(jù)遷移時(shí)數(shù)據(jù)會(huì)落到不同的物理機(jī)上，這樣就減小了數(shù)據(jù)遷移時(shí)某臺(tái)服務(wù)器的分擔(dān)壓力，能夠保證系統(tǒng)的穩(wěn)定性。

虛擬槽分區(qū)

虛擬槽分區(qū)是 redis cluster 中默認(rèn)的數(shù)據(jù)分布技術(shù)，虛擬槽分區(qū)巧妙地使用了哈?？臻g，使用分散度良好的哈希函數(shù)把所有數(shù)據(jù)映射到一個(gè)固定范圍的整數(shù)集合中，這個(gè)整數(shù)定義為槽(slot)，而且這個(gè)槽的個(gè)數(shù)一般遠(yuǎn)遠(yuǎn)的大于節(jié)點(diǎn)數(shù)。

在 redis cluster 中有16384(0~16383)個(gè)槽，會(huì)將這些槽平均分配到每個(gè) master 上，在存儲(chǔ)數(shù)據(jù)時(shí)利用 CRC16 算法，具體的計(jì)算公式為：slot=CRC16(key)/16384 來計(jì)算 key 屬于哪個(gè)槽。在我們的集群環(huán)境中，一個(gè) key 的存儲(chǔ)或者查找過程，可能如下圖所示：

虛擬槽分區(qū)解耦了數(shù)據(jù)與節(jié)點(diǎn)的關(guān)系，通過引入槽，讓槽成為集群內(nèi)數(shù)據(jù)管理和遷移的基本單位，簡化了節(jié)點(diǎn)擴(kuò)容和收縮難度，你只需要關(guān)注數(shù)據(jù)在哪個(gè)槽，并不需要關(guān)心數(shù)據(jù)在哪個(gè)節(jié)點(diǎn)上。所以虛擬槽分區(qū)可以說比較好的兼容了數(shù)據(jù)均勻分布和擴(kuò)展性的問題。

以上就是我要分享關(guān)于集群中數(shù)據(jù)分布的技術(shù)，希望本文的內(nèi)容對大家的學(xué)習(xí)或者工作能帶來一定的幫助，感謝大家的支持！