multithreading - Iterator type in java (weakly consistent)

Question

I understand fail-fast (LinkedList) and fail-safe (copyonwrite) iterators, however weakly consistent remains a mystery.

Documentation says it might reflect the changes of the underlying collections but there is no guarantee. So I assume that weakly consistent do not create copy of the backing collection. (in a concurrent Map it works on the same bucketarray).

I assume if a thread A creates an iterator and gone through halfway, when comes thread B that puts an item to the bucket at the beginning of the array that this change wont be visible to the iterator of thread A.

If B would have put that item to the end of the array, A would have seen it.

Is it possibly to have a nosuchelement exception?

if thread A creates an iterator, then traverse to an item X which has a next item Y , then jvm stops thread A and resumes thread B, who removes Y. Will this be visible to thread A (I guess so otherwise concurrent map wouldn't be thread safe, but know nothing about how its iterator is implemented), because it is not visible to thread A then it could easily throw an exception.

Answer 1

The definition of weakly consistent is given in the java.util.concurrent package documentation. For convenience I'll quote the relevant bits. Regarding weakly consistent iterators and spliterators, the documentation says:

• they may proceed concurrently with other operations
• they will never throw ConcurrentModificationException
• they are guaranteed to traverse elements as they existed upon construction exactly once, and may (but are not guaranteed to) reflect any modifications subsequent to construction.

What this doesn't say (and what may be implicit in the use of the word "consistent") is that iteration won't result in an error such as IndexOutOfBoundsException or NoSuchElementException. It also doesn't say whether that the iteration will even terminate! (I believe it will.) In some sense this behavior is indeed consistent, though the guarantees are pretty weak. The third bullet in particular explicitly doesn't make any guarantees about what elements are seen by the iteration if modifications occur during iteration.

Consider the following example:

    List<String> input = Arrays.asList("a", "b", "c", "d", "e");
    List<String> output = new ArrayList<>();

    Deque<String> deque = new ConcurrentLinkedDeque<>(input);
    for (String s : deque) {
        output.add(s);
        if (s.equals("c")) {
            deque.addFirst("XXX");
            deque.removeLast();
        }
    }

A ConcurrentLinkedDeqeue is an example of a collection with weakly consistent iteration semantics. This code iterates over it and adds each element seen into a copy, but in the middle of the iteration, the deque is modified.

If you try this with a LinkedList you'll get a ConcurrentModificationException as you expect. With a ConcurrentLinkedDeque, the output list is

    [a, b, c, d]

Note that "XXX" was added before the "e" was removed, so the output list reflects only some of the modifications that were made to the input during the iteration. Since iteration proceeds left-to-right in this case, it's not surprising that modifications made to the left of the current iteration point aren't seen, and modifications made to the right of the current iteration point are seen. Of course, not all collections have such a straightforward iteration order.

Note also that the output doesn't reflect a snapshot of the input as it occurred at any point in time. (If you want snapshot semantics, you'd need to use something like CopyOnWriteArrayList.) The only guarantee is that the elements seen by the iteration were present in the input at some point. That's a pretty weak guarantee!

It is, however, stronger than what I'd call inconsistent behavior. Consider this code that uses indexes (instead of an Iterator object) to iterate over an ArrayList:

    List<String> input = Arrays.asList("a", "b", "c", "d", "e");
    List<String> output = new ArrayList<>();

    List<String> arrayList = new ArrayList<>(input);
    for (int i = 0; i < arrayList.size(); i++) {
        String s = arrayList.get(i);
        output.add(s);
        if (i == 2) {                   // <<< MODIFY
            arrayList.add(0, "XXX");
        }
    }

In this case the output is

    [a, b, c, c, d, e]

which repeats the element "c" which occurs only once in the input. That's clearly an error. Or, suppose the line marked MODIFY is changed to this:

        if (s.equals("c")) {

In this case the loop will never terminate! You can also easily imagine cases where, with an index-style loop, modifying the list at exactly the right (wrong) time will cause an IndexOutOfBoundsException.

So you can see that there are a lot of things that can go wrong with iterating over a collection while it's being modified. Weakly consistent iteration provides guarantees against repeated elements and against a variety of errors or infinite loops that can occur. The "weakness" is that they provide few guarantees about exactly which elements are observed during iteration.

Finally, note that fail-fast and weakly consistent are particular terms that are defined and used in the Java SE specifications. The term "fail-safe" isn't used anywhere in official Java documentation. Therefore, I recommend not using "fail-safe" to describe any of the Java collections' concurrent-modification policies. Some people think that "fail-safe" is the opposite of "fail-fast" and you'll see this occur in various blogs and articles around the internet. Frankly, I think this is sloppy writing that should be avoided.