不同load balancing演算法的比較

less than 1 minute read

在Hacker News看到Load Balancing這篇,裡面比較幾個常見的load balancing 演算法。

最基本的Round Robin就不用說了,還有Round Robin的改良版,Weighted Round Robin(又分人工給權重和系統來判斷權重)。

接著提到一個簡單、粗暴有效的方式,AWS load balancer用的 ““least connections” load balancing”,從字面上就可以知道,load balancer每次都挑目前最少連線的node。

“least connections”的想法也沒很難理解,通常同一個後端的request種類不會差太多,所以如果node的連線數少,代表現在的loading比較輕。

作者寫到這先比較了三個演算法的drop requestrate和latency,基本上在中位數的時候,三者的表現都很好,但是在99th percentile之後RR的長尾效應就出現了,RR在尾端後面總是會有latency很高的request。即使是Weighted Round Robin也沒有比least connections的方法表現來的好。

不過作者最後又提出一個peak exponentially weighted moving average (PEWMA)的演算法,看起來是一種混合Weighted Round Robinleast connections,再加上計算每個node最近N個request的latency乘以某個factor,來決定要assign給哪個node。

作者本來就有提到PEWMA是為了latency特化的演算法,加上PEWMA來比較,得到在latency方面在95 percentile99 percentile的表現比least connections來的好。

不過在drop request方面,PEWMA表現就沒有least connections來的好,雖說作者強調PEWMA的參數還有fine tune的空間,但考量演算法的簡潔性和綜合的表現來說,讓我來挑的話,我還是會挑least connections吧……

Updated: