1. Overview
In this tutorial, we'll walk through some of the main implementations of concurrent queues in Java. For a general introduction to queues, refer to our Guide to the Java Queue Interface article.
2. Queues
In multithreaded applications, queues need to handle multiple concurrent producers-consumers scenarios. The correct choice of a concurrent queue could be crucial in achieving good performance in our algorithms.
Firstly, we'll see some important differences between a blocking queue and a non-blocking one. Then, we'll take a look at some implementations and best practices.
2. Blocking vs Non-Blocking Queue
BlockingQueue offers a simple thread-safe mechanism. In this queue, threads need to wait for the queue's availability. The producers will wait for available capacity before adding elements, while consumers will wait until the queue is empty. In those cases, the non-blocking queue will either throw an exception or return a special value, like null or false.
To achieve this blocking mechanism, the BlockingQueue interface exposes two functions on top of the normal Queue functions: put and take. Those functions are the equivalent of add and remove in a standard Queue.
3. Concurrent Queue Implementations
3.1. ArrayBlockingQueue
As its name suggests, this queue uses an array internally. As a consequence, it's a bounded queue, meaning it has a fixed size.
A simple work queue is an example use case. This scenario is often a low producer-to-consumer ratio, where we split time-consuming tasks among multiple workers. Since this queue can't grow indefinitely, the size limit acts as a safety threshold if memory is an issue.
Speaking of memory, it's important to note that the queue pre-allocates the array. While this may improve throughput, it may also consume more memory than necessary. For instance, a large-capacity queue may stay empty for long periods of time.
Also, the ArrayBlockingQueue uses a single lock for both put and take operations. This ensures no overwrite of entries, at the cost of a performance hit.
3.2. LinkedBlockingQueue
The LinkedBlockingQueue uses a LinkedList variant, where each queue item is a new node. While this makes the queue unbounded in principle, it still has a hard limit of Integer.MAX_VALUE.
On the other hand, we can set the queue size by using the constructor LinkedBlockingQueue(int capacity).
This queue uses distinct locks for put and take operations. As a consequence, both operations can be done in parallel and improve throughput.
Since the LinkedBlockingQueue can be either bounded or unbounded, why would we use the ArrayBlockingQueue over this one? LinkedBlockingQueue needs to allocate and deallocate nodes every time an item is added or removed from the queue. For this reason, an ArrayBlockingQueue can be a better alternative if the queue grows fast and shrinks fast.
The performance of LinkedBlockingQueue is said to be unpredictable. In other words, we always need to profile our scenarios to ensure we use the right data structure.
3.3. PriorityBlockingQueue
The PriorityBlockingQueue is our go-to solution when we need to consume items in a specific order. To achieve this, the PriorityBlockingQueue uses an array-based binary heap.
While internally it uses a single lock mechanism, the take operation can occur simultaneously with the put operation. The use of a simple spinlock makes this possible.
A typical use case is consuming tasks with different priorities. We don't want a low priority task to take the place of a high priority one.
3.4. DelayQueue
We use a DelayQueue when a consumer can only take an expired item. Interestingly, it uses a PriorityQueue internally to order the items by their expiration.
Since this is not a general-purpose queue, it doesn't cover as many scenarios as the ArrayBlockingQueue or the LinkedBlockingQueue. For example, we can use this queue to implement a simple event loop similar to what is found in NodeJS. We place asynchronous tasks in the queue for later processing when they expire.
3.5. LinkedTransferQueue
The LinkedTransferQueue introduces a transfer method. While other queues typically block when producing or consuming items, the LinkedTransferQueue allows a producer to wait for the consumption of an item.
We use a LinkedTransferQueue when we need a guarantee that a particular item we put in the queue has been taken by someone. Also, we can implement a simple backpressure algorithm using this queue. Indeed, by blocking producers until consumption, consumers can drive the flow of messages produced.
3.6. SynchronousQueue
While queues typically contain many items, the SynchronousQueue will always have, at most, a single item. In other words, we need to see the SynchronousQueue as a simple way to exchange some data between two threads.
When we have two threads that need access to a shared state, we often synchronize these with CountDownLatch or other synchronization mechanisms. By using a SynchronousQueue, we can avoid this manual synchronization of threads.
3.7. ConcurrentLinkedQueue
The ConcurrentLinkedQueue is the only non-blocking queue of this guide. Consequently, it provides a “wait-free” algorithm where add and poll are guaranteed to be thread-safe and return immediately. Instead of locks, this queue uses CAS (Compare-And-Swap).
Internally, it's based on an algorithm from Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms by Maged M. Michael and Michael L. Scott.
It's a perfect candidate for modern reactive systems, where using blocking data structures is often forbidden.
On the other hand, if our consumer ends up waiting in a loop, we should probably choose a blocking queue as a better alternative.
4. Conclusion
In this guide, we walked through different concurrent queue implementations, discussing their strengths and weaknesses. With this in mind, we're better equipped to develop efficient, durable, and available systems.