不同load balancing演算法的比較

在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 Robin、least connections，再加上計算每個node最近N個request的latency乘以某個factor，來決定要assign給哪個node。

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

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