Linux 塊層向上為文件系統(tǒng)和塊設(shè)備提交接口，使得上層能夠以統(tǒng)一的方式訪問各種類型的后端存儲設(shè)備。同時，它也向下為設(shè)備驅(qū)動提供接口，讓驅(qū)動層能夠以一致的方式來接受請求。一些驅(qū)動如上一篇文章中提到的DRBD和RBD設(shè)備，只使用bio層提供的一些接口，對bio請求進(jìn)行處理。其它的驅(qū)動則可以從IO請求plugging機制,各種請求排序和請求合并中受益。為了給驅(qū)動層提供服務(wù)，塊層做了不少事情，我且稱之為"request層"。

現(xiàn)在，"request層"并存著兩種模型：單隊列(single-queue) 和 多隊列(multi-queue)。多隊列的出現(xiàn)也就是近幾年的事情，也許總有一天會完全取代單隊列的，但是目前來看兩者在內(nèi)核的使用都相當(dāng)活躍。有了這兩種不同的排隊方法(queuing approach)做參考，我們就可以兩相對比來學(xué)習(xí)學(xué)習(xí)，所以我們將花點時間都看看，分析他們?nèi)绾伟颜埱蟪尸F(xiàn)給驅(qū)動層的。首先，我們來看看兩者的共同之處，分析這兩個關(guān)鍵的結(jié)構(gòu)體是個不錯的入手點： struct request_queue 和 struct request。

請求隊列和請求

struct request_queue之于struct request的關(guān)系，非常像struct gendisk之于struct bio的關(guān)系：一個代表具體的設(shè)備，一個代表IO請求。需要注意的是，每個gendisk都有一個關(guān)聯(lián)的request_queue結(jié)構(gòu)體，但是只有那些使用了"request層"的設(shè)備才會分配request結(jié)構(gòu)體。按理說，適用于所有塊設(shè)備的域，比如struct queue_limits，都應(yīng)該放到gendisk結(jié)構(gòu)體里面，而對于一些僅適用于"request層"隊列管理的域，其實只應(yīng)當(dāng)分配給那些使用了"request層"的設(shè)備。現(xiàn)在來看，這些結(jié)構(gòu)體里有些域的安排可能就是歷史巧合，也不值得去糾正了。各種隊列相關(guān)的域，都可以在/sys/block/*/queue/目錄下查看。

request結(jié)構(gòu)體代表單個IO請求，最終要傳遞到底層設(shè)備。一個request包含一個或多個代表連續(xù)IO請求的bio，一些跟蹤總體狀態(tài)的信息（比如時間戳，哪個CPU發(fā)來的請求），和一些用來鏈入更大數(shù)據(jù)結(jié)構(gòu)的“錨點”，比如用struct list_head queuelist鏈入一個簡單的隊列結(jié)構(gòu)，用struct hlist_node hash鏈入一個哈希表(用來查找與新bio相鄰的請求)，用struct rb_node rb_node來把請求放在一棵紅黑樹上。在分配一個request結(jié)構(gòu)體的時候，有時候要分配一些額外的空間來給底層驅(qū)動保存一些額外的信息。有時候這些空間用來保存命令頭部，以便發(fā)送給底層設(shè)備，比如 SCSI command descriptor block，驅(qū)動可以自由地決定如何使用這塊空間。

相應(yīng)的make_request_fn()函數(shù) (單隊列是blk_queue_bio，多隊列是blk_mq_make_request())為IO請求創(chuàng)建一個request結(jié)構(gòu)體，然后把交給IO調(diào)度器, 也叫電梯算法"elevator", 這個名字來自電梯算法（ elevator algorithm），電梯算法曾是磁盤IO調(diào)度一個里程碑式的成就。我們將快速看一下單隊列的實現(xiàn)，然后再對比地去看多隊列。

單隊列上的請求調(diào)度

過去，大多存儲設(shè)備都是機械硬盤，要通過磁頭尋道，盤片旋轉(zhuǎn)來定位數(shù)據(jù)。機械盤一次只能處理一個請求，從盤片上一個位置挪動到下一個位置代價很大。單隊列的實現(xiàn)就是為這種類型的設(shè)備而生的，然后漸漸地也能支持其它快速設(shè)備，然而單隊列整體結(jié)構(gòu)依然反映了旋轉(zhuǎn)類型存儲設(shè)備的需求。

單隊列調(diào)度器主要有三個任務(wù)：

積聚代表連續(xù)IO操作的多個bio，合并成更大的IO請求，充分發(fā)揮硬件性能，但是請求不能太大超高硬件設(shè)備的限制；

把請求進(jìn)行排序來減少尋道時間，但是又要保證重要的請求得到及時處理。不斷尋求較優(yōu)方案，來解決這個問題，是這一部分代碼復(fù)雜度的根源。一般很難知道這兩點：一個請求有多重要，和一個請求需要多少尋道時間，我們只能依賴啟發(fā)式方法來判斷怎樣排序比較好，然而啟發(fā)式方法絕不是完美的；

把經(jīng)過整理的請求列表交給底層驅(qū)動，讓驅(qū)動從隊列取下請求去處理，同時提供一個通知機制來告訴上層請求處理的結(jié)果。

最后一個任務(wù)很直接了當(dāng)。驅(qū)動會通過blk_init_queue_node()來注冊一個request_fn()策略例程，只要隊列上有新請求已經(jīng)準(zhǔn)備好，策略例程被調(diào)用去處理這個請求。驅(qū)動負(fù)責(zé)用blk_peek_request()來從隊列上取下請求，然后進(jìn)行處理。當(dāng)請求處理完畢 [有些設(shè)備可以并行處理多個請求]，驅(qū)動會從隊列上摘下另一個請求來處理，而不用再去調(diào)用request_fn() [因為request_fn()一次拿到了整個列表上的所有request]。請求一旦處理完畢，就可調(diào)用blk_finish_request()來通知上層。

第一個任務(wù)有部分是用elv_attempt_insert_merge()完成的，它會快速地檢查隊列，看是否可以找到一個已經(jīng)存在的request，把新的bio合并進(jìn)入。如果成功，調(diào)度器就會允許合并，如果失敗，調(diào)度器還有一次機會嘗試在調(diào)度器內(nèi)部進(jìn)行一次合并。如果沒有機會合并，就分配一個新的請求，然后交給調(diào)度器。稍后一會，如果某個請求因合并而長大，使得它與該請求變成了連續(xù)的，調(diào)度器就可以再次嘗試合并操作。

第二個任務(wù)可能是最復(fù)雜的。如何把請求按照"適當(dāng)"順序排隊非常依賴我們?nèi)绾蝸斫忉?適當(dāng)"的含義。這三種不同的單隊列調(diào)度器: noop, deadline和cfq，對“適當(dāng)”的解釋就非常不一樣。

"noop"會對請求做一些簡單的排序，不允許把讀請求挪到寫請求之前，反之亦然；依據(jù)電梯算法，一個同類型的請求可以插入到另一個之前。除了elv_dispatch_sort()所做簡單排序，"noop"就是一個FIFO隊列。

“deadline”會把提交時間相近的請求放在一批。在同一批中，請求會被排序。當(dāng)一批請求達(dá)到了大小上限或著定時器超時，這批請求就會提交到設(shè)備隊列上去。這個算法嘗試給每一個請求都設(shè)置一個延遲時間上限，同時盡量聚集比較大的一批請求。

"cfq"即"Complete Fairness Queuing"，相比其它幾個調(diào)度器要復(fù)雜很多，目的是在不同進(jìn)程或進(jìn)程組間保證IO資源使用的公平性。cfq調(diào)度器內(nèi)部維護(hù)了多個隊列，每一個進(jìn)程都有一個隊列來保存來自該進(jìn)程的同步請求(通常是讀)，而對于異步請求(通常是寫)，每一個優(yōu)先級都有一個隊列，所有請求不論來自哪個進(jìn)程都按照優(yōu)先級放到相應(yīng)的隊列上。在提交請求時，按照優(yōu)先級每個隊列都有機會得到調(diào)度。每個隊列都有一定的時間片，在時間片內(nèi)才能提交一定數(shù)量的請求。當(dāng)一個同步隊列中的請求不足一定數(shù)量時，這個設(shè)備可以空閑一會，即使其它隊列里可能有請求等待處理。通常，同步請求之間在磁盤上的物理位置是連續(xù)的，所以讓磁盤稍等一會來接收更多連續(xù)的請求，這樣做可以提高吞吐量。以上對CFQ的描述僅僅是點皮毛。內(nèi)核文檔（Documentation/block/cfq-iosched.txt）講的更詳細(xì)點，還列出了所有參數(shù)，通過調(diào)整這些參數(shù)能夠適應(yīng)各種不同的場景。

之前提到過，一些高端點的設(shè)備可以一次處理多個請求，即在一個請求還沒有處理完成之前，就能夠處理新的請求。通常，這個要用到"tagging"功能，給每一個請求加一個標(biāo)簽，這樣請求完成通知就能和原來的請求正確的對應(yīng)起來。單隊列的"request層"可以對任意深度的設(shè)備提供"tagging"功能。

一個設(shè)備內(nèi)部可以通過真正地并行處理請求，來支持被標(biāo)記的命令，比如通過訪問一個內(nèi)存緩存，通過設(shè)計多模塊而每個模塊都能處理一個請求，或者通過其內(nèi)部隊列，這樣的隊列比"request層"更加了解設(shè)備。

多隊列和多CPU

多隊列的另一個動機就是減少鎖的開銷，因為我們的系統(tǒng)處理器越來越多，而請求從多個處理器放到一個隊列中時需要加鎖，鎖的開銷變得越來越大。"plugging"機制能幫得上一些忙，但是不夠理想。如果我們能夠分配更多隊列：每個NUMA節(jié)點一個隊列，或者一個CPU一個隊列，那么把請求放到隊列的鎖開銷就會減少很多。如果硬件支持并行處理多個請求，那么這樣做的優(yōu)勢就更大了。如果硬件只支持一次提交一個請求，那么多個per-CPU隊列仍然需要合并。如果他們比"plugging"機制批處理的效果更好，那么這樣做也是有益處的。假如不能提高批處理的效果，寫程序的時候小心點應(yīng)該也能夠保證，至少不會有什么損失。

之前說過，cfq調(diào)度器內(nèi)部已經(jīng)有多個隊列，但是它們跟multi-queue的目的完全不一樣，它們把請求與進(jìn)程和優(yōu)先級關(guān)聯(lián)起來，而multi-queue的隊列是跟硬件密切相關(guān)的。multi-queue "request層"維護(hù)著兩組硬件相關(guān)的隊列：軟件的"staging"隊列和硬件的"dispatch"隊列。

軟件staging隊列(struct blk_mq_ctx)是依CPU硬件情況而分配的，每個CPU分配一個，或每個NUMA節(jié)點分配一個。當(dāng)塊層的"plugging"機制拔開"塞子"時(blk_mq_flush_plug_list())，request請求在一個spinlock的保護(hù)下被添加到隊列上，鎖競爭應(yīng)該很少。multi-queue的隊列可以選擇由某一個multi-queue調(diào)度器來管理, 現(xiàn)在有三種multi-queue調(diào)度器：bfq, kyber和mq-deadline.

硬件dispatch隊列是基于目標(biāo)硬件塊設(shè)備進(jìn)行分配的，所以有可能只有一個，也有可能多達(dá)2048個隊列 (或與硬件支持的中斷源個數(shù)一樣)。"request層"為每一個硬件隊列(或"硬件上下文")分配一個數(shù)據(jù)結(jié)構(gòu)struct blk_mq_hw_ctx，維護(hù)著一個CPU和隊列之間的映射表，而隊列本身就是為底層驅(qū)動而服務(wù)的。“request 層”時不時地把硬件隊列中的請求傳遞給底層驅(qū)動。接下來，請求就全由驅(qū)動處理了，通常情況下，又會很快按照接收的順序交給硬件。

與single-queue相比有另一個重要區(qū)別，multi-queue使用的request結(jié)構(gòu)體都是預(yù)分配的。每個request結(jié)構(gòu)體都關(guān)聯(lián)著一個不同tag number，這個tag number會隨著請求傳遞到硬件，再隨著請求完成通知傳遞回來。早點為一個請求分配tag number，在時機到來的時候，request 層可隨時向底層發(fā)送請求。

single-queue只需要一個request_fn()就可以了，但是multi-queue需要底層驅(qū)動提供一個struct blk_mq_ops結(jié)構(gòu)體，包含了多達(dá)11個函數(shù)。其中，最核心的一個函數(shù)是queue_rq()，其它的函數(shù)實現(xiàn)了超時，請求完成輪詢，請求初始化，等類似操作。

一旦請求就緒，并且調(diào)度器不想再把請求保持在隊列上來排序或擴展，調(diào)度器就會調(diào)用queue_rq()函數(shù)。single-queue把收集請求的責(zé)任交給了驅(qū)動層，與之不同，multi-queue卻把這個責(zé)任交給了"request層"。queue_rq()有個參數(shù)代表的是硬件上下文，通常會把請求放在內(nèi)部FIFO隊列上，也有可能會直接處理。queue_rq()可以拒絕一個請求，然后返回BLK_STS_RESOURCE，讓請求繼續(xù)在staging隊列上等待。除了BLK_STS_RESOURCE和BLK_STS_OK，其它返回值都被視為IO錯誤。

多隊列調(diào)度

multi-queue不是必須要配置一個調(diào)度器，如果不指定的話，那么就會用類似單隊列中的“noop”調(diào)度器。連續(xù)的bio會被合并到一個請求，而不連續(xù)的bio各成為一個獨立的請求。這些請求以FIFO的順序被放到staging隊列中，盡管有多個submission隊列，默認(rèn)的調(diào)度器會嘗試直接提交新請求，僅僅在收到BLK_STS_RESOURCE返回值時才會使用staging隊列。當(dāng)塊設(shè)備上的plugging機制拔開“塞子”時，調(diào)度器會調(diào)用blk_mq_run_hw_queue()或blk_mq_delay_run_hw_queue()把軟件隊列傳遞給驅(qū)動層處理。

可插拔的multi-queue調(diào)度器有22個入口點，其中有兩個函數(shù)，一個是insert_requests()把一組請求添加到軟件staging隊列中，另一個是dispatch_request()會選擇一個請求然后傳遞給硬件設(shè)備。如果沒有實現(xiàn)insert_request()函數(shù)，請求就會被簡單的插入到列表末尾。如果沒有提供dispatch_request()函數(shù)，就會從staging隊列里取下請求，然后以任意順序傳遞到相應(yīng)的硬件隊列。This "collect everything" step is the main point of cross-CPU locking and can hurt performance, so it is best if a device with a single hardware queue accepts all the requests it is given.[最后一句我理解不到那個點，大致理解是說staging隊列有多個，硬件隊列只有一個的情況，那么多個軟件隊列上的請求最終要收集到這個硬件隊列上來，那么必然要加鎖，會比較影響性能]

mq-deadline調(diào)度器跟單隊列的deadline調(diào)度器發(fā)揮的功能很相似。它有個insert_request()函數(shù)，不會使用多個staging隊列，而是把請求放到兩個全局的基于時間的隊列中 - 一個放讀請求，一個放寫請求，先嘗試把該新請求與已經(jīng)存在的請求合并，如果合并不了，則把這個新請求放到隊列尾部。dispatch_request()函數(shù)會從這些隊列中返回第一個請求：基于時間的隊列，基于請求批大小，以及避免寫?zhàn)囸I的隊列。

bfq調(diào)度器，即Budget Fair Queueing, 一定程度上是借鑒cfq實現(xiàn)的。內(nèi)核里有介紹bfq的文檔(Documentation/block/bfq-iosched.txt)，幾年前l(fā)wn上有篇講bfq的文章（https://lwn.net/Articles/601799/），后來又出了一篇文章(https://lwn.net/Articles/709202/)，跟進(jìn)了bfq被吸納進(jìn)multi-queue的情況。bfq有一點比較像mq-deadline,沒有使用多個per-CPU staging隊列。bfq有多個隊列，每一個隊列由一把自旋鎖保護(hù)。

與mq-deadline和bfq不一樣，kyber IO調(diào)度器，在這篇文章中(https://lwn.net/Articles/720675/)有簡單介紹，它使用了per-CPU的staging隊列，也沒有實現(xiàn)自己的insert_request()函數(shù)，而用的是默認(rèn)行為。dispatch_request()函數(shù)為每一個硬件上下文都維護(hù)著各種內(nèi)部隊列，如果這些隊列是空的，它就會從給定的硬件上下文所對應(yīng)的所有staging隊列來收集請求，然后在內(nèi)部將請求做個分布，如果硬件隊列不是空的，它就直接從對應(yīng)的內(nèi)部隊列里下發(fā)請求。關(guān)于kyber調(diào)度器的這幾個方面內(nèi)核沒有相應(yīng)的注釋和文檔：策略解釋，請求分布，以及處理順序。

單隊列要壽終正寢了？

在塊層中，并存兩套不同的隊列系統(tǒng)，兩套調(diào)度器和兩套不同的驅(qū)動接口很明顯是不理想的。我們可以期待single-queue的代碼很快被移除掉嗎？multi-queue到底又有多好呢？

不幸的是，這些問題的回答需要在不同的硬件上做很多測試，而筆者只是個做軟件的。從軟件的角度來說，很清楚，在支持多隊列并行提交請求的硬件上，multi-queue應(yīng)該能帶來很多好處。當(dāng)用在單隊列硬件上時，multi-queue至少應(yīng)該和單隊列旗鼓相當(dāng)，但是不要期望一夜之間就能達(dá)到旗鼓相當(dāng)?shù)乃剑驗槿魏涡率挛锒疾皇峭昝赖摹?/p>

說到不完美，舉個例子，最近一個補丁集進(jìn)了Linux 4.15。這些補丁對mq-deadline調(diào)度器做了一些修改來解決redhat在內(nèi)部存儲系統(tǒng)測試中發(fā)現(xiàn)的性能問題。假如切換到multi-queue, 存儲領(lǐng)域的各家廠商很有可能在測試中發(fā)現(xiàn)類似的性能回退。在未來幾個月里，這些被發(fā)現(xiàn)的問題很有希望得到修復(fù)。2017可能不會成為multi-queue-ony Linux的一年，但是這樣的一天不會太遠(yuǎn)。