4 ms·

I really don't want to put this down. This looks very interesting and is nicely presented. But I have trouble recognizing the main idea(s) behind the "LMAX Disr

by vog 10y ago

I really don't want to put this down. This looks very interesting and is nicely presented. But I have trouble recognizing the main idea(s) behind the "LMAX Disruptor". To me, this all boils down to: "You get better performance if you implement your event queue via a pre-allocated ring buffer instead of (dynamically allocated) linked-lists or arrays." Is it really just that? If so, this is nothing new, but quite common in game programming and related fields. For example, see: https://fgiesen.wordpress.com/2010/12/14/ring-buffers-and-queues/ https://fgiesen.wordpress.com/2010/12/14/ring-buffers-and-qu... What am I missing?

deleted 10y ago
[deleted]
ahoka 10y ago
What you are missing is that with the disruptor pattern you can do this lock-less while keeping the order: The producer gets a sequence number before accessing the space in the queue. This seqno guarantees the order of consumption so there will be no reordering of events on the consumer side. After creating the message, the producer commits this id. Meanwhile the consumer waits for the next seqno to become committed and consumes it. I have implemented a multiple producer, single consumer variant in C for logging and it works quite well. Loggers can write their message concurrently to the ring buffer, but the order will be correct in the log file.
- infamouscow 10y ago
  Sounds exactly what Concurrency Kit already does. http://concurrencykit.org/ http://concurrencykit.org/
  - therestisgone 10y ago
    Except Concurrency Kit only supports a single producer.
    - mej10 10y ago
      The paper linked says that the most common use of Disruptor only has one producer.
  - newobj 10y ago
    "Already does"? They're both from 2011. Even if they both do the same thing, do you have a point?
- irishjohnnie 10y ago
  IIRC, the data structure that they used was not thread-safe. There eventually had to be an interlocked compare exchange operation which slowed throughput. Also, I couldn't imagine this working correctly in out-of-order cores without memory barriers at the very least.
  - ahoka 10y ago
    Yes, you need to use CAS and barriers to make it thread safe. I have also used a condvar for the consumer to avoid spinning while waiting for log messages.
xedarius 10y ago
Mostly yes. Perhaps the thing to note is that the Disruptor moves the logic for manipulating the the indices outside of the ringbuffer itself. Allowing multiple independent consumers to exist. The idea behind he Disruptor is to move data between threads in a contention free manor.
shahbazac 10y ago
Its been many years since I saw the presentation but I believe they made a point of mentioning that ring buffers are not a new technology. They mentioned how such data structures are used all the time in network devices, such as switches. The disruptor is an actual library based on ring buffers (other have already pointed out some other features). In practical terms, this library has been immensely popular. Within a couple years of disruptor's release, practically every (java based) trading firm was using them. I've even seen c++ implementations, only vaguely resembling this library, being referred to as 'disruptors.' Beyond the library, the original (and subsequent) presentations by the authors popularized the concepts of "mechanical sympathy" (understand the abstraction layer beneath what you are currently working in) and introduced a whole new set of developers to modern CPUs, thinking about cache lines, etc.
- ignoramous 10y ago
  Log4J is one such example outside the HFT realm. https://www.grobmeier.de/log4j-2-performance-close-to-insane-20072013.html https://www.grobmeier.de/log4j-2-performance-close-to-insane... And Spring Reactor uses the disruptor as it's default async processor. Disruptor looks like great fit for IoT and msg-relay (think whatsapp) workloads
- irishjohnnie 10y ago
  Ring buffers are also used in web servers, database servers, different kinds of device drivers protocol stacks, constrained embedded devices, etc.
- delibes 10y ago
  You might want to also see Martin Thompson's old blog called Mechanical Sympathy, and in particular his post on 'false sharing' http://mechanical-sympathy.blogspot.co.uk/2011/07/false-sharing.html http://mechanical-sympathy.blogspot.co.uk/2011/07/false-shar...
sethev 10y ago
The Disruptor is an example of solid engineering - the fact that there's nothing "new" is a point in its favor. Its creators acknowledge that similar approaches are common in network switches, etc. I would say these techniques aren't well known among Java programmers. Not new != widely known.
muratk 10y ago
The ideas reminded me of a Fowler article, and in fact he was just describing the LMAX's architecture: http://martinfowler.com/articles/lmax.html http://martinfowler.com/articles/lmax.html Maybe that one is clearer for some.
- vog 10y ago
  That one explains the concepts in much better way, thanks for sharing!

by vog 10y ago

deleted 10y ago

[deleted]

ahoka 10y ago

What you are missing is that with the disruptor pattern you can do this lock-less while keeping the order: The producer gets a sequence number before accessing the space in the queue. This seqno guarantees the order of consumption so there will be no reordering of events on the consumer side. After creating the message, the producer commits this id. Meanwhile the consumer waits for the next seqno to become committed and consumes it. I have implemented a multiple producer, single consumer variant in C for logging and it works quite well. Loggers can write their message concurrently to the ring buffer, but the order will be correct in the log file.

infamouscow 10y ago
Sounds exactly what Concurrency Kit already does. http://concurrencykit.org/ http://concurrencykit.org/
- therestisgone 10y ago
  Except Concurrency Kit only supports a single producer.
  - mej10 10y ago
    The paper linked says that the most common use of Disruptor only has one producer.
- newobj 10y ago
  "Already does"? They're both from 2011. Even if they both do the same thing, do you have a point?
irishjohnnie 10y ago
IIRC, the data structure that they used was not thread-safe. There eventually had to be an interlocked compare exchange operation which slowed throughput. Also, I couldn't imagine this working correctly in out-of-order cores without memory barriers at the very least.
- ahoka 10y ago
  Yes, you need to use CAS and barriers to make it thread safe. I have also used a condvar for the consumer to avoid spinning while waiting for log messages.

xedarius 10y ago

Mostly yes. Perhaps the thing to note is that the Disruptor moves the logic for manipulating the the indices outside of the ringbuffer itself. Allowing multiple independent consumers to exist. The idea behind he Disruptor is to move data between threads in a contention free manor.

shahbazac 10y ago

Its been many years since I saw the presentation but I believe they made a point of mentioning that ring buffers are not a new technology. They mentioned how such data structures are used all the time in network devices, such as switches. The disruptor is an actual library based on ring buffers (other have already pointed out some other features). In practical terms, this library has been immensely popular. Within a couple years of disruptor's release, practically every (java based) trading firm was using them. I've even seen c++ implementations, only vaguely resembling this library, being referred to as 'disruptors.' Beyond the library, the original (and subsequent) presentations by the authors popularized the concepts of "mechanical sympathy" (understand the abstraction layer beneath what you are currently working in) and introduced a whole new set of developers to modern CPUs, thinking about cache lines, etc.

ignoramous 10y ago
Log4J is one such example outside the HFT realm. https://www.grobmeier.de/log4j-2-performance-close-to-insane-20072013.html https://www.grobmeier.de/log4j-2-performance-close-to-insane... And Spring Reactor uses the disruptor as it's default async processor. Disruptor looks like great fit for IoT and msg-relay (think whatsapp) workloads
irishjohnnie 10y ago
Ring buffers are also used in web servers, database servers, different kinds of device drivers protocol stacks, constrained embedded devices, etc.
delibes 10y ago
You might want to also see Martin Thompson's old blog called Mechanical Sympathy, and in particular his post on 'false sharing' http://mechanical-sympathy.blogspot.co.uk/2011/07/false-sharing.html http://mechanical-sympathy.blogspot.co.uk/2011/07/false-shar...

sethev 10y ago

The Disruptor is an example of solid engineering - the fact that there's nothing "new" is a point in its favor. Its creators acknowledge that similar approaches are common in network switches, etc. I would say these techniques aren't well known among Java programmers. Not new != widely known.

muratk 10y ago

The ideas reminded me of a Fowler article, and in fact he was just describing the LMAX's architecture: http://martinfowler.com/articles/lmax.html http://martinfowler.com/articles/lmax.html Maybe that one is clearer for some.

vog 10y ago
That one explains the concepts in much better way, thanks for sharing!