📦 Розділ 4 · Питання #20

Що таке CopyOnWriteArrayList

Головний принцип роботи:

📦 Колекції 📄 Вихідний Markdown

🟢 Junior Level

1. Що таке CopyOnWriteArrayList

CopyOnWriteArrayList — це потокобезпечна реалізація інтерфейсу List, заснована на ідіомі Copy-On-Write (копіювання при записі).

Головний принцип роботи:

  • Будь-яка операція читання (get, indexOf, contains, обхід через ітератор) виконується без блокувань (Lock-Free) з максимальною швидкістю $O(1)$.
  • Будь-яка операція зміни (add, set, remove) створює повну копію внутрішнього масиву, застосовує зміни до цієї копії й атомарно підміняє посилання на масив.
List<String> list = new CopyOnWriteArrayList<>();

// Потокобезпечний запис:
list.add("Java");
list.add("Kotlin");

// Потокобезпечне читання без жодних блокувань:
String lang = list.get(0); // "Java"

2. Порівняння з Collections.synchronizedList

Критерій Collections.synchronizedList CopyOnWriteArrayList
Операція читання (get) Блокує весь список (synchronized) Lock-Free (без блокувань)
Операція запису (add) Блокує весь список ($O(1)$ амортизовано) Створює повну копію масиву ($O(N)$)
Ітерація Вимагає зовнішньої ручної синхронізації Безпечна без блокувань (Snapshot)
Поведінка ітератора Fail-Fast (ConcurrentModificationException) Fail-Safe (ніколи не викидає CME)
Найкращий сценарій Баланс читань і частих записів Read-Heavy (читань у сотні/тисячі разів більше за записи)

🟡 Middle Level

1. Як влаштований механізм під капотом

Усередині класу CopyOnWriteArrayList дані зберігаються в єдиному масиві з модифікатором volatile:

public class CopyOnWriteArrayList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    final transient Object lock = new Object();
    private transient volatile Object[] array;

    final Object[] getArray() {
        return array;
    }

    final void setArray(Object[] a) {
        array = a;
    }
}

Механіка додавання елемента (add):

public boolean add(E e) {
    synchronized (lock) { // Захист від паралельних потоків запису
        Object[] es = getArray();
        int len = es.length;
        // 1. Створюємо новий масив на 1 елемент більший і копіюємо дані:
        Object[] newElements = Arrays.copyOf(es, len + 1);
        // 2. Додаємо новий елемент у кінець:
        newElements[len] = e;
        // 3. Атомарно підміняємо volatile-посилання:
        setArray(newElements);
        return true;
    }
}

Оскільки посилання array оголошене як volatile, у момент виклику setArray(newElements) спрацьовує правило Happens-Before: усі наступні операції читання гарантовано побачать посилання на новий масив з усіма внесеними змінами.

2. Ітератор як незмінний знімок (Snapshot Iterator)

При виклику list.iterator() повертається легкозважений ітератор COWIterator, який зберігає посилання на масив, актуальний рівно на момент створення ітератора:

List<String> list = new CopyOnWriteArrayList<>(List.of("A", "B", "C"));

Iterator<String> it = list.iterator(); // Зафіксовано знімок: ["A", "B", "C"]

list.add("D");    // Модифікація списку: створено НОВИЙ масив ["A", "B", "C", "D"]
list.remove("A"); // Ще одна модифікація: створено масив ["B", "C", "D"]

// Ітератор спокійно продовжує обхід старого знімка:
while (it.hasNext()) {
    System.out.print(it.next() + " "); // Виведе: A B C
}

Критичні властивості знімка:

  1. Ітератор ніколи не викидає ConcurrentModificationException.
  2. Ітератор не бачить змін, які сталися в списку після моменту його створення.
  3. Усі методи мутації через ітератор заборонені: 
    it.remove(); // Завжди викидає UnsupportedOperationException!

🔴 Senior Level

1. Архітектурна ніша: списки слухачів подій (Event Listeners)

Ідеальний патерн застосування CopyOnWriteArrayList — реєстрація підписників у шинах подій (Observer / Event Bus):

public class EventBus {
    // Підписники реєструються рідко (під час старту модулів/сервісів),
    // але події публікуються тисячі або мільйони разів на секунду:
    private final List<EventListener> listeners = new CopyOnWriteArrayList<>();

    public void register(EventListener listener) {
        listeners.add(listener); // Рідкісний запис O(N)
    }

    public void publishEvent(Event event) {
        // Читання O(1) без блокувань і без ризику ConcurrentModificationException,
        // навіть якщо один із підписників під час обробки викличе listeners.remove(this)!
        for (EventListener listener : listeners) {
            listener.onEvent(event);
        }
    }
}

Якби тут використовувався ArrayList із блокуванням synchronized, публікація кожної події блокувала б усі потоки на час виконання onEvent(). Якби використовувався звичайний ArrayList, відписка слухача всередині onEvent() миттєво зламала б обхід винятком ConcurrentModificationException.

2. Проблеми продуктивності: GC Churn та сплески пам’яті (Memory Spikes)

Використання CopyOnWriteArrayList у сценаріях із частим записом (Write-Heavy) є грубою архітектурною помилкою:

  1. Тимчасовий сплеск споживання пам’яті (Memory Spike): При додаванні елемента до списку з $10\,000\,000$ посилань ($\approx 40$ МБ на 64-бітній JVM) під час роботи Arrays.copyOf() у купі (Heap) одночасно співіснують старий масив (40 МБ) і новий масив (40 МБ). Під час пікових навантажень це може спровокувати OutOfMemoryError.
  2. Тиск на збирач сміття (GC Pressure / Allocation Churn): Кожна операція запису відправляє старий масив у сміття. При 10 000 записів на секунду виділяються й викидаються гігабайти пам’яті, що викликає часті паузи збирача сміття (Stop-the-World Minor GC).
  3. Алгоритмічна деградація: Додавання $N$ елементів по одному в циклі виконується за $O(N^2)$, тоді як у звичайному ArrayList це займає амортизований час $O(N)$.

[!TIP] Якщо необхідно додати одразу кілька елементів, обов’язково використовуйте list.addAll(collection): цей метод виконає рівно одне копіювання масиву для всієї пачки елементів, скорочуючи витрати з $O(M \cdot N)$ до $O(M + N)$.

3. Еволюція в JDK: чому в Java 11 перейшли з ReentrantLock на synchronized (lock)?

В ранніх версіях Java (до Java 10) CopyOnWriteArrayList використовував final transient ReentrantLock lock = new ReentrantLock(). Починаючи з Java 11, його було замінено на звичайний монітор: final transient Object lock = new Object() і блоки synchronized (lock).

Причини зміни:

  1. Зменшення споживання пам’яті (Footprint): екземпляр Object займає лише 16 байтів (із Compressed OOPs), тоді як ReentrantLock є складним складеним об’єктом, що містить стан синхронізатора AQS (AbstractQueuedSynchronizer) і чергу очікування.
  2. Оптимізації JVM: сучасні JIT-компілятори JVM надзвичайно ефективно інлайнять та оптимізують монітори synchronized за низької конкуренції (Lightweight Locking, Biased Locking в старих JDK). Оскільки CopyOnWriteArrayList призначений для рідкісних записів, накладні витрати на монітор практично нульові.

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

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

«CopyOnWriteArrayList — це потокобезпечний список, оптимізований для переважання операцій читання (Read-Heavy). Операції читання виконуються без блокувань (Lock-Free) з volatile-масиву. За будь-якої модифікації (add, set, remove) під ексклюзивним замком створюється повна копія внутрішнього масиву, модифікується й атомарно підміняється. Ітератор списку працює по незмінному знімку (Snapshot) масиву на момент створення, ніколи не викидає ConcurrentModificationException, але й не підтримує метод remove(). Основна сфера застосування — списки підписників та слухачів подій (Listeners / Observers)».

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

1. Чому метод iterator().remove() у CopyOnWriteArrayList викидає UnsupportedOperationException?

Відповідь: Ітератор тримає пряме посилання на зафіксований масив-знімок (snapshot), який існував у мить створення ітератора. Цей масив є незмінним. Якби метод remove() дозволили, виникла б дилема: мутувати оригінальний список під час ітерації (що суперечить семантиці знімка та потребувало б дорогої синхронізації з актуальною версією) чи видаляти елемент лише з локального масиву знімка (що не вплинуло б на базову колекцію і ввело б в оману). Тому розробники JDK заблокували всі операції модифікації через ітератор.

2. Чи гарантує CopyOnWriteArrayList сувору узгодженість (Strong Consistency) при читанні?

Відповідь: Ні, він гарантує слабку або кінцеву узгодженість (Eventual Consistency). Якщо потік $A$ створив ітератор і обходить список, а потік $B$ у цей самий час додав або видалив елементи, потік $A$ не побачить цих змін і працюватиме із застарілими даними (Stale Data). Водночас завдяки volatile-семантиці масиву будь-який прямий виклик list.get(i), виконаний після завершення запису потоком $B$, гарантовано поверне актуальні дані.

3. Чому в Java 11 розробники OpenJDK замінили ReentrantLock на synchronized (lock)?

Відповідь: Задля економії пам’яті та підвищення продуктивності. Поле final Object lock = new Object() важить значно менше за важкий об’єкт ReentrantLock з чергою AQS. Крім того, JVM чудово оптимізує монітори synchronized в умовах слабкої конкуренції (Lightweight Locking), що ідеально відповідає профілю CopyOnWriteArrayList, де записи відбуваються рідко.

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

  • ❌ Використання CopyOnWriteArrayList у системах із частим записом (Write-Heavy): Призводить до колосальної деградації швидкодії через копіювання $O(N)$ під час кожної вставки та перевантаження Garbage Collector.
  • ❌ Спроба модифікувати колекцію через ітератор (it.remove()): Викидає UnsupportedOperationException прямо в продакшені.
  • ❌ Поштучне додавання елементів у циклі for: Додавання 1 000 елементів по одному створить 1 000 повних копій масиву ($O(N^2)$). Необхідно використовувати пакетний метод addAll().
  • ❌ Очікування, що ітератор відобразить паралельні зміни: Ітератор читає ізольований знімок на момент свого створення і не реагує на подальші модифікації списку.

Пов’язані теми