本文觀點部分來自：http://blog.csdn.net/pi9nc/article/details/9883705
簡言：
? ? ? ?隨著數據時代的來臨，為應對大數據，高并發(fā)的數據訪問量。系統(tǒng)架構師利用各種方法來保證系統(tǒng)組成運行，如建立緩存服務器器， 合理的利用各種調度算法?，F在我們來介紹常見的調度算法。
調度算法：調度算法是指：根據系統(tǒng)的資源分配策略所規(guī)定的資源分配算法，如任務A在執(zhí)行完后，選擇哪個任務來執(zhí)行，使得某個因素（如進程總執(zhí)行時間，或者磁盤尋道時間等）最小。對于不同的系統(tǒng)目標，通常采用不同的調度算法。本文將從多個角度來闡述調度算法
調度方法：動態(tài)靜態(tài)算法
靜態(tài)調度算法：
靜態(tài)算法：調度策略已經確定，不考慮系統(tǒng)運行的狀態(tài)。對系統(tǒng)cpu利用率比較高。
1..輪叫調度：以輪詢的調度方式來請求不同的服務器。優(yōu)點是簡單，無需記錄鏈接狀態(tài)，它適用于假設服務器的處理性能相同，不管服務器的當前的鏈接數和響應時間。改算法不使用與服務器處理性能不一的情況，當請求服務時長差異較大是，會導致服務器負載不均衡
2.加權輪叫：它解決了服務器性能不一的情況，用相應的權值來代表服務器的性能好壞。該算法將服務器高低和輪詢方式分配到請求服務器。權值高的優(yōu)先分配鏈接請求，并能處理更多的連接。但如果連接請求處理服務時間變化較大時，單獨的加權輪詢算法依然會對導致服務器負載不平衡。
3.目標地址散列調度:改算法是根據請求目標地址的ip地址，作為散列的靜態(tài)分配的散列表找出對應的服務器。若服務器可用未超載，將請求發(fā)往服務器，否則返回為空。
4.源地址散列調度：:改算法是根據源ip地址，作為散列鍵從靜態(tài)分配的散列表找出對應的服務器。若服務器可用未超載，將請求發(fā)往服務器，否則返回為空。
動態(tài)算法
動態(tài)算法指負載平衡系統(tǒng)利用系統(tǒng)的信息，做出負載調度決策。其適用單用戶/多用戶共享集群環(huán)境，運行時對系統(tǒng)資源實施監(jiān)控，并以此來作為掉度依據。不過缺點是及其消耗系統(tǒng)資源。
1.隊列調度
1 .1先來先服務（隊列調度）
先來先服務(FCFS)調度算法是一種最簡單的調度算法，該算法既可用于作業(yè)調度，也可用于進程調度。當在作業(yè)調度中采用該算法時，每次調度都是從后備作業(yè)隊列中選擇一個或多個最先進入該隊列的作業(yè)，將它們調入內存，為它們分配資源、創(chuàng)建進程，然后放入就緒隊列。在進程調度中采用FCFS算法時，則每次調度是從就緒隊列中選擇一個最先進入該隊列的進程，為之分配處理機，使之投入運行。該進程一直運行到完成或發(fā)生某事件而阻塞后才放棄處理機。
缺點：比較有利于長作業(yè)，而不利于短作業(yè)。 有利于CPU繁忙的作業(yè)，而不利于I/O繁忙的作業(yè)。
1.2最短優(yōu)先（優(yōu)先隊列）
最短優(yōu)先調度算法是指對短作業(yè)或短進程優(yōu)先調度的算法。它們可以分別用于作業(yè)調度和進程調度。短作業(yè)優(yōu)先(SJF)的調度算法是從后備隊列中選擇一個或若干個估計運行時間最短的作業(yè)，將它們調入內存運行。而短進程優(yōu)先(SPF)調度算法則是從就緒隊列中選出一個估計運行時間最短的進程，將處理機分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機時再重新調度。
缺點：長作業(yè)的運行得不到保證。
為了照顧緊迫型作業(yè)，使之在進入系統(tǒng)后便獲得優(yōu)先處理，引入了最高優(yōu)先權優(yōu)先(FPF)調度算法。此算法常被用于批處理系統(tǒng)中，作為作業(yè)調度算法，也作為多種操作系統(tǒng)中的進程調度算法，還可用于實時系統(tǒng)中。當把該算法用于作業(yè)調度時，系統(tǒng)將從后備隊列中選擇若干個優(yōu)先權最高的作業(yè)裝入內存。當用于進程調度時，該算法是把處理機分配給就緒隊列中優(yōu)先權最高的進程，這時，又可進一步把該算法分成如下兩種。
1) 非搶占式優(yōu)先權算法
在這種方式下，系統(tǒng)一旦把處理機分配給就緒隊列中優(yōu)先權最高的進程后，該進程便一直執(zhí)行下去，直至完成；或因發(fā)生某事件使該進程放棄處理機時，系統(tǒng)方可再將處理機重新分配給另一優(yōu)先權最高的進程。這種調度算法主要用于批處理系統(tǒng)中；也可用于某些對實時性要求不嚴的實時系統(tǒng)中。
2) 搶占式優(yōu)先權調度算法
在這種方式下，系統(tǒng)同樣是把處理機分配給優(yōu)先權最高的進程，使之執(zhí)行。但在其執(zhí)行期間，只要又出現了另一個其優(yōu)先權更高的進程，進程調度程序就立即停止當前進程(原優(yōu)先權最高的進程)的執(zhí)行，重新將處理機分配給新到的優(yōu)先權最高的進程。因此，在采用這種調度算法時，是每當系統(tǒng)中出現一個新的就緒進程i 時，就將其優(yōu)先權Pi與正在執(zhí)行的進程j 的優(yōu)先權Pj進行比較。如果Pi≤Pj，原進程Pj便繼續(xù)執(zhí)行；但如果是Pi>Pj，則立即停止Pj的執(zhí)行，做進程切換，使i 進程投入執(zhí)行。顯然，這種搶占式的優(yōu)先權調度算法能更好地滿足緊迫作業(yè)的要求，故而常用于要求比較嚴格的實時系統(tǒng)中，以及對性能要求較高的批處理和分時系統(tǒng)中。
在批處理系統(tǒng)中，短作業(yè)優(yōu)先算法是一種比較好的算法，其主要的不足之處是長作業(yè)的運行得不到保證。如果我們能為每個作業(yè)引入前面所述的動態(tài)優(yōu)先權，并使作業(yè)的優(yōu)先級隨著等待時間的增加而以速率a 提高，則長作業(yè)在等待一定的時間后，必然有機會分配到處理機。該優(yōu)先權的變化規(guī)律可描述為：
由于等待時間與服務時間之和就是系統(tǒng)對該作業(yè)的響應時間，故該優(yōu)先權又相當于響應比RP。據此，又可表示為：
由上式可以看出：
(1) 如果作業(yè)的等待時間相同，則要求服務的時間愈短，其優(yōu)先權愈高，因而該算法有利于短作業(yè)。
(2) 當要求服務的時間相同時，作業(yè)的優(yōu)先權決定于其等待時間，等待時間愈長，其優(yōu)先權愈高，因而它實現的是先來先服務。
(3) 對于長作業(yè)，作業(yè)的優(yōu)先級可以隨等待時間的增加而提高，當其等待時間足夠長時，其優(yōu)先級便可升到很高，從而也可獲得處理機。
簡言之，該算法考慮到了系統(tǒng)的任務的差異性，有考慮到系統(tǒng)服務器的硬件差異性。因此，該算法實現了一種較好的折衷。當然，在利用該算法時，每要進行調度之前，都須先做響應比的計算，這會增加系統(tǒng)開銷。
調度系統(tǒng)
LVS：
1.靜態(tài)方法：
（1）、輪詢:輪詢調度是一種注重調度過程的調度算法。只在乎訪問是否調度到后端服務器，不過后端服務器的性能是否能處理的過來。
（2）、加權：又叫加權輪詢，是一種注重結果的調度算法。它會考慮后端服務器的的性能，
根據性能，管理者可以對服務器所的權重來合理的進行調度，
（3）、SH：Source Hashing，實現session sticky，源IP地址hash；將來自于同一個IP地址的請求始終發(fā)往第一次挑中的RS，從而實現會話綁定
（4）、DH：Destination Hashing；目標地址哈希，將發(fā)往同一個目標地址的請求始終轉發(fā)至第一次挑中的RS，典型使用場景是正向代理緩存場景中的負載均衡，如：寬帶運營商
動態(tài)方法：主要根據每RS當前的負載狀態(tài)及調度算法進行調度Overhead=value較小的RS將被調度
（1）、LC：least connections 適用于長連接應用
Overhead=activeconns*256+inactiveconns
（2）、WLC：Weighted LC，默認調度方法
Overhead=(activeconns*256+inactiveconns)/weight
（3）、SED：Shortest Expection Delay,初始連接高權重優(yōu)先
Overhead=(activeconns+1)*256/weight
（4）、NQ：Never Queue，第一輪均勻分配，后續(xù)SED
（5）、LBLC：Locality-Based LC，動態(tài)的DH算法，使用場景：根據負載狀態(tài)實現正向代理
（6）、LBLCR：LBLC with Replication，帶復制功能的LBLC
解決LBLC負載不均衡問題，從負載重的復制到負載輕的RS
Nginx
ip_hash源地址hash調度方法
(1)、least_conn最少連接調度算法，當server擁有不同的權重時其為wlc，當所有后端主機連接數相同時，則使用wrr，適用于長連接
(2)、hash key [consistent]基于指定的key的hash表來實現對請求的調度，此處的key可以直接文本、變量或二者組合
作用：將請求分類，同一類請求將發(fā)往同一個upstream server，使用consistent參數，將使用ketama一致性hash算法，適用于后端是Cache服務器（如varnish）時使用
hash $request_uriconsistent;
hash $remote_addr;
haproxy:
roundrobin：基于權重輪詢，動態(tài)算法，支持權重的運行時調整，支持慢啟動；每個后端backend中最多支持4095個server
server options：weight #
?static-rr：基于權重輪詢，靜態(tài)算法，不支持權重的運行時調整及慢啟動；后端主機數量無上限
?leastconn：加權最少連接，動態(tài)算法，最少連接的后端服務器優(yōu)先分配接收新連接，相同連接時輪詢，推薦在較長會話的場景使用，例如MySQL、LDAP等，不適合http
?first：根據服務器在列表中的位置，自上而下進行調度；前面服務器的連接數達到上限，新請求才會分配給下一臺服務
?source：源地址hash，新連接先按權重分配，后續(xù)連接按source分配請求
uri：對URI的左半部分或整個uri做hash計算，并除以服務器總權重取模，以后派發(fā)至某挑出的服務器,適用于后端緩存服務器://:@:/;?#左半部分：/;整個uri：/;?#?url_param：對用戶請求的uri聽部分中的參數的值作hash計算，并由服務器總權重相除以后派發(fā)至某挑出的服務器；通常用于追蹤用戶，以確保來自同一個用戶的請求始終發(fā)往同一個Backend Server
hdr()：對于每個http請求，此處由指定的http首部將會被取出做hash計算；并由服務器總權重相除以后派發(fā)至某挑出的服務器；無有效值的會被輪詢調度
hdr(Cookie)
