This is the fifth day of my participation in the August Wen Challenge.More challenges in August
directory
One, foreword
2. RingBuffer Introduction
Dependency chain
Four, no lock competition implementation
1. Realization of competition between producers and consumers
2. Realization of competition between producers and producers
3, consumer and consumer competition realization
4. Realization of consumer competition within the consumer group
5. Implementation summary
Five, the convention
One, foreword
When you talk about Disruptor, you’ll probably think of its lockless implementation as awesome performance. Everyone will say that because it is lock-free (an important factor, not the only one), it performs well.
So how does it solve the competition between multiple threads (consumers and producers) in a lock-free way? This article will give you a basic analysis.
2. RingBuffer Introduction
Disruptor uses a RingBuffer data structure to store data, rather than a queue like BlockingQueue. RingBuffer is a data group based ring structure. Producers move forward one space for each piece of data they produce, and consumers move forward one space for each piece of data they consume.
Image from Internet
In addition, the size of RingBuffer is fixed when it is created and all memory is pre-allocated. That is, each location is pre-populated with a corresponding data object (usually an empty object). Then each time the producer generates the data, it simply takes the data object at that location and populates that object (such as through setters) with the data (this step is done by the business code itself). This avoids unnecessary object recycling caused by frequent object creation and destruction. Of course, not creating objects frequently has a significant performance benefit, and object creation is still an expensive operation for the corresponding JVM.
Dependency chain
Before introducing lockless implementations, review the relationship between producers and consumers (groups) within Disruptor. In Disruptor, producers and consumers (groups) actually form a chain of dependencies. Let’s take a simple scenario where we have one producer and three consumer groups that depend on each other. Form the following dependency chain (the figure is only a simplified dependency relationship, the actual dependency relationship is more complex than this, for example, in fact every consumer group will depend on producers) :
The approximate dependencies are as follows:
- When consumer group 1 catches up with producer, consumer group 1 needs to wait for producer 1 to generate more data before continuing to consume
- When consumer group 2 catches up with consumer group 1, consumer group 2 waits for consumer group 1 to complete its consumption before consuming
- When consumer group 3 catches up with consumer group 2, consumer group 3 waits for consumer group 2 to complete its consumption before consuming
- When producer 1 catches up with consumer group 3, producer 1 needs to wait for the last consumer group 3 to consume before it can continue to generate data
Four, no lock competition implementation
Based on the dependency chain in the figure above, we can know that there are generally several scenarios with data competition between producers and consumers (groups) as follows:
- Producers and consumer groups compete for the same data (a data object in a RingBuffer ring)
- Producers and producers (multiple producers) compete for the same data (up)
- Consumer groups and consumer groups compete for the same data location (to determine whether it can be consumed)
- Consumers within the consumer group compete for the same message data (data in a slot in the RingBuffer)
1. Realization of competition between producers and consumers
In this scenario, we mainly consider that when the producer catches up with the last consumer (group) in the dependency chain, the producer can no longer produce data and must wait for the consumer’s further consumption to release available slots. So how do producers judge that they have caught up with consumers? What happens when the producer catches up with the consumer? Is locked? Or wait?
The first problem is actually relatively simple, because the producer stores the Sequence of the last producer (group) (mark the current consumption position, as mentioned in False Sharing), so the producer only needs to constantly determine whether the position of the consumer is greater than the current position of the producer. If the Sequence of the producer is equal to the Sequence of the last consumer, it indicates that the producer has caught up with the consumer.
Then how to further deal with the second problem after catching up. In fact, it is relatively simple, at this point, the production thread will constantly check whether there is a available slot (in practice, there is a sleep 1 ms operation, see the code screenshot for details). So there’s a constant loop that prevents locking.
Note: If wait/notify is used here, the lock is introduced indirectly because wait must be used in synchronized blocks.
2. Realization of competition between producers and producers
In the multi-producer scenario, there is competition for resources. That is, multiple producers are competing for slots that are currently available. A simple solution is to lock to prevent multiple threads from competing for available slots in the RingBuffer. So how does lockless work? In fact, it is very simple, is reference AtomicInteger implementation, using CAS+ continuous loop logic.
Here is the code for multi-producer competition for Disruptor, which is the generic CAS implementation idea. I won’t go into details, but if you are not familiar with AtomicInteger, you can take a look at the source code.
3, consumer and consumer competition realization
In fact, the realization of competition between consumers and producers is similar to the realization of competition between producers and consumers, that is, downstream consumers continue to judge whether there is a need for consumable data between upstream consumers, without continuous waiting cycle. The difference is that instead of park, Thread’s onSpinWait is used. This is a new method in Java9. The idea is to optimize blocks of code that don’t pause loops. There are some notes that I added in the picture that you can take a look at, and if you still don’t know, you can search for more information on your own.
The first consumer depends on the producer as well as this code logic. That is, the first consumer treats the producer as an upstream consumer.
4. Realization of consumer competition within the consumer group
Disruptor Consumer Groups have two consumption strategies:
- Each message is consumed by only one consumer
- Each message can be consumed by all consumers
Obviously, if it is the second strategy, the message can be consumed by all consumers, and there is no competition among consumers. But if it is the first strategy, consumers can only be consumed by one consumer, and there is competition among consumers. That is, people are fighting over who is going to consume this data. Its implementation is relatively simple, is also the idea of CAS, here no longer repeat, directly on the source code.
5. Implementation summary
Disruptor lock-free implementation ideas from the above analysis, you can see that there are two main Disruptor lock-free implementations:
- CAS thought
- Infinite loop + Short Park (Pause)
The whole idea is to “waste” THE CPU clock to increase speed. Both of the above ideas “waste” a lot of extra CPU clock (looping consumes a lot of CPU clock), but they improve performance by avoiding locking. The idea of “wasting” CPU clocks to improve performance is relatively common in highly concurrent components or implementations.
Five, the convention
If you have any questions or comments about this article, please add an official account to discuss it. (Add an official account to get 10GB video and graphic materials on “Java Advanced Architecture”.)