The Coalescing Ring Buffer

2013-03-07

4 min read

The Coalescing Ring Buffer is the first component of the LMAX Collections Library we are open-sourcing today. It is a component that we have written in Java to efficiently buffer messages between a producer and a consumer thread where only the latest value for a given topic is of interest. All other messages can be discarded immediately.

The Problem of Market Data

Let’s imagine we are trying to write an automated trading system that listens to all stock price updates on an exchange in order to find under-valued stocks. The following diagram shows an exchange sending price updates for 3 stock symbols being queued for processing by our trading system.

marketData1

Deciding if the latest price for any stock is a good investment takes a certain amount of time. So it is quite possible that a price will change before the old price has been processed.

marketData2

Since we are only interested in the latest prices, considering Red Hat at 55 is a waste of memory and time. It would be better to update the already queued price of 55 to 56.

marketData3

This is the problem that the Coalescing Ring Buffer solves. It is a buffer that holds the incoming price updates and checks if it can update an existing value instead of growing the buffer before the consumer is ready to process them.

Great Engineers Steal

The key insight that makes the LMAX Disruptor so fast is an understanding of how modern CPUs are designed. Martin Thompson explains all this very well on his blog Mechanical Sympathy. I would very strongly recommend that anyone with an interest in designing high performance software, to read every article on his blog from the beginning.

The Coalescing Ring Buffer borrows the following design principles from the Disruptor:

using arrays as data structures because of their memory locality
using lock-free concurrency as it avoids kernel arbitration
using the single-writer principle to avoid cache line contention

I really just want to introduce the Coalescing Ring Buffer here but I will go into much more detail about its design and performance in future posts.

Ok Great, How Do I Use It?

First, download the Coalescing Ring Buffer jar and the source zip.

Then create a data class to represent the values we want the buffer to hold. In our example we will simply have a stock symbol and price:

public class StockPrice {
    public final String symbol;
    public final double price;

    public StockPrice(String symbol, double price) {
        this.symbol = symbol;
        this.price = price;
    }

    @Override
    public String toString() {
        return String.format("%s =\t$%.2f", symbol, price);
    }
}

Next create the buffer. The buffer takes two type arguments: the key and value types. Offering a value to the buffer with a key that equals another key already in the buffer causes the buffer to overwrite the existing value instead of growing larger.

CoalescingBuffer<String, StockPrice> buffer = new CoalescingRingBuffer<String, StockPrice>(8);

Please note that for performance reasons, the size of the buffer must be a power of 2 (more on this in future posts).

On the producer thread we can now offer the values as follows:

String symbol = "RHT";
StockPrice stockPrice = new StockPrice(symbol, 123.45);

boolean success = buffer.offer(symbol, stockPrice);

if (!success) {
    throw new AssertionError("offer of " + stockPrice + " failed");
}

Since the buffer is non-blocking, it signals an overflow by returning false. The correct way to handle the overflow condition depends on your application, but here we will simply throw an AsserionError.

On the consumer thread we collect values from the buffer in batches as follows:

Collection<StockPrice> prices = new ArrayList<StockPrice>();

while (!stop) {
    buffer.poll(prices);

    for (StockPrice price : prices) {
        System.out.println(price);
    }

    prices.clear();
}

The call to poll will transfer all StockPrices currently in the buffer to the prices collection and remove them from the buffer. If the buffer is empty, poll will return immediately without adding anything to the prices collection.

You can optionally specify the maximum number of items that should be transferred to the collection on each poll. Please note that the buffer only adds to the collection, it is the client’s responsibility to clear the buffer before subsequent calls to poll.

The full code for this example can be found here.

Current Limitations

Version 1.0 of the Coalescing Ring Buffer has the following limitations:

it supports only one producer and one consumer
it has no wait-strategy for the consumer thread
there is a small but non-zero probability that the consumer will see some duplicated values

If you get a chance to try it, please let me know what you think.