Detailed Explanation of fail fast of Fast Failure Mechanism in Java Set

Brief introduction

We know that many collections under the Collection interface in Java are thread-unsafe, for example, java. util. ArrayList are not thread-safe, so if other threads modify list during the use of iterators, ConcurrentModificationException will be thrown, which is called fail-fast policy.

This 1 strategy is implemented in the source code through modCount domain, modCount is the number of modifications as its name implies, and the modification of ArrayList content will increase this value, so this value will be assigned to expectedModCount of iterator during iterator initialization. In the iterative process, it is judged whether modCount and expectedModCount are equal. If not, it means that other threads have modified list
Note that modCount is declared as volatile, which guarantees the visibility of modifications between threads.

modCount and expectedModCount

modCount and expectedModCount are used to represent the number of modifications, where modCount represents the number of modifications of the set, which includes modifications made when calling add, remove, clear methods of the set itself and modifications made when calling modifications made by modifying methods of the set iterator. expectedModCount represents the number of times the iterator modifies the collection.

The purpose of setting expectedModCount is to ensure that the list object can have only one iterator to modify list during iterator use.

The value of the modCount of the object is passed to the expectedModCount of the iterator when the iterator is created:

 private class ListItr implements ListIterator<E> {
  private Node<E> lastReturned;
  private Node<E> next;
  private int nextIndex;
  private int expectedModCount = modCount;

If multiple iterators are created to modify a collection object, there will be one modCount and multiple expectedModCount, and the values of modCount will be different, which will lead to the values of moCount and expectedModCount being different, resulting in an exception:

public E next() {
  checkForComodification();
  if (!hasNext())
  throw new NoSuchElementException();

  lastReturned = next;
  next = next.next;
  nextIndex++;
  return lastReturned.item;
 }

checkForComodification in the above code checks whether the values of modCount and expectedModCount are 1, and throws an exception if they are not 1.

 final void checkForComodification() {
  if (modCount != expectedModCount)
   throw new ConcurrentModificationException();
  

How is modCount modified

 //  Add an element to the end of the queue 
 public boolean add(E e) {
  //  Modify modCount
  ensureCapacity(size + 1); // Increments modCount!!
  elementData[size++] = e;
  return true;
 }


 //  Adds an element to a specified location 
 public void add(int index, E element) {
  if (index > size || index < 0)
   throw new IndexOutOfBoundsException(
   "Index: "+index+", Size: "+size);

  //  Modify modCount
  ensureCapacity(size+1); // Increments modCount!!
  System.arraycopy(elementData, index, elementData, index + 1,
    size - index);
  elementData[index] = element;
  size++;
 }

 //  Add a collection 
 public boolean addAll(Collection<? extends E> c) {
  Object[] a = c.toArray();
  int numNew = a.length;
  //  Modify modCount
  ensureCapacity(size + numNew); // Increments modCount
  System.arraycopy(a, 0, elementData, size, numNew);
  size += numNew;
  return numNew != 0;
 }


 //  Deletes an element at a specified location 
 public E remove(int index) {
  RangeCheck(index);

  //  Modify modCount
  modCount++;
  E oldValue = (E) elementData[index];

  int numMoved = size - index - 1;
  if (numMoved > 0)
   System.arraycopy(elementData, index+1, elementData, index, numMoved);
  elementData[--size] = null; // Let gc do its work

  return oldValue;
 }


 //  Quickly delete an element at a specified location 
 private void fastRemove(int index) {

  //  Modify modCount
  modCount++;
  int numMoved = size - index - 1;
  if (numMoved > 0)
   System.arraycopy(elementData, index+1, elementData, index,
        numMoved);
  elementData[--size] = null; // Let gc do its work
 }

 //  Empty the collection 
 public void clear() {
  //  Modify modCount
  modCount++;

  // Let gc do its work
  for (int i = 0; i < size; i++)
   elementData[i] = null;

  size = 0;
 }

That is to say, modcount + + will be executed when adding or deleting data to the collection, so if a thread is still using iterators to traverse this list, it will find an exception and fail-fast (quick failure) will occur

Comparison of fail-fast (Fast Failure) and fail-safe (Safe Failure)

The rapid failure of Iterator is based on the fact that copying the underlying collection is a shallow copy, so it is affected by modifications on the source collection. All collection classes under the java. util package fail quickly

All the classes under the java. util. concurrent package fail to secure using locks.

A fast-failing iterator throws an ConcurrentModificationException exception, whereas a safe-failing iterator never throws such an exception.

What problem does fail-fast solve

fail-fast mechanism is an error detection mechanism.

It can only be used to detect errors, because JDK does not guarantee that fail-fast mechanism 1 will happen. Just tell the client that there is a multithread safety problem in a multithreaded environment.
Therefore, if the collection of fail-fast mechanisms is used in a multithreaded environment, it is recommended to use "classes under java. util. concurrent package" instead of "classes under java. util package".

How to Resolve fail-fast Events

ArrayList corresponds to CopyOnWriteArrayList. Let's look at the source code of CopyOnWriteArrayList first:

public class CopyOnWriteArrayList<E>
 implements List<E>, RandomAccess, Cloneable, java.io.Serializable {

 ...

 //  Returns the iterator corresponding to the collection 
 public Iterator<E> iterator() {
  return new COWIterator<E>(getArray(), 0);
 }

 ...

 private static class COWIterator<E> implements ListIterator<E> {
  private final Object[] snapshot;

  private int cursor;

  private COWIterator(Object[] elements, int initialCursor) {
   cursor = initialCursor;
   //  New COWIterator Saves the elements in the collection to the 1 In a new copy array. 
   //  In this way, when the data of the original set changes, the values in the copied data will not change. 
   snapshot = elements;
  }

  public boolean hasNext() {
   return cursor < snapshot.length;
  }

CopyOnWriteArrayList implements Iterator by itself, and there is no so-called checkForComodification () in the Iterator implementation class of CopyOnWriteArrayList, and ConcurrentModificationException exception will not be thrown

CopyOnWriteArrayList When you create a new COWIterator, the elements in the collection are saved to a new copy array. In this way, when the data of the original set changes, the values in the copied data will not change.

Summarize