- 讀后感
逐字逐句看完《大型分布式網(wǎng)站架構(gòu)設(shè)計與實(shí)踐》第2章,意猶未盡!如標(biāo)題所言,這是一本“真材實(shí)料的分布式資料”,它與我看過的分布式書籍(如《大型網(wǎng)站系統(tǒng)與Java中間件實(shí)踐》)不同,本書 重技術(shù)兼并理論 ,給了新人入手的方向。
?
我最最感動的是書中介紹了很多分布式的“干貨”:分布式緩存可以用memcache、數(shù)據(jù)庫水平/垂直拆分技術(shù)、分布式存儲可以HBase/Redis等、消息通道可以用ActiveMQ、搜索引擎Lucene/Solr等。當(dāng)然每一種技術(shù)都不是一本書能說完的,作者至少給了我們學(xué)習(xí)的方向,我很感動。
?
這只是第2章,后面還會有我很感興趣的日志處理、數(shù)據(jù)倉庫、負(fù)載均衡等,如果沒有中獎,我也會去買一本學(xué)習(xí)。 這是一本適合入門和進(jìn)階的書籍 ,有介紹分布式的理論,也同時介紹每種技術(shù)用到的具體實(shí)現(xiàn)方式,可以讓我們少走彎路。
?
書中介紹了 一致性hash算法(consistent hashing) ,我個人也非常佩服這個經(jīng)典算法,所以后面對它進(jìn)行一些介紹總結(jié)。
?
- 一致性算法
?
背景:所謂分布式緩存不是說每臺服務(wù)器都存儲所有的緩存,而是讓每臺服務(wù)器均分存儲緩存。要實(shí)現(xiàn)服務(wù)器的均分及更新就要注意兩點(diǎn): ①用什么算法去均分才能快速找到指定緩存;②當(dāng)緩存出現(xiàn)新增、刪除時如何將變化的緩存同步到對應(yīng)服務(wù)器也是一個關(guān)鍵。
?
傳統(tǒng)算法:最傳統(tǒng)的算法是通過“ 緩存總數(shù)/服務(wù)器數(shù)量 ”的形式來 均分 ,每一個緩存都有其唯一的Hash值(數(shù)字),要找到指定緩存在哪臺服務(wù)器上可通過 hash(key)%N取余 的形式判斷,這樣基本能達(dá)到平衡。
傳統(tǒng)的算法查找緩存運(yùn)行模式如下圖所示,當(dāng)客戶端需要某個緩存的時候,首先會向緩存索引(菱形結(jié)構(gòu))發(fā)出請求,此時索引器通過算法(hash(key)%N)取余的形式找到余數(shù)對應(yīng)的緩存服務(wù)器并取得該緩存返回。
這種算法能達(dá)到緩存的第一個條件“用什么算法去均分才能快速找到指定緩存”,但是卻在第二個條件上碰了壁“當(dāng)緩存出現(xiàn)新增、刪除時如何將變化的緩存同步到對應(yīng)服務(wù)器”。假設(shè)server1突然宕機(jī),該服務(wù)器上的所有緩存失效,這時又得重新平均計算緩存并且平均放到剩余的幾臺服務(wù)器上。 重置緩存是需要花費(fèi)時間的 ,這時如果有用戶請求則無法取到緩存,取而代之的是從數(shù)據(jù)源讀數(shù)據(jù),一大波數(shù)據(jù)請求不斷沖擊服務(wù)器,很可能造成系統(tǒng)崩潰,這也就是所謂的“ 雪崩效應(yīng) ”。
?
一致性哈希(consistent hashing):一致性哈希算法在1997年由麻省理工學(xué)院提出,設(shè)計目標(biāo)是為了解決因特網(wǎng)中的熱點(diǎn)問題,目前在集群緩存應(yīng)用中得到非常高的肯定。
?
下圖所示為一致性哈希的理論原理。
>>首先要有一個首位相接的圓環(huán),這個圓環(huán)大小是有科學(xué)依據(jù)的:一般一個緩存對象的hash值是32位的,那么理論上就可以存在2的32次方個(也就是從數(shù)字0~2的32次方-1)不同的哈希值,那么只需要將0和2的32次方-1首尾相連就成了一個 數(shù)字圓環(huán) 。
>>假設(shè)有9個緩存,這時將其進(jìn)行hash計算成一個數(shù)字,再根據(jù)他們的哈希值放到圓環(huán)對應(yīng)數(shù)字點(diǎn)位上,這樣9個緩存就已經(jīng)有自己位置(如下圖粉色小圓點(diǎn)即是 緩存哈希 )。
>>假設(shè)有4臺緩存服務(wù)器,我們也對 服務(wù)器進(jìn)行哈希計算 生成32位數(shù)字,這時再將服務(wù)器放在圓環(huán)對應(yīng)位置上(如下圖淡藍(lán)色圓圈)。這樣就組成了緩存與緩存服務(wù)器的物理結(jié)構(gòu)圖。[順便提一下服務(wù)器的hash計算,一般的方法可以使用機(jī)器的IP地址或者機(jī)器名作為hash輸入。]
>>如何將緩存映射到對應(yīng)服務(wù)器上呢?一致性哈希算法采用 單向就近原則 :在這個環(huán)形空間中,如果沿著順時針方向從緩存哈希出發(fā),直到遇見一個服務(wù)器Node,那么就將該對象存儲在這個Node上,因?yàn)榫彺婀:头?wù)器的hash值是固定的,因此這個緩存必然是唯一和確定的。這樣就能很方便根據(jù)哈希值找到對應(yīng)服務(wù)器下的緩存對象。
用這種方式只需要維護(hù)node的hash值即可找到對應(yīng)緩存, 非常快速方便 。而且假設(shè)有一個node宕機(jī),則只需要將它維護(hù)的緩存hash放入下一個Node中即可;假設(shè)有新緩存加入,則只需要根據(jù)其hash值找最近的Node即可, 緩存變化影響非常小 。這是模式滿足了前面提到的分布式緩存第二點(diǎn)要求“當(dāng)緩存出現(xiàn)新增、刪除時如何將變化的緩存同步到對應(yīng)服務(wù)器”。
?
當(dāng)然,上面描繪的只是一種理想的情況,各個節(jié)點(diǎn)在環(huán)上分布得十分均勻。正常情況下,當(dāng)節(jié)點(diǎn)數(shù)量較少時,節(jié)點(diǎn)的分布可能十分不均勻,從而導(dǎo)致數(shù)據(jù)訪問的傾斜,大量的 key 被映射到同一臺服務(wù)器上。為了避免這種情況的出現(xiàn),可以引入 虛擬節(jié)點(diǎn)機(jī)制 ,對每一個服務(wù)器節(jié)點(diǎn)都計算多個 Hash值,每一個Hash值都對應(yīng)環(huán)上一個節(jié)點(diǎn)的位置,該節(jié)點(diǎn)稱為虛擬節(jié)點(diǎn),而key 的映射方式不變,只是多了一步從虛擬節(jié)點(diǎn)再映射到真實(shí)節(jié)點(diǎn)的過程。這樣,如果虛擬節(jié)點(diǎn)的數(shù)量足夠多,即使只有很少的實(shí)際節(jié)點(diǎn), 也能夠使 key分布得相對均衡 。?
?
這就是一致性哈希算法的原理,理論非常合理,所以才會受到這么廣泛的應(yīng)用,希望能給大家有所幫助。
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯(lián)系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點(diǎn)擊下面給點(diǎn)支持吧,站長非常感激您!手機(jī)微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點(diǎn)擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
