319ArrayBlockingQueue: Weakly Consistent Iteration Powered by Weak References

Author: Dr Heinz M. KabutzDate: 2024-10-25Java Version: 23-previewCategory: Concurrency

Abstract: Like many other concurrent collections, the ArrayBlockingQueue sports a weakly-consistent iterator. However, the ArrayBlockingQueue always has a maximum capacity, the length of the underlying array. In this newsletter we explore what happens to pending iterators when we wrap around the circular array.

Welcome to the 319th edition of The Java(tm) Specialists' Newsletter. We've been exceedingly busy in the last few months, with hundreds of visitors to Crete, and setting our daughter up for her studies in Kilkis, Northern Greece. JCrete was a blast, with lots of new faces. As always, the discussions were fascinating and enriching, plus super inspiring. Please reach out to our team if you think you should be invited for 2025.

javaspecialists.teachable.com: Please visit our new self-study course catalog to see how you can upskill your Java knowledge.

ArrayBlockingQueue: Weakly Consistent Iteration Powered by Weak References

We are usually discouraged from writing our own concurrency constructs. Instead, they recommend we use the battle-hardened classes in java.util.concurrent. But how do these actually work? A few years ago, I started recording "teardowns" of java.util.concurrent, so that programmers can boost their understanding of what goes on inside these magic classes. The first class I tackled was the ArrayBlockingQueue. It looked simple enough. A circular array based structure with a single ReentrantLock guarding the invariants. I did not think it would take more than 30 minutes, including time for coffee breaks. Turns out, a full deep-dive of just this one class, took almost 4 hours, of which over an hour was showing how the iterator worked. Crazy, I did not expect that. Even though I recorded this in 2021, the ArrayBlockingQueue is almost exactly the same as in 2024, with the only change being a few variable names. I can strongly recommend you get the ArrayBlockingQueue teardown, or alternatively, read through the source code all by yourself.

Like some other concurrent collections, the ArrayBlockingQueue sports weakly consistent iteration. This means that if we are busy iterating over the queue and the contents are changed, we can continue iterating without an exception. The iterator will not necessarily show all the changes, but it will try. We explored weakly consistent iteration in 2021 in Newsletter 288.

Here is a demo class that shows the effects of changing a queue whilst we are iterating. LinkedList fails with an exception, LinkedBlockingQueue mostly works, whereas ArrayBlockingQueue has a strange caveat:

import java.util.*;
import java.util.concurrent.*;

public class WeaklyConsistentIterator {
    // Java 23-preview simpler version of "main"
    public void main() {
        test(new LinkedList<>());
        test(new LinkedBlockingQueue<>());
        test(new ArrayBlockingQueue<>(5));
    }

    private void test(Queue<Integer> queue) {
        System.out.println("Testing: " + queue.getClass());
        try {
            // fill up the queue with 5 numbers 0..4
            System.out.println("Adding 0..4");
            for (int i = 0; i < 5; i++) queue.add(i);
            System.out.println("queue = " + queue);

            // create an iterator
            var iterator = queue.iterator();

            // show the first three items in the iterator
            System.out.println("Iterating over the first 3 items");
            for (int i = 0; i < 3; i++) {
                System.out.println(iterator.next());
            }

            // replace the items in the queue with 5..9
            System.out.println("Replacing items in queue with 5..9");
            for (int i = 5; i < 10; i++) {
                queue.poll();
                queue.add(i);
            }
            System.out.println("queue = " + queue);

            // show the next five items in the iterator
            System.out.println("Iterating over the next 5 items");
            for (int i = 0; i < 5; i++)
                System.out.println(iterator.next());

            // Keep on removing and adding items until we have 10..19
            System.out.println("Replace items until we have 10..19");
            for (int i = 10; i < 20; i++) {
                queue.poll();
                queue.add(i);
            }
            System.out.println("queue = " + queue);

            // Show the remaining items in the iterator
            while (iterator.hasNext())
                System.out.println(iterator.next());
        } catch (ConcurrentModificationException ex) {
            System.out.println(ex);
        }
        System.out.println();
    }
}

Let's describe the experiment. We start with a queue that contains Integers 0 through 4. We then create an Iterator. Next we get the first three elements using the iterator. We then remove the 5 Integers and replace them with 5 through 9. At this point, since we have changed the underlying collection, a fast-fail iterator would stop working. A weakly-consistent iterator will deliver the last item it was looking at, and then continue with whatever was in the queue. Thus if we get the next() 5 elements, we will see 3, 5, 6, 7, 8. We then add another 10 elements, 10 through 19, each time first removing the first element from the queue. We then iterate through the remaining elements in the iterator. At this point, the LinkedBlockingQueue and the ArrayBlockingQueue differ. The LinkedBlockingQueue returns 9, 15, 16, 17, 18, 19, whereas the ArrayBlockingQueue returns only 9.

The output for the LinkedList is thus:

Testing: class java.util.LinkedList
Adding 0..4
queue = [0, 1, 2, 3, 4]
Iterating over the first 3 items
0
1
2
Replacing items in queue with 5..9
queue = [5, 6, 7, 8, 9]
Iterating over the next 5 items
java.util.ConcurrentModificationException

For the LinkedBlockingQueue we see:

Testing: class java.util.concurrent.LinkedBlockingQueue
Adding 0..4
queue = [0, 1, 2, 3, 4]
Iterating over the first 3 items
0
1
2
Replacing items in queue with 5..9
queue = [5, 6, 7, 8, 9]
Iterating over the next 5 items
3
5
6
7
8
Replace items until we have 10..19
queue = [15, 16, 17, 18, 19]
9
15
16
17
18
19

And for the ArrayBlockingQueue, we see:

Testing: class java.util.concurrent.ArrayBlockingQueue
Adding 0..4
queue = [0, 1, 2, 3, 4]
Iterating over the first 3 items
0
1
2
Replacing items in queue with 5..9
queue = [5, 6, 7, 8, 9]
Iterating over the next 5 items
3
5
6
7
8
Replace items until we have 10..19
queue = [15, 16, 17, 18, 19]
9

The ArrayBlockingQueue output in Java 7 would have been a bit different. Here is what we would have seen:

Testing: class java.util.concurrent.ArrayBlockingQueue
Adding 0..4
queue = [0, 1, 2, 3, 4]
Iterating over the first 3 items
0
1
2
Replacing items in queue with 5..9
queue = [5, 6, 7, 8, 9]
Iterating over the next 5 items
8
9
Exception in thread "main" java.util.NoSuchElementException
        at java.util.concurrent.ArrayBlockingQueue$Itr.next(ArrayBlockingQueue.java:764)
        at WeaklyConsistentIterator.test(WeaklyConsistentIterator.java:39)
        at WeaklyConsistentIterator.main(WeaklyConsistentIterator.java:8)

In other words, the iterator in the Java 7 ArrayBlockingQueue did not "get the memo" that the underlying data structure had changed, and thus was pointing in the wrong part of the queue. How does the more modern ArrayBlockingQueue know that the queue has changed, and find the correct place?

Since Java 8, the ArrayBlockingQueue maintains a list of all current iterators. This could easily cause a memory leak, because there is no way that the collection could know conclusively when we stop using an iterator. To solve this, it has WeakReferences to all the active iterators. We explored a similar concept in 2009 in our Newsletter 171 - Throwing ConcurrentModificationException Early. By maintaining a list of all active iterators, the ArrayBlockingQueue can let them know which the next element should be. The only issue comes when the ArrayBlockingQueue overwrites its own elements. In that case, the only reasonable thing to do is to stop delivering more elements. This is in line with the definition of "weakly-consistent".

I would encourage you to take a look at how the iterator works inside ArrayBlockingQueue. It is complex. The weakly-consistent iteration, based on WeakReference, increased the LOC of the class by about 77%!

Then again, should we even iterate over a queue? In most cases not, but since Queue is a Collection, it has to support this.

Kind regards

Heinz

Comments

We are always happy to receive comments from our readers. Feel free to send me a comment via email or discuss the newsletter in our JavaSpecialists Slack Channel (Get an invite here)

Related Articles

Browse the Newsletter Archive