一、常見的調度算法

QoS（Quality of Service）即服務質量，是一種調度控制機制，是網(wǎng)絡設計和運維的重要技術。在帶寬資源有限情況下，針對不同用戶 / 業(yè)務采用不同的調度策略，為任務提供端到端的服務質量保證。

QoS 本身并不會拓展帶寬，提升網(wǎng)絡吞吐量，相反設計不合理的調度反而有可能降低整體吞吐量。QoS 的一個關鍵點是允許不平等的網(wǎng)絡調度，降低時延要求低、性能和抖動不敏感的業(yè)務調度優(yōu)先級，優(yōu)先調度時延要求高、帶寬要求一般不高的業(yè)務。

調度器是實現(xiàn) QoS 的關鍵，調度器根據(jù)優(yōu)先級和帶寬配比進行業(yè)務調度。調度器的輸入是要提供服務的數(shù)據(jù)包隊列，輸出是完成調度輸出的一個個數(shù)據(jù)包。調度算法是調度器的核心，設計調度算法要充分考慮業(yè)務場景和用戶需求，沒有萬能的調度算法，只有合適的調度算法。常見的調度算法有很多，這里我們只簡單介紹 GaussDB 網(wǎng)絡調度涉及的調度算法：

1.FIFO 調度

FIFO (First In Forst Out) 調度使用的是 FCFS 策略，是一種不考慮 QoS 的調度算法。FIFO 調度不進行報文分類，所有業(yè)務共用一個隊列，按照請求進入隊列順序進行調度。如下圖所示，三種不同業(yè)務的請求全部加入到一個隊列中，按照 FIFO 的規(guī)則進行調度。



FIFO 調度實現(xiàn)簡單、開銷小，但是 FIFO 不區(qū)分請求類型、不考慮 QoS，對時延、抖動敏感的業(yè)務不友好，無法保證關鍵業(yè)務服務質量。

2.SP 調度

SP (Strict Priority) 嚴格優(yōu)先級調度嚴格按照隊列優(yōu)先級進行調度，只有在高優(yōu)先級隊列中請求全部調度完成的情況下，才會考慮調度低優(yōu)先級隊列中的請求。如下圖所示，三種不同業(yè)務分別對應三種不同優(yōu)先級的隊列：高優(yōu)隊列、中優(yōu)隊列和低優(yōu)隊列。不同業(yè)務的請求分別加入到相應優(yōu)先級隊列中，調度時優(yōu)先調度高優(yōu)隊列請求，高優(yōu)隊列中請求調度完成后，依次調度中優(yōu)和低優(yōu)隊列請求。



SP 調度算法的實現(xiàn)比較簡單，優(yōu)點是可以保證關鍵業(yè)務可以優(yōu)先調度到，可以最大限度的降低網(wǎng)絡延遲和抖動；缺點是網(wǎng)絡擁塞，高優(yōu)先級隊列中一直有請求時，會導致低優(yōu)先級隊列中請求一直調度不到，出現(xiàn) “餓死” 的情況。

3.RR 調度

RR (Round Robin) 輪詢調度通常采用分時機制，為每個隊列分配一個時間片或調度時刻。RR 調度按照固定順序循環(huán)調度每一個隊列中的請求，每次調度相同數(shù)量（一般是 1 個）的請求，且在調度過程中不考慮任何優(yōu)先級。算法較為簡單且容易實現(xiàn)，同時不會產生 “餓死” 問題。如下圖所示，RR 調度輪詢調度隊列 1/2/3 中的請求，每次調度一個隊列中的一個請求，直到請求調度完成。



RR 調度假設所有隊列的優(yōu)先級和帶寬需求都是相同的，調度時不考慮包長、隊列時延和帶寬需求。隊列包長差異比較大時，可能導致不同隊列實際占用帶寬差異巨大，同時因為不考慮時延和帶寬需求，導致無法做到對網(wǎng)絡流量的精準隔離和調度。

4.WRR 調度

輪詢調度保證了各隊列在請求調度時的公平性，但是無法滿足個性化的調度需求。WRR (Weighted Round Robin) 加權輪詢調度在輪詢的基礎上為隊列增加權重，每個隊列設置一個計數(shù)器，根據(jù)權重初始化計數(shù)器初始值，每調度一個報文，計數(shù)器減 1。權重越大，每次輪詢調度次數(shù)越多，能調度的包數(shù)量也就越多。如下圖所示，三個隊列權重分別是 31，每一輪調度的包數(shù)量比例就是 31。



當所有隊列權重值都是 1 時，WRR 調度退化為 RR 調度。WRR 的優(yōu)點是可以按比例調度各個隊列的請求，適應性更強，但是由于調度時沒有考慮包長，還是按照請求個數(shù)進行調度，在請求長度變化時無法保證各隊列按照設置比例占用帶寬，而用戶一般關心和感知到的是帶寬。此外隊列請求長度不一致時，WRR 調度對請求長度較小的隊列帶來不公平性。

5.DWRR 調度

為了解決隊列請求長度不一致帶來的不公平性，DWRR (Deficit Weighted Round Robin) 差分加權輪詢調度在 WRR 基礎上，基于請求長度而非請求個數(shù)設置權值，按照權重和請求長度進行調度。DWRR 為每個隊列設置一個計數(shù)器，計數(shù)器初始化為 weight * MTU，每次調度計數(shù)器減去請求長度。具體算法邏輯如下：

初始化隊列計數(shù)器 DC = weight * MTU；

調度器輪詢非空隊列，如果隊列 DC <= 0，則跳過輪詢下一個隊列；

調度隊列請求，計數(shù)器 DC = DC - request_len；

所有隊列 DC < 0 或無請求調度時，DC = DC + weight * MTU。

DWRR 調度克服了請求長度變化帶來的不公平性，提供了更為精準的帶寬分配。但是隊列數(shù)量較大或者 MTU 設置較大時，調度器完成一輪調度的時間可能比較長，這樣可能會引發(fā)較大的傳輸時延抖動，此外 DWRR 調度無法滿足高優(yōu)隊列優(yōu)先調度的需求。

6. SP+DWRR 調度

SP 調度可能出現(xiàn) “餓死” 問題，同時不能實現(xiàn)帶寬按比例調度；而 DWRR 調度可以實現(xiàn)帶寬的按比例調度，同時解決了 “餓死” 問題，但是無法滿足高優(yōu)業(yè)務優(yōu)先調度的需求。因此結合 SP 調度和 DWRR 調度的優(yōu)點，實現(xiàn) SP+DWRR 的調度。調度時優(yōu)先保證 SP 調度，在高優(yōu)隊列無請求調度時，才嘗試調度低優(yōu)隊列請求。如下圖所示，SP 調度高優(yōu)隊列、低優(yōu)隊列和普通隊列，隊列優(yōu)先級為：高優(yōu)隊列 > 普通隊列 > 低優(yōu)隊列。



隊列 1/2/3 按照配置權重值進行 DWRR 調度，高優(yōu)隊列、低優(yōu)隊列和普通隊列間按照 SP 算法進行調度。高優(yōu)隊列無請求調度時，嘗試調用普通隊列組內的請求，在普通隊列組內所有隊列均無請求時，才調度低優(yōu)隊列請求。

二、 GaussDB 網(wǎng)絡調度

1. 網(wǎng)絡調度實現(xiàn)

GaussDB 目前采用的 FIFO 調度機制，該調度機制無法滿足用戶的網(wǎng)絡隔離需求和 QoS 需求，同時 FIFO 調度可能帶來比較嚴重的抖動。抖動來自兩方面：一方面是不同業(yè)務爭取同一隊列引發(fā)的入列時延損耗，另一方面是隊列內請求數(shù)量變化帶來的調度時延變化。因此為了滿足用戶個性化的網(wǎng)絡隔離需求和 QoS 需求，設計實現(xiàn) GaussDB 網(wǎng)絡調度。 GaussDB 的網(wǎng)絡調度有三層需求：

不同資源池間的網(wǎng)絡隔離和帶寬配比需求；

高優(yōu)業(yè)務的優(yōu)先調度需求；

網(wǎng)絡欠佳 SQL 的降級需求。

考慮到以上需求，我們采用 SP+DWRR 調度算法設計實現(xiàn) GaussDB 的網(wǎng)絡調度，同時考慮到隊列數(shù)量變化及 MTU 設置帶來的時延影響，對 DWRR 調度進行改進，每次獲取最優(yōu)隊列進行調度（性能損耗較大，但是可以優(yōu)化改進）。 設計實現(xiàn)三種優(yōu)先級隊列：高優(yōu)隊列、普通隊列和低優(yōu)隊列。三種隊列優(yōu)先級順序為：高優(yōu)隊列 > 普通隊列 > 低優(yōu)隊列。三類隊列調度的業(yè)務類型如下：

高優(yōu)隊列用于調度超戶和不需管控查詢的網(wǎng)絡請求；

普通隊列用于調度正常需要管控的查詢的網(wǎng)絡請求，普通隊列間按照 DWRR 算法進行請求調度；

低優(yōu)隊列用于調度降級查詢的網(wǎng)絡請求。

GaussDB 基于 DWRR 實現(xiàn)的網(wǎng)絡隔離屬于配額共享的資源隔離，區(qū)別于限流的網(wǎng)絡隔離，該隔離方案在保障資源池間網(wǎng)絡隔離和帶寬占比的前提下，可以最大化地利用網(wǎng)絡帶寬，有效降低網(wǎng)絡隔離對網(wǎng)絡吞吐量的影響。GaussDB 配額共享的網(wǎng)絡隔離有兩層含義：

共享：所有資源池間網(wǎng)絡資源共享，網(wǎng)絡空閑時，按需調度；

配額：網(wǎng)絡調度繁忙情況下，按照配置權重比例進行調度。

基于 SP 調度機制實現(xiàn)的網(wǎng)絡降級有以下優(yōu)點：

超戶業(yè)務或正常業(yè)務有網(wǎng)絡請求時，優(yōu)先調度超戶和正常業(yè)務的網(wǎng)絡請求，保障超戶和正常業(yè)務的 QoS；

網(wǎng)絡空閑，超戶和正常業(yè)務調度無請求調度時，降級查詢可以按需占用空閑時間進行網(wǎng)絡調度。

SP 調度可能出現(xiàn) “餓死” 情況，因此一般情況下，用戶在設計網(wǎng)絡隔離方案時，不建議有資源池不設置網(wǎng)絡管控參數(shù)（帶寬權重）。此外網(wǎng)絡欠佳 SQL 降級后如果出現(xiàn) “餓死” 情況，一般說明網(wǎng)絡帶寬資源緊張，需要進行錯峰調度或配置并發(fā)管控。

2. 網(wǎng)絡隔離應用

考慮一個比較簡單的客戶場景：用戶自定義兩個資源池 rp1 和 rp2，兩個資源池帶寬權重分別配置為 4 和 2，同時配置默認資源池帶寬權重值為 1。

ALTER RESOURCE POOL rp1 WITH(WEIGHT=4);

ALTER RESOURCE POOL rp2 WITH(WEIGHT=2);

ALTER RESOURCE POOL default_pool WITH(WEIGHT=1);

配置完成后，在三個隊列都有請求的情況下，rp1、rp2 和 default_pool 會按照 41 的比例進行網(wǎng)絡請求調度。網(wǎng)絡擁塞，三個隊列都有調度不完的請求情況下，rp1 占用 4/7 的帶寬，rp2 占用 2/7 的帶寬，default_pool 占用 1/7 的帶寬。在有隊列無請求情況下，其他有請求的隊列按照權重配比搶占網(wǎng)絡帶寬。

設置查詢運行超過 20min，且網(wǎng)絡帶寬占用超過 512MB 時降級：

CREATE EXCEPT RULE bandwidth_rule1 WITH(bandwidth=512, ELAPSEDTIME=1200, action='penalty');

設置查詢運行超過 30min，且網(wǎng)絡帶寬占用超過 1GB 時降級：

CREATE EXCEPT RULE bandwidth_rule2 WITH(bandwidth=1024, ELAPSEDTIME=1800, action='abort');

資源池關聯(lián)異常規(guī)則：

ALTER RESOURCE POOL rp1 WITH(EXCEPT_RULE='bandwidth_rule1, bandwidth_rule2');

關聯(lián)資源池 rp1 的用戶執(zhí)行的查詢，如果運行時間超過 20min，且占用帶寬超過 512MB 時查詢即被降級，降級后該查詢網(wǎng)絡請求由低優(yōu)隊列調度，為了防止報文錯亂，降級不可恢復；如果運行時間超過 30min，且占用帶寬超過 1GB 時查詢即被查殺。

資源池監(jiān)控視圖集成了網(wǎng)絡收發(fā)速率監(jiān)控，可以通過查詢資源池監(jiān)控對各資源池網(wǎng)絡收發(fā)流量進行監(jiān)控：

查詢當前 CN/DN 上網(wǎng)絡收發(fā)速率：

SELECT rpname,send_speed,recv_speed FROM gs_respool_resource_info;

查詢所有 CN/DN 上網(wǎng)絡收發(fā)速率：

SELECT nodename,rpname,send_speed,recv_speed FROM pgxc_respool_resource_info order by 1,2;

通過資源池網(wǎng)絡監(jiān)控視圖可以直觀地觀察到資源池網(wǎng)絡隔離效果，同時對資源池帶寬權重配置優(yōu)化配置進行指導。

審核編輯：劉清