USENIX Association 2013 USENIX Annual Technical Conference (USENIX ATC ’13) 67 FlashFQ: A Fair Queueing I/O Scheduler for Flash-Based SSDs

On Flash-based solid-state disks (SSDs), different I/O operations (reads vs. writes, operations of differ-ent sizes) incur substantially different resource usage. This presents challenges for fair resource management in multi-programmed computer systems and multi-tenant cloud systems. Existing timeslice-based I/O schedulers achieve fairness at the cost of poor responsiveness, par-ticularly when a large number of tasks compete for I/O simultaneously. At the same time, the diminished ben-efits of I/O spatial proximity on SSDs motivate fine-grained fair queueing approaches that do not enforce task-specific timeslices. This paper develops a new Flash I/O scheduler called FlashFQ. It enhances the start-time fair queueing schedulers with throttled dispatch to ex-ploit restricted Flash I/O parallelism without losing fair-ness. It also employs I/O anticipation to minimize fair-ness violation due to deceptive idleness. We implemented FlashFQ in Linux and compared it with several existing I/O schedulers—Linux CFQ [2], an Argon [19]-inspired quanta scheduler, FIOS timeslice scheduler [17], FIOS with short timeslices, and 4-Tag SFQ(D) [11]. Results on synthetic I/O benchmarks, the Apache web server, and Kyoto Cabinet key-value store demonstrate that only FlashFQ can achieve both fairness and high responsive-ness on Flash-based SSDs.