Multi-Queue Block Dispatch and Why One Lock Was Not Enough

A block device driver has one function that submits a request to the hardware and one that reports its completion. Everything between the filesystem’s write and that submission is the block layer: it merges adjacent requests, orders them, accounts them against limits, and decides when to hand them over. Until the early 2010s that layer kept all pending requests for a device in a single queue protected by a single lock. That design was adequate for a disk with one head and a queue of a few dozen commands. It became the bottleneck when devices could sustain hundreds of thousands of operations per second and systems had tens of cores submitting concurrently.

The shape of the old bottleneck

A single request queue per device means every submission takes the queue lock, every completion takes it, and every merge decision reads the queue’s tail. The critical section is short, but it is on the path of every I/O, and the lock is contended by every CPU. Two effects compound. The first is direct: cores queue up for the lock, and the time spent waiting is time not spent submitting. The second is indirect and worse: the cache line holding the lock and the queue’s counters is written by every core, so it bounces between per-core caches instead of staying resident in one. A workload with many threads issuing small I/Os spends a growing fraction of its time moving that line.

The scheduler made it worse rather than better. Elevator-style merging wants to see all pending requests together, because a merge is only possible if the neighbour is already queued. A per-device queue is the natural structure for that, and it is the structure that cannot scale.

Splitting the queue by core and by hardware

The replacement splits the queue in two dimensions. The software side has one queue per CPU, or per group of CPUs, and a submission from a CPU goes to its own queue with no cross-core synchronization in the common case. The hardware side has one queue per hardware dispatch channel the device exposes: an NVMe device may expose dozens or hundreds of submission queues, each with its own doorbell register, so a submission to a hardware queue touches only that queue’s registers.

Between the two sits a mapping. Each software queue is bound to one or more hardware queues, and the binding is arranged so that the CPUs sharing a hardware queue are the ones that share a cache or a NUMA node. The intent is that a submission stays on one core, reaches one software queue, and is handed to one hardware queue whose doorbell that core already has mapped.

The number of hardware queues is a property of the device and its driver, bounded by what the device supports and by the number of CPUs. A device that exposes a single queue, such as a virtio device configured without multiqueue, degenerates to the old shape with extra indirection; the mechanism pays off only when the device has real parallelism to offer.

/* A model of the split, not the kernel's own types. A submission from one CPU
 * reaches that CPU's software queue and then a device queue with a free tag.
 * Tag-map and queue-selection helpers are elided. */
struct sw_queue {                 /* one per CPU */
    struct hw_queue *hw;          /* the queue this CPU is mapped to */
    struct bio_list   plugged;    /* requests held until the plug is released */
};

struct hw_queue {                 /* one per device dispatch channel */
    unsigned int index;           /* selects the device's doorbell register */
    unsigned int nr_tags;         /* in-flight command slots */
    unsigned long tag_map;        /* one bit per free slot */
};

static struct hw_queue *submit(struct sw_queue *sw, struct bio *bio)
{
    struct hw_queue *hw = sw->hw;

    if (tag_map_full(&hw->tag_map)) {
        hw = alternate_queue(sw);     /* fallback, off the fast path */
        if (!hw)
            return NULL;              /* caller keeps the request queued */
    }
    reserve_tag(&hw->tag_map, bio);
    return hw;
}

The tag allocation is the second half of the design. A tag is an index into the device’s in-flight request table, and a hardware queue has a fixed number of them, matching the queue depth the device supports. Getting a tag is an atomic bit test-and-set on a per-queue bitmap, which is uncontended when the CPU is working on its own hardware queue and contended only when several CPUs share one. The tag becomes the request’s identity for the device: the completion carries the tag, and the driver uses it to find the request without a search.

Dispatch, plugging, and the scheduler’s new position

Splitting the queue changes what a scheduler can see. A per-CPU queue holds only the requests that CPU submitted, so an elevator merging a request with its neighbour sees a small fraction of the device’s pending work. The block layer’s response is to keep a per-task plug: submissions from one task accumulate in a small list attached to the task, and the list is flushed to the hardware queue at a boundary the task controls, such as a fsync, a scheduler yield, or a full plug. A plug released by fsync is also where the durability barrier lands, as described in flush and FUA ordering.

Plugging recovers locality without a global queue. A filesystem writing a large file submits many adjacent blocks from one task, and the plug holds them until they can be dispatched as a batch. The device receives a run of adjacent logical addresses, which is exactly what its internal write path wants. The merge opportunity is found within the plug rather than across the device, and the plug is per-task so there is no contention.

The scheduler, when one is configured, operates on the software queue rather than on a single device-wide list. Its job is to order requests within the queue by a policy: deadline, token throttling, or none. On a device with a deep queue and no seek cost, the scheduler’s value is in limiting the queue depth and in grouping reads ahead of writes, not in minimizing head movement. On a device that benefits from batching, it is in producing long runs. The choice of scheduler and its parameters is examined in I/O scheduler selection for flash and disks.

Completion and the return path

A completion arrives on an interrupt, or on a polled queue when the driver is configured for polling. The driver finds the request by tag, marks it complete, and the block layer’s completion path ends the request and calls the submitter’s callback, which for a filesystem write is the path that releases the page and, for a synchronous write, wakes the waiter.

Completions are not necessarily handled on the CPU that submitted. A device may deliver an interrupt to any CPU, and a driver may steer completions to the submitting CPU or to a separate set of CPUs. Steering to the submitter improves cache locality for the request’s data structures but concentrates interrupt load; steering away keeps the submitting core free to submit but costs a cache transfer of the request. Drivers choose based on whether the workload is latency-sensitive or throughput-sensitive, and the choice is exposed as a queue parameter rather than fixed.

The tag must not be released until the request is fully done, including any post-completion work the driver does. A tag released early allows the same slot to be reused for a new request whose completion then races with the old one’s, and the driver cannot tell which is which. This is why tag lifetime is tied to the request’s end rather than to the interrupt.

Failure modes specific to the split

The fallback path is the first. When a CPU’s mapped hardware queue has no free tags, the submission must go somewhere: to another hardware queue with tags available, or back to the software queue to be retried. Choosing the wrong fallback defeats the mapping and reintroduces cross-core contention, because every core under pressure converges on the same spare queue. The mapping therefore has to be computed with the device’s queue count and the CPU topology in mind, and a mismatch between the two, more CPUs than hardware queues, is the case where contention returns.

The second is queue depth accounting. A device’s advertised queue depth is a limit on in-flight commands, and the block layer must not exceed it. With multiple hardware queues each holding tags, the aggregate is the sum, and a driver that reports a per-queue depth larger than the device supports will overflow the device’s internal table and get commands rejected. Devices report their limits through the transport, and the block layer’s queue limits are derived from them rather than assumed.

The third is the interaction with memory. Requests and their payloads are described by scatter-gather lists, and a device’s DMA engine may have a limit on the number of segments per request or on the address range it can reach. A request that exceeds the segment limit must be split, and splitting in a multi-queue layer means the pieces may go to different hardware queues, which means they may complete out of order. The block layer preserves ordering only within a request or within an ordered sequence, not across independent requests, so a split write’s pieces can land in any order and the device must still produce the correct final contents. On a device that guarantees only per-range ordering, that is fine; on one that reorders within a range, the split must be accompanied by a flush or must be avoided.

What remains single-threaded

A few things in the block layer are still global per device: the queue limits, the statistics counters, and the elevator’s configuration. They are read-mostly and updated rarely, so their contention is negligible compared with the submission path. The one exception is the queue’s freeze and drain operations, used for suspending a queue during a reconfiguration or a device reset, which must wait for all in-flight requests across all hardware queues. A drain is inherently a global operation and its latency is the tail of the in-flight request distribution, which is why a device reset on a busy queue can take as long as the slowest outstanding command. For the same reason, the depth a host allows in flight is a load control rather than a throughput knob once the device is saturated, as covered in scheduler selection and queue depth.

The design’s lesson generalizes beyond this layer. A shared queue with a lock scales to the number of cores only while the critical section is short relative to the work between submissions, and block I/O crossed that threshold when devices became fast enough that the lock was the dominant cost. The same split, per-CPU structures with a mapping to shared hardware resources, appears in network receive paths and in allocator front ends for the same reason.