深度剖析基于塊層的組成“request層”

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

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

請(qǐng)求隊(duì)列和請(qǐng)求

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

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

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

單隊(duì)列上的請(qǐng)求調(diào)度

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

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

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

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

把經(jīng)過(guò)整理的請(qǐng)求列表交給底層驅(qū)動(dòng)，讓驅(qū)動(dòng)從隊(duì)列取下請(qǐng)求去處理，同時(shí)提供一個(gè)通知機(jī)制來(lái)告訴上層請(qǐng)求處理的結(jié)果。

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

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

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

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

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

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

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

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

多隊(duì)列和多CPU

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

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

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

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

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

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

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

多隊(duì)列調(diào)度

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

可插拔的multi-queue調(diào)度器有22個(gè)入口點(diǎn)，其中有兩個(gè)函數(shù)，一個(gè)是insert_requests()把一組請(qǐng)求添加到軟件staging隊(duì)列中，另一個(gè)是dispatch_request()會(huì)選擇一個(gè)請(qǐng)求然后傳遞給硬件設(shè)備。如果沒(méi)有實(shí)現(xiàn)insert_request()函數(shù)，請(qǐng)求就會(huì)被簡(jiǎn)單的插入到列表末尾。如果沒(méi)有提供dispatch_request()函數(shù)，就會(huì)從staging隊(duì)列里取下請(qǐng)求，然后以任意順序傳遞到相應(yīng)的硬件隊(duì)列。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.[最后一句我理解不到那個(gè)點(diǎn)，大致理解是說(shuō)staging隊(duì)列有多個(gè)，硬件隊(duì)列只有一個(gè)的情況，那么多個(gè)軟件隊(duì)列上的請(qǐng)求最終要收集到這個(gè)硬件隊(duì)列上來(lái)，那么必然要加鎖，會(huì)比較影響性能]

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

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

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

單隊(duì)列要壽終正寢了？

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

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

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