• 讀后感

逐字逐句看完《大型分布式網站架構設計與實踐》第2章，意猶未盡！如標題所言，這是一本“真材實料的分布式資料”，它與我看過的分布式書籍（如《大型網站系統與Java中間件實踐》）不同，本書 重技術兼并理論 ，給了新人入手的方向。

?

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

?

這只是第2章，后面還會有我很感興趣的日志處理、數據倉庫、負載均衡等，如果沒有中獎，我也會去買一本學習。 這是一本適合入門和進階的書籍 ，有介紹分布式的理論，也同時介紹每種技術用到的具體實現方式，可以讓我們少走彎路。

?

書中介紹了 一致性hash算法(consistent hashing) ，我個人也非常佩服這個經典算法，所以后面對它進行一些介紹總結。

?

• 一致性算法

?

背景：所謂分布式緩存不是說每臺服務器都存儲所有的緩存，而是讓每臺服務器均分存儲緩存。要實現服務器的均分及更新就要注意兩點： ①用什么算法去均分才能快速找到指定緩存；②當緩存出現新增、刪除時如何將變化的緩存同步到對應服務器也是一個關鍵。

?

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

傳統的算法查找緩存運行模式如下圖所示，當客戶端需要某個緩存的時候，首先會向緩存索引（菱形結構）發出請求，此時索引器通過算法（hash(key)%N）取余的形式找到余數對應的緩存服務器并取得該緩存返回。

?

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

?

一致性哈希（consistent hashing）：一致性哈希算法在1997年由麻省理工學院提出，設計目標是為了解決因特網中的熱點問題，目前在集群緩存應用中得到非常高的肯定。

?

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

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

>>假設有9個緩存，這時將其進行hash計算成一個數字，再根據他們的哈希值放到圓環對應數字點位上，這樣9個緩存就已經有自己位置（如下圖粉色小圓點即是 緩存哈希 ）。

>>假設有4臺緩存服務器，我們也對 服務器進行哈希計算 生成32位數字，這時再將服務器放在圓環對應位置上（如下圖淡藍色圓圈）。這樣就組成了緩存與緩存服務器的物理結構圖。[順便提一下服務器的hash計算，一般的方法可以使用機器的IP地址或者機器名作為hash輸入。]

>>如何將緩存映射到對應服務器上呢？一致性哈希算法采用 單向就近原則 ：在這個環形空間中，如果沿著順時針方向從緩存哈希出發，直到遇見一個服務器Node，那么就將該對象存儲在這個Node上，因為緩存哈希和服務器的hash值是固定的，因此這個緩存必然是唯一和確定的。這樣就能很方便根據哈希值找到對應服務器下的緩存對象。

?

用這種方式只需要維護node的hash值即可找到對應緩存， 非常快速方便 。而且假設有一個node宕機，則只需要將它維護的緩存hash放入下一個Node中即可；假設有新緩存加入，則只需要根據其hash值找最近的Node即可， 緩存變化影響非常小 。這是模式滿足了前面提到的分布式緩存第二點要求“當緩存出現新增、刪除時如何將變化的緩存同步到對應服務器”。

?

當然，上面描繪的只是一種理想的情況，各個節點在環上分布得十分均勻。正常情況下，當節點數量較少時，節點的分布可能十分不均勻，從而導致數據訪問的傾斜，大量的 key 被映射到同一臺服務器上。為了避免這種情況的出現，可以引入 虛擬節點機制 ，對每一個服務器節點都計算多個 Hash值，每一個Hash值都對應環上一個節點的位置，該節點稱為虛擬節點，而key 的映射方式不變，只是多了一步從虛擬節點再映射到真實節點的過程。這樣，如果虛擬節點的數量足夠多，即使只有很少的實際節點， 也能夠使 key分布得相對均衡 。?

?

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