0
雷鋒網AI科技評論按：運行大型Web服務需要負載平衡，例如內容托管。通常做法是在多個服務器之間均勻分發(fā)客戶端，以免任何服務器超負荷運行。此外，谷歌的研究者們期望找到一種分發(fā)方式，使得在客戶端和服務器可以隨時增加或刪除的動態(tài)環(huán)境中，分發(fā)也不會隨時間波動產生太大變化。
谷歌與哥本哈根大學訪問研究員Mikkel Thorup合作，開發(fā)了一種新的高效分配算法來解決這個問題：即嚴格控制每個服務器的最大負載，并從理論和經驗上進行了研究。緊接著，谷歌研究院與云團隊合作，在Google Cloud Pub / Sub（一種可擴展的事件流媒體服務）中實現(xiàn)算法，并在保證一致性和穩(wěn)定性的同時，對負載分配（分配給服務器的最大負載）的均勻性進行了實質性改進。在2016年8月，谷歌紐約研究院的 Vahab Mirrokni、Mikkel Thorup 及Mikkel Thorup發(fā)表了論文“Consistent Hashing with Bounded Loads”，并在論文中描述了算法，并分享在ArXiv上，方便更廣泛的研究用途。
三個月后，Vimeo的Andrew Rodland告訴我們，他發(fā)現(xiàn)了這篇論文并在haproxy（一個廣泛使用的開源軟件）中實現(xiàn)此算法，將其用于Vimeo的負載平衡項目。結果非常驚人：這種算法幫助他們將緩存帶寬降低了近8倍，解決了擴大規(guī)模的一個瓶頸。他最近在一篇博客文章中詳細介紹了此應用。這證明了谷歌研究院的理論研究不僅能應用到實踐中，也兼具開源及有效的優(yōu)點。
以下為雷鋒網編譯的論文部分內容，未經許可不得轉載。
盡管一致性哈希算法早以被應用到動態(tài)環(huán)境中的負載平衡問題上，但是普遍存在的一個基本問題是，在某些情況下，它們可能導致許多服務器上的負載平衡次優(yōu)化。
此外，客戶端和服務器可能會定期添加或刪除，但谷歌研究團隊不希望因此導致客戶端的大量移動。因此，動態(tài)分配算法不僅要始終確保適當?shù)呢撦d均衡，還要最小化每次變化后被移動的客戶端數(shù)量。此外，服務器容量的嚴格限制使得這種分配問題更具挑戰(zhàn)性，也就是， 每臺服務器都有一個最大負載容量限制，我們希望容量能接近于平均負載。
換句話說，我們希望同時實現(xiàn)分配的均勻性和一致性。有大量的文獻討論了簡單場景，即服務器集群是固定的，只有客戶端被更新。但在這篇文章中，谷歌研究團隊討論了完全動態(tài)的場景，即客戶端和服務器可以隨時被添加和刪除。
谷歌研究團隊把每個客戶端想象成一個球，將服務器想象成進球箱，仔細研究進球的隨機過程。為了實現(xiàn)進球箱的均勻性，期望所有箱子的負載盡量接近平均負載（球的數(shù)量除以箱子數(shù)量）。對于參數(shù)ε，谷歌研究團隊將每個箱子的容量上下界設置為平均負載的上下（1 +ε）倍。這種容量范圍允許設計一個同時滿足一致性和均勻性的分配算法。
想象一下，在一個圓上覆蓋了給定范圍的數(shù)字。谷歌研究團隊對球和進球箱分別應用不同的哈希函數(shù)，以獲得與該圓上的位置對應范圍內的數(shù)字。然后，我們開始以特定的順序（假設根據它們的ID）分配球，而不考慮它們的哈希值。然后每個球順時針移動，并分配到還有剩余容量的第一個箱子。
想象一下有6個球和3個箱子，使用2個哈希函數(shù)來隨機循環(huán)地分配球進箱。設每個箱子的容量是2，然后按球的升序依次分配球（根據它們的ID），順時針移動，1號球進入箱子C，2號球進入箱子A，3號球和4號球進入箱子B，5號球進入箱子C，然后6號球順時針移動嘗試進入箱子B，然而箱子B容量已達限制（箱子容量為2，箱子B已經裝了3號球和4號球），所以6號球繼續(xù)順時針移動嘗試進入箱子C，但是箱子C也已達容量，最后6號球進入了箱子A。
系統(tǒng)有任何更新（球或箱增加/刪除）時，算法需要重新進行計算分配以保證均勻性。算法中巧妙的一點在于，確保小范圍的更新（少量球或箱增加/刪除）只引起細微的分配變化，以滿足一致性。 在論文中，谷歌研究團隊表明了增加和刪除一個球引起其他球O（1 /ε2）的移動。最重要的一點是負載上界與系統(tǒng)中的球或箱的數(shù)量相對獨立。 所以即使球或箱的數(shù)量加倍，負載的界限也不會改變。這一點增強了分配問題的可擴展性（即使擴大分配規(guī)模，也不影響一致性）。下圖模擬了球或箱有更新時，移動次數(shù)（再分配）隨更新的變化情況。
紅色曲線顯示平均移動次數(shù)，藍色線條表示不同ε值的方差。 虛線曲線是基于理論研究建議的負載上界（通過預測實際運動次數(shù)能較好地擬合）。除此之外，對于任意值ε，谷歌研究團隊知道每個箱子的負載上下界為平均負載的（1 +ε）倍。 下圖表示不同值ε（ 0.1，0.3，0.9）對應的箱子的負載分布。
不同ε值的負載分布。 負載分布幾乎均勻，覆蓋了從0到（1 +ε）倍的平均負載，還有許多箱子的負載等于（1 +ε）倍的平均負載
從圖中可以看出均勻性和一致性的一個折衷 - 較小的ε值增強了均勻性，降低了一致性；而較大的ε值增加了一致性而降低了均勻性。較低的ε值能確保許多箱子的負載等于（1 +ε）倍的平均負載，其余箱子的負載依次衰減。
提供內容托管服務可能會遇到差異很大的各種場景，在這種情況下，谷歌研究院提供的這種一致性哈希算法將是理想的解決方案，即使是面對最壞的情況。
作者們對于內部試驗的結果感到興奮，但更加高興的是，外界發(fā)現(xiàn)該算法很有效果且兼具開源特性，允許任何人使用此算法。
致謝：感謝Google Cloud Pub / Sub團隊的Alex Totok，Matt Gruskin，Sergey Kondratyev和Haakon Ringberg，以及Mikkel Thorup對本文的寶貴貢獻。
原文鏈接：https://research.googleblog.com/2017/04/consistent-hashing-with-bounded-loads.html，雷鋒網編譯
雷峰網版權文章，未經授權禁止轉載。詳情見轉載須知。
