問題：1-2億數(shù)據(jù)需要緩存，如何設(shè)計？

1 哈希取余分區(qū)

2億條記錄就是2億個k,v，假設(shè)有3臺機器構(gòu)成一個集群，用戶每次讀寫操作都是根據(jù)公：hash(key) % N個機器臺數(shù)，計算出哈希值，并用來決定數(shù)據(jù)映射到哪一個節(jié)點上。取數(shù)據(jù)的時候只需要個根據(jù)公式在相應(yīng)的機器，用key就可以取到value。

優(yōu)點：  簡單粗暴，直接有效，只需要預(yù)估好數(shù)據(jù)規(guī)劃好節(jié)點，例如3臺、8臺、10臺，就能保證一段時間的數(shù)據(jù)支撐。使用Hash算法讓固定的一部分請求落到同一臺服務(wù)器上，這樣每臺服務(wù)器固定處理一部分請求（并維護這些請求的信息），起到負載均衡+分而治之的作用。

缺點：原來規(guī)劃好的節(jié)點，進行擴容或者縮容就比較麻煩了，不管擴縮，每次數(shù)據(jù)變動導(dǎo)致節(jié)點有變動，映射關(guān)系需要重新進行計算，在服務(wù)器個數(shù)固定不變時沒有問題，如果需要彈性擴容或故障停機的情況下，原來的取模公式就會發(fā)生變化：Hash(key)/3會變成Hash(key) /?。此時地址經(jīng)過取余運算的結(jié)果將發(fā)生很大變化，根據(jù)公式獲取的服務(wù)器也會變得不可控。某個redis機器宕機了，由于臺數(shù)數(shù)量變化，會導(dǎo)致hash取余全部數(shù)據(jù)重新洗牌。

2 一致性哈希算法分區(qū)

提出一致性Hash解決方案，目的是當服務(wù)器個數(shù)發(fā)生變動時，盡量減少影響客戶端到服務(wù)器的映射關(guān)系。

2.1 一致性哈希環(huán)

        一致性哈希算法必然有個hash函數(shù)并按照算法產(chǎn)生hash值，這個算法的所有可能哈希值會構(gòu)成一個全量集，這個集合可以成為一個hash空間[0,2^32-1]，這個是一個線性空間，但是在算法中，我們通過適當?shù)倪壿嬁刂茖⑺孜蚕噙B(0 = 2^32),這樣讓它邏輯上形成了一個環(huán)形空間。

        它也是按照使用取模的方法，前面筆記介紹的節(jié)點取模法是對節(jié)點（服務(wù)器）的數(shù)量進行取模。而一致性Hash算法是對2^32取模，簡單來說， 一致性Hash算法將整個哈希值空間組織成一個虛擬的圓環(huán) ，如假設(shè)某哈希函數(shù)H的值空間為0-2^32-1（即哈希值是一個32位無符號整形），整個哈希環(huán)如下圖：整個空間 按順時針方向組織 ，圓環(huán)的正上方的點代表0，0點右側(cè)的第一個點代表1，以此類推，2、3、4、……直到2^32-1，也就是說0點左側(cè)的第一個點代表2^32-1， 0和2^32-1在零點中方向重合，我們把這個由2^32個點組成的圓環(huán)稱為Hash環(huán)。

2.2 節(jié)點映射

 將集群中各個IP節(jié)點映射到環(huán)上的某一個位置。

   將各個服務(wù)器使用Hash進行一個哈希，具體可以選擇服務(wù)器的IP或主機名作為關(guān)鍵字進行哈希，這樣每臺機器就能確定其在哈希環(huán)上的位置。假如4個節(jié)點NodeA、B、C、D，經(jīng)過IP地址的 哈希函數(shù) 計算(hash(ip))，使用IP地址哈希后在環(huán)空間的位置如下：

2.3 落鍵規(guī)則

        當我們需要存儲一個kv鍵值對時，首先計算key的hash值，hash(key)，將這個key使用相同的函數(shù)Hash計算出哈希值并確定此數(shù)據(jù)在環(huán)上的位置， 從此位置沿環(huán)順時針“行走” ，第一臺遇到的服務(wù)器就是其應(yīng)該定位到的服務(wù)器，并將該鍵值對存儲在該節(jié)點上。

        如我們有Object A、Object B、Object C、Object D四個數(shù)據(jù)對象，經(jīng)過哈希計算后，在環(huán)空間上的位置如下：根據(jù)一致性Hash算法，數(shù)據(jù)A會被定為到Node A上，B被定為到Node B上，C被定為到Node C上，D被定為到Node D上。

 2.4 優(yōu)缺點

優(yōu)點：容錯性和擴展性

容錯性：

        假設(shè)Node C宕機，可以看到此時對象A、B、D不會受到影響，只有C對象被重定位到Node D。一般的，在一致性Hash算法中，如果一臺服務(wù)器不可用，則 受影響的數(shù)據(jù)僅僅是此服務(wù)器到其環(huán)空間中前一臺服務(wù)器（即沿著逆時針方向行走遇到的第一臺服務(wù)器）之間數(shù)據(jù) ，其它不會受到影響。簡單說，就是C掛了，受到影響的只是B、C之間的數(shù)據(jù)，并且這些數(shù)據(jù)會轉(zhuǎn)移到D進行存儲。

 缺點：數(shù)據(jù)傾斜（節(jié)點少不宜）

        一致性Hash算法在服務(wù) 節(jié)點太少時 ，容易因為節(jié)點分布不均勻而造成 數(shù)據(jù)傾斜 （被緩存的對象大部分集中緩存在某一臺服務(wù)器上）問題，

例如系統(tǒng)中只有兩臺服務(wù)器：

3 哈希槽計算

為了解決一致性哈希算法的傾斜問題

解決均勻分配的問題， 在數(shù)據(jù)和節(jié)點之間又加入了一層，把這層稱為哈希槽（slot），用于管理數(shù)據(jù)和節(jié)點之間的關(guān)系 ，現(xiàn)在就相當于節(jié)點上放的是槽，槽里放的是數(shù)據(jù)。

槽解決的是粒度問題，相當于把粒度變大了，這樣便于數(shù)據(jù)移動。

哈希解決的是映射問題，使用key的哈希值來計算所在的槽，便于數(shù)據(jù)分配。

一個集群只能有16384個槽，編號0-16383（0-2^14-1）。這些槽會分配給集群中的所有主節(jié)點，分配策略沒有要求?？梢灾付男┚幪柕牟鄯峙浣o哪個主節(jié)點。集群會記錄節(jié)點和槽的對應(yīng)關(guān)系。解決了節(jié)點和槽的關(guān)系后，接下來就需要對key求哈希值，然后對16384取余，余數(shù)是幾key就落入對應(yīng)的槽里。slot = CRC16(key) % 16384。以槽為單位移動數(shù)據(jù)，因為槽的數(shù)目是固定的，處理起來比較容易，這樣數(shù)據(jù)移動問題就解決了。

        Redis 集群中內(nèi)置了 16384 個哈希槽，redis 會根據(jù)節(jié)點數(shù)量大致均等的將哈希槽映射到不同的節(jié)點。當需要在 Redis 集群中放置一個 key-value時，redis 先對 key 使用 crc16 算法算出一個結(jié)果，然后把結(jié)果對 16384 求余數(shù)，這樣每個 key 都會對應(yīng)一個編號在 0-16383 之間的哈希槽，也就是映射到某個節(jié)點上。如下代碼，key之A 、B在Node2， key之C落在Node3上

總結(jié)

到此這篇關(guān)于Redis數(shù)據(jù)庫分布式設(shè)計方案介紹的文章就介紹到這了,更多相關(guān)Redis分布式內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論