October 12, 2011 at 17:21Disruptor - A New Multithreaded Programming Paradigm
Last week, the LMAX company where I work won the Java Duke's Choice Award 2011 for the Disruptor framework. Earlier, Martin Fowler , known to many readers for publications on object programming, wrote about this technology .
In this article, I would like to briefly talk about this technology, as well as about the specific problem that this technology solves at LMAX.
LMAX provides a CFD and Forex trading platform with very low latency and high bandwidth.
To achieve a execution speed of more than 10 thousand operations per second, LMAX developed the Disruptor pattern. This is a completely new and very unconventional approach to solving parallel programming problems. Disruptor is a multi-threaded parallel transaction processing framework with high throughput and very low latency. Disruptor LMAX replaces java.util.concurrent.ArrayBlockingQueue and surpasses it in performance up to 80 times.
Performance testing showed that using queues to transfer data between parts of the system delays are generated. Blocking threads and semaphores are difficult to understand and test, and often using them takes more time to debug than to solve a real problem. Testing of multi-threaded programming also showed that the use of multiple threads often not only does not lead to high performance, but also reduces it.
The table illustrates the costs of increasing a 64-bit counter 500 million times using different techniques on a 2.4Ghz Nehalem processor (stolen from a colleague’s blog ).
Let's use a simple example to illustrate. Imagine that you order a pack of sweets and pay for them by credit card. A simple retail system will receive information about your order, use the credit card verification service to check the card number, and then confirm your order - all in one transaction. The thread processing your order will be blocked while waiting for a credit card check, but this blocking will not be very long for the user, and the server will always be able to start another thread on the processor.
In the LMAX architecture, this operation will be divided into two parts. The first operation is the collection of information about the order, which will end with the conclusion of the event (credit card verification request) for the credit card company. The business logic processor will then continue to process events for other clients until it receives a credit card verification event in the input event stream. After processing this event, an order confirmation will be carried out.
Disruptor is a very high-speed, low-latency way to exchange messages between threads. It’s like queuing up on steroids (large amounts of steroids!) And it is one of the main innovations of the LMAX exchange. Disruptor includes manufacturer, consumer, and circular buffer. Each producer and consumer knows the serial number - the cell in the buffer that he is currently processing. Each producer and consumer writes their number to the counter, and can read other counters. Thus, the consumer can read the manufacturer’s counter to make sure that the cell in which he wants to write is available. Also, the consumer can verify that he processes the message only after another consumer has finished processing.
Disruptor's advantage is that consumers can quickly catch up with others if they are behind. If the message converter (un-marshaller) encountered a problem in cell 15, and understood this when the receiver is in cell 31, it can read data from cells 16-30 in one go and quickly catch up. The ability to read large blocks helps lagging consumers quickly catch up with others, thus reducing latency.
The business logic processor manages the entire business logic using a single-threaded Java program that responds to method calls and produces output events. It works completely in RAM, without a database or other persistent storage.
Although business logic is implemented in a single thread, a number of tasks should be performed before invoking a business object. An incoming message from the network needs to be unmarshall in a format convenient for business logic, you need to save it to a reliable drive to be able to recover data in the event of an accident.
These problems are solved by input and output disruptors. Unlike a business logic processor, these are parallel components, since they include I / O operations that are slow and independent.
Since the input stream of events is stored in a reliable storage (this is one of the tasks of the input disruptor), you can always restore the current state of the business logic processor by replaying input events - just like in the version control system, having a sequence of changes, you can get the final version of the document .
Disruptor is not a universal solution for each development, however, if used correctly, it can show a noticeable increase in the speed of software systems.
Often financial companies do not talk about their technology. LMAX not only speaks openly about its developments (see blogs ), but also released Disruptor code in Open Source .
See also - the official LMAX website and the LMAX partner site in Russian .
PS I will add that this framework lies at the heart of the LMAX trading platform, launched a year ago, and successfully processing thousands of transactions per second.
In this article, I would like to briefly talk about this technology, as well as about the specific problem that this technology solves at LMAX.
LMAX provides a CFD and Forex trading platform with very low latency and high bandwidth.
To achieve a execution speed of more than 10 thousand operations per second, LMAX developed the Disruptor pattern. This is a completely new and very unconventional approach to solving parallel programming problems. Disruptor is a multi-threaded parallel transaction processing framework with high throughput and very low latency. Disruptor LMAX replaces java.util.concurrent.ArrayBlockingQueue and surpasses it in performance up to 80 times.
Multithreaded programming problem
Performance testing showed that using queues to transfer data between parts of the system delays are generated. Blocking threads and semaphores are difficult to understand and test, and often using them takes more time to debug than to solve a real problem. Testing of multi-threaded programming also showed that the use of multiple threads often not only does not lead to high performance, but also reduces it.
The table illustrates the costs of increasing a 64-bit counter 500 million times using different techniques on a 2.4Ghz Nehalem processor (stolen from a colleague’s blog ).
| Method | Time (ms) |
| Single thread | 300 |
| Single stream with Memory Barrier | 4,700 |
| Single stream with CAS | 5,700 |
| Two streams with CAS | 30,000 |
| Single thread with Lock | 10,000 |
| Two threads with Lock | 224,000 |
LMAX approach
Let's use a simple example to illustrate. Imagine that you order a pack of sweets and pay for them by credit card. A simple retail system will receive information about your order, use the credit card verification service to check the card number, and then confirm your order - all in one transaction. The thread processing your order will be blocked while waiting for a credit card check, but this blocking will not be very long for the user, and the server will always be able to start another thread on the processor.
In the LMAX architecture, this operation will be divided into two parts. The first operation is the collection of information about the order, which will end with the conclusion of the event (credit card verification request) for the credit card company. The business logic processor will then continue to process events for other clients until it receives a credit card verification event in the input event stream. After processing this event, an order confirmation will be carried out.
Disruptor is a very high-speed, low-latency way to exchange messages between threads. It’s like queuing up on steroids (large amounts of steroids!) And it is one of the main innovations of the LMAX exchange. Disruptor includes manufacturer, consumer, and circular buffer. Each producer and consumer knows the serial number - the cell in the buffer that he is currently processing. Each producer and consumer writes their number to the counter, and can read other counters. Thus, the consumer can read the manufacturer’s counter to make sure that the cell in which he wants to write is available. Also, the consumer can verify that he processes the message only after another consumer has finished processing.
Disruptor's advantage is that consumers can quickly catch up with others if they are behind. If the message converter (un-marshaller) encountered a problem in cell 15, and understood this when the receiver is in cell 31, it can read data from cells 16-30 in one go and quickly catch up. The ability to read large blocks helps lagging consumers quickly catch up with others, thus reducing latency.
The business logic processor manages the entire business logic using a single-threaded Java program that responds to method calls and produces output events. It works completely in RAM, without a database or other persistent storage.
Although business logic is implemented in a single thread, a number of tasks should be performed before invoking a business object. An incoming message from the network needs to be unmarshall in a format convenient for business logic, you need to save it to a reliable drive to be able to recover data in the event of an accident.
These problems are solved by input and output disruptors. Unlike a business logic processor, these are parallel components, since they include I / O operations that are slow and independent.
Since the input stream of events is stored in a reliable storage (this is one of the tasks of the input disruptor), you can always restore the current state of the business logic processor by replaying input events - just like in the version control system, having a sequence of changes, you can get the final version of the document .
Conclusions and Resources
Disruptor is not a universal solution for each development, however, if used correctly, it can show a noticeable increase in the speed of software systems.
Often financial companies do not talk about their technology. LMAX not only speaks openly about its developments (see blogs ), but also released Disruptor code in Open Source .
See also - the official LMAX website and the LMAX partner site in Russian .
PS I will add that this framework lies at the heart of the LMAX trading platform, launched a year ago, and successfully processing thousands of transactions per second.
