歡迎光臨
每天分享高質量文章

塊層介紹 第二篇: request層

原文鏈接:https://lwn.net/Articles/738449

摘要: 本文翻譯自Neil Brown發表在LWN上的兩篇介紹塊層的文章。Neil是前MD RAID的maintainer,他通過這兩篇文章,提綱契領地描繪了塊層的主脈絡。

Linux 塊層向上為檔案系統和塊設備提交接口,使得上層能夠以統一的方式訪問各種型別的後端儲存設備。同時,它也向下為設備驅動提供接口,讓驅動層能夠以一致的方式來接受請求。一些驅動如上一篇文章中提到的DRBD和RBD設備,只使用bio層提供的一些接口,對bio請求進行處理。其它的驅動則可以從IO請求plugging機制,各種請求排序和請求合併中受益。為了給驅動層提供服務,塊層做了不少事情,我且稱之為”request層”。

現在,”request層”並存著兩種模型:單佇列(single-queue) 和 多佇列(multi-queue)。多佇列的出現也就是近幾年的事情,也許總有一天會完全取代單佇列的,但是目前來看兩者在內核的使用都相當活躍。有了這兩種不同的排隊方法(queuing approach)做參考,我們就可以兩相對比來學習學習,所以我們將花點時間都看看,分析他們如何把請求呈現給驅動層的。首先,我們來看看兩者的共同之處,分析這兩個關鍵的結構體是個不錯的入手點: struct request_queue 和 struct request。

請求佇列和請求

struct request_queue之於struct request的關係,非常像struct gendisk之於struct bio的關係:一個代表具體的設備,一個代表IO請求。需要註意的是,每個gendisk都有一個關聯的request_queue結構體,但是只有那些使用了”request層”的設備才會分配request結構體。按理說,適用於所有塊設備的域,比如struct queue_limits,都應該放到gendisk結構體裡面,而對於一些僅適用於”request層”佇列管理的域,其實只應當分配給那些使用了”request層”的設備。現在來看,這些結構體里有些域的安排可能就是歷史巧合,也不值得去糾正了。各種佇列相關的域,都可以在/sys/block/*/queue/目錄下查看。

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

相應的make_request_fn()函式 (單佇列是blk_queue_bio,多佇列是blk_mq_make_request())為IO請求創建一個request結構體,然後把交給IO調度器, 也叫電梯演算法”elevator”, 這個名字來自電梯演算法( elevator algorithm),電梯演算法曾是磁盤IO調度一個裡程碑式的成就。我們將快速看一下單佇列的實現,然後再對比地去看多佇列。

單佇列上的請求調度

過去,大多儲存設備都是機械硬碟,要通過磁頭尋道,盤片旋轉來定位資料。機械盤一次只能處理一個請求,從盤片上一個位置挪動到下一個位置代價很大。單佇列的實現就是為這種型別的設備而生的,然後漸漸地也能支持其它快速設備,然而單佇列整體結構依然反映了旋轉型別儲存設備的需求。

單佇列調度器主要有三個任務:

  • 積聚代表連續IO操作的多個bio,合併成更大的IO請求,充分發揮硬體性能,但是請求不能太大超高硬體設備的限制;

  • 把請求進行排序來減少尋道時間,但是又要保證重要的請求得到及時處理。不斷尋求較優方案,來解決這個問題,是這一部分代碼複雜度的根源。一般很難知道這兩點:一個請求有多重要,和一個請求需要多少尋道時間,我們只能依賴啟髮式方法來判斷怎樣排序比較好,然而啟髮式方法絕不是完美的;

  • 把經過整理的請求串列交給底層驅動,讓驅動從佇列取下請求去處理,同時提供一個通知機制來告訴上層請求處理的結果。

最後一個任務很直接了當。驅動會通過blk_init_queue_node()來註冊一個request_fn()策略例程,只要佇列上有新請求已經準備好,策略例程被呼叫去處理這個請求。驅動負責用blk_peek_request()來從佇列上取下請求,然後進行處理。當請求處理完畢 [有些設備可以並行處理多個請求],驅動會從佇列上摘下另一個請求來處理,而不用再去呼叫request_fn() [因為request_fn()一次拿到了整個串列上的所有request]。請求一旦處理完畢,就可呼叫blk_finish_request()來通知上層。

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

第二個任務可能是最複雜的。如何把請求按照”適當”順序排隊非常依賴我們如何來解釋”適當”的含義。這三種不同的單佇列調度器: noop, deadline和cfq,對“適當”的解釋就非常不一樣。

  • “noop”會對請求做一些簡單的排序,不允許把讀請求挪到寫請求之前,反之亦然;依據電梯演算法,一個同型別的請求可以插入到另一個之前。除了elv_dispatch_sort()所做簡單排序,”noop”就是一個FIFO佇列。

  • “deadline”會把提交時間相近的請求放在一批。在同一批中,請求會被排序。當一批請求達到了大小上限或著定時器超時,這批請求就會提交到設備佇列上去。這個演算法嘗試給每一個請求都設置一個延遲時間上限,同時儘量聚集比較大的一批請求。

  • “cfq”即”Complete Fairness Queuing”,相比其它幾個調度器要複雜很多,目的是在不同行程或行程組間保證IO資源使用的公平性。cfq調度器內部維護了多個佇列,每一個行程都有一個佇列來儲存來自該行程的同步請求(通常是讀),而對於異步請求(通常是寫),每一個優先級都有一個佇列,所有請求不論來自哪個行程都按照優先級放到相應的佇列上。在提交請求時,按照優先級每個佇列都有機會得到調度。每個佇列都有一定的時間片,在時間片內才能提交一定數量的請求。當一個同步佇列中的請求不足一定數量時,這個設備可以空閑一會,即使其它佇列里可能有請求等待處理。通常,同步請求之間在磁盤上的物理位置是連續的,所以讓磁盤稍等一會來接收更多連續的請求,這樣做可以提高吞吐量。以上對CFQ的描述僅僅是點皮毛。內核文件(Documentation/block/cfq-iosched.txt)講的更詳細點,還列出了所有引數,通過調整這些引數能夠適應各種不同的場景。

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

一個設備內部可以通過真正地並行處理請求,來支持被標記的命令,比如通過訪問一個記憶體快取,通過設計多模塊而每個模塊都能處理一個請求,或者通過其內部佇列,這樣的佇列比”request層”更加瞭解設備。

多佇列和多CPU

多佇列的另一個動機就是減少鎖的開銷,因為我們的系統處理器越來越多,而請求從多個處理器放到一個佇列中時需要加鎖,鎖的開銷變得越來越大。”plugging”機制能幫得上一些忙,但是不夠理想。如果我們能夠分配更多佇列:每個NUMA節點一個佇列,或者一個CPU一個佇列,那麼把請求放到佇列的鎖開銷就會減少很多。如果硬體支持並行處理多個請求,那麼這樣做的優勢就更大了。如果硬體只支持一次提交一個請求,那麼多個per-CPU佇列仍然需要合併。如果他們比”plugging”機制批處理的效果更好,那麼這樣做也是有益處的。假如不能提高批處理的效果,寫程式的時候小心點應該也能夠保證,至少不會有什麼損失。

之前說過,cfq調度器內部已經有多個佇列,但是它們跟multi-queue的目的完全不一樣,它們把請求與行程和優先級關聯起來,而multi-queue的佇列是跟硬體密切相關的。multi-queue “request層”維護著兩組硬體相關的佇列:軟體的”staging”佇列和硬體的”dispatch”佇列。

軟體staging佇列(struct blk_mq_ctx)是依CPU硬體情況而分配的,每個CPU分配一個,或每個NUMA節點分配一個。當塊層的”plugging”機制拔開”塞子”時(blk_mq_flush_plug_list()),request請求在一個spinlock的保護下被添加到佇列上,鎖競爭應該很少。multi-queue的佇列可以選擇由某一個multi-queue調度器來管理, 現在有三種multi-queue調度器:bfq, kyber和mq-deadline.

硬體dispatch佇列是基於標的硬體塊設備進行分配的,所以有可能只有一個,也有可能多達2048個佇列 (或與硬體支持的中斷源個數一樣)。”request層”為每一個硬體佇列(或”硬體背景關係”)分配一個資料結構struct blk_mq_hw_ctx,維護著一個CPU和佇列之間的映射表,而佇列本身就是為底層驅動而服務的。“request 層”時不時地把硬體佇列中的請求傳遞給底層驅動。接下來,請求就全由驅動處理了,通常情況下,又會很快按照接收的順序交給硬體。

與single-queue相比有另一個重要區別,multi-queue使用的request結構體都是預分配的。每個request結構體都關聯著一個不同tag number,這個tag number會隨著請求傳遞到硬體,再隨著請求完成通知傳遞迴來。早點為一個請求分配tag number,在時機到來的時候,request 層可隨時向底層發送請求。

single-queue只需要一個request_fn()就可以了,但是multi-queue需要底層驅動提供一個struct blk_mq_ops結構體,包含了多達11個函式。其中,最核心的一個函式是queue_rq(),其它的函式實現了超時,請求完成輪詢,請求初始化,等類似操作。

一旦請求就緒,並且調度器不想再把請求保持在佇列上來排序或擴展,調度器就會呼叫queue_rq()函式。single-queue把收集請求的責任交給了驅動層,與之不同,multi-queue卻把這個責任交給了”request層”。queue_rq()有個引數代表的是硬體背景關係,通常會把請求放在內部FIFO佇列上,也有可能會直接處理。queue_rq()可以拒絕一個請求,然後傳回BLK_STS_RESOURCE,讓請求繼續在staging佇列上等待。除了BLK_STS_RESOURCE和BLK_STS_OK,其它傳回值都被視為IO錯誤。

多佇列調度

multi-queue不是必須要配置一個調度器,如果不指定的話,那麼就會用類似單佇列中的“noop”調度器。連續的bio會被合併到一個請求,而不連續的bio各成為一個獨立的請求。這些請求以FIFO的順序被放到staging佇列中,儘管有多個submission佇列,預設的調度器會嘗試直接提交新請求,僅僅在收到BLK_STS_RESOURCE傳回值時才會使用staging佇列。當塊設備上的plugging機制拔開“塞子”時,調度器會呼叫blk_mq_run_hw_queue()或blk_mq_delay_run_hw_queue()把軟體佇列傳遞給驅動層處理。

可插拔的multi-queue調度器有22個入口點,其中有兩個函式,一個是insert_requests()把一組請求添加到軟體staging佇列中,另一個是dispatch_request()會選擇一個請求然後傳遞給硬體設備。如果沒有實現insert_request()函式,請求就會被簡單的插入到串列末尾。如果沒有提供dispatch_request()函式,就會從staging佇列里取下請求,然後以任意順序傳遞到相應的硬體佇列。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調度器跟單佇列的deadline調度器發揮的功能很相似。它有個insert_request()函式,不會使用多個staging佇列,而是把請求放到兩個全域性的基於時間的佇列中 – 一個放讀請求,一個放寫請求,先嘗試把該新請求與已經存在的請求合併,如果合併不了,則把這個新請求放到佇列尾部。dispatch_request()函式會從這些佇列中傳回第一個請求:基於時間的佇列,基於請求批大小,以及避免寫饑餓的佇列。

bfq調度器,即Budget Fair Queueing, 一定程度上是借鑒cfq實現的。內核里有介紹bfq的文件(Documentation/block/bfq-iosched.txt),幾年前lwn上有篇講bfq的文章(https://lwn.net/Articles/601799/),後來又出了一篇文章(https://lwn.net/Articles/709202/), 跟進了bfq被吸納進multi-queue的情況。bfq有一點比較像mq-deadline,沒有使用多個per-CPU staging佇列。bfq有多個佇列,每一個佇列由一把自旋鎖保護。

與mq-deadline和bfq不一樣,kyber IO調度器,在這篇文章中(https://lwn.net/Articles/720675/)有簡單介紹,它使用了per-CPU的staging佇列,也沒有實現自己的insert_request()函式,而用的是預設行為。dispatch_request()函式為每一個硬體背景關係都維護著各種內部佇列,如果這些佇列是空的,它就會從給定的硬體背景關係所對應的所有staging佇列來收集請求,然後在內部將請求做個分佈,如果硬體佇列不是空的,它就直接從對應的內部佇列里下發請求。關於kyber調度器的這幾個方面內核沒有相應的註釋和文件:策略解釋,請求分佈,以及處理順序。

單佇列要壽終正寢了?

在塊層中,並存兩套不同的佇列系統,兩套調度器和兩套不同的驅動接口很明顯是不理想的。我們可以期待single-queue的代碼很快被移除掉嗎?multi-queue到底又有多好呢?

不幸的是,這些問題的回答需要在不同的硬體上做很多測試,而筆者只是個做軟體的。從軟體的角度來說,很清楚,在支持多佇列並行提交請求的硬體上,multi-queue應該能帶來很多好處。當用在單佇列硬體上時,multi-queue至少應該和單佇列旗鼓相當,但是不要期望一夜之間就能達到旗鼓相當的水平,因為任何新事物都不是完美的。

說到不完美,舉個例子,最近一個補丁集進了Linux 4.15。這些補丁對mq-deadline調度器做了一些修改來解決redhat在內部儲存系統測試中發現的性能問題。假如切換到multi-queue, 儲存領域的各家廠商很有可能在測試中發現類似的性能回退。在未來幾個月里,這些被髮現的問題很有希望得到修複。2017可能不會成為multi-queue-ony Linux的一年,但是這樣的一天不會太遠。

赞(0)

分享創造快樂