一緻性雜湊演算法及其在分布式系統中的應用

摘要

本文将會從實際應用場景出發，介紹一緻性雜湊演算法（Consistent Hashing）及其在分布式系統中的應用。首先本文會描述一個在日常開發中經常會遇到的問題場景，借此介紹一緻性雜湊演算法以及這個算法如何解決此問題；接下來會對這個算法進行相對詳細的描述，并讨論一些如虛拟節點等與此算法應用相關的話題。

分布式緩存問題

假設我們有一個網站，最近發現随着流量增加，伺服器壓力越來越大，之前直接讀寫資料庫的方式不太給力了，于是我們想引入Memcached作為緩存機制。現在我們一共有三台機器可以作為Memcached伺服器，如下圖所示。

很顯然，最簡單的政策是将每一次Memcached請求随機發送到一台Memcached伺服器，但是這種政策可能會帶來兩個問題：一是同一份資料可能被存在不同的機器上而造成資料備援，二是有可能某資料已經被緩存但是通路卻沒有命中，因為無法保證對相同key的所有通路都被發送到相同的伺服器。是以，随機政策無論是時間效率還是空間效率都非常不好。

要解決上述問題隻需做到如下一點：保證對相同key的通路會被發送到相同的伺服器。很多方法可以實作這一點，最常用的方法是計算哈希。例如對于每次通路，可以按如下算法計算其哈希值：

h = Hash(key) % 3

其中Hash是一個從字元串到正整數的哈希映射函數。這樣，如果我們将Memcached Server分别編号為0、1、2，那麼就可以根據上式和key計算出伺服器編号h，然後去通路。

這個方法雖然解決了上面提到的兩個問題，但是存在一些其它的問題。如果将上述方法抽象，可以認為通過：

h = Hash(key) % N

這個算式計算每個key的請求應該被發送到哪台伺服器，其中N為伺服器的台數，并且伺服器按照0 – (N-1)編号。

這個算法的問題在于容錯性和擴充性不好。所謂容錯性是指當系統中某一個或幾個伺服器變得不可用時，整個系統是否可以正确高效運作；而擴充性是指當加入新的伺服器後，整個系統是否可以正确高效運作。

現假設有一台伺服器當機了，那麼為了填補空缺，要将當機的伺服器從編号清單中移除，後面的伺服器按順序前移一位并将其編号值減一，此時每個key就要按h = Hash(key) % (N-1)重新計算；同樣，如果新增了一台伺服器，雖然原有伺服器編号不用改變，但是要按h = Hash(key) % (N+1)重新計算哈希值。是以系統中一旦有伺服器變更，大量的key會被重定位到不同的伺服器進而造成大量的緩存不命中。而這種情況在分布式系統中是非常糟糕的。

一個設計良好的分布式哈希方案應該具有良好的單調性，即服務節點的增減不會造成大量哈希重定位。一緻性雜湊演算法就是這樣一種哈希方案。

個人部落格已遷移至

www.codinglabs.org

，本文全文最新位址為

http://www.codinglabs.org/html/consistent-hashing.html

，歡迎通路！！！