fq_codel這個新的機(jī)制進(jìn)入內(nèi)核已經(jīng)有一段時間了，主要是在Linux的Wi-Fi子系統(tǒng)中使用。但是目前好像并沒有像樣的中文的介紹。正好之前參與開源組織合作開發(fā)Airtime fairness(ATF)的時候，有比較深入的去了解它的大致原理，這里試著縷一縷它的大致邏輯。
目錄
I. fq-codel 的由來
II. fq-codel的基本原理
I. fq-codel 的由來
如果不做些search，可能很多人根本不知道fq-codel代表的是什么意思。fq-codel代表的就是the flow queue control delay，中文翻譯出來味道就變了，所以不做翻譯。
為什么我們需要fq_codel,它要解決什么問題？
想象一下，你現(xiàn)在在你的手機(jī)上干三件事，第一個通過百度云App下載不可描述的島國小片片，第二個你在和好基友微信語音聊天，第三個，聊天的同時還會開個瀏覽器查詢下和好基友聊到的島國明星。這時候?qū)τ谀慵依锏穆酚善鰽P來說，就有三個數(shù)據(jù)流要發(fā)往你的手機(jī)，一個是百度云上下載的片的數(shù)據(jù)，一個是好基友回復(fù)的一段語音，還有就是你百度一下的島國明星，百度返回給你的一系列不可描述的網(wǎng)站地址，然而遵循一般的先到先發(fā)的原則(FIFO)，很有可能你下載的小片片下載速率很高，每時每刻都有數(shù)據(jù)到達(dá)AP, 于是堵在發(fā)送隊(duì)列前頭，占據(jù)了很多的發(fā)送帶寬。如果這個等待發(fā)送的數(shù)據(jù)隊(duì)列足夠長（對應(yīng)的buffer足夠大），對于微信語音和網(wǎng)站的返回?cái)?shù)據(jù)這些對時間敏感，數(shù)據(jù)量其實(shí)不大，但是非常影響用戶體驗(yàn)的數(shù)據(jù)流，就會被卡住發(fā)不出去，除非排隊(duì)排到自己。這樣對你來說就是感覺延遲很大，半天等不到基友的回復(fù)和網(wǎng)站的返回。更糟的情況可能是，如果運(yùn)氣不好，后兩種數(shù)據(jù)流來的時候隊(duì)列滿了，那么很有可能基友的回復(fù)和網(wǎng)站的返回的數(shù)據(jù)都會被丟掉，這樣微信還需要替你的基友重發(fā)一下，百度也會重新發(fā)送搜索的結(jié)果，又是一坨從遠(yuǎn)端過來的等待時間，運(yùn)氣再差點(diǎn)的話，又會遇到同樣的問題，周而復(fù)始。
這種問題叫bufferbloat，fq_codel就是要致力于解決bufferbloat的問題，改善round-time times(RTT)，甚至提高整體吞吐率. fq_codel對于實(shí)時性要求高的，數(shù)據(jù)包不大的應(yīng)用特別nice，比如VOIP，在線游戲。
更多的詳情參考wiki：
https://en.wikipedia.org/wiki/Bufferbloat
# fq-codel的基本原理
思考一下上面的那個簡單例子，倘若能有什么方法能夠適當(dāng)調(diào)整發(fā)包的順序，將基友的語音數(shù)據(jù)和百度返回的數(shù)據(jù)提前，那么是不是整個體驗(yàn)就會好得多?；舅悸肪褪沁@樣，but How？
在講原理之前，首先要明白fq-codel中flow的概念，一個flow是于tuple5和隨機(jī)數(shù)關(guān)聯(lián)的概念。tuple5代表了源/目的 地址，源/目的 端口，以及協(xié)議類型五個元素。這樣子每一個從遠(yuǎn)端發(fā)往你手機(jī)上的應(yīng)用的數(shù)據(jù)都可以按tuple5劃分成唯一的flow。
先前說了fq-codel其實(shí)是the flow queue control delay，進(jìn)一步說就是flow queue + codel算法的結(jié)合。
簡單來說就是將數(shù)據(jù)按照flow區(qū)分開來，把數(shù)據(jù)緩存在該flow的queue之中，同時引入DRR(Deficit Round Robin) 調(diào)度機(jī)制。Deficit以字節(jié)數(shù)為單位，可以理解為是一個關(guān)于該flow是否可以發(fā)送的閾值判斷，除非有大于0的deficit，否則這個flow緩存的數(shù)據(jù)不能夠發(fā)送。
發(fā)往同一設(shè)備的flow組成一個隊(duì)列，每次調(diào)度的時候，如果隊(duì)列頭的flow的deficit小于0，會放到隊(duì)列尾部并回補(bǔ)固定的Deficit，然后繼續(xù)iterate該隊(duì)列直到找到deficit大于0的flow進(jìn)行發(fā)送，并更新deficit(減掉發(fā)送字節(jié)數(shù))，flow也會被從隊(duì)列頭調(diào)度走。(為了方便描述，具體的調(diào)度算法會有些出入，等待被調(diào)度flow的隊(duì)列由new，old兩個flow隊(duì)列)
如果某個flow緩存的數(shù)據(jù)時間過長，就要依照codel的算法drop；如果緩存需要的總的buffer用完或者緩存的總的packets大于一定閾值，緩存最多數(shù)據(jù)的flow里面的skb也會被drop, 直到有可用buffer或者緩存總packets小于閾值為止。更多的內(nèi)容會在后續(xù)文章詳述，如果有的話 :) 。
具體來講，按照上面的例子就是，當(dāng)數(shù)據(jù)到達(dá)AP，被分成三條flow，由于deficit的原因，比如初始值300，每次回補(bǔ)300。開始的時候下載小片片的flow在隊(duì)頭，如果它發(fā)送一次就消耗了400字節(jié)，deficit變成-100，在接下來的調(diào)度中，其他兩個flow由于包比較小，消耗不到300，只有200，deficit變成100；當(dāng)小片片的flow的再次到達(dá)時，由于deficit為-100，它不會被調(diào)度，只能重新排隊(duì)到隊(duì)尾，回補(bǔ)300，deficit變成200，而接下來的兩次調(diào)度中其他兩個flow會被發(fā)送，deficit會變成-100。這就意味著實(shí)時性小包被發(fā)送的次數(shù)是大包的兩倍。但是即使這樣，也不代表大包沒有機(jī)會被發(fā)送，在后續(xù)的調(diào)度中它也會被調(diào)度到。
這樣子每個flow都不可能一直發(fā)送數(shù)據(jù)，讓其他flow干等，按照發(fā)送字節(jié)數(shù)去調(diào)度，最大限度保證了，實(shí)時性的小包能更早被發(fā)送出去。所以這個deficit也不能設(shè)置很大。
這種基于發(fā)送字節(jié)數(shù)的DRR是不是蠻巧妙？
歡迎指正。
