解決的問(wèn)題

當(dāng)數(shù)據(jù)過(guò)多時(shí), 可以對(duì)數(shù)據(jù)進(jìn)行水平拆分, 比如有4個(gè)Cache cache0, cache1, cache2, cache3部署在不同的node上, 我們可以根據(jù)數(shù)據(jù)的特征(比如id)進(jìn)行hash, 來(lái)使數(shù)據(jù)品均分配在4個(gè)cache上.
然鵝, 當(dāng)我們想增加或減少一個(gè)node時(shí)候, 問(wèn)題就來(lái)了, rehash 需要大量的時(shí)間, 這段時(shí)間內(nèi)會(huì)導(dǎo)致數(shù)據(jù)無(wú)法被找到.
一致性Hash就是為了解決這個(gè)問(wèn)題

基本概念

可以想像一致性Hash 為一個(gè)換, 坐標(biāo)為 0 到 2^32 -1, 從 0 到 2^32 -1 為順時(shí)針, 而我們的節(jié)點(diǎn)就分布在這個(gè)環(huán)上(根據(jù)IP 或其他信息 進(jìn)行Hash), 當(dāng)查詢數(shù)據(jù)時(shí), 會(huì)先進(jìn)性Hash, 認(rèn)定改數(shù)據(jù)位于順指針?lè)较蛏险业降牡谝粋€(gè)節(jié)點(diǎn). 比如一個(gè)環(huán)為 A -> B -> C -> D -> A, 其中數(shù)據(jù)T hash 位于A B 之間, 則會(huì)在B上尋找數(shù)據(jù)T

這樣, 當(dāng)B 掛了的時(shí)候, 影響的只有 A->C, 而B(niǎo)->C, C->D, D->A不收影響, 同樣的, 如果我們想在 D -> A 之間加一個(gè)Node, 那么影響的只有D-> A, 而另外三個(gè)分段不收影響.

一致性Hash可能會(huì)造成數(shù)據(jù)不均勻的問(wèn)題, 比如當(dāng)節(jié)點(diǎn)很少的時(shí)候, 假定只有 A B 兩個(gè)節(jié)點(diǎn),
A->B->A, 那么 當(dāng) A -> B 范圍較小的時(shí)候, 有可能大量數(shù)據(jù)分散在 B -> A, 所以有虛擬節(jié)點(diǎn)的概念, A1->B1->A2->B2->A3->B3->A4->B4->A1, 這樣A1, A2, A3, A4會(huì)被定為到A

節(jié)點(diǎn)的添加與刪除

在D->A中添加 E 時(shí) 變?yōu)?D->E->A, 則需要對(duì)A進(jìn)行rehash, 將D到E的部分復(fù)制到E
若刪除E,則需要將E中的數(shù)據(jù)拷貝給A