AI科技評(píng)論按：運(yùn)行大型Web服務(wù)需要負(fù)載平衡，例如內(nèi)容托管。通常做法是在多個(gè)服務(wù)器之間均勻分發(fā)客戶端，以免任何服務(wù)器超負(fù)荷運(yùn)行。此外，谷歌的研究者們期望找到一種分發(fā)方式，使得在客戶端和服務(wù)器可以隨時(shí)增加或刪除的動(dòng)態(tài)環(huán)境中，分發(fā)也不會(huì)隨時(shí)間波動(dòng)產(chǎn)生太大變化。

谷歌與哥本哈根大學(xué)訪問(wèn)研究員Mikkel Thorup合作，開(kāi)發(fā)了一種新的高效分配算法來(lái)解決這個(gè)問(wèn)題：即嚴(yán)格控制每個(gè)服務(wù)器的最大負(fù)載，并從理論和經(jīng)驗(yàn)上進(jìn)行了研究。緊接著，谷歌研究院與云團(tuán)隊(duì)合作，在Google Cloud Pub / Sub(一種可擴(kuò)展的事件流媒體服務(wù))中實(shí)現(xiàn)算法，并在保證一致性和穩(wěn)定性的同時(shí)，對(duì)負(fù)載分配(分配給服務(wù)器的最大負(fù)載)的均勻性進(jìn)行了實(shí)質(zhì)性改進(jìn)。在2016年8月，谷歌紐約研究院的 Vahab Mirrokni、Mikkel Thorup 及Mikkel Thorup發(fā)表了論文“Consistent Hashing with Bounded Loads”，并在論文中描述了算法，并分享在ArXiv上，方便更廣泛的研究用途。

三個(gè)月后，Vimeo的Andrew Rodland告訴我們，他發(fā)現(xiàn)了這篇論文并在haproxy(一個(gè)廣泛使用的開(kāi)源軟件)中實(shí)現(xiàn)此算法，將其用于Vimeo的負(fù)載平衡項(xiàng)目。結(jié)果非常驚人：這種算法幫助他們將緩存帶寬降低了近8倍，解決了擴(kuò)大規(guī)模的一個(gè)瓶頸。他最近在一篇博客文章中詳細(xì)介紹了此應(yīng)用。這證明了谷歌研究院的理論研究不僅能應(yīng)用到實(shí)踐中，也兼具開(kāi)源及有效的優(yōu)點(diǎn)。

以下為雷鋒網(wǎng)編譯的論文部分內(nèi)容，未經(jīng)許可不得轉(zhuǎn)載。

背景

盡管一致性哈希算法早以被應(yīng)用到動(dòng)態(tài)環(huán)境中的負(fù)載平衡問(wèn)題上，但是普遍存在的一個(gè)基本問(wèn)題是，在某些情況下，它們可能導(dǎo)致許多服務(wù)器上的負(fù)載平衡次優(yōu)化。

此外，客戶端和服務(wù)器可能會(huì)定期添加或刪除，但谷歌研究團(tuán)隊(duì)不希望因此導(dǎo)致客戶端的大量移動(dòng)。因此，動(dòng)態(tài)分配算法不僅要始終確保適當(dāng)?shù)呢?fù)載均衡，還要最小化每次變化后被移動(dòng)的客戶端數(shù)量。此外，服務(wù)器容量的嚴(yán)格限制使得這種分配問(wèn)題更具挑戰(zhàn)性，也就是， 每臺(tái)服務(wù)器都有一個(gè)最大負(fù)載容量限制，我們希望容量能接近于平均負(fù)載。

換句話說(shuō)，我們希望同時(shí)實(shí)現(xiàn)分配的均勻性和一致性。有大量的文獻(xiàn)討論了簡(jiǎn)單場(chǎng)景，即服務(wù)器集群是固定的，只有客戶端被更新。但在這篇文章中，谷歌研究團(tuán)隊(duì)討論了完全動(dòng)態(tài)的場(chǎng)景，即客戶端和服務(wù)器可以隨時(shí)被添加和刪除。

算法

谷歌研究團(tuán)隊(duì)把每個(gè)客戶端想象成一個(gè)球，將服務(wù)器想象成進(jìn)球箱，仔細(xì)研究進(jìn)球的隨機(jī)過(guò)程。為了實(shí)現(xiàn)進(jìn)球箱的均勻性，期望所有箱子的負(fù)載盡量接近平均負(fù)載(球的數(shù)量除以箱子數(shù)量)。對(duì)于參數(shù)ε，谷歌研究團(tuán)隊(duì)將每個(gè)箱子的容量上下界設(shè)置為平均負(fù)載的上下(1 +ε)倍。這種容量范圍允許設(shè)計(jì)一個(gè)同時(shí)滿足一致性和均勻性的分配算法。

想象一下，在一個(gè)圓上覆蓋了給定范圍的數(shù)字。谷歌研究團(tuán)隊(duì)對(duì)球和進(jìn)球箱分別應(yīng)用不同的哈希函數(shù)，以獲得與該圓上的位置對(duì)應(yīng)范圍內(nèi)的數(shù)字。然后，我們開(kāi)始以特定的順序(假設(shè)根據(jù)它們的ID)分配球，而不考慮它們的哈希值。然后每個(gè)球順時(shí)針移動(dòng)，并分配到還有剩余容量的第一個(gè)箱子。

想象一下有6個(gè)球和3個(gè)箱子，使用2個(gè)哈希函數(shù)來(lái)隨機(jī)循環(huán)地分配球進(jìn)箱。設(shè)每個(gè)箱子的容量是2，然后按球的升序依次分配球(根據(jù)它們的ID)，順時(shí)針移動(dòng)，1號(hào)球進(jìn)入箱子C，2號(hào)球進(jìn)入箱子A，3號(hào)球和4號(hào)球進(jìn)入箱子B，5號(hào)球進(jìn)入箱子C，然后6號(hào)球順時(shí)針移動(dòng)嘗試進(jìn)入箱子B，然而箱子B容量已達(dá)限制(箱子容量為2，箱子B已經(jīng)裝了3號(hào)球和4號(hào)球)，所以6號(hào)球繼續(xù)順時(shí)針移動(dòng)嘗試進(jìn)入箱子C，但是箱子C也已達(dá)容量，最后6號(hào)球進(jìn)入了箱子A。

系統(tǒng)有任何更新(球或箱增加/刪除)時(shí)，算法需要重新進(jìn)行計(jì)算分配以保證均勻性。算法中巧妙的一點(diǎn)在于，確保小范圍的更新(少量球或箱增加/刪除)只引起細(xì)微的分配變化，以滿足一致性。 在論文中，谷歌研究團(tuán)隊(duì)表明了增加和刪除一個(gè)球引起其他球O(1 /ε2)的移動(dòng)。最重要的一點(diǎn)是負(fù)載上界與系統(tǒng)中的球或箱的數(shù)量相對(duì)獨(dú)立。 所以即使球或箱的數(shù)量加倍，負(fù)載的界限也不會(huì)改變。這一點(diǎn)增強(qiáng)了分配問(wèn)題的可擴(kuò)展性(即使擴(kuò)大分配規(guī)模，也不影響一致性)。下圖模擬了球或箱有更新時(shí)，移動(dòng)次數(shù)(再分配)隨更新的變化情況。

紅色曲線顯示平均移動(dòng)次數(shù)，藍(lán)色線條表示不同ε值的方差。 虛線曲線是基于理論研究建議的負(fù)載上界(通過(guò)預(yù)測(cè)實(shí)際運(yùn)動(dòng)次數(shù)能較好地?cái)M合)。除此之外，對(duì)于任意值ε，谷歌研究團(tuán)隊(duì)知道每個(gè)箱子的負(fù)載上下界為平均負(fù)載的(1 +ε)倍。 下圖表示不同值ε( 0.1，0.3，0.9)對(duì)應(yīng)的箱子的負(fù)載分布。

不同ε值的負(fù)載分布。 負(fù)載分布幾乎均勻，覆蓋了從0到(1 +ε)倍的平均負(fù)載，還有許多箱子的負(fù)載等于(1 +ε)倍的平均負(fù)載

從圖中可以看出均勻性和一致性的一個(gè)折衷 - 較小的ε值增強(qiáng)了均勻性，降低了一致性;而較大的ε值增加了一致性而降低了均勻性。較低的ε值能確保許多箱子的負(fù)載等于(1 +ε)倍的平均負(fù)載，其余箱子的負(fù)載依次衰減。

提供內(nèi)容托管服務(wù)可能會(huì)遇到差異很大的各種場(chǎng)景，在這種情況下，谷歌研究院提供的這種一致性哈希算法將是理想的解決方案，即使是面對(duì)最壞的情況。

作者們對(duì)于內(nèi)部試驗(yàn)的結(jié)果感到興奮，但更加高興的是，外界發(fā)現(xiàn)該算法很有效果且兼具開(kāi)源特性，允許任何人使用此算法。

致謝：感謝Google Cloud Pub / Sub團(tuán)隊(duì)的Alex Totok，Matt Gruskin，Sergey Kondratyev和Haakon Ringberg，以及Mikkel Thorup對(duì)本文的寶貴貢獻(xiàn)。