??1 hash分區(qū)規(guī)則
?? 由于Redis Cluster（集群）采用哈希分區(qū)規(guī)則，所以先介紹下常見(jiàn)的哈希分區(qū)規(guī)則。常見(jiàn)的哈希規(guī)則：節(jié)點(diǎn)取余分區(qū)規(guī)則、一致性哈希分區(qū)（Consistent hashing）、虛擬槽（Virtual slot）分區(qū)。
??2 節(jié)點(diǎn)取余分區(qū)
?? 使用特定的數(shù)據(jù)，如Redis的鍵或用戶ID，再根據(jù)節(jié)點(diǎn)（運(yùn)行在集群模式下的Redis服務(wù)器）的數(shù)量N使用公式：hash(key) % N計(jì)算出hash值，用來(lái)決定數(shù)據(jù)存儲(chǔ)在哪個(gè)節(jié)點(diǎn)上。例如，將20個(gè)數(shù)據(jù)存儲(chǔ)在4個(gè)節(jié)點(diǎn)上：
?? 如果此時(shí)增加一個(gè)節(jié)點(diǎn)，那么經(jīng)過(guò)重新hash計(jì)算后得到的分布如下（其中數(shù)據(jù)1、2、3、20這4個(gè)數(shù)據(jù)存儲(chǔ)的位置沒(méi)有改變，其他的數(shù)據(jù)位置都發(fā)生了改變。）：
??節(jié)點(diǎn)取余分區(qū)缺點(diǎn)：在節(jié)點(diǎn)的數(shù)量變化時(shí)，如擴(kuò)容或收縮節(jié)點(diǎn)時(shí)，數(shù)據(jù)節(jié)點(diǎn)映射關(guān)系需要重新計(jì)算，會(huì)導(dǎo)致大量數(shù)據(jù)重新遷移。
?? 節(jié)點(diǎn)取余分區(qū)優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單。常用于數(shù)據(jù)庫(kù)分庫(kù)分表規(guī)則，通常先預(yù)先根據(jù)數(shù)據(jù)數(shù)量規(guī)劃好區(qū)數(shù)，保證可以支撐一段時(shí)間，再根據(jù)負(fù)載情況將數(shù)據(jù)遷移到其他數(shù)據(jù)庫(kù)中，擴(kuò)容時(shí)通常采用翻倍擴(kuò)容，這樣大約只需遷移一半的數(shù)據(jù)量，從而避免映射全部被打亂導(dǎo)致全量遷移的情況。
??2 一致性哈希分區(qū)
??一致性哈希分區(qū)實(shí)現(xiàn)思路是為系統(tǒng)中的每個(gè)節(jié)點(diǎn)分配一個(gè)token，范圍是0~232-1，這些token構(gòu)成一個(gè)哈希環(huán)。數(shù)據(jù)讀寫(xiě)執(zhí)行節(jié)點(diǎn)查找操作時(shí)，先根據(jù)key計(jì)算出哈希值，然后順時(shí)針找到第一個(gè)遇到的token節(jié)點(diǎn)。
??這種方式相對(duì)于節(jié)點(diǎn)取余的好處在于加入和刪除節(jié)點(diǎn)只影響哈希環(huán)中相鄰的節(jié)點(diǎn)，對(duì)其他節(jié)點(diǎn)無(wú)影響。
??如下圖表示新增一個(gè)節(jié)點(diǎn)，經(jīng)過(guò)hash計(jì)算出其位置為在節(jié)點(diǎn)2和節(jié)點(diǎn)3之間，它對(duì)數(shù)據(jù)分布影響的范圍只是節(jié)點(diǎn)3和節(jié)點(diǎn)4之間的綠色部分的數(shù)據(jù)無(wú)法命中，對(duì)其他的節(jié)點(diǎn)的無(wú)影響。
??考慮這樣的一種情況，如果只有3個(gè)節(jié)點(diǎn)，且節(jié)點(diǎn)在哈希環(huán)上的分布是可能是這個(gè)樣子的，即使數(shù)據(jù)分布的均勻，大量的數(shù)據(jù)存儲(chǔ)在節(jié)點(diǎn)0上，而節(jié)點(diǎn)1、2不會(huì)存儲(chǔ)多少數(shù)據(jù)，節(jié)點(diǎn)0的負(fù)載會(huì)很高，這種情況就是哈希傾斜性導(dǎo)致的。
??一致性哈希分區(qū)的缺點(diǎn)：
(1) 當(dāng)使用少量節(jié)點(diǎn)時(shí)，節(jié)點(diǎn)變化將大范圍的影響哈希環(huán)中的數(shù)據(jù)映射，因此這種方法不適合少量數(shù)據(jù)節(jié)點(diǎn)的分布式方案。
(2) 加減節(jié)點(diǎn)會(huì)造成哈希環(huán)中的部分?jǐn)?shù)據(jù)無(wú)法命中，需要手動(dòng)處理這部分?jǐn)?shù)據(jù)。
(3) 由于哈希傾斜性，當(dāng)數(shù)據(jù)節(jié)點(diǎn)較少時(shí)，往往導(dǎo)致某個(gè)節(jié)點(diǎn)負(fù)載過(guò)大而其他節(jié)點(diǎn)負(fù)載過(guò)小，負(fù)載不均衡。
??3 虛擬槽分區(qū)
??Redis Cluster采用的就是虛擬槽分區(qū)。虛擬槽分區(qū)巧妙的使用了哈?？臻g，使用分散度良好的哈希函數(shù)將所有的數(shù)據(jù)映射到一個(gè)固定范圍的整數(shù)集合中，整數(shù)定義為槽（slot）。這個(gè)范圍一般遠(yuǎn)遠(yuǎn)大于節(jié)點(diǎn)數(shù)，這是為了消除哈希的傾斜性，便于數(shù)據(jù)拆分和擴(kuò)展。例如Redis Cluster槽的范圍是0~16383。槽是集群內(nèi)數(shù)據(jù)管理和遷移的基本單位，每個(gè)節(jié)點(diǎn)都會(huì)負(fù)責(zé)一定數(shù)量的槽。
??如在Redis中，假設(shè)有5個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)平均負(fù)責(zé)3276個(gè)槽。
??由于采用了分散性較好的哈希函數(shù)，所有的數(shù)據(jù)大致均勻分布在0~16383各個(gè)槽中，計(jì)算公式為slot = CRC16(key) & 16383，當(dāng)要操作數(shù)據(jù)時(shí)，只需要計(jì)算出相應(yīng)的槽，并根據(jù)槽即可找到對(duì)應(yīng)的節(jié)點(diǎn)。
??虛擬槽分布的特點(diǎn)：
(1) 解耦數(shù)據(jù)和節(jié)點(diǎn)之間的關(guān)系，簡(jiǎn)化了節(jié)點(diǎn)的擴(kuò)容和收縮。
(2) 解決了普通一致性哈希分區(qū)只有少量節(jié)點(diǎn)負(fù)載不均衡問(wèn)題。
(3) 支持節(jié)點(diǎn)、槽、鍵之間的映射查詢，用于數(shù)據(jù)路由。
??4 小結(jié)
??(1) 常見(jiàn)的哈希分區(qū)規(guī)則有：節(jié)點(diǎn)取余分區(qū)、一致性哈希分區(qū)和虛擬槽分區(qū)。
??(2) Redis Cluster數(shù)據(jù)分區(qū)規(guī)則采用虛擬槽方式，所有的鍵映射到16384個(gè)槽中，每個(gè)節(jié)點(diǎn)負(fù)責(zé)一部分槽和相關(guān)數(shù)據(jù)，實(shí)現(xiàn)數(shù)據(jù)和請(qǐng)求的負(fù)載均衡。
??本文完
??注：本文參考《Redis開(kāi)發(fā)與運(yùn)維》，如發(fā)現(xiàn)錯(cuò)誤，請(qǐng)指正！
