Writeback Scheduling and Merging at the Block Layer

Two writes of 4 KiB to adjacent file offsets can leave the machine as one 8 KiB request, or as two separate ones, or as one large request that contains other data as well. Which of those happens is decided by a layer that sits below the filesystem and above the driver, and it is the layer whose behaviour determines queue depth, device utilisation, and the latency of a request once it is issued. Understanding it means separating two distinct jobs: combining requests, and choosing their order.

Merging is an address comparison

When a file write reaches the block layer, the filesystem has already translated the logical offset into a device-relative sector number. The block layer maintains a queue of pending requests per device. On insertion it checks whether the new request adjoins an existing one.

An insertion at the front or back of an existing request, where the sector ranges are contiguous, is a simple merge: the existing request grows and its data is concatenated. That is the cheapest and most common case, and it is why a sequential writer’s requests grow. An insertion in the middle of an existing request, where the new range is entirely contained in an already-queued range, allows the new request to be dropped after its data is copied into the queued one — relevant when two writers touch overlapping sectors.

The merge is constrained by the physical limits of the request: the maximum number of sectors (max_sectors_kb), the number of hardware segments if the device uses scatter-gather, and the number of distinct memory pages the request touches. A merged request whose data is not physically contiguous needs a segment list, and each additional segment costs an entry in the driver’s table. When the limit is reached, a further merge is refused and the request stays separate even though the sectors adjoin. This is why large sequential writes on a fragmented physical layout produce more requests than a naive count of bytes would predict.

The other important limit is the request’s start: a device with a 4096-byte physical block size can be told about a request starting at an offset not aligned to 4096, but that request cannot benefit from the device’s internal read-modify-write avoidance. The block layer exposes and applies alignment constraints so that requests are built to the device’s preference, which sometimes means not merging two requests that would produce a misaligned combination.

Ordering is a scheduling decision, and its value depends on the medium

Rotational media reward ordering because seek time dwarfs transfer time. A scheduler that sorts requests by sector reduces total head movement to roughly the cost of one sweep per batch, and a read of the nearest pending sector can be served before one that would need a long seek. The elevator metaphor is exact: requests are sorted, and the head moves in one direction until there is nothing left, then reverses. Starvation is controlled by ageing requests that have waited too long so that a steady stream of arrivals cannot delay them indefinitely.

Flash media have no seek time, but they have erase-block granularity and internal parallelism across channels and dies. Sorting by address gains little; what matters is having enough requests in flight to fill the device’s internal pipelines. This motivated the multi-queue design in which each CPU has its own submission and completion queues, and the scheduler, if there is one, operates on per-queue structures. The classic single-queue elevator with a global lock is what the multi-queue redesign removed.

The scheduler is a name for a policy, and the policies that matter in current practice are few: a simple one that does minimal reordering and relies on the device’s internal scheduler, and a more expensive one that maintains a per-process fairness tree. A device that supports command queueing with a deep hardware queue often does better with the first, because the device’s firmware already knows about its own erase blocks and channels.

Depth is the variable that changes results more than the policy name. With a queue depth of one, no scheduler can reorder anything: each request waits for the previous one to complete. With depth 32, both merging and ordering can act, and the device can overlap internal work. A benchmark that reports scheduler A is faster than scheduler B without reporting the depth, the concurrency, and the read/write ratio is not a comparison of schedulers.

Writeback arrives in bursts, and bursts are what make merging possible

The flusher described in What write() Actually Does Before Data Leaves the Process does not submit pages one at a time in the order they were dirtied. It walks each inode’s page tree and submits runs of dirty pages, then moves to the next inode. Runs that are contiguous in the file and contiguous on disk become large requests; runs that are contiguous in the file but scattered on disk become many small ones.

That asymmetry is the main reason a filesystem that allocates sequentially outperforms one that fragments. It is not a merge failure at the block layer; the layer merges what it is given, and the filesystem gave it sectors that do not adjoin. Defragmentation, delayed allocation, and extent-based allocation all exist to give the block layer larger units to work with.

Writes also interact with reads at this layer. A read that must wait behind a queue full of writeback requests sees latency proportional to the queue, and the flusher has no knowledge of the reader’s urgency. Some schedulers mitigate this by giving reads priority; the mechanism works only while the queue holds both. Once the queue is saturated by writes and the device’s write buffer is full, a newly issued read still waits.

Completion, tagging, and the cost of an untagged queue

Modern devices report completion through tagged queues: the driver posts a request with a tag, and the device reports which tag finished. Ordering on the completion side is not preserved, so the block layer must track each request’s completion independently, and a filesystem that requires ordering, such as one that must write a data block before a journal commit referencing it, expresses that requirement through flush and fence operations rather than relying on arrival order.

A device without tags, or one configured in a mode that serialises, has a depth of one per queue and the ordering of completions follows the order of issue. That is a safer model but a slower one, and the gap between a queue of depth one and a queue of depth thirty-two on a flash device is the reason asynchronous interfaces exist at all.

The point is structural: the block layer can only merge and the device can only pipeline what has already been issued. A synchronous loop that waits for each operation before starting the next gives the layer a queue depth of one, and no scheduler can recover from that.

/* Depth from the application, not from the scheduler. */
for (size_t i = 0; i < batch; i++) {
    submit_read(fd, bufs[i], len, offsets[i]);   /* does not wait */
}
for (size_t i = 0; i < batch; i++)
    wait_read(bufs[i]);                          /* reap in any order */

Where the layer cannot help

Requests that are already maximal cannot be merged further: a device reporting a 128 KiB maximum will not accept a 1 MiB request no matter how sequential the access is, and the split happens either in the filesystem’s direct I/O path or at the block layer’s bio splitting. The size the device sees is capped by a queue attribute, so changing it changes results, and defaults differ between devices and distributions.

Nor can the layer merge across a barrier: a flush request, a discard, or a zone-reset command breaks the ordering of the queue and prevents requests on either side from combining. A workload that depends on frequent flushes, described in What fsync Guarantees and What It Costs on Real Devices, therefore sees smaller merged requests than its write sizes suggest.

The device itself adds a later stage of scheduling, in firmware, which is opaque. Its own write buffering, garbage collection, and internal over-provisioning determine how much of the layered request stream becomes efficient media operations. That is the subject of Write Amplification and Garbage Collection in Flash Translation Layers, and it is why the block layer’s view is a good predictor of driver-level behaviour but not always of the number of erase operations underneath.