Dissecting the Disruptor: How do I read from the ring buffer?

The next in the series of understanding the Disruptor pattern developed at LMAX.

After the last post we all understand ring buffers and how awesome they are.  Unfortunately for you, I have not said anything about how to actually populate them or read from them when you're using the Disruptor.

ConsumerBarriers and Consumers
I'm going to approach this slightly backwards, because it's probably easier to understand in the long run.  Assuming that some magic has populated it: how do you read something from the ring buffer?

(OK, I'm starting to regret using Paint/Gimp.  Although it's an excellent excuse to purchase a graphics tablet if I do continue down this road.  Also UML gurus are probably cursing my name right now.)

Your Consumer is the thread that wants to get something off the buffer.  It has access to a ConsumerBarrier, which is created by the RingBuffer and interacts with it on behalf of the Consumer.  While the ring buffer obviously needs a sequence number to figure out what the next available slot is, the consumer also needs to know which sequence number it's up to - each consumer needs to be able to figure out which sequence number it's expecting to see next.  So in the case above, the consumer has dealt with everything in the ring buffer up to and including 8, so it's expecting to see 9 next.

The consumer calls waitFor on the ConsumerBarrier with the sequence number it wants next

    final long availableSeq = consumerBarrier.waitFor(nextSequence);

and the ConsumerBarrier returns the highest sequence number available in the ring buffer - in the example above, 12.  The ConsumerBarrier has a WaitStrategy which it uses to decide how to wait for this sequence number - I won't go into details of that right now, the code has comments in outlining the advantages and disadvantages of each.

Now what?
So the consumer has been hanging around waiting for more stuff to get written to the ring buffer, and it's been told what has been written - entries 9, 10, 11 and 12.  Now they're there, the consumer can ask the ConsumerBarrier to fetch them.

As it's fetching them, the Consumer is updating its own cursor.

You should start to get a feel for how this helps to smooth latency spikes - instead of asking "Can I have the next one yet?  How about now?  Now?" for every individual item, the Consumer simply says "Let me know when you've got more than this number", and is told in return how many more entries it can grab.  Because these new entries have definitely been written (the ring buffer's sequence has been updated), and because the only things trying to get to these entries can only read them and not write to them, this can be done without locks.  Which is nice.  Not only is it safer and easier to code against, it's much faster not to use a lock.

And the added bonus - you can have multiple Consumers reading off the same RingBuffer, with no need for locks and no need for additional queues to coordinate between the different threads.  So you can really run your processing in parallel with the Disruptor coordinating the effort.

The BatchConsumer is an example of consumer code, and if you implement the BatchHandler you can get the BatchConsumer to do the heavy lifting I've outlined above.  Then it's easy to deal with the whole batch of entries processed (e.g. from 9-12 above) without having to fetch each one individually.

EDIT: Note that version 2.0 of the Disruptor uses different names to the ones in this article.  Please see my summary of the changes if you are confused about class names.

Dissecting the Disruptor: What's so special about a ring buffer?

Recently we open sourced the LMAX Disruptor, the key to what makes our exchange so fast.  Why did we open source it?  Well, we've realised that conventional wisdom around high performance programming is... a bit wrong. We've come up with a better, faster way to share data between threads, and it would be selfish not to share it with the world.  Plus it makes us look dead clever.

On the site you can download a technical article explaining what the Disruptor is and why it's so clever and fast.  I even get a writing credit on it, which is gratifying when all I really did is insert commas and re-phrase sentences I didn't understand.

However I find the whole thing a bit much to digest all at once, so I'm going to explain it in smaller pieces, as suits my NADD audience.

First up - the ring buffer.  Initially I was under the impression the Disruptor was just the ring buffer.  But I've come to realise that while this data structure is at the heart of the pattern, the clever bit about the Disruptor is controlling access to it.

What on earth is a ring buffer?
Well, it does what it says on the tin - it's a ring (it's circular and wraps), and you use it as a buffer to pass stuff from one context (one thread) to another:

(OK, I drew it in Paint.  I'm experimenting with sketch styles and hoping my OCD doesn't kick in and demand perfect circles and straight lines at precise angles).

So basically it's an array with a pointer to the next available slot.

As you keep filling up the buffer (and presumable reading from it too), the sequence keeps incrementing, wrapping around the ring:

To find the slot in the array that the current sequence points to you use a mod operation:

sequence mod array length = array index

So for the above ring buffer (using Java mod syntax): 12 % 10 = 2. Easy.

Actually it was a total accident that the picture had ten slots.  Powers of two work better because computers think in binary.

So what?
If you look at Wikipedia's entry on Circular Buffers, you'll see one major difference to the way we've implemented ours - we don't have a pointer to the end.  We only have the next available sequence number.  This is deliberate - the original reason we chose a ring buffer was so we could support reliable messaging.  We needed a store of the messages the service had sent, so when another service sent a nak to say they hadn't received some messages, it would be able to resend them.

The ring buffer seems ideal for this.  It stores the sequence to show where the end of the buffer is, and if it gets a nak it can replay everything from that point to the current sequence:

The difference between the ring buffer as we've implemented it, and the queues we had traditionally been using, is that we don't consume the items in the buffer - they stay there until they get over-written.  Which is why we don't need the "end" pointer you see in the Wikipedia version.  Deciding whether it's OK to wrap or not is managed outside of the data structure itself (this is part of the producer and consumer behaviour - if you can't wait for me to get round to blogging about it, check out the Disruptor site).

And it's so great because...?
So we use this data structure because it gives us some nice behaviour for reliable messaging.  It turns out though that it has some other nice characteristics.

Firstly, it's faster than something like a linked list because it's an array, and has a predictable pattern of access.  This is nice and CPU-cache-friendly - at the hardware level the entries can be pre-loaded, so the machine is not constantly going back to main memory to load the next item in the ring.

Secondly, it's an array and you can pre-allocate it up front, making the objects effectively immortal.  This means the garbage collector has pretty much nothing to do here.  Again, unlike a linked list which creates objects for every item added to the list - these then all need to be cleaned up when the item is no longer in the list.

The missing pieces
I haven't talked about how to prevent the ring wrapping, or specifics around how to write stuff to and read things from the ring buffer.  You'll also notice I've been comparing it to a data structure like a linked list, which I don't think anyone believes is the answer to the world's problems.

The interesting part comes when you compare the Disruptor with an implementation like a queue.  Queues usually take care of all the stuff like the start and end of the queue, adding and consuming items, and so forth.  All the stuff I haven't really touched on with the ring buffer.  That's because the ring buffer itself isn't responsible for these things, we've moved these concerns outside of the data structure.

For more details you're just going to have to read the paper or check out the code.  Or watch Mike and Martin at QCon San Francisco last year.  Or wait for me to have a spare five minutes to get my head around the rest of it.

A chance to see some of my actual code (even if it is C#)

Remember I posted about having to write .NET?

Well, the code and the tutorial are available for you, my lucky readers, to rip to pieces view.

I am not the only person responsible for this code though, so be kind.

Vote for the LJC

I nominated LMAX for a couple of JAX Innovation Awards, but unfortunately we did not get shortlisted :(

However, the London Java Community did!  So if you have a second please vote for the LJC for Top Java Ambassador

STAC London Summit

On Wednesday I tagged along to the STAC London Summit to provide backup for Mike, who was on the "The Future of Messaging Middleware" panel.

The panel consisted of two messaging providers, one hardware (Solace Systems) and one software (29West/Informatica), and two "users", Citihub and LMAX.    Obviously both providers were arguing that theirs was the best solution. But what I found interesting is that I came away with the impression that everyone was really on the same side - everyone wants to use or to provide the best system, but there are different approaches. Which one you adopt is likely to be influenced by how your team work and the hardware you have (or can obtain).

Mike touched on how we as developers need to do more than simply rely on fast messaging to provide our high performance.  At LMAX, we keep banging on about mechanical sympathy and clean, well designed code to make sure we make the most of the infrastructure.  He also got a dig in at JMS, which I don't think anyone disagreed with.

The main point I took away, however, is that although speed is very important in ultra high performance trading (of course), control is becoming almost more important: specifically configuration and monitoring.  Because it's all well and good having a super-fast messaging infrastructure, but if you can't get it to do what you want, or you can't see what it's doing, where the bottlenecks are, or even if you're using it properly, it's a massive waste of cash.

Throughout later presentations and panels, and some chat afterwards, I picked up the configuration/monitoring theme a few more times.  Fast is one thing, high availability is another, which should not be ignored simply for speed of execution.

Something else I heard a lot is how Java is totally unsuitable for high performance systems.  Well... we'd like to disprove that.  I guess we need need to get out there and start talking about why this is a myth.

I was impressed with the event actually.  It was such a contrast to TradeTech, which was all vendors and boys in suits who couldn't wait to get to the pub.  This summit hit our sweet spot - technology and trading.  The presentations were aimed at people with both deep technical knowledge and a clear understanding of the business domain.  It was somewhere we could talk quite comfortably about what we do, with a good mix of attendees who were seriously interested in the field.

Something I particularly liked was how the vendor pitches were kept to lightning talks - five minutes per pitch.  This was an excellent idea.  You got enough of a flavour to decide to find out more if it looked like something useful, but not so much you were bored or felt sold to.

The event was also a really good size, it seemed to encourage networking and chatting.  People mingled more easily than at any of the other events I've been to recently, and not necessarily because they already knew each other.  Mike and I were approached by a lot of people who were either curious to find out what LMAX did, or had already heard of us through some other channel.  I even gave out a bunch of business cards, which finally justified the long, hard battle I had getting them ("Developers don't need business cards" apparently - but what if I meet a cute guy?  How am I supposed to give him my number?).

The only disappointment was not delivering on promises. The agenda distinctly mentions cocktails.  But instead there was simply wine and beer.  I forgave them because the wine was decent and there was plenty of it.

In conclusion, I was impressed and definitely want to go to more of these events. We'd love to get more involved at presenting at some too.