Сказ о двух итераторах: стратегии конкурентной модификации в Java

Среди наиболее популярных вопросов на собеседованиях по языку Java есть и такой: В чем различие между fail-fast и fail-safe итераторами? Максимально упрощенный ответ на него: Fail-fast итератор генерирует исключение ConcurrentModificationException, если коллекция меняется во время итерации, а fail-safe нет. Хотя это звучит достаточно осмысленно, остается непонятным, что интервьюер понимает под fail-safe? Спецификации языка Java не определяют этот термин в отношении итераторов. Однако существуют четыре стратегии конкурентной модификации. Если коротко: fail-fast итератор (ArrayList, HashMap) бросает ConcurrentModificationException, как только замечает, что коллекцию изменили в обход итератора, а под «fail-safe» на собеседовании обычно имеют в виду любую из трех остальных стратегий: слабо согласованный итератор (ConcurrentHashMap), снимок состояния (CopyOnWriteArrayList) или неопределенное поведение (Enumeration у Vector и Hashtable).

Кратко

• Конкурентная модификация это любое изменение коллекции во время обхода не через сам итератор; многопоточность для нее не обязательна, достаточно list.remove() внутри цикла.
• Fail-fast (ArrayList, HashMap и почти все коллекции java.util): итератор сравнивает счетчик modCount с сохраненной копией и бросает ConcurrentModificationException, но только «по мере возможности», без гарантии.
• Слабая согласованность (ConcurrentHashMap, большинство очередей java.util.concurrent): исключения нет никогда, каждый элемент, существовавший на момент создания итератора, обходится ровно один раз, а более поздние изменения могут быть видны, а могут и нет.
• Снимок состояния (CopyOnWriteArrayList, CopyOnWriteArraySet): итератор обходит копию массива на момент своего создания, изменений не видит, а remove, set и add через него невозможны; выгодно, когда обходов намного больше, чем изменений.
• Неопределенное поведение: Enumeration у Vector и Hashtable может пропускать или дублировать элементы; в новом коде не используйте.
• Термина «fail-safe» в документации Java нет: на собеседовании под ним обычно имеют в виду любую стратегию, кроме fail-fast, чаще всего снимок состояния.

Конкурентная модификация

Во-первых, давайте определимся, что такое конкурентная (или параллельная) модификация. Допустим у нас есть коллекция и при активном итераторе происходят какие-либо ее изменения, не исходящие от данного итератора. В таком случае у нас получается конкурентная модификация. Приведу простейший пример: допустим, у нас есть несколько нитей. Первая нить выполняет итерации, а вторая вставляет элементы в ту же коллекцию или удаляет их из нее. Однако мы можем получить исключение ConcurrentModificationException и при работе в однопоточной среде:

List<String> cities = new ArrayList<>();
cities.add("Warsaw");
cities.add("Prague");
cities.add("Budapest");

Iterator<String> cityIterator = cities.iterator();
cityIterator.next();
cities.remove(1);
cityIterator.next(); // генерирует ConcurrentModificationException

Fail-fast

Вышеприведенный фрагмент кода это пример fail-fast итератора. Как вы можете видеть, при попытке извлечения второго элемента из итератора было сгенерировано исключение ConcurrentModificationException. Откуда итератор узнает, что коллекция была модифицирована после его создания? Например, в коллекции может быть метка даты/времени, скажем, lastModified. При создании итератора вам стоит скопировать это поле и сохранить его в объекте итератора. Затем, при каждом вызове метода next(), нужно будет просто сравнить значение lastModified из коллекции с копией из итератора. Очень близкий подход используется, например, в реализации класса ArrayList. В нем есть переменная экземпляра modCount (она объявлена в AbstractList, а ArrayList ее наследует), в которой хранится количество структурных модификаций списка:

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

Важно отметить, что fail-fast итераторы работают на основе принципа "по мере возможности", то есть не дается никаких гарантий генерации исключения ConcurrentModificationException в случае конкурентной модификации. Так что полагаться на это не стоит: скорее, их следует использовать для обнаружения ошибок. Большинство неконкурентных коллекций предоставляют fail-fast итераторы.

Слабая согласованность

Большинство конкурентных коллекций из пакета java.util.concurrent (например, ConcurrentHashMap и большинство Queue) предоставляют слабо согласованные итераторы. Смысл этого термина очень хорошо разъясняется в документации:

• Они могут обрабатываться конкурентно с другими операциями
• Они никогда не генерируют исключение ConcurrentModificationException
• Они гарантированно обходят существовавшие на момент создания итератора элементы ровно один раз, и могут (но не обязаны) отражать последующие модификации.

С Java 8 то же самое документация обещает и для Spliterator, а значит, и для стримов по таким коллекциям.

Снимок состояния

При такой стратегии итератор связывается с состоянием коллекции на момент его создания, это и есть снимок состояния (снепшот) коллекции. Любые произведенные над исходной коллекцией изменения приводят к созданию новой версии нижележащей структуры данных. При этом наш снимок состояния остается неизменным, так что он не отражает изменения в коллекции, которые произошли после создания итератора. Это старая добрая методика копирования при записи (copy-on-write, COW). Она полностью решает проблему конкурентных модификаций, поэтому исключение ConcurrentModificationException при таком подходе не генерируется. Кроме того, итераторы не поддерживают операции, которые меняют элементы. Коллекции с копированием при записи обычно требуют слишком больших расходов ресурсов при использовании, но имеет смысл воспользоваться ими, если изменения происходят намного реже, чем обходы итераторов. Примерами могут служить классы CopyOnWriteArrayList и CopyOnWriteArraySet.

Неопределенное поведение

Неопределенное поведение может встретиться вам в устаревших унаследованных типах коллекций, таких как Vector и Hashtable. В обеих есть стандартные fail-fast итераторы, но кроме этого, они позволяют использовать реализации интерфейса Enumeration, а они не знают, как себя вести в случае конкурентной модификации. Вы можете столкнуться с тем, что некоторые элементы повторяются или оказываются пропущенными, а то и вовсе увидите какие-то странные исключения. Лучше с ними не играться!

Четыре стратегии рядом

Сведем описанное в одну таблицу:

Вопросы и ответы

Чем fail-fast итератор отличается от fail-safe?

Fail-fast итератор (ArrayList, HashMap и другие коллекции java.util) бросает ConcurrentModificationException, если коллекцию изменили после его создания не через сам итератор. Термина fail-safe в документации Java нет, так называют итераторы, которые исключение не бросают: слабо согласованные (ConcurrentHashMap видит часть изменений) и снимки состояния (CopyOnWriteArrayList обходит копию и изменений не видит вовсе). Разница в том, что fail-fast защищает от ошибки шумно, а fail-safe тихо, ценой копирования или неполной картины.

Почему ConcurrentModificationException возникает в одном потоке?

Потому что итератор проверяет не потоки, а счетчик изменений. ArrayList увеличивает modCount при каждом add и remove, итератор при создании запоминает его значение, а в каждом next() сравнивает. Классический случай: цикл for-each под капотом использует итератор, и list.remove(x) внутри такого цикла ломает счетчик.

Почему удаление предпоследнего элемента в for-each не бросает исключение?

Из-за проверки hasNext(): у итератора ArrayList она сравнивает позицию с размером списка (cursor != size). После удаления предпоследнего элемента размер уменьшается на единицу и совпадает с позицией, hasNext() возвращает false, и цикл тихо заканчивается, так и не дойдя до последнего элемента. Проверка modCount живет в next(), а до него дело не доходит. Это хуже исключения: ошибка есть, а сигнала о ней нет.

Как безопасно удалить элементы из коллекции во время обхода?

Через сам итератор: iterator.remove() удаляет текущий элемент и синхронизирует счетчик. С Java 8 короче list.removeIf(x -> условие), он делает то же самое внутри. Для Map работает map.entrySet().removeIf(...) или map.values().removeIf(...). Еще два варианта: собрать кандидатов в отдельный список и удалить после цикла, либо идти по индексам с конца.

Гарантирует ли fail-fast итератор исключение при конкурентной модификации?

Нет. Документация Oracle прямо пишет, что fail-fast итераторы бросают ConcurrentModificationException по мере возможности (best-effort), а при несинхронизированном доступе из нескольких потоков жестких гарантий дать невозможно: проверка счетчика сама не атомарна. Поэтому строить на этом исключении логику программы нельзя, оно только для обнаружения ошибок.

Когда брать CopyOnWriteArrayList вместо Collections.synchronizedList?

Когда обходов намного больше, чем изменений: списки слушателей, редко меняющиеся настройки. У synchronizedList итератор все равно fail-fast, и на время обхода документация требует вручную синхронизироваться на списке. CopyOnWriteArrayList при каждом изменении копирует массив, зато обход идет без блокировок и никогда не бросает ConcurrentModificationException. Если запись частая или список большой, копирование съест всю выгоду.