圖解分布式DB/redis的幾種路由算法（一致性哈希）

背景

隨著應(yīng)用的越做越大蒸痹，數(shù)據(jù)量越來越多，不論是MySQL數(shù)據(jù)庫的單庫單表還是單臺redis都無法滿足高并發(fā)的讀寫操作和大數(shù)據(jù)量的存儲功能咱扣，因此有了大家耳熟能詳?shù)?strong>分庫分表。

垂直拆分和水平拆分

垂直拆分，即拆分列查排，從業(yè)務(wù)上將原來一個(gè)表的信息拆到兩個(gè)表中，形象的理解為垂直的一把刀切開了表

image

水平拆分抄沮，即拆分行跋核，通過某種規(guī)則將一個(gè)表中的數(shù)據(jù)拆分到不同的表中，形象的理解為水平的一把刀切開了表

image

當(dāng)然垂直拆分和水平拆分的概念不是本文要討論的重點(diǎn)叛买，本文要討論的是水平拆分的規(guī)則砂代。水平拆分的本質(zhì)其實(shí)和分布式系統(tǒng)下微服務(wù)的思想不謀而合，微服務(wù)的出現(xiàn)筆者前文提到過是因?yàn)閱蝹€(gè)服務(wù)承載了太多的業(yè)務(wù)邏輯率挣，導(dǎo)致出現(xiàn)了諸如代碼邏輯龐大復(fù)雜刻伊、開發(fā)人員關(guān)系耦合、單點(diǎn)故障等問題。這些問題對于DB和redis同樣會有：

當(dāng)訪問請求越來越多時(shí)捶箱，單機(jī)的DB/redis無法分配足夠的線程抗住高并發(fā)的請求
當(dāng)數(shù)據(jù)量越來越大時(shí)智什，從一碗水中找一根針和從一片大海中找一根針的難度和耗時(shí)也是不一樣的，我們要做的是找到那個(gè)碗丁屎，然后從碗里撈針

大碗撈針

大海撈針

所以我們需要將DB/redis擴(kuò)展為多臺荠锭。

幾種分布式集群中的路由算法

相信前面的介紹已經(jīng)說明了水平拆分的必要性，現(xiàn)在的問題就是如何拆分晨川，按何種規(guī)則將不同的數(shù)據(jù)歸類到不同的mysql庫/mysql表/redis機(jī)器上证九。下面我們以userid作為key為例。

固定哈希

固定哈希很好理解础爬，筆者現(xiàn)在所在的部門數(shù)據(jù)庫的分庫分表邏輯就是簡單的 (userid % 32) ^ (userid >> 32)甫贯，取了userid的高32位和低32位進(jìn)行了與運(yùn)算。

image

這么做的好處是邏輯簡單看蚜，相信這也是很多公司db業(yè)務(wù)的分庫分表方法叫搁，如果能夠保證用戶的id能夠均勻分布在每個(gè)分片上。
缺點(diǎn)是伸縮性差供炎，當(dāng)需要新增服務(wù)時(shí)渴逻，新機(jī)器根本路由不到；當(dāng)需要下線服務(wù)時(shí)音诫，由于固定哈希必然會導(dǎo)致請求到該服務(wù)的請求失敗惨奕。

一致性哈希

一致性哈希帶來的最大變化就是把節(jié)點(diǎn)對應(yīng)的哈希值變成了一個(gè)范圍，可以將一致性哈希想象成一個(gè)環(huán)形的鐘表竭钝，現(xiàn)在我們在12點(diǎn)梨撞、4點(diǎn)、8點(diǎn)鐘反向分別有三臺機(jī)器香罐，這時(shí)候我們算出hash(key)之后就去找離它最近的機(jī)器節(jié)點(diǎn)

一致性哈希是一個(gè)鐘表

例如這里hash(key)=2卧波，則找到了4點(diǎn)鐘方向的節(jié)點(diǎn)

image

一致性哈希雖然能夠穩(wěn)定的將請求切換到新機(jī)器，但是它也有一些小缺陷庇茫。因?yàn)?hash取模算法得到的結(jié)果是隨機(jī)的港粱，我們并不能保證各個(gè)服務(wù)節(jié)點(diǎn)能均勻的分配到哈希環(huán)上，這就導(dǎo)致了經(jīng)典的熱點(diǎn)問題旦签，又叫數(shù)據(jù)傾斜問題查坪，例如如圖情況會導(dǎo)致8點(diǎn)鐘服務(wù)承受了過多的負(fù)載。

image

引入虛擬節(jié)點(diǎn)的一致性哈希

為了應(yīng)對上面的問題宁炫，我們引入了虛擬節(jié)點(diǎn)的概念偿曙，我們通過對每個(gè)機(jī)器映射出多個(gè)hash，

hashA = hash("192.168.0.1-A") % 32
hashB = hash("192.168.0.1-B") % 32
hashC = hash("192.168.0.1-C") % 32

從而實(shí)現(xiàn)一個(gè)機(jī)器在環(huán)上有多個(gè)虛擬節(jié)點(diǎn)淋淀，如圖

image

自定義計(jì)算方式

如上文所述遥昧，筆者所在的公司前期的分庫規(guī)則是固定哈希覆醇，但是隨后結(jié)合業(yè)務(wù)實(shí)際表現(xiàn)來看有部分用戶（稱為大戶）訪問量是小用戶的n倍，和普通用戶路由到一個(gè)db或redis中勢必會影響到普通用戶的讀寫炭臭，因此對于這些特殊的戶單獨(dú)做了一個(gè)規(guī)則路由到分片號為9999的特殊分片永脓。

$ip = \begin{cases} ip[userid \% 32],\quad userid\ not\ in\ big\ users \\ ip[9999], \quad userid\ in\ big\ users \end{cases}$

以上這種模式其實(shí)就是自定義計(jì)算方式。

reference

[1] 分布式系統(tǒng)中一致性哈希算法
[2] 大型網(wǎng)站系統(tǒng)與Java中間件開發(fā)實(shí)踐
[3] 一致哈希-維基百科

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者