ConcurrentNavigableMap, interpretation of weakly consistent iterators

1.2k views Asked by At

In the JavaDoc for ConcurrentNavigableMap, I'm a bit confused as to the following:

The view's iterator is a "weakly consistent" iterator that will never throw ConcurrentModificationException, and guarantees to traverse elements as they existed upon construction of the iterator, and may (but is not guaranteed to) reflect any modifications subsequent to construction.

The wording seems the same in implementations of the interface like ConcurrentSkipListMap.

What does this mean, it seems a contradiction - either it could guarantee to traverse elements as they existed upon construction, OR it might reflect modifications subsequent to construction??

UPDATE: I'd basically like to know if creating an iterator on ConcurrentNavigableMaps like ConcurrentSkipListMap, creates a "snapshot" view of the map.

2

There are 2 answers

0
npgall On BEST ANSWER

To answer my own question, there is a discussion of the strength of the consistency guarantee provided by iterators on the concurrency-interest mailing list here.

The author of ConcurrentHashMap and ConcurrentSkipListMap, Doug Lea, appears to agree that the guarantee is not much of a guarantee at all, and that in the case of ConcurrentHashMap, the iterator can report the map to be in a state that it was never actually in.

For those curious, the source of ConcurrentSkipListMap, specifically its internal Iter (iterator) class is here.

The iterator in ConcurrentSkipListMap iterates the regular nodes within the skip list, and those nodes are linked using volatile references. It might be the case that this somewhat confusing JavaDoc statement is actually [simply] referring to a happens-before guarantee. i.e. that changes made by other threads prior to creating the iterator, will be simply be visible to the thread driving the iteration.

3
axtavt On

The wording is strange, but actually it means that iterator may reflect some of the changes made after construction of the iterator, but it's not guaranteed to reflect all of them. Except for these reflected changes, elements are traversed as they existed upon construction.

In practice it means (roughly) that as weakly consistent iterator traverses a collection, it cannot reflect changes in parts of collection that already have been traversed, but reflects changes in parts of collection that haven't been traversed yet.