谷歌推出有界負載的一致性哈希演算法，解決伺服器負載均衡問題

studyinsweden

雷鋒網AI科技評論按：運行大型Web服務需要負載平衡，例如內容託管。通常做法是在多個伺服器之間均勻分發客戶端，以免任何伺服器超負荷運行。此外，谷歌的研究者們期望找到一種分發方式，使得在客戶端和伺服器可以隨時增加或刪除的動態環境中，分發也不會隨時間波動產生太大變化。

谷歌與哥本哈根大學訪問研究員Mikkel Thorup合作，開發了一種新的高效分配演算法來解決這個問題：即嚴格控制每個伺服器的最大負載，並從理論和經驗上進行了研究。緊接著，谷歌研究院與雲團隊合作，在Google Cloud Pub / Sub（一種可擴展的事件流媒體服務）中實現演算法，並在保證一致性和穩定性的同時，對負載分配（分配給伺服器的最大負載）的均勻性進行了實質性改進。在2016年8月，谷歌紐約研究院的 Vahab Mirrokni、Mikkel Thorup 及Mikkel Thorup發表了論文「Consistent Hashing with Bounded Loads」，並在論文中描述了演算法，並分享在ArXiv上，方便更廣泛的研究用途。

三個月後，Vimeo的Andrew Rodland告訴我們，他發現了這篇論文並在haproxy（一個廣泛使用的開源軟體）中實現此演算法，將其用於Vimeo的負載平衡項目。結果非常驚人：這種演算法幫助他們將緩存帶寬降低了近8倍，解決了擴大規模的一個瓶頸。這證明了谷歌研究院的理論研究不僅能應用到實踐中，也兼具開源及有效的優點。

以下為雷鋒網編譯的論文部分內容，未經許可不得轉載。

儘管一致性哈希演算法早以被應用到動態環境中的負載平衡問題上，但是普遍存在的一個基本問題是，在某些情況下，它們可能導致許多伺服器上的負載平衡次優化。

此外，客戶端和伺服器可能會定期添加或刪除，但谷歌研究團隊不希望因此導致客戶端的大量移動。因此，動態分配演算法不僅要始終確保適當的負載均衡，還要最小化每次變化後被移動的客戶端數量。此外，伺服器容量的嚴格限制使得這種分配問題更具挑戰性，也就是， 每台伺服器都有一個最大負載容量限制，我們希望容量能接近於平均負載。

換句話說，我們希望同時實現分配的均勻性和一致性。有大量的文獻討論了簡單場景，即伺服器集群是固定的，只有客戶端被更新。但在這篇文章中，谷歌研究團隊討論了完全動態的場景，即客戶端和伺服器可以隨時被添加和刪除。

谷歌研究團隊把每個客戶端想像成一個球，將伺服器想像成進球箱，仔細研究進球的隨機過程。為了實現進球箱的均勻性，期望所有箱子的負載盡量接近平均負載（球的數量除以箱子數量）。對於參數ε，谷歌研究團隊將每個箱子的容量上下界設置為平均負載的上下（1 +ε）倍。這種容量範圍允許設計一個同時滿足一致性和均勻性的分配演算法。

想像一下，在一個圓上覆蓋了給定範圍的數字。谷歌研究團隊對球和進球箱分別應用不同的哈希函數，以獲得與該圓上的位置對應範圍內的數字。然後，我們開始以特定的順序（假設根據它們的ID）分配球，而不考慮它們的哈希值。然後每個球順時針移動，並分配到還有剩餘容量的第一個箱子。

想像一下有6個球和3個箱子，使用2個哈希函數來隨機循環地分配球進箱。設每個箱子的容量是2，然後按球的升序依次分配球（根據它們的ID），順時針移動，1號球進入箱子C，2號球進入箱子A，3號球和4號球進入箱子B，5號球進入箱子C，然後6號球順時針移動嘗試進入箱子B，然而箱子B容量已達限制（箱子容量為2，箱子B已經裝了3號球和4號球），所以6號球繼續順時針移動嘗試進入箱子C，但是箱子C也已達容量，最後6號球進入了箱子A。

系統有任何更新（球或箱增加/刪除）時，演算法需要重新進行計算分配以保證均勻性。演算法中巧妙的一點在於，確保小範圍的更新（少量球或箱增加/刪除）只引起細微的分配變化，以滿足一致性。 在論文中，谷歌研究團隊表明了增加和刪除一個球引起其他球O（1 /ε²）的移動。最重要的一點是負載上界與系統中的球或箱的數量相對獨立。 所以即使球或箱的數量加倍，負載的界限也不會改變。這一點增強了分配問題的可擴展性（即使擴大分配規模，也不影響一致性）。下圖模擬了球或箱有更新時，移動次數（再分配）隨更新的變化情況。

紅色曲線顯示平均移動次數，藍色線條表示不同ε值的方差。 虛線曲線是基於理論研究建議的負載上界（通過預測實際運動次數能較好地擬合）。除此之外，對於任意值ε，谷歌研究團隊知道每個箱子的負載上下界為平均負載的（1 +ε）倍。 下圖表示不同值ε（ 0.1，0.3，0.9）對應的箱子的負載分布。

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

從圖中可以看出均勻性和一致性的一個折衷 - 較小的ε值增強了均勻性，降低了一致性；而較大的ε值增加了一致性而降低了均勻性。較低的ε值能確保許多箱子的負載等於（1 +ε）倍的平均負載，其餘箱子的負載依次衰減。

提供內容託管服務可能會遇到差異很大的各種場景，在這種情況下，谷歌研究院提供的這種一致性哈希演算法將是理想的解決方案，即使是面對最壞的情況。

作者們對於內部試驗的結果感到興奮，但更加高興的是，外界發現該演算法很有效果且兼具開源特性，允許任何人使用此演算法。

致謝：感謝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，雷鋒網編譯