Shulou(Shulou.com)06/02 Report--

This article mainly explains "what is the principle of Disruptor". The content of the explanation is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought to study and learn "what is the principle of Disruptor"?

Disruptor solves the problem of slow queues through the following designs:

Ring array structure

To avoid garbage collection, use arrays instead of linked lists. At the same time, the array is more friendly to the processor caching mechanism.

Element location, array length 2 ^ n, through bit operation to speed up the positioning speed. The subscript takes the form of increment. Don't worry about index overflow. Index is a long type, and even with a processing speed of 1 million QPS, it takes 300000 years to run out. -unlocked design

Each producer or consumer thread will first apply for the position of the operable element in the array, and then write or read data directly at that location.

Let's ignore the ring structure of the array and describe how to implement a lock-free design. The whole process ensures the thread safety of the operation through the atomic variable CAS.

A producer writes data

The process for producers to write data with one thread is relatively simple: 1. Apply to write m elements; 2. If there are m elements to write to, the largest sequence number is returned. Here we mainly judge whether the unread elements will be overwritten. If the return is correct, the producer begins to write the element.

Multiple producers

In the case of multiple producers, you will encounter the problem of "how to prevent multiple threads from repeating the same element". The solution for Disruptor is for each thread to get a different section of array space to operate on. This is easy to achieve through CAS. You only need to use CAS to determine whether the space has been allocated when allocating elements.

But there is a new problem: how to prevent reading unwritten elements when reading. Disruptor introduces a buffer:available Buffer of the same size as Ring Buffer in the case of multiple producers. When a certain location is successfully written, the corresponding position of the availble Buffer is set and marked as successful. When reading, the available Buffer is traversed to determine whether the element is ready.

The following two situations are introduced: reading data and writing data.

Read data

The situation of producer multithreaded writing will be much more complicated: 1. Apply to read the serial number n; 2. If writer cursor > = n, it is still not possible to determine the maximum subscript that is continuously readable. Read available Buffer from reader cursor, check to the first unavailable element, and then return the location of the largest continuous readable element; 3. The consumer reads the element.

As shown in the following figure, the reader thread reads the element with subscript 2, the three threads Writer1/Writer2/Writer3 are writing data to the corresponding location of the RingBuffer, and the maximum element subscript to which the writer thread is assigned is 11.

The reader thread applies to read the element with subscript from 3 to 11 and determines that writer cursor > = 11. Then start reading the availableBuffer, starting at 3 and reading back, and find that the element with subscript 7 is not produced successfully, so WaitFor (11) returns 6.

The consumer then reads the subscript from 3 to 6 for a total of 4 elements.

Write data

When multiple producers write: 1. Apply to write m elements; 2. If there are m elements to write to, the largest sequence number is returned. Each producer will be allocated a section of exclusive space; 3. The producer writes the element and sets the corresponding location in the available Buffer while writing the element to mark which locations have been successfully written.

As shown in the following figure, the Writer1 and Writer2 threads write to the array and both apply for writable array space. Writer1 is allocated space from subscript 3 to table 5 below, and Writer2 is allocated space from subscript 6 to subscript 9.

Writer1 writes the element in subscript 3 and sets the corresponding position in available Buffer. The tag has been successfully written, move back one bit, and start writing the element in subscript 4. Writer2 in the same way. Finally, all the writes are completed.

Code that prevents different producers from writing to the same space, as follows:

Public long tryNext (int n) throws InsufficientCapacityException {if (n)

0 ");} long current; long next; do {current = cursor.get (); next = current + n; if (! hasAvailableCapacity (gatingSequences, n, current)) {throw InsufficientCapacityException.INSTANCE;}} while (! cursor.compareAndSet (current, next)); return next;}

The condition cursor.compareAndSet (current, next) of the do/while cycle is used to determine whether the space of each application has been occupied by other producers. If it is already occupied, the function returns a failure, and the While loop executes again, requesting write space.

The process of the consumer is very similar to that of the producer, so I won't describe it here.

Summary

Disruptor achieves high performance in high concurrency situations through ingenious lock-free design.

Thank you for your reading, the above is the content of "what is the principle of Disruptor", after the study of this article, I believe you have a deeper understanding of what the principle of Disruptor is, and the specific use needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.