本文觀(guān)點(diǎn)部分來(lái)自：http://blog.csdn.net/pi9nc/article/details/9883705

簡(jiǎn)言：

? ? ? ?隨著數(shù)據(jù)時(shí)代的來(lái)臨，為應(yīng)對(duì)大數(shù)據(jù)，高并發(fā)的數(shù)據(jù)訪(fǎng)問(wèn)量。系統(tǒng)架構(gòu)師利用各種方法來(lái)保證系統(tǒng)組成運(yùn)行，如建立緩存服務(wù)器器， 合理的利用各種調(diào)度算法。現(xiàn)在我們來(lái)介紹常見(jiàn)的調(diào)度算法。

調(diào)度算法：調(diào)度算法是指：根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法，如任務(wù)A在執(zhí)行完后，選擇哪個(gè)任務(wù)來(lái)執(zhí)行，使得某個(gè)因素（如進(jìn)程總執(zhí)行時(shí)間，或者磁盤(pán)尋道時(shí)間等）最小。對(duì)于不同的系統(tǒng)目標(biāo)，通常采用不同的調(diào)度算法。本文將從多個(gè)角度來(lái)闡述調(diào)度算法

調(diào)度方法：動(dòng)態(tài)靜態(tài)算法

靜態(tài)調(diào)度算法：

靜態(tài)算法：調(diào)度策略已經(jīng)確定，不考慮系統(tǒng)運(yùn)行的狀態(tài)。對(duì)系統(tǒng)cpu利用率比較高。

1..輪叫調(diào)度：以輪詢(xún)的調(diào)度方式來(lái)請(qǐng)求不同的服務(wù)器。優(yōu)點(diǎn)是簡(jiǎn)單，無(wú)需記錄鏈接狀態(tài)，它適用于假設(shè)服務(wù)器的處理性能相同，不管服務(wù)器的當(dāng)前的鏈接數(shù)和響應(yīng)時(shí)間。改算法不使用與服務(wù)器處理性能不一的情況，當(dāng)請(qǐng)求服務(wù)時(shí)長(zhǎng)差異較大是，會(huì)導(dǎo)致服務(wù)器負(fù)載不均衡

2.加權(quán)輪叫：它解決了服務(wù)器性能不一的情況，用相應(yīng)的權(quán)值來(lái)代表服務(wù)器的性能好壞。該算法將服務(wù)器高低和輪詢(xún)方式分配到請(qǐng)求服務(wù)器。權(quán)值高的優(yōu)先分配鏈接請(qǐng)求，并能處理更多的連接。但如果連接請(qǐng)求處理服務(wù)時(shí)間變化較大時(shí)，單獨(dú)的加權(quán)輪詢(xún)算法依然會(huì)對(duì)導(dǎo)致服務(wù)器負(fù)載不平衡。

3.目標(biāo)地址散列調(diào)度:改算法是根據(jù)請(qǐng)求目標(biāo)地址的ip地址，作為散列的靜態(tài)分配的散列表找出對(duì)應(yīng)的服務(wù)器。若服務(wù)器可用未超載，將請(qǐng)求發(fā)往服務(wù)器，否則返回為空。

4.源地址散列調(diào)度：:改算法是根據(jù)源ip地址，作為散列鍵從靜態(tài)分配的散列表找出對(duì)應(yīng)的服務(wù)器。若服務(wù)器可用未超載，將請(qǐng)求發(fā)往服務(wù)器，否則返回為空。

動(dòng)態(tài)算法

動(dòng)態(tài)算法指負(fù)載平衡系統(tǒng)利用系統(tǒng)的信息，做出負(fù)載調(diào)度決策。其適用單用戶(hù)/多用戶(hù)共享集群環(huán)境，運(yùn)行時(shí)對(duì)系統(tǒng)資源實(shí)施監(jiān)控，并以此來(lái)作為掉度依據(jù)。不過(guò)缺點(diǎn)是及其消耗系統(tǒng)資源。

1.隊(duì)列調(diào)度

1 .1先來(lái)先服務(wù)（隊(duì)列調(diào)度）

先來(lái)先服務(wù)(FCFS)調(diào)度算法是一種最簡(jiǎn)單的調(diào)度算法，該算法既可用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度。當(dāng)在作業(yè)調(diào)度中采用該算法時(shí)，每次調(diào)度都是從后備作業(yè)隊(duì)列中選擇一個(gè)或多個(gè)最先進(jìn)入該隊(duì)列的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進(jìn)程，然后放入就緒隊(duì)列。在進(jìn)程調(diào)度中采用FCFS算法時(shí)，則每次調(diào)度是從就緒隊(duì)列中選擇一個(gè)最先進(jìn)入該隊(duì)列的進(jìn)程，為之分配處理機(jī)，使之投入運(yùn)行。該進(jìn)程一直運(yùn)行到完成或發(fā)生某事件而阻塞后才放棄處理機(jī)。

缺點(diǎn)：比較有利于長(zhǎng)作業(yè)，而不利于短作業(yè)。 有利于CPU繁忙的作業(yè)，而不利于I/O繁忙的作業(yè)。

1.2最短優(yōu)先（優(yōu)先隊(duì)列）

最短優(yōu)先調(diào)度算法是指對(duì)短作業(yè)或短進(jìn)程優(yōu)先調(diào)度的算法。它們可以分別用于作業(yè)調(diào)度和進(jìn)程調(diào)度。短作業(yè)優(yōu)先(SJF)的調(diào)度算法是從后備隊(duì)列中選擇一個(gè)或若干個(gè)估計(jì)運(yùn)行時(shí)間最短的作業(yè)，將它們調(diào)入內(nèi)存運(yùn)行。而短進(jìn)程優(yōu)先(SPF)調(diào)度算法則是從就緒隊(duì)列中選出一個(gè)估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，將處理機(jī)分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機(jī)時(shí)再重新調(diào)度。

缺點(diǎn)：長(zhǎng)作業(yè)的運(yùn)行得不到保證。

2 高優(yōu)先權(quán)優(yōu)先調(diào)度算法

2.1 優(yōu)先權(quán)調(diào)度算法的類(lèi)型

為了照顧緊迫型作業(yè)，使之在進(jìn)入系統(tǒng)后便獲得優(yōu)先處理，引入了最高優(yōu)先權(quán)優(yōu)先(FPF)調(diào)度算法。此算法常被用于批處理系統(tǒng)中，作為作業(yè)調(diào)度算法，也作為多種操作系統(tǒng)中的進(jìn)程調(diào)度算法，還可用于實(shí)時(shí)系統(tǒng)中。當(dāng)把該算法用于作業(yè)調(diào)度時(shí)，系統(tǒng)將從后備隊(duì)列中選擇若干個(gè)優(yōu)先權(quán)最高的作業(yè)裝入內(nèi)存。當(dāng)用于進(jìn)程調(diào)度時(shí)，該算法是把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程，這時(shí)，又可進(jìn)一步把該算法分成如下兩種。

1) 非搶占式優(yōu)先權(quán)算法

在這種方式下，系統(tǒng)一旦把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程后，該進(jìn)程便一直執(zhí)行下去，直至完成；或因發(fā)生某事件使該進(jìn)程放棄處理機(jī)時(shí)，系統(tǒng)方可再將處理機(jī)重新分配給另一優(yōu)先權(quán)最高的進(jìn)程。這種調(diào)度算法主要用于批處理系統(tǒng)中；也可用于某些對(duì)實(shí)時(shí)性要求不嚴(yán)的實(shí)時(shí)系統(tǒng)中。

2) 搶占式優(yōu)先權(quán)調(diào)度算法

在這種方式下，系統(tǒng)同樣是把處理機(jī)分配給優(yōu)先權(quán)最高的進(jìn)程，使之執(zhí)行。但在其執(zhí)行期間，只要又出現(xiàn)了另一個(gè)其優(yōu)先權(quán)更高的進(jìn)程，進(jìn)程調(diào)度程序就立即停止當(dāng)前進(jìn)程(原優(yōu)先權(quán)最高的進(jìn)程)的執(zhí)行，重新將處理機(jī)分配給新到的優(yōu)先權(quán)最高的進(jìn)程。因此，在采用這種調(diào)度算法時(shí)，是每當(dāng)系統(tǒng)中出現(xiàn)一個(gè)新的就緒進(jìn)程i 時(shí)，就將其優(yōu)先權(quán)Pi與正在執(zhí)行的進(jìn)程j 的優(yōu)先權(quán)Pj進(jìn)行比較。如果Pi≤Pj，原進(jìn)程Pj便繼續(xù)執(zhí)行；但如果是Pi>Pj，則立即停止Pj的執(zhí)行，做進(jìn)程切換，使i 進(jìn)程投入執(zhí)行。顯然，這種搶占式的優(yōu)先權(quán)調(diào)度算法能更好地滿(mǎn)足緊迫作業(yè)的要求，故而常用于要求比較嚴(yán)格的實(shí)時(shí)系統(tǒng)中，以及對(duì)性能要求較高的批處理和分時(shí)系統(tǒng)中。

2.2 高響應(yīng)比優(yōu)先調(diào)度算法

在批處理系統(tǒng)中，短作業(yè)優(yōu)先算法是一種比較好的算法，其主要的不足之處是長(zhǎng)作業(yè)的運(yùn)行得不到保證。如果我們能為每個(gè)作業(yè)引入前面所述的動(dòng)態(tài)優(yōu)先權(quán)，并使作業(yè)的優(yōu)先級(jí)隨著等待時(shí)間的增加而以速率a 提高，則長(zhǎng)作業(yè)在等待一定的時(shí)間后，必然有機(jī)會(huì)分配到處理機(jī)。該優(yōu)先權(quán)的變化規(guī)律可描述為：

由于等待時(shí)間與服務(wù)時(shí)間之和就是系統(tǒng)對(duì)該作業(yè)的響應(yīng)時(shí)間，故該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比RP。據(jù)此，又可表示為：

由上式可以看出：

(1) 如果作業(yè)的等待時(shí)間相同，則要求服務(wù)的時(shí)間愈短，其優(yōu)先權(quán)愈高，因而該算法有利于短作業(yè)。

(2) 當(dāng)要求服務(wù)的時(shí)間相同時(shí)，作業(yè)的優(yōu)先權(quán)決定于其等待時(shí)間，等待時(shí)間愈長(zhǎng)，其優(yōu)先權(quán)愈高，因而它實(shí)現(xiàn)的是先來(lái)先服務(wù)。

(3) 對(duì)于長(zhǎng)作業(yè)，作業(yè)的優(yōu)先級(jí)可以隨等待時(shí)間的增加而提高，當(dāng)其等待時(shí)間足夠長(zhǎng)時(shí)，其優(yōu)先級(jí)便可升到很高，從而也可獲得處理機(jī)。

簡(jiǎn)言之，該算法考慮到了系統(tǒng)的任務(wù)的差異性，有考慮到系統(tǒng)服務(wù)器的硬件差異性。因此，該算法實(shí)現(xiàn)了一種較好的折衷。當(dāng)然，在利用該算法時(shí)，每要進(jìn)行調(diào)度之前，都須先做響應(yīng)比的計(jì)算，這會(huì)增加系統(tǒng)開(kāi)銷(xiāo)。

調(diào)度系統(tǒng)

LVS：

1.靜態(tài)方法：

（1）、輪詢(xún):輪詢(xún)調(diào)度是一種注重調(diào)度過(guò)程的調(diào)度算法。只在乎訪(fǎng)問(wèn)是否調(diào)度到后端服務(wù)器，不過(guò)后端服務(wù)器的性能是否能處理的過(guò)來(lái)。

（2）、加權(quán)：又叫加權(quán)輪詢(xún)，是一種注重結(jié)果的調(diào)度算法。它會(huì)考慮后端服務(wù)器的的性能，

根據(jù)性能，管理者可以對(duì)服務(wù)器所的權(quán)重來(lái)合理的進(jìn)行調(diào)度，

（3）、SH：Source Hashing，實(shí)現(xiàn)session sticky，源IP地址hash；將來(lái)自于同一個(gè)IP地址的請(qǐng)求始終發(fā)往第一次挑中的RS，從而實(shí)現(xiàn)會(huì)話(huà)綁定

（4）、DH：Destination Hashing；目標(biāo)地址哈希，將發(fā)往同一個(gè)目標(biāo)地址的請(qǐng)求始終轉(zhuǎn)發(fā)至第一次挑中的RS，典型使用場(chǎng)景是正向代理緩存場(chǎng)景中的負(fù)載均衡，如：寬帶運(yùn)營(yíng)商

動(dòng)態(tài)方法：主要根據(jù)每RS當(dāng)前的負(fù)載狀態(tài)及調(diào)度算法進(jìn)行調(diào)度Overhead=value較小的RS將被調(diào)度

（1）、LC：least connections 適用于長(zhǎng)連接應(yīng)用

Overhead=activeconns*256+inactiveconns

（2）、WLC：Weighted LC，默認(rèn)調(diào)度方法

Overhead=(activeconns*256+inactiveconns)/weight

（3）、SED：Shortest Expection Delay,初始連接高權(quán)重優(yōu)先

Overhead=(activeconns+1)*256/weight

（4）、NQ：Never Queue，第一輪均勻分配，后續(xù)SED

（5）、LBLC：Locality-Based LC，動(dòng)態(tài)的DH算法，使用場(chǎng)景：根據(jù)負(fù)載狀態(tài)實(shí)現(xiàn)正向代理

（6）、LBLCR：LBLC with Replication，帶復(fù)制功能的LBLC

解決LBLC負(fù)載不均衡問(wèn)題，從負(fù)載重的復(fù)制到負(fù)載輕的RS

Nginx

ip_hash源地址hash調(diào)度方法

(1)、least_conn最少連接調(diào)度算法，當(dāng)server擁有不同的權(quán)重時(shí)其為wlc，當(dāng)所有后端主機(jī)連接數(shù)相同時(shí)，則使用wrr，適用于長(zhǎng)連接

(2)、hash key [consistent]基于指定的key的hash表來(lái)實(shí)現(xiàn)對(duì)請(qǐng)求的調(diào)度，此處的key可以直接文本、變量或二者組合

作用：將請(qǐng)求分類(lèi)，同一類(lèi)請(qǐng)求將發(fā)往同一個(gè)upstream server，使用consistent參數(shù)，將使用ketama一致性hash算法，適用于后端是Cache服務(wù)器（如varnish）時(shí)使用

hash $request_uriconsistent;

hash $remote_addr;

haproxy:

roundrobin：基于權(quán)重輪詢(xún)，動(dòng)態(tài)算法，支持權(quán)重的運(yùn)行時(shí)調(diào)整，支持慢啟動(dòng)；每個(gè)后端backend中最多支持4095個(gè)server

server options：weight #

?static-rr：基于權(quán)重輪詢(xún)，靜態(tài)算法，不支持權(quán)重的運(yùn)行時(shí)調(diào)整及慢啟動(dòng)；后端主機(jī)數(shù)量無(wú)上限

?leastconn：加權(quán)最少連接，動(dòng)態(tài)算法，最少連接的后端服務(wù)器優(yōu)先分配接收新連接，相同連接時(shí)輪詢(xún)，推薦在較長(zhǎng)會(huì)話(huà)的場(chǎng)景使用，例如MySQL、LDAP等，不適合http

?first：根據(jù)服務(wù)器在列表中的位置，自上而下進(jìn)行調(diào)度；前面服務(wù)器的連接數(shù)達(dá)到上限，新請(qǐng)求才會(huì)分配給下一臺(tái)服務(wù)

?source：源地址hash，新連接先按權(quán)重分配，后續(xù)連接按source分配請(qǐng)求

uri：對(duì)URI的左半部分或整個(gè)uri做hash計(jì)算，并除以服務(wù)器總權(quán)重取模，以后派發(fā)至某挑出的服務(wù)器,適用于后端緩存服務(wù)器://:@:/;?#左半部分：/;整個(gè)uri：/;?#?url_param：對(duì)用戶(hù)請(qǐng)求的uri聽(tīng)部分中的參數(shù)的值作hash計(jì)算，并由服務(wù)器總權(quán)重相除以后派發(fā)至某挑出的服務(wù)器；通常用于追蹤用戶(hù)，以確保來(lái)自同一個(gè)用戶(hù)的請(qǐng)求始終發(fā)往同一個(gè)Backend Server

hdr()：對(duì)于每個(gè)http請(qǐng)求，此處由指定的http首部將會(huì)被取出做hash計(jì)算；并由服務(wù)器總權(quán)重相除以后派發(fā)至某挑出的服務(wù)器；無(wú)有效值的會(huì)被輪詢(xún)調(diào)度

hdr(Cookie)