8 ms·

LMAX Disruptor – High Performance Inter-Thread Messaging Library

126 points by dgudkov 3y ago

samsquire 3y ago
I am working on a C version of the disruptor ringbuffer it is very simple and I need to verify it so it's probably not ready for others but it might be interesting. Aligning by 128 bytes has dropped latency and stopped false sharing. I have gotten latencies to 50 nanoseconds and up. disruptor-multi.c(SPMC) and disruptor-multi-producer.c (MPSC) https://GitHub.com/samsquire/assembly https://GitHub.com/samsquire/assembly I am trying to work out how to support multiple producers and multiple readers (MPMC) at low latency that's what I'm literally working on today. The MPSC and SPMC seem to be working at low latencies. I am hoping to apply actor model to the ringbuffer for communication. I'm also working on nonblocking lock free barrier. This has latency as low as 42 nanoseconds and up.
- cplusplusfellow 3y ago
  Do you think it’s possible to obtain this performance with Rust? I’ve been down the path you’re on a few times and I love the pursuit. Have built my own over the years about 4 times. Hardware was much slower in those days so my lower barrier was 650ns. Things got worse appreciably as a function of the number of producers I found. Some of my most sleepless nights. The funnest nights.
  - topbanana 3y ago
    std::collections::vec_deque is implemented as a growable ring buffer so you might like to start there https://doc.rust-lang.org/std/collections/vec_deque/index.html https://doc.rust-lang.org/std/collections/vec_deque/index.ht...
  - samsquire 3y ago
    How many producers and how many consumers is that 650 nanoseconds? I have pinned threads to even numbered cores with pthread_setaffinity_np and that seems to have evened out the MPMC ringbuffer - 2 producers 2 consumers to under 400 nanoseconds, usually under 1000 nanoseconds. I think hyperthreading causes problems. EDIT: Would you like to chat about this? I would like to! My email is in my profile.
yafetn 3y ago
Semi-related is the Aeron project: https://github.com/real-logic/aeron https://github.com/real-logic/aeron
deleted 3y ago
[deleted]
convexstrictly 3y ago
LMAX - How to Do 100K TPS at Less than 1ms Latency: Video https://www.infoq.com/presentations/LMAX/ https://www.infoq.com/presentations/LMAX/
colanderman 3y ago
I had implemented more-or-less this same concurrency scheme for an IPS/DDoS prevention box ~10 years ago, running on Tilera architecture. It was fast (batching + separating read & write heads really does help a ton)... but not as fast as Tilera's built-in intercore fabric. It had some limitations but was basically a register store/load to access and only like 1 or 2 cycles intercore latency. (Aside, generic atomic operation pro-tip: don't if you can help it. Load + local modify + store is always faster than atomic modify, if you can make the memory ordering work out. And if you can't do away with an atomic modify, batch your updates locally to issue fewer of them at least.)
- sakras 3y ago
  > batch your updates locally to issue fewer of them at least I don’t know why I never thought of this, brilliant!
- pjc50 3y ago
  Tilera! There's a name I'd not heard in years. They leaned very heavily on providing a very large number of cores with small local storage and having to do all the intercore work yourself.
jojohohanon 3y ago
I came across this a few years back when numbly watching the dependencies scroll by during some Java install. “Disruptor is a fairly presumptuous name for a package” I thought. So I looked into it. It fed musings and thought experiments for many walks to and from the T. I love the balance between simplicity and subtlety in the design. If i recall, it was a dependency for log4j, which makes sense for high volume logging.
vinay_ys 3y ago
There's a whole new generation of engineers for whom this is new news. Enjoy!
- nimchimpsky 3y ago
  [dead]
dang 3y ago
Related. Others? Disruptor: High performance alternative to bounded queues - https://news.ycombinator.com/item?id=36073710 https://news.ycombinator.com/item?id=36073710 - May 2023 (1 comment) LMAX Disruptor: High performance method for exchanging data between threads - https://news.ycombinator.com/item?id=30778042 https://news.ycombinator.com/item?id=30778042 - March 2022 (1 comment) The LMAX Architecture - https://news.ycombinator.com/item?id=22369438 https://news.ycombinator.com/item?id=22369438 - Feb 2020 (1 comment) You could have invented the LMAX Disruptor, if only you were limited enough - https://news.ycombinator.com/item?id=17817254 https://news.ycombinator.com/item?id=17817254 - Aug 2018 (29 comments) Disruptor: High performance alternative to bounded queues (2011) [pdf] - https://news.ycombinator.com/item?id=12054503 https://news.ycombinator.com/item?id=12054503 - July 2016 (27 comments) The LMAX Architecture (2011) - https://news.ycombinator.com/item?id=9753044 https://news.ycombinator.com/item?id=9753044 - June 2015 (4 comments) LMAX Disruptor: High Performance Inter-Thread Messaging Library - https://news.ycombinator.com/item?id=8064846 https://news.ycombinator.com/item?id=8064846 - July 2014 (2 comments) Serious high-performance and lock-free algorithms (by LMAX devs) - https://news.ycombinator.com/item?id=4022977 https://news.ycombinator.com/item?id=4022977 - May 2012 (17 comments) The LMAX Architecture - 100K TPS at Less than 1ms Latency - https://news.ycombinator.com/item?id=3173993 https://news.ycombinator.com/item?id=3173993 - Oct 2011 (53 comments)
vivzkestrel 3y ago
stupid question: how to build a trading system? anyone got a starter guide, resources?
- cwalv 3y ago
  Not a real system, obviously, but a high level overview of what it does: https://www.kalzumeus.com/2015/10/30/developing-in-stockfighter-with-no-trading-experience/ https://www.kalzumeus.com/2015/10/30/developing-in-stockfigh...
  - vivzkestrel 3y ago
    thank you for sharing, it has a few code snippets here and there. Would you be aware of a course or something (Google didnt help) that teaches how to build one from the ground up
- nimchimpsky 3y ago
  [dead]
- onetimeuse92304 3y ago
  I built a PoC of a 5us trading system (guaranteed 5us response in every situation) for a brokerage house a long time ago, around the time of LMAX Disruptor. It was one man job and I had to start with nothing (they had no knowledge at all). Fun project and I learned a lot. * full kernel bypass (I even implemented driver for the networking hardware) * everything that could disrupt the application disabled (like SME interrupts, etc.) Memory mapped as huge buffers to prevent tlb lookup failures, etc. * application consists of threads pinned to specified cores * each thread on the path of market data to sending the order is never calling the operating system for anything. When not processing anything it is busy spinning. * all memory preallocated carefully to have it pinned to the local core * data flows from the networking hardware into one core and then passess through cores using disruptor, each core doing further processing and publishing signals to the next core * the main insight was that rather than wait for market signals to then decide what to do, you can precalculate your responses up to and including the actual message to be sent to the exchange.
pclmulqdq 3y ago
Every time a new generation plays with the LMAX disruptor, it's time to remind them that the modes with multiple producers/consumers can have really bad tail latency if your application's threading is not designed in the intended way. Disruptor and most other data structures that come from trading are designed to run with thread-per-core systems. This means systems where there will be no preemption during a critical section. They can get away with a lot of shenanigans on the concurrency model due to this. If you are using these data structures and have a thread-per-request model, you're probably going to have a bad time.
- xoranth 3y ago
  In general, what are the advantage of a thread-per-request model? Better load balancing between cores?
  - onetimeuse92304 3y ago
    Thread per request can never have better load balancing between cores than a well designed, custom solution. You are essentially asking the operating system to do the scheduling for you. But the OS will never be able to do it perfectly as it has no knowledge of what your application is doing. The main advantage of OS scheduling is that you get pretty good results without having to think about it at all. Pretty good, but never perfect.
    - xoranth 3y ago
      > You are essentially asking the operating system to do the scheduling for you. But the OS will never be able to do it perfectly as it has no knowledge of what your application is doing. From LMAX presentations, it looks like they want you to split your application into tasks [1], define a graph of task dependencies, have each core process a particular kind of task and have task processors communicate their producers via a ring buffer. In particular, the allocation of tasks is static. The use of a ring buffer means that there is very little contention, and task processing is very efficient, but some cores might end up underutilized. On the other hand, if you have a thread per request, and allow them to migrate between cores, idle cores can steal tasks from busy ones. So in theory you could get better utilization, but task processing is less efficient since you need to share more data between cores. ("threads" don't need to be OS threads, they can be green threads) That said, I am not sure if GP meant this by thread-per-request, or "legacy" applications that use a thread pool, or something else. [1]: https://www.slideshare.net/trishagee/introduction-to-the-disruptor#39 https://www.slideshare.net/trishagee/introduction-to-the-dis...
willtemperley 3y ago
Beware the advertised latency will probably be when using the busy-spin wait strategy which uses a lot of CPU resource. Great library which makes processing concurrent streams incredibly easy.
vkaku 3y ago
I've actually seen this particular library used (and misused and abused). People tried to offload I/O and data heavy tasks on it and was a spectacular fail, with multiple threads getting blocked and people having to frequently adjust it's buffer size and batch size. One of those things to remember is that Java I/O layering (stuff like JPA) is really terrible. And people in my known Java world tend to prefer the abstractions while the people in the trading world try to use GC-less code (unboxed primitives and byte arrays). Unless you have verified your E2E I/O to be really fast (possible off heap), you're just pushing a few bytes here and there, your latencies are all in check - this library is not for you. Do all that work first, then use this library.
bob1029 3y ago
I love this pattern. There are many problems that fit it quite well once you start thinking in these terms - Intentionally delaying execution over (brief amounts of) time in order to create batching opportunities which leverage the physical hardware's unique quirks. Any domain with synchronous/serializable semantics can modeled as a single writer, with an MPSC queue in front of it. Things like game worlds, business decision systems, database engines, etc. fit the mold fairly well. The busy-spin strategy can be viewed as a downside, but I can't ignore the latency advantages. In my experiments where I have some live "analog" input like a mouse, the busy wait strat feels 100% transparent. I've tested it for hours without it breaking into the millisecond range (on windows 10!). For gaming/real-time UI cases, you either want this or yield. Sleep strategies are fine if you can tolerate jitter in the millisecond range.
mgaunard 3y ago
I built trading systems for LMAX exchanges. Their technology seems quite far from the state of the art to me. I didn't know they even claimed to attempt being the fastest exchange in the world. They're very far from being so and it's quite clear that there are architectural decisions in that platform that would prevent that.
- quadrature 3y ago
  What kinds of issues did you see?. Do you think there are better alternatives to the disruptor ?
  - mgaunard 3y ago
    I don't particularly know anything about this disruptor, and it being in Java kinda biases me towards dismissing it out of hand (no one does serious systems programming in Java). From a quick reading it's just a standard spmc queue with some mpmc capabilities. Queues (preferably lock-free and bounded) are a basic component of any low-latency distributed software system. They seem to understand the basics right, nothing too outstanding, some decisions quite suboptimal. Myself I use spsc task queues for inter-thread communication (because in that scenario you know who you're sending tasks to, and you can easily just attach multiple spsc queues for pseudo-mpsc capabilities), and mpmc message queues for inter-process communication (because that scenario is more of a message bus, and you don't know who's talking to who). I have built these kinds of things many times together with bespoke threading and scheduling models, as have others at all of the trading shops I've seen, so I'd say it's a pretty standard thing in the industry. Open-source frameworks of interest would be Seastar or DPDK. However, while a good threading model helps, it's far from sufficient to be the highest performance trading exchange. You also need to think hard about networking, be it the protocols, the software, the hardware and the topology. For example key factors in trading are deterministically publishing data to all participants at the same time, ensuring private information is not published before its public equivalent, making sure that whoever sent their packet first gets processed first. Even something as simple as the kind of switches you use has a huge impact.
    - 3y ago
up2isomorphism 3y ago
I never understand the reason open sourcing a trading system, if it works.
- auntienomen 3y ago
  This is a matching engine. It's the platform where traders trade.
pixelmonkey 3y ago
Martin Fowler has a lovely deep-dive blog post on this architecture: https://martinfowler.com/articles/lmax.html https://martinfowler.com/articles/lmax.html It includes lots of diagrams and citations. One term I always loved re: LMAX is “mechanical sympathy.” Covered in this section: https://martinfowler.com/articles/lmax.html#QueuesAndTheirLackOfMechanicalSympathy https://martinfowler.com/articles/lmax.html#QueuesAndTheirLa...

126 points by dgudkov 3y ago

I am working on a C version of the disruptor ringbuffer it is very simple and I need to verify it so it's probably not ready for others but it might be interesting. Aligning by 128 bytes has dropped latency and stopped false sharing. I have gotten latencies to 50 nanoseconds and up. disruptor-multi.c(SPMC) and disruptor-multi-producer.c (MPSC) https://GitHub.com/samsquire/assembly https://GitHub.com/samsquire/assembly I am trying to work out how to support multiple producers and multiple readers (MPMC) at low latency that's what I'm literally working on today. The MPSC and SPMC seem to be working at low latencies. I am hoping to apply actor model to the ringbuffer for communication. I'm also working on nonblocking lock free barrier. This has latency as low as 42 nanoseconds and up.

cplusplusfellow 3y ago
Do you think it’s possible to obtain this performance with Rust? I’ve been down the path you’re on a few times and I love the pursuit. Have built my own over the years about 4 times. Hardware was much slower in those days so my lower barrier was 650ns. Things got worse appreciably as a function of the number of producers I found. Some of my most sleepless nights. The funnest nights.
- topbanana 3y ago
  std::collections::vec_deque is implemented as a growable ring buffer so you might like to start there https://doc.rust-lang.org/std/collections/vec_deque/index.html https://doc.rust-lang.org/std/collections/vec_deque/index.ht...
- samsquire 3y ago
  How many producers and how many consumers is that 650 nanoseconds? I have pinned threads to even numbered cores with pthread_setaffinity_np and that seems to have evened out the MPMC ringbuffer - 2 producers 2 consumers to under 400 nanoseconds, usually under 1000 nanoseconds. I think hyperthreading causes problems. EDIT: Would you like to chat about this? I would like to! My email is in my profile.

yafetn 3y ago

Semi-related is the Aeron project: https://github.com/real-logic/aeron https://github.com/real-logic/aeron

deleted 3y ago

[deleted]

convexstrictly 3y ago

LMAX - How to Do 100K TPS at Less than 1ms Latency: Video https://www.infoq.com/presentations/LMAX/ https://www.infoq.com/presentations/LMAX/

colanderman 3y ago

I had implemented more-or-less this same concurrency scheme for an IPS/DDoS prevention box ~10 years ago, running on Tilera architecture. It was fast (batching + separating read & write heads really does help a ton)... but not as fast as Tilera's built-in intercore fabric. It had some limitations but was basically a register store/load to access and only like 1 or 2 cycles intercore latency. (Aside, generic atomic operation pro-tip: don't if you can help it. Load + local modify + store is always faster than atomic modify, if you can make the memory ordering work out. And if you can't do away with an atomic modify, batch your updates locally to issue fewer of them at least.)

sakras 3y ago
> batch your updates locally to issue fewer of them at least I don’t know why I never thought of this, brilliant!
pjc50 3y ago
Tilera! There's a name I'd not heard in years. They leaned very heavily on providing a very large number of cores with small local storage and having to do all the intercore work yourself.

jojohohanon 3y ago

I came across this a few years back when numbly watching the dependencies scroll by during some Java install. “Disruptor is a fairly presumptuous name for a package” I thought. So I looked into it. It fed musings and thought experiments for many walks to and from the T. I love the balance between simplicity and subtlety in the design. If i recall, it was a dependency for log4j, which makes sense for high volume logging.

vinay_ys 3y ago

There's a whole new generation of engineers for whom this is new news. Enjoy!

nimchimpsky 3y ago
[dead]

dang 3y ago

Related. Others? Disruptor: High performance alternative to bounded queues - https://news.ycombinator.com/item?id=36073710 https://news.ycombinator.com/item?id=36073710 - May 2023 (1 comment) LMAX Disruptor: High performance method for exchanging data between threads - https://news.ycombinator.com/item?id=30778042 https://news.ycombinator.com/item?id=30778042 - March 2022 (1 comment) The LMAX Architecture - https://news.ycombinator.com/item?id=22369438 https://news.ycombinator.com/item?id=22369438 - Feb 2020 (1 comment) You could have invented the LMAX Disruptor, if only you were limited enough - https://news.ycombinator.com/item?id=17817254 https://news.ycombinator.com/item?id=17817254 - Aug 2018 (29 comments) Disruptor: High performance alternative to bounded queues (2011) [pdf] - https://news.ycombinator.com/item?id=12054503 https://news.ycombinator.com/item?id=12054503 - July 2016 (27 comments) The LMAX Architecture (2011) - https://news.ycombinator.com/item?id=9753044 https://news.ycombinator.com/item?id=9753044 - June 2015 (4 comments) LMAX Disruptor: High Performance Inter-Thread Messaging Library - https://news.ycombinator.com/item?id=8064846 https://news.ycombinator.com/item?id=8064846 - July 2014 (2 comments) Serious high-performance and lock-free algorithms (by LMAX devs) - https://news.ycombinator.com/item?id=4022977 https://news.ycombinator.com/item?id=4022977 - May 2012 (17 comments) The LMAX Architecture - 100K TPS at Less than 1ms Latency - https://news.ycombinator.com/item?id=3173993 https://news.ycombinator.com/item?id=3173993 - Oct 2011 (53 comments)

vivzkestrel 3y ago

stupid question: how to build a trading system? anyone got a starter guide, resources?

cwalv 3y ago
Not a real system, obviously, but a high level overview of what it does: https://www.kalzumeus.com/2015/10/30/developing-in-stockfighter-with-no-trading-experience/ https://www.kalzumeus.com/2015/10/30/developing-in-stockfigh...
- vivzkestrel 3y ago
  thank you for sharing, it has a few code snippets here and there. Would you be aware of a course or something (Google didnt help) that teaches how to build one from the ground up
nimchimpsky 3y ago
[dead]
onetimeuse92304 3y ago
I built a PoC of a 5us trading system (guaranteed 5us response in every situation) for a brokerage house a long time ago, around the time of LMAX Disruptor. It was one man job and I had to start with nothing (they had no knowledge at all). Fun project and I learned a lot. * full kernel bypass (I even implemented driver for the networking hardware) * everything that could disrupt the application disabled (like SME interrupts, etc.) Memory mapped as huge buffers to prevent tlb lookup failures, etc. * application consists of threads pinned to specified cores * each thread on the path of market data to sending the order is never calling the operating system for anything. When not processing anything it is busy spinning. * all memory preallocated carefully to have it pinned to the local core * data flows from the networking hardware into one core and then passess through cores using disruptor, each core doing further processing and publishing signals to the next core * the main insight was that rather than wait for market signals to then decide what to do, you can precalculate your responses up to and including the actual message to be sent to the exchange.

pclmulqdq 3y ago

Every time a new generation plays with the LMAX disruptor, it's time to remind them that the modes with multiple producers/consumers can have really bad tail latency if your application's threading is not designed in the intended way. Disruptor and most other data structures that come from trading are designed to run with thread-per-core systems. This means systems where there will be no preemption during a critical section. They can get away with a lot of shenanigans on the concurrency model due to this. If you are using these data structures and have a thread-per-request model, you're probably going to have a bad time.

xoranth 3y ago
In general, what are the advantage of a thread-per-request model? Better load balancing between cores?
- onetimeuse92304 3y ago
  Thread per request can never have better load balancing between cores than a well designed, custom solution. You are essentially asking the operating system to do the scheduling for you. But the OS will never be able to do it perfectly as it has no knowledge of what your application is doing. The main advantage of OS scheduling is that you get pretty good results without having to think about it at all. Pretty good, but never perfect.
  - xoranth 3y ago
    > You are essentially asking the operating system to do the scheduling for you. But the OS will never be able to do it perfectly as it has no knowledge of what your application is doing. From LMAX presentations, it looks like they want you to split your application into tasks [1], define a graph of task dependencies, have each core process a particular kind of task and have task processors communicate their producers via a ring buffer. In particular, the allocation of tasks is static. The use of a ring buffer means that there is very little contention, and task processing is very efficient, but some cores might end up underutilized. On the other hand, if you have a thread per request, and allow them to migrate between cores, idle cores can steal tasks from busy ones. So in theory you could get better utilization, but task processing is less efficient since you need to share more data between cores. ("threads" don't need to be OS threads, they can be green threads) That said, I am not sure if GP meant this by thread-per-request, or "legacy" applications that use a thread pool, or something else. [1]: https://www.slideshare.net/trishagee/introduction-to-the-disruptor#39 https://www.slideshare.net/trishagee/introduction-to-the-dis...

willtemperley 3y ago

Beware the advertised latency will probably be when using the busy-spin wait strategy which uses a lot of CPU resource. Great library which makes processing concurrent streams incredibly easy.

vkaku 3y ago

I've actually seen this particular library used (and misused and abused). People tried to offload I/O and data heavy tasks on it and was a spectacular fail, with multiple threads getting blocked and people having to frequently adjust it's buffer size and batch size. One of those things to remember is that Java I/O layering (stuff like JPA) is really terrible. And people in my known Java world tend to prefer the abstractions while the people in the trading world try to use GC-less code (unboxed primitives and byte arrays). Unless you have verified your E2E I/O to be really fast (possible off heap), you're just pushing a few bytes here and there, your latencies are all in check - this library is not for you. Do all that work first, then use this library.

bob1029 3y ago

I love this pattern. There are many problems that fit it quite well once you start thinking in these terms - Intentionally delaying execution over (brief amounts of) time in order to create batching opportunities which leverage the physical hardware's unique quirks. Any domain with synchronous/serializable semantics can modeled as a single writer, with an MPSC queue in front of it. Things like game worlds, business decision systems, database engines, etc. fit the mold fairly well. The busy-spin strategy can be viewed as a downside, but I can't ignore the latency advantages. In my experiments where I have some live "analog" input like a mouse, the busy wait strat feels 100% transparent. I've tested it for hours without it breaking into the millisecond range (on windows 10!). For gaming/real-time UI cases, you either want this or yield. Sleep strategies are fine if you can tolerate jitter in the millisecond range.

mgaunard 3y ago

I built trading systems for LMAX exchanges. Their technology seems quite far from the state of the art to me. I didn't know they even claimed to attempt being the fastest exchange in the world. They're very far from being so and it's quite clear that there are architectural decisions in that platform that would prevent that.

quadrature 3y ago
What kinds of issues did you see?. Do you think there are better alternatives to the disruptor ?
- mgaunard 3y ago
  I don't particularly know anything about this disruptor, and it being in Java kinda biases me towards dismissing it out of hand (no one does serious systems programming in Java). From a quick reading it's just a standard spmc queue with some mpmc capabilities. Queues (preferably lock-free and bounded) are a basic component of any low-latency distributed software system. They seem to understand the basics right, nothing too outstanding, some decisions quite suboptimal. Myself I use spsc task queues for inter-thread communication (because in that scenario you know who you're sending tasks to, and you can easily just attach multiple spsc queues for pseudo-mpsc capabilities), and mpmc message queues for inter-process communication (because that scenario is more of a message bus, and you don't know who's talking to who). I have built these kinds of things many times together with bespoke threading and scheduling models, as have others at all of the trading shops I've seen, so I'd say it's a pretty standard thing in the industry. Open-source frameworks of interest would be Seastar or DPDK. However, while a good threading model helps, it's far from sufficient to be the highest performance trading exchange. You also need to think hard about networking, be it the protocols, the software, the hardware and the topology. For example key factors in trading are deterministically publishing data to all participants at the same time, ensuring private information is not published before its public equivalent, making sure that whoever sent their packet first gets processed first. Even something as simple as the kind of switches you use has a huge impact.
  - 3y ago

up2isomorphism 3y ago

I never understand the reason open sourcing a trading system, if it works.

auntienomen 3y ago
This is a matching engine. It's the platform where traders trade.

pixelmonkey 3y ago

Martin Fowler has a lovely deep-dive blog post on this architecture: https://martinfowler.com/articles/lmax.html https://martinfowler.com/articles/lmax.html It includes lots of diagrams and citations. One term I always loved re: LMAX is “mechanical sympathy.” Covered in this section: https://martinfowler.com/articles/lmax.html#QueuesAndTheirLackOfMechanicalSympathy https://martinfowler.com/articles/lmax.html#QueuesAndTheirLa...