Linux系統基礎知識：IO排程
IO排程發生在Linux核心的IO排程層。這個層次是針對Linux的整體IO層次體系來說的。從read()或者write()系統呼叫的角度來說，Linux整體IO體系可以分為七層，它們分別是：
VFS層：虛擬檔案系統層。由於核心要跟多種檔案系統打交道，而每一種檔案系統所實現的資料結構和相關方法都可能不盡相同，所以，核心抽象了這一層，專門用來適配各種檔案系統，並對外提供統一操作介面。
檔案系統層：不同的檔案系統實現自己的操作過程，提供自己特有的特徵，具體不多說了，大家願意的話自己去看程式碼即可。
頁快取層：負責真對page的快取。
通用塊層：由於絕大多數情況的io操作是跟塊裝置打交道，所以Linux在此提供了一個類似vfs層的塊裝置操作抽象層。下層對接各種不同屬性的塊裝置，對上提供統一的Block IO請求標準。
IO排程層：因為絕大多數的塊裝置都是類似磁碟這樣的裝置，所以有必要根據這類裝置的特點以及應用的不同特點來設定一些不同的排程演算法和佇列。以便在不同的應用環境下有針對性的提高磁碟的讀寫效率，這裡就是大名鼎鼎的Linux電梯所起作用的地方。針對機械硬碟的各種排程方法就是在這實現的。
塊裝置驅動層：驅動層對外提供相對比較高階的裝置操作介面，往往是C語言的，而下層對接裝置本身的操作方法和規範。
塊裝置層：這層就是具體的物理裝置了，定義了各種真對裝置操作方法和規範。
有一個已經整理好的Linux IO結構圖，非常經典，一圖勝千言：
我們今天要研究的內容主要在IO排程這一層。它要解決的核心問題是，如何提高塊裝置IO的整體效能?這一層也主要是針對機械硬碟結構而設計的。眾所周知，機械硬碟的儲存介質是磁碟，磁頭在碟片上移動進行磁軌定址，行為類似播放一張唱片。這種結構的特點是，順序訪問時吞吐量較高，但是如果一旦對碟片有隨機訪問，那麼大量的時間都會浪費在磁頭的移動上，這時候就會導致每次IO的響應時間變長，極大的降低IO的響應速度。磁頭在碟片上尋道的操作，類似電梯排程，如果在尋道的過程中，能把順序路過的相關磁軌的資料請求都“順便”處理掉，那麼就可以在比較小影響響應速度的前提下，提高整體IO的吞吐量。這就是我們問什麼要設計IO排程演算法的原因。在最開始的時期，Linux把這個演算法命名為Linux電梯演算法。
目前在核心中預設開啟了三種演算法，其實嚴格算應該是兩種，因為第一種叫做noop，就是空操作排程演算法，也就是沒有任何排程操作，並不對io請求進行排序，僅僅做適當的io合併的一個fifo佇列。
目前核心中預設的排程演算法應該是cfq，叫做完全公平佇列排程。這個排程演算法人如其名，它試圖給所有程序提供一個完全公平的IO操作環境。它為每個程序建立一個同步IO排程佇列，並預設以時間片和請求數限定的方式分配IO資源，以此保證每個程序的IO資源佔用是公平的，cfq還實現了針對程序級別的優先順序排程，這個我們後面會詳細解釋。
檢視和修改IO排程演算法的方法是：
cfq是通用伺服器比較好的IO排程演算法選擇，對桌面使用者也是比較好的選擇。但是對於很多IO壓力較大的場景就並不是很適應，尤其是IO壓力集中在某些程序上的場景。因為這種場景我們需要更多的滿足某個或者某幾個程序的IO響應速度，而不是讓所有的程序公平的使用IO，比如資料庫應用。
deadline排程(最終期限排程)就是更適合上述場景的解決方案。deadline實現了四個佇列，其中兩個分別處理正常read和write，按扇區號排序，進行正常io的合併處理以提高吞吐量.因為IO請求可能會集中在某些磁碟位置，這樣會導致新來的請求一直被合併，可能會有其他磁碟位置的io請求被餓死。因此實現了另外兩個處理超時read和write的佇列，按請求建立時間排序，如果有超時的請求出現，就放進這兩個佇列，排程演算法保證超時(達到最終期限時間)的佇列中的請求會優先被處理，防止請求被餓死。
不久前，核心還是預設標配四種演算法，還有一種叫做as的演算法(Anticipatory scheduler)，預測排程演算法。一個高大上的名字，搞得我一度認為Linux核心都會算命了。結果發現，無非是在基於deadline演算法做io排程的之前等一小會時間，如果這段時間內有可以合併的io請求到來，就可以合併處理，提高deadline排程的在順序讀寫情況下的資料吞吐量。其實這根本不是啥預測，我覺得不如叫撞大運排程演算法，當然這種策略在某些特定場景差效果不錯。但是在大多數場景下，這個排程不僅沒有提高吞吐量，還降低了響應速度，所以核心乾脆把它從預設配置裡刪除了。畢竟Linux的宗旨是實用，而我們也就不再這個排程演算法上多費口舌了。
CFQ完全公平佇列
CFQ是核心預設選擇的IO排程佇列，它在桌面應用場景以及大多數常見應用場景下都是很好的選擇。如何實現一個所謂的完全公平佇列(Completely Fair Queueing)?首先我們要理解所謂的公平是對誰的公平?從作業系統的角度來說，產生操作行為的主體都是程序，所以這裡的公平是針對每個程序而言的，我們要試圖讓程序可以公平的佔用IO資源。那麼如何讓程序公平的佔用IO資源?我們需要先理解什麼是IO資源。當我們衡量一個IO資源的時候，一般喜歡用的是兩個單位，一個是資料讀寫的頻寬，另一個是資料讀寫的IOPS。頻寬就是以時間為單位的讀寫資料量，比如，100Mbyte/s。而IOPS是以時間為單位的讀寫次數。在不同的讀寫情境下，這兩個單位的表現可能不一樣，但是可以確定的是，兩個單位的任何一個達到了效能上限，都會成為IO的瓶頸。從機械硬碟的結構考慮，如果讀寫是順序讀寫，那麼IO的表現是可以通過比較少的IOPS達到較大的頻寬，因為可以合併很多IO，也可以通過預讀等方式加速資料讀取效率。當IO的表現是偏向於隨機讀寫的時候，那麼IOPS就會變得更大，IO的請求的合併可能性下降，當每次io請求資料越少的時候，頻寬表現就會越低。從這裡我們可以理解，針對程序的IO資源的主要表現形式有兩個，程序在單位時間內提交的IO請求個數和程序佔用IO的頻寬。其實無論哪個，都是跟程序分配的IO處理時間長度緊密相關的。
有時業務可以在較少IOPS的情況下佔用較大頻寬，另外一些則可能在較大IOPS的情況下佔用較少頻寬，所以對程序佔用IO的時間進行排程才是相對最公平的。即，我不管你是IOPS高還是頻寬佔用高，到了時間咱就換下一個程序處理，你愛咋樣咋樣。所以，cfq就是試圖給所有程序分配等同的塊裝置使用的時間片，程序在時間片內，可以將產生的IO請求提交給塊裝置進行處理，時間片結束，程序的請求將排進它自己的佇列，等待下次排程的時候進行處理。這就是cfq的基本原理。
當然，現實生活中不可能有真正的“公平”，常見的應用場景下，我們很可能需要人為的對程序的IO佔用進行人為指定優先順序，這就像對程序的CPU佔用設定優先順序的概念一樣。所以，除了針對時間片進行公平佇列排程外，cfq還提供了優先順序支援。每個程序都可以設定一個IO優先順序，cfq會根據這個優先順序的設定情況作為排程時的重要參考因素。優先順序首先分成三大類：RT、BE、IDLE，它們分別是實時(Real Time)、最佳效果(Best Try)和閒置(Idle)三個類別，對每個類別的IO，cfq都使用不同的策略進行處理。另外，RT和BE類別中，分別又再劃分了8個子優先順序實現更細節的QOS需求，而IDLE只有一個子優先順序。
另外，我們都知道核心預設對儲存的讀寫都是經過快取(buffer/cache)的，在這種情況下，cfq是無法區分當前處理的請求是來自哪一個程序的。只有在程序使用同步方式(sync read或者sync wirte)或者直接IO(Direct IO)方式進行讀寫的時候，cfq才能區分出IO請求來自哪個程序。所以，除了針對每個程序實現的IO佇列以外，還實現了一個公共的佇列用來處理非同步請求。
當前核心已經實現了針對IO資源的cgroup資源隔離，所以在以上體系的基礎上，cfq也實現了針對cgroup的排程支援。關於cgroup的blkio功能的`描述，請看我之前的文章Cgroup – Linux的IO資源隔離。總的來說，cfq用了一系列的資料結構實現了以上所有複雜功能的支援，大家可以通過原始碼看到其相關實現，檔案在原始碼目錄下的block/cfq-iosched.c。
CFQ設計原理
在此，我們對整體資料結構做一個簡要描述：首先，cfq通過一個叫做cfq_data的資料結構維護了整個排程器流程。在一個支援了cgroup功能的cfq中，全部程序被分成了若干個contral group進行管理。每個cgroup在cfq中都有一個cfq_group的結構進行描述，所有的cgroup都被作為一個排程物件放進一個紅黑樹中，並以vdisktime為key進行排序。vdisktime這個時間紀錄的是當前cgroup所佔用的io時間，每次對cgroup進行排程時，總是通過紅黑樹選擇當前vdisktime時間最少的cgroup進行處理，以保證所有cgroups之間的IO資源佔用“公平”。當然我們知道，cgroup是可以對blkio進行資源比例分配的，其作用原理就是，分配比例大的cgroup佔用vdisktime時間增長較慢，分配比例小的vdisktime時間增長較快，快慢與分配比例成正比。這樣就做到了不同的cgroup分配的IO比例不一樣，並且在cfq的角度看來依然是“公平“的。
選擇好了需要處理的cgroup(cfq_group)之後，排程器需要決策選擇下一步的service_tree。service_tree這個資料結構對應的都是一系列的紅黑樹，主要目的是用來實現請求優先順序分類的，就是RT、BE、IDLE的分類。每一個cfq_group都維護了7個service_trees，其定義如下：
struct cfq_rb_root service_trees[2][3];
struct cfq_rb_root service_tree_idle;
其中service_tree_idle就是用來給IDLE型別的請求進行排隊用的紅黑樹。而上面二維陣列，首先第一個維度針對RT和BE分別各實現了一個數組，每一個數組中都維護了三個紅黑樹，分別對應三種不同子型別的請求，分別是：SYNC、SYNC_NOIDLE以及ASYNC。我們可以認為SYNC相當於SYNC_IDLE並與SYNC_NOIDLE對應。idling是cfq在設計上為了儘量合併連續的IO請求以達到提高吞吐量的目的而加入的機制，我們可以理解為是一種“空轉”等待機制。空轉是指，當一個佇列處理一個請求結束後，會在發生排程之前空等一小會時間，如果下一個請求到來，則可以減少磁頭定址，繼續處理順序的IO請求。為了實現這個功能，cfq在service_tree這層資料結構這實現了SYNC佇列，如果請求是同步順序請求，就入隊這個service tree，如果請求是同步隨機請求，則入隊SYNC_NOIDLE佇列，以判斷下一個請求是否是順序請求。所有的非同步寫操作請求將入隊ASYNC的service tree，並且針對這個佇列沒有空轉等待機制。此外，cfq還對SSD這樣的硬碟有特殊調整，當cfq發現儲存裝置是一個ssd硬碟這樣的佇列深度更大的裝置時，所有針對單獨佇列的空轉都將不生效，所有的IO請求都將入隊SYNC_NOIDLE這個service tree。
每一個service tree都對應了若干個cfq_queue佇列，每個cfq_queue佇列對應一個程序，這個我們後續再詳細說明。
cfq_group還維護了一個在cgroup內部所有程序公用的非同步IO請求佇列，其結構如下：
struct cfq_queue *async_cfqq[2][IOPRIO_BE_NR];
struct cfq_queue *async_idle_cfqq;
非同步請求也分成了RT、BE、IDLE這三類進行處理，每一類對應一個cfq_queue進行排隊。BE和RT也實現了優先順序的支援，每一個型別有IOPRIO_BE_NR這麼多個優先順序，這個值定義為8，陣列下標為0-7。我們目前分析的核心程式碼版本為Linux 4.4，可以看出，從cfq的角度來說，已經可以實現非同步IO的cgroup支援了，我們需要定義一下這裡所謂非同步IO的含義，它僅僅表示從記憶體的buffer/cache中的資料同步到硬碟的IO請求，而不是aio(man 7 aio)或者linux的native非同步io以及libaio機制，實際上這些所謂的“非同步”IO機制，在核心中都是同步實現的(本質上馮諾伊曼計算機沒有真正的“非同步”機制)。
我們在上面已經說明過，由於程序正常情況下都是將資料先寫入buffer/cache，所以這種非同步IO都是統一由cfq_group中的async請求佇列處理的。那麼為什麼在上面的service_tree中還要實現和一個ASYNC的型別呢?這當然是為了支援區分程序的非同步IO並使之可以“完全公平”做準備嘍。實際上在最新的cgroup v2的blkio體系中，核心已經支援了針對buffer IO的cgroup限速支援，而以上這些可能容易混淆的一堆型別，都是在新的體系下需要用到的型別標記。新體系的複雜度更高了，功能也更加強大，但是大家先不要著急，正式的cgroup v2體系，在Linux 4.5釋出的時候會正式跟大家見面。
我們繼續選擇service_tree的過程，三種優先順序型別的service_tree的選擇就是根據型別的優先順序來做選擇的，RT優先順序最高，BE其次，IDLE最低。就是說，RT裡有，就會一直處理RT，RT沒了再處理BE。每個service_tree對應一個元素為cfq_queue排隊的紅黑樹，而每個cfq_queue就是核心為程序(執行緒)建立的請求佇列。每一個cfq_queue都會維護一個rb_key的變數，這個變數實際上就是這個佇列的IO服務時間(service time)。這裡還是通過紅黑樹找到service time時間最短的那個cfq_queue進行服務，以保證“完全公平”。
選擇好了cfq_queue之後，就要開始處理這個佇列裡的IO請求了。這裡的排程方式基本跟deadline類似。cfq_queue會對進入佇列的每一個請求進行兩次入隊，一個放進fifo中，另一個放進按訪問扇區順序作為key的紅黑樹中。預設從紅黑樹中取請求進行處理，當請求的延時時間達到deadline時，就從紅黑樹中取等待時間最長的進行處理，以保證請求不被餓死。
這就是整個cfq的排程流程，當然其中還有很多細枝末節沒有交代，比如合併處理以及順序處理等等。
CFQ的引數調整
理解整個排程流程有助於我們決策如何調整cfq的相關引數。所有cfq的可調引數都可以在/sys/class/block/sda/queue/iosched/目錄下找到，當然，在你的系統上，請將sda替換為相應的磁碟名稱。我們來看一下都有什麼：
[root@zorrozou-pc0 zorro]# echo cfq > /sys/block/sda/queue/scheduler
[root@zorrozou-pc0 zorro]# ls /sys/class/block/sda/queue/iosched/
back_seek_max back_seek_penalty fifo_expire_async fifo_expire_sync group_idle low_latency quantum slice_async slice_async_rq slice_idle slice_sync target_latency
這些引數部分是跟機械硬碟磁頭尋道方式有關的，如果其說明你看不懂，請先補充相關知識：
back_seek_max:磁頭可以向後定址的最大範圍，預設值為16M。
back_seek_penalty:向後定址的懲罰係數。這個值是跟向前定址進行比較的。
以上兩個是為了防止磁頭尋道發生抖動而導致定址過慢而設定的。基本思路是這樣，一個io請求到來的時候，cfq會根據其定址位置預估一下其磁頭尋道成本。首先設定一個最大值back_seek_max，對於請求所訪問的扇區號在磁頭後方的請求，只要定址範圍沒有超過這個值，cfq會像向前定址的請求一樣處理它。然後再設定一個評估成本的係數back_seek_penalty，相對於磁頭向前定址，向後定址的距離為1/2(1/back_seek_penalty)時，cfq認為這兩個請求定址的代價是相同。這兩個引數實際上是cfq判斷請求合併處理的條件限制，凡事複合這個條件的請求，都會盡量在本次請求處理的時候一起合併處理。
fifo_expire_async:設定非同步請求的超時時間。同步請求和非同步請求是區分不同佇列處理的，cfq在排程的時候一般情況都會優先處理同步請求，之後再處理非同步請求，除非非同步請求符合上述合併處理的條件限制範圍內。當本程序的佇列被排程時，cfq會優先檢查是否有非同步請求超時，就是超過fifo_expire_async引數的限制。如果有，則優先發送一個超時的請求，其餘請求仍然按照優先順序以及扇區編號大小來處理。
fifo_expire_sync:這個引數跟上面的類似，區別是用來設定同步請求的超時時間。
slice_idle:引數設定了一個等待時間。這讓cfq在切換cfq_queue或service tree的時候等待一段時間，目的是提高機械硬碟的吞吐量。一般情況下，來自同一個cfq_queue或者service tree的IO請求的定址區域性性更好，所以這樣可以減少磁碟的定址次數。這個值在機械硬碟上預設為非零。當然在固態硬碟或者硬RAID裝置上設定這個值為非零會降低儲存的效率，因為固態硬碟沒有磁頭定址這個概念，所以在這樣的裝置上應該設定為0，關閉此功能。
group_idle:這個引數也跟上一個引數類似，區別是當cfq要切換cfq_group的時候會等待一段時間。在cgroup的場景下，如果我們沿用slice_idle的方式，那麼空轉等待可能會在cgroup組內每個程序的cfq_queue切換時發生。這樣會如果這個程序一直有請求要處理的話，那麼直到這個cgroup的配額被耗盡，同組中的其它程序也可能無法被排程到。這樣會導致同組中的其它程序餓死而產生IO效能瓶頸。在這種情況下，我們可以將slice_idle = 0而group_idle = 8。這樣空轉等待就是以cgroup為單位進行的，而不是以cfq_queue的程序為單位進行，以防止上述問題產生。
low_latency:這個是用來開啟或關閉cfq的低延時(low latency)模式的開關。當這個開關開啟時，cfq將會根據target_latency的引數設定來對每一個程序的分片時間(slice time)進行重新計算。這將有利於對吞吐量的公平(預設是對時間片分配的公平)。關閉這個引數(設定為0)將忽略target_latency的值。這將使系統中的程序完全按照時間片方式進行IO資源分配。這個開關預設是開啟的。
我們已經知道cfq設計上有“空轉”(idling)這個概念，目的是為了可以讓連續的讀寫操作儘可能多的合併處理，減少磁頭的定址操作以便增大吞吐量。如果有程序總是很快的進行順序讀寫，那麼它將因為cfq的空轉等待命中率很高而導致其它需要處理IO的程序響應速度下降，如果另一個需要排程的程序不會發出大量順序IO行為的話，系統中不同程序IO吞吐量的表現就會很不均衡。就比如，系統記憶體的cache中有很多髒頁要寫回時，桌面又要開啟一個瀏覽器進行操作，這時髒頁寫回的後臺行為就很可能會大量命中空轉時間，而導致瀏覽器的小量IO一直等待，讓使用者感覺瀏覽器執行響應速度變慢。這個low_latency主要是對這種情況進行優化的選項，當其開啟時，系統會根據target_latency的配置對因為命中空轉而大量佔用IO吞吐量的程序進行限制，以達到不同程序IO佔用的吞吐量的相對均衡。這個開關比較合適在類似桌面應用的場景下開啟。
target_latency:當low_latency的值為開啟狀態時，cfq將根據這個值重新計算每個程序分配的IO時間片長度。
quantum:這個引數用來設定每次從cfq_queue中處理多少個IO請求。在一個佇列處理事件周期中，超過這個數字的IO請求將不會被處理。這個引數只對同步的請求有效。
slice_sync:當一個cfq_queue佇列被排程處理時，它可以被分配的處理總時間是通過這個值來作為一個計算引數指定的。公式為：time_slice = slice_sync + (slice_sync/5 * (4 – prio))。這個引數對同步請求有效。
slice_async:這個值跟上一個類似，區別是對非同步請求有效。
slice_async_rq:這個引數用來限制在一個slice的時間範圍內，一個佇列最多可以處理的非同步請求個數。請求被處理的最大個數還跟相關程序被設定的io優先順序有關。
