公平隊(duì)列C/C++實(shí)現(xiàn)：從原理到二次開發(fā))
簡介這是一份面向網(wǎng)絡(luò)編程學(xué)習(xí)者與通信方向開發(fā)者的WFQ加權(quán)公平隊(duì)列算法C/C實(shí)現(xiàn)工程聚焦多路復(fù)用網(wǎng)絡(luò)中數(shù)據(jù)流公平共享帶寬這一核心問題涵蓋發(fā)送端、接收端與路由器轉(zhuǎn)發(fā)三部分代碼適合用于理解隊(duì)列調(diào)度、權(quán)重分配與服務(wù)質(zhì)量保障的完整鏈路。壓縮包共344個(gè)文件約14.98MB以cpp與c源碼為主體配合h頭文件、obj編譯產(chǎn)物、exe可執(zhí)行程序及dsp/dsw工程文件另有doc說明與txt配置便于直接編譯運(yùn)行與二次修改。目前已有958人學(xué)習(xí)下載。資源完整呈現(xiàn)了隊(duì)列結(jié)構(gòu)設(shè)計(jì)、數(shù)據(jù)包分類、權(quán)重調(diào)度與循環(huán)監(jiān)控等關(guān)鍵環(huán)節(jié)讀者可對照源碼梳理WFQ與FIFO的差異掌握C面向?qū)ο蠼ＥcC底層轉(zhuǎn)發(fā)實(shí)現(xiàn)的結(jié)合方式并借助工程文件快速搭建調(diào)試環(huán)境為網(wǎng)絡(luò)協(xié)議棧與流量管理相關(guān)課程設(shè)計(jì)或項(xiàng)目開發(fā)提供可復(fù)用的參考實(shí)現(xiàn)。1. 從一次隊(duì)列調(diào)度翻車說起WFQ 到底解決什么問題做過網(wǎng)絡(luò)轉(zhuǎn)發(fā)或者 QoS 限速的朋友大概率遇到過這種場景多個(gè)業(yè)務(wù)流共享一條出口鏈路結(jié)果某個(gè)大流量業(yè)務(wù)把帶寬全吃光了語音、信令這些小包業(yè)務(wù)被餓死延遲飆到幾百毫秒。你可能會想加個(gè)優(yōu)先級隊(duì)列不就完了但優(yōu)先級隊(duì)列的問題是低優(yōu)先級流會被徹底餓死公平性無從談起。WFQWeighted Fair Queueing加權(quán)公平隊(duì)列就是來解決這個(gè)矛盾的。它給每條流分配一個(gè)權(quán)重按權(quán)重比例分配帶寬同時(shí)保證每條流至少能拿到屬于自己的那一份。這份資源是一套 C/C 實(shí)現(xiàn)的 WFQ 算法代碼適合做網(wǎng)絡(luò)協(xié)議棧、QoS 調(diào)度模塊、或者嵌入式轉(zhuǎn)發(fā)設(shè)備的開發(fā)者拿來直接集成或二次開發(fā)。代碼結(jié)構(gòu)清晰核心調(diào)度邏輯和數(shù)據(jù)結(jié)構(gòu)分離新手能跑通熟手能直接改權(quán)重計(jì)算和虛擬時(shí)間推進(jìn)策略。2. 核心架構(gòu)拆解虛擬時(shí)間、權(quán)重與包調(diào)度怎么串起來2.1 WFQ 的兩個(gè)核心概念虛擬時(shí)間與權(quán)重WFQ 的本質(zhì)是模擬一個(gè)“理想公平隊(duì)列”——假設(shè)鏈路可以無限細(xì)分每條流按權(quán)重比例同時(shí)獲得服務(wù)。實(shí)際實(shí)現(xiàn)里用一個(gè)虛擬時(shí)間Virtual Time來近似這個(gè)理想模型。每條流維護(hù)一個(gè)虛擬開始時(shí)間start_time和虛擬完成時(shí)間finish_time調(diào)度器每次選finish_time最小的包發(fā)送。權(quán)重決定了流之間分配帶寬的比例。權(quán)重為 2 的流理論上拿到的帶寬是權(quán)重為 1 的流的兩倍。虛擬時(shí)間的推進(jìn)速度與鏈路速率和活躍流的總權(quán)重相關(guān)這是整個(gè)算法最容易被寫錯(cuò)的地方。代碼里通常用這樣的結(jié)構(gòu)體表示一個(gè)流// 流控制塊每條流一個(gè)實(shí)例 typedef struct wfq_flow { uint32_t flow_id; // 流標(biāo)識 uint32_t weight; // 權(quán)重決定帶寬分配比例 double virtual_time; // 該流當(dāng)前的虛擬時(shí)間 double start_time; // 當(dāng)前包的虛擬開始時(shí)間 double finish_time; // 當(dāng)前包的虛擬完成時(shí)間 struct pkt *head; // 流內(nèi)包隊(duì)列頭 struct pkt *tail; // 流內(nèi)包隊(duì)列尾 uint32_t pkt_count; // 當(dāng)前排隊(duì)包數(shù)量 } wfq_flow_t;這里weight是外部配置進(jìn)來的virtual_time是該流上一次調(diào)度后的虛擬時(shí)間戳。start_time和finish_time在每次新包入隊(duì)時(shí)計(jì)算計(jì)算方式直接決定了調(diào)度公平性。2.2 包入隊(duì)start_time 和 finish_time 的計(jì)算當(dāng)一個(gè)包到達(dá)時(shí)WFQ 需要計(jì)算它的虛擬開始時(shí)間和虛擬完成時(shí)間。標(biāo)準(zhǔn)做法是// 包入隊(duì)時(shí)計(jì)算虛擬時(shí)間戳 // pkt_len: 包長字節(jié)link_rate: 鏈路速率字節(jié)/秒 void wfq_enqueue(wfq_flow_t *flow, struct pkt *pkt, double link_rate) { double pkt_virtual_len (double)pkt-len / flow-weight; // 如果流內(nèi)沒有排隊(duì)包start_time 取當(dāng)前虛擬時(shí)間 if (flow-pkt_count 0) { flow-start_time flow-virtual_time; } else { // 否則取上一個(gè)包的 finish_time flow-start_time flow-finish_time; } // finish_time start_time 包長/權(quán)重 flow-finish_time flow-start_time pkt_virtual_len; // 包掛入流內(nèi)隊(duì)列 pkt-start_time flow-start_time; pkt-finish_time flow-finish_time; enqueue_pkt(flow, pkt); flow-pkt_count; }關(guān)鍵點(diǎn)在于pkt_virtual_len pkt_len / weight。權(quán)重越大虛擬包長越小finish_time增長越慢該流的包就越容易被優(yōu)先調(diào)度。這就是“加權(quán)”的體現(xiàn)。start_time的取值邏輯保證了同一條流內(nèi)部的包按到達(dá)順序服務(wù)不會出現(xiàn)后到的包插隊(duì)。2.3 調(diào)度出隊(duì)選 finish_time 最小的包調(diào)度器每次從所有非空流中選出finish_time最小的包發(fā)送。如果多條流的finish_time相同可以按流 ID 或輪詢方式打破平局。// 從所有活躍流中選出 finish_time 最小的包 struct pkt *wfq_dequeue(wfq_flow_t *flows, int flow_cnt, double link_rate) { int selected -1; double min_finish 1e18; for (int i 0; i flow_cnt; i) { if (flows[i].pkt_count 0) continue; struct pkt *head_pkt flows[i].head; if (head_pkt-finish_time min_finish) { min_finish head_pkt-finish_time; selected i; } } if (selected 0) return NULL; // 所有流為空 struct pkt *pkt dequeue_pkt(flows[selected]); flows[selected].pkt_count--; // 更新該流的虛擬時(shí)間 flows[selected].virtual_time pkt-finish_time; // 如果流內(nèi)還有包更新 start_time/finish_time 基準(zhǔn) if (flows[selected].pkt_count 0) { flows[selected].start_time flows[selected].virtual_time; flows[selected].finish_time flows[selected].start_time (double)flows[selected].head-len / flows[selected].weight; } return pkt; }這段代碼里virtual_time的更新很關(guān)鍵。它記錄的是該流最近一次被服務(wù)到的虛擬時(shí)間點(diǎn)后續(xù)入隊(duì)的包會以此為基準(zhǔn)計(jì)算start_time。如果忘了更新同一條流的包會一直用舊的虛擬時(shí)間導(dǎo)致調(diào)度順序錯(cuò)亂。2.4 虛擬時(shí)間的全局推進(jìn)上面只講了單流內(nèi)部的虛擬時(shí)間。實(shí)際上所有流共享一個(gè)全局虛擬時(shí)間global_vtime它隨著鏈路發(fā)送包而推進(jìn)。推進(jìn)速度與當(dāng)前活躍流的總權(quán)重有關(guān)// 每發(fā)送一個(gè)包后推進(jìn)全局虛擬時(shí)間 // pkt_len: 剛發(fā)送的包長active_weight: 當(dāng)前所有非空流的權(quán)重之和 void wfq_advance_vtime(double *global_vtime, uint32_t pkt_len, uint32_t active_weight, double link_rate) { if (active_weight 0) return; // 虛擬時(shí)間推進(jìn)量 實(shí)際發(fā)送時(shí)間 / 活躍總權(quán)重 double real_time (double)pkt_len / link_rate; *global_vtime real_time * active_weight; }這個(gè)公式的含義是鏈路每發(fā)送一個(gè)包全局虛擬時(shí)間前進(jìn)的量等于“實(shí)際耗時(shí) × 活躍總權(quán)重”?；钴S流越多虛擬時(shí)間走得越快新入隊(duì)的包start_time就越大避免新流插隊(duì)。這是 WFQ 保證公平性的核心機(jī)制。3. 編譯與運(yùn)行從源碼到可執(zhí)行 Demo 的完整步驟3.1 目錄結(jié)構(gòu)與文件說明拿到源碼后先看目錄結(jié)構(gòu)。典型的 WFQ 實(shí)現(xiàn)項(xiàng)目會包含以下文件wfq/ ├── include/ │ ├── wfq.h # 核心數(shù)據(jù)結(jié)構(gòu)與接口聲明 │ └── pkt.h # 包結(jié)構(gòu)定義 ├── src/ │ ├── wfq.c # WFQ 調(diào)度核心實(shí)現(xiàn) │ ├── pkt.c # 包隊(duì)列操作 │ └── main.c # 測試入口模擬多流調(diào)度 ├── Makefile └── README.mdwfq.h里定義了wfq_flow_t、struct pkt以及對外暴露的wfq_enqueue、wfq_dequeue、wfq_advance_vtime等函數(shù)。main.c通常是一個(gè)模擬程序構(gòu)造幾條不同權(quán)重的流往里面塞包然后循環(huán)調(diào)用wfq_dequeue觀察調(diào)度順序和帶寬分配比例。3.2 編譯命令與 Makefile 關(guān)鍵項(xiàng)如果項(xiàng)目自帶 Makefile直接make即可。如果沒有手動(dòng)編譯也不復(fù)雜# 編譯所有源文件生成 wfq_demo 可執(zhí)行文件 gcc -O2 -Wall -Iinclude src/wfq.c src/pkt.c src/main.c -o wfq_demo -lm-Iinclude指定頭文件路徑-lm鏈接數(shù)學(xué)庫虛擬時(shí)間計(jì)算用到浮點(diǎn)運(yùn)算。-O2開啟優(yōu)化WFQ 調(diào)度在高速鏈路上對性能敏感優(yōu)化編譯能明顯降低單包調(diào)度耗時(shí)。如果項(xiàng)目用 CMake常見做法是mkdir build cd build cmake .. make -j4編譯產(chǎn)物一般在build/目錄下。注意檢查CMakeLists.txt里是否鏈接了m庫有些項(xiàng)目會漏掉導(dǎo)致鏈接報(bào)錯(cuò)。3.3 運(yùn)行 Demo 與輸出解讀編譯成功后直接運(yùn)行./wfq_demo典型輸出會打印每個(gè)包的調(diào)度順序、所屬流 ID、包長、虛擬開始/完成時(shí)間。比如[調(diào)度] 流1 pkt#3 len512 finish120.5 [調(diào)度] 流2 pkt#1 len1024 finish128.0 [調(diào)度] 流1 pkt#4 len512 finish136.5 [調(diào)度] 流3 pkt#2 len256 finish140.0從輸出里能直觀看到權(quán)重高的流比如流1權(quán)重為4在相同時(shí)間內(nèi)被調(diào)度的包更多finish_time增長更慢。如果發(fā)現(xiàn)某條流長時(shí)間沒被調(diào)度先檢查它的權(quán)重是否配置為 0或者pkt_count是否一直為 0。3.4 參數(shù)調(diào)整與驗(yàn)證方法想驗(yàn)證加權(quán)公平性可以改main.c里的流數(shù)量和權(quán)重配置。常見做法是構(gòu)造兩條流權(quán)重分別為 1 和 3往兩條流里各塞 100 個(gè)相同大小的包統(tǒng)計(jì)各自被調(diào)度的包數(shù)量。理論上權(quán)重 3 的流應(yīng)該拿到約 75% 的調(diào)度機(jī)會。如果結(jié)果偏差很大重點(diǎn)檢查wfq_advance_vtime里active_weight的計(jì)算是否正確——它應(yīng)該是當(dāng)前所有非空流的權(quán)重之和而不是固定值。另一個(gè)容易翻車的地方是浮點(diǎn)精度長時(shí)間運(yùn)行后finish_time可能累積誤差可以考慮用定點(diǎn)數(shù)替代double。4. 避坑與排查WFQ 實(shí)現(xiàn)里最容易翻車的幾個(gè)點(diǎn)4.1 現(xiàn)象某條流被完全餓死一個(gè)包都發(fā)不出去原因通常是該流的weight被設(shè)為 0或者finish_time初始值過大導(dǎo)致永遠(yuǎn)排不到隊(duì)首。解決方法是檢查權(quán)重配置確保每條活躍流的權(quán)重至少為 1同時(shí)確認(rèn)finish_time在首次入隊(duì)時(shí)是基于global_vtime計(jì)算的而不是硬編碼的大數(shù)。4.2 現(xiàn)象調(diào)度順序和預(yù)期完全相反權(quán)重大的流反而被壓制這多半是pkt_virtual_len算反了。正確公式是pkt_len / weight權(quán)重越大虛擬包長越小。如果寫成了pkt_len * weight權(quán)重大的流finish_time增長更快反而被優(yōu)先調(diào)度的機(jī)會更少。改回來即可。4.3 現(xiàn)象程序運(yùn)行一段時(shí)間后調(diào)度越來越慢CPU 占用飆升常見原因是流內(nèi)隊(duì)列沒有及時(shí)釋放已發(fā)送的包節(jié)點(diǎn)內(nèi)存泄漏導(dǎo)致鏈表越來越長。每次wfq_dequeue后要確保free掉包節(jié)點(diǎn)并把head指針后移。另一個(gè)可能是活躍流數(shù)量很多時(shí)每次出隊(duì)都遍歷所有流找最小值復(fù)雜度是 O(n)。流數(shù)量超過幾百條時(shí)建議改用最小堆維護(hù)finish_time。4.4 現(xiàn)象虛擬時(shí)間推進(jìn)異常新入隊(duì)的包 start_time 比老包還小這是全局虛擬時(shí)間沒有正確推進(jìn)導(dǎo)致的。檢查wfq_advance_vtime是否在每次發(fā)送包后都被調(diào)用以及active_weight是否包含了所有非空流。如果active_weight算成了 0虛擬時(shí)間就停住了新包的start_time會一直停留在舊值造成插隊(duì)。4.5 現(xiàn)象多線程環(huán)境下調(diào)度結(jié)果隨機(jī)錯(cuò)亂WFQ 的流隊(duì)列和全局虛擬時(shí)間都是共享狀態(tài)多線程并發(fā)入隊(duì)/出隊(duì)必須加鎖。常見做法是給每條流一把自旋鎖全局虛擬時(shí)間用原子操作或單獨(dú)的互斥鎖保護(hù)。如果項(xiàng)目本身是單線程模型不要貿(mào)然引入多線程否則調(diào)試成本會成倍增加。5. 二次開發(fā)改權(quán)重策略、換數(shù)據(jù)結(jié)構(gòu)、接真實(shí)網(wǎng)卡5.1 把固定權(quán)重改成動(dòng)態(tài)權(quán)重原始代碼里權(quán)重是靜態(tài)配置的。實(shí)際業(yè)務(wù)中可能需要根據(jù)流的實(shí)時(shí)速率動(dòng)態(tài)調(diào)整權(quán)重——比如某條流突然流量暴漲臨時(shí)降低它的權(quán)重來保護(hù)其他流。改造點(diǎn)在wfq_enqueue之前加一個(gè)權(quán)重更新鉤子// 動(dòng)態(tài)權(quán)重調(diào)整示例根據(jù)流的歷史速率降低突發(fā)流的權(quán)重 void wfq_update_weight(wfq_flow_t *flow, uint32_t measured_rate) { uint32_t base_weight flow-weight; if (measured_rate HIGH_RATE_THRESHOLD) { // 速率超過閾值權(quán)重打七折 flow-weight base_weight * 7 / 10; } else { flow-weight base_weight; } if (flow-weight 0) flow-weight 1; // 保底 }注意權(quán)重變化后已經(jīng)入隊(duì)的包的finish_time不會自動(dòng)重算。如果希望立即生效需要遍歷流內(nèi)隊(duì)列重新計(jì)算finish_time但這會帶來額外開銷。我一般只在流內(nèi)隊(duì)列為空時(shí)更新權(quán)重避免重算。5.2 用最小堆替換線性掃描流數(shù)量少的時(shí)候線性掃描沒問題但流數(shù)量到幾百上千條時(shí)每次出隊(duì) O(n) 的掃描會成為瓶頸。把活躍流組織成以finish_time為鍵的最小堆出隊(duì)復(fù)雜度降到 O(log n)。改造時(shí)注意堆里存的是流索引還是流指針以及流變空后如何從堆中移除。5.3 對接真實(shí)網(wǎng)卡或 DPDK 的注意事項(xiàng)如果要把這套 WFQ 接到真實(shí)轉(zhuǎn)發(fā)面包的內(nèi)存管理需要從malloc/free換成內(nèi)存池避免頻繁分配釋放導(dǎo)致性能抖動(dòng)。另外真實(shí)網(wǎng)卡的包是按批次到達(dá)的入隊(duì)接口最好支持批量操作減少鎖競爭。虛擬時(shí)間的浮點(diǎn)運(yùn)算在高速場景下也可能成為瓶頸可以考慮用 64 位定點(diǎn)數(shù)替代double精度損失可控但速度更快。5.4 驗(yàn)證改造是否正確的三個(gè)方法改完代碼后怎么確認(rèn)沒改壞我一般走這三步第一跑原始 Demo 對比改造前后的調(diào)度序列確?；拘袨橐恢碌诙?gòu)造權(quán)重比為 1:1:1 的三條流統(tǒng)計(jì)長時(shí)間運(yùn)行后的包數(shù)量比例是否接近 1:1:1第三故意把某條流的權(quán)重調(diào)大 10 倍看它拿到的帶寬比例是否接近 10 倍。三個(gè)測試都過了基本可以認(rèn)為調(diào)度邏輯沒跑偏。從那以后我每次改調(diào)度類代碼都強(qiáng)制走一遍“權(quán)重比例驗(yàn)證 長時(shí)間運(yùn)行內(nèi)存檢查 邊界條件空流、單流、權(quán)重為 1測試”這三板斧踩過的坑實(shí)在太多了。希望這套 WFQ 實(shí)現(xiàn)和上面的改造思路能幫到你拿到源碼后先跑通 Demo再按自己的業(yè)務(wù)場景動(dòng)權(quán)重和數(shù)據(jù)結(jié)構(gòu)別一上來就大改。本文還有配套的精品資源點(diǎn)擊獲取 WFQ加權(quán)公平隊(duì)列C/C++實(shí)現(xiàn)：從原理到二次開發(fā)
簡介這是一份面向網(wǎng)絡(luò)編程學(xué)習(xí)者與通信方向開發(fā)者的WFQ加權(quán)公平隊(duì)列算法C/C實(shí)現(xiàn)工程聚焦多路復(fù)用網(wǎng)絡(luò)中數(shù)據(jù)流公平共享帶寬這一核心問題涵蓋發(fā)送端、接收端與路由器轉(zhuǎn)發(fā)三部分代碼適合用于理解隊(duì)列調(diào)度、權(quán)重分配與服務(wù)質(zhì)量保障的完整鏈路。壓縮包共344個(gè)文件約14.98MB以cpp與c源碼為主體配合h頭文件、obj編譯產(chǎn)物、exe可執(zhí)行程序及dsp/dsw工程文件另有doc說明與txt配置便于直接編譯運(yùn)行與二次修改。目前已有958人學(xué)習(xí)下載。資源完整呈現(xiàn)了隊(duì)列結(jié)構(gòu)設(shè)計(jì)、數(shù)據(jù)包分類、權(quán)重調(diào)度與循環(huán)監(jiān)控等關(guān)鍵環(huán)節(jié)讀者可對照源碼梳理WFQ與FIFO的差異掌握C面向?qū)ο蠼ＥcC底層轉(zhuǎn)發(fā)實(shí)現(xiàn)的結(jié)合方式并借助工程文件快速搭建調(diào)試環(huán)境為網(wǎng)絡(luò)協(xié)議棧與流量管理相關(guān)課程設(shè)計(jì)或項(xiàng)目開發(fā)提供可復(fù)用的參考實(shí)現(xiàn)。1. 從一次隊(duì)列調(diào)度翻車說起WFQ 到底解決什么問題做過網(wǎng)絡(luò)轉(zhuǎn)發(fā)或者 QoS 限速的朋友大概率遇到過這種場景多個(gè)業(yè)務(wù)流共享一條出口鏈路結(jié)果某個(gè)大流量業(yè)務(wù)把帶寬全吃光了語音、信令這些小包業(yè)務(wù)被餓死延遲飆到幾百毫秒。你可能會想加個(gè)優(yōu)先級隊(duì)列不就完了但優(yōu)先級隊(duì)列的問題是低優(yōu)先級流會被徹底餓死公平性無從談起。WFQWeighted Fair Queueing加權(quán)公平隊(duì)列就是來解決這個(gè)矛盾的。它給每條流分配一個(gè)權(quán)重按權(quán)重比例分配帶寬同時(shí)保證每條流至少能拿到屬于自己的那一份。這份資源是一套 C/C 實(shí)現(xiàn)的 WFQ 算法代碼適合做網(wǎng)絡(luò)協(xié)議棧、QoS 調(diào)度模塊、或者嵌入式轉(zhuǎn)發(fā)設(shè)備的開發(fā)者拿來直接集成或二次開發(fā)。代碼結(jié)構(gòu)清晰核心調(diào)度邏輯和數(shù)據(jù)結(jié)構(gòu)分離新手能跑通熟手能直接改權(quán)重計(jì)算和虛擬時(shí)間推進(jìn)策略。2. 核心架構(gòu)拆解虛擬時(shí)間、權(quán)重與包調(diào)度怎么串起來2.1 WFQ 的兩個(gè)核心概念虛擬時(shí)間與權(quán)重WFQ 的本質(zhì)是模擬一個(gè)“理想公平隊(duì)列”——假設(shè)鏈路可以無限細(xì)分每條流按權(quán)重比例同時(shí)獲得服務(wù)。實(shí)際實(shí)現(xiàn)里用一個(gè)虛擬時(shí)間Virtual Time來近似這個(gè)理想模型。每條流維護(hù)一個(gè)虛擬開始時(shí)間start_time和虛擬完成時(shí)間finish_time調(diào)度器每次選finish_time最小的包發(fā)送。權(quán)重決定了流之間分配帶寬的比例。權(quán)重為 2 的流理論上拿到的帶寬是權(quán)重為 1 的流的兩倍。虛擬時(shí)間的推進(jìn)速度與鏈路速率和活躍流的總權(quán)重相關(guān)這是整個(gè)算法最容易被寫錯(cuò)的地方。代碼里通常用這樣的結(jié)構(gòu)體表示一個(gè)流// 流控制塊每條流一個(gè)實(shí)例 typedef struct wfq_flow { uint32_t flow_id; // 流標(biāo)識 uint32_t weight; // 權(quán)重決定帶寬分配比例 double virtual_time; // 該流當(dāng)前的虛擬時(shí)間 double start_time; // 當(dāng)前包的虛擬開始時(shí)間 double finish_time; // 當(dāng)前包的虛擬完成時(shí)間 struct pkt *head; // 流內(nèi)包隊(duì)列頭 struct pkt *tail; // 流內(nèi)包隊(duì)列尾 uint32_t pkt_count; // 當(dāng)前排隊(duì)包數(shù)量 } wfq_flow_t;這里weight是外部配置進(jìn)來的virtual_time是該流上一次調(diào)度后的虛擬時(shí)間戳。start_time和finish_time在每次新包入隊(duì)時(shí)計(jì)算計(jì)算方式直接決定了調(diào)度公平性。2.2 包入隊(duì)start_time 和 finish_time 的計(jì)算當(dāng)一個(gè)包到達(dá)時(shí)WFQ 需要計(jì)算它的虛擬開始時(shí)間和虛擬完成時(shí)間。標(biāo)準(zhǔn)做法是// 包入隊(duì)時(shí)計(jì)算虛擬時(shí)間戳 // pkt_len: 包長字節(jié)link_rate: 鏈路速率字節(jié)/秒 void wfq_enqueue(wfq_flow_t *flow, struct pkt *pkt, double link_rate) { double pkt_virtual_len (double)pkt-len / flow-weight; // 如果流內(nèi)沒有排隊(duì)包start_time 取當(dāng)前虛擬時(shí)間 if (flow-pkt_count 0) { flow-start_time flow-virtual_time; } else { // 否則取上一個(gè)包的 finish_time flow-start_time flow-finish_time; } // finish_time start_time 包長/權(quán)重 flow-finish_time flow-start_time pkt_virtual_len; // 包掛入流內(nèi)隊(duì)列 pkt-start_time flow-start_time; pkt-finish_time flow-finish_time; enqueue_pkt(flow, pkt); flow-pkt_count; }關(guān)鍵點(diǎn)在于pkt_virtual_len pkt_len / weight。權(quán)重越大虛擬包長越小finish_time增長越慢該流的包就越容易被優(yōu)先調(diào)度。這就是“加權(quán)”的體現(xiàn)。start_time的取值邏輯保證了同一條流內(nèi)部的包按到達(dá)順序服務(wù)不會出現(xiàn)后到的包插隊(duì)。2.3 調(diào)度出隊(duì)選 finish_time 最小的包調(diào)度器每次從所有非空流中選出finish_time最小的包發(fā)送。如果多條流的finish_time相同可以按流 ID 或輪詢方式打破平局。// 從所有活躍流中選出 finish_time 最小的包 struct pkt *wfq_dequeue(wfq_flow_t *flows, int flow_cnt, double link_rate) { int selected -1; double min_finish 1e18; for (int i 0; i flow_cnt; i) { if (flows[i].pkt_count 0) continue; struct pkt *head_pkt flows[i].head; if (head_pkt-finish_time min_finish) { min_finish head_pkt-finish_time; selected i; } } if (selected 0) return NULL; // 所有流為空 struct pkt *pkt dequeue_pkt(flows[selected]); flows[selected].pkt_count--; // 更新該流的虛擬時(shí)間 flows[selected].virtual_time pkt-finish_time; // 如果流內(nèi)還有包更新 start_time/finish_time 基準(zhǔn) if (flows[selected].pkt_count 0) { flows[selected].start_time flows[selected].virtual_time; flows[selected].finish_time flows[selected].start_time (double)flows[selected].head-len / flows[selected].weight; } return pkt; }這段代碼里virtual_time的更新很關(guān)鍵。它記錄的是該流最近一次被服務(wù)到的虛擬時(shí)間點(diǎn)后續(xù)入隊(duì)的包會以此為基準(zhǔn)計(jì)算start_time。如果忘了更新同一條流的包會一直用舊的虛擬時(shí)間導(dǎo)致調(diào)度順序錯(cuò)亂。2.4 虛擬時(shí)間的全局推進(jìn)上面只講了單流內(nèi)部的虛擬時(shí)間。實(shí)際上所有流共享一個(gè)全局虛擬時(shí)間global_vtime它隨著鏈路發(fā)送包而推進(jìn)。推進(jìn)速度與當(dāng)前活躍流的總權(quán)重有關(guān)// 每發(fā)送一個(gè)包后推進(jìn)全局虛擬時(shí)間 // pkt_len: 剛發(fā)送的包長active_weight: 當(dāng)前所有非空流的權(quán)重之和 void wfq_advance_vtime(double *global_vtime, uint32_t pkt_len, uint32_t active_weight, double link_rate) { if (active_weight 0) return; // 虛擬時(shí)間推進(jìn)量 實(shí)際發(fā)送時(shí)間 / 活躍總權(quán)重 double real_time (double)pkt_len / link_rate; *global_vtime real_time * active_weight; }這個(gè)公式的含義是鏈路每發(fā)送一個(gè)包全局虛擬時(shí)間前進(jìn)的量等于“實(shí)際耗時(shí) × 活躍總權(quán)重”?；钴S流越多虛擬時(shí)間走得越快新入隊(duì)的包start_time就越大避免新流插隊(duì)。這是 WFQ 保證公平性的核心機(jī)制。3. 編譯與運(yùn)行從源碼到可執(zhí)行 Demo 的完整步驟3.1 目錄結(jié)構(gòu)與文件說明拿到源碼后先看目錄結(jié)構(gòu)。典型的 WFQ 實(shí)現(xiàn)項(xiàng)目會包含以下文件wfq/ ├── include/ │ ├── wfq.h # 核心數(shù)據(jù)結(jié)構(gòu)與接口聲明 │ └── pkt.h # 包結(jié)構(gòu)定義 ├── src/ │ ├── wfq.c # WFQ 調(diào)度核心實(shí)現(xiàn) │ ├── pkt.c # 包隊(duì)列操作 │ └── main.c # 測試入口模擬多流調(diào)度 ├── Makefile └── README.mdwfq.h里定義了wfq_flow_t、struct pkt以及對外暴露的wfq_enqueue、wfq_dequeue、wfq_advance_vtime等函數(shù)。main.c通常是一個(gè)模擬程序構(gòu)造幾條不同權(quán)重的流往里面塞包然后循環(huán)調(diào)用wfq_dequeue觀察調(diào)度順序和帶寬分配比例。3.2 編譯命令與 Makefile 關(guān)鍵項(xiàng)如果項(xiàng)目自帶 Makefile直接make即可。如果沒有手動(dòng)編譯也不復(fù)雜# 編譯所有源文件生成 wfq_demo 可執(zhí)行文件 gcc -O2 -Wall -Iinclude src/wfq.c src/pkt.c src/main.c -o wfq_demo -lm-Iinclude指定頭文件路徑-lm鏈接數(shù)學(xué)庫虛擬時(shí)間計(jì)算用到浮點(diǎn)運(yùn)算。-O2開啟優(yōu)化WFQ 調(diào)度在高速鏈路上對性能敏感優(yōu)化編譯能明顯降低單包調(diào)度耗時(shí)。如果項(xiàng)目用 CMake常見做法是mkdir build cd build cmake .. make -j4編譯產(chǎn)物一般在build/目錄下。注意檢查CMakeLists.txt里是否鏈接了m庫有些項(xiàng)目會漏掉導(dǎo)致鏈接報(bào)錯(cuò)。3.3 運(yùn)行 Demo 與輸出解讀編譯成功后直接運(yùn)行./wfq_demo典型輸出會打印每個(gè)包的調(diào)度順序、所屬流 ID、包長、虛擬開始/完成時(shí)間。比如[調(diào)度] 流1 pkt#3 len512 finish120.5 [調(diào)度] 流2 pkt#1 len1024 finish128.0 [調(diào)度] 流1 pkt#4 len512 finish136.5 [調(diào)度] 流3 pkt#2 len256 finish140.0從輸出里能直觀看到權(quán)重高的流比如流1權(quán)重為4在相同時(shí)間內(nèi)被調(diào)度的包更多finish_time增長更慢。如果發(fā)現(xiàn)某條流長時(shí)間沒被調(diào)度先檢查它的權(quán)重是否配置為 0或者pkt_count是否一直為 0。3.4 參數(shù)調(diào)整與驗(yàn)證方法想驗(yàn)證加權(quán)公平性可以改main.c里的流數(shù)量和權(quán)重配置。常見做法是構(gòu)造兩條流權(quán)重分別為 1 和 3往兩條流里各塞 100 個(gè)相同大小的包統(tǒng)計(jì)各自被調(diào)度的包數(shù)量。理論上權(quán)重 3 的流應(yīng)該拿到約 75% 的調(diào)度機(jī)會。如果結(jié)果偏差很大重點(diǎn)檢查wfq_advance_vtime里active_weight的計(jì)算是否正確——它應(yīng)該是當(dāng)前所有非空流的權(quán)重之和而不是固定值。另一個(gè)容易翻車的地方是浮點(diǎn)精度長時(shí)間運(yùn)行后finish_time可能累積誤差可以考慮用定點(diǎn)數(shù)替代double。4. 避坑與排查WFQ 實(shí)現(xiàn)里最容易翻車的幾個(gè)點(diǎn)4.1 現(xiàn)象某條流被完全餓死一個(gè)包都發(fā)不出去原因通常是該流的weight被設(shè)為 0或者finish_time初始值過大導(dǎo)致永遠(yuǎn)排不到隊(duì)首。解決方法是檢查權(quán)重配置確保每條活躍流的權(quán)重至少為 1同時(shí)確認(rèn)finish_time在首次入隊(duì)時(shí)是基于global_vtime計(jì)算的而不是硬編碼的大數(shù)。4.2 現(xiàn)象調(diào)度順序和預(yù)期完全相反權(quán)重大的流反而被壓制這多半是pkt_virtual_len算反了。正確公式是pkt_len / weight權(quán)重越大虛擬包長越小。如果寫成了pkt_len * weight權(quán)重大的流finish_time增長更快反而被優(yōu)先調(diào)度的機(jī)會更少。改回來即可。4.3 現(xiàn)象程序運(yùn)行一段時(shí)間后調(diào)度越來越慢CPU 占用飆升常見原因是流內(nèi)隊(duì)列沒有及時(shí)釋放已發(fā)送的包節(jié)點(diǎn)內(nèi)存泄漏導(dǎo)致鏈表越來越長。每次wfq_dequeue后要確保free掉包節(jié)點(diǎn)并把head指針后移。另一個(gè)可能是活躍流數(shù)量很多時(shí)每次出隊(duì)都遍歷所有流找最小值復(fù)雜度是 O(n)。流數(shù)量超過幾百條時(shí)建議改用最小堆維護(hù)finish_time。4.4 現(xiàn)象虛擬時(shí)間推進(jìn)異常新入隊(duì)的包 start_time 比老包還小這是全局虛擬時(shí)間沒有正確推進(jìn)導(dǎo)致的。檢查wfq_advance_vtime是否在每次發(fā)送包后都被調(diào)用以及active_weight是否包含了所有非空流。如果active_weight算成了 0虛擬時(shí)間就停住了新包的start_time會一直停留在舊值造成插隊(duì)。4.5 現(xiàn)象多線程環(huán)境下調(diào)度結(jié)果隨機(jī)錯(cuò)亂WFQ 的流隊(duì)列和全局虛擬時(shí)間都是共享狀態(tài)多線程并發(fā)入隊(duì)/出隊(duì)必須加鎖。常見做法是給每條流一把自旋鎖全局虛擬時(shí)間用原子操作或單獨(dú)的互斥鎖保護(hù)。如果項(xiàng)目本身是單線程模型不要貿(mào)然引入多線程否則調(diào)試成本會成倍增加。5. 二次開發(fā)改權(quán)重策略、換數(shù)據(jù)結(jié)構(gòu)、接真實(shí)網(wǎng)卡5.1 把固定權(quán)重改成動(dòng)態(tài)權(quán)重原始代碼里權(quán)重是靜態(tài)配置的。實(shí)際業(yè)務(wù)中可能需要根據(jù)流的實(shí)時(shí)速率動(dòng)態(tài)調(diào)整權(quán)重——比如某條流突然流量暴漲臨時(shí)降低它的權(quán)重來保護(hù)其他流。改造點(diǎn)在wfq_enqueue之前加一個(gè)權(quán)重更新鉤子// 動(dòng)態(tài)權(quán)重調(diào)整示例根據(jù)流的歷史速率降低突發(fā)流的權(quán)重 void wfq_update_weight(wfq_flow_t *flow, uint32_t measured_rate) { uint32_t base_weight flow-weight; if (measured_rate HIGH_RATE_THRESHOLD) { // 速率超過閾值權(quán)重打七折 flow-weight base_weight * 7 / 10; } else { flow-weight base_weight; } if (flow-weight 0) flow-weight 1; // 保底 }注意權(quán)重變化后已經(jīng)入隊(duì)的包的finish_time不會自動(dòng)重算。如果希望立即生效需要遍歷流內(nèi)隊(duì)列重新計(jì)算finish_time但這會帶來額外開銷。我一般只在流內(nèi)隊(duì)列為空時(shí)更新權(quán)重避免重算。5.2 用最小堆替換線性掃描流數(shù)量少的時(shí)候線性掃描沒問題但流數(shù)量到幾百上千條時(shí)每次出隊(duì) O(n) 的掃描會成為瓶頸。把活躍流組織成以finish_time為鍵的最小堆出隊(duì)復(fù)雜度降到 O(log n)。改造時(shí)注意堆里存的是流索引還是流指針以及流變空后如何從堆中移除。5.3 對接真實(shí)網(wǎng)卡或 DPDK 的注意事項(xiàng)如果要把這套 WFQ 接到真實(shí)轉(zhuǎn)發(fā)面包的內(nèi)存管理需要從malloc/free換成內(nèi)存池避免頻繁分配釋放導(dǎo)致性能抖動(dòng)。另外真實(shí)網(wǎng)卡的包是按批次到達(dá)的入隊(duì)接口最好支持批量操作減少鎖競爭。虛擬時(shí)間的浮點(diǎn)運(yùn)算在高速場景下也可能成為瓶頸可以考慮用 64 位定點(diǎn)數(shù)替代double精度損失可控但速度更快。5.4 驗(yàn)證改造是否正確的三個(gè)方法改完代碼后怎么確認(rèn)沒改壞我一般走這三步第一跑原始 Demo 對比改造前后的調(diào)度序列確?；拘袨橐恢碌诙?gòu)造權(quán)重比為 1:1:1 的三條流統(tǒng)計(jì)長時(shí)間運(yùn)行后的包數(shù)量比例是否接近 1:1:1第三故意把某條流的權(quán)重調(diào)大 10 倍看它拿到的帶寬比例是否接近 10 倍。三個(gè)測試都過了基本可以認(rèn)為調(diào)度邏輯沒跑偏。從那以后我每次改調(diào)度類代碼都強(qiáng)制走一遍“權(quán)重比例驗(yàn)證 長時(shí)間運(yùn)行內(nèi)存檢查 邊界條件空流、單流、權(quán)重為 1測試”這三板斧踩過的坑實(shí)在太多了。希望這套 WFQ 實(shí)現(xiàn)和上面的改造思路能幫到你拿到源碼后先跑通 Demo再按自己的業(yè)務(wù)場景動(dòng)權(quán)重和數(shù)據(jù)結(jié)構(gòu)別一上來就大改。本文還有配套的精品資源點(diǎn)擊獲取