CopyOnWriteArrayList / CopyOnWriteArraySet 写时复制源码

概述

CopyOnWriteArrayList 是 JUC 中"读无锁、写复制"的并发容器：每次修改（add/remove/set）都复制一份全新数组再整体发布，读操作永远在不可变快照上进行，因此读不需要任何同步。CopyOnWriteArraySet 则是基于它的去重视图。

代价是写操作 O(n) 全量拷贝——只适合读多写少的场景。本文基于 OpenJDK 21 源码拆解其存储、写复制流程、快照迭代与去重实现。

---

核心源码解析

① CopyOnWriteArrayList 的内部存储

public class CopyOnWriteArrayList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    final transient ReentrantLock lock = new ReentrantLock();   // 写锁
    private transient volatile Object[] array;                  // 数据存储

    final void setArray(Object[] a) { array = a; }              // 发布新数组
    final Object[] getArray() { return array; }                 // 读取当前快照
}

• volatile transient Object[] array：volatile 保证写线程 setArray 后，读线程立即可见新数组（写-读 happens-before）；transient 表示序列化时绕过它，由 writeObject/readObject 自定义处理。
• 所有读方法的第一步都是 getArray() 拿到当前数组引用——此后操作的都是这个不可变快照，与并发写互不影响。
• 数组引用一旦发布，内容永不修改（只换引用不更元素），这是无锁读正确性的根基。

② CopyOnWriteArrayList.add(E e) 的加锁拷贝

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();                                   // ① 加写锁
    try {
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);  // ② 全量拷贝 + 1
        newElements[len] = e;                      // ③ 末尾追加
        setArray(newElements);                     // ④ 发布新数组
        return true;
    } finally {
        lock.unlock();                             // ⑤ 释放写锁
    }
}

• 三步写流程：加锁 → Arrays.copyOf 复制整数组 → setArray 发布。写操作串行化，杜绝并发写互相覆盖。
• lock.lock()（非公平）保证同一时刻只有一个写者；读操作不参与此锁。
• 每次 add 都是 O(n) 全量拷贝：n 越大写代价越高，这是"写时复制"的固有成本。

③ get(int index) 的无锁读

@SuppressWarnings("unchecked")
private E get(Object[] a, int index) { return (E) a[index]; }

public E get(int index) {
    return get(getArray(), index);                 // 快照上直接读，无需加锁
}

• 零同步读取：getArray() 取引用 → a[index] 读元素。数组内容不可变 + volatile 引用发布，二者共同保证读到的是某个一致版本的完整快照，不会读到半更新状态。
• 不变性保证：新数组在完全构造好之后才通过 setArray 发布，读线程要么看到旧数组（旧值），要么看到新数组（全量新值），绝无中间态。
• 同理 iterator()、size()、contains() 等都是无锁读；size() 直接返回 getArray().length。

④ addIfAbsent(E e) 的检查 + 拷贝

public boolean addIfAbsent(E e) {
    Object[] snapshot = getArray();                               // ① 无锁快照检查
    return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false
        : addIfAbsent(e, snapshot);
}

private boolean addIfAbsent(E e, Object[] snapshot) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] current = getArray();
        int len = current.length;
        if (snapshot != current) {                                // ② 检查期间有写操作
            int common = Math.min(snapshot.length, len);
            for (int i = 0; i < common; i++)
                if (current[i] != snapshot[i] && eq(e, current[i]))
                    return false;                                 // 已被并发加入
            if (indexOf(e, current, common, len) >= 0)
                return false;
        }
        Object[] newElements = Arrays.copyOf(current, len + 1);   // ③ 拷贝 + 追加
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

• 两阶段去重：先无锁扫快照（快速路径）；若期间有并发写（snapshot != current），加锁后重扫公共前缀 + 尾部确认不存在，避免重复加入。
• eq 用 Objects.equals 语义比较（e == o || e.equals(o)）；indexOf 从头线性查找。
• 返回 false 表示已存在（未加入），true 表示加入成功——这正是 CopyOnWriteArraySet.add 的去重依赖。

⑤ remove(Object o) 的拷贝删除

public boolean remove(Object o) {
    Object[] snapshot = getArray();
    int index = indexOf(o, snapshot, 0, snapshot.length);         // ① 快照定位
    return (index < 0) ? false : remove(o, snapshot, index);
}

private boolean remove(Object o, Object[] snapshot, int index) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] current = getArray();
        int len = current.length;
        if (snapshot != current) {                                // ② 快照失效则重定位
            findIndex: {
                int prefix = Math.min(index, len);
                for (int i = 0; i < prefix; i++)
                    if (current[i] != snapshot[i] && eq(o, current[i])) { index = i; break findIndex; }
                if (index >= len) return false;
                if (current[index] == o) break findIndex;
                index = indexOf(o, current, index, len);
                if (index < 0) return false;
            }
        }
        Object[] newElements = new Object[len - 1];               // ③ 新数组少一个元素
        System.arraycopy(current, 0, newElements, 0, index);      // 前段
        System.arraycopy(current, index + 1, newElements, index, len - index - 1);  // 后段
        setArray(newElements);                                    // ④ 发布
        return true;
    } finally {
        lock.unlock();
    }
}

• 快照失效重定位：无锁阶段找到的 index 在加锁后可能已漂移，通过"公共前缀比较 + 尾段重扫"精确定位当前数组中的真实位置。
• 删除同样走"新数组 + 两段 System.arraycopy + setArray"，newElements[len - 1] 语义即数组缩小一档。
• 读快照中的迭代器不受影响：它持有的旧数组引用仍完整有效。

⑥ COWIterator 的快照遍历

static final class COWIterator<E> implements ListIterator<E> {
    private final Object[] snapshot;    // 构造时固定的数组快照
    private int cursor;

    COWIterator(Object[] elements, int initialCursor) {
        cursor = initialCursor;
        snapshot = elements;
    }
    public boolean hasNext() { return cursor < snapshot.length; }
    @SuppressWarnings("unchecked")
    public E next() {
        if (cursor >= snapshot.length) throw new NoSuchElementException();
        return (E) snapshot[cursor++];
    }
    public void remove() { throw new UnsupportedOperationException(); }  // 快照不可变
    public void set(E e) { throw new UnsupportedOperationException(); }
    public void add(E e) { throw new UnsupportedOperationException(); }
}

• final Object[] snapshot：迭代器创建时一次性取数组引用，之后遍历固定快照——并发修改不影响遍历（不会抛 ConcurrentModificationException，也看不到新增元素）。
• 弱一致性语义：迭代期间其他线程的写对当前迭代不可见；迭代器不支持修改操作（快照只读）。
• COWSubList（subList 返回的视图）同理持有 expectedArray 快照，视图操作时校验快照，失效则抛 ConcurrentModificationException。

⑦ CopyOnWriteArraySet 的委派实现

public class CopyOnWriteArraySet<E> extends AbstractSet<E> implements java.io.Serializable {
    private final CopyOnWriteArrayList<E> al;     // 内部委托

    public CopyOnWriteArraySet() {
        al = new CopyOnWriteArrayList<E>();
    }
    public boolean add(E e) {
        return al.addIfAbsent(e);                 // 去重：不存在才加入
    }
    public boolean contains(Object o) { return al.contains(o); }
    public boolean remove(Object o) { return al.remove(o); }
    public Iterator<E> iterator() { return al.iterator(); }
    public int size() { return al.size(); }
}

• 零额外逻辑：CopyOnWriteArraySet 完全委托 CopyOnWriteArrayList，靠 addIfAbsent 天然保证无重复，不需要自己的存储。
• 因此它继承了 COW 的全部特性：无锁读、写复制、快照迭代、弱一致性；同时也继承了写 O(n) 的代价。
• 适用：需要"读多写少 + 去重 + 并发遍历安全"的集合场景（如监听器注册表、路由表快照）。

⑧ 适用场景与性能权衡

维度	说明
读	O(1) 无锁（volatile 读 + 数组索引）
写	O(n) 全量拷贝 + 加锁（Arrays.copyOf + setArray）
迭代	快照遍历，弱一致，不抛 ConcurrentModificationException
内存	写操作产生双份数组（旧 + 新），GC 压力上升
一致性	读写分离快照；读可能看不到最新写入（最终可见）
最佳场景	读多写少、遍历频繁、集合小（如配置监听器、黑白名单）
不适用	写密集、元素量大（每次写都 O(n) 拷贝 + 双份内存）

• 典型用途：事件监听器集合（遍历频率远高于注册/注销）、缓存配置快照、订阅者列表——这些场景"读与遍历"是主路径，写是低频操作。
• 若写占比高或集合很大，应改用 ConcurrentHashMap（分段无锁）或 ConcurrentSkipListSet（有序 + 无锁）——它们的写不需要全量复制。
• 内存警示：大集合 + 高写频率会导致频繁复制与旧数组短暂共存，注意堆内存与 GC 压力。

---

总结

机制	实现	设计要点
存储	volatile Object[] array	引用发布 + 内容不可变
读	getArray() + 索引	零锁、弱一致
写	lock + Arrays.copyOf + setArray	串行化、全量复制
去重	addIfAbsent 两阶段检查	快照 + 加锁重扫
迭代	COWIterator 快照	并发安全、不支持修改

写时复制的核心哲学是"用空间换并发"：用每次写操作的全量拷贝，换取读路径的绝对无锁与迭代的绝对安全。理解 volatile 发布 + 不可变快照这两个支点，就掌握了 CopyOnWrite* 家族的全部并发语义。