How LinkedTransferQueue Works: The Smart Lock‑Free Queue Behind Java Concurrency

LinkedTransferQueue Overview

LinkedTransferQueue is an unbounded, FIFO blocking queue introduced in JDK 7. It acts as a superset of ConcurrentLinkedQueue, SynchronousQueue (fair mode), and unbounded LinkedBlockingQueue, providing both capacity and lock‑free transfer capabilities.

Core Concepts

The queue uses a pre‑allocation mode : a consumer thread takes an element immediately if available; otherwise it creates a placeholder node and parks until a producer arrives. This behavior resembles SynchronousQueue but without locking the entire queue.

Structure

The queue consists of a linked list of Node objects. Each node contains: isData: indicates whether the node holds data (producer) or a request (consumer). item: the actual data element; null for request nodes. next: reference to the next node in the list. waiter: the thread parked on this node when it is waiting for a match.

Key Methods

The queue implements TransferQueue, adding methods such as tryTransfer, transfer, tryTransfer(E e, long timeout, TimeUnit unit), and the standard put, offer, add, take, poll operations. All of these delegate to a central private method xfer(E e, boolean haveData, int how, long nanos).

The xfer Algorithm

xfer

attempts to match a producer node with a waiting consumer node (or vice‑versa). It scans from the head, looking for an unmatched node of opposite type. When a match is found, it uses CAS on the item field, unparks the waiting thread, and returns the transferred element.

If no match is found, the method creates a new node (unless how == NOW) and appends it to the tail via tryAppend. Depending on the how parameter, the thread may return immediately ( NOW), spin briefly ( ASYNC), or block awaiting a match ( SYNC or TIMED).

Appending Nodes

tryAppend(Node s, boolean haveData)

walks from the tail, attempts a CAS on the next pointer of the last node, and updates the tail pointer. If the queue is empty, it also CASes the head to the new node.

Blocking Await

When a thread must wait ( SYNC or TIMED), it calls awaitMatch. The method first spins for a short period, then parks the thread using LockSupport.park (or parkNanos for timed waits). If the thread is interrupted or the timeout expires, it attempts to cancel the node via casItem and removes it from the list with unsplice.

Cancellation and Cleanup

unsplice(Node pred, Node s)

removes a cancelled node from the list, updating predecessor links and possibly advancing the head. The queue also performs periodic sweeping of cancelled nodes when a threshold of SWEEP_THRESHOLD is reached.

Summary of Operation

All public operations ultimately invoke xfer with different how values.

If a matching node exists, the algorithm atomically transfers the element and unparks the waiting thread.

If no match is found, the node is appended to the tail; for non‑asynchronous modes the thread blocks until a counterpart arrives.

The design achieves high concurrency by avoiding global locks and using CAS operations on individual nodes.

Example Scenarios

1. Producer after consumer : a consumer node is waiting; a producer arrives, matches, and the consumer receives the element.

2. Consumer after producer : a producer node is waiting; a consumer arrives, matches, and the producer’s element is transferred.

3. No immediate match : the node is appended and the thread blocks (or returns immediately for NOW operations).

Overall, LinkedTransferQueue provides a highly scalable, lock‑free mechanism for transferring data between threads, making it suitable for high‑throughput concurrent applications.