很顯然，最簡(jiǎn)單的策略是將每一次Memcached請(qǐng)求隨機(jī)發(fā)送到一臺(tái)Memcached服務(wù)器，但是這種策略可能會(huì)帶來(lái)兩個(gè)問(wèn)題：一是同一份數(shù)據(jù)可能被存在不同的機(jī)器上而造成數(shù)據(jù)冗余，二是有可能某數(shù)據(jù)已經(jīng)被緩存但是訪問(wèn)卻沒(méi)有命中，因?yàn)闊o(wú)法保證對(duì)相同key的所有訪問(wèn)都被發(fā)送到相同的服務(wù)器。因此，隨機(jī)策略無(wú)論是時(shí)間效率還是空間效率都非常不好。
要解決上述問(wèn)題只需做到如下一點(diǎn)：保證對(duì)相同key的訪問(wèn)會(huì)被發(fā)送到相同的服務(wù)器。很多方法可以實(shí)現(xiàn)這一點(diǎn)，最常用的方法是計(jì)算哈希。例如對(duì)于每次訪問(wèn)，可以按如下算法計(jì)算其哈希值：
h = Hash(key) % 3
其中Hash是一個(gè)從字符串到正整數(shù)的哈希映射函數(shù)。這樣，如果我們將Memcached Server分別編號(hào)為0、1、2，那么就可以根據(jù)上式和key計(jì)算出服務(wù)器編號(hào)h，然后去訪問(wèn)。
這個(gè)方法雖然解決了上面提到的兩個(gè)問(wèn)題，但是存在一些其它的問(wèn)題。如果將上述方法抽象，可以認(rèn)為通過(guò)：
h = Hash(key) % N
這個(gè)算式計(jì)算每個(gè)key的請(qǐng)求應(yīng)該被發(fā)送到哪臺(tái)服務(wù)器，其中N為服務(wù)器的臺(tái)數(shù)，并且服務(wù)器按照0 – (N-1)編號(hào)。
這個(gè)算法的問(wèn)題在于容錯(cuò)性和擴(kuò)展性不好。所謂容錯(cuò)性是指當(dāng)系統(tǒng)中某一個(gè)或幾個(gè)服務(wù)器變得不可用時(shí)，整個(gè)系統(tǒng)是否可以正確高效運(yùn)行；而擴(kuò)展性是指當(dāng)加入新的服務(wù)器后，整個(gè)系統(tǒng)是否可以正確高效運(yùn)行。
現(xiàn)假設(shè)有一臺(tái)服務(wù)器宕機(jī)了，那么為了填補(bǔ)空缺，要將宕機(jī)的服務(wù)器從編號(hào)列表中移除，后面的服務(wù)器按順序前移一位并將其編號(hào)值減一，此時(shí)每個(gè)key就要按h = Hash(key) % (N-1)重新計(jì)算；同樣，如果新增了一臺(tái)服務(wù)器，雖然原有服務(wù)器編號(hào)不用改變，但是要按h = Hash(key) % (N+1)重新計(jì)算哈希值。因此系統(tǒng)中一旦有服務(wù)器變更，大量的key會(huì)被重定位到不同的服務(wù)器從而造成大量的緩存不命中。而這種情況在分布式系統(tǒng)中是非常糟糕的。
一個(gè)設(shè)計(jì)良好的分布式哈希方案應(yīng)該具有良好的單調(diào)性，即服務(wù)節(jié)點(diǎn)的增減不會(huì)造成大量哈希重定位。一致性哈希算法就是這樣一種哈希方案。 一致性哈希算法算法簡(jiǎn)述一致性哈希算法（Consistent Hashing）最早在論文《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》中被提出。簡(jiǎn)單來(lái)說(shuō)，一致性哈希將整個(gè)哈希值空間組織成一個(gè)虛擬的圓環(huán)，如假設(shè)某哈希函數(shù)H的值空間為0 – 232-1（即哈希值是一個(gè)32位無(wú)符號(hào)整形），整個(gè)哈希空間環(huán)如下： 哈希空間環(huán)
整個(gè)空間按順時(shí)針?lè)较蚪M織。0和232-1在零點(diǎn)中方向重合。
下一步將各個(gè)服務(wù)器使用H進(jìn)行一個(gè)哈希，具體可以選擇服務(wù)器的ip或主機(jī)名作為關(guān)鍵字進(jìn)行哈希，這樣每臺(tái)機(jī)器就能確定其在哈希環(huán)上的位置，這里假設(shè)將上文中三臺(tái)服務(wù)器使用ip地址哈希后在環(huán)空間的位置如下：
接下來(lái)使用如下算法定位數(shù)據(jù)訪問(wèn)到相應(yīng)服務(wù)器：將數(shù)據(jù)key使用相同的函數(shù)H計(jì)算出哈希值h，根據(jù)h確定此數(shù)據(jù)在環(huán)上的位置，從此位置沿環(huán)順時(shí)針“行走”，第一臺(tái)遇到的服務(wù)器就是其應(yīng)該定位到的服務(wù)器。
例如我們有A、B、C、D四個(gè)數(shù)據(jù)對(duì)象，經(jīng)過(guò)哈希計(jì)算后，在環(huán)空間上的位置如下：
根據(jù)一致性哈希算法，數(shù)據(jù)A會(huì)被定為到Server 1上，D被定為到Server 3上，而B(niǎo)、C分別被定為到Server 2上。 容錯(cuò)性與可擴(kuò)展性分析下面分析一致性哈希算法的容錯(cuò)性和可擴(kuò)展性。現(xiàn)假設(shè)Server 3宕機(jī)了：
可以看到此時(shí)A、C、B不會(huì)受到影響，只有D節(jié)點(diǎn)被重定位到Server 2。一般的，在一致性哈希算法中，如果一臺(tái)服務(wù)器不可用，則受影響的數(shù)據(jù)僅僅是此服務(wù)器到其環(huán)空間中前一臺(tái)服務(wù)器（即順著逆時(shí)針?lè)较蛐凶哂龅降牡谝慌_(tái)服務(wù)器）之間數(shù)據(jù)，其它不會(huì)受到影響。
下面考慮另外一種情況，如果我們?cè)谙到y(tǒng)中增加一臺(tái)服務(wù)器Memcached Server 4：
此時(shí)A、D、C不受影響，只有B需要重定位到新的Server 4。一般的，在一致性哈希算法中，如果增加一臺(tái)服務(wù)器，則受影響的數(shù)據(jù)僅僅是新服務(wù)器到其環(huán)空間中前一臺(tái)服務(wù)器（即順著逆時(shí)針?lè)较蛐凶哂龅降牡谝慌_(tái)服務(wù)器）之間數(shù)據(jù)，其它不會(huì)受到影響。
綜上所述，一致性哈希算法對(duì)于節(jié)點(diǎn)的增減都只需重定位環(huán)空間中的一小部分?jǐn)?shù)據(jù)，具有較好的容錯(cuò)性和可擴(kuò)展性。 虛擬節(jié)點(diǎn)一致性哈希算法在服務(wù)節(jié)點(diǎn)太少時(shí)，容易因?yàn)楣?jié)點(diǎn)分部不均勻而造成數(shù)據(jù)傾斜問(wèn)題。例如我們的系統(tǒng)中有兩臺(tái)服務(wù)器，其環(huán)分布如下：
此時(shí)必然造成大量數(shù)據(jù)集中到Server 1上，而只有極少量會(huì)定位到Server 2上。為了解決這種數(shù)據(jù)傾斜問(wèn)題，一致性哈希算法引入了虛擬節(jié)點(diǎn)機(jī)制，即對(duì)每一個(gè)服務(wù)節(jié)點(diǎn)計(jì)算多個(gè)哈希，每個(gè)計(jì)算結(jié)果位置都放置一個(gè)此服務(wù)節(jié)點(diǎn)，稱為虛擬節(jié)點(diǎn)。具體做法可以在服務(wù)器ip或主機(jī)名的后面增加編號(hào)來(lái)實(shí)現(xiàn)。例如上面的情況，我們決定為每臺(tái)服務(wù)器計(jì)算三個(gè)虛擬節(jié)點(diǎn)，于是可以分別計(jì)算“Memcached Server 1#1”、“Memcached Server 1#2”、“Memcached Server 1#3”、“Memcached Server 2#1”、“Memcached Server 2#2”、“Memcached Server 2#3”的哈希值，于是形成六個(gè)虛擬節(jié)點(diǎn)：
同時(shí)數(shù)據(jù)定位算法不變，只是多了一步虛擬節(jié)點(diǎn)到實(shí)際節(jié)點(diǎn)的映射，例如定位到“Memcached Server 1#1”、“Memcached Server 1#2”、“Memcached Server 1#3”三個(gè)虛擬節(jié)點(diǎn)的數(shù)據(jù)均定位到Server 1上。這樣就解決了服務(wù)節(jié)點(diǎn)少時(shí)數(shù)據(jù)傾斜的問(wèn)題。在實(shí)際應(yīng)用中，通常將虛擬節(jié)點(diǎn)數(shù)設(shè)置為32甚至更大，因此即使很少的服務(wù)節(jié)點(diǎn)也能做到相對(duì)均勻的數(shù)據(jù)分布。 總結(jié)目前一致性哈希基本成為了分布式系統(tǒng)組件的標(biāo)準(zhǔn)配置，例如Memcached的各種客戶端都提供內(nèi)置的一致性哈希支持。本文只是簡(jiǎn)要介紹了這個(gè)算法，更深入的內(nèi)容可以參看論文《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》，同時(shí)提供一個(gè)C語(yǔ)言版本的實(shí)現(xiàn)供參考。
——–
作者已經(jīng)在文章中介紹的比較清楚了，在這里補(bǔ)充下對(duì)“一致性哈希”這個(gè)名詞的簡(jiǎn)單說(shuō)明，在這個(gè)算法中就是指的機(jī)器標(biāo)識(shí)符和存儲(chǔ)對(duì)象采用相同的哈希算法，從而把他們映射到同一個(gè)集合（即0-2^32-1的哈希環(huán)）。
哈希空間環(huán)
