BFQ (Budget Fair Queueing)

BFQ是一個比例份額I/O排程器，具有一些額外的低延遲能力。除了cgroups支援（blkio或io控制器）之外，BFQ的主要特性是

  • BFQ保證了高系統和應用程式響應性，以及時間敏感型應用程式（如音訊或影片播放器）的低延遲；

  • BFQ在程序或組之間分配頻寬，而不僅僅是時間（在需要保持高吞吐量時切換回時間分配）。

在其預設配置中，BFQ優先考慮延遲而不是吞吐量。因此，當需要實現更低的延遲時，BFQ構建的排程可能會導致更低的吞吐量。如果對於給定的裝置，您的主要或唯一目標是在任何時候都實現儘可能高的吞吐量，那麼請透過將low_latency設定為0來關閉該裝置的所有低延遲啟發式。有關如何配置BFQ以實現延遲和吞吐量之間的期望折衷，或如何最大化吞吐量的詳細資訊，請參見第3節。

與每個I/O排程器一樣，BFQ會增加每個I/O請求處理的一些開銷。為了給出這種開銷的概念，BFQ的總的、單鎖保護的、每個請求的處理時間---即請求插入、排程和完成鉤子的執行時間之和---例如，在Intel Core i7-2760QM@2.40GHz上是1.9 us（筆記型電腦的舊CPU；使用簡單的程式碼檢測以及S套件[1]的throughput-sync.sh指令碼在效能分析模式下進行測量）。為了將此結果放入上下文中，blk-mq中最輕量級的I/O排程器mq-deadline的總的、單鎖保護的、每個請求的執行時間為0.7 us（mq-deadline約為800 LOC，而BFQ約為10500 LOC）。

排程開銷進一步限制了CPU可以處理的最大IOPS（已經受到其餘I/O堆疊執行的限制）。為了給出BFQ限制的概念，在速度較慢或一般的CPU上，以下是三種不同CPU上BFQ的限制，分別是在一臺普通的筆記型電腦、一臺舊桌上型電腦和一個廉價的嵌入式系統上，如果啟用了完全分層支援（即設定了CONFIG_BFQ_GROUP_IOSCHED），但未設定CONFIG_BFQ_CGROUP_DEBUG（第4-2節）： - Intel i7-4850HQ：400 KIOPS - AMD A8-3850：250 KIOPS - ARM CortexTM-A53八核：80 KIOPS

如果設定了CONFIG_BFQ_CGROUP_DEBUG（當然也啟用了完全分層支援），那麼BFQ的可持續吞吐量會降低，因為建立和更新了所有blkio.bfq*統計資訊（第4-2節）。對於BFQ，這導致以下最大可持續吞吐量，與上述相同的系統上： - Intel i7-4850HQ：310 KIOPS - AMD A8-3850：200 KIOPS - ARM CortexTM-A53八核：56 KIOPS

BFQ也適用於多佇列裝置。

1. BFQ在什麼情況下可能有用？

BFQ在個人和伺服器系統上提供以下好處。

1-1 個人系統

互動式應用程式的低延遲

無論實際的後臺工作負載如何，BFQ都能保證，對於互動式任務，儲存裝置的響應速度幾乎與空閒時一樣。例如，即使正在執行以下一個或多個後臺工作負載

  • 正在讀取、寫入或複製一個或多個大型檔案，

  • 正在編譯原始碼樹，

  • 一個或多個虛擬機器正在執行I/O，

  • 軟體更新正在進行中，

  • 索引守護程式正在掃描檔案系統並更新其資料庫，

啟動應用程式或從應用程式中載入檔案所花費的時間與儲存裝置空閒時大致相同。作為比較，使用CFQ、NOOP或DEADLINE，在相同條件下，應用程式會遇到高延遲，甚至變得無響應，直到後臺工作負載終止（即使在SSD上也是如此）。

軟即時應用程式的低延遲

軟即時應用程式（如音訊和影片播放器/流媒體）也可以享受低延遲和低丟包率，而與後臺I/O工作負載無關。因此，這些應用程式幾乎不會受到後臺工作負載引起的任何故障的影響。

更快的程式碼開發任務速度

如果碰巧並行執行一些額外的工作負載，那麼BFQ執行的典型程式碼開發任務（編譯、檢出、合併等）的I/O相關元件比CFQ、NOOP或DEADLINE快得多。

高吞吐量

在硬碟上，BFQ的吞吐量比CFQ高出30％，比DEADLINE和NOOP高出150％，這包括我們測試中考慮的所有順序工作負載。對於隨機工作負載以及基於快閃記憶體的裝置上的所有工作負載，BFQ的吞吐量與其他排程器大致相同。

強大的公平性、頻寬和延遲保證

BFQ根據I/O密集型應用程式的權重比例分配裝置吞吐量，而不僅僅是裝置時間，適用於任何工作負載，並且與裝置引數無關。透過一個簡單的公式，可以根據這些頻寬保證計算出嚴格的每個I/O請求的延遲保證。如果未配置為嚴格的服務保證，BFQ會切換到基於時間的資源共享（僅）用於那些會導致吞吐量損失的應用程式。

1-2 伺服器系統

伺服器系統的大多數好處都來自與上述相同的服務屬性。特別是，無論是否正在提供額外的（可能是繁重的）工作負載，BFQ都能保證

  • 音訊和影片流的抖動和丟包率非常低或為零；

  • 快速檢索WEB頁面和嵌入式物件；

  • 即時記錄即時轉儲應用程式中的資料（例如，資料包日誌記錄）；

  • 伺服器的本地和遠端訪問的響應速度。

2. BFQ如何工作？

BFQ是一個比例份額I/O排程器，其通用結構和大量程式碼都借用自CFQ。

  • 在裝置上執行I/O的每個程序都與權重和一個(bfq_)queue相關聯。

  • BFQ在一段時間內授予佇列（程序）對裝置的獨佔訪問權，並透過將每個佇列與預算（以扇區數衡量）相關聯來實現此服務模型。

    • 在佇列被授予對裝置的訪問許可權後，每次請求排程時，佇列的預算都會減少，減少量為請求的大小。

    • 只有在發生以下事件之一時，才會使服務中的佇列過期，即暫停其服務：1）佇列用完預算，2）佇列為空，3）觸發“預算超時”。

      • 預算超時可防止執行隨機I/O的程序持有裝置太長時間並大大降低吞吐量。

      • 實際上，與CFQ中一樣，與發出同步請求的程序關聯的佇列在為空時可能不會立即過期。相反，BFQ可能會使裝置空閒一小段時間間隔，如果該程序及時發出新請求，則使其有機會繼續獲得服務。如果程序執行同步和順序I/O，則裝置空閒通常會提高旋轉裝置和非排隊快閃記憶體裝置的吞吐量。此外，在BFQ下，裝置空閒還有助於保證程序發出同步請求的預期吞吐量分數（有關此文件中slice_idle可調引數的描述，或[1, 2]中的更多詳細資訊）。

        • 關於保證服務保證的空閒，如果多個程序同時爭用裝置，但所有程序和組的權重相同，那麼BFQ保證預期的吞吐量分配，而無需使裝置空閒。因此，在這種常見情況下，吞吐量儘可能高。

      • 在具有內部命令排隊的基於快閃記憶體的儲存（通常為NCQ）上，裝置空閒始終對吞吐量有害。因此，對於這些裝置，BFQ僅在嚴格需要保證服務的情況下執行空閒，即為了保證低延遲或公平性。在這些情況下，整體吞吐量可能不是最優的。目前沒有解決方案可以在具有內部排隊的裝置上提供強大的服務保證和最佳吞吐量。

    • 如果啟用了低延遲模式（預設配置），BFQ會執行一些特殊的啟發式方法來檢測互動式和軟即時應用程式（例如，影片或音訊播放器/流媒體），並降低它們的延遲。為實現此目標而採取的最重要措施是，使與這些應用程式關聯的佇列獲得超過其公平份額的裝置吞吐量。為簡潔起見，我們將BFQ為優先處理這些佇列而採取的整套措施稱為“權重提升”。特別是，BFQ為互動式應用程式提供較溫和形式的權重提升，為軟即時應用程式提供更強的形式。

    • BFQ會自動停用在佇列建立突發中出生的佇列的空閒。實際上，這些佇列通常與主要受益於高吞吐量的應用程式和服務的程序相關聯。例如，啟動時的systemd或git grep。

    • 與CFQ一樣，BFQ合併執行交錯I/O的佇列，即如果合併，則執行隨機I/O，該I/O變得主要是順序的。與CFQ不同，BFQ透過一種更具反應性的機制來實現此目標，該機制稱為早期佇列合併（EQM）。EQM在檢測交錯I/O（協作程序）方面非常靈敏，從而使BFQ可以透過佇列合併來實現高吞吐量，即使對於CFQ需要一種不同的機制（搶佔）來獲得高吞吐量的佇列也是如此。因此，EQM是一種用於透過交錯I/O實現高吞吐量的統一機制。

    • 根據WF2Q+的一種變體（名為B-WF2Q+）排程佇列，並使用增強的rb樹來實現，以保留O（log N）的整體複雜度。有關更多詳細資訊，請參見[2]。B-WF2Q+也已準備好進行分層排程，詳細資訊請參見第4節。

    • B-WF2Q+保證了相對於理想、完全公平和流暢服務的嚴格偏差。特別是，B-WF2Q+保證每個佇列都獲得與其權重成比例的裝置吞吐量的一部分，即使吞吐量波動，並且與以下因素無關：裝置引數、當前工作負載和分配給佇列的預算。

    • 最後一個預算獨立屬性（儘管最初可能違反直覺）絕對是有益的，原因如下

      • 首先，對於任何比例份額排程器，相對於理想服務的最大偏差都與分配給佇列的最大預算（切片）成正比。因此，BFQ可以保持這種偏差嚴格，不僅因為B-WF2Q+的準確服務，還因為BFQ不需要為佇列分配更大的預算，以使該佇列獲得裝置吞吐量的更大部分。

      • 其次，BFQ可以自由地為每個程序（佇列）選擇最適合程序需求的預算，或最能利用程序的I/O模式。特別是，BFQ使用簡單的反饋迴圈演算法更新佇列預算，該演算法可以實現高吞吐量，同時仍為時間敏感型應用程式提供嚴格的延遲保證。當服務中的佇列過期時，該演算法將計算佇列的下一個預算，以便

        • 最終將較大的預算分配給與執行順序I/O的I/O密集型應用程式關聯的佇列：實際上，這些應用程式在獲得對裝置的訪問許可權後，被服務的時間越長，吞吐量就越高。

        • 最終將較小的預算分配給與時間敏感型應用程式關聯的佇列（這些應用程式通常執行零星和短I/O），因為等待服務的佇列的預算越小，B-WF2Q+服務該佇列的時間就越早（[2]中的Subsec 3.3）。

  • 如果多個程序同時爭用裝置，但所有程序和組的權重相同，那麼BFQ保證預期的吞吐量分配，而無需使裝置空閒。而是使用搶佔。然後在這種常見情況下，吞吐量會高得多。

  • ioprio類以嚴格的優先順序順序提供服務，即只要有較高優先順序的佇列，較低優先順序的佇列就不會獲得服務。在同一類佇列中，頻寬的分配與每個佇列的權重成比例。但是，為了防止空閒類餓死，保證了非常小的額外頻寬。

3. BFQ的可調引數是什麼？如何正確配置BFQ？

大多數BFQ可調引數都會影響服務保證（基本上是延遲和公平性）和吞吐量。有關如何選擇服務保證和吞吐量之間的期望折衷的完整詳細資訊，請參見引數slice_idle、strict_guarantees和low_latency。有關如何最大化吞吐量的詳細資訊，請參見slice_idle、timeout_sync和max_budget。其他與效能相關的引數是從CFQ繼承而來，並且主要為了與CFQ的相容性而保留。到目前為止，尚未報告在BFQ中更改後者的引數會帶來任何效能改進。

特別是，以下可調引數back_seek-max、back_seek_penalty、fifo_expire_async和fifo_expire_sync與CFQ中的相同。它們的描述只是從CFQ中複製而來。slice_idle描述中的一些考慮事項也從CFQ中複製而來。

每個程序的ioprio和權重

除非使用cgroups介面（請參閱“4. BFQ組排程”），否則只能透過I/O優先順序間接將權重分配給程序，並且根據以下關係：weight =（IOPRIO_BE_NR - ioprio）* 10。

請注意，如果設定了low-latency，則BFQ會自動提高與互動式和軟即時應用程式關聯的佇列的權重。如果您需要/想要控制權重，請取消設定此可調引數。

slice_idle

此引數指定當某些同步BFQ佇列變為空時，BFQ應為下一個I/O請求空閒多長時間。預設情況下，slice_idle是一個非零值。空閒有兩個目的：提高吞吐量並確保尊重期望的吞吐量分配（請參見BFQ的工作方式的描述，如果需要，請參閱此處引用的論文）。

至於吞吐量，空閒對於像單軸SATA / SAS磁碟這樣的高尋道介質非常有用，在這些磁碟上，我們可以減少總體尋道次數，並看到吞吐量提高。

將slice_idle設定為0將刪除佇列上的所有空閒，並且在更快的儲存裝置（如硬體RAID配置中的多個SATA / SAS磁碟）以及具有內部命令排隊（和並行性）的基於快閃記憶體的儲存上，應該會看到整體吞吐量提高。

因此，根據儲存和工作負載的不同，將slice_idle = 0可能很有用。通常，對於SATA / SAS磁碟和SATA / SAS磁碟的軟體RAID，保持slice_idle啟用應該很有用。對於任何在單個LUN後面具有多個軸的配置（基於主機的硬體RAID控制器或儲存陣列）或具有基於快閃記憶體的快速儲存的配置，將slice_idle = 0可能會導致更好的吞吐量和可接受的延遲。

但是，如果存在差異化的權重或差異化的I/O請求長度，則空閒對於強制實施服務保證是必要的。要了解原因，請假設給定的BFQ佇列A必須為每個為另一個佇列B服務的請求提供多個I/O請求。空閒確保，如果A在變為空之後不久就提出了新的I/O請求，則不會在中間排程B的請求，因此A不會失去在排程B的下一個請求之前排程多個請求的可能性。請注意，空閒僅在I/O請求排程的範圍內保證佇列的期望差異化處理。要保證實際的服務順序隨後與排程順序對應，還必須設定strict_guarantees可調引數。

空閒也有一個重要的不利方面：除了上述對吞吐量也有益的情況外，空閒可能會嚴重影響吞吐量。一個重要的情況是隨機工作負載。由於此問題，BFQ傾向於儘可能避免空閒，因為它對吞吐量也沒有好處（如第2節所述）。由於這種行為，以及為strict_guarantees可調引數描述的其他問題，短期服務保證可能會偶爾被違反。並且，在某些情況下，這些保證可能比保證最大吞吐量更重要。例如，在影片播放/流式傳輸中，非常低的丟包率可能比最大吞吐量更重要。在這些情況下，請考慮設定strict_guarantees引數。

slice_idle_us

以微秒為單位控制與slice_idle相同的調整引數。可以使用任一可調引數來設定空閒行為。之後，另一個可調引數將在sysfs中反映新設定的值。

strict_guarantees

如果設定了此引數（預設：未設定），則BFQ

  • 始終在服務中的佇列變為空時執行空閒；

  • 強制裝置一次提供一個I/O請求，僅在沒有未完成請求的情況下才排程新請求。

在存在差異化權重或I/O請求大小的情況下，需要上述兩個條件才能保證每個BFQ佇列都獲得其分配的頻寬份額。第一個條件是出於slice_idle可調引數描述中解釋的原因而需要的。第二個條件是必需的，因為所有現代儲存裝置都會在內部對已排隊的請求進行重新排序，這可能會輕易破壞I/O排程器強制執行的服務保證。

設定strict_guarantees顯然可能會影響吞吐量。

back_seek_max

這以KB為單位指定了向後尋道的最大“距離”。該距離是從當前磁頭位置到向後扇區的空間量。

此引數允許排程器預測“向後”方向的請求，如果它們在距當前磁頭位置的此距離內，則將其視為“下一個”。

back_seek_penalty

此引數用於計算向後尋道的成本。如果請求的向後距離僅為距“前”請求的1 / back_seek_penalty，則兩個請求的尋道成本被認為是等效的。

因此，排程程式不會偏向一個或另一個請求（否則排程程式將偏向前端請求）。back_seek_penalty的預設值為2。

fifo_expire_async

此引數用於設定非同步請求的超時。此引數的預設值為250ms。

fifo_expire_sync

此引數用於設定同步請求的超時。此引數的預設值為125ms。如果需要優先於非同步請求的同步請求，則應相對於fifo_expire_async減小此值。

low_latency

此引數用於啟用/停用BFQ的低延遲模式。預設情況下，啟用低延遲模式。如果啟用，則互動式和軟即時應用程式將被優先處理，並且體驗到較低的延遲，如BFQ的工作方式的描述中所述。

如果您需要完全控制頻寬分配，請停用此模式。實際上，如果啟用此模式，BFQ會自動增加特權應用程式的頻寬份額，這是保證它們較低延遲的主要手段。

此外，如本文件開頭所述，如果您的唯一目標是實現高吞吐量，請停用此模式。實際上，優先處理某些應用程式的I/O而不是其他應用程式可能會導致較低的吞吐量。要在非旋轉裝置上實現儘可能高的吞吐量，可能還需要將slice_idle設定為0（以放棄對公平性和低延遲的任何嚴格保證為代價）。

timeout_sync

一旦選擇了要服務的任務（佇列），可以分配給它的最大裝置時間量。在尋道成本很高的裝置上，增加此時間通常會增加最大吞吐量。另一方面，增加此時間會粗化短期頻寬和延遲保證的粒度，尤其是在以下引數設定為零的情況下。

max_budget

一旦BFQ佇列投入服務，就可以為其提供的最大服務量（以扇區衡量）（當然在上述超時限制內）。根據演算法描述中所述，較大的值會根據發出的順序I/O請求的百分比來提高吞吐量。較大值的代價是它們粗化了短期頻寬和延遲保證的粒度。

預設值為0，這啟用了自動調整：BFQ根據估計的峰值速率將max_budget設定為timeout_sync期間可以服務的最大扇區數。

對於某些特定裝置，一些使用者偶爾報告透過顯式設定max_budget來達到更高的吞吐量，也就是說，透過將max_budget設定為高於BFQ透過自動調整設定的值。特別是，他們已將max_budget設定為高於BFQ透過自動調整將設定的值。實現此目標的另一種方法是僅增加timeout_sync的值，而將max_budget設定為0。

4. BFQ的組排程

BFQ支援cgroups-v1和cgroups-v2 io控制器，即blkio和io。特別是，BFQ支援基於權重的比例份額。要啟用cgroups支援，請設定BFQ_GROUP_IOSCHED。

4-1 提供的服務保證

對於BFQ，比例份額是指裝置頻寬的真實比例份額，具體取決於組權重。例如，權重為200的組獲得的頻寬是權重為100的組的兩倍，而不僅僅是兩倍的時間。

BFQ支援任何深度的層次結構（組樹）。頻寬以預期的方式在組和程序之間分配：對於每個組，該組的子組按其權重的比例共享該組的全部頻寬。特別是，這意味著，對於每個葉組，除非修改程序的ioprio，否則該組的每個程序都收到該組的全部頻寬的相同份額。

如果為組提供頻寬保證會過多地降低吞吐量，則組的資源共享保證可能會部分或完全從頻寬切換到時間。此切換是在每個程序的基礎上進行的：如果葉組的一個程序如果以接收其頻寬份額的方式提供服務會導致吞吐量損失，則BFQ會切換回僅對該程序基於時間的比例份額。

4-2 介面

要使BFQ獲得給定裝置的頻寬的比例共享，BFQ當然必須是該裝置的活動排程器。

在每個組目錄中，與BFQ特定的cgroup引數和統計資訊關聯的檔案的名稱以“bfq。”字首開頭。因此，使用cgroups-v1或cgroups-v2，BFQ特定檔案的完整字首是“blkio.bfq。”或“io.bfq。” 例如，用於使用BFQ設定組權重的組引數是blkio.bfq.weight或io.bfq.weight。

至於cgroups-v1（blkio控制器），建立並由bfq保持最新的stat檔案的確切集取決於是否設定了CONFIG_BFQ_CGROUP_DEBUG。如果設定了該選項，則bfq會建立塊IO控制器中記錄的所有stat檔案。相反，如果未設定CONFIG_BFQ_CGROUP_DEBUG，則bfq僅建立以下檔案

blkio.bfq.io_service_bytes
blkio.bfq.io_service_bytes_recursive
blkio.bfq.io_serviced
blkio.bfq.io_serviced_recursive

CONFIG_BFQ_CGROUP_DEBUG的值會極大地影響bfq的可持續最大吞吐量，因為更新blkio.bfq。* 統計資訊非常昂貴，特別是對於CONFIG_BFQ_CGROUP_DEBUG啟用的某些統計資訊。

引數

對於每個組，可以設定以下引數

weight

這指定了cgroup在其父級內部的預設權重。可用值：1..1000（預設值：100）。

對於cgroup v1，透過將值寫入blkio.bfq.weight來設定它。

對於cgroup v2，透過將值寫入io.bfq.weight來設定它。（帶有可選的default字首和空格）。

在可調部分開頭描述的ioprio和權重之間的線性對映仍然有效，但是所有高於IOPRIO_BE_NR * 10的權重都將對映到ioprio 0。

請記住，如果設定了low-latency，則BFQ會自動提高與互動式和軟即時應用程式關聯的佇列的權重。如果您需要/想要控制權重，請取消設定此可調引數。

weight_device

這指定了cgroup的每個裝置權重。語法為minor:major weight。權重0可用於重置為預設權重。

對於cgroup v1，透過將值寫入blkio.bfq.weight_device來設定它。

對於cgroup v2，檔名為io.bfq.weight。

[1]

P. Valente，A。Avanzini，“BFQ儲存I/O排程器的發展”，第一屆移動系統技術研討會（MST-2015）論文集，2015年5月。

http://algogroup.unimore.it/people/paolo/disk_sched/mst-2015.pdf

[2]

P. Valente和M. Andreolini，“使用BFQ磁碟I/O排程器提高應用程式響應能力”，第5屆年度國際系統和儲存會議（SYSTOR '12）論文集，2012年6月。

略有擴充套件的版本

http://algogroup.unimore.it/people/paolo/disk_sched/bfq-v1-suite-results.pdf

[3]

https://github.com/Algodev-github/S