1. Introduction to fail-fast
"Fast Fail" is also called fail-fast, which is an error detection mechanism for Java collections. When a thread iterates over the collection, other threads are not allowed to modify the collection structurally.
For example: suppose there are two threads (thread 1 and thread 2), and thread 1 traverses the elements in set A through Iterator. At some point, thread 2 modifies the structure of set A (a modification on the structure, rather than simply modifying the content of the set element), then the program will throw a ConcurrentModificationException exception, thereby generating fail-fast.
The iterator's fast failure behavior cannot be guaranteed, it cannot guarantee that the error will occur, so the ConcurrentModificationException should be used only to detect bugs.
All collection classes in the Java.util package fail quickly, while the collection classes in the java.util.concurrent package fail safely;
The iterator that fails quickly throws a ConcurrentModificationException, while the iterator that fails safely never throws this exception.
2 fail-fast examples
Sample code: (FastFailTest.java)
import java.util.*;import java.util.concurrent.*;/* * @desc Test program for Fast-Fail in java collection. * * Conditions for the fast-fail event: When multiple threads operate on the Collection, if one of the threads traverse the collection through the iterator, the content of the collection is changed by other threads; a ConcurrentModificationException exception will be thrown. * Fast-fail solution: If you process it through the corresponding class under the util.concurrent collection package, the fast-fail event will not be generated. * * In this example, the two cases of ArrayList and CopyOnWriteArrayList are tested respectively. ArrayList will generate a fast-fail event, while CopyOnWriteArrayList will not generate a fast-fail event. * (01) When using ArrayList, a fast-fail event will be generated and a ConcurrentModificationException exception will be thrown; the definition is as follows: * private static List<String> list = new ArrayList<String>(); * (02) When using CopyOnWriteArrayList, a fast-fail event will not be generated; the definition is as follows: * private static List<String> list = new CopyOnWriteArrayList<String>(); * * @author skywang */public class FastFailTest { private static List<String> list = new ArrayList<String>(); //private static List<String> list = new CopyOnWriteArrayList<String>(); public static void main(String[] args) { // Start two threads at the same time to operate on the list! new ThreadOne().start(); new ThreadTwo().start(); } private static void printAll() { System.out.println(""); String value = null; Iterator iter = list.iterator(); while(iter.hasNext()) { value = (String)iter.next(); System.out.print(value+", "); } } /** * Add 0,1,2,3,4,5 to the list in turn. After adding a number, iterates through printAll() */ private static class ThreadOne extends Thread { public void run() { int i = 0; while (i<6) { list.add(String.valueOf(i)); printAll(); i++; } } } /** * Add 10,11,12,13,14,15 to the list in turn. After each number is added, it will traverse the entire list through printAll() */ private static class ThreadTwo extends Thread { public void run() { int i = 10; while (i<16) { list.add(String.valueOf(i)); printAll(); i++; } } }} Run the code as a result and throws an exception java.util.ConcurrentModificationException! That is, a fail-fast event is generated!
Results Description
(01) In FastFailTest, start two threads at the same time to operate the list through new ThreadOne().start() and new ThreadTwo().start().
ThreadOne thread: add 0, 1, 2, 3, 4, 5 to the list. After each number is added, the entire list is traversed through printAll().
ThreadTwo thread: add 10, 11, 12, 13, 14, 15 to the list. After each number is added, the entire list is traversed through printAll().
(02) When a thread traverses the list, the content of the list is changed by another thread; a ConcurrentModificationException exception will be thrown, resulting in a fail-fast event.
3. Fail-fast solution
The fail-fast mechanism is an error detection mechanism. It can only be used to detect errors, because JDK does not guarantee that the fail-fast mechanism will happen. If you use a collection of fail-fast mechanism in a multi-threaded environment, it is recommended to use "classes under java.util.concurrent package" to replace "classes under java.util package".
Therefore, in this example, you only need to replace ArrayList with the corresponding class under the java.util.concurrent package. That is, the code
private static List<String> list = new ArrayList<String>();
Replace with
private static List<String> list = new CopyOnWriteArrayList<String>();
This solution can be solved.
4. Fail-fast principle
The fail-fast event is generated, which is triggered by throwing a ConcurrentModificationException exception.
So, how does ArrayList throw a ConcurrentModificationException exception?
We know that ConcurrentModificationException is an exception thrown when operating Iterator. Let's take a look at the Iterator source code first. The Iterator of ArrayList is implemented in the parent class AbstractList.java. The code is as follows:
package java.util;
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> { ... // The unique attribute in AbstractList// Used to record the number of List modified: every time (add/delete operations, etc.), modCount+1 protected transient int modCount = 0; // Return the iterator for List. In fact, it is to return the Itr object. public Iterator<E> iterator() { return new Itr(); } // Itr is the implementation class of Iterator (iterator). private class Itr implements Iterator<E> { int cursor = 0; int lastRet = -1; // Modify the record value of the number. // Every time a new Itr() object is created, the corresponding modCount when the new object is created will be saved; // Every time you traverse the elements in the List, you will compare whether expectedModCount and modCount are equal; // If not equal, a ConcurrentModificationException exception is thrown, resulting in a fail-fast event. int expectedModCount = modCount; public boolean hasNext() { return cursor != size(); } public E next() { // Before obtaining the next element, it will be judged whether the "modCount saved when creating a new Itr object" and "current modCount" are equal; // If it is not equal, a ConcurrentModificationException exception is thrown, resulting in a fail-fast event. checkForComodification(); try { E next = get(cursor); lastRet = cursor++; return next; } catch (IndexOutOfBoundsException e) { checkForComodification(); throw new NoSuchElementException(); } } public void remove() { if (lastRet == -1) throw new IllegalStateException(); checkForComodification(); try { AbstractList.this.remove(lastRet); if (lastRet < cursor) cursor--; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException e) { throw new ConcurrentModificationException(); } } final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } } ...} From this, we can find that checkForComodification() is executed when next() and remove() are called. If "modCount is not equal to expectedModCount", a ConcurrentModificationException exception is thrown, resulting in a fail-fast event.
To understand the fail-fast mechanism, we need to understand when "modCount does not equal expectedModCount"!
From the Itr class, we know that expectedModCount is assigned to modCount when creating the Itr object. Through Itr, we know that expectedModCount cannot be modified to not equal modCount. Therefore, what needs to be verified is when modCount will be modified.
Next, let's check the source code of ArrayList to see how modCount is modified.
package java.util;public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{ ... // When the capacity changes in the list, the corresponding synchronization function public void ensureCapacity(int minCapacity) { modCount++; int oldCapacity = elementData.length; if (minCapacity > oldCapacity) { Object oldData[] = elementData; int newCapacity = (oldCapacity * 3)/2 + 1; if (newCapacity < minCapacity) newCapacity = minCapacity; // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } } // Add element to the last of the queue public boolean add(E e) { // Modify modCount ensureCapacity(size + 1); // Increments modCount!! elementData[size++] = e; return true; } // Add element to the 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 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; } // Delete the element in the 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 elements in the 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 } // Clear 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; } ...} From this, we found that whether it is add(), remove(), or clear(), the value of modCount will be changed as long as it involves modifying the number of elements in the set.
Next, let’s systematically sort out how fail-fast is produced. The steps are as follows:
(01) Create a new ArrayList name as arrayList.
(02) Add content to the arrayList.
(03) Create a new "thread a" and read the value of arrayList repeatedly through Iterator in "thread a".
(04) Create a new "thread b" and delete a "node A" in the arrayList in "thread b".
(05) At this time, interesting events will occur.
At some point, "thread a" creates the Iterator of the arrayList. At this time, "node A" still exists in the arrayList. When creating an arrayList, expectedModCount = modCount (assuming that their values are N at this time).
At some point during the process of traversing the arrayList, "thread b" executes, and "thread b" deletes "node A" in the arrayList. When "thread b" executes remove() for delete operation, "modCount++" is executed in remove(), and modCount becomes N+1!
"Thread a" then traverses. When it executes the next() function, checkForComodification() is called to compare the sizes of "expectedModCount" and "modCount"; and "expectedModCount=N", "modCount=N+1", so a ConcurrentModificationException exception is thrown, resulting in a fail-fast event.
At this point, we have a complete understanding of how fail-fast is produced!
That is, when multiple threads operate on the same set, when a thread accesses the set, the content of the set is changed by other threads (that is, other threads change the value of modCount through add, remove, clear and other methods); at this time, a ConcurrentModificationException exception will be thrown, resulting in a fail-fast event.
5. The principle of solving fail-fast
The above explains the "methods to solve the fail-fast mechanism" and also knows the "root cause of the failure-fast". Next, let's talk further about how to solve the fail-fast event in the java.util.concurrent package.
Let's explain it with the CopyOnWriteArrayList corresponding to ArrayList. Let's first take a look at the source code of CopyOnWriteArrayList:
package java.util.concurrent;import java.util.*;import java.util.concurrent.locks.*;import sun.misc.Unsafe;public class CopyOnWriteArrayList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable { ... // Return the iterator corresponding to the collection public Iterator<E> iterator() { return The fast-fail implementation methods in the new collection class are almost the same. Let's take the simplest ArrayList as an example. protected transient int modCount = 0; records the number of times we modify ArrayList. For example, when we call add(), remove(), etc. to change data, modCount++ will be changed. protected transient int modCount = 0; records the number of times we modify ArrayList. For example, when we call add(), remove(), etc. to change data, modCount++ will be changed. 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; // When creating a new COWIterator, save the elements in the collection to a new copy array. // In this way, when the data of the original set changes, the values in the copy data will not change either. snapshot = elements; } public boolean hasNext() { return cursor < snapshot.length; } public boolean hasPrevious() { return cursor > 0; } public E next() { if (! hasNext()) throw new NoSuchElementException(); return (E) snapshot[cursor++]; } public E previous() { if (! hasPrevious()) throw new NoSuchElementException(); return (E) snapshot[--cursor]; } public int nextIndex() { return cursor; } public int previousIndex() { return cursor-1; } public void remove() { throw new UnsupportedOperationException(); } public void set(E e) { throw new UnsupportedOperationException(); } public void add(E e) { throw new UnsupportedOperationException(); } } ...} From this we can see:
(01) Unlike ArrayList inherits from AbstractList, CopyOnWriteArrayList does not inherit from AbstractList, it only implements the List interface.
(02) The Iterator returned by the iterator() function of ArrayList is implemented in AbstractList; while CopyOnWriteArrayList implements the Iterator itself.
(03) When next() is called in ArrayList's Iterator implementation class, "call checkForComodification() to compare the sizes of 'expectedModCount' and 'modCount'"; however, there is no so-called checkForComodification() in the Iterator implementation class of CopyOnWriteArrayList, and the ConcurrentModificationException will not be thrown!
6. Summary
Since HashMap (ArrayList) is not thread-safe, if other threads modify the map during the process of using the iterator (the modification here refers to structural modification, not simply to modify elements of the collection content), then a ConcurrentModificationException will be thrown, that is, the fail-fast strategy is mainly implemented through the modCount field to ensure visibility between threads. modCount is the number of modifications. This value will be added to the modification of HashMap (ArrayList) content. Then during the initialization of the iterator, this value will be assigned to the iterator's expectedModCount.
But the fail-fast behavior is not guaranteed, so the practice of relying on this exception is wrong