Как работает CopyOnWriteArrayList?

Как работает CopyOnWriteArrayList

CopyOnWriteArrayList - это потокобезопасная реализация List, которая оптимизирована для сценариев с частым чтением и редким изменением данных. Это важно знать для собеседований и практики.

Базовое описание

Это коллекция, которая при каждой операции записи создаёт копию внутреннего массива. Звучит неэффективно, но для read-heavy операций это очень быстро.

public class CopyOnWriteArrayList<E> extends Object 
    implements List<E>, RandomAccess, Cloneable, Serializable {
    
    private transient volatile Object[] array;
    // Весь список хранится в одном массиве
}

Как это работает

Чтение (Read)

Чтение максимально быстро - просто берём элемент из массива:

public E get(int index) {
    return (E) array[index];  // Просто доступ, без синхронизации!
}

public Iterator<E> iterator() {
    return new COWIterator(array.clone(), 0);
    // Iterator работает со снимком массива на момент создания
}

Это O(1) без какой-либо синхронизации - супер быстро!

Запись (Write)

Запись создаёт копию:

public boolean add(E e) {
    synchronized(lock) {  // Синхронизируем
        Object[] elements = array;
        int len = elements.length;
        
        // Создаём новый массив большего размера
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        
        // Заменяем ссылку
        array = newElements;
        return true;
    }
}

Это O(n) - медленнее, потому что копируем весь массив.

Remove

Так же копируем:

public E remove(int index) {
    synchronized(lock) {
        Object[] elements = array;
        E oldValue = (E) elements[index];
        int newlen = elements.length - 1;
        
        // Копируем все элементы кроме удаляемого
        Object[] newElements = new Object[newlen];
        System.arraycopy(elements, 0, newElements, 0, index);
        System.arraycopy(elements, index + 1, newElements, index, 
                        newlen - index);
        
        array = newElements;
        return oldValue;
    }
}

Пример работы

Исходный список:
array = ["A", "B", "C"]

Вызов list.add("D"):
1. Захватываем lock
2. Создаём newArray размером 4: [null, null, null, null]
3. Копируем: ["A", "B", "C", null]
4. Добавляем: ["A", "B", "C", "D"]
5. array = newArray (атомарно заменяем ссылку)
6. Отпускаем lock

Это всё время читающие потоки видят старый массив ["A", "B", "C"]

Преимущества

1. Читающие потоки не блокируют друг друга

// Без блокировок при чтении
for (String s : list) {
    System.out.println(s);  // Может выполняться параллельно с записью
}

2. Iterator безопасен

CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
list.add("A");
list.add("B");

Iterator<String> it = list.iterator();  // Снимок на момент создания

list.add("C");  // Список изменился
list.add("D");  // Но iterator не будет выбрасывать ConcurrentModificationException

while (it.hasNext()) {
    System.out.println(it.next());  // Выведет: A, B (не видит C и D)
}

3. Отсутствие deadlock'ов

Потому что читаем без синхронизации, нет риска deadlock'ов.

Недостатки

1. Дорогие операции записи

CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();

long start = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
    list.add("item" + i);  // Каждый add копирует весь массив!
}
long end = System.currentTimeMillis();

// На list из 100000 элементов это будет ОЧЕНЬ медленно
// Последний add копирует 99999 элементов!

2. Высокое потребление памяти

Копии массивов занимают память:

5 потоков делают reads
1 поток делает writes

Если каждый write создаёт полную копию массива - много копий
в памяти одновременно

3. Старые iterators видят старые данные

Это может быть как плюс, так и минус:

list.add(1);
list.add(2);
Iterator<Integer> it = list.iterator();

list.add(3);  // Список изменился

while (it.hasNext()) {
    System.out.println(it.next());  // Выведет только 1, 2
}

Это может быть неожиданно!

Когда использовать CopyOnWriteArrayList

✓ Хорошо для:

// 1. Event listener'ы (много читаем, редко добавляем/удаляем)
List<EventListener> listeners = new CopyOnWriteArrayList<>();

for (EventListener listener : listeners) {
    listener.onEvent(event);  // Частое чтение
}

listeners.add(newListener);  // Редкая запись

// 2. Кеши с редким обновлением
CopyOnWriteArrayList<CachedValue> cache = new CopyOnWriteArrayList<>();

// 3. Конфигурации приложения
CopyOnWriteArrayList<String> allowedHosts = new CopyOnWriteArrayList<>();

✗ Плохо для:

// 1. Частые модификации
for (int i = 0; i < 1000000; i++) {
    list.add(i);  // Очень медленно!
}

// 2. Большие списки с редкими чтениями
CopyOnWriteArrayList<Item> items = new CopyOnWriteArrayList<>();
// Если mostly writes - используй Collections.synchronizedList

// 3. Когда нужна строгая непротиворечивость
// Если нужны актуальные данные во всех iterators

Альтернативы

Collections.synchronizedList

List<String> list = Collections.synchronizedList(new ArrayList<>());
// Синхронизирует все операции
// Но итератор требует явной синхронизации:

synchronized(list) {
    for (String s : list) {
        System.out.println(s);
    }
}

ConcurrentHashMap (если нужен Map)

Map<String, String> map = new ConcurrentHashMap<>();
// Более эффективно для частых reads и writes
// Использует bucket-level locking (segment-based)

Внутренние детали реализации

private final transient Object lock = new Object();
private transient volatile Object[] array;

// Все writes синхронизируются здесь
private static final Object[] EMPTY_ELEMENTDATA = new Object[0];

// Snapshot reads
public Object[] toArray() {
    return array.clone();  // Копия для безопасности
}

Практический пример

public class EventBus {
    private final CopyOnWriteArrayList<EventListener> listeners = 
        new CopyOnWriteArrayList<>();
    
    // Часто вызывается
    public void publish(Event event) {
        for (EventListener listener : listeners) {
            listener.onEvent(event);  // No synchronization needed
        }
    }
    
    // Редко вызывается
    public void subscribe(EventListener listener) {
        listeners.add(listener);  // Creates a copy internally
    }
    
    public void unsubscribe(EventListener listener) {
        listeners.remove(listener);  // Creates a copy internally
    }
}

Производительность

Operация          | ArrayList | synchronizedList | CopyOnWriteArrayList
------------------+-----------+------------------+--------------------
get(int)          | O(1)      | O(1)             | O(1) - САМЫЙ БЫСТРО
add(E)            | O(1) amort| O(1) amort       | O(n) - МЕДЛЕННЫЙ
remove(Object)    | O(n)      | O(n)             | O(n) - ЕЩЁ МЕДЛЕННЕЕ
iterator()        | O(1)      | O(1)*             | O(1) - БЕЗОПАСНЫЙ
Concurrency       | нет       | есть             | отличное

Итог

CopyOnWriteArrayList оптимален для read-heavy сценариев, где вы часто читаете и редко изменяете список. Каждая операция записи создаёт копию всего массива, что дорого, но зато чтения работают параллельно без синхронизации. Это разумный trade-off для event listener'ов, кешей и конфигураций.