這篇文章是CMU Intel lab在2011年發表的，它高屋建瓴地提出：空間複雜度下界為O(nlogn)的cache（n為後端節點數）即可保證集羣服務的負載均衡可靠性。建模和證明的過程非常巧妙，對cache design會很有啟發。

摘要

在大規模的雲計算服務中，為了避免後端節點過早暴露性能瓶頸、保證服務的SLO，以及更好地水平擴展，通常會在應用請求到達時經由一個load balancer處理，將請求平滑均勻地分發給後端節點。優秀的負載均衡能力是系統高吞吐，低延遲的前提。

但在生產環境中，沒有cache加持的load balancer只能是阿克琉斯之踵：隨著集羣規模的動態變更，load balancer的partition規則不能保證負載被均勻地劃分給各個後端節點；此外，請求負載的類型和分佈無法預測，不排除DoS攻擊的可能。系統設計者必須很小心地選擇/組合load balancing策略，否則不同規格後端節點的處理能力將很容易成為系統瓶頸，被skewed load洪流擊垮。

《Small Cache, Big Effect》提出：在load balancer中集成一層空間複雜度下界為O(nlogn)的cache（n為後端節點數！）來緩存熱點數據，即可在顯著提升load balancer吞吐量的同時，保證到達後端節點的請求負載是均勻分佈的。

文中還給出了漂亮的證明過程和模擬結果，非常反直覺對吧？我們往下看。

small, fast cache at the front-end load balancer.

背景

簡單講一下處理負載均衡的兩種方式：

  1. 靜態處理。根據節點的處理能力（節點的規格，涉及CPU，內存，存儲多個維度），load balancer可以對負載預先劃分邊界，能者多勞。對於hash-based的方法，例如consistent-hashing，引入virtual nodes實現環狀hash空間的均勻散列（其實可以在virtual nodes中對節點的規格做分拆，為處理能力強的節點適當分配更多的virtual nodes）。
  2. 動態處理：就是負載均衡的策略選擇了，從round-robin，least connections到the power of two random choices（one more random，big effect！這也很有意思，可以看文後的參考資料）。

建模/證明

為了模擬skewed load，文中假設了一個對抗型的請求模式（adversarial workload），請求要儘可能旁路cache，直接命中後端節點，與load balancer呈一個攻防態勢。後文直接簡稱對抗模式。

首先對模型做幾個假設吧：

  • key映射到後端節點的過程對客戶端透明，且完全隨機。
  • cache足夠快。
  • cache永遠持有最熱的c（cache size）個key。
  • 後端節點處理單次請求負載的時間都一致。

再定義一些證明過程需要用到的符號，請別右上角：

  • c（cache size）；
  • n（後端節點數，）；
  • m（記錄條數，即請求負載的目標）；
  • Li（劃分給節點i的最大請求速率）；
  • ri（節點i的最大請求處理速率）；

請求的範圍是所有key或者key的子集，那麼對抗模式的請求策略可以用以下分佈表示：

S = (p1, p2, ..., p(m))

p1，p2 ... pm即各個key的請求概率，和為1。為了方便證明，給它們排序一下，默認p1到pm降序排列。因為前c個key一定會被緩存，所以S實際上呈如下分佈：

S: p1 geq p2 geq ... geq pc=h geq p(c+1) geq ... geq p(m)

對抗模式需要研究的是如何讓分佈在 p(c+1)~p(m) 這個範圍的key，best effort地向後端節點發起請求，設這個臨界的概率為h。因為同一個key一定會被hash到同一個節點（假設此過程節點數不變），所以對抗模式通過構造uncached keys對某個或某幾個節點發起skewed queries，企圖讓這些後端節點達到最大負載，直到不可用。

這裡再引入一個定理：

某兩個未緩存的keyi和keyi， h geq p(i) geq p(j) geq 0 ，對抗模式可以構造一對新的概率：

p(i) = p(i) + delta, p(j) = p(j) - delta delta = minleft {h-p(i), p(j) ight }

實質就是負載可以在節點間轉移，證明比較簡單，感興趣的同學可以看參考資料中的原文附錄。對抗模式通過lantency等特徵來判斷key的熱度，不斷嘗試轉移負載，並調整keys的概率分佈，儘可能多地構造請求概率同樣為h的uncached keys，一波操作之後，設最後只剩下x個key。

此時能對系統產生威脅的keys的範圍為(c+1)~(x)，共x-c個，如下圖所示。

對抗模式構造的最佳keys概率分佈

前面的假設中有一條，對每個key的請求都會隨機分配給某個後端節點，這是經典的Balls into Bins模型：

M個ball依次隨機地投入N個bin中（queries-for-keys依次隨機地被分配給某個後端節點）。

當balls數量遠大於bins時，負載最大的一個bin中balls數目有極大的概率遵循以下Balls into Bins模型的分佈（硬核推導見參考資料中的原文）：

frac{M}{N} + alpha sqrt{2*frac{M}{N}*logN}

alpha>1 ，是一個常係數。在我們的場景中，N = n，M = x-c，那麼負載最大的一個節點被分配的keys數遵循以下分佈：

frac{x-c}{n} + alpha sqrt{2*frac{x-c}{n}*logn}

更近一步！假設對抗模式發起速率為R的請求，前x-1個key（那些請求概率為h的key）被平均分配到的速率為 R/(x-1) ，那麼單節點的負載上界為：

egin{split} E[Lmax] &leq left ( frac{x-c}{n} + alpha sqrt{2*frac{x-c}{n}*logn} ight )*frac{R}{x-1} \ &= left ( frac{x-c}{x-1} + alpha sqrt{2*frac{x-c}{{(x-1)}^{2}}*n*logn} ight )*frac{R}{n} end{split}

若請求被完全均勻地分發給後端節點，那麼每個後端節點處理的請求速率為 R/n ，為了得到這樣的運算元，不等式的右側乘上 frac{n}{x-1}*frac{x-1}{n} ，得到下一行的變換式。

在系統設計階段，我們不知道哪個節點會承受最大的負載，所以需要為每個節點都預留最大負載所需的資源，嚴重拉低了整體的資源利用率，顯然無法被接受。

對抗模式為了達成目的，要繼續優化這個不等式，確定x值使得可能的負載最大化，R和n都可視作常量的話，即求 left ( frac{x-c}{x-1} + alpha sqrt{2*frac{x-c}{{(x-1)}^{2}}*n*logn} ight ) 這部分的最大值，換元求解一下可得函數極大值對應的x，這個x值也是對抗模式應該選取的最優值：

x^{*} = 1+2(c-1)left ( 1+frac{1}{sqrt{1+frac{2alpha^{2}nlogn}{c-1}}-1} ight )

把 x^{*} 代入原來的負載上界不等式，可以得到一個更簡潔清晰的式子：

E[Lmax] leq frac{1+sqrt{1+2alpha^{2}frac{nlogn}{c-1}}}{2}*frac{R}{n}

那麼單節點的最大吞吐量（最大負載）可以表示為：

frac{E[Lmax]}{R/n} leq frac{1+sqrt{1+2alpha^{2}frac{nlogn}{c-1}}}{2}

這個式子已經代表了cache size（c）和單節點最大負載的關係。為了讓最大負載與節點數n無關，把根號下的分式因子消掉，只需要取c = k*nlogn + 1 = O(nlogn) ，k是一個常量係數。

O(nlogn)的空間複雜度是這麼得出的！最終獨立於節點數n的單節點max-load為：

frac{1}{2} * left ( 1+sqrt{1+frac{2alpha^{2}}{k}} ight )

可以通過調整係數k縮放max-load。對於異構的後端節點，可以參考負載靜態處理方式中提到的：把一個physical node拆分成多個virtual nodes。

為每個節點預留max-load所需的資源，即可保證對抗模式發起的請求永遠不會飽和。

模擬

以上模型還是有很多理想條件約束的，需要丟到模擬環境裏摩擦一下，paper的作者利用1個高性能的前端節點和85個普通後端節點搭建了一個FAWN-KV集羣，每個後端節點承擔100k的kv鍵值對存儲（key 20bytes / value 128bytes），所有節點與同一個交換機相連，網路不會成為瓶頸。

實驗結果非常驚艷：

重點關注adversarial workload和uniform workload，可以明顯看到加了cache之後，adversarial workload的吞吐和uniform workload幾乎重合，完美符合推演。並且在cache加持下，這三種workload的吞吐和節點數n都呈線性關係。

總結

建模和模擬共同驗證了這麼一層薄薄的small-fast-cache對負載均衡效果的重大影響，我感覺它在load balancer中像是扮演了一個「filter」的角色，skewed load經由cache過濾，以足夠uniform的分佈被後端節點處理，很神奇但又很合理。

建模的過程遵循的是樸素的Balls into Bins模型，如果採用The Power of Two Random Choices的方法，max-load還可以進一步降低：

在balls into bins的基礎上，一次選擇d個bins（d≥2），把ball投入負載最低的bin中

The Power of Two Random Choices模型也很有意思，並且在負載均衡中已經成熟應用，大家可以參見參考資料自行了解。

當然了，建模過程中的很多假設是不能直接搬到真實環境中的，比如「cache只緩存最熱的keys」，假設了一個perfect caching policy，但在現實中幾乎做不到，諸如LRU、LRU的變種，這些緩存策略也只能在特定場景下做到逼近完美，並且維護key的狀態，緩存的置換，保證cache consistency，都會有額外的開銷；再比如「後端節點處理單次請求負載的時間都一致」，顯然這在真實環境中無法保證。

除此之外，網路，多級緩存設計，讀寫分離等等都會成為影響最終性能的因素。

也許對於部署在純應用層的load balancer， O(nlogn) 的指標意義沒有特別大，畢竟內存可以放心糟蹋，但對cache的容量規劃，命中率與內存利用率的兼顧，還是有一定指導意義的。重點在於，這樣經過驗證的輕量級緩存，完全可以集成進專有硬體中，比如CPU的L3 cache，甚至是L2 cache，做到真正的 small and fast。

以上。更詳細的內容請參見原文，如有不當之處歡迎指出 :)

參考資料：

暗淡了烏雲：The Power of Two Random Choices?

zhuanlan.zhihu.com圖標「Balls into Bins」 — A Simple and Tight Analysis?

www.dblab.ntua.gr

Small Cache, Big Effect: Provable Load Balancing for. Randomly Partitioned Cluster Services?

www.cs.cmu.edu

The Power of Two Random Choices: A Survey of Techniques and Results?

www.eecs.harvard.edu

古文：[Paper Review]FAST19 DistCache?

zhuanlan.zhihu.com圖標
推薦閱讀：

相關文章