• 讀后感

逐字逐句看完《大型分布式網(wǎng)站架構(gòu)設(shè)計(jì)與實(shí)踐》第2章，意猶未盡！如標(biāo)題所言，這是一本“真材實(shí)料的分布式資料”，它與我看過(guò)的分布式書(shū)籍（如《大型網(wǎng)站系統(tǒng)與Java中間件實(shí)踐》）不同，本書(shū) 重技術(shù)兼并理論 ，給了新人入手的方向。

?

我最最感動(dòng)的是書(shū)中介紹了很多分布式的“干貨”：分布式緩存可以用memcache、數(shù)據(jù)庫(kù)水平/垂直拆分技術(shù)、分布式存儲(chǔ)可以HBase/Redis等、消息通道可以用ActiveMQ、搜索引擎Lucene/Solr等。當(dāng)然每一種技術(shù)都不是一本書(shū)能說(shuō)完的，作者至少給了我們學(xué)習(xí)的方向，我很感動(dòng)。

?

這只是第2章，后面還會(huì)有我很感興趣的日志處理、數(shù)據(jù)倉(cāng)庫(kù)、負(fù)載均衡等，如果沒(méi)有中獎(jiǎng)，我也會(huì)去買(mǎi)一本學(xué)習(xí)。 這是一本適合入門(mén)和進(jìn)階的書(shū)籍 ，有介紹分布式的理論，也同時(shí)介紹每種技術(shù)用到的具體實(shí)現(xiàn)方式，可以讓我們少走彎路。

?

書(shū)中介紹了 一致性hash算法(consistent hashing) ，我個(gè)人也非常佩服這個(gè)經(jīng)典算法，所以后面對(duì)它進(jìn)行一些介紹總結(jié)。

?

• 一致性算法

?

背景：所謂分布式緩存不是說(shuō)每臺(tái)服務(wù)器都存儲(chǔ)所有的緩存，而是讓每臺(tái)服務(wù)器均分存儲(chǔ)緩存。要實(shí)現(xiàn)服務(wù)器的均分及更新就要注意兩點(diǎn)： ①用什么算法去均分才能快速找到指定緩存；②當(dāng)緩存出現(xiàn)新增、刪除時(shí)如何將變化的緩存同步到對(duì)應(yīng)服務(wù)器也是一個(gè)關(guān)鍵。

?

傳統(tǒng)算法：最傳統(tǒng)的算法是通過(guò)“ 緩存總數(shù)/服務(wù)器數(shù)量 ”的形式來(lái) 均分 ，每一個(gè)緩存都有其唯一的Hash值（數(shù)字），要找到指定緩存在哪臺(tái)服務(wù)器上可通過(guò) hash(key)%N取余 的形式判斷，這樣基本能達(dá)到平衡。

傳統(tǒng)的算法查找緩存運(yùn)行模式如下圖所示，當(dāng)客戶端需要某個(gè)緩存的時(shí)候，首先會(huì)向緩存索引（菱形結(jié)構(gòu)）發(fā)出請(qǐng)求，此時(shí)索引器通過(guò)算法（hash(key)%N）取余的形式找到余數(shù)對(duì)應(yīng)的緩存服務(wù)器并取得該緩存返回。

?

這種算法能達(dá)到緩存的第一個(gè)條件“用什么算法去均分才能快速找到指定緩存”，但是卻在第二個(gè)條件上碰了壁“當(dāng)緩存出現(xiàn)新增、刪除時(shí)如何將變化的緩存同步到對(duì)應(yīng)服務(wù)器”。假設(shè)server1突然宕機(jī)，該服務(wù)器上的所有緩存失效，這時(shí)又得重新平均計(jì)算緩存并且平均放到剩余的幾臺(tái)服務(wù)器上。 重置緩存是需要花費(fèi)時(shí)間的 ，這時(shí)如果有用戶請(qǐng)求則無(wú)法取到緩存，取而代之的是從數(shù)據(jù)源讀數(shù)據(jù)，一大波數(shù)據(jù)請(qǐng)求不斷沖擊服務(wù)器，很可能造成系統(tǒng)崩潰，這也就是所謂的“ 雪崩效應(yīng) ”。

?

一致性哈希（consistent hashing）：一致性哈希算法在1997年由麻省理工學(xué)院提出，設(shè)計(jì)目標(biāo)是為了解決因特網(wǎng)中的熱點(diǎn)問(wèn)題，目前在集群緩存應(yīng)用中得到非常高的肯定。

?

下圖所示為一致性哈希的理論原理。

>>首先要有一個(gè)首位相接的圓環(huán)，這個(gè)圓環(huán)大小是有科學(xué)依據(jù)的：一般一個(gè)緩存對(duì)象的hash值是32位的，那么理論上就可以存在2的32次方個(gè)（也就是從數(shù)字0~2的32次方-1）不同的哈希值，那么只需要將0和2的32次方-1首尾相連就成了一個(gè) 數(shù)字圓環(huán) 。

>>假設(shè)有9個(gè)緩存，這時(shí)將其進(jìn)行hash計(jì)算成一個(gè)數(shù)字，再根據(jù)他們的哈希值放到圓環(huán)對(duì)應(yīng)數(shù)字點(diǎn)位上，這樣9個(gè)緩存就已經(jīng)有自己位置（如下圖粉色小圓點(diǎn)即是 緩存哈希 ）。

>>假設(shè)有4臺(tái)緩存服務(wù)器，我們也對(duì) 服務(wù)器進(jìn)行哈希計(jì)算 生成32位數(shù)字，這時(shí)再將服務(wù)器放在圓環(huán)對(duì)應(yīng)位置上（如下圖淡藍(lán)色圓圈）。這樣就組成了緩存與緩存服務(wù)器的物理結(jié)構(gòu)圖。[順便提一下服務(wù)器的hash計(jì)算，一般的方法可以使用機(jī)器的IP地址或者機(jī)器名作為hash輸入。]

>>如何將緩存映射到對(duì)應(yīng)服務(wù)器上呢？一致性哈希算法采用 單向就近原則 ：在這個(gè)環(huán)形空間中，如果沿著順時(shí)針?lè)较驈木彺婀３霭l(fā)，直到遇見(jiàn)一個(gè)服務(wù)器Node，那么就將該對(duì)象存儲(chǔ)在這個(gè)Node上，因?yàn)榫彺婀：头?wù)器的hash值是固定的，因此這個(gè)緩存必然是唯一和確定的。這樣就能很方便根據(jù)哈希值找到對(duì)應(yīng)服務(wù)器下的緩存對(duì)象。

?

用這種方式只需要維護(hù)node的hash值即可找到對(duì)應(yīng)緩存， 非?？焖俜奖? 。而且假設(shè)有一個(gè)node宕機(jī)，則只需要將它維護(hù)的緩存hash放入下一個(gè)Node中即可；假設(shè)有新緩存加入，則只需要根據(jù)其hash值找最近的Node即可， 緩存變化影響非常小 。這是模式滿足了前面提到的分布式緩存第二點(diǎn)要求“當(dāng)緩存出現(xiàn)新增、刪除時(shí)如何將變化的緩存同步到對(duì)應(yīng)服務(wù)器”。

?

當(dāng)然，上面描繪的只是一種理想的情況，各個(gè)節(jié)點(diǎn)在環(huán)上分布得十分均勻。正常情況下，當(dāng)節(jié)點(diǎn)數(shù)量較少時(shí)，節(jié)點(diǎn)的分布可能十分不均勻，從而導(dǎo)致數(shù)據(jù)訪問(wèn)的傾斜，大量的 key 被映射到同一臺(tái)服務(wù)器上。為了避免這種情況的出現(xiàn)，可以引入 虛擬節(jié)點(diǎn)機(jī)制 ，對(duì)每一個(gè)服務(wù)器節(jié)點(diǎn)都計(jì)算多個(gè) Hash值，每一個(gè)Hash值都對(duì)應(yīng)環(huán)上一個(gè)節(jié)點(diǎn)的位置，該節(jié)點(diǎn)稱為虛擬節(jié)點(diǎn)，而key 的映射方式不變，只是多了一步從虛擬節(jié)點(diǎn)再映射到真實(shí)節(jié)點(diǎn)的過(guò)程。這樣，如果虛擬節(jié)點(diǎn)的數(shù)量足夠多，即使只有很少的實(shí)際節(jié)點(diǎn)， 也能夠使 key分布得相對(duì)均衡 。?

?

這就是一致性哈希算法的原理，理論非常合理，所以才會(huì)受到這么廣泛的應(yīng)用，希望能給大家有所幫助。