背景介紹

在分布式系統(tǒng)中每聪，負(fù)載均衡是非常重要的環(huán)節(jié)摔竿，通過負(fù)載均衡將請求派發(fā)到網(wǎng)絡(luò)中的一個或多個節(jié)點上進(jìn)行處理潮尝。

image

通常來說，負(fù)載均衡分為硬件負(fù)載均衡及軟件負(fù)載均衡理茎。硬件負(fù)載均衡黑界，顧名思義，在服務(wù)器節(jié)點之間安裝專門的硬件進(jìn)行負(fù)載均衡的工作皂林，F(xiàn)5或者A10便為其中的佼佼者朗鸠。軟件負(fù)載均衡則是通過在服務(wù)器上安裝的特定的負(fù)載均衡軟件或是自帶負(fù)載均衡模塊完成對請求的分配派發(fā)。例如础倍，平時我們使用的Nginx或者API-Gateway網(wǎng)關(guān)服務(wù)就主要采用負(fù)載均衡的方式去轉(zhuǎn)發(fā)分派下游服務(wù)烛占。

image

負(fù)載均衡的算法策略

一般而言，有以下幾種常見的負(fù)載均衡策略：

輪詢機(jī)制（一般默認(rèn)的策略）

【輪詢機(jī)制】作為非常經(jīng)典的負(fù)載均衡策略沟启，早期該策略應(yīng)用地非常廣泛忆家。

算法原理

其原理很簡單，給每個請求標(biāo)記一個序號德迹，然后將請求依次派發(fā)到服務(wù)器節(jié)點中芽卿，適用于集群中各個節(jié)點提供服務(wù)能力等同且無狀態(tài)的場景。算法實現(xiàn)原理圖如下所示胳搞。

image

該算法原理三要素

• 為每個服務(wù)器進(jìn)行建立一個編號或者序號（作為唯一標(biāo)識）卸例。

• 負(fù)載均衡器這一側(cè)需要建立一個全局的計數(shù)器称杨，作為負(fù)載均衡的參數(shù)。每次調(diào)用都進(jìn)行+1

• 當(dāng)負(fù)載均衡器的計數(shù)器當(dāng)前值與下游服務(wù)的數(shù)量取模之后筷转，會得出對應(yīng)的序號值列另，則回去進(jìn)行分派到對應(yīng)序號值的下游服務(wù)即可。

缺略優(yōu)點

實現(xiàn)比較簡單旦装，均衡化較好页衙，每一個節(jié)點都屬于公平化分配，（上面也說到了）比較適合相同場景和條件規(guī)則下的所有下游服務(wù)阴绢。

策略缺點

缺點也非常明顯店乐，該策略將節(jié)點視為等同，與實際中復(fù)雜的環(huán)境不符呻袭。加權(quán)輪詢?yōu)檩喸兊囊粋€改進(jìn)策略眨八，每個節(jié)點會有權(quán)重屬性，但是因為權(quán)重的設(shè)置難以做到隨實際情況變化左电，仍有一定的不足廉侧。

隨機(jī)機(jī)制

【隨機(jī)機(jī)制】與輪詢相似，只是不需要對每個請求進(jìn)行編號篓足，每次隨機(jī)取一個下游服務(wù)節(jié)點即可段誊。

算法原理

其原理也很簡單，就是采用隨機(jī)算法或者散列算法將請求服務(wù)進(jìn)行隨機(jī)散列到下游的不同的服務(wù)節(jié)點栈拖，該策略也將后端的每個節(jié)點是為等同的连舍。

另外同樣也有改進(jìn)的加權(quán)隨機(jī)的算法，不再贅述涩哟，然后將請求依次派發(fā)到服務(wù)器節(jié)點中索赏，適用于集群中各個節(jié)點提供服務(wù)能力等同且無狀態(tài)的場景。算法實現(xiàn)原理圖如下所示贴彼。

image

主要依靠于隨機(jī)算法或者隨機(jī)組件去生產(chǎn)隨機(jī)值之后在進(jìn)行取模就可以潜腻。

該算法原理三要素

• 為每個服務(wù)器進(jìn)行建立一個編號或者序號（作為唯一標(biāo)識）。

• 負(fù)載均衡器這一側(cè)需要建立一個隨機(jī)數(shù)算法組件器仗。每次調(diào)用都進(jìn)行分配融涣。

• 然后選取隨機(jī)值對應(yīng)的服務(wù)組件即可（可以取模、也可以采用隨機(jī)數(shù)從該范圍內(nèi)選取的方式）

缺略優(yōu)點

實現(xiàn)比較簡單青灼，隨機(jī)性較好暴心，每一個節(jié)點都屬于公平化分配，（上面也說到了）比較適合相同場景和條件規(guī)則下的所有下游服務(wù)杂拨。

策略缺點

缺點也非常明顯，該策略將節(jié)點視為等同悯衬，與實際中復(fù)雜的環(huán)境不符弹沽。加權(quán)輪詢?yōu)檩喸兊囊粋€改進(jìn)策略檀夹，每個節(jié)點會有權(quán)重屬性，但是因為權(quán)重的設(shè)置難以做到隨實際情況變化策橘，仍有一定的不足炸渡。

最小響應(yīng)時間

通過記錄每次請求所需的時間，得出平均的響應(yīng)時間丽已，然后根據(jù)響應(yīng)時間選擇最小的響應(yīng)時間蚌堵。

算法原理

該策略能較好地反應(yīng)服務(wù)器的狀態(tài)，但是由于是平均響應(yīng)時間的關(guān)系沛婴，時間上有些滯后吼畏，無法滿足快速響應(yīng)的要求。因此在此基礎(chǔ)之上嘁灯，會有一些改進(jìn)版本的策略泻蚊，如只計算最近若干次的平均時間的策略等。算法需要進(jìn)行有狀態(tài)話的方式進(jìn)行統(tǒng)計每一次請求丑婿，算法實現(xiàn)原理圖如下所示性雄。

image

主要依靠于隨機(jī)算法或者隨機(jī)組件去生產(chǎn)隨機(jī)值之后在進(jìn)行取模就可以。

該算法原理三要素

• 不需要為每一個服務(wù)節(jié)點建立序號了羹奉，但是需要進(jìn)行對每一個服務(wù)節(jié)點采用一個bucket存儲對應(yīng)的調(diào)用次數(shù)以及調(diào)用的耗時總和秒旋。作為計算平均耗時的依據(jù)。

• 耗時選擇器：在負(fù)載均衡器端調(diào)用的時候诀拭，將建立一個順序性隊列滩褥，存放依據(jù)最短耗時（正序）排序的方式存儲的隊列模型，故此每次可以取隊首位置的元素節(jié)點作為最短耗時服務(wù)節(jié)點炫加。

  • 當(dāng)然瑰煎，也可以將每次最短的耗時時間的服務(wù)節(jié)點直接存儲在負(fù)載均衡器節(jié)點中，這樣會提高相應(yīng)的性能俗孝，

• 然后選取隨機(jī)值對應(yīng)的服務(wù)組件即可（可以取模酒甸、也可以采用隨機(jī)數(shù)從該范圍內(nèi)選取的方式）

image

缺略優(yōu)點

• 可以依據(jù)實際情況進(jìn)行動態(tài)計算最合適的服務(wù)節(jié)點進(jìn)行調(diào)用，可以實現(xiàn)能者多勞赋铝，讓優(yōu)秀的服務(wù)節(jié)點更加出色的發(fā)揮其作用插勤，慢慢的可以屏蔽掉不好用或者有問題的節(jié)點。

• 可以促使性能和服務(wù)能力革骨、可以體驗度達(dá)到一個比較高的高度和效果农尖。

策略缺點

• 性能會造成一段時間的影響，如果不考慮絕對一致性良哲，也可以后臺進(jìn)行異步計算進(jìn)行可以能減低每次計算排序服務(wù)節(jié)點所造成的耗時盛卡。

• 此外還可以考慮當(dāng)不存在最短耗時記錄的時候其算法是存在短時間不可靠的問題，隨意最好可以做一下提前預(yù)熱模式筑凫。

• 客觀問題是否如何排除滑沧，當(dāng)由于網(wǎng)絡(luò)因素導(dǎo)致某幾次該節(jié)點的耗時耗費很久并村，會導(dǎo)致算法模式的影響，所以是否以及選取合適的調(diào)用次數(shù)統(tǒng)計閾值是一個需要好好考慮的問題滓技。例如只有當(dāng)調(diào)用5次以上才進(jìn)行計算平均耗時哩牍，否則不會考慮其計算，好比一個服務(wù)節(jié)點只調(diào)用了一次并且耗時非常少令漂，其實這個節(jié)點耗時計算過于主觀以及巧合膝昆。

最小并發(fā)數(shù)

客戶端的每一次請求服務(wù)在服務(wù)器停留的時間可能會有較大的差異，隨著工作時間加長,如果采用簡單的輪循或隨機(jī)均衡算法,每一臺服務(wù)器上的連接進(jìn)程可能會產(chǎn)生較大的不同,并沒有達(dá)到真正的負(fù)載均衡?

算法原理

最小并發(fā)數(shù)的策略則是記錄了當(dāng)前時刻叠必，每個備選節(jié)點正在處理的事務(wù)數(shù)荚孵，然后選擇并發(fā)數(shù)最小的節(jié)點。該策略能夠快速地反應(yīng)服務(wù)器的當(dāng)前狀況挠唆，較為合理地將負(fù)責(zé)分配均勻处窥，適用于對當(dāng)前系統(tǒng)負(fù)載較為敏感的場景。

image

該算法原理三要素

• 當(dāng)處理請求接收的時候為該節(jié)點的計數(shù)器+1

• 當(dāng)返回并且釋放請求的時候為該節(jié)點的計數(shù)器-1

• 每次依據(jù)每個后臺異步計算的排序隊列進(jìn)行選取最短的節(jié)點作為每次請求的首選服務(wù)節(jié)點玄组。（排序規(guī)則為：從小打到去進(jìn)行依據(jù)當(dāng)前處理事務(wù)數(shù)進(jìn)行排序）滔驾，

缺略優(yōu)點

• 可以依據(jù)實際情況進(jìn)行動態(tài)計算最合適的服務(wù)節(jié)點進(jìn)行調(diào)用，可以讓大家動態(tài)化實現(xiàn)的均衡模式進(jìn)行分配俄讹，讓每一個節(jié)點都可以充分進(jìn)行處理請求哆致，而不是壓在某一個或者某幾個服務(wù)節(jié)點進(jìn)行處理，其他節(jié)點變得過于空閑患膛。適用于集群中各個節(jié)點提供服務(wù)能力等同且無狀態(tài)的場景摊阀，比起輪詢模式其動態(tài)化更好。

• 可以促使性能和服務(wù)能力踪蹬、可以體驗度達(dá)到一個比較高的高度和效果胞此。

策略缺點

• 與最小耗時相同，性能會造成一段時間的影響跃捣，如果不考慮絕對一致性漱牵，也可以后臺進(jìn)行異步計算進(jìn)行可以能減低每次計算排序服務(wù)節(jié)點所造成的耗時。

哈希散列

在后端節(jié)點有狀態(tài)的情況下疚漆，需要使用哈希的方法進(jìn)行負(fù)載均衡酣胀，此種情況下情況比較復(fù)雜∪⑵福可以理解為輪詢模式的升級版闻镶，在這里不是單純的考慮取模的計算方式，而是采用key的方式進(jìn)行計算-依賴于hash函數(shù)進(jìn)行計算丸升。

算法三要素

• hash值映射表铆农，用于計算提供路由能力，方便負(fù)載均衡器選取計算后的Hash值與節(jié)點的Hash標(biāo)準(zhǔn)值進(jìn)行匹配路由发钝。

• hash值計算器：主要用于計算每一個服務(wù)節(jié)點的hash計算值顿涣，以及每次請求的hash值波闹，從而進(jìn)行數(shù)據(jù)對比酝豪。

算法優(yōu)點

• 散列性和公平性更加的優(yōu)秀和完善
• 性能計算非常的不錯涛碑，接近于O(1)的時間復(fù)雜度。
• 與輪詢一樣孵淘，思路較為簡單蒲障。
• 可以實現(xiàn)相同的條件，會實現(xiàn)數(shù)據(jù)指紋模式瘫证，數(shù)據(jù)請求追蹤方式揉阎，例如：原始ip - 會匹配相同的服務(wù)節(jié)點，達(dá)成請求的有狀態(tài)話背捌。目前nginx常會使用 ip-hash算法毙籽、url-hash算法模式。

image

算法缺點

• 強(qiáng)依賴于Hash算法和Hash組件
• 對于時間復(fù)雜度而言降低很多毡庆，但是其依靠的是增加了空間復(fù)雜度坑赡。

分布式系統(tǒng)容錯性因素分析

分布式系統(tǒng)面臨著遠(yuǎn)比單機(jī)系統(tǒng)更加復(fù)雜的環(huán)境，包括不同的網(wǎng)絡(luò)環(huán)境么抗、運行平臺毅否、機(jī)器配置等等。在如此復(fù)雜的環(huán)境中蝇刀，發(fā)生錯誤是不可避免的螟加，然后如何能夠做到容錯性，將發(fā)生錯誤的代價降低到最低是在分布式系統(tǒng)中必須要考慮的問題吞琐。

分布式系統(tǒng)算法的實際選擇

前提背景

選擇不同的負(fù)載均衡策略將會有非常大的不同捆探，考慮下列的情況。完成請求需要如下四個集群站粟，A,B,C,D黍图，其中，假定完成調(diào)用需要調(diào)用集群B3次卒蘸，B集群共有5臺服務(wù)器雌隅。

單次調(diào)用概率計算

當(dāng)集群B中的某臺服務(wù)器出現(xiàn)故障而導(dǎo)致無法提供服務(wù)，若集群中其他容錯手段尚未生效缸沃，那么理想情況下恰起，4/5的請求不受影響。

采用輪詢或隨機(jī)的負(fù)載均衡策略

單次請求派發(fā)到正常節(jié)點的概率為4/5趾牧，那么該請求成功的機(jī)率為 (4/5) * (4/5) * (4/5) = 64/125 ：約為二之一检盼，低于4/5的理想狀態(tài)。

在因此翘单，在此種情況下吨枉，若僅僅采用此種策略蹦渣，會使故障的影響范圍擴(kuò)散，不符合預(yù)期貌亭。

采用最小并發(fā)數(shù)的復(fù)雜均衡策略

假定正常一個請求需耗時10ms柬唯，超時時間設(shè)置為1s，那么圃庭，按照最小并發(fā)數(shù)的策略锄奢，異常節(jié)點的提供服務(wù)的能力為1，正常節(jié)點提供服務(wù)能力為100剧腻，則派發(fā)到異常節(jié)點的概率為1/(100 * 4+1)=1/401拘央，該請求成功的幾率為1(400/401)^3≈99.25%，高于4/5书在。

計算的公式

更加一般地灰伟，設(shè)集群中發(fā)生故障的故障機(jī)器的比例p，那么調(diào)用失敗的預(yù)期概率為

1/(100 * 4+1)=1/401
p * 1/401 = N

N為最后的預(yù)測調(diào)用失敗的概率儒旬，對應(yīng)的成功的概率就為：

(1-p) * 1/401 = M 或 1 - N 

計算的公式

整個請求需要調(diào)用k次栏账，若采用輪詢或隨機(jī)的負(fù)載均衡策略，那么單次派發(fā)到正常節(jié)點的概率為多少义矛？有上面的計算分析的思路可以了解到：（1-P）為正常機(jī)器的比例发笔，那么K次就是：（1-P）的K次方。請求的成功率便會下降低于單次的（1-P）凉翻。

當(dāng)k為3的時候了讨，得到成功率f(p)與p的關(guān)系：

f(p) = (1-p) ^n

從上面的公式可知，在p在增大的時候制轰，請求的成功率f(p)便會有明顯的下降前计，故而在對可靠性要求比較高的分布式系統(tǒng)中，不能簡單地采用此種策略垃杖。

采用最小并發(fā)數(shù)的策略

假設(shè)集群服務(wù)器的總數(shù)為m男杈，假定異常情況下服務(wù)能力下降到正常的1/q，那么單位時間內(nèi)调俘，集群能提供服務(wù)的總數(shù)為：m * (1- 1/q) 伶棒，那么單次派發(fā)到正常節(jié)點的概率為:

m * (1- 1/q) / m

請求的成功率則是上述值的k次方，即

m * (1- 1/q) / m ^k

1. 當(dāng)p在較小的區(qū)間內(nèi)變化時(如(0,0.4])彩库，隨著p的增大,成功率f(p)并未有明顯的下降肤无，在每個節(jié)點可以承受服務(wù)壓力的情況下，可以良好地處理多個節(jié)點故障的異常狀況骇钦。

2. 換個角度思考宛渐，再挖掘一下上述等式，若p為恒定，即集群中若已有一定數(shù)量的機(jī)器發(fā)生了故障窥翩。

3. 所以服務(wù)的超時時間無須設(shè)置地過大业岁，一般來說，設(shè)置為10倍的正常提供服務(wù)器時間即可寇蚊。

在此種情況下笔时，會導(dǎo)致失敗大大提升，即使只有較小比例的集群出現(xiàn)異常幔荒，也會使得請求大量失敗糊闽，故而還需要其他手段檢測到此類型的異常梳玫。

最后的總結(jié)

在實際應(yīng)用中爹梁，客戶端的并發(fā)數(shù)可能存在一直維持在一個較低的水平上，由于客戶端的并發(fā)數(shù)并不能代表服務(wù)端的并發(fā)情況提澎，會造成在客戶端并發(fā)數(shù)較小的情況下姚垃，服務(wù)端實際負(fù)載不均衡的狀況。

故而盼忌，最小并發(fā)數(shù)的負(fù)載均衡策略不適用于在客戶端做負(fù)載均衡积糯，且客戶端負(fù)載較小的情況。這種情況下谦纱，目前采用隨機(jī)的方法解決負(fù)載不均衡的問題看成。當(dāng)然，在實際的分布式系統(tǒng)中跨嘉，因為一個節(jié)點異常而導(dǎo)致其他節(jié)點的壓力增大川慌，可能會使其他節(jié)點的性能下降，他們之間的關(guān)系難以用上述的等式簡單地描述祠乃。