FLIN（2018 ISCA）

文章目錄

• FLIN：Enabling Fairness and Enhancing Performance in Modern NVMe Solid State Drives
• • Abstract
  • Introduction
  • Background
  • Design and Implementation
  • • 1. fairness-aware queue insertion
    • 2. Priority-Aware Queue Arbitration
    • 3. Wait-Balancing Transaction Selection
  • Results
  • Conclusion

FLIN：Enabling Fairness and Enhancing Performance in Modern NVMe Solid State Drives

這篇論文發表在2018年的International Symposium on Computer Architecture(ISCA)會議上，主要講的是：在NVMe協定下，多隊列I/O請求直接通路SSD，SSD如何保證其間的公平性問題。

Abstract

1. 原來單隊列模式下的應用程式需要在作業系統與之關聯的IO堆中建立一個堆棧單元，現在多隊列SSD用的協定主要是NVMe，NVMe協定允許應用程式跳過作業系統IO堆，直接發送IO請求到SSD中。這樣就出現了一個問題：原來在作業系統中的公平性控制機制就不起作用了，多個應用程式産生的多個IO請求流直接進入SSD後很難保證公平性，當一個流的強度太大，其它請求流就會明顯變慢。
2. 本文提出了一個叫做FLIN的排程機制來解決這個公平性問題
3. 實驗結果表明，FLIN在公平性和性能方面分别提升了70%和47%

Introduction

1. 像之前說的，本來應用程式先通過作業系統的軟體堆，作業系統通過限制每個應用程式派遣到SSD的請求數量來保證公平性。多隊列SSD中，應用程式直接把請求發到SSD，應用程式的優先級可以由作業系統控制，NVMe允許host給每個流配置設定不同的優先級，但是相同優先級的io流之間的公平性就很難保證，當一個流的請求強度太大，另一個低強度的流可能會一直得不到滿足。

2. 影響io流之間的公平性主要有四個因素：

   第一個是I / O強度：具有較高流強度的I O流會導緻具有較低流強度的流變慢。

   第二個是通路模式：與不利用并行性的I / O流一起運作時，較好的利用内部并行性的io流速度反而會降低大概2.4倍。因為利用了并行性的io流會分到不同的chip中，單個chip裡的io強度就會更低。

   第三個是讀/寫比例：寫入請求比例較高的流會讓寫入請求比例較小的并發運作的流速度減慢。

   第四個是垃圾回收：當I / O流需要頻繁進行GC操作時，這些操作可能會阻止很少執行GC的第二個流的I / O請求。

3. 本文的目的是設計一種有效的I / O請求排程程式，通過減輕SSD内的所有四種幹擾來提供I / O流之間的公平性，并最大化SSD的性能和吞吐量。

   FLIN考慮每個流的優先級類别，并使用三個階段來排程請求。

   (1). 感覺強度和并行性的隊列插入，對事務進行重新排序，以減輕不同的I / O強度和不同的通路模式的影響。

   (2). 流級别的優先級仲裁，根據事務的相應流的優先級對事務進行優先級排序。

   (3). 讀/寫等待平衡，平衡讀寫請求的總體停頓時間，并計劃GC活動以在不同流之間按比例配置設定GC開銷。

Background

1. MQ-SSD的内部結構如下圖所示：

   

   HIL: 将請求分解成多個閃存事務，每個事務的閃存操作粒度是一個頁

   FTL: 将事務分進chip層次的隊列，隊列分為讀隊列和寫隊列

   TSU: 将隊列配置設定到對應的FCC(flash chip controllers)

2. 性能衡量标準：

   

   

   

   

   Slowdown越小越好，fairness越大越好。

   下圖是高強度的io流對一個中等強度的io流的影響，黑色是中等強度的io流，紅色是高強度的io流。可以看到中等強度的io流速度明顯減慢了，缺乏公平性。

   

Design and Implementation

FLIN是将原來多隊列SSD中的TSU子產品也就是事務排程單元進行了重新設計。

Chip隻有一個接口，而事務太多、優先級不同

1. fairness-aware queue insertion: 第一步是将請求加到對應優先級的隊列中，這個數值P是根據NVMe協定來定的，因為NVMe允許host給每個流配置設定不同的優先級，NVMe能定義多少個優先級數值P就是多少。是以第一步中相同優先級的請求、不管屬于哪個io流都會被分到同個隊列，然後采用設計的算法就事務進行排序，保證公平性。
2. Priority-Aware Queue Arbitration: 第二步是根據不同的優先級，用權重輪詢算法選出要執行的讀事務和寫事務。
3. Wait-Balancing Transaction Selection: 第三步是利用算法平衡讀寫事務和GC操作。

1. fairness-aware queue insertion

在第一階段，FLIN在每個chip中為每個流優先級維護單獨的讀隊列和寫隊列。 在每個隊列中找到事務的最佳排序是多元配置設定問題的一個變體，是一個NP難問題。 FLIN使用一種近似最佳排序的試探法。

需要解決以下幾個問題：

1，當高強度流一下子插入許多事務時，低強度流的性能對增加的隊列長度會非常敏感；2，根據應用程式的目前階段，一些流可以在高強度和低強度之間變化；3，當并行性差的流将請求插入到某些（但不是全部）晶片級隊列中時，利用後端并行性的流中的某些（但不是全部）事務會經曆較高的隊列等待時間。

下面是stage1的算法：将低強度的io流事務配置設定在隊列前面，高強度的io流事務配置設定在隊列後面，每次增加一個事務時如果是低強度流的事務就加到低強度事務中的末端，如果是高強度流的事務就加到高強度事務中的末端。然後再根據情況進行調整。

2. Priority-Aware Queue Arbitration

優先級感覺隊列仲裁從P個讀取隊列的開頭的事務中選擇一個就緒讀取事務，并從P個寫入隊列的開頭的事務中選擇一個就緒寫入事務。 然後，兩個標明的事務移至排程程式的最後階段。

隊列仲裁器使用權重循環政策來選擇移至下一個排程階段的讀取和寫入事務。 如果協定定義了P個優先級，其中0級是最低優先級，P – 1是最高優先級，則FLIN将權重2的i次方配置設定給優先級i。 在權重輪詢下，這意味着在第二階段的每2的i個排程決策中，優先級為i隊列的事務接收到這些時隙中的2的i次方個。

3. Wait-Balancing Transaction Selection

第三步比較簡單，算法看圖：

Results

平均而言，與最先進的裝置級I / O請求排程程式相比，FLIN可以提供70％的公平性和47％的性能提升。

FLIN在工作負載中的每個流之間更公平地分布幹擾的影響。 他們得出的結論是，FLIN的減速管理方案可以有效地提高兩個最新基準的MQ-SSD公平性。

Conclusion

FLIN是用于現代多隊列SSD（MQ-SSD）的輕型事務排程程式，可在并發運作的流之間提供公平性。

FLIN使用三階段設計來防禦實際MQ-SSD中存在的所有四個主要幹擾源，同時強制執行由主機配置設定的應用程式級優先級。

評估表明，與最新的裝置級排程程式相比，FLIN有效地提高了公平性和系統性能。 FLIN易于在SSD控制器固件中實作，不需要額外的硬體，并且消耗的記憶體少于SSD内置DRAM中可用存儲空間的0.06％。