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

1 哈希取余分區(qū)

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

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

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

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

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

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

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

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

2.2 節(jié)點(diǎn)映射

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

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

2.3 落鍵規(guī)則

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

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

 2.4 優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：容錯(cuò)性和擴(kuò)展性

容錯(cuò)性：

        假設(shè)Node C宕機(jī)，可以看到此時(shí)對(duì)象A、B、D不會(huì)受到影響，只有C對(duì)象被重定位到Node D。一般的，在一致性Hash算法中，如果一臺(tái)服務(wù)器不可用，則 受影響的數(shù)據(jù)僅僅是此服務(wù)器到其環(huán)空間中前一臺(tái)服務(wù)器（即沿著逆時(shí)針?lè)较蛐凶哂龅降牡谝慌_(tái)服務(wù)器）之間數(shù)據(jù) ，其它不會(huì)受到影響。簡(jiǎn)單說(shuō)，就是C掛了，受到影響的只是B、C之間的數(shù)據(jù)，并且這些數(shù)據(jù)會(huì)轉(zhuǎn)移到D進(jìn)行存儲(chǔ)。

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

        一致性Hash算法在服務(wù) 節(jié)點(diǎn)太少時(shí) ，容易因?yàn)楣?jié)點(diǎn)分布不均勻而造成 數(shù)據(jù)傾斜 （被緩存的對(duì)象大部分集中緩存在某一臺(tái)服務(wù)器上）問(wèn)題，

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

3 哈希槽計(jì)算

為了解決一致性哈希算法的傾斜問(wèn)題

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

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

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

一個(gè)集群只能有16384個(gè)槽，編號(hào)0-16383（0-2^14-1）。這些槽會(huì)分配給集群中的所有主節(jié)點(diǎn)，分配策略沒(méi)有要求。可以指定哪些編號(hào)的槽分配給哪個(gè)主節(jié)點(diǎn)。集群會(huì)記錄節(jié)點(diǎn)和槽的對(duì)應(yīng)關(guān)系。解決了節(jié)點(diǎn)和槽的關(guān)系后，接下來(lái)就需要對(duì)key求哈希值，然后對(duì)16384取余，余數(shù)是幾key就落入對(duì)應(yīng)的槽里。slot = CRC16(key) % 16384。以槽為單位移動(dòng)數(shù)據(jù)，因?yàn)椴鄣臄?shù)目是固定的，處理起來(lái)比較容易，這樣數(shù)據(jù)移動(dòng)問(wèn)題就解決了。

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

總結(jié)

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

最新評(píng)論