背景
一般生產(chǎn)環(huán)境單機(jī)所能承受的QPS壓力為2w左右，過(guò)大的壓力會(huì)導(dǎo)致服務(wù)器爆炸。即便是單機(jī)能夠撐住2w QPS，一般也不會(huì)這么做，生產(chǎn)環(huán)境一般會(huì)預(yù)留50%的冗余能力，防止QPS因?yàn)槟硞€(gè)熱門(mén)的活動(dòng)而爆炸。當(dāng)QPS超過(guò)單機(jī)所能承受的壓力時(shí)，自然而然會(huì)想到引入分布式集群。那么，某一個(gè)請(qǐng)求會(huì)被哪臺(tái)服務(wù)器處理呢，這是隨機(jī)的，還是說(shuō)按照一定的規(guī)則處理的？這就是負(fù)載均衡算法所要干的事。
負(fù)載均衡器
負(fù)載均衡器就是實(shí)現(xiàn)一種或者多種負(fù)載均衡算法的軟件或者硬件設(shè)備。負(fù)載均衡器根據(jù)協(xié)議層的不同，通常又分為兩種，第一種在四層傳輸層實(shí)現(xiàn)，第二種就是在七層應(yīng)用層實(shí)現(xiàn)。
很多專(zhuān)用的硬件負(fù)載均衡器都支持在TCP層實(shí)現(xiàn)負(fù)載均衡，效率高。當(dāng)然TCP層實(shí)現(xiàn)負(fù)載均衡有它的缺點(diǎn)，如無(wú)法保存長(zhǎng)連接等。所以一般類(lèi)似于BAT這種大公司，都是多層負(fù)載均衡配合的。
一般純軟件實(shí)現(xiàn)的通常在應(yīng)用層來(lái)實(shí)現(xiàn)，這也是應(yīng)用比較多的一種實(shí)現(xiàn)方式。目前比較流行的實(shí)現(xiàn)有Nginx、HAProxy、Keepalived等。當(dāng)然Linux內(nèi)核自帶的LVS(Linux Virtual Server)就是四層的實(shí)現(xiàn)。
輪詢(xún)(Round Robin)
輪詢(xún)是一種很簡(jiǎn)單的實(shí)現(xiàn)，依次將請(qǐng)求分配給后端服務(wù)器。優(yōu)點(diǎn)就是實(shí)現(xiàn)簡(jiǎn)單，請(qǐng)求均勻分配。
缺點(diǎn)也恰恰在于請(qǐng)求均勻分配，因?yàn)楹蠖朔?wù)器通常性能會(huì)有差異，所以希望性能好的服務(wù)器能夠多承擔(dān)一部分。也不適合對(duì)長(zhǎng)連接和命中率有要求的場(chǎng)景。
加權(quán)輪詢(xún)(Weighted Round Robin)
加權(quán)本質(zhì)是一種帶優(yōu)先級(jí)的方式，加權(quán)輪詢(xún)就是一種改進(jìn)的輪詢(xún)算法，輪詢(xún)算法是權(quán)值相同的加權(quán)輪詢(xún)。需要給后端每個(gè)服務(wù)器設(shè)置不同的權(quán)值，決定分配的請(qǐng)求數(shù)比例。這個(gè)算法應(yīng)用就相當(dāng)廣泛了，對(duì)于無(wú)狀態(tài)的負(fù)載場(chǎng)景，非常適合。
優(yōu)點(diǎn)解決了服務(wù)器性能不一的情況，缺點(diǎn)是權(quán)值需要靜態(tài)配置，無(wú)法自動(dòng)調(diào)節(jié)。也不適合對(duì)長(zhǎng)連接和命中率有要求的場(chǎng)景。
隨機(jī)Random
隨機(jī)把請(qǐng)求分配給后端服務(wù)器。請(qǐng)求分配的均勻程度依賴(lài)于隨機(jī)算法了，因?yàn)閷?shí)現(xiàn)簡(jiǎn)單，常常用于配合處理一些極端的情況，如出現(xiàn)熱點(diǎn)請(qǐng)求，這個(gè)時(shí)候就可以random到任意一臺(tái)后端，以分散熱點(diǎn)。當(dāng)然缺點(diǎn)也不言而喻。
哈希Hash
哈希算法想必大家并不陌生，應(yīng)用最為廣泛。根據(jù)Source IP、 Destination IP、URL、或者其它，算hash值或者md5，再采用取模。比如有N臺(tái)服務(wù)器: S1、S2、S3……Sn
hash值 % N
顯然，相同的請(qǐng)求會(huì)被映射到相同的后端。這非常適合維護(hù)長(zhǎng)連接和提高命中率。
但是它天生也有一些缺點(diǎn)。比如說(shuō)，現(xiàn)在某個(gè)請(qǐng)求通過(guò)哈希被映射到S3上去了，如果S3宕機(jī)了，就不得不二次Hash，重新計(jì)算路由時(shí)會(huì)剔除宕機(jī)的后端。
hash值 % (N - 1)
這樣會(huì)導(dǎo)致幾乎所有請(qǐng)求路由產(chǎn)生變化。由此導(dǎo)致命中率的急劇下降。當(dāng)然一般生產(chǎn)環(huán)境通過(guò)提供S3的備機(jī)來(lái)解決這種問(wèn)題，但是主備之間切換也是需要時(shí)間，它們之間的數(shù)據(jù)同步也是有延時(shí)的。所以需要根據(jù)業(yè)務(wù)場(chǎng)景來(lái)權(quán)衡了。
擴(kuò)容也會(huì)有類(lèi)似的問(wèn)題，計(jì)算路由公式變?yōu)椋?/p>
hash值 % (N + 1)
為了解決這種問(wèn)題，一般生產(chǎn)環(huán)境可能采用成倍擴(kuò)容的方式。N -> 2N，這樣求路由可以做到與原來(lái)保持一致。當(dāng)然必不可少的造成機(jī)器資源的浪費(fèi)。請(qǐng)各位看官自行權(quán)衡。
對(duì)于熱點(diǎn)請(qǐng)求，這種Hash算法也可能成在雪崩效應(yīng)，取決于采用何種Hash，基于URL還是基于IP等?？傊荒馨褵狳c(diǎn)請(qǐng)求路由到單機(jī)上，否則單機(jī)撐不住，會(huì)逐個(gè)逐個(gè)被打爆，也就是雪崩效應(yīng)。
最小連接數(shù)LC
最小連接數(shù)(Least Connection)，把請(qǐng)求分配給活動(dòng)連接數(shù)最小的后端服務(wù)器。它通過(guò)活動(dòng)來(lái)估計(jì)服務(wù)器的負(fù)載。比較智能，但需要維護(hù)后端服務(wù)器的連接列表。
加權(quán)最小連接數(shù)WLC
加權(quán)最小連接數(shù)(Weighted Least Connection)，在后端服務(wù)器性能差異較大的情況下，可以?xún)?yōu)化LC的性能，高權(quán)值的服務(wù)可以承受更多的連接負(fù)載。
最短響應(yīng)時(shí)間LRT
最短響應(yīng)時(shí)間(Least Response Time)，把請(qǐng)求分配給平均響應(yīng)時(shí)間最短的后端服務(wù)器。平均響應(yīng)時(shí)間可以通過(guò)ping探測(cè)請(qǐng)求或者正常請(qǐng)求響應(yīng)時(shí)間獲取。
RT(Response Time)是衡量服務(wù)器負(fù)載的一個(gè)非常重要的指標(biāo)。對(duì)于響應(yīng)很慢的服務(wù)器，說(shuō)明其負(fù)載一般很高了，應(yīng)該降低它的QPS。
之前有人說(shuō)使用CPU占用率作為負(fù)載均衡的指標(biāo)，只能說(shuō)沒(méi)理解CPU占用率的實(shí)質(zhì)。理論上CPU占用率是越高越好，說(shuō)明服務(wù)充分利用了CPU資源。但對(duì)于設(shè)計(jì)不合理的程序?qū)е碌腃PU占用過(guò)高這是程序的設(shè)計(jì)問(wèn)題，并不違背這條理論。
一致性Hash
介紹
一致性哈希算法(Consistent Hashing)在1997年由麻省理工學(xué)院提出的一種分布式哈希（DHT）實(shí)現(xiàn)算法，設(shè)計(jì)目標(biāo)是為了解決因特網(wǎng)中的熱點(diǎn)(Hot spot)問(wèn)題。
原理
想象抽象哈希環(huán)，32位整數(shù)表示即可，2^32個(gè)桶位，后端節(jié)點(diǎn)s0, s1…sn等，hash映射到不同的桶位，假想首尾相連，形成環(huán)。（以下圖是我無(wú)恥的盜過(guò)來(lái)的）
將所有后端節(jié)點(diǎn)node通過(guò)Hash映射到環(huán)上，如下圖所示：
實(shí)際請(qǐng)求Job以同樣的方式映射到哈希環(huán)上，如下圖所示：
再按照順時(shí)針的規(guī)則，請(qǐng)求Job沿著哈希環(huán)找到最近的節(jié)點(diǎn)。如圖中，請(qǐng)求Job_1按照規(guī)則就分配到Node_1上，請(qǐng)求Job_k、Job_k+1分配到Node_n上面。
優(yōu)勢(shì)
-
節(jié)點(diǎn)宕機(jī)
Node_1宕機(jī)
假設(shè)后端節(jié)點(diǎn)Node_1宕機(jī)，按照規(guī)則，請(qǐng)求Job_1被分配到Node_k上，但是Job_k、Job_k+1、Job_i不受影響。說(shuō)白了，僅僅影響宕機(jī)節(jié)點(diǎn)上的請(qǐng)求。
-
擴(kuò)容
增加Node_i
按照規(guī)則，僅僅請(qǐng)求Job_k被重新分配到Node_i上去了，其它請(qǐng)求Job_1、Job_k+1、Job_i都不受影響。說(shuō)白了僅僅影響分流的很少部分請(qǐng)求。
- 引入虛擬節(jié)點(diǎn)
Hash算法不均勻必然會(huì)導(dǎo)致映射到請(qǐng)求環(huán)上不均勻，部分后端節(jié)點(diǎn)會(huì)承受比較多的請(qǐng)求，如果突然發(fā)生宕機(jī)的話(huà)，會(huì)把宕機(jī)節(jié)點(diǎn)的全部請(qǐng)求轉(zhuǎn)移到下一個(gè)節(jié)點(diǎn)，會(huì)導(dǎo)致下一個(gè)節(jié)點(diǎn)請(qǐng)求量暴增，也可能會(huì)宕機(jī)，也可能出現(xiàn)類(lèi)似的雪崩效應(yīng)。
為了保證均勻性，將給每個(gè)物理節(jié)點(diǎn)虛擬出一定數(shù)量的虛擬節(jié)點(diǎn)，分散到哈希環(huán)上，需要盡可能地隨機(jī)分散開(kāi)。虛擬節(jié)點(diǎn)承載的請(qǐng)求實(shí)際是指向真實(shí)的物理節(jié)點(diǎn)。出現(xiàn)物理機(jī)節(jié)點(diǎn)宕機(jī)時(shí)，虛擬節(jié)點(diǎn)上的請(qǐng)求按照規(guī)則轉(zhuǎn)移至下一個(gè)節(jié)點(diǎn)，避免雪崩效應(yīng)。
當(dāng)物理節(jié)點(diǎn)較少時(shí)，虛擬節(jié)點(diǎn)數(shù)需要更高來(lái)確保更好的一致性表現(xiàn)。
