Writing with a single thread LMAX

Question

I've got introduced to LMAX and this wonderful concept called RingBuffer. So guys tell that when writing to the ringbuffer with only one thread performance is way better than with multiple producers...

However i dont really find it possible for tipical application to use only one thread for writes on ringbuffer... i dont really understand how lmax is doing that (if they do). For example N number of different traders put orders on exchange, those are all asynchronious requests that are getting transformed to orders and put into ringbuffer, how can they possibly write those using one thread?

Question 1. I might missing something or misunderstanding some aspect, but if you have N concurrent producers how is it possible to merge them into 1 and not lock each other?

Question 2. I recall rxJava observables, where you could take N observables and merge them into 1 using Observable.merge i wonder if it is blocking or maintaining any lock in any way?

score 3 · Accepted Answer · edited Apr 13 '17 at 12:40

3

The impact on a RingBuffer of multi-treaded writing is slight but under very heavy loads can be significant.

A RingBuffer implementation holds a next node where the next addition will be made. If only one thread is writing to the ring the process will always complete in the minimum time, i.e. buffer[head++] = newData.

To handle multi-threading while avoiding locks you would generally do something like while ( !buffer[head++].compareAndSet(null,newValue)){}. This tight loop would continue to execute while other threads were interfering with the storing of the data, thus slowing town the throughput.

Note that I have used pseudo-code above, have a look at getFree in my implementation here for a real example.

  // Find the next free element and mark it not free.
  private Node<T> getFree() {
    Node<T> freeNode = head.get();
    int skipped = 0;
    // Stop when we hit the end of the list
    // ... or we successfully transit a node from free to not-free.
    // This is the loop that could cause delays under hight thread activity.
    while (skipped < capacity && !freeNode.free.compareAndSet(true, false)) {
      skipped += 1;
      freeNode = freeNode.next;
    }
    // ...
  }

edited Apr 13 '17 at 12:40

Community

1
1

answered May 14 '15 at 13:28

OldCurmudgeon

64,482
16
119
213

So using this for N producers (where n is not much big) will work faster than blocking on a write access? – vach May 15 '15 at 04:41
@vach - Yes. Any nonblocking algorithm is preferable to one using locks. – OldCurmudgeon May 15 '15 at 07:22
What i cant understand is how LMAX manages to do that in a single thread? they are getting lot of order concurrently how do they get them to ringbuffer in a single thread? Any thoughts on this :) ? – vach May 19 '15 at 17:24
@vach - There's a great article [here](http://martinfowler.com/articles/lmax.html). It's just the business logic that is single-threaded. – OldCurmudgeon May 19 '15 at 18:21
I've read it 2 times :) Just got impression that they somehow managed to make producer a single thread (cos they actually developed it) – vach May 19 '15 at 19:42

score 2 · Answer 2 · answered May 14 '15 at 14:09

Internally, RxJava's merge uses a serialization construct I call emitter-loop which uses synchronized and is blocking.

Our 'clients' use merge mostly in throughput- and latency insensitive cases or completely single-threaded and blocking isn't really an issue there.

It is possible to write a non-blocking serializer I call queue-drain but merge can't be configured to use that instead.

You can also take a look at JCTools' MpscArrayQueue directly if you are willing to handle the producer and consumer threads manually.

Writing with a single thread LMAX

2 Answers2