0
雷鋒網(wǎng)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é)訪問研究員Mikkel Thorup合作，開發(fā)了一種新的高效分配算法來解決這個(gè)問題：即嚴(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è)廣泛使用的開源軟件）中實(shí)現(xiàn)此算法，將其用于Vimeo的負(fù)載平衡項(xiàng)目。結(jié)果非常驚人：這種算法幫助他們將緩存帶寬降低了近8倍，解決了擴(kuò)大規(guī)模的一個(gè)瓶頸。他最近在一篇博客文章中詳細(xì)介紹了此應(yīng)用。這證明了谷歌研究院的理論研究不僅能應(yīng)用到實(shí)踐中，也兼具開源及有效的優(yōu)點(diǎn)。
以下為雷鋒網(wǎng)編譯的論文部分內(nèi)容，未經(jīng)許可不得轉(zhuǎn)載。
盡管一致性哈希算法早以被應(yīng)用到動(dòng)態(tài)環(huán)境中的負(fù)載平衡問題上，但是普遍存在的一個(gè)基本問題是，在某些情況下，它們可能導(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)格限制使得這種分配問題更具挑戰(zhàn)性，也就是， 每臺(tái)服務(wù)器都有一個(gè)最大負(fù)載容量限制，我們希望容量能接近于平均負(fù)載。
換句話說，我們希望同時(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ī)過程。為了實(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ù)字。然后，我們開始以特定的順序（假設(shè)根據(jù)它們的ID）分配球，而不考慮它們的哈希值。然后每個(gè)球順時(shí)針移動(dòng)，并分配到還有剩余容量的第一個(gè)箱子。
想象一下有6個(gè)球和3個(gè)箱子，使用2個(gè)哈希函數(shù)來隨機(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)了分配問題的可擴(kuò)展性（即使擴(kuò)大分配規(guī)模，也不影響一致性）。下圖模擬了球或箱有更新時(shí)，移動(dòng)次數(shù)（再分配）隨更新的變化情況。
紅色曲線顯示平均移動(dòng)次數(shù)，藍(lán)色線條表示不同ε值的方差。 虛線曲線是基于理論研究建議的負(fù)載上界（通過預(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)該算法很有效果且兼具開源特性，允許任何人使用此算法。
致謝：感謝Google Cloud Pub / Sub團(tuán)隊(duì)的Alex Totok，Matt Gruskin，Sergey Kondratyev和Haakon Ringberg，以及Mikkel Thorup對(duì)本文的寶貴貢獻(xiàn)。
原文鏈接：https://research.googleblog.com/2017/04/consistent-hashing-with-bounded-loads.html，雷鋒網(wǎng)編譯
雷峰網(wǎng)版權(quán)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。
