負載均衡的那些算法們
上周發了問卷，想了解一下大家對老王有沒有什么建議，然后好多朋友都投了票，想了解編程技術和服務器架構的干貨，所以接下來會先聊聊編程和架構相關的算法，然后大概在6月下旬會跟大家聊聊面試那些事兒（老王到目前大約參加了幾百次的面試，可以從面試官的角度來聊聊不一樣的面試）。老王聊技術有個特點，就是絕不假大空，只求貼地飛行。所以，聊的東西一定會跟實際有關聯，大家在平時也有可能用得著。
今天跟大伙兒聊的是負載均衡相關的一些算法。老王在百度的時候（估計是 5-6 年前），寫過一個通用的基礎庫（不知道現在還有沒有部門在用），用來做不同系統間負載均衡。太細節的東東估計想不起來了，不過基本的算法可以跟大家做做分享。
那第一個問題： what's load-balance?
假設我有兩個模塊（或者兩個系統）： module-A 和 module-B ， A 依賴 B 提供服務。當用戶請求過來的時候， A 就會去請求 B ，讓 B 根據請求進行某些處理（比如：根據單詞 id 查對應的單詞），完成后把結果返回給 A ， A 再對這個結果進行處理。然而，為了保證服務穩定，有可能 B 服務有很多臺機器， A 遇到這個時候就犯難了：我該去找 B 的哪臺機器取數據呢？
最常見的一個 case 就是 nginx ：比如我們的 web 邏輯服務器是 jetty 或者 tomcat ，一般會有多臺， nginx 就需要配置這多臺機器：
upstream simplemain.com {
server 192.168.1.100:8080;
server 192.168.1.101:8080;
}
那這些機器是怎么樣選擇的呢？實際就是負載均衡算法。
老王對負載均衡的理解，他應該包含兩個層面：
1 、負載：就是后端系統的承載能力。比如同等條件下，一個 1 核 cpu-1G 內存的機器的承載能力一般會比 8 核 cpu-8G 內存的機器要差；相同配置下，一個 cpu 利用率為 80% 的機器比 30% 的承載能力一般要差等等。
2 、均衡：保證后端請求的平衡。比如：在同等情況下，分配到多臺機器的請求要相當；有些情況下，同一用戶盡可能分配到同一臺機器等等。
所以，負載均衡的算法實際上就是解決跨系統調用的時候，在考慮后端機器承載情況的前提下，保證請求分配的平衡和合理。
那第二個問題隨之而來： why ？
為什么要有負載均衡呢？
1 、很明顯，如果我們不去考慮后端的承載情況，有可能直接就把某臺機器壓垮了（比如 cpu 利用率已經 80% 了，再給大量的請求直接就干死了），更嚴重的會直接造成雪崩（一臺壓死了，對應的請求又壓倒其他某臺機器上，又干死一臺……），從而致使服務癱瘓。
2 、如果我們均衡算法選的不好，就會導致后端資源浪費。比如：如果選擇一致 Hash 算法，可以很好利用 cache 的容量。而如果用隨機，有可能就會讓 cache 效果大打折扣（每臺機器上都要緩存幾乎相同的內容）。
所以，用負載均衡應該是一個比較好的選擇。
那就解決第三個問題吧： how ？
按照之前的思路，我們還是分成兩個部分來講：負載 & 均衡。
1 、先來看 負載算法 ：
既然要解決后端系統的承載能力，那我們就有很多方式，常見的有以下幾種：
A 、簡單粗暴有效的：手工配置！
大家是不是覺得這個聽起來很山寨呢？其實不是。這種方式對于中小系統來講是最有效最穩定的。因為后端機器的性能配置、上面部署了哪些服務、還能有多大的承載能力等等，我們是最清楚的。那我們在配置的時候，就可以明確的告訴調用者，你只能分配多大的壓力到某臺服務器上，多了不行！
比如，我們經常看到 nginx 的配置：
upstream simplemain.com {
server 192.168.1.100:8080 weight=30 ;
server 192.168.1.101:8080 weight=70 ;
}
就是說，雖然有兩臺后端的服務器，但是他們承載能力是不一樣的，有一個能力更強，我們就給他 70% 的壓力；有一個更弱，我們就給他 30% 的壓力。這樣， nginx 就會把更多的壓力分配給第二臺。
這種方式配置簡單，而且很穩定，基本不會產生分配的抖動。不過，帶來的問題就是分配很固定，不能動態調整。如果你的后端服務器有一段時間出現性能抖動（比如有其他服務擾動了機器的穩定運行，造成 cpu 利用率一段時間升高），前端調用者就很難根據實際的情況重新分配請求壓力。所以，引入了第二種方法。
B 、動態調整。
這種方案會根據機器當前運行的狀態和歷史平均值進行對比，發現如果當前狀態比歷史的要糟糕，那么就動態減少請求的數量。如果比歷史的要好，那么就可以繼續增加請求的壓力，直到達到一個平衡。
具體怎么做呢？
首先，剛開始接入的時候，我們可以計算所有機器對于請求的響應時間，算一個平均值。對于響應較快的機器，我們可以多分配一些請求。如果請求多了導致響應減慢，這個時候就會逐步和其他機器持平，說明這臺機器達到了相應的平衡。
接著，當接入達到平衡以后，就可以統計這臺機器平均的響應時間。如果某一段響應請求變慢了（同時比其他機器都要慢），就可以減少對他請求的分配，將壓力轉移一部分到其他機器，直到所有機器達到一個整體的平衡。
這種方案是不是看起來很高級呢？他的好處在于可以動態的來平衡后面服務器的處理能力。不過，任何事物都有兩面性。這種方案如果遇到極端情況，可能會造成系統雪崩！當某臺機器出現短暫網絡抖動的時候，他的響應就可能變慢，這個時候，前端服務就會將他的請求分配給其他的機器。如果分配的很多，就有可能造成某些機器響應也變慢。然后又將這些機器的請求分配給另外的……如此這般，那些勤勤懇懇的機器終將被這些請求壓死。
所以，更好的方案，將兩者結合。一方面靜態配置好承載負荷的一個范圍，超過最大的就扔掉；另一方面動態的監控后端機器的響應情況，做小范圍的請求調整。
2 、 均衡算法
均衡算法主要解決將請求如何發送給后端服務。經常會用到以下四種算法：隨機（ random ）、輪訓（ round-robin ）、一致哈希（ consistent-hash ）和主備（ master-slave ）。
比如：我們配置 nginx 的時候，經常會用到這樣的配置：
upstream simplemain.com {
ip_hash ;
server 192.168.1.100:8080;
server 192.168.1.101:8080;
}
這個配置就是按 ip 做 hash 算法，然后分配給對應的機器。
接下來我們詳細的看看這幾個算法是如何來工作的。
A 、隨機算法 。
顧名思義，就是在選取后端服務器的時候，采用隨機的一個方法。在具體講這個算法之前，我們先來看看一個例子，我們寫如下 C 語言的代碼 :
#include <stdlib.h>
#include <stdio.h>
int main()
{
srand( 1234 );
printf( " %d\n " , rand());
return 0 ;
}
我們用 srand 函數給隨機算法播了一個 1234 的種子，然后再去隨機數，接著我們編譯和鏈接 gcc rand.c -o rand
按理想中說，我們每次運行 rand 這個程序，都應該得到不一樣的結果，對吧。可是……
可以看到，我們每次運行的結果都是一樣的！！出了什么問題呢？
我們說的隨機，在計算機算法中通常采用的是一種偽隨機的算法。我們會先給算法放一個種子，然后根據一定的算法將種子拿來運算，最后得到一個所謂的隨機值。我們將上面的算法做一個小小的改動，將 1234 改為 time(NULL) ，效果就不一樣了：
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
int main()
{
srand(( int )time( NULL ));
printf( " %d\n " , rand());
return 0 ;
}
time 這個函數會獲取當前秒數，然后將這個值作為種子放入到偽隨機函數，從而計算出的偽隨機值會因為秒數不一樣而不同。
具體來看一下 java 源代碼里如何來實現的。我們常用的 java 隨機類是 java.util.Random 這個類。他提供了兩個構造函數：
public Random() {
this ( seedUniquifier () ^ System. nanoTime ());
}
public Random( long seed) {
if (getClass() == Random. class )
this . seed = new AtomicLong( initialScramble (seed));
else {
//subclass might have overriden setSeed
this . seed = new AtomicLong();
setSeed(seed);
}
}
我們可以看到，這個類也是需要一個種子。然后我們獲取隨機值的時候，會調用 next 函數：
protected int next ( int bits) {
long oldseed, nextseed;
AtomicLong seed = this . seed ;
do {
oldseed = seed.get();
nextseed = (oldseed * multiplier + addend ) & mask ;
} while (!seed.compareAndSet(oldseed, nextseed));
return ( int )(nextseed>>> (48 - bits));
}
這個函數會利用種子進行一個運算，然后得到隨機值。所以，我們看起來隨機的一個算法，實際上跟時間是相關的，跟算法的運算是相關的。并不是真正的隨機。
好了，話歸正題，我們用隨機算法怎么樣做請求均衡呢？比如，還是我們之前那個 nginx 配置：
upstream simplemain.com {
server 192.168.1.100:8080 weight=30 ;
server 192.168.1.101:8080 weight=70 ;
}
我們有兩臺機器，分別需要承載 30% 和 70% 的壓力，那么我們算法就可以這樣來寫（偽代碼）：
bool res = abs(rand()) % 100 < 30
這句話是什么意思呢？
1 、我們先產生一個偽隨機數： rand()
2 、將這個偽隨機數的轉化為非負數 : abs(rand())
3 、將這個數取模 100 ，將值轉化到 [0,100) 的半開半閉區間： abs(rand()) % 100
4 、看這個數是否落入了前 30 個數的區間 [0,30) ： abs(rand()) % 100 < 30
如果隨機是均勻的話，他們落到 [0,100) 這個區間里一定是均勻的，所以只要在 [0,30) 這個區間里，我們就分給第一臺機器，否則就分給第二臺機器。
其實這里講述的只是一種方法，還有很多其他的方法，大家都可以去想想。
隨機算法是我們最最最最最最常用的算法，絕大多數情況都使用他。首先，從概率上講，它能保證我們的請求基本是分散的，從而達到我們想要的均衡效果；其次，他又是無狀態的，不需要維持上一次的選擇狀態，也不需要均衡因子等等。總體上，方便實惠又好用，我們一直用他！
B 、輪訓算法 。
輪訓算法就像是挨個數數一樣（ 123-123-123 ……），一個個的輪著來。
upstream simplemain.com {
server 192.168.1.100:8080 weight=30 ;
server 192.168.1.101:8080 weight=70 ;
}
還是這個配置，我們就可以這樣來做（為了方便，我們把第一臺機器叫做 A ，第二臺叫做 B ）：
1 、我們先給兩臺機器做個排序的數組： array = [ABBABBABBB]
2 、我們用一個計數指針來標明現在數組的位置： idx = 3
3 、當一個請求來的時候，我們就把指針對應的機器選取出來，并且指針加一，挪到下一個位置。
這樣，十個請求，我們就可以保證有 3 個一定是 A ， 7 個一定是 B 。
輪訓算法在實際中也有使用，但是因為要維護 idx 指針，所以是有狀態的。我們經常會用隨機算法取代。
C 、一致哈希算法 。
這個算法是大家討論最對，研究最多，神秘感最強的一個算法。老王當年剛了解這個算法的時候，也是花了很多心思去研究他。在百度上搜：“一致 hash ”，大概有 321 萬篇相關文章。
大家到網上搜這個算法，一般都會講將 [0,2 32 ) 所有的整數投射到一個圓上，然后再將你的機器的唯一編碼（比如： IP ）通過 hash 運算得到的整數也投射到這個圓上（ Node-A 、 Node-B ）。如果一個請求來了，就將這個請求的唯一編碼（比如：用戶 id ）通過 hash 算法運算得到的整數也投射到這個圓上（ request-1 、 request-2 ），通過順時針方向，找到第一個對應的機器。如下圖：
當時老王看了這些文章也覺得很有道理，但是過了一段時間就忘了……自己琢磨了一段時間，不斷的問自己，為什么要這樣做呢？
過了很久，老王有了一些體會。實際上，一致 Hash 要解決的是兩個問題：
1 、散列的不變性：就是同一個請求（比如：同一個用戶 id ）盡量的落入到一臺機器，不要因為時間等其他原因，落入到不同的機器上了；
2 、異常以后的分散性：當某些機器壞掉（或者增加機器），原來落到同一臺機器的請求（比如：用戶 id 為 1 ， 101 ， 201 ），盡量分散到其他機器，不要都落入其他某一臺機器。這樣對于系統的沖擊和影響最小。
有了以上兩個原則，這個代碼寫起來就很好寫了。比如我們可以這樣做 ( 假定請求的用戶 id=100 ）：
1 、我們將這個 id 和所有的服務的 IP 和端口拼接成一個字符串：
str1 = "192.168.1.100:8080-100"
str2 = "192.168.1.101:8080-100"
2 、對這些字符串做 hash ，然后得到對應的一些整數：
iv1 = hash(str1)
iv2 = hash(str2)
3 、對這些整數做從大到小的排序，選出第一個。
好，現在來看看我們的這個算法是否符合之前說的兩個原則。
1 、散列的不變性：很明顯，這個算法是可重入的，只要輸入一樣，結果肯定一樣；
2 、異常以后的分散性：當某臺機器壞掉以后，原本排到第一的這些機器就被第二位的取代掉了。只要我們的 hash 算法是分散的，那么得到排到第二位的機器就是分散的。
所以，這種算法其實也能達到同樣的目的。當然，可以寫出同樣效果的算法很多很多，大家也可以自己琢磨琢磨。最根本的，就是要滿足以上說的原則。
一致 Hash 算法用的最多的場景，就是分配 cache 服務。將某一個用戶的數據緩存在固定的某臺服務器上，那么我們基本上就不用多臺機器都緩存同樣的數據，這樣對我們提高緩存利用率有極大的幫助。
不過硬幣都是有兩面的，一致 Hash 也不例外。當某臺機器出問題以后，這臺機器上的 cache 失效，原先壓倒這臺機器上的請求，就會壓到其他機器上。由于其他機器原先沒有這些請求的緩存，就有可能直接將請求壓到數據庫上，造成數據庫瞬間壓力增大。如果壓力很大的話，有可能直接把數據庫壓垮。
所以，在考慮用一致 Hash 算法的時候，一定要估計一下如果有機器宕掉后，后端系統是否能承受對應的壓力。如果不能，則建議浪費一點內存利用率，使用隨機算法。
D 、主備算法 。
這個算法核心的思想是將請求盡量的放到某個固定機器的服務上（注意這里是盡量），而其他機器的服務則用來做備份，如果出現問題就切換到另外的某臺機器的服務上。
這個算法用的相對不是很多，只是在一些特殊情況下會使用這個算法。比如，我有多臺 Message Queue 的服務，為了保證提交數據的時序性，我就想把所有的請求都盡量放到某臺固定的服務上，當這臺服務出現問題，再用其他的服務。
那怎么做呢？最簡單的做法，我們就對每臺機器的 IP ： Port 做一個 hash ，然后按從大到小的順序排序，第一個就是我們想要的結果。如果第一個出現問題，那我們再取第二個： head(sort(hash("IP:Port1"), hash("IP:Port2"), …… ))
當然，還有其他做法。比如：老王做的 Naming Service 就用一個集中式的鎖服務來判定當前的主服務器，并對他進行鎖定。
好了，關于負載均衡相關的算法就大體上說這么多。其實還有一個相關話題沒有說，就是健康檢查。他的作用就是對所有的服務進行存活和健康檢測，看是否需要提供給負載均衡做選擇。如果一臺機器的服務出現了問題，健康檢查就會將這臺機器從服務列表中去掉，讓負載均衡算法看不到這臺機器的存在。這個是給負載均衡做保障的，但是可以不劃在他的體系內。不過也有看法是可以將這個也算在負載均衡算法中。因為這個算法的實現其實也比較復雜，老王這次就不講這個算法了，可以放到接下來的文章中來分析。
==== 感謝的分割線 ====
1 、上周做了一個問卷，想了解一下大家都關注哪些技術方向。好多盆友都投了票，給老王提了建議和想法，讓老王對接下來的扯淡有了更多的思考；
2 、有幾位盆友問老王怎么沒開通評論和打賞，準備要給老王打個賞。更有一位姓姜的盆友加了老王的微信，硬給老王發了紅包（是老王收到的第一個賞哦，老王會永遠記住的）。讓老王感動的不行。本來老王寫這些東東沒太想其他的，就想把多年的積累記錄下來，分享給更多的人，所以收到大家的贊賞真的很感動。也巧，這周收到微信的原創邀請和評論了 ~
3 、好幾位盆友還將自己未來的發展方向找老王來聊。這是把自己的未來跟老王做分享和交流，這是對老王最大的信任！
所以，老王要對所有支持我的朋友深深的鞠一躬，謝謝各位的支持與信任！