Tagged queuing

Tagged queuing (also called tagged command queuing or TCQ) is a method for allowing a hardware device or controller to process commands received from a device driver out of order. The technique requires that the device driver attach a numeric identifier, called a tag, to each command; the controller or device uses these tags to match completed operations to the original requests regardless of the order in which they were serviced. Tagged queuing was first standardised in the SCSI-2 specification in the early 1990s and subsequently influenced queuing designs in ATA, Serial ATA (SATA), Serial Attached SCSI (SAS), and NVMe interfaces.

Background and motivation

Before tagged queuing was introduced, a host system could issue only one command at a time to a storage device. The device driver was therefore responsible for determining the most efficient order in which to submit requests, based on its own — often imprecise — model of the device's internal state. This arrangement had two significant drawbacks: the driver lacked accurate knowledge of the physical layout of data on the media, and requests from multiple processes had to be serialised through a single pipeline.

Tagged queuing addressed both problems by permitting the host to submit a backlog of pending commands — a queue — which the device itself then reorders for optimal execution. Because the device has direct knowledge of its own geometry (the current position of the read/write head, rotation speed, and sector layout), it can schedule commands far more efficiently than a driver operating at a higher level of abstraction.

In multi-user environments the benefit is particularly pronounced. A single-user workstation with localised, sequential I/O gains relatively little from command reordering. However, a server handling simultaneous requests from many clients, each targeting a different region of a disk platter, can see dramatic throughput improvements because the drive can group nearby sectors together rather than traversing the full platter surface repeatedly.

How tagged queuing works

Tag assignment

When tagged queuing is active, the device driver assigns a unique numeric tag to each I/O command before submitting it to the host bus adapter. The tag travels with the command through the interface bus and is stored by the target device alongside the command in its internal queue. When the device finishes executing a command, it returns the tag to the host along with the result data, allowing the driver and operating system to match the completion to the original request.

Rotational position optimisation

For hard disk drives the primary benefit of command reordering is the reduction of seek time and rotational latency. A naive approach processes commands in arrival order, which may require the read/write head to traverse the platter back and forth across widely separated sectors. With a queue of outstanding commands, the drive's firmware can apply a scheduling algorithm — analogous to the elevator algorithm used by operating-system I/O schedulers — to group nearby sectors and complete the same set of requests in far fewer platter rotations. Studies of rotational position optimisation (RPO) scheduling show that, when multiple commands are pending, serving requests in order of proximity to the current head position (shortest positioning time first, or SPTF) consistently outperforms sequential dispatch.

Queue depth

Queue depth refers to the maximum number of commands that may be outstanding simultaneously. A deeper queue gives the device more commands to choose from when optimising execution order, which generally improves throughput at the cost of higher memory usage within the device. Different interface standards specify different maximum queue depths; see the sections below for per-technology values.

SCSI Tagged Command Queuing

Tagged queuing was introduced formally in the SCSI-2 specification, codified as ANSI standard X3.131-1994, though drives implementing it appeared in the early 1990s during the standard's development.

Queue tag message types

SCSI-2 defines three distinct queue tag message types that govern how a target device may reorder queued commands:

• Simple Queue Tag: The target may execute the command in any order it considers optimal relative to other simple-tagged commands in the queue. This is the most commonly used mode and yields the greatest performance benefit from reordering.
• Ordered Queue Tag: The target must execute all previously queued simple-tagged commands before this command, and must execute this command before any subsequently queued simple-tagged commands. This mode allows an initiator to enforce ordering when data dependencies require it.
• Head of Queue Tag: The command is placed at the front of the execution queue, ahead of all other pending commands. Multiple consecutive head-of-queue commands are processed in last-in-first-out order. Because heavy use of this mode can starve other queued commands, it is reserved for high-priority or time-sensitive operations.

Tag mechanics

An initiator specifies the chosen tag type and a unique tag value during the MESSAGE OUT phase that follows the IDENTIFY message at the start of a command. The resulting combination of initiator, target, logical unit, and queue tag — termed an I_T_L_Q nexus in the SCSI specification — uniquely identifies each queued I/O process and allows the target to maintain independent context for each. If the device's queue is full it responds with a QUEUE FULL status rather than accepting additional commands. The specification prohibits mixing tagged and untagged queuing for the same logical unit during normal operation.

Queue depth in SCSI and SAS

SCSI-2 supports up to 256 outstanding commands per logical unit per initiator. The successor SCSI-3 protocol extended the tag field to 64 bits, theoretically permitting a vastly larger number of outstanding tasks, though practical implementations use far fewer. Serial Attached SCSI (SAS), which replaced parallel SCSI in most enterprise environments, retains Tagged Command Queuing and supports up to 256 outstanding commands per queue, making it well-suited for high-concurrency server workloads.

ATA Tagged Command Queuing

The Parallel ATA (PATA) specification incorporated a version of Tagged Command Queuing beginning with the ATA-4 standard, finalised in 1998. ATA TCQ supports up to 32 outstanding commands per device, compared with the larger queues available under SCSI.

Despite its availability in the standard, ATA TCQ achieved negligible market adoption. The ATA interface architecture at the time required host bus adapters to use ISA bus device protocols when communicating with the operating system, mandating that the CPU generate an interrupt for each transfer and participate actively in each data movement, resulting in high CPU utilisation. Because the CPU overhead largely cancelled out the performance benefit from command reordering, drive manufacturers and system builders had little incentive to implement or enable ATA TCQ. As a result, Parallel ATA systems typically operated with only one outstanding command per port despite the standard permitting more.

Serial ATA Native Command Queuing

Native Command Queuing (NCQ) is the Serial ATA implementation of command queuing, introduced with the SATA II generation of the specification in the mid-2000s. NCQ addressed the CPU overhead problem that hampered ATA TCQ by eliminating the requirement for CPU involvement in each data transfer. Instead, the drive signals the host controller directly about which command to service next, and the controller uses first-party DMA to move data without CPU intervention. NCQ also supports deferred interrupt reporting, allowing the controller to batch completion notifications and further reduce interrupt overhead.

NCQ uses two dedicated command codes — READ FPDMA QUEUED and WRITE FPDMA QUEUED — and assigns each command a tag value in the range 0 to 31, yielding a maximum queue depth of 32. From late 2004 onwards, most new SATA drive families shipped with NCQ support enabled.

Unlike SCSI TCQ, NCQ does not expose Simple, Ordered, and Head of Queue tag modes to the host. Reordering is performed entirely within the drive firmware and cannot be directly controlled by the initiator. Both the host controller and the drive must support NCQ for it to function; an NCQ-capable drive connected to a non-NCQ controller operates in compatibility mode without queuing, and vice versa.

NVMe and multi-queue architectures

NVM Express (NVMe), introduced in 2011 as a storage interface designed specifically for solid-state drives connected over PCI Express, extends the command queuing model far beyond what any earlier storage standard envisioned. Where SATA NCQ provides a single queue of up to 32 commands, NVMe supports up to 65,535 I/O queues, each capable of holding up to 65,535 commands simultaneously.

The multi-queue design serves a different purpose from the single-queue model of SCSI and SATA. In multi-core processors, each CPU core can be assigned its own dedicated submission queue and completion queue, avoiding the locking contention that arises when multiple cores compete to add commands to a shared queue. Each core submits commands directly to its own queue, and the NVMe controller distributes work across the many parallel flash memory channels inside the drive.

For solid-state drives, the original motivation for tagged queuing — minimising mechanical seek and rotational latency — does not apply, since flash memory has no moving parts and all locations are accessed in roughly equal time. However, command queuing remains important for SSDs because the devices contain multiple flash memory chips that can be accessed in parallel; a deeper queue allows the controller to dispatch operations to different chips simultaneously, improving aggregate throughput. NVMe also simplifies command submission compared with AHCI: it is sufficient to write new entries directly into the queue structures without first reading interface registers, reducing per-command overhead.

Performance considerations

Multi-user versus single-user workloads

Tagged queuing delivers the largest gains in environments where many independent I/O requests targeting different disk locations are outstanding simultaneously. In server workloads — databases, file servers, virtualisation hosts — the combination of deep queues and intelligent reordering can raise throughput dramatically. At a queue depth of one, TCQ-capable and non-TCQ controllers perform comparably; at queue depths of 16 or more, TCQ-capable controllers begin to show clear advantages; and at queue depths of 64 and beyond, throughput differences become very significant.

By contrast, single-user desktop workloads with mostly sequential, localised I/O gain little or nothing from command reordering, and the additional firmware complexity can impose a slight performance penalty in those conditions.

Interaction with RAID arrays

In RAID configurations, the performance benefit of tagged queuing scales with the number of drives. At low queue depths, a RAID array with tagged queuing offers only modest advantages over one without. As queue depth increases, the TCQ-enabled array can distribute reordered commands across multiple spindles, multiplying the throughput benefit.

Operating system and driver requirements

Realising the benefits of tagged queuing requires support at every layer of the storage stack: the drive firmware, the host bus adapter or controller, and the operating system driver must all cooperate. On Linux systems, the block layer exposes queue depth via the device's sysfs node, and I/O schedulers such as the Deadline or BFQ scheduler interact with device-level queuing to balance throughput and latency.

Comparison of command queuing across storage interfaces

Interface	Standard	Year introduced	Maximum queue depth	Tag modes exposed to host
Parallel SCSI (TCQ)	ANSI X3.131-1994 (SCSI-2)	c. 1990	256 per LUN per initiator	Simple, Ordered, Head of Queue
Parallel ATA (TCQ)	ATA-4	1998	32	Simple
Serial ATA (NCQ)	SATA II	c. 2004	32	None (firmware-controlled)
SAS (TCQ)	SAS-1	c. 2004	256	Simple, Ordered, Head of Queue
NVMe	NVMe 1.0	2011	65,535 per queue (up to 65,535 queues)	Per-queue priority levels

See also

• Native Command Queuing
• SCSI
• Serial ATA
• NVM Express
• Elevator algorithm
• Direct memory access
• Advanced Host Controller Interface

External links

• SCSI-2 Specification — Chapter 7: SCSI Commands and Status (University of Mainz archive)
• Native Command Queuing overview — Serial ATA International Organization
• NVM Express: An Introduction — NVM Express Organisation