[Java] Fail-Fast Iterator vs Fail-Safe Iterator

0. 학습 목적

• iterator.next()를 활용하여 Collections의 자료구조들을 순회하면서, 자료 구조 내의 값들을 수정하려고 하면 ConcurrntModificationException이 나는 이유를 이해한다.
• Fail-Fast Interator와 Fail-Safe Iterator의 차이를 이해한다.

1. Fail-Fast 전략과 Fail-Safe 전략

Fail-Fast 전략 은 시스템 작동 중 실패 지점이 생기면 그 즉시 모든 작동을 멈추는 전략이다. 이는 실패 지점에 대한 명확한 판단과 일관성 유지를 목표로 한다.
Fail-Safe 전략 은 시스템 작동 중 실패를 맞딱뜨린 상황에도 작동을 중단하지 않는다. 다만 최대한 실패가 커지지 않는 방향으로 나아가는 전략이다.

Java는 Iterator 패턴을 Collection 산하 자료구조에 적용함에 있어 이 두가지 전략을 모두 사용하여 구현하였다. 따라서 Java의 Iterator의 종류는 Fail-Fast Iterators 와 Fail-Safe Iterators로 나뉜다.

2. Fail-Fast Iterators

(1) 정의

Fail-Fast Iterators 는 그것이 현재 순회하고 있는 자료구조에 '구조적 수정' 이 일어났을 경우 '최대한' ConcurrencyModificationException을 발생시키는 Iterator이다.

여기서 두 가지 사항을 강조했는데 바로 '구조적 수정' 과 '최대한' 이다.

A. 구조적 수정

구조적 수정이란 말 그대로 자료구조에 구조적인 변화가 생기는 수정이다. 즉 특정 값을 삽입하거나 삭제해서 실질적으로 자료구조의 크기에 변화를 주는 작업을 말한다.

public static void main(String[] args) throws IOException {  
    HashMap<Integer, Integer> map = new HashMap<>();  
    map.put(1,1);  
    map.put(2,2);  
    Iterator<Integer> iter = map.keySet().iterator();  
    while (iter.hasNext()){  
        map.put(1,12324);  
        System.out.println(map.get(iter.next()));  
        map.put(2,4);  
    }  
}

예를 들어 위의 수정은 HashMap의 특정 Key의 value를 바꾸는 작업이기에 구조적 수정이라 볼 수 없다. 따라서 Iterator 작업 도중 위와 같은 수정을 가해도 오류없이 동작한다.

public static void main(String[] args) throws IOException {  
    HashMap<Integer, Integer> map = new HashMap<>();  
    map.put(1,1);  
    map.put(2,2);  
    Iterator<Integer> iter = map.keySet().iterator();  
    while (iter.hasNext()){  
        map.remove(1);  
        System.out.println(map.get(iter.next()));  
        map.put(3,2);  
    }  
}

반면 위의 수정은 구조적 변화를 일으킨다. 따라서 다음과 같은 오류가 발생한다.

B. '최대한' 오류를 발생

The Fail-Fast behavior isn't guaranteed to happen in all scenarios as it's impossible to predict behavior in case of concurrent modifications. These iterators throw ConcurrentModificationException on a best effort basis.

위는 Baedung 에 나온 Fail-Fast에 대한 설명이다. 위 설명대로 동시 수정 사항이 생기는 것을 예측할 수 없기 때문에, 구조적 동시 수정이 생기는 모든 시나리오에 예외가 발생한다는 것을 보장할 수가 없다. 따라서 '최대한' 이라는 표현을 썼다.

(2) 동작 과정

1. Iterator.next()로 자료구조 순회 시작

2. 본격적으로 다음 index를 바라보기 전에 iterator가 작동 중인 자료구조의 modCount 확인

3. 만약 해당 값이 순회 시작 전이랑 비교해서 바뀌어 있으면 바로 ConcurrencyModificationException 발생시킴.

   Collections를 상속받은 모든 자료 구조들은 내부에 modCount라는 int 형 변수를 가진다. 해당 변수는 자료구조에 구조적 변경 (삽입 혹은 삭제)가 생겼을 때마다 count가 1씩 오른다.

만약 특정 Fail-Fast 전략을 따르는 자료구조에 Iterator 구현체를 만들었다면, Iterator는 순회하기 위해 iterator.next() 라는 함수를 사용할 것이다. 해당 함수는 실제 작동을 하기 전에 modcount가 순회 전이랑 값이 바뀌었는지 확인한다. 만약 바뀌어 있으면 그 자리에서 ConCurrencyModificationException을 발생시키고 작동을 중지한다.

(3) 종류

우리가 알고리즘을 풀며 쓰는 자료구조들 (즉 java.util.package 에 있는 Collections 자료구조)은 모두 Fail-Fast 전략을 사용하고 있다.

(4) 그럼에도 자료구조를 순회하면서 삭제해야할 경우 어떻게 할까?

이 경우에는 해당 자료구조의 remove 대신에 Iterator의 remove를 사용하면 된다.
Iterator의 멤버 함수 remove는 동시수정 예외를 우회하며 순회와 동시에 삭제를 할 수 있는 매커니즘을 가지고 있기 때문이다.

A. iterator.remove() 내부 메커니즘

이는 Iterator를 구현한 각 자료구조의 구현체마다 조금씩 다르다. 가장 간단하게 ArrayList의 Iterator 구현체를 예시로 들어보겠다.

private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount; // modCount는 자료구조인 ArrayList에게 달려있음.

        // prevent creating a synthetic constructor
        Itr() {}

        public boolean hasNext() {
            return cursor != size;
        }

        @SuppressWarnings("unchecked")
        public E next() {
            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];
        }

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

먼저 주목해야할 3가지 변수가 있는데, 바로 cursor와 lastRet, expectedModCount이다. cursor는 현재 방문한 index이고 lastRet은 이전에 방문한 index이다. expectedModCount는 순회 이전의 modCount값을 저장하여 순회를 하면서 modCount가 실제로 바뀌었는지 체크를 하는 변수이다.

iterator.remove()는 현재 바라보고 있는 인덱스를 삭제한다. 삭제 이후에는 cursor를 다시 lastRet으로 맞춘다. 삭제로 인해 ArrayList 자체 modCount 값이 변경 되었을 것임으로, expectedModCount를 바뀐 값과 동기화 시킨다.

위와 같은 과정으로 동시 수정 오류를 피한다.

다음의 동시 수정 오류가 나는 삭제와 안 나는 삭제에 대한 예시와 함께 Fail-Fast Iterator에 대한 설명을 마치겠다.

ArrayList<Integer> numbers = // ...

Iterator<Integer> iterator = numbers.iterator();
while (iterator.hasNext()) {
    if (iterator.next() == 30) {
        iterator.remove(); // ok!
    }
}

iterator = numbers.iterator();
while (iterator.hasNext()) {
    if (iterator.next() == 40) {
        numbers.remove(2); // exception
    }
}

3. Fail-Safe Iterators

(1) 정의

Fail-Safe Iterators 는 순회 도중에 구조적 변경이 일어나는 동시성 문제가 발생해도 예외를 발생시키지 않는 것을 택한 전략이다. 다만 문제 상황이 커지는 것을 피해서 시스템 전체가 최대한 정상 작동하도록 유도한다.

(2) 구현 전략

Java에서 해당 전략을 구현한 방법에는 두 가지가 있다.

1. 복사해서 사용하기 (Copy-On-Write)
2. 약한 일관성 (Weakly-Consistent)

A. Copy on Write

해당 구현 방법은 Iterator가 복사본에서 순회하도록 만든다. 따라서 본 자료구조에서 변경 사항이 생겨도, 순회 과정 자체는 변경 사항이 반영되지 않기 때문에, 오류 없이 작업을 끝낼 수 있다.

• 장점: 멀티 스레드 환경에서 readOnly 작업을 할 경우 쓰기 적합하다.
• 단점:
  1. 매번 복사하기 때문에 기능 처리에 대한 CPU 비용이 높고, 메모리 사용량이 증가한다.
  2. 위에서 말한대로 순회 도중 생긴 변경 사항은 확인이 불가능하다.

해당 방법을 사용해 구현한 자료구조에는 CopyOnWirteArrayList가 있다.

B. Weakly-Consistent

해당 구현 방법은 구조적 변경이 진행될 때, 변경되는 '부분에만 분할 CAS 세그먼트 락' 을 걸어서 동시성 문제 없이 모든 스레드에서 자료 구조의 내용이 동기화되도록 하는 방법이다.

• 장점: 순회 도중에 생긴 변경 사항은 최대한 반영

a. 지역적 락은 어떻게 동작하나?

예를 들어 ConcurentHashMap의 경우 구조적 변경이 일어나는 버킷에만 Lock을 건다. 따라서 나머지 bucket은 여전히 접근 가능한 상태가 된다.

b. 순회 도중에 생긴 변경 사항은 최대한 반영

iterator가 순회하기 전에 생긴 변경사항은 최대한 반영해서 진행한다.

public static void main(String[] args) throws IOException {  
    ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();  

    map.put("First", 10);  
    map.put("Second", 20);  
    map.put("Third", 30);  
    map.put("Fourth", 40);  

    Iterator<String> iterator = map.keySet().iterator();  
    int i = 1;  
    while (iterator.hasNext()) {  
        map.put("Fifth", 50);  
        String key = iterator.next();  
        System.out.println(i++);  
    }  
}

이건 ConcurrentHashMap이 5번 돈다.

해당 방법으로 구현한 자료구조에는 ConcurrentHashMap, ConcurrentLinkedQueue 가 있다.

4. 핵심 요약

1. fail-fast iterator는 순회 도중 구조적 변경이 일어난 즉시 해당 자료구조의 작동을 멈추는 iterator이다. 데이터의 정합성과 일관성을 중시하는 전략이다.
2. fail-safe iterator는 순회 도중에 구조적 변경이 일어나도 오류를 발생시키지 않고 해당 작업을 진행한다. 변경 사항은 아예 반영되지 않거나 (copy-on-write), 아니면 최대한 반영(weakly-consistence)하는 전략을 택한다.

---

부록

A. 모르는 단어 정리

• play along with ~~
  : (상대방이 원하는 대로) 맞춰 주다. 동조해주다. 협조하다.
  (Fail-fast iterators in Java don't play along when the underlying collection gets modified.)
  (자바의 빠른 실패 이터레이터는 그것이 돌아가고 있는 컬렉션이 수정되었을 때 순순히 협조해주지 않는다.)

• abort
  : 중단하다.
  (Fail-Fast systems abort operation as-fast-as-possible exposing failures immediately and stopping the whole operation.)
  빠른 실패 시스템은 실패에 노출되는 즉시 작동을 중단한다. 그리고 모든 작동을 중단한다.

• basis
  : 기준, 방식, 방법
  (These iterators throw ConcurrentModificationException on a best effort basis.)
  (이터레이터는 최선을 다해 노력해서 동시수정 오류를 일으킨다.)

• favor A over B
  : A를 B보다 선호하다.
  (Faile-Safe Iterator favor lack of failure over the inconvenience of exception handling)
  (실패-안전 이터레이터는 예외 핸들링의 불편보다 실패가 없는 것을 더 선호한다.)

B. 참고 문서

• Fail-Safe Iterator vs Fail-Fast Iterator