負載均衡的那些算法們

今天跟大伙兒聊的是負載均衡相干的1些算法。老王在百度的時候（估計是5⑹年前），寫過1個通用的基礎庫（不知道現在還有無部門在用），用來做不同系統間負載均衡。太細節的東東估計想不起來了，不過基本的算法可以跟大家做做分享。

那第1個問題：what's load-balance?

假定我有兩個模塊（或兩個系統）：module-A和module-B，A依賴B提供服務。當用戶要求過來的時候，A就會去要求B，讓B根據要求進行某些處理（比如：根據單詞id查對應的單詞），完成后把結果返回給A，A再對這個結果進行處理。但是，為了保證服務穩定，有可能B服務有很多臺機器，A遇到這個時候就犯難了：我該去找B的哪臺機器取數據呢？

最多見的1個case就是nginx：比如我們的web邏輯服務器是jetty或tomcat，1般會有多臺，nginx就需要配置這多臺機器：

upstream simplemain.com {

     server  192.168.1.100:8080;

     server  192.168.1.101:8080;

}

那這些機器是怎樣樣選擇的呢？實際就是負載均衡算法。

老王對負載均衡的理解，他應當包括兩個層面：

1、負載：就是后端系統的承載能力。比猶如等條件下，1個1核cpu⑴G內存的機器的承載能力1般會比8核cpu⑻G內存的機器要差；相同配置下，1個cpu利用率為80%的機器比30%的承載能力1般要差等等。

2、均衡：保證后端要求的平衡。比如：在同等情況下，分配到多臺機器的要求要相當；有些情況下，同1用戶盡量分配到同1臺機器等等。

所以，負載均衡的算法實際上就是解決跨系統調用的時候，在斟酌后端機器承載情況的條件下，保證要求分配的平衡和公道。

那第2個問題隨之而來：why？

為何要有負載均衡呢？

1、很明顯，如果我們不去斟酌后真個承載情況，有可能直接就把某臺機器壓垮了（比如cpu利用率已80%了，再給大量的要求直接就干死了），更嚴重的會直接造成雪崩（1臺壓死了，對應的要求又壓倒其他某臺機器上，又干死1臺……），從而導致服務癱瘓。

2、如果我們均衡算法選的不好，就會致使后端資源浪費。比如：如果選擇1致Hash算法，可以很好利用cache的容量。而如果用隨機，有可能就會讓cache效果大打折扣（每臺機器上都要緩存幾近相同的內容）。

所以，用負載均衡應當是1個比較好的選擇。

那就解決第3個問題吧：how？

依照之前的思路，我們還是分成兩個部份來說：負載& 均衡。

1、先來看負載算法：

既然要解決后端系統的承載能力，那我們就有很多方式，常見的有以下幾種：

A、簡單粗魯有效的：手工配置！

大家是否是覺得這個聽起來很山寨呢？其實不是。這類方式對中小系統來說是最有效最穩定的。由于后端機器的性能配置、上臉部署了哪些服務、還能有多大的承載能力等等，我們是最清楚的。那我們在配置的時候，就能夠明確的告知調用者，你只能分配多大的壓力到某臺服務器上，多了不行！

比如，我們常常看到nginx的配置：

upstream simplemain.com {

     server  192.168.1.100:8080 weight=30;

     server  192.168.1.101:8080 weight=70;

}

就是說，雖然有兩臺后真個服務器，但是他們承載能力是不1樣的，有1個能力更強，我們就給他70%的壓力；有1個更弱，我們就給他30%的壓力。這樣，nginx就會把更多的壓力分配給第2臺。

這類方式配置簡單，而且很穩定，基本不會產生分配的抖動。不過，帶來的問題就是分配很固定，不能動態調劑。如果你的后端服務器有1段時間出現性能抖動（比如有其他服務擾動了機器的穩定運行，造成cpu利用率1段時間升高），前端調用者就很難根據實際的情況重新分配要求壓力。所以，引入了第2種方法。

B、動態調劑。

這類方案會根據機器當前運行的狀態和歷史平均值進行對照，發現如果當前狀態比歷史的要糟，那末就動態減少要求的數量。如果比歷史的要好，那末就能夠繼續增加要求的壓力，直到到達1個平衡。

具體怎樣做呢？

首先，剛開始接入的時候，我們可以計算所有機器對要求的響應時間，算1個平均值。對響應較快的機器，我們可以多分配1些要求。如果要求多了致使響應減慢，這個時候就會逐漸和其他機器持平，說明這臺機器到達了相應的平衡。

接著，當接入到達平衡以后，就能夠統計這臺機器平均的響應時間。如果某1段響應要求變慢了（同時比其他機器都要慢），就能夠減少對他要求的分配，將壓力轉移1部份到其他機器，直到所有機器到達1個整體的平衡。

這類方案是否是看起來很高級呢？他的好處在于可以動態的來平衡后面服務器的處理能力。不過，任何事物都有兩面性。這類方案如果遇到極端情況，可能會造成系統雪崩！當某臺機器出現短暫網絡抖動的時候，他的響應便可能變慢，這個時候，前端服務就會將他的要求分配給其他的機器。如果分配的很多，就有可能造成某些機器響應也變慢。然后又將這些機器的要求分配給另外的……如此這般，那些勤勤奮懇的機器終將被這些要求壓死。

所以，更好的方案，將二者結合。1方面靜態配置好承載負荷的1個范圍，超過最大的就扔掉；另外一方面動態的監控后端機器的響應情況，做小范圍的要求調劑。

2、均衡算法

均衡算法主要解決將要求如何發送給后端服務。常常會用到以下4種算法：隨機（random）、輪訓（round-robin）、1致哈希（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、隨機算法。

顧名思義，就是在選取后端服務器的時候，采取隨機的1個方法。在具體講這個算法之前，我們先來看看1個例子，我們寫以下C語言的代碼:

#include <stdlib.h>

#include<stdio.h>

int main()

{

        srand(1234);

        printf("%d\n", rand());

       return0;

}

我們用srand函數給隨機算法播了1個1234的種子，然后再去隨機數，接著我們編譯和鏈接gcc rand.c -o rand

按理想中說，我們每次運行rand這個程序，都應當得到不1樣的結果，對吧。可是……

可以看到，我們每次運行的結果都是1樣的！！出了甚么問題呢？

我們說的隨機，在計算機算法中通常采取的是1種偽隨機的算法。我們會先給算法放1個種子，然后根據1定的算法將種子拿來運算，最后得到1個所謂的隨機值。我們將上面的算法做1個小小的改動，將1234改成time(NULL)，效果就不1樣了：

#include <stdlib.h>

#include <stdio.h>

#include<time.h>

int main()

{

        srand((int)time(NULL));

        printf("%d\n", rand());

       return 0;

}

time這個函數會獲得當前秒數，然后將這個值作為種子放入到偽隨機函數，從而計算出的偽隨機值會由于秒數不1樣而不同。

具體來看1下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);

    }

}

我們可以看到，這個類也是需要1個種子。然后我們獲得隨機值的時候，會調用next函數：

protectedintnext(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));

}

這個函數會利用種子進行1個運算，然后得到隨機值。所以，我們看起來隨機的1個算法，實際上跟時間是相干的，跟算法的運算是相干的。其實不是真實的隨機。

好了，話歸正題，我們用隨機算法怎樣樣做要求均衡呢？比如，還是我們之前那個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、我們先產生1個偽隨機數：rand()

2、將這個偽隨機數的轉化為非負數: abs(rand())

3、將這個數取模100，將值轉化到[0,100)的半開半閉區間：abs(rand()) % 100

4、看這個數是不是落入了前30個數的區間[0,30)：abs(rand()) % 100 < 30

如果隨機是均勻的話，他們落到[0,100)這個區間里1定是均勻的，所以只要在[0,30)這個區間里，我們就分給第1臺機器，否則就分給第2臺機器。

其實這里講述的只是1種方法，還有很多其他的方法，大家都可以去想一想。

隨機算法是我們最最最最最最經常使用的算法，絕大多數情況都使用他。首先，從幾率上講，它能保證我們的要求基本是分散的，從而到達我們想要的均衡效果；其次，他又是無狀態的，不需要保持上1次的選擇狀態，也不需要均衡因子等等。整體上，方便實惠又好用，我們1直用他！

B、輪訓算法。

輪訓算法就像是挨個數數1樣（123⑴23⑴23……），1個個的輪著來。

upstream simplemain.com {

     server  192.168.1.100:8080 weight=30;

     server  192.168.1.101:8080 weight=70;

}

還是這個配置，我們就能夠這樣來做（為了方便，我們把第1臺機器叫做A，第2臺叫做B）：

1、我們先給兩臺機器做個排序的數組：array = [ABBABBABBB]

2、我們用1個計數指針來標明現在數組的位置：idx = 3

3、當1個要求來的時候，我們就把指針對應的機器選取出來，并且指針加1，挪到下1個位置。

這樣，10個要求，我們就能夠保證有3個1定是A，7個1定是B。

輪訓算法在實際中也有使用，但是由于要保護idx指針，所以是有狀態的。我們常常會用隨機算法取代。

C、1致哈希算法。

這個算法是大家討論最對，研究最多，神秘感最強的1個算法。老王當年剛了解這個算法的時候，也是花了很多心思去研究他。在百度上搜：“1致hash”，大概有321萬篇相干文章。

大家到網上搜這個算法，1般都會講將[0,2³²)所有的整數投射到1個圓上，然后再將你的機器的唯1編碼（比如：IP）通過hash運算得到的整數也投射到這個圓上（Node-A、Node-B）。如果1個要求來了，就將這個要求的唯1編碼（比如：用戶id）通過hash算法運算得到的整數也投射到這個圓上（request⑴、request⑵），通過順時針方向，找到第1個對應的機器。以下圖：

當時老王看了這些文章也覺得很有道理，但是過了1段時間就忘了……自己揣摩了1段時間，不斷的問自己，為何要這樣做呢？

過了很久，老王有了1些體會。實際上，1致Hash要解決的是兩個問題：

1、散列的不變性：就是同1個要求（比如：同1個用戶id）盡可能的落入到1臺機器，不要由于時間等其他緣由，落入到不同的機器上了；

2、異常以后的分散性：當某些機器壞掉（或增加機器），原來落到同1臺機器的要求（比如：用戶id為1，101，201），盡可能分散到其他機器，不要都落入其他某1臺機器。這樣對系統的沖擊和影響最小。

有了以上兩個原則，這個代碼寫起來就很好寫了。比如我們可以這樣做(假定要求的用戶id=100）：

1、我們將這個id和所有的服務的IP和端口拼接成1個字符串：

str1 = "192.168.1.100:8080⑴00"

str2 = "192.168.1.101:8080⑴00"

2、對這些字符串做hash，然后得到對應的1些整數：

iv1 = hash(str1)

iv2 = hash(str2)

3、對這些整數做從大到小的排序，選出第1個。

好，現在來看看我們的這個算法是不是符合之前說的兩個原則。

1、散列的不變性：很明顯，這個算法是可重入的，只要輸入1樣，結果肯定1樣；

2、異常以后的分散性：當某臺機器壞掉以后，本來排到第1的這些機器就被第2位的取代掉了。只要我們的hash算法是分散的，那末得到排到第2位的機器就是分散的。

所以，這類算法其實也能到達一樣的目的。固然，可以寫出一樣效果的算法很多很多，大家也能夠自己揣摩揣摩。最根本的，就是要滿足以上說的原則。

1致Hash算法用的最多的場景，就是分配cache服務。將某1個用戶的數據緩存在固定的某臺服務器上，那末我們基本上就不用多臺機器都緩存一樣的數據，這樣對我們提高緩存利用率有極大的幫助。

不過硬幣都是有兩面的，1致Hash也不例外。當某臺機器出問題以后，這臺機器上的cache失效，本來壓倒這臺機器上的要求，就會壓到其他機器上。由于其他機器本來沒有這些要求的緩存，就有可能直接將要求壓到數據庫上，造成數據庫瞬間壓力增大。如果壓力很大的話，有可能直接把數據庫壓垮。

所以，在斟酌用1致Hash算法的時候，1定要估計1下如果有機器宕掉后，后端系統是不是能承受對應的壓力。如果不能，則建議浪費1點內存利用率，使用隨機算法。

D、主備算法。

這個算法核心的思想是將要求盡可能的放到某個固定機器的服務上（注意這里是盡可能），而其他機器的服務則用來做備份，如果出現問題就切換到另外的某臺機器的服務上。

這個算法用的相對不是很多，只是在1些特殊情況下會使用這個算法。比如，我有多臺Message Queue的服務，為了保證提交數據的時序性，我就想把所有的要求都盡可能放到某臺固定的服務上，當這臺服務出現問題，再用其他的服務。

那怎樣做呢？最簡單的做法，我們就對每臺機器的IP：Port做1個hash，然后按從大到小的順序排序，第1個就是我們想要的結果。如果第1個出現問題，那我們再取第2個：head(sort(hash("IP:Port1"), hash("IP:Port2"), ……))

固然，還有其他做法。比如：老王做的Naming Service就用1個集中式的鎖服務來判定當前的主服務器，并對他進行鎖定。

好了，關于負載均衡相干的算法就大體上說這么多。其實還有1個相干話題沒有說，就是健康檢查。他的作用就是對所有的服務進行存活和健康檢測，看是不是需要提供給負載均衡做選擇。如果1臺機器的服務出現了問題，健康檢查就會將這臺機器從服務列表中去掉，讓負載均衡算法看不到這臺機器的存在。這個是給負載均衡做保障的，但是可以不劃在他的體系內。不過也有看法是可以將這個也算在負載均衡算法中。由于這個算法的實現其實也比較復雜，老王這次就不講這個算法了，可以放到接下來的文章中來分析。

====感謝的分割線 ====

1、上周做了1個問卷，想了解1下大家都關注哪些技術方向。好多盆友都投了票，給老王提了建議和想法，讓老王對接下來的扯淡有了更多的思考；

2、有幾位盆友問老王怎樣沒開通評論和打賞，準備要給老王打個賞。更有1位姓姜的盆友加了老王的微信，硬給老王發了紅包（是老王收到的第1個賞哦，老王會永久記住的）。讓老王感動的不行。本來老王寫這些東東沒太想其他的，就想把多年的積累記錄下來，分享給更多的人，所以收到大家的贊美真的很感動。也巧，這周收到微信的原創約請和評論了~

3、好幾位盆友還將自己未來的發展方向找老王來聊。這是把自己的未來跟老王做分享和交換，這是對老王最大的信任！

所以，老王要對所有支持我的朋友深深的鞠1躬，謝謝各位的支持與信任！

有興趣的盆友，可以繼續關注老王：simplemain

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈