Disruptor - a new paradigm for multi-threaded programming
Last week, LMAX , where I work, received the 2011 Java Duke's Choice Award for the Disruptor framework. Previously, Martin Fowler wrote about this technology, known to many readers by publications about object programming.
In this article I would like to briefly tell about this technology, as well as about a specific problem that this technology solves in the company LMAX.
LMAX provides a trading platform for CFD and Forex, characterized by very low latency and high bandwidth.
')
To achieve execution speeds of more than 10,000 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 featuring high bandwidth and very low latency. Disruptor LMAX replaces java.util.concurrent.ArrayBlockingQueue and surpasses it in performance up to 80 times.
Performance testing has shown that using queues to transfer data between parts of the system results in latency. Locking threads and semaphores is difficult to understand and test, and often using them takes more time to debug than to solve a real problem. Also testing of multi-threaded programming has shown that the use of multiple threads often not only does not lead to high performance, but also lowers it.
The table illustrates the costs of increasing the 64-bit counter 500 million times using different techniques on the 2.4Ghz Nehalem processor (strayed from a colleague's blog ).
Let's use a simple example to illustrate. Imagine that you order a pack of sweets and pay them by credit card. A simple retailer will take your order information, use the credit card verification service to check the card number, and then confirm your order — all in one transaction. The stream processing your order will be blocked while waiting for credit card verification, but this block will not be very long for the user, and the server will always be able to run another thread on the processor.
In the LMAX architecture, this operation will be divided into two parts. The first operation is to collect information about the order, which will end with an event (credit card verification request) for the credit card company. The business logic processor will then continue to process events for other customers until it receives a credit card verification event in the input event stream. After processing this event, the order will be confirmed.
Disruptor is a very high-speed, low-latency way of exchanging messages between threads. It's like a lineup on steroids (on large quantities 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 sequence number — the cell in the buffer that he is currently processing. Each producer and consumer writes his number into 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 the other consumer has finished processing.
The advantage of Disruptor is that consumers can quickly catch up with the rest if they fall behind. If the message converter (un-marshaller) encountered a problem on cell 15, and realized this when the recipient is on cell 31, he can read the data from cells 16-30 in one go and quickly catch up. The ability to read large blocks helps lagging consumers quickly catch up on others, thereby reducing latency.
The business logic processor manages all 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 permanent storage.
Although business logic is carried out in one thread, a number of tasks should be carried out before calling a business object. The incoming message from the network needs to be unmarshall in a format convenient for business logic, it is necessary to save to a reliable drive in order to be able to recover data in case of an accident.
These tasks are solved by input and output disruptors. Unlike the business logic processor, these are parallel components, as they include I / O operations that are slow and independent.
Since the input event stream 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 every development, but if used correctly it can show a noticeable increase in the speed of software systems.
Often, financial companies do not spread about their technology. LMAX not only speaks openly about its developments (see blogs ), but also released the Disruptor code in Open Source .
See also - LMAX official website and LMAX partner website in Russian .
PS Add that this framework is 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 tell about this technology, as well as about a specific problem that this technology solves in the company LMAX.
LMAX provides a trading platform for CFD and Forex, characterized by very low latency and high bandwidth.
')
To achieve execution speeds of more than 10,000 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 featuring high bandwidth and very low latency. Disruptor LMAX replaces java.util.concurrent.ArrayBlockingQueue and surpasses it in performance up to 80 times.
The problem of multi-threaded programming
Performance testing has shown that using queues to transfer data between parts of the system results in latency. Locking threads and semaphores is difficult to understand and test, and often using them takes more time to debug than to solve a real problem. Also testing of multi-threaded programming has shown that the use of multiple threads often not only does not lead to high performance, but also lowers it.
The table illustrates the costs of increasing the 64-bit counter 500 million times using different techniques on the 2.4Ghz Nehalem processor (strayed from a colleague's blog ).
| Method | Time (ms) |
| One 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 them by credit card. A simple retailer will take your order information, use the credit card verification service to check the card number, and then confirm your order — all in one transaction. The stream processing your order will be blocked while waiting for credit card verification, but this block will not be very long for the user, and the server will always be able to run another thread on the processor.
In the LMAX architecture, this operation will be divided into two parts. The first operation is to collect information about the order, which will end with an event (credit card verification request) for the credit card company. The business logic processor will then continue to process events for other customers until it receives a credit card verification event in the input event stream. After processing this event, the order will be confirmed.
Disruptor is a very high-speed, low-latency way of exchanging messages between threads. It's like a lineup on steroids (on large quantities 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 sequence number — the cell in the buffer that he is currently processing. Each producer and consumer writes his number into 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 the other consumer has finished processing.
The advantage of Disruptor is that consumers can quickly catch up with the rest if they fall behind. If the message converter (un-marshaller) encountered a problem on cell 15, and realized this when the recipient is on cell 31, he can read the data from cells 16-30 in one go and quickly catch up. The ability to read large blocks helps lagging consumers quickly catch up on others, thereby reducing latency.
The business logic processor manages all 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 permanent storage.
Although business logic is carried out in one thread, a number of tasks should be carried out before calling a business object. The incoming message from the network needs to be unmarshall in a format convenient for business logic, it is necessary to save to a reliable drive in order to be able to recover data in case of an accident.
These tasks are solved by input and output disruptors. Unlike the business logic processor, these are parallel components, as they include I / O operations that are slow and independent.
Since the input event stream 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 every development, but if used correctly it can show a noticeable increase in the speed of software systems.
Often, financial companies do not spread about their technology. LMAX not only speaks openly about its developments (see blogs ), but also released the Disruptor code in Open Source .
See also - LMAX official website and LMAX partner website in Russian .
PS Add that this framework is at the heart of the LMAX trading platform, launched a year ago, and successfully processing thousands of transactions per second.
Source: https://habr.com/ru/post/130113/
All Articles