【Java 并发编程】CopyOnWriterArrayList 详解

CopyOnWriterArrayList 详解

1. ArrayList

1.1 ArrayList 和 LinkedList 的区别

  • ArrayList：底层是数组实现，线程不安全，查询和修改非常快，但是增加和删除慢。

  • LinkedList：底层是双向链表，线程不安全，查询和修改速度慢，但是增加和删除速度快。

1.2 ArrayList 如何保证线程安全

JDK 建议我们，如果有多个线程并发访问 ArrayList 实例，并且至少有一个线程做修改操作（可能会引起线程安全问题，具体表现为 ConcurrentModificationException 异常），要自己加锁或者使用 Collections.synchronizedList 方法。

在这里插入图片描述
其实，在 Java 并发包下实现了线程安全的 ArrayList - CopyOnWriteArrayList。

2. CopyOnWriteArrayList 原理

CopyOnWriteArrayList 适用于读多写少的并发场景，其内部适用写时复制的机制，它的核心思想是在写操作时，先创建一个原集合的副本（即拷贝一份原始数组），然后在副本上进行修改操作，最后将修改后的副本替换原集合。这样可以保证在写操作期间，其他线程仍然可以安全地读取原集合的数据（读操作返回的结果可能不是最新的），不会受到并发修改的影响。

在这里插入图片描述

CopyOnWriteArrayList 在结构上与 ArrayList 类似（内部都是使用数组来存储元素），但在线程安全性和写操作的代价上有所不同，基本会分为4步：

  • 加锁；

  • 从原数组中拷贝出新数组；

  • 在新数组上进行操作，并把新数组赋值给数组容器；

  • 释放锁。

除了加锁之外，CopyOnWriteArrayList 的底层数组还被 volatile 关键字修饰，意味着一旦数组被修改，其它线程立马能够感知到：

private transient volatile Object[] array;

总结：CopyOnWriteArrayList 的设计思想是：读写分离 + 最终一致，并利用 锁 + 数组拷贝 + volatile 关键字保证了 List 的线程安全。

3. CopyOnWriteArrayList 的优缺点

3.1 优点

  1. 线程安全：CopyOnWriteArrayList 在写操作时采用写时复制的策略，即创建一个副本进行修改，这保证了写操作的安全性。其他线程可以继续读取原集合的数据，不会受到写操作的影响。

  2. 高效的读操作：读取操作不需要加锁或同步，多个线程可以同时读取 CopyOnWriteArrayList，不会出现读取冲突的情况。

CopyOnWriteArrayList 适用于读多写少的并发环境，例如缓存、观察者模式等场景。在这些场景中，读操作远远多于写操作，CopyOnWriteArrayList 可以提供较好的性能和线程安全性。

3.2 缺点

  1. 内存占用：由于每次写操作都会创建一个新的数组，CopyOnWriteArrayList 会消耗更多的内存空间。如果集合中的元素较多或写操作频繁，可能导致 young gc 或者 full gc。

  2. 数据一致性：CopyOnWriteArrayList 的写操作是通过创建副本数组来实现的，因此在写操作过程中，读取操作仍然访问原始数组。这意味着在写操作期间，读取操作可能无法立即反映最新的修改。这种数据一致性的延迟可能会对某些应用场景产生影响。

CopyOnWriteArrayList 不适用于写操作过多、实时性要求高的场景，需要根据具体的应用场景进行权衡和选择。

4. 源码分析

4.1 两个成员变量

// 可重入锁，用于对写操作加锁
final transient ReentrantLock lock = new ReentrantLock();

// Object类型数组，存放数据，volatile 修饰，目的是一个线程对这个字段的修改另外一个线程立即可见
private transient volatile Object[] array;

4.2 构造函数

CopyOnWriteArrayList() 空参构造函数：

public CopyOnWriteArrayList() {
    setArray(new Object[0]);
}

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

无参构造函数直接创建了一个长度为 0 的 Object 数组。

CopyOnWriteArrayList(Collection<? extends E> c)：

public CopyOnWriteArrayList(Collection<? extends E> c) {
    Object[] elements;
    if (c.getClass() == CopyOnWriteArrayList.class)
        // 如果集合类型就是 CopyOnWriteArrayList，则直接将其 array 赋值给当前 CopyOnWriteArrayList
        elements = ((CopyOnWriteArrayList<?>)c).getArray();
    else {
        // 如果不是 CopyOnWriteArrayList 类型，则将集合转换为数组
        elements = c.toArray();
        // 就如 ArrayList 源码分析所述那样，c.toArray() 返回类型不一定是 Object[].class，所以需要转换
        if (elements.getClass() != Object[].class)
            elements = Arrays.copyOf(elements, elements.length, Object[].class);
    }
    // 设置 array 值
    setArray(elements);
}

CopyOnWriteArrayList(E[] toCopyIn)：

public CopyOnWriteArrayList(E[] toCopyIn) {
    // 入参为数组，拷贝一份赋值给 array
    setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}

4.3 add(E e)

add(E e) 往 CopyOnWriteArrayList 末尾添加元素：

public boolean add(E e) {
    // 获取可重入锁
    final ReentrantLock lock = this.lock;
    // 上锁，同一时间内只能有一个线程进入
    lock.lock();
    try {
        // 获取当前 array 属性值
        Object[] elements = getArray();
        // 获取当前 array 数组长度
        int len = elements.length;
        // 复制一份新数组，新数组长度为当前 array 数组长度 +1
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        // 在新数组末尾添加元素
        newElements[len] = e;
        // 新数组赋值给 array 属性
        setArray(newElements);
        return true;
    } finally {
        // 锁释放
        lock.unlock();
    }
}

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

可以看到，add 操作通过 ReentrantLock 来确保线程安全。通过 add 方法，我们也可以看出 CopyOnWriteArrayList 修改操作的基本思想为：复制一份新的数组，新数组长度刚好能够容纳下需要添加的元素；在新数组里进行操作；最后将新数组赋值给 array 属性，替换旧数组。这种思想也称为 “写时复制”，所以称为 CopyOnWriteArrayList。

此外，我们可以看到 CopyOnWriteArrayList 中并没有类似于 ArrayList 的 grow 方法扩容的操作。

4.4 add(int index, E element)

add(int index, E element) 指定下标添加指定元素：

public void add(int index, E element) {
    // 获取可重入锁
    final ReentrantLock lock = this.lock;
    // 上锁，同一时间内只能有一个线程进入
    lock.lock();
    try {
        // 获取当前 array 属性值
        Object[] elements = getArray();
        // 获取当前 array 数组长度
        int len = elements.length;
        // 下标检查
        if (index > len || index < 0)
            throw new IndexOutOfBoundsException("Index: "+index+", Size: "+len);
        Object[] newElements;
        int numMoved = len - index;
        if (numMoved == 0)
            // numMoved 为 0，说明是在末尾添加，过程和 add(E e) 方法一致
            newElements = Arrays.copyOf(elements, len + 1);
        else {
            // 否则创建一个新数组，数组长度为旧数组长度值 +1
            newElements = new Object[len + 1];
            // 分两次复制，分别将 index 之前和 index+1 之后的元素复制到新数组中
            System.arraycopy(elements, 0, newElements, 0, index);
            System.arraycopy(elements, index, newElements, index + 1, numMoved);
        }
        // 在新数组的 index 位置添加指定元素
        newElements[index] = element;
        // 新数组赋值给 array 属性，替换旧数组
        setArray(newElements);
    } finally {
        // 锁释放
        lock.unlock();
    }
}

4.5 set(int index, E element)

set(int index, E element) 设置指定位置的值：

public E set(int index, E element) {
    // 获取可重入锁
    final ReentrantLock lock = this.lock;
    // 上锁，同一时间内只能有一个线程进入
    lock.lock();
    try {
        // 获取当前 array 属性值
        Object[] elements = getArray();
        // 获取当前 array 指定 index 下标值
        E oldValue = get(elements, index);
        if (oldValue != element) {
            // 如果新值和旧值不相等
            int len = elements.length;
            // 复制一份新数组，长度和旧数组一致
            Object[] newElements = Arrays.copyOf(elements, len);
            // 修改新数组 index 下标值
            newElements[index] = element;
            // 新数组赋值给 array 属性，替换旧数组
            setArray(newElements);
        } else {
            // 即使新值和旧值一致，为了确保 volatile 语义，需要重新设置 array
            setArray(elements);
        }
        return oldValue;
    } finally {
        // 释放锁
        lock.unlock();
    }
}

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

4.6 remove(int index)

remove(int index) 删除指定下标元素：

public E remove(int index) {
    // 获取可重入锁
    final ReentrantLock lock = this.lock;
    // 上锁，同一时间内只能有一个线程进入
    try {
        // 获取当前 array 属性值
        Object[] elements = getArray();
        // 获取当前 array 长度
        int len = elements.length;
        // 获取旧值
        E oldValue = get(elements, index);
        int numMoved = len - index - 1;
        if (numMoved == 0)
            // 如果删除的是最后一个元素，则将当前 array 设置为新数组
            // 新数组长度为旧数组长度 -1，这样刚好截去了最后一个元素
            setArray(Arrays.copyOf(elements, len - 1));
        else {
            // 分段复制，将 index 前的元素和 index+1 后的元素复制到新数组
            // 新数组长度为旧数组长度 -1
            Object[] newElements = new Object[len - 1];
            System.arraycopy(elements, 0, newElements, 0, index);
            System.arraycopy(elements, index + 1, newElements, index, numMoved);
            // 设置 array
            setArray(newElements);
        }
        return oldValue;
    } finally {
        // 锁释放
        lock.unlock();
    }
}

可以看到，CopyOnWriteArrayList 中的增删改操作都是在新数组中进行的，并且通过加锁的方式确保同一时刻只能有一个线程进行操作，操作完后赋值给 array 属性，替换旧数组，旧数组失去了引用，最终由 GC 回收。

4.7 get(int index)

public E get(int index) {
    return get(getArray(), index);
}
final Object[] getArray() {
    return array;
}

可以看到，get(int index) 操作是分两步进行的：

  1. 通过 getArray() 获取array属性值；
  2. 获取 array 数组 index 下标值。

这个过程并没有加锁，所以在并发环境下可能出现如下情况：

  1. 线程1调用 get(int index) 方法获取值，内部通过 getArray() 方法获取到了array 属性值；
  2. 线程2调用 CopyOnWriteArrayList 的增删改方法，内部通过 setArray 方法修改了array 属性的值；
  3. 线程1还是从旧的 array 数组中取值。

所以 get 方法是弱一致性的。

4.8 size()

public int size() {
    return getArray().length;
}

size() 方法返回当前 array 属性长度，因为 CopyOnWriteArrayList 中的 array 数组每次复制都刚好能够容纳下所有元素，并不像 ArrayList 那样会预留一定的空间。所以 CopyOnWriteArrayList 中并没有 size 属性，元素的个数和数组的长度是相等的。

4.9 迭代器

public Iterator<E> iterator() {
    return new COWIterator<E>(getArray(), 0);
}
static final class COWIterator<E> implements ListIterator<E> {
    /** Snapshot of the array */
    private final Object[] snapshot;
    /** Index of element to be returned by subsequent call to next.  */
    private int cursor;

    private COWIterator(Object[] elements, int initialCursor) {
        cursor = initialCursor;
        snapshot = elements;
    }

    public boolean hasNext() {
        return cursor < snapshot.length;
    }
    ......
}

可以看到，迭代器也是弱一致性的，并没有在锁中进行。如果其他线程没有对 CopyOnWriteArrayList 进行增删改的操作，那么 snapshot 还是创建迭代器时获取的 array，但是如果其他线程对 CopyOnWriteArrayList 进行了增删改的操作，旧的数组会被新的数组给替换掉，但是 snapshot 还是原来旧的数组的引用：

CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
list.add("hello");
Iterator<String> iterator = list.iterator();
list.add("world");
while (iterator.hasNext()){
    System.out.println(iterator.next());
}

输出结果仅为 hello。

6. 迭代器的 fail-fast 与 fail-safe 机制

在 Java 中，迭代器（Iterator）在迭代的过程中，如果底层的集合被修改（添加或删除元素），不同的迭代器对此的表现行为是不一样的，可分为两类：Fail-Fast（快速失败）和 Fail-Safe（安全失败）。

6.1 fail-fast 机制

fail-fast 机制是 java 集合（Collection）中的一种错误机制。当多个线程对同一个集合的内容进行操作时，就可能会产生 fail-fast 事件。例如：当某一个线程A通过 iterator 去遍历某集合的过程中，若该集合的内容被其他线程所改变了；那么线程A访问集合时，就会抛出 ConcurrentModificationException 异常，产生 fail-fast 事件。

在 java.util 包中的集合，如 ArrayList、HashMap 等，它们的迭代器默认都是采用 fail-fast 机制。

在这里插入图片描述

fail-fast 解决方案

  • 方案一：在遍历过程中所有涉及到改变 modCount 值的地方全部加上 synchronized 或者直接使用 Collection#synchronizedList，这样就可以解决问题，但是不推荐，因为增删造成的同步锁可能会阻塞遍历操作。

  • 方案二：使用 CopyOnWriteArrayList 替换 ArrayList，推荐使用该方案（即fail-safe）。

6.2 fail-safe 机制

任何对集合结构的修改都会在一个复制的集合上进行，因此不会抛出 ConcurrentModificationException。在 java.util.concurrent 包中的集合，如 CopyOnWriteArrayList、ConcurrentHashMap 等，它们的迭代器一般都是采用 Fail-Safe 机制。

缺点：

  • 采用 Fail-Safe 机制的集合类都是线程安全的，但是它们无法保证数据的实时一致性，它们只能保证数据的最终一致性。在迭代过程中，如果集合被修改了，可能读取到的仍然是旧的数据。

  • Fail-Safe 机制还存在另外一个问题，就是内存占用。由于这类集合一般都是通过复制来实现读写分离的，因此它们会创建出更多的对象，导致占用更多的内存，甚至可能引起频繁的垃圾回收，严重影响性能。

5. 总结

  1. CopyOnWriteArrayList 体现了写时复制的思想，增删改操作都是在复制的新数组中进行的；

  2. CopyOnWriteArrayList 的取值方法是弱一致性的，无法确保实时取到最新的数据；

  3. CopyOnWriteArrayList 的增删改方法通过可重入锁确保线程安全；

  4. CopyOnWriteArrayList 线程安全体现在多线程增删改不会抛出java.util.ConcurrentModificationException异常，并不能确保数据的强一致性；

  5. 同一时刻只能有一个线程对 CopyOnWriteArrayList 进行增删改操作，而读操作没有限制，并且 CopyOnWriteArrayList 增删改操作都需要复制一份新数组，增加了内存消耗，所以 CopyOnWriteArrayList 适合读多写少的情况。