背景
隨著memcache和redis的出現(xiàn)替梨，更多人認(rèn)識(shí)到了一致性哈希钓试。
一致性哈希用于解決分布式緩存系統(tǒng)中的數(shù)據(jù)選擇節(jié)點(diǎn)存儲(chǔ)問題和數(shù)據(jù)選擇節(jié)點(diǎn)讀取問題以及在增刪節(jié)點(diǎn)后減少數(shù)據(jù)緩存的消失范疇装黑，防止雪崩的發(fā)生。
哈希槽是在redis cluster集群方案中采用的弓熏，redis cluster集群沒有采用一致性哈希方案恋谭，而是采用數(shù)據(jù)分片中的哈希槽來(lái)進(jìn)行數(shù)據(jù)存儲(chǔ)與讀取的。
哈希
哈希算法最重要的特點(diǎn)就是：
- 相同的輸入一定得到相同的輸出挽鞠；
- 不同的輸入大概率得到不同的輸出疚颊。
哈希碰撞
哈希碰撞是指，兩個(gè)不同的輸入得到了相同的輸出：
"AaAaAa".hashCode(); // 0x7460e8c0
"BBAaBB".hashCode(); // 0x7460e8c0
有童鞋會(huì)問：碰撞能不能避免信认？答案是不能材义。碰撞是一定會(huì)出現(xiàn)的，因?yàn)檩敵龅淖止?jié)長(zhǎng)度是固定的嫁赏，String的hashCode()輸出是4字節(jié)整數(shù)其掂，最多只有4294967296種輸出，但輸入的數(shù)據(jù)長(zhǎng)度是不固定的潦蝇，有無(wú)數(shù)種輸入款熬。所以，哈希算法是把一個(gè)無(wú)限的輸入集合映射到一個(gè)有限的輸出集合护蝶，必然會(huì)產(chǎn)生碰撞华烟。
碰撞不可怕，我們擔(dān)心的不是碰撞持灰，而是碰撞的概率盔夜，因?yàn)榕鲎哺怕实母叩完P(guān)系到哈希算法的安全性。一個(gè)安全的哈希算法必須滿足：
- 碰撞概率低堤魁；
- 不能猜測(cè)輸出喂链。
不能猜測(cè)輸出是指，輸入的任意一個(gè)bit的變化會(huì)造成輸出完全不同妥泉，這樣就很難從輸出反推輸入（只能依靠暴力窮舉）椭微。假設(shè)一種哈希算法有如下規(guī)律：
hashA("java001") = "123456"
hashA("java002") = "123457"
hashA("java003") = "123458"
那么很容易從輸出123459反推輸入，這種哈希算法就不安全盲链。安全的哈希算法從輸出是看不出任何規(guī)律的：
hashB("java001") = "123456"
hashB("java002") = "580271"
hashB("java003") = ???
常用的哈希算法有：
| 算法 | 輸出長(zhǎng)度（位） | 輸出長(zhǎng)度（字節(jié)) |
|---|---|---|
| MD5 | 128 bits | 16 bytes |
| SHA-1 | 160 bits | 20 bytes |
| RipeMD-160 | 160 bits | 20 bytes |
| SHA-256 | 256 bits | 32 bytes |
| SHA-512 | 512 bits | 64 bytes |
根據(jù)碰撞概率蝇率，哈希算法的輸出長(zhǎng)度越長(zhǎng)，就越難產(chǎn)生碰撞刽沾，也就越安全本慕。
哈希算法的用途
- 判斷是否篡改
因?yàn)橄嗤妮斎胗肋h(yuǎn)會(huì)得到相同的輸出，因此侧漓，如果輸入被修改了锅尘，得到的輸出就會(huì)不同。
我們?cè)赿ocker hup上隨便找一個(gè)鏡像布蔗，看到采用的hash算法為SHA-256：
如何判斷下載到本地的軟件是原始的藤违、未經(jīng)篡改的文件浪腐？
我們只需要自己計(jì)算一下本地文件的哈希值，再與官網(wǎng)公開的哈希值對(duì)比顿乒，如果相同议街，說明文件下載正確，否則淆游，說明文件已被篡改傍睹。
- 密碼加密
在登錄系統(tǒng)中我們通常使用md5方式加密用戶密碼，這樣當(dāng)數(shù)據(jù)庫(kù)泄漏之后犹菱，也看不到用戶的密碼拾稳。
因?yàn)橄嗤妮斎胗肋h(yuǎn)會(huì)得到相同的輸出，因此腊脱，對(duì)用戶輸入的密碼進(jìn)行MD5加密并與數(shù)據(jù)庫(kù)存儲(chǔ)的MD5對(duì)比访得，如果一致，說明口令正確陕凹，否則悍抑，口令錯(cuò)誤
介紹了這么多，言歸正傳杜耙，介紹一致性哈希搜骡。
一致性哈希
一致性hash是一個(gè)0-2^32的閉合圓，占用4個(gè)字節(jié)（擁有2^23個(gè)桶空間佑女，每個(gè)桶里面可以存儲(chǔ)很多數(shù)據(jù)记靡，可以理解為s3的存儲(chǔ)桶）所有節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)都是不一樣的。計(jì)算一致性哈希是采用的是如下步驟：
- 對(duì)節(jié)點(diǎn)進(jìn)行hash,通常使用其節(jié)點(diǎn)的ip或者是具有唯一標(biāo)示的數(shù)據(jù)進(jìn)行hash(ip),將其值分布在這個(gè)閉合圓上团驱。
- 將存儲(chǔ)的key進(jìn)行hash(key),然后將其值要分布在這個(gè)閉合圓上摸吠。
- 從hash(key)在圓上映射的位置開始順時(shí)針方向找到的一個(gè)節(jié)點(diǎn)即為存儲(chǔ)key的節(jié)點(diǎn)。如果到圓上的0處都未找到節(jié)點(diǎn)嚎花，那么0位置后的順時(shí)針方向的第一個(gè)節(jié)點(diǎn)就是key的存儲(chǔ)節(jié)點(diǎn)寸痢。
添加節(jié)點(diǎn)帶來(lái)的影響
圖1為一致性hash的分布情況，箭頭指向key的分布情況紊选。
如果現(xiàn)在node2和node4節(jié)點(diǎn)中間增加一個(gè)node5節(jié)點(diǎn)啼止，那么在node4和node2之間的這些數(shù)據(jù)要存儲(chǔ)的節(jié)點(diǎn)就會(huì)有所變化。在圖中的黃色區(qū)域的數(shù)據(jù)將會(huì)從原來(lái)的node4節(jié)點(diǎn)挪到node5節(jié)點(diǎn)兵罢。
刪除節(jié)點(diǎn)帶來(lái)的影響
以圖1為基準(zhǔn)族壳，刪除了node2節(jié)點(diǎn)后，原本在node2節(jié)點(diǎn)上的數(shù)據(jù)就會(huì)被重新定位node4上趣些。這樣就產(chǎn)生一個(gè)影響：原來(lái)node2的數(shù)據(jù)轉(zhuǎn)移到node4上，這樣node4的內(nèi)存使用率會(huì)驟增贰您，如果node2上存在熱點(diǎn)數(shù)據(jù)坏平，node4會(huì)扛不住甚至?xí)赡軖斓袈２伲瑨斓糁髷?shù)據(jù)又轉(zhuǎn)移給node3,如此循環(huán)會(huì)造成所有節(jié)點(diǎn)崩潰，也就是前面所說的雪崩的情況舶替。
節(jié)點(diǎn)太少造成的影響
節(jié)點(diǎn)太少的話可能造成數(shù)據(jù)傾斜的情況令境，如圖中中只有倆節(jié)點(diǎn)，可能會(huì)造成大量數(shù)據(jù)存放在node A節(jié)點(diǎn)上顾瞪，而node B節(jié)點(diǎn)存儲(chǔ)很少的數(shù)據(jù)舔庶。
虛擬節(jié)點(diǎn)
為了解決雪崩現(xiàn)象和數(shù)據(jù)傾斜現(xiàn)象，提出了虛擬節(jié)點(diǎn)這個(gè)概念陈醒。就是將真實(shí)節(jié)點(diǎn)計(jì)算多個(gè)哈希形成多個(gè)虛擬節(jié)點(diǎn)并放置到哈希環(huán)上惕橙，定位算法不變，只是多了一步虛擬節(jié)點(diǎn)到真實(shí)節(jié)點(diǎn)映射的過程
以雪崩現(xiàn)象來(lái)說明:如下圖節(jié)點(diǎn)real1節(jié)點(diǎn)又倆個(gè)虛擬節(jié)點(diǎn)v100和v101,real2有倆個(gè)虛擬節(jié)點(diǎn)v200和v201钉跷，real3節(jié)點(diǎn)有v300和v301倆個(gè)虛擬節(jié)點(diǎn)弥鹦。
當(dāng)real1節(jié)點(diǎn)掛掉后，v100和v101節(jié)點(diǎn)也會(huì)隨即消失爷辙，這時(shí)k1數(shù)據(jù)就會(huì)被分配到v301上彬坏，k4就會(huì)被分配到了v200上，這就解決了雪崩的問題膝晾，當(dāng)某個(gè)節(jié)點(diǎn)宕機(jī)后栓始，其數(shù)據(jù)并沒有全部分配給某一個(gè)節(jié)點(diǎn)，而是被分到了多個(gè)節(jié)點(diǎn)血当。
正因?yàn)榧尤肓颂摂M節(jié)點(diǎn)機(jī)制幻赚，數(shù)據(jù)傾斜的問題也隨之解決
注意：
- 真實(shí)節(jié)點(diǎn)不放置到哈希環(huán)上，只有虛擬節(jié)點(diǎn)才會(huì)放上去歹颓。
- 為什么要使用閉合的哈希環(huán)?舉個(gè)例子坯屿，如果在2^23-3處有一個(gè)key,而2^23-3~2^23處并沒有節(jié)點(diǎn),那么這個(gè)key該存在哪里節(jié)點(diǎn)呢？說到這里你應(yīng)該明白了吧巍扛。
- 一致性哈希使用的32個(gè)bits领跛，4個(gè)bytes，肯定也會(huì)有哈希碰撞的問題存在撤奸。
哈希槽
redis cluster采用數(shù)據(jù)分片的哈希槽來(lái)進(jìn)行數(shù)據(jù)存儲(chǔ)和數(shù)據(jù)的讀取吠昭。redis cluster一共有2^14（16384）個(gè)槽，所有的master節(jié)點(diǎn)都會(huì)有一個(gè)槽區(qū)比如0～1000胧瓜，槽數(shù)是可以遷移的矢棚。master節(jié)點(diǎn)的slave節(jié)點(diǎn)不分配槽，只擁有讀權(quán)限府喳。但是注意在代碼中redis cluster執(zhí)行讀寫操作的都是master節(jié)點(diǎn)蒲肋，并不是你想 的讀是從節(jié)點(diǎn)，寫是主節(jié)點(diǎn)。第一次新建redis cluster時(shí)兜粘，16384個(gè)槽是被master節(jié)點(diǎn)均勻分布的申窘。
和一致性哈希相比
- 它并不是閉合的，key的定位規(guī)則是根據(jù)CRC-16(key)%16384的值來(lái)判斷屬于哪個(gè)槽區(qū)孔轴，從而判斷該key屬于哪個(gè)節(jié)點(diǎn)剃法，而一致性哈希是根據(jù)hash(key)的值來(lái)順時(shí)針找第一個(gè)hash(ip)的節(jié)點(diǎn)，從而確定key存儲(chǔ)在哪個(gè)節(jié)點(diǎn)路鹰。
- 一致性哈希是創(chuàng)建虛擬節(jié)點(diǎn)來(lái)實(shí)現(xiàn)節(jié)點(diǎn)宕機(jī)后的數(shù)據(jù)轉(zhuǎn)移并保證數(shù)據(jù)的安全性和集群的可用性的贷洲。redis cluster是采用master節(jié)點(diǎn)有多個(gè)slave節(jié)點(diǎn)機(jī)制來(lái)保證數(shù)據(jù)的完整性的,master節(jié)點(diǎn)寫入數(shù)據(jù)，slave節(jié)點(diǎn)同步數(shù)據(jù)晋柱。當(dāng)master節(jié)點(diǎn)掛機(jī)后优构，slave節(jié)點(diǎn)會(huì)通過選舉機(jī)制選舉出一個(gè)節(jié)點(diǎn)變成master節(jié)點(diǎn)，實(shí)現(xiàn)高可用趣斤。但是這里有一點(diǎn)需要考慮俩块，如果master節(jié)點(diǎn)存在熱點(diǎn)緩存，某一個(gè)時(shí)刻某個(gè)key的訪問急劇增高浓领，這時(shí)該mater節(jié)點(diǎn)可能操勞過度而死玉凯，隨后從節(jié)點(diǎn)選舉為主節(jié)點(diǎn)后，同樣宕機(jī)联贩，一次類推漫仆，造成緩存雪崩。解決這個(gè)問題請(qǐng)看我的另一篇文章如何應(yīng)對(duì)熱點(diǎn)緩存問題
- 擴(kuò)容和縮容
可以看到一致性哈希算法在新增和刪除節(jié)點(diǎn)后泪幌，數(shù)據(jù)會(huì)按照順時(shí)針來(lái)重新分布節(jié)點(diǎn)盲厌。而redis cluster的新增和刪除節(jié)點(diǎn)都需要手動(dòng)來(lái)分配槽區(qū)。
-
新建master節(jié)點(diǎn)
使用redis-trib.rb工具來(lái)創(chuàng)建master節(jié)點(diǎn)./redis-trib.rb add-node 172.60.0.7:6379 172.60.0.5:6379
注釋：192.168.10.219:6378是新增的節(jié)點(diǎn)
192.168.10.219:6379集群任一個(gè)舊節(jié)點(diǎn)
注意：新建的master節(jié)點(diǎn)是沒有槽區(qū)的祸泪，需要給master節(jié)點(diǎn)分配槽吗浩，不然緩存無(wú)法命中。分配槽的方法自行百度没隘。
刪除master節(jié)點(diǎn)
1.如果主節(jié)點(diǎn)有從節(jié)點(diǎn)懂扼，需要將從節(jié)點(diǎn)轉(zhuǎn)移到別的主節(jié)點(diǎn)上。
2.轉(zhuǎn)移后 如果主節(jié)點(diǎn)有哈希槽右蒲，將哈希槽轉(zhuǎn)移到別的master節(jié)點(diǎn)上阀湿，然后在刪除master節(jié)點(diǎn)
注意：redis cluster的動(dòng)態(tài)擴(kuò)容和縮容并不會(huì)影響集群的使用。
參考文章
一致性哈希原理
一致性hash介紹及使用原理
