Що таке fail-fast та fail-safe ітератори

Під час обходу колекцій у Java поведінка ітератора в разі паралельної або некоректної модифікації колекції поділяється на дві ключові стратегії:

🟢 Junior Level

1. Просте визначення концепцій

Fail-Fast («Швидкий збій»): ітератор негайно викидає виняток ConcurrentModificationException, якщо виявляє, що колекція була змінена (додано, видалено або замінено елемент) в обхід методів самого ітератора.
Fail-Safe («Безпечний збій»): ітератор не падає з винятком при модифікації колекції, спокійно продовжуючи обхід елементів.

// 1. Fail-Fast (ArrayList, HashMap, HashSet)
List<String> fastList = new ArrayList<>(List.of("A", "B"));
for (String s : fastList) {
    fastList.add("C"); // КАТАСТРОФА: викине ConcurrentModificationException!
}

// 2. Fail-Safe (CopyOnWriteArrayList, ConcurrentHashMap)
List<String> safeList = new CopyOnWriteArrayList<>(List.of("A", "B"));
for (String s : safeList) {
    safeList.add("C"); // БЕЗПЕЧНО: ітератор завершить цикл (обійде "A", "B")
}

2. Порівняльна таблиця

Критерій	`Fail-Fast`	`Fail-Safe` (Snapshot)	`Weakly Consistent`
Викидання `CME`	✅ Так (при будь-якій сторонній зміні)	❌ Ніколи	❌ Ніколи
Приклади колекцій	`ArrayList`, `HashSet`, `HashMap`	`CopyOnWriteArrayList`, `CopyOnWriteArraySet`	`ConcurrentHashMap`, `ConcurrentLinkedQueue`
Робота з копією	Ні (прямий доступ до даних)	Так (незмінний знімок масиву)	Ні (живі дані через `volatile`)
Чи бачить нові дані	Викидає помилку до того, як зможе побачити	❌ Ні (ізольований у знімку)	⚠️ Може побачити, але не гарантує
Накладні витрати	Мінімальні ($O(1)$)	Високі при записі ($O(N)$ копіювання)	Мінімальні (Lock-Free)

🟡 Middle Level

1. Механізм роботи Fail-Fast: змінні `modCount` та `expectedModCount`

Усередині колекцій із fail-fast поведінкою реалізовано лічильник структурних змін:

protected transient int modCount = 0;

Будь-яка дія, що змінює розмір або топологію структури даних (add, remove, clear, resize), викликає інкремент modCount++.

Коли створюється екземпляр ітератора, він фіксує поточне значення лічильника:

int expectedModCount = modCount;

Під час кожного кроку обходу в методах next() та remove() перевіряється інваріант:

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

Якщо колекція була модифікована безпосередньо (наприклад, list.add("X")), значення modCount збільшилося, а локальне expectedModCount ітератора залишилося старим. Під час наступного ж виклику it.next() генерується аварійне виключення.

[!NOTE] Якщо елемент видаляється через метод самого ітератора (it.remove()), ітератор власноруч вирівнює лічильники: expectedModCount = modCount, тому виняток не викидається.

2. Термінологічний нюанс: офіційна позиція специфікації JDK

[!IMPORTANT] Термін «Fail-Safe» не є офіційним терміном специфікації Java (JLS / Javadoc)! Це усталений розмовний сленг інженерів.

Офіційна документація JDK класифікує стійкі до модифікацій ітератори на дві суворі категорії:

Snapshot-style Iterators (Знімкові): працюють по фіксованій незмінній копії даних (CopyOnWriteArrayList).

Weakly Consistent Iterators (Слабкоузгоджені): працюють із живою структурою даних, гарантуючи відсутність CME, проходження всіх елементів на момент створення та відсутність дублювання (ConcurrentHashMap).

🔴 Senior Level

1. Чому Fail-Fast — це «Best-Effort», а не гарантія багатопоточності?

Javadoc класу ArrayList містить фундаментальне застереження:

«Зверніть увагу, що поведінка fail-fast не може бути гарантованою, оскільки неможливо надати жорсткі гарантії за наявності несинхронізованих паралельних модифікацій… Fail-fast ітератори повинні використовуватися виключно для виявлення помилок проєктування програми».

Апаратна причина: Змінна modCount оголошена як звичайний примітив int, вона НЕ є volatile:

protected transient int modCount = 0; // Ключове слово volatile відсутнє!

Якщо Потік 1 змінює список на ядрі CPU 1, оновлений modCount++ осідає в локальному кеші L1/L2 процесора і не скидається в спільну оперативну пам’ять негайно. Потік 2, що обходить список на ядрі CPU 2, може прочитати застаріле значення modCount зі свого кешу, пройти перевірку modCount != expectedModCount і продовжити ітерацію по пошкодженому масиву, викликаючи спотворення даних або раптовий ArrayIndexOutOfBoundsException.

Висновок: Fail-fast — це детектор логічних багів в однопотоковому коді, а не засіб синхронізації в конкурентному середовищі.

2. Порівняння продуктивності: `iterator.remove()` проти `removeIf()`

Під час видалення елементів із ArrayList в циклі традиційно використовують iterator.remove(). Проте для списків на основі динамічного масиву це породжує серйозну проблему продуктивності:

// ❌ СКЛАДНІСТЬ O(N^2):
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (it.next().startsWith("bad_")) {
        it.remove(); // Кожен виклик виконує System.arraycopy для зсуву хвоста масиву!
    }
}

// ✅ СКЛАДНІСТЬ O(N) у Java 8+:
list.removeIf(s -> s.startsWith("bad_"));

Метод removeIf в ArrayList спочатку сканує масив за допомогою бітової маски BitSet, фіксуючи індекси всіх елементів для видалення за один лінійний прохід, а потім здійснює рівно одне компактувальне переміщення даних.

🎯 Шпаргалка для інтерв’ю

30-секундна відповідь (Elevator Pitch)

«Fail-Fast ітератори (в ArrayList, HashMap) фіксують структурні зміни колекції, здійснені в обхід методів самого ітератора, і негайно викидають ConcurrentModificationException. Це реалізовано порівнянням лічильника модифікацій modCount зі значенням expectedModCount ітератора. Термін Fail-Safe неофіційний: під ним розуміють або знімкові ітератори (CopyOnWriteArrayList), що обходять ізольовану копію масиву, або слабкоузгоджені ітератори (ConcurrentHashMap), що обходять живі volatile-вузли без ризику CME. Механізм fail-fast не гарантує захисту в багатопотоковості (має статус Best-Effort), оскільки змінна modCount не є volatile».

3 каверзних запитання з інтерв’ю та відповіді

1. Чи може однопотокова програма без паралельних потоків викинути `ConcurrentModificationException`?

Відповідь: Так, і це найпоширеніша причина виникнення цього винятку на практиці. Якщо всередині звичайного циклу for-each викликати прямий метод модифікації колекції (наприклад, list.remove(item) або list.add(item)), колекція інкрементує modCount. На наступному кроці циклу метод next() ітератора виявить розбіжність між modCount та expectedModCount і викине ConcurrentModificationException.

2. Чому розробники JDK не зробили поле `modCount` змінною `volatile`?

Відповідь: Модифікатор volatile накладає відчутний апаратний оверхед, вимагаючи скидання кешів і генерації апаратних бар’єрів пам’яті (Memory Barriers) на кожну операцію додавання або видалення елемента. Колекції пакета java.util (як-от ArrayList) проєктувалися як максимально швидкі однопотокові структури. Уповільнювати базові операції заради негарантованої діагностики в завідомо некоректному багатопотоковому коді було визнано невиправданим компромісом.

3. Що станеться, якщо під час ітерації по `ConcurrentHashMap` інший потік видалить поточний елемент?

Відповідь: Жодного винятку викинуто не буде. Ітератор ConcurrentHashMap є слабкоузгодженим (Weakly Consistent). Він утримує посилання на поточний вузол Node, поля якого є volatile. Якщо елемент видаляється з мапи, внутрішні зв’язки в бакеті перебудовуються, але сам вузол продовжує коректно посилатися на наступний елемент ланцюжка через node.next, тому ітератор успішно продовжить обхід решти колекції.

Типові помилки та Red Flags

❌ Стверджувати, що ConcurrentModificationException виникає лише в багатопотокових програмах: Найчастіше воно виникає в одному потоці при виклику list.remove() всередині for-each.
❌ Впевненість, що fail-fast надійно захищає від гонитви даних: Поле modCount не є volatile, діагностика має статус Best-Effort.
❌ Спроба використати iterator.remove() в CopyOnWriteArrayList: Викине UnsupportedOperationException, оскільки знімок є незмінним.
❌ Очікування, що знімковий ітератор побачить елементи, додані під час його роботи: Знімок повністю ізольований від подальших мутацій.