ScyllaDB的Userspace IO Scheduler實現

02-01

1. 關於ScyllaDB

ScyllaDB號稱世界上最快的NoSQL資料庫。它兼容Cassandra協議，性能優於Canssandra資料庫（據ScyllaDB給出的benchmark, 性能要優於10倍）。ScyllaDB由Avi Kivity, Dor Laor團隊開發（這兩位都是業界大牛）。

2. 為什麼要實現用戶態IO調度器

雖然磁碟技術在近10年有長足進步，特別是SSD盤的出現，為存儲系統提供了可觀的IO能力。即便如此，磁碟的IO速度遠遠落後於內存，更別提CPU了。在存儲系統中，存在激烈的磁碟IO競爭。這些IO產來自於系統的讀，寫，後台整理數據等動作。在沒有合理調度的請情況下，這些來自不同動作的磁碟IO會嚴重影響系統服務質量。例如，後台整理數據產生的IO消耗了系統所有磁碟IO能力，那麼系統就無法提供讀寫服務了。

由此可見，合理高效的磁碟IO對存儲系統顯得尤為重要。

2.1 系統磁碟IO過載會降低存儲系統服務質量

首先，放一張IO Stack全景圖（這是一張很經典的圖）。

從這個圖中，我們可以看到IO Stack中存在不同級別的隊列。這些隊列用於不同組件之間的通訊或傳遞數據。然而隊列的長度是有限制的。

由於磁碟的處理能力遠遠低於CPU的處理能力。大量的IO請求會被緩存在IO-Stack中的隊列里：磁碟硬體隊列，Block Layer 隊列，文件系統隊列。通常我們還很難判斷某個IO請求當前到底在哪個隊列里。

用戶線程需要一個關於系統IO能力的全局視圖，根據當前系統IO負載情況，判斷是否提交IO請求。否則，用戶線程會提交很多無效IO請求。舉個栗子：在存儲系統中，讀請求都有timeout限制，當上層請求timeout後，IO請仍然緩存在內核態的某個隊列里等待完成。

總之，不加控制的向系統提交IO請求，當超過IO負載能力後，IO請求就會緩存在IO協議棧中的隊列里，造成存儲服務質量下降。

2.2 實現用戶態IO調度器帶來的好處

當用戶線程提交的IO請求速度超過磁碟處理速度，IO請求總會被緩存在內存里等待處理。IO請求緩存在用戶空間隊列里，並不比緩存在內核空間更能提供IO處理能力。那IO請求緩存在用戶空間里仍然有如下好處：

1）將當前IO 請求的統計信息吐出來，用戶線程或者客戶端根據當前IO請求堆積情況，合理調節IO規模與速度，從而充分利用磁碟IO能力；
2）對不同IO請求區別對待，優先處理優先順序高的請求；
3）可取消無效IO，避免浪費磁碟IO能力；

在用戶線程與系統IO-Stack之間實現一個IO調度器，合理調度IO請求，及時吐出描述當前系統IO狀況的數據，確保系統IO不會過載，而影響服務質量。

3. ScyllaDB設計用戶態IO調度器考量的問題

線程模型

由於ScyllaDB採用per-core-per-thread線程模型，使用全局IO調度器就於該模型秉承的理念不符了。所以，最好的情況是IO調度器也是每一個線程擁有一個，這樣避免跨線程傳遞message（ScyllaDB 跨線程傳遞數據採用by message方式，而非共享內存）。但是另一方面，考慮到系統IO能力有限，存在多個線程共享一個IO調度器。

在ScyllaDB中，用戶態IO調度器主要邏輯實現在IO-Queue中。

IO-Depth

還有一個重要的問題需要考慮：如何選擇合適的IO-depth, 也就是在IO不過載的情況下，如何確定能夠並行處理的IO請求數量（關於IO-depth, 也可以參考這裡）。ScyllaDB提供一個工具，在首次運行時候，需要先跑該工具，測量出合適的IO-depth，作為ScyllaDB啟動的參數之一。

IO請求優先順序

由於存在多個用戶線程共享一個IO-Queue的情況，IO調度器的設計不是按照IO-Queue調度，是按照IO請求的優先順序調度。在ScyllaDB中，IO請求被劃分為6個不同類別，每一個類別擁有自己的優先順序（優先順序通過一個正整數來表示，數值越高，優先順序越高，這個數值稱之為shares）：

寫commit log，shares = 100;
刷memtable數據到磁碟，shares = 100;
流式讀請求，shares = 20;
流式寫請求， shares = 20;
處理CQL請求，shares = 100;
Compaction動作，shares = 100;

4. ScyllaDB用戶態IO調度器實現

ScyllaDB的用戶態IO調度器要實現的目標是：合理控制IO請求的規模與速度。保障系統不會過載的情況下，在單位時間窗口內，系統中所有IO請求按照優先順序處理，相同優先順序的按FIFO原則處理。接下來看，如何達成上述目標的。

4.1 IO調度模型

IO-Queue實現了用戶態IO調度器的主要邏輯。系統啟動後會在每一個IO-Queue中註冊多種類型的PriorityClass。每次提交IO請求都會緩存在對應的PriorityClass的隊列中。 IO調度是按照PriorityClass來調度的。

具體來說，每一個PriorityClass都維護一個度量IO請求消耗的變數。每一個IO請求都有一個消耗值(cost), 當IO請求提交到內核後，該消耗值會累加到對應的PriorityClass的總消耗變數中。調度器總是選擇一個擁有最小累加消耗值的PriorityClass，將其隊列的第一個IO請求提交到內核。

也就是說，PriorityClass 總消耗值越小，越被調度器優先選擇並執行其隊列中的IO請求。IO請求提交到系統後，需要根據該IO請求在隊列中等待時間，評估本次IO請求的消耗值，並將該值累加到所在PriorityClass中。

總的流程看起來很簡單。如何評估一次IO請求的消耗值呢？繼續往下看。

4.2 IO請求消耗的評估

在此之前，我們先了解下什麼是指數衰減。

某個量的下降速度和它的值成比例，稱之為服從指數衰減。關於指數衰減，更多內容請閱讀維基百科裡的內容。ScyllaDB 的用戶態IO調度器使用指數衰減模型描述IO請求的消耗(cost)。一次IO請求從發起請求到提交的IO-Stack這段時間裡，IO請求的cost是時間的函數。

IO請求提交到調度器時候，會根據數據長度，所在PriorityClass來確定一個初始IO消耗值。直到IO請求被提交到內核，調度器會根據IO請求在調度器中等待的時間，以及初始消耗值，按照指數衰減函數來計算此次IO消耗值。

由此可見，一個IO請求等待時間越長，其消耗值衰減的月厲害，最終累加到PriorityClass上值就會少，也就是對該PriorityClass上其他請求影響減弱。

4.3 用戶態IO調度器實現細節

一次IO請求的消耗初始值與數據長度成正比，與PriorityClass的優先順序值成反比。

IO請求從提交到調度器，到請求被提交到內核過程中，其消耗值服從指數衰減。當超過衰減周期後，本次IO請求對所在PriorityClass的總消耗值影響就微乎其微了。

5. 後記

ScyllaDB 的用戶態IO調度器的實現，給存儲系統處理IO問題提供了一種思路。以往工作中，用Google的LevelDB作為存儲引擎，經常遇到IO能力在讀，寫，Compaction 之間分配不均衡，導致系統服務質量急劇下降的情況。

引用

[1]: Designing a Userspace Disk I/O Scheduler for Modern Datastores: the Scylla example (Part 2)

[2]: Designing a Userspace Disk I/O Scheduler for Modern Datastores: the Scylla example (Part 1)

[3]: https://zh.wikipedia.org/wiki/%E6%8C%87%E6%95%B0%E8%A1%B0%E5%87%8F

[4]: Fio壓測工具和io隊列深度理解和誤區

本文屬於我翻閱ScyllaDB代碼時候隨手筆記的一部分，經過整理分享出來，希望有更多人認識ScyllaDB, 使用ScyllaDB。轉載請註明出處。