I. INTRODUCTION

In the cloud computing service, it is critical problem that system resources should be isolated and allocated among multiple tenants according to different service requirements ⁽³⁾. Especially, as high performance storage such as SSDs are introduced in the cloud computing area, sharing I/O resource of SSDs among multiple tenants with only few overhead became an important problem. Linux Cgroups ^(5,6) is a resource control framework of Linux which allocates system resources such as CPU, memory, and I/O bandwidth to each process group(called as cgroup). Specifically, it provides a proportional I/O resource sharing scheme which distributes I/O bandwidth to each cgroup in proportion to I/O weight through an I/O scheduler.

NAND flash memory-based SSDs (Solid-state Drives) are recently very popular as a second storage device because of its outstanding I/O performance in comparison to HDDs (Hard-disk Drives). However, legacy storage interface, Serial ATA(SATA) has insufficient maximum bandwidth due to supporting single I/O queue so that it could not take full advantage of internal parallelism of SSDs. NVM Express (NVMe) ⁽⁴⁾ is the state-of-the-art storage interface providing multiple submission queues for SSDs, so that it can achieve more than one million IOPS with maximizing internal parallelism of SSDs. However, I/O bandwidth sharing is not efficiently supported for NVMe SSDs with Linux Cgroups.

There are some studies have proposed proportional I/O scheduler for a multi-queue storage ^(13,14). However, they cannot fully utilize the performance of NVMe SSD because of a scalability problem. Especially, BFQ scheduler ⁽¹³⁾, the only proportional share scheduler of Linux, suffers from performance overhead due to single dispatch queue. According to our preliminary performance evaluation results, it degrades I/O throughput of NVMe SSD up to 63% compared to None scheduler.

In this paper, we present scalable multi-queue I/O scheduler supporting proportional I/O bandwidth sharing for NVMe SSDs without performance degradation. The proposed scheduler employs a cgroup dedicated request queue set for each CPU for parallel I/O request dispatching. Also, I/O bandwidth is shared by periodically allocating I/O tokens to each cgroup in proportion to their I/O weight. Consequently, our scheduler can parallelly dispatch I/O request and share I/O bandwidth with no global synchronization between multiple cgroups because of the scalable architecture. Moreover, the total amount of I/O tokens periodically updates for adjusting to the fluctuated performance of NVMe SSDs due to internal operations such as garbage collection. The proposed I/O scheduler is implemented on Linux kernel 5.2.0 and evaluated with both synthetic and real workloads. The evaluation results show that our I/O scheduler improves I/O bandwidth 3.61 times than BFQ scheduler while allocating I/O bandwidth in proportion to I/O weights exactly. Also, scalability evaluation result shows that our scheduler has no scalability problem even with high degree of multi-threading unlike other multi-queue proportional share scheduler.

The remainder of this paper is organized as follows. Section II introduces the previous studies for I/O resource sharing with SSDs. Then, we show the preliminary evaluation results for BFQ scheduler in Section III. Section IV describes the proposed proportional-share I/O scheduler. Experimental results are presented in Section V. The conclusion is given in Section VI.

II. RELATED WORK

There have been several studies on the proportional I/O sharing scheme for multi-queue SSDs. Ahn et al. ⁽¹²⁾ implemented the weight-based dynamic throttling (WDT) technique on Linux Cgroups layer to throttle the bandwidth to match the I/O weight of each cgroup. However, although it guarantees the fairness on Linux Cgroups layer, the fairness can be degraded due to unexpected scheduling because the WDT is implemented above the multi-queue block layer ⁽⁷⁾. Moreover, the responsibility for the guarantee of fairness has been maintained by the scheduler traditionally. Therefore, it is hierarchically appropriate that I/O schedulers in the multi-queue block layer carry out the proportional I/O sharing.

Budget fair queueing (BFQ) scheduler proposed by Valente et al. ⁽¹³⁾ is currently the default proportional share scheduler for Linux multi-queue block layer. BFQ scheduler allocates a budget, the number of sectors used for dispatching I/O requests, to each cgroup according to I/O weight to achieve proportional I/O sharing. However, in BFQ scheduler, the internal parallelism of multi-queue NVMe SSDs cannot be fully utilized because only one request queue can dispatch I/O request to the storage device at a time.

M. Hedayati et al. ⁽¹⁴⁾ proposed the MQFQ scheduler which adapts a classical fair queueing algorithm to multi-queue designs and employs scalable data structures to minimize synchronization overhead. However, even with these attempts, MQFQ shows scalability problem with extremely high degree of concurrency workload because the global data structure must be referred whenever each I/O request is dispatched. In addition, since MQFQ provides request queue for each CPU, scalability problem occurs with large number of threads exceeding the number of CPUs.

Kim et al. ⁽¹⁵⁾ proposed a I/O differentiated scheme based on Linux process priority. However, it is focused to improve the performance of I/O intensive processes by considering process priority even for I/O scheduling, not to share I/O bandwidth proportionally.

The proportional I/O sharing schemes for multi-queue SSDs should be implemented slightly differently from the traditional schemes for single-queue SSDs ^(9-11). First, the parallelism of multi-queue block layer should not be harmed by minimizing global synchronization and allowing each I/O queue to perform proportional I/O sharing without interaction between other cgroups. Unlike single queue block layer, attempting to maintain the fairness of bandwidth between multiple cgroups through global synchronization would break the parallel processing of multi-queues and causes the severe I/O performance degradation.

Second, work-conservation should also be considered while implementing proportional I/O sharing schemes for multi-queue NVMe SSDs. Work-conserving in the proportional I/O bandwidth sharing scheme means that the storage device should be busy without leaving the SSDs idle, even if all of cgroups are consumed their own allocated I/O bandwidth.

III. MOTIVATION

In this section, we show the performance degradation of the BFQ scheduler through the experimental results. To evaluate the fairness and performance overhead of the BFQ scheduler, we measured the I/O throughput of four cgroups having different I/O weight (1000:500:250:100) for the None and BFQ scheduler. Note that the None scheduler is FIFO-fashioned I/O scheduler with little scheduling overhead, and provides a baseline of the maximum performance of NVMe SSD ⁽¹⁷⁾. Fig. 1 shows the I/O throughput of both the None and BFQ scheduler measured by using synthetic mixed 4KB random workload configured by 0.5 read ratio with FIO benchmark ⁽¹⁶⁾. As you can see in the figure, the None scheduler does not provide any proportional bandwidth sharing scheme for cgroups, while the BFQ scheduler accurately shares the bandwidth among four cgroups according to their own I/O weight. However, for the BFQ scheduler, the aggregated throughput was seriously degraded by about 0.38 times compared to the None scheduler. Moreover, the throughput of the cgroup with the highest weight in the BFQ scheduler is lower than any cgroup in the None scheduler. It means that the BFQ scheduler cannot fully utilize the performance of NVMe SSDs.

The reason for the performance degradation in the BFQ scheduler is a serialized request dispatching process used to guarantee the fairness between multiple cgroups ⁽¹⁴⁾. Therefore, in this paper, we propose the new proportional-share I/O scheduler that can accurately share I/O bandwidth proportionally without wasting high performance of multi-queue SSDs.

IV. KYBER-FAIRNESS SCHEDULER

In this section we describe the Kyber-fairness scheduler, a novel proportional share I/O scheduler for multi-queue block layer proposed in this paper.

V. EXPERIMENTAL RESULTS

To evaluate the performance and fairness of Kyber-fairness scheduler, we have implemented and evaluated it on Linux kernel 5.2.0 and the experimental environment described in Table 1 ⁽⁸⁾. Also, FIO and trace-replay ⁽²⁰⁾ have been used for measuring I/O performance of synthetic and real workloads, respectively.

FIO benchmark performs four different synthetic I/O workload, random read/write and sequential read/write workloads. Four cgroups are generated in total and each one has four threads. The I/O weight of cgroups are 100, 250, 500 and 1000, respectively. Table 2 shows the parameters used for FIO.

Fig. 4 shows the results of FIO benchmark. Fig. 4(a) shows Kyber-fairness scheduler can delivers closed I/O throughput to the None scheduler for all types of workloads. It improves I/O performance by 2.68x and 3.61x, respectively, for random read and random write workloads compared to BFQ scheduler. However, we can see that the performance improvement is not impressive in sequential workloads. The reason is that the scalability problem of BFQ is hidden for sequential workloads that do not require high scalability. Moreover, as you can see in Fig. 4(b), proposed Kyber-fairness scheduler ensures the fairness among multiple cgroups having different I/O weights. Note that Fairness Index (FI) ⁽¹⁸⁾ is an indicator of how accurately the I/O bandwidth is shared in proportion to I/O weights, the closer it is to 1, the more accurately it is shared.

For generating real workloads, block I/O trace replay tool, trace-replay ⁽²⁰⁾ is used with block I/O traces from SNIA ⁽²¹⁾. Tables 3 and 4 shows the parameters used for the trace-replay and the characteristics of I/O workloads, respectively. In our experiments, four cgroups are created and each cgroup replays one of the block I/O traces described in Table 4 where the different I/O weights are given to them. Note that all traces are replayed by four concurrent threads during 60 seconds without timing consideration of the I/O requests.

Fig. 5 shows the I/O performance and fairness of I/O schedulers for real workloads. Fig. 5(a) shows that Kyber-fairness scheduler can improves the I/O performance up to 1.33 times higher than that of BFQ scheduler. Moreover, Kyber-fairness scheduler shows slightly better fairness index than BFQ scheduler, as shown in Fig. 5(b). However, in Fig. 5(a), you can see that the performance gap between BFQ and Kyber-fairness is narrower when the LUN3 has the highest weight. The reason is that LUN3 does not require scalable performance compared to other LUNs so that the scalability problem of BFQ scheduler is not significantly exposed.

Fig. 6 shows the scalability evaluation results of I/O schedulers. To evaluate scalability, we use small sized (1KB) random read requests with increasing number of cgroups. As you can see in the figure, the Kyber-fairness shows a performance close to that of the None scheduler even if the number of cgroups increases, whereas the BFQ scheduler decreases sharply as the number of cgroups increases. The experimental result shows that our proposed scheduler does not harm the parallelism of multi-queue block design even with high degree of multiple threading.

VI. CONCLUSIONS

We proposed the scalable low-overhead proportional-share I/O scheduler for multi-queue block layer. The proposed I/O scheduler efficiently supports the proportional I/O bandwidth sharing for NVMe SSDs with removing global synchronization and token amount prediction technique. According to the experimental results, our I/O scheduler shows up to 3.61 times better I/O performance than the existing proportional-share I/O scheduler while the fairness was also accurately guaranteed. Moreover, the scalability evaluation result shows that the proposed Kyber-fairness scheduler can serve a scalable performance even with extremely high degree of multiple threading.