3 Weeks - [ConcurrentModification 동작 원리]

[devjy39]

문제

• Collection이나 Map의 경우 foreach로 순회하면서 수정하면 ConcurrentModificationException이 발생합니다.
• 내부적으로 어떤 원리로 발생하는 건가요?
• 어떤 것들을 사용할 때, 그리고 어떤 상황들에서 발생하는건가요?

contents - 세부 내용

• foreach를 사용하면서 종종 겪는 exception이었는데 내부적으로 어떤 원리로 동시 수정을 감지하고 예외를 발생시키는건지,
  어떤 상황들에서 발생하는 건지 정확히 알지 못했는데 이번 기회에 확실히 알고 넘어가면 좋을 것 같습니다!

참고

[dpwns523]

• ConcurrentModificationException이란?

17 java docs에 명확히 정리하고 있어서 전체 내용을 가져왔습니다

This exception may be thrown by methods that have detected concurrent modification of an object when such modification is not permissible.

객체의 동시 수정이 허용되지 않을 때, 해당 객체의 수정이 감지된 메서드에 의해 발생된다.

For example, it is not generally permissible for one thread to modify a Collection while another thread is iterating over it.
In general, the results of the iteration are undefined under these circumstances.
Some Iterator implementations (including those of all the general purpose collection implementations provided by the JRE) may choose to throw this exception if this behavior is detected.
Iterators that do this are known as fail-fast iterators, as they fail quickly and cleanly, rather that risking arbitrary, non-deterministic behavior at an undetermined time in the future.

예로, 한 스레드가 Collection을 수정하고 다른 스레드가 동시에 iterate하려고 할 때 이는 일반적으로 허용되지 않는다.
Iterator 구현체(JRE에서 제공하는 일반적인 컬렉션 구현체 포함)는 이러한 동작을 감지하면 이 예외를 던질 수 있으며 이를 fail-fast Iterator라고 부르며
미래의 불분명한 시간에 임의의 비결정적 동작을 위험하게 가져오지 않고 빠르게 실패시킴

-> 자바에서 제공되는 컬렉션 라이브러리는 Thread-Safe하지 못합니다. 멀티 스레드 환경은 곧 공유 자원에 접근할 수 있다는 것을 의미하는데
이러한 환경에서 컬렉션이라는 공유 자원에 대한 수정이 일어나게되면 동기화를 지원하지 않기 때문에 이를 감지하고 에러를 던져 이를 방지하는 예외처리라고 볼 수 있습니다
이를 fast-fail이라고 표현하고 있네요
쉽게 표현하면 이것저것 따지지 않고 나한테 반영되지 않는 변경이 감지되면 종료시킨다는 의미로 이해할 수 있습니다

예외를 던지는 목적을 이해했으니 for-each 구현체와 Iterator 구현체를 보면서 어떤 상황에 예외를 던지는 지 확인해보았습니다 (List 인터페이스 기준으로 알아보았습니다)
책에서 제공해 주듯 for-each 루프는 Iterator 객체를 사용해 객체를 탐색합니다
for-each 코드

        for (Transaction transaction : transactions) {
            if(Character.isDigit(transaction.getReferenceCode().charAt(0))) {
                transactions.remove(transaction);	// ConcurrentModificationException!
            }
        }

내부 동작 코드

        for (Iterator<Transaction> iterator = transactions.iterator();
             iterator.hasNext(); ) {
            Transaction transaction = iterator.next();
            if(Character.isDigit(transaction.getReferenceCode().charAt(0))) {
                transactions.remove(transaction);	// 반복하면서 별도의 두 객체를 통해 컬렉션을 바꾸고 있는 문제
            }
        }

그렇다면 Iterator의 메서드는 어떻게 동작하기에 조회하는 컬렉션의 remove 상태를 파악할 수 있을까?

ArrayList 구현체의 Iterator를 살펴보았습니다

public Iterator<E> iterator() {
        return new Itr();
    }

    /**
     * An optimized version of AbstractList.Itr
     */
    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;	// The modCount value that the iterator believes that the backing List should have.

        // 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();
            }
        }

AbstractList의 내부 변수로 컬렉션의 수정 횟수를 추적하는 modCount 멤버 변수를 가지고 Iter를 생성한 시점의 modCount를 가지고 추적을 하는
멤버변수를 가지고있습니다. Iterator와 Collection의 상태가 일치하는지 확인하는데 사용되는 변수로 Iterator를 통한 삭제를 해야
ConcurrentModificationException을 방지할 수 있는데 이는 Sync를 맞추기 위한 로직으로 이해됩니다

내부로직을 통해 Iterator로 삭제하면 ConcurrentModificationException을 피할 수 있다고 정리하고 넘어갈 수 있는데 이 짧은 remove메서드에는 좀 더 의미가 담겨져있는 것 같습니다

ConcurrentModificationException의 본질적인 의미는 Thread-Safe하지 않은 컬렉션에 대한 무결성 보장입니다
따라서 멀티 스레드 환경에서 Iterator로 동시에 삭제하는 상황도 생각해봐야 합니다
어떻게 어떤 순서로 삭제하느냐에 따라 원하는 요소를 삭제하는게 바뀔 수 있습니다 - 동시성 이슈
이를 방지하기 위해 checkForComodification를 통해 삭제하는 순간에도 Sync가 맞는지 체크를 하고 작업을 진행합니다

싱글 스레드에서 ConcurrentModificationException이 발생하는 것은 우리가 컬렉션의 내부구조를 모르고 하나의 객체를 조작하는데 이를 두 객체로 접근하여 동시성 이슈를 발생시키는,. 즉 잘못된 사용예시가 됩니다

그렇다면 결국 상태를 변경하는 상황에서 멀티 스레드 환경에 컬렉션을 사용하면 일관성이 깨질 수 있다는 건데
이런 작업이 존재한다면 동시성을 보장해주는 ConcurrentHashMap을 사용하면 됩니다!
ConcurrentHashMap은 Thread safe 해시 맵 구현체로, 여러 스레드가 동시에 데이터에 접근하더라도 안전하게 작동합니다

정리하면

• 컬렉션에 대해 삭제 작업이 필요하다 -> Iterator를 통해 삭제하라
• 멀티 스레드 환경에서 컬렉션에 대해 삭제 작업이 필요하다 -> concurrent를 보장해주는 컬렉션을 사용하라

추가로 한 가지 더 고려사항이 있습니다
컬렉션을 순회하면서 순회하는 대상 컬렉션에 삭제가 아닌 수정을 가하는 경우에 대한 일관성은 어떻게 방지해주나요?

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

-> fail-fast 동작은 동기화되지 않은 동시 수정의 존재에서 어떠한 보장도 제공할 수없으며 fail-fast 연산은 최선의 노력으로 ConcurrentModificationException 던진다
이 예외에 의존하여 프로그램을 작성하는 것은 올바르지 않습니다. ConcurrentModificationException은 버그를 감지하기 위해 사용되어야 한다

따라서 수정에 대해서는 modCount를 세지 않고 이에 대한 추적, 예외처리는 불가능합니다 -> 멀티 스레드 환경에서 Thread safe 하지 못한 컬렉션인 이유가 될 것 같습니다

//ArrayList 메서드
        public E remove(int index) {
            Objects.checkIndex(index, size);
            checkForComodification();
            E result = root.remove(offset + index);
            updateSizeAndModCount(-1);
            return result;
        }
        private void updateSizeAndModCount(int sizeChange) {
            SubList<E> slist = this;
            do {
                slist.size += sizeChange;
                slist.modCount = root.modCount;
                slist = slist.parent;
            } while (slist != null);
        }
                public void set(E e) {
                    if (lastRet < 0)
                        throw new IllegalStateException();
                    checkForComodification();

                    try {
                        root.set(offset + lastRet, e);
                    } catch (IndexOutOfBoundsException ex) {
                        throw new ConcurrentModificationException();
                    }
                }

public class Test {
    static class TestThread implements Runnable {
        List<String> list;
        String name;

        public TestThread(List<String> list, String name) {
            this.list = list;
            this.name = name;
        }

        @Override
        public void run() {
            int idx = 0;
            for (String str : list) {
                System.out.println("before in " + name +": " + str);
                list.set(idx, "change by " + name);
                System.out.println("after in " + name +": " + list.get(idx) + " idx: "+(idx++ + 1));
            }
        }
    }

    public static void main(String[] args) {
        List<String> list = new ArrayList<>();

        list.add("str1");
        list.add("str2");
        list.add("str3");
        
        Thread t1 = new Thread(new TestThread(list, "thread1"));
        Thread t2 = new Thread(new TestThread(list, "thread2"));
        t1.start();
        t2.start();

    }
}
/* sout
before in thread1: str1
before in thread2: str1
after in thread2: change by thread1 idx: 1    --- 
before in thread2: str2
after in thread2: change by thread2 idx: 2    
after in thread1: change by thread1 idx: 1
before in thread2: str3
before in thread1: change by thread2   --- 
after in thread2: change by thread2 idx: 3
after in thread1: change by thread1 idx: 2
before in thread1: change by thread2   --- 
after in thread1: change by thread1 idx: 3
*/

공유 자원 수정 시 이에 대한 일관성을 보장하지 못합니다

정리

• ConcurrentModificationException은 Thread safe하지 않은 컬렉션에 대해 동시성에 의한 무결성을 보장하기 위한 방지용에러
• 수정(Update)에 대해서는 예외를 던지지 않으므로 ConcurrentModificationException에 의존하면 안된다
  • 수정에 대해선 자원 공유시 추적할 수 없음
• 동시성이 걱정된다면 java.util.concurrent에서 제공하는 클래스를 활용하자

Reference

java docs