January 30th, 2007


High performance Linux kernel IO scheduler design.

JA: In February of 2003 you posted two new I/O schedulers. The first was the Stochastic Fair Queuing (SFQ) scheduler. The second was the Complete Fair Queuing (CFQ) scheduler. What prompted you to try and improve upon your earlier deadline scheduler?

Jens Axboe: While [the] deadline [scheduler] worked great from a latency and hard drive perspective, it had no concept of individual process fairness. SFQ is originally a network queuing algorithm, but the main concept applied equally well to IO queuing disciplines. The core design is dividing a flow of packets into a fixed number of buckets, based on the hash of the source. So if you have N number of buckets, the algorithm should be fair to N number of processes (barring no hash collisions, hence the occasional hash function change). So the SFQ IO scheduler divides incoming process IO into a fixed number of buckets, and does request dispatch in a round robin fashion from these buckets.