A lock-free array-based bounded queue. It is thread-safe and can be used in multiple-producer/multiple-consumer (MPMC) setting.

Main concepts

A simple array-based queue of size N uses an array buf of size N as an underlying storage. There are 2 pointers head and tail. The element is enqueued into buf at position tail % N and dequeued from head % N. Each time an enqueue happens tail is incremented, similarly when dequeue happens head is incremented.

Since pointers wrap around the array as they get incremented such data structure is also called a circular buffer or a ring buffer.

Because queue is bounded, enqueue and dequeue may fail, which is captured in the semantics of offer and poll methods.

Using offer as an example, the algorithm can be broken down roughly into three steps:

1. Find a place to insert an element. 2. Reserve this place, put an element and make it visible to other threads (store and publish). 3. If there was no place on step 1 return false, otherwise returns true.

Steps 1 and 2 are usually done in a loop to accommodate the possibility of failure due to race. Depending on the implementation of these steps the resulting queue will have different characteristics. For instance, the more sub-steps are between reserve and publish in step 2, the higher is the chance that one thread will delay other threads due to being descheduled.

Notes on the design

The queue uses a buf array to store elements. It uses seq array to store longs which serve as: 1. an indicator to producer/consumer threads whether the slot is right for enqueue/dequeue, 2. an indicator whether the queue is empty/full, 3. a mechanism to publish changes to buf via volatile write (can even be relaxed to ordered store). See comments in offer/poll methods for more details on seq.

The benefit of using seq + head/tail counters is that there are no allocations during enqueue/dequeue and very little overhead. The downside is it doubles (on 64bit) or triples (compressed OOPs) the amount of memory needed for a queue.

Concurrent enqueues and concurrent dequeues are possible. However there is no helping, so threads can delay other threads, and thus the queue doesn't provide full set of lock-free guarantees. In practice it's usually not a problem, since benefits are simplicity, zero GC pressure and speed.

There are 2 implementations of a RingBuffer: 1. RingBufferArb that supports queues with arbitrary capacity; 2. RingBufferPow2 that supports queues with only power of 2 capacities.

The reason is head % N and tail % N are rather cheap when can be done as a simple mask (N is pow 2), and pretty expensive when involve an idiv instruction. The difference is especially pronounced in tight loops (see. RoundtripBenchmark).

To ensure good performance reads/writes to head and tail fields need to be independent, e.g. they shouldn't fall on the same (adjacent) cache-line.

We can make those counters regular volatile long fields and space them out, but we still need a way to do CAS on them. The only way to do this except Unsafe is to use AtomicLongFieldUpdater, which is exactly what we have here.