Fail-fast vs. Fail-Safe

Fail-fast vs. Fail-Safe

Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

Writing in the front

Recently, I got familiar with the commonly used data structures again in the process of brushing the questions. I found that the fail-fast and Fail-safe mechanisms were a little vague. Here I rearrange them to deepen my impression. Remind you to deal with the data structure carefully during the normal development process.

Comments in documents

Note that this implementation is not synchronized. If multiple threads access a linked list concurrently, and at least one of the threads modifies the list structurally, it must be synchronized externally. (A structural modification is any operation that adds or deletes one or more elements; merely setting the value of an element is not a structural modification.) This is typically accomplished by synchronizing on some object that naturally encapsulates the list. If no such object exists, the list should be “wrapped” using the Collections.synchronizedList method. This is best done at creation time, to prevent accidental unsynchronized access to the list: List list = Collections.synchronizedList(new LinkedList(…) );

The iterators returned by this class’s iterator and listIterator methods are fail-fast: if the list is structurally modified at any time after the iterator is created, in any way except through the Iterator’s own remove or add methods, the iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

The Javadoc from LinkedList briefly states that the implementation of LinkedList is not thread-safe. When a LinkedList is manipulated in a multi-threaded environment and its structure is changed (structural changes are simply defined as adding or removing elements; modifying the value of the element itself is not structural changes), it needs to be synchronized to other threads. That is to say, you need to use synchronization lock, if there is no corresponding synchronization mechanism. It can be wrapped using synchronizedList under Collections. The main purpose is to build the iterator. Changes to data structures (add and remove) must use the iterator’s own add and remove methods. And they used the fail – fast mechanism, that is not in accordance with the rules to manipulate data structures will quote ConcurrentModificationException, concurrent modification abnormalities. A simple summary leads to the conclusion (non-thread-safe data structures) :

• A non-thread-safe linear data structure that must be used when the structure is modified concurrentlyiteratorsMethod (The add and remove).
• Concurrent modification does not have to occur only in multithreaded cases, as in single-threaded cases, traversal deletes will also be reportedConcurrentModificationException. (Use its own add and remove methods).
• Because it isFail-FastYou can use your own synchronization mechanism, or you can useCollectionsWrap it up and use ititeratorsTo manipulate data structures.

What is fail-fast?

Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.

In simple terms, Fail-fast is simply a detection mechanism that throws an exception to alert developers when they carelessly write structural changes like this without using any synchronization methods during application development. Since fail-Fast is a reminder mechanism, it also determines its limitations (not 100% detection), requiring developers to not rely on this mechanism to ensure the robustness of the code in the actual development process (fail-fast is not a hard guarantee).

Look at two examples of scenarios

public class FailFast {
  public static void main(String[] args) {
    List<String> list = new ArrayList<>();
    list.add("1");
    list.add("2");
    list.add("3");
    list.add("4");
    list.add("5");
    list.add("6");
  }
  
  private static void deleteItem(List<String> list) {
    for (String item: list) {
      if ("2".equals(item)) { list.remove(item); }}}public static void deleteItem2(List<String> list) {
    for (int i = 0; i < list.size(); i++) {
      String item = list.get(i);
      if ("2".equals(item)) { list.remove(item); }}}}//(--> deleteItem)Exception in thread "main" java.util.ConcurrentModificationException
//at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:911)
//at java.util.ArrayList$Itr.next(ArrayList.java:861)
Copy the code

When the methods deleteItem and deleteItem2 are respectively executed, it can be found that the enhanced for loop method deleteItem directly reported concurrent modification exceptions when deleting elements, but the ordinary for loop does not delete elements, and can successfully delete elements. WTF? Is the analysis wrong? Again, the exception itself was not detected, and this was indeed a modification of the structure. Go back and read the notes carefully.

The iterators returned by this class’s iterator and listIterator methods are fail-fast: if the list is structurally modified at any time after the iterator is created, in any way except through the Iterator’s own remove or add methods, the iterator will throw a ConcurrentModificationException.

Iterator is fail-fast, and ArrayList implements the List interface, which inherits from Collection, which in turn inherits from Iterable. ArrayList implements Iterable internally. The enhanced for loop is the same as the normal for loop calls the remove method.

public boolean remove(Object o) {
  if (o == null) {
    for (int index = 0; index < size; index++)
      if (elementData[index] == null) {
        fastRemove(index);
        return true; }}else {
    for (int index = 0; index < size; index++)
      if (o.equals(elementData[index])) {
        fastRemove(index);
        return true; }}return false;
}

private void fastRemove(int index) {
  modCount++;
  int numMoved = size - index - 1;
  if (numMoved > 0)
    System.arraycopy(elementData, index+1, elementData, index,numMoved);
  elementData[--size] = null; // clear to let GC do its work
}
Copy the code

The problem must be to enhance the underlying implementation of the for loop, using IDEA to look at the bytecode information and see how it differs from a regular for loop.

The iterator is designed as a fail-fast mechanism, and structural changes can only be made using the iterator’s add and remove methods. Otherwise, concurrent modification exceptions will be reported. See how the source code is checked:

@SuppressWarnings("unchecked")
public E next(a) {
  checkForComodification();
  int i = cursor;
  if (i >= size)
    throw new NoSuchElementException();
  Object[] elementData = ArrayList.this.elementData;
  if (i >= elementData.length)
    throw new ConcurrentModificationException();
  cursor = i + 1;
  return (E) elementData[lastRet = i];
}

final void checkForComodification(a) {
  if(modCount ! = expectedModCount)throw new ConcurrentModificationException();
}
Copy the code

The key is checkForComodification, no matter adding or deleting the modCount count field maintained inside the element, it will increment, while enhancing the iterator iteration used at the bottom of the for loop (which is actually the syntactic sugar of iterator iteration). This modCount is validated in the next method. When found the structure of the data with the modified will throw ConcurrentModificationException concurrent modification abnormalities.

When are exceptions not thrown?

Thinking about a problem, the enhanced for loop to element deletion (do not use the iterator) will throw ConcurrentModificationException? The answer is no. Look at the Iterator

internal implementation class Itr in ArrayList:

The condition of the delete while loop is hasNext(), which determines if there are any remaining elements to iterate over, and goes to the next method. Taking the deletion in this paper as an example, the whole call process is as follows:

hasNext() -->next(checkForComodification) -->remove(modeCount++) -->hasNext().
Copy the code

Intuitively, as long as the delete operation satisfies hasNext() == false, it is also cursor! If =size is false, then when cursor==size, the loop exits, then it is natural that the structure of the data is not detected to be modified, and the checkForComodification exception will not be thrown. The size of the array is decremented by remove, –size, while the cursor in next is set to CURSOR = I +1. I +1=–size, which happens to be the next-to-last element. Is that right? Test it out:

// delete element "2" given test data: [1,2,3]
List<String> list = new ArrayList<>();
list.add("1");
list.add("2");
list.add("3");
[1,2,3,4,5,6] delete element "5"
List<String> list = new ArrayList<>();
list.add("1");
list.add("2");
list.add("3");
list.add("4");
list.add("5");
list.add("6");
Copy the code

The corresponding results are:

The result is the same as the verification. As long as the penultimate element of the set is deleted, the detection of checkForComodification exception can be bypassing, but it is very dangerous ⚠️. This also shows that Fail-fast is only an internally implemented detection mechanism, and may not even be a “fault tolerant mechanism”. The fail-fast behavior of iterators should be used only to detect bugs. Programs should be designed to avoid relying on this mechanism for their own bottom line, embarrassingly it does not fully cover 😊. To sum up:

• Fail-fast is not 100% for concurrent modification exceptions and is simply a bug detection mechanism.

• The underlying implementation that enhances the For loop is the iterator, which is essentially a syntactic sugar For iterator traversal. Iterators, on the other hand, follow the fail-fast mechanism (throw concurrent modification exceptions immediately when non-Iterator methods change data structures).

• In the case of non-thread-safe data structures such as ArrayList and LinkedList, the add and remove methods of the internal iterator must be used for concurrent modification. Of course, in the case of multiple threads, synchronization mechanisms are also required.

• The normal for loop does not have validation, but this operation is also unsafe. When there is duplicate data, there will be omissions, so it is no longer validated.

• Concurrent modification does not just refer to multi-threaded situations, this should not be confused, the examples here are all single-threaded.

Why learn about fail-fast

Quote a sentence of foreign little brother article, original

Difference between Fail fast and fail safe iterator or Fail fast vs Fail Safe iterator is one of those questions which are used to test your knowledge about the topic Concurrency.

I think it’s well explained, including stackOverflow where there’s a lot of discussion about this. Stackoverflow, the foundation of concurrency, includes comparisons to Fail-safe to better understand both concepts. Usually in the process of program development, will also remind attention to this aspect of the content, a little more thinking.

“Fail – Safe” mechanism

The reason for the fail-safe quotation marks is that the official term fail-safe is not found in javadoc comments. Using the previous delete as an example, replace the ArrayList with the thread-safe class CopyOnWriteArrayList and see what happens.

public static void main(String[] args) {
  List<String> list = new CopyOnWriteArrayList<>();
  list.add("1");
  list.add("2");
  list.add("3");
  list.add("4");
  list.add("5");
  list.add("6");
  
  deleteItem(list);
}
private static void deleteItem(List<String> list) {
  for (String item : list) {
    if ("2".equals(item)) { list.remove(item); }}}private static void deleteItem3(List<String> list) {
  Iterator<String> iterator = list.iterator();
  while (iterator.hasNext()) {
    String item = iterator.next();
    if ("2".equals(item)) { iterator.remove(); }}}// The printed information is not pasted, the bytecode information is not changed
Copy the code

You can see that if you call the remove method in the enhanced for loop, nothing happens, but if you call the deleteItem3 method, you throw an exception:

Iterator

is implemented in CopyOnWriteArrayList as COWIterator

and it specifies that the Iterator

will throw an exception when it deletes:

There is also no verification of modCount in next as in ArrayList, so there are no concurrent exceptions. It seems that many developers are calling this “mechanism” “fail-safe” in comparison to Fail-fast. (At least not in the documentation).

Stamp here

Take a look at the remove method of CopyOnWriteArrayList:

Thread-safe because not only do operations lock, but they actually copy data, which is a natural weakness of CopyOnWriteArrayList, which takes up extra memory. Of course, in the actual development process, reasonable technical solutions and selection is still necessary.

link

stackoverflow

Fail Fast and Fail Safe Iterators in Java