Оповідь про двох ітераторів: стратегії конкурентної модифікації в Java

Автор нотатки — Гжегож Мірек — розробник програмного забезпечення із Кракова (Польща). Він зайнявся розробкою на Java близько 6 років тому, ще в університеті, і з цього часу невпинно шліфує свою майстерність у цій сфері. Його особливо цікавить питання продуктивності JVM та оптимізації, про що він, в основному, і пише у своєму блозі . Серед найбільш популярних питань на співбесідах з мови Java є й такий: У чому різниця між fail-fast та fail-safe ітераторами? Максимально спрощена відповідь: Fail-fast ітератор генерує виняток ConcurrentModificationException, якщо колекція змінюється під час ітерації, а fail-safe – ні. Хоча це звучить досить свідомо, залишається незрозумілим, що інтерв'юер розуміє під fail-safe? Специфікації мови Java не визначають цей термін щодо ітераторів. Проте є чотири стратегії конкурентної модифікації.

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

По-перше, давайте визначимося, що таке конкурентна (або паралельна) модифікація. Припустимо, у нас є колекція і при активному ітераторі відбуваються будь-які її зміни, що не виходять від даного ітератора. У такому разі ми отримуємо конкурентну модифікацію. Наведу найпростіший приклад: припустимо, ми маємо кілька ниток. Перша нитка виконує ітерації, а друга вставляє елементи у колекцію чи видаляє їх із неї. Однак ми можемо отримати виняток 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 , в якій зберігається кількість модифікацій списку:

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

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

Слабка узгодженість

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

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

Знімок стану

За такої стратегії ітератор пов'язується із станом колекції на момент його створення – це і є знімок стану (снепшот) колекції. Будь-які зроблені над вихідною колекцією зміни призводять до створення нової версії структури даних, що нижче лежить. При цьому наш знімок стану залишається незмінним, тому він не відображає зміни в колекції, які відбулися після створення ітератора. Це стара добра методика копіювання при записі (copy-on-write, COW) . Вона повністю вирішує проблему конкурентних модифікацій, тому виняток ConcurrentModificationExceptionза такого підходу не генерується. З іншого боку, ітератори не підтримують операції, які змінюють елементи. Колекції з копіюванням при записі зазвичай вимагають надто великих витрат ресурсів при використанні, але є сенс скористатися ними, якщо зміни відбуваються набагато рідше, ніж обходи ітераторів. Прикладами можуть бути класи CopyOnWriteArrayList і CopyOnWriteArraySet .

Невизначена поведінка

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