運(yùn)行大規(guī)模網(wǎng)絡(luò)服務(wù)(例如內(nèi)容托管)離不開負(fù)載平衡，也就是將客戶端均勻地分配到多個(gè)服務(wù)器上，使得每個(gè)服務(wù)器都不至于過載。此外，在隨時(shí)可以添加或移除客戶端和服務(wù)器的動(dòng)態(tài)環(huán)境中，較為理想的做法是找到一種不會(huì)隨時(shí)間而大幅改變的分配方案。換而言之，我們需要在一段時(shí)間內(nèi)一致地將客戶端分配到服務(wù)器。

背景

盡管過去已經(jīng)研發(fā)出一致的哈希算法理念來解決動(dòng)態(tài)環(huán)境中的負(fù)載平衡問題，但所有之前開發(fā)的方案都存在一個(gè)根本性的問題：在特定的場(chǎng)景下，它們可能導(dǎo)致許多服務(wù)器上的負(fù)載平衡不能達(dá)到***狀態(tài)。

此外，由于可能隨時(shí)添加或移除客戶端和服務(wù)器，在做出此類改動(dòng)時(shí)，我們不希望移動(dòng)太多的客戶端。因此，動(dòng)態(tài)分配算法不僅必須始終確保正確的負(fù)載平衡，還應(yīng)盡量減少每次對(duì)系統(tǒng)做出改動(dòng)之后所移動(dòng)的客戶端數(shù)量。當(dāng)每臺(tái)服務(wù)器的容量存在嚴(yán)格的限制時(shí)，也就是說，每臺(tái)服務(wù)器都有嚴(yán)格的容量限制，負(fù)載不得超過此限制之時(shí)，此類分配問題會(huì)變得更為嚴(yán)峻。通常，我們希望容量接近于平均負(fù)載。

換而言之，我們希望在最終的分配中同時(shí)實(shí)現(xiàn)均勻性和一致性這兩大目標(biāo)。對(duì)于服務(wù)器集固定不變、只有客戶端集會(huì)更新這種簡(jiǎn)單很多的情形，有大量的文獻(xiàn)介紹了相關(guān)的解決方案，但在本文中，我們討論的解決方案針對(duì)的是客戶端和服務(wù)器均可隨時(shí)添加和移除的完全動(dòng)態(tài)的情形。

算法

我們可以將服務(wù)器比作垃圾桶，將客戶端比作球，并借鑒將球隨機(jī)投入垃圾桶的過程 (balls-to-bins stochastic processes) 這一經(jīng)過深入研究的模型，采用與之類似的抽象方法。均勻性目標(biāo)要求所有垃圾桶所裝的球數(shù)量大致等于平均密度(球數(shù)除以箱子數(shù))。對(duì)于參數(shù) ε，我們將每個(gè)垃圾桶的容量設(shè)置為平均負(fù)載的***或***倍數(shù) (1+ε)。這一額外的容量讓我們可以設(shè)計(jì)出一種能夠同時(shí)滿足均勻性目標(biāo)和一致性目標(biāo)的分配算法。

設(shè)想給定范圍的一組數(shù)字，將其分布到一個(gè)圓圈上。我們對(duì)球應(yīng)用一個(gè)哈希函數(shù)，對(duì)垃圾桶應(yīng)用另一個(gè)不同的哈希函數(shù)，以獲取該范圍內(nèi)、與該圓圈上不同位置對(duì)應(yīng)的數(shù)字。隨后，我們開始按特定的順序分配球，此順序與其哈希值無關(guān)(假設(shè)基于其 ID)。然后，按順時(shí)針移動(dòng)每個(gè)球并將其分配到***個(gè)有空閑容量的垃圾桶。

我們分析一下上面的例子，我們使用兩種不同的哈希函數(shù)，將 6 個(gè)球和 3 個(gè)垃圾桶隨機(jī)分配到圓圈上的不同位置。對(duì)于本例，我們假設(shè)每個(gè)垃圾桶的容量設(shè)置為 2。我們開始按 ID 值的升序分配球。1 號(hào)球按順時(shí)針移動(dòng)，進(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)，首先***垃圾桶 B。然而，垃圾桶 B 的容量為 2，而其中已經(jīng)裝有 3 號(hào)和 4 號(hào)球。因此，6 號(hào)球繼續(xù)向前移動(dòng)，直至到達(dá)垃圾桶 C，但該垃圾桶也已滿。***，6 號(hào)球進(jìn)入仍有空余位置的垃圾桶 A。

如對(duì)系統(tǒng)進(jìn)行任何更新(插入/刪除球或垃圾桶)，則會(huì)重新計(jì)算分配，以保持均勻性目標(biāo)。分析表明小幅更新(插入和刪除少量的球或垃圾桶)會(huì)導(dǎo)致分配狀態(tài)的小幅改變，因此，可滿足一致性目標(biāo)。在我們的論文中，我們展示了在該系統(tǒng)中，每插入或移除一個(gè)球?qū)?huì)導(dǎo)致其他球進(jìn)行 O(1/ε2) 次運(yùn)動(dòng)。最重要的是，此上限與系統(tǒng)中球或垃圾桶的總數(shù)無關(guān)。因此，如果球或垃圾桶的數(shù)量加倍，此上限不會(huì)改變。上限與球或垃圾桶的數(shù)量無關(guān)，為可伸縮性帶來了巨大的空間，因?yàn)槲覀儗⑵浒岬礁蟮膶?shí)例中，仍然可以滿足一致性目標(biāo)。下面顯示了更新某個(gè)垃圾桶/服務(wù)器時(shí)，每次更新所導(dǎo)致的移動(dòng)(重新分配)次數(shù)模擬結(jié)果。

紅色曲線代表移動(dòng)的平均次數(shù)，藍(lán)色柱線代表不同 ε 值(X 軸)的方差。虛線代表我們的理論結(jié)果所建議的上限，其非常適合用于預(yù)測(cè)實(shí)際的移動(dòng)次數(shù)。此外，對(duì)于任何 ε 值，我們知道，每個(gè)垃圾桶的負(fù)載至多是平均負(fù)載的 (1+ε) 倍。下面，我們看到不同值 ε=0.1、ε=0.3 和 ε=0.9 條件下垃圾桶的負(fù)載分布情況。

▲ 不同 ε 值下的負(fù)載分布。對(duì)于所有范圍的負(fù)載(從 0 到 (1+ε) 倍于平均負(fù)載)，負(fù)載分布均接近均勻，許多垃圾桶的負(fù)載等于平均負(fù)載的 (1+ε) 倍。

我們可以看到，這里需要折中考慮，較低的 ε 值有利于確保均勻性，但不利于確保一致性，而較大的 ε 值則有利于確保一致性。較低的 ε 值可確保許多負(fù)載等于平均負(fù)載的 (1+ε) 倍這一硬性容量限制，而其他負(fù)載則為遞減分布。

在提供內(nèi)容托管服務(wù)時(shí)，必須做好應(yīng)對(duì)許多不同特性的實(shí)例的準(zhǔn)備。這種一致的哈希方案非常適合此類情形，因?yàn)榧幢闶亲钤愀獾那樾蜗?，它也能有不錯(cuò)的表現(xiàn)。

我們的內(nèi)部研究結(jié)果激動(dòng)人心，我們更欣慰的是，更廣大的社區(qū)發(fā)現(xiàn)我們的解決方案非常有用，足以列入開放源代碼，讓任何人都可以使用該算法：

https://github.com/arodland/haproxy

【本文是51CTO專欄機(jī)構(gòu)“谷歌開發(fā)者”的原創(chuàng)稿件，轉(zhuǎn)載請(qǐng)聯(lián)系原作者(微信公眾號(hào)：Google_Developers)】

戳這里，看該作者更多好文