Choosing an I/O Scheduler and Setting Queue Depth

The elevator algorithm was invented for a device whose cost was dominated by moving a head to the right track. Ordering requests by address turned random access into something close to sequential, and the improvement was large enough that every general-purpose operating system shipped a scheduler. A flash device has no head. Reading any page costs the same as reading any other, apart from channel and die contention, and the device’s parallelism is in the number of dies that can work at once rather than in the order of addresses. The scheduler’s job survives, but it has changed from minimizing movement to controlling how much work is in flight and how reads and writes share the device.

What scheduling can still buy

Three things remain worth doing. The first is read prioritization. A read blocks a process that is waiting for data, while a write usually lands in the page cache and is not waited on. A device that mixes reads and writes, with writes filling its internal buffers, delays reads behind them. A scheduler that dispatches reads ahead of queued writes reduces read latency at the cost of write latency, and the cost is usually invisible because writes were not on anyone’s critical path.

The second is bounding the queue depth. A device performs best with enough requests in flight to keep its dies busy and worst with so many that the device’s internal queues overflow and requests wait in the controller. A scheduler can hold requests back, keeping the number in flight near a target, which reduces latency for the requests that are dispatched while leaving the rest queued. This is the opposite of the throughput-maximizing strategy, and which one is correct depends on whether the workload is a batch job or an interactive service.

The third is fairness. Several processes submitting to one device can starve each other if one submits far more, and a scheduler can assign each a share of the dispatch slots. Without it, a large sequential write from one process delays a small read from another by however long the write takes to drain.

What scheduling cannot buy on flash is address locality. Two requests to adjacent logical blocks have no guaranteed physical adjacency, because the mapping is not the host’s to know. Merging adjacent requests still helps, because it reduces command count and descriptor overhead, but it does not improve the device’s internal access pattern in the way it did for a disk.

The three shapes in the Linux block layer

The multi-queue block layer exposes a small set of schedulers, and the choice is per device.

The none scheduler is the absence of one. Requests go to the hardware queue as soon as a tag is available, in submission order, and the only batching is the per-task plug described in multi-queue dispatch. This is the right choice for a device that is itself good at scheduling, which is most NVMe devices: the controller has its own queues, its own arbitration between them, and its own knowledge of which die is free. Adding a host-side scheduler in front of it duplicates work and adds latency. The cost of none is that the host has no control over the read/write mix or the depth; a device that handles both badly will do so.

The deadline scheduler keeps two queues, one for reads and one for writes, and assigns each request an expiry. Dispatch takes the request closest to expiry, with reads given a shorter deadline than writes by default. The deadlines are not promises to the application; they are a mechanism for ensuring that no request waits indefinitely behind a stream of others. A request whose deadline passes is dispatched ahead of younger requests, which bounds the worst-case wait and gives the read/write priority a concrete expression. The default read expiry is on the order of hundreds of milliseconds and the write expiry several times that, both adjustable.

The Kyber scheduler targets fast devices with a small number of hardware queues, and it does so by throttling rather than by reordering. Requests are separated into classes, reads and writes and discards, and each class gets its own queue and a cap on how many of its requests may be in flight at once. The caps are not fixed: each class has a target latency, and the scheduler shrinks the cap for a class whose completions are arriving slower than that target and grows it again when latency improves. The effect is that a flood of one class cannot occupy the device’s whole depth, and the host’s in-flight count stays near what the device can service rather than at whatever the submitters offer. It is the wrong choice for a device that prefers a continuously full queue, and the right one for a device whose latency degrades sharply past a certain depth.

/* Deadline dispatch: expired first, then the earliest deadline.
 * The queue primitives are elided; the policy is the whole content. */
struct request *deadline_next(struct deadline_queue *dq, uint64_t now)
{
    struct request *rq;

    rq = peek_expired(&dq->reads, now);          /* reads first: shorter deadline */
    if (rq)
        return rq;
    rq = peek_expired(&dq->writes, now);
    if (rq)
        return rq;

    /* Nothing expired: take the earliest deadline, preferring reads on ties. */
    if (earliest_deadline(&dq->reads) <= earliest_deadline(&dq->writes))
        return peek_earliest(&dq->reads);
    return peek_earliest(&dq->writes);
}

The important property is that the scheduler’s decisions are cheap: two ordered structures and a comparison. A scheduler that needs to scan the queue to decide cannot run on the submission path of a device doing hundreds of thousands of operations per second.

Queue depth as the real control

The number of requests the host allows in flight determines both throughput and latency, and the relation is not linear. Starting from one request in flight, adding more increases throughput because the device can overlap work across dies, and the gain continues until the device’s internal parallelism is saturated. Past that point, additional requests queue inside the device and each one’s latency grows by the service time of those ahead of it, while throughput stays flat.

The knee is a property of the device: the number of dies, the number of channels, and the controller’s ability to reorder. A consumer drive with a handful of channels saturates at a modest depth, and a datacentre drive with many more saturates higher. Little’s law relates the quantities: the number of requests in flight equals throughput multiplied by latency. A device with a service time of 100 microseconds per request and a depth of 32 can sustain 32/0.0001 = 320,000 operations per second if it can truly process 32 concurrently, and a host that offers only 4 gets one eighth of that.

The host-side depth is bounded by the tag space in the hardware queue, which is the device’s advertised queue depth. Exceeding it is impossible, since a request without a tag waits; setting it too low leaves the device underfed. The usual configuration lets the device advertise its depth and lets the block layer use it, and the scheduler’s role is to decide how many of those slots to fill at once.

Latency-sensitive workloads want the opposite of the throughput-maximizing setting. A single request’s latency is roughly the service time plus the queueing delay behind requests dispatched before it, so a depth of 1 gives the minimum latency and a fraction of the throughput. A service that must answer in a bounded time keeps the depth low and accepts the throughput loss, or uses a device with more parallelism so that a low depth still fills it.

Interaction with the filesystem’s own batching

The scheduler is not the only layer that batches. A filesystem submitting a large write builds a chain of bios and submits them together; a journal commit submits its blocks and then a flush; a readahead window submits a run of read requests. The block layer sees these as a burst, and the scheduler’s decisions apply to the burst as a whole. A filesystem that submits a hundred adjacent requests in one call has already produced the locality that the scheduler would otherwise try to create, and the scheduler’s contribution is limited to ordering them against other work.

The reverse case is a filesystem that submits one small request at a time, each waiting for completion. That pattern leaves the device with a depth of one and no opportunity to overlap, and no scheduler can fix it because the limitation is the submitter’s. The fix is in the filesystem or the application: asynchronous submission, larger writes, or readahead. This is the most common reason a device underperforms its specification, and it is invisible in the scheduler’s statistics because the scheduler never had a queue to schedule.

Separating host-side delay from device-side delay

The block layer exposes per-device statistics: requests completed, bytes transferred, and the time spent in the queue and in the device. The distinction between queue time and device time separates the two causes of latency. Time in the queue is the scheduler holding the request or the depth limit being reached; time in the device is the device’s own service, including any internal queuing. A device showing high device time with low queue time is saturated internally; one showing high queue time with low device time is being throttled by the host.

The histogram of request latencies is more informative than the mean. A device that occasionally takes a millisecond for a request that usually takes a hundred microseconds has a tail caused by garbage collection, an erase, or a channel conflict, and the mean hides it. Schedulers cannot remove that tail; only reducing the load or the device’s internal work can. The tail is the reason interactive workloads on shared devices are configured with a depth limit even when throughput would favour more.