[ISCA'18] FLIN

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

作者： * Carnegie Mellon University

论文概要

MQ-SSD内部架构图

Abstract

  以NVMe为例，新的SSD主机接口被广泛使用，也就是MQ-SSD(Multi-Queue SSD)的概念。使得SSD可以直接访问应用级的I/O队列，消除了传统的软件栈开销。消除传统软件栈之后，虽然性能提升了，但是却带来了一个新问题：公平性缺失。这是因为传统的维护公平性的机制也被取消了。

  公平性缺失的一个体现就是：当一个用户增大请求密度的时候，其他用户被很明显的slow down了。我们认为MQ-SSD的这种干扰来源主要有四个：

1. 每个应用程序发送请求的强度；

2. 请求访问模式的区别；

3. 读写比；

4. 垃圾回收

  为了消除这种不公平，我们提出了Flash- Level INterference-aware scheduler (FLIN)。这是一个在不同应用之间保证公平性的、轻量级的I/O请求调度机制。它采取了一个three-stage的调度算法，在保证host端指定的优先级的基础上，针对上面的四个方面的因素进行保障。

接下来就是对实验效果的一些列举。

Introduction

核心设计

主要是一个三阶段的设计，如下图所示：

FLIN的总体架构

1. 4KB请求的插入位置进行调度，取决于当前的访问强度以及访问模式；

2. priority-aware队列仲裁，用来决定闪存芯片上下一个读/写请求。其目的是保证相同优先级的flow会有相同的slowdown。

3. wait-balancing transaction selection，选择下发到闪存芯片控制器的4KB transaction，从而减少读/写比和GC带来的干扰。 下发读事务、写事务或者GC事务，保证：① 读的slowdown与写的slowdown持平；② 将GC的transaction公平地分配到各个事务上。

对于第一个阶段，主要是根据请求的密集程度不同，将其插到队列的不同位置：低密度的请求插到队列前端、高密度的请求插到队列后端；

对于第二个阶段，采用了weighted round-robin策略，来判定哪个transaction会下发到闪存芯片上；

对于第三个阶段，不再是无脑地让读事务比写事务优先执行，而是定义了一个proportional wait time (PW)，也就是一个transaction“从调度器下发到被下发到FCC的等待时间”和“请求在内存的时间+请求传回前端的时间的总和”的比值。根据读和写的这个比值大小，来判断哪个先执行。

我的思考

值得学习的结论

MQ-SSD中影响公平性的几个因素：

1. 请求密度。I/O密集的应用会导致其他应用的性能急剧下降。

2. 访问模式。请求A的并行性很高，子请求放在很多chip上；而请求B的并行性很差，可能往某些chip上插入了很多请求，从而影响了请求A的完成时间。

3. 读/写比。因为写请求的执行速度比读慢10-40倍，当前MQ-SSD往往倾向于优先服务读请求，甚至读请求会抢占正在执行的写请求，这回导致写事务的延迟大大增加。

4. GC。由于GC具有延后性，因此一个请求的GC会导致其他请求slow down。GC密集的flow会频繁干扰其他flow。

本文对于公平性的定义

在收到干扰时，相同优先级的负载有相同的slow down（以响应时间来量化）。

$$S_i = RT_i^{shared} / RT_i^{alone}$$

$$F=\min\limits_i\{S_i\}/\max\limits_i\{S_i\}$$

引用

GB/T

Tavakkol A, Sadrosadati M, Ghose S, et al. FLIN: Enabling fairness and enhancing performance in modern NVMe solid state drives[C]//2018 ACM/IEEE 45th Annual International Symposium on Computer Architecture (ISCA). IEEE, 2018: 397-410.