Disruptor

Disruptor is a lock-free message queue introduced by LMAX in 2011. Its 45-minute presentation contains many ideas worth exploring.

Background

First, let’s examine the performance cost of various locks in multithreaded programming, using a counter:

1
static long counter = 0
2

3
private static void increment() {
4
  for (long l = 0; l < 500000000L; l++) {
5
    counter++;
6
  }
7
}

Redefining the counter with common multithreading approaches gives these results:

Locking can cost several or even hundreds of times more than the actual application logic. A commonly used queue such as ArrayListQueue, with one producer and one consumer, works as follows:

The producer adds data while the consumer retrieves and removes it. Both threads change the queue’s state, so a lock must ensure consistency between them. This lock is often the bottleneck. There are two competing resources:

• Data: the producer adds it and the consumer deletes it.
• Metadata: remaining queue capacity, the latest data index, and so on.

Contention Free Design

The consumer changes state because it must remove data. What if it did not remove data, but instead tracked its position with a cursor? Could that avoid costly locking? Disruptor stores data in a RingBuffer. The producer maintains a Sequence as the message index, and each consumer maintains its own index tracking its position. The overall structure is:

The only shared variable with contention is sequence: a consumer must ensure that its index is below the queue’s highest sequence. Declaring sequence volatile is straightforward, but can it be optimized further?

Optimization

To optimize beyond volatile, we first need to understand its cost. The diagram shows a multicore CPU. CPUs optimize instruction execution to use caches effectively, for example by pipelining and reordering instructions to maximize cache hits. Under the JVM’s happens-before rules, volatile writes must precede reads, prohibiting reordering. After a volatile modification, a Store Barrier forces cached data from the Store Buffer into memory. A volatile read inserts a Load Barrier to fetch the latest data from memory. Load Barriers are relatively expensive.

For a message queue, if reading the very latest sequence on every access is unnecessary, instruction reordering need not be prohibited: reading an older cached value temporarily is acceptable. Updating sequence inserts a StoreStore Barrier, while the CPU refreshes the Load Buffer automatically. Reads can thus come from the CPU cache. AtomicLong’s lazySet provides this behavior.

References

• Understanding the Disruptor, a Beginner’s Guide to Hardcore Concurrency -Trisha Gee & Mike Barker
• Memory Barriers/Fences