2

Fail-fast iterator iterates over collection. If collection gets modified while iterating, we get exception. Opposite applies for fail-safe, where iteration is happening on one collection, while write operation happen on copy of it, thus it is how fail-safe works (f.e. CopyOnWriteArrayList).

Can someone explain me how does ConcurrentSkipListSet has fail-safe? There are no copies when modifying collection (like CopyOnWrite classes do), so how does it happen? I read because its Iterator is weakly consistent. I read docs, I still don't understand. (but I do know what code visibility or happens-before relation in concurrency is).

Does anyone have logic and easy to remember explanation, as I am a beginner?

//Example:

 ConcurrentSkipListSet<Integer> set = new ConcurrentSkipListSet<>();
      set.add(1);
      set.add(2);
      set.add(3);
      set.add(4);

      Iterator<Integer> iterator = set.iterator();
      while (iterator.hasNext()){
          System.out.println(iterator.next());
          set.remove(4);
      }

OUTPUT:
1
2
3

I was expecting ConcurrentException to be thrown here.. Please help :(

Ana Maria
  • 475
  • 2
  • 11

1 Answers1

2

The "weakly consistent" term is defined in the java.util.concurrent package description:

Most concurrent Collection implementations (including most Queues) also differ from the usual java.util conventions in that their Iterators and Spliterators provide weakly consistent rather than fast-fail traversal:

  • 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.

In this case with ConcurrentSkipListSet, the iterator does not have a "fast-fail" property, instead it reflects the modification of 4 having been removed from the set.

Internally, ConcurrentSkipListSet is implemented with ConcurrentSkipListMap, and its iterators are implemented by keeping track of which skip list node should be traversed next. This naturally gives you the "weakly consistent" property: If the next item is deleted, the iterator will still return it. If items beyond the next are deleted, the iterator will reflect those changes.

Joni
  • 108,737
  • 14
  • 143
  • 193
  • Why did they even invent it? Couldn't they fix that problem using snapshot like some classes did? In weakly consistent iterator inserts might not be visible to my iterator, thus be incomplete.. – Ana Maria Aug 22 '20 at 11:46
  • 1
    To get a consistent snapshot of a skiplist you would have to make all write operations wait until the snapshot is complete. ConcurrentSkipListMap was designed to take advantage of a "lock-free" algorithm where no read or write operation has to wait. – Joni Aug 22 '20 at 12:14
  • Great! Why don't Stack or Vector use it as well? I noticed they have fail-fast. Was is because they are 'old' and there was no such thing as 'weakly consistent iterator' at a time? – Ana Maria Aug 22 '20 at 12:16
  • 1
    Yes the reason is historical: "weakly consistent" iterator concept was introduced with the `java.util.concurrent` package in Java 1.5. "Fail fast" iterator concept was introduced with the "java collections framework" in Java 1.2. Vector and Stack are even older than that, and their Java 1.0 methods like `Vector.elements` don't give you any guarantees at all. – Joni Aug 22 '20 at 12:28
  • Then why is it called CONCURRENT SkipListMap if there are no locks in the first place? It doesn't fix concurrency issues, so why call it Concurrent? Only thing it fixed is fail-fast iterator, which is now weakly consistent. – Ana Maria Aug 22 '20 at 14:18
  • 1
    It's called "concurrent" because it gives you the memory consistency guarantees needed for concurrent programming as listed in the [package summary](https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/concurrent/package-summary.html). The implementation happens to give these guarantees without using heavy weight lock mechanisms that force threads to wait. – Joni Aug 22 '20 at 14:37
  • 3rd thanks from me! You answered me few times on Stack and every single time your answer helped the most. – Ana Maria Aug 22 '20 at 14:52