K2: Work-Constraining Scheduling of NVMe-Attached Storage

For data-driven cyber-physical systems, timely access to storage is an important building block of real-time guarantees. At the same time, storage technology undergoes continued technological advancements. The introduction of NVMe fundamentally changes the interface to the drive by exposing request parallelism available at the flash package level to the storage stack, allowing to extract higher throughput and lower latencies from the drive. The resulting architectural changes within the operating system render many historical designs and results obsolete, requiring a fresh look at the I/O scheduling landscape. In this paper, we conduct a comprehensive survey of the existing NVMe-compatible I/O schedulers in Linux regarding their suitability for real-time applications. We find all schedulers severely lacking in terms of performance isolation and tail latencies. Therefore, we propose K2, a new I/O scheduler specifically designed to reduce latency at the 99.9th percentile, while maintaining the throughput gains promised by NVMe. By limiting the length of NVMe device queues, K2 reduces read latencies up to 10x and write latencies up to 6.8x, while penalizing throughput for non-real-time background load by at most 2.7x.