Java 数据结构：CopyOnWriteArrayList 是如何保证线程安全的？-六虎

本文已收录到 AndroidFamily，技能和职场问题，请关注大众号 [彭旭锐] 发问。

前语

大家好，我是小彭。

在上一篇文章里，咱们聊到了ArrayList 的线程安全问题，其中提到了 CopyOnWriteArrayList 的处理办法。那么 CopyOnWriteArrayList 是如何处理线程安全问题的，背面的设计思维是什么，今天咱们就环绕这些问题展开。

本文源码根据 Java 8 CopyOnWriteArrayList。

思维导图：

Java 数据结构：CopyOnWriteArrayList 是如何保证线程安全的？

1. 回忆 ArrayList

ArrayList 是根据数组完结的动态数据，是线程不安全的。例如，咱们在遍历 ArrayList 的时分，假如其他线程并发修正数组（当然也不一定是被其他线程修正），在迭代器中就会触发 fail-fast 机制，抛出 ConcurrentModificationException 反常。

示例程序

List<String> list = new ArrayList();
list.add("xiao");
list.add("peng");
list.add(".");
Iterator iterator = list.iterator();
while (iterator.hasNext()) {
    // 或许抛出 ConcurrentModificationException 反常
    iterator.next();
}

要完结线程安全有 3 种办法：

办法 1 – 运用 Vector 容器： Vector 是线程安全版本的数组容器，它会在所有办法上增加 synchronized 关键字（过期，了解即可）；
办法 2 – 运用 Collections.synchronizedList 包装类
办法 3 – 运用 CopyOnWriteArrayList 容器

Collections.synchronizedList 包装类的原理很简略，便是运用 synchronized 加锁，源码摘要如下：

Collections.java

public static <T> List<T> synchronizedList(List<T> list) {
    return (list instanceof RandomAccess ?
            new SynchronizedRandomAccessList<>(list) :
            new SynchronizedList<>(list));
}
// 运用 synchronized 完结线程安全
static class SynchronizedList<E> extends SynchronizedCollection<E> implements List<E> {
    final List<E> list;
    public boolean equals(Object o) {
        if (this == o) return true;
        synchronized (mutex) {return list.equals(o);}
    }
    public int hashCode() {
        synchronized (mutex) {return list.hashCode();}
    }
    public E get(int index) {
        synchronized (mutex) {return list.get(index);}
    }
    public E set(int index, E element) {
        synchronized (mutex) {return list.set(index, element);}
    }
    public void add(int index, E element) {
        synchronized (mutex) {list.add(index, element);}
    }
    public E remove(int index) {
        synchronized (mutex) {return list.remove(index);}
    }
		...
}

假如咱们将 ArrayList 替换为 CopyOnWriteArrayList，即使其他线程并发修正数组，也不会抛出 ConcurrentModificationException 反常，这是为什么呢？

2. CopyOnWriteArrayList 的特点

CopyOnWriteArrayList 和 ArrayList 都是根据数组的动态数组，封装了操作数组时的转移和扩容等逻辑。除此之外，CopyOnWriteArrayList 仍是用了根据加锁的 “读写别离” 和 “写时仿制” 的计划处理线程安全问题：

思维 1 – 读写别离（Read/Write Splitting）： 将对资源的读取和写入操作别离，使得读取和写入没有依赖，在 “读多写少” 的场景中能有用减少资源竞赛；
思维 2 – 写时仿制（CopyOnWrite，COW）： 在写入数据时，不直接在原数据上修正，而是仿制一份新数据后写入到新数据，最终再替换到原数据的引证上。这个特性各有优缺陷：
- 长处 1 – 延迟处理： 在没有写入操作时不会仿制 / 分配资源，能够防止瞬时的资源消耗。例如操作系统的 fork 操作也是一种写时仿制的思维；
- 长处 2 – 下降锁颗粒度： 在写的进程中，读操作不会被影响，读操作也不需求加锁，锁的颗粒度从整个列表下降为写操作；
- 缺陷 1 – 弱数据共同性： 在读的进程中，假如数据被其他线程修正，是无法实时感知到最新的数据变化的；
- 缺陷 2 – 有内存压力： 在写操作中需求仿制原数组，在仿制的进程中内存会同时存在两个数组目标（仅仅引证，数组元素的目标仍是只需一份），会带来内存占用和垃圾回收的压力。假如是 “写多读少” 的场景，就不合适。

所以，运用 CopyOnWriteArrayList 的场景一定要确保是 “读多写少” 且数据量不大的场景，并且在写入数据的时分，要做到批量操作。不然每个写入操作都会触发一次仿制，想想就可怕。举 2 个比如：

例如批量写入一组数据，要运用 addAll 办法批量写入；
例如在做排序时，要先输出为 ArrayList，在 ArrayList 上完结排序后再写回 CopyOnWriteArrayList。

3. CopyOnWriteArrayList 源码剖析

这一节，咱们来剖析 CopyOnWriteArrayList 中首要流程的源码。

3.1 CopyOnWriteArrayList 的特点

ArrayList 的特点很好了解，底层是一个 Object 数组，我要举手发问 ‍♀️：

疑问 1： 为什么 array 字段要运用 volatile 关键字？

// 锁
final transient ReentrantLock lock = new ReentrantLock();
// 在 Java 11 中，ReentrantLock 被替换为 synchronized 锁
// The lock protecting all mutators.  (We have a mild preference for builtin monitors over ReentrantLock when either will do.)
final transient Object lock = new Object();
// 底层数组
// 疑问 1：为什么 array 要运用 volatile 关键字？
private transient volatile Object[] array;

这个问题咱们在剖析源码的进程中回答。有了 ArrayList 的剖析基础，疑问也变少了，CopyOnWriteArrayList 真香。

3.2 CopyOnWriteArrayList 的结构办法

结构器的源码不难，但小朋友总有太多的问号，举手发问 ‍♀️：

疑问 2：为什么 CopyOnWriteArrayList 不供给初始化容量的结构器？

这是因为 CopyOnWriteArrayList 主张咱们运用批量操作写入数据。假如供给了带初始化容量的结构器，意味着开发者预期会一个个地写入数据，这不契合 CopyOnWriteArrayList 的正确运用办法。所以，不供给这个结构器才是合理的。

疑问 3：为什么要把 E[] 类型的入参转化为 Object[] 类型？

假如不转化数组类型，那么在 toArray() 办法回来的数组中刺进 Object 类型目标时，会抛出 ArrayStoreException。

提示： 这个问题与 “奇怪” 分支的原因相同，具体剖析能够看讲《Java 面试题：ArrayList 能够彻底替代数组吗？》的文章中，这里不重复讲了。

// 疑问 2：为什么 CopyOnWriteArrayList 不供给预初始化容量的结构器？
// 无参结构办法
public CopyOnWriteArrayList() {
    // 创立空数组
    setArray(new Object[0]);
}
// 带调集的结构办法
public CopyOnWriteArrayList(Collection<? extends E> c) {
    Object[] elements;
    if (c.getClass() == CopyOnWriteArrayList.class)
        elements = ((CopyOnWriteArrayList<?>)c).getArray();
    else {
        elements = c.toArray();
        // 这个“奇怪”的分支在 ArrayList 文章中剖析过，去看看
        if (elements.getClass() != Object[].class)
            elements = Arrays.copyOf(elements, elements.length, Object[].class);
    }
    setArray(elements);
}
// 带数组的结构办法
public CopyOnWriteArrayList(E[] toCopyIn) {
    // 疑问 3：为什么要把 E[] 类型的入参转化为 Object[] 类型
    setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, *Object[]*.class));
}
final Object[] getArray() {
    return array;
}
final void setArray(Object[] a) {
    array = a;
}
public Object[] toArray() {
    Object[] elements = getArray();
    return Arrays.copyOf(elements, elements.length);
}

3.3 CopyOnWriteArrayList 的写办法

咱们将 CopyOnWriteArrayList 的增加、删去和修正办法共同为 “写办法”，三种写办法的模板其实是一样的：

1、在写入之前先获取目标的锁；
2、仿制新数组；
3、在新数组上完结写入操作；
4、将新数组设置为底层数组；
5、开释目标的锁。

小朋友总是有太多问号，举手发问 ‍♀️：

疑问 4：在增加办法中，为什么扩容只增大 1 容量，而 ArrayList 会增大 1.5 倍？

这仍是因为 CopyOnWriteArrayList 主张咱们运用批量操作写入数据。ArrayList 额定扩容 1.5 倍是为了防止每次 add 都扩容，而 CopyOnWriteArrayList 并不主张一个个地增加数据，而是主张批量操作写入数据，例如 addAll 办法。所以，CopyOnWriteArrayList 不额定扩容才是合理的。

别的，网上有观点看到 CopyOnWriteArrayList 没有约束数组最大容量，~~就说 CopyOnWriteArrayList 是无界的，没有容量约束~~。这明显太表面了。数组的长度约束是被虚拟机固化的，CopyOnWriteArrayList 没有约束的原因是：它没有做额定扩容，并且不合适大数据的场景，所以没有约束的必要。

最终还剩余 1 个问题：

疑问 1：为什么 array 字段要运用 volatile 关键字？

volatile 变量是 Java 轻量级的线程同步原语，volatile 变量的读取和写入操作中会参加内存屏障，能够确保变量写入的内存可见性，确保一个线程的写入能够被另一个线程观察到。

增加办法

// 在数组尾部增加元素
public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    // 获取锁
    lock.lock();
    // 仿制新数组
    Object[] elements = getArray();
    int len = elements.length;
    // 疑问 4：在增加办法中，为什么扩容只增大 1 容量，而 ArrayList 会增大 1.5 倍？
    Object[] newElements = Arrays.copyOf(elements, len + 1 /* 容量 + 1*/);
    // 在新数组上增加元素
    newElements[len] = e;
    // 设置新数组
    setArray(newElements);
    // 开释锁
    lock.unlock();
    return true;
}
// 在数组尾部增加元素
public void add(int index, E element) {
    // 原理相同，省掉
    ...
}
// 批量在数组尾部增加元素
public boolean addAll(Collection<? extends E> c) {
    // 原理相同，省掉
    ...
}

修正办法

// 修正数组元素
public E set(int index, E element) {
    final ReentrantLock lock = this.lock;
    // 获取锁
    lock.lock();
    // 旧元素
    Object[] elements = getArray();
    E oldValue = get(elements, index);
    if (oldValue != element) {
        // 仿制新数组
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len);
        // 在新数组上增加元素
        newElements[index] = element;
        // 设置新数组
        setArray(newElements);
    } else {
        // Not quite a no-op; ensures volatile write semantics
        setArray(elements);
    }
    // 开释锁
    lock.unlock();
    // 回来旧数据
    return oldValue;
}

删去办法

// 删去数组元素
public E remove(int index) {
    final ReentrantLock lock = this.lock;
    // 获取锁
    lock.lock();
    Object[] elements = getArray();
    int len = elements.length;
    // 旧元素
    E oldValue = get(elements, index);
    int numMoved = len - index - 1;
    if (numMoved == 0)
        // 删去首位元素
        setArray(Arrays.copyOf(elements, len - 1));
    else {
        // 删去中心元素
        // 仿制新数组
        Object[] newElements = new Object[len - 1];
        System.arraycopy(elements, 0, newElements, 0, index);
        System.arraycopy(elements, index + 1, newElements, index, numMoved);
        // 设置新数组
        setArray(newElements);
    }
    // 开释锁
    lock.unlock();
    // 回来旧数据
    return oldValue;
}

3.4 CopyOnWriteArrayList 的读取办法

能够看到读取办法并没有加锁。

private E get(Object[] a, int index) {
    return (E) a[index];
}
public E get(int index) {
    return get(getArray(), index);
}
public boolean contains(Object o) {
    Object[] elements = getArray();
    return indexOf(o, elements, 0, elements.length) >= 0;
}

3.5 CopyOnWriteArrayList 的迭代器

CopyOnWriteArrayList 的迭代器 COWIterator 是 “弱数据共同性的” ，所谓数据共同性问题讨论的是同一份数据在多个副本之间的共同性问题，你也能够了解为多个副本的状况共同性问题。例如内存与多核心 Cache 副本之间的共同性，或许数据在主从数据库之间的共同性。

提示： 关于 “数据共同性和次序共同性” 的差异，在小彭的计算机组成原理专栏讨论过《现已有 MESI 协议，为什么还需求 volatile 关键字？》，去看看。

为什么是 “弱” 的呢？这是因为 COWIterator 迭代器会持有 CopyOnWriteArrayList “底层数组” 的引证，而 CopyOnWriteArrayList 的写入操作是写入到新数组，因而 COWIterator 是无法感知到的，除非重新创立迭代器。

相较之下，ArrayList 的迭代器是经过持有 “外部类引证” 的办法访问 ArrayList 的底层数组，因而在 ArrayList 上的写入操作会实时被迭代器观察到。

CopyOnWriteArrayList.java

// 注意看：有 static 关键字，直接引证底层数组
static final class COWIterator<E> implements ListIterator<E> {
    // 底层数组
    private final Object[] snapshot;
    private int cursor;
    private COWIterator(Object[] elements, int initialCursor) {
        cursor = initialCursor;
        snapshot = elements;
    }
}

ArrayList.java

// 注意看：没有 static 关键字，经过外部类引证来访问底层数组
private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;
    Itr() {}
    ...
}

3.6 CopyOnWriteArraySet 的序列化进程

与 ArrayList 相似，CopyOnWriteArraySet 也重写了 JDK 序列化的逻辑，只把 elements 数组中有用元素的部分序列化，而不会序列化整个数组。

同时，ReentrantLock 目标是锁目标，序列化没有意义。在反序列化时，会经过 resetLock() 设置一个新的 ReentrantLock 目标。

// 序列化进程
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException {
    s.defaultWriteObject();
    Object[] elements = getArray();
    // 写入数组长度
    s.writeInt(elements.length);
    // 写入有用元素
    for (Object element : elements)
        s.writeObject(element);
}
// 反序列化进程
private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException {
    s.defaultReadObject();
    // 设置 ReentrantLock 目标
    resetLock();
    // 读取数组长度
    int len = s.readInt();
    SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, len);
    // 创立底层数组
    Object[] elements = new Object[len];
    // 读取数组目标
    for (int i = 0; i < len; i++)
        elements[i] = s.readObject();
    // 设置新数组
    setArray(elements);
}
// 疑问 5：resetLock() 办法不好了解，解释一下？
private void resetLock() {
    // 等价于带 Volatile 语义的 this.lock = new ReentrantLock()
    UNSAFE.putObjectVolatile(this, lockOffset, new ReentrantLock());
}
// Unsafe API
private static final sun.misc.Unsafe UNSAFE;
// lock 字段在目标实例数据中的偏移量
private static final long lockOffset;
static {
    // 这三行的作用：lock 字段在目标实例数据中的偏移量
    UNSAFE = sun.misc.Unsafe.getUnsafe();
    Class<?> k = CopyOnWriteArrayList.class;
    lockOffset = UNSAFE.objectFieldOffset(k.getDeclaredField("lock"));
}

小朋友又是有太多问号，举手发问 ‍♀️：

‍♀️疑问 5：resetLock() 办法不好了解，解释一下？

在 static 代码块中，会运用 Unsafe API 获取 CopyOnWriteArrayList 的 “lock 字段在目标实例数据中的偏移量” 。因为字段的偏移是全局固定的，所以这个偏移量能够记录在 static 字段 lockOffset 中。

在 resetLock() 中，经过 UnSafe API putObjectVolatile 将新建的 ReentrantLock 目标设置到 CopyOnWriteArrayList 的 lock 字段中，等价于带 volatile 语义的 this.lock = new ReentrantLock()，确保这个字段的写入具有内存可见性。

字段的偏移量是什么意思呢？简略来说，一般目标和 Class 目标的实例数据区域是不同的：

1、一般目标：包含当时类声明的实例字段以及父类声明的实例字段，不包含类的静态字段。UnSafe API objectFieldOffset(Filed) 便是获取了参数 Filed 在实例数据中的偏移量，后续就能够经过这个偏移量为字段赋值；
2、Class 目标：包含当时类声明的静态字段和办法表等。

目标内存布局

提示： 关于字段的偏移量，咱们在《目标的内存分为哪几个部分？》这篇文章里讨论过，去看看。

3.7 CopyOnWriteArraySet 的 clone() 进程

CopyOnWriteArraySet 的 clone() 很奇妙。依照正常的思维，CopyOnWriteArraySet 中的 array 数组是引证类型，因而在 clone() 中需求完结深复制，不然原目标与克隆目标就会相互影响。但事实上，array 数组并没有被深复制，哇点解啊？

‍♀️疑问 6：为什么 array 数组没有深复制？

这便是因为 CopyOnWrite 啊！没有 Write 为什么要 Copy 呢？（我觉得现已提醒到位了，只需你仔细阅读前文对 CopyOnWrite 的论证，你一定会懂的。要是是在不明白，私信我吧~）

public Object clone() {
    try {
        @SuppressWarnings("unchecked")
        // 疑问 6：为什么 array 数组没有深复制？
        CopyOnWriteArrayList<E> clone = (CopyOnWriteArrayList<E>) super.clone();
        // 设置 ReentrantLock 目标（相当于 lock 字段的深复制）
        clone.resetLock();
        return clone;
    } catch (CloneNotSupportedException e) {
        // this shouldn't happen, since we are Cloneable
        throw new InternalError();
    }
}

4. CopyOnWriteArraySet 源码剖析

在 Java 规范库中，还供给了一个运用 COW 思维的 Set 调集 —— CopyOnWriteArraySet。

CopyOnWriteArraySet 和 HashSet 都是承继于 AbstractSet 的，但 CopyOnWriteArraySet 是根据 CopyOnWriteArrayList 动态数组的，并没有运用哈希思维。而 HashSet 是根据 HashMap 散列表的，能够完结 O(1) 查询。

4.1 CopyOnWriteArraySet 的结构办法

看一下 CopyOnWriteArraySet 的结构办法，底层便是有一个 CopyOnWriteArrayList 动态数组。

CopyOnWriteArraySet.java

public class CopyOnWriteArraySet<E> extends AbstractSet<E> implements java.io.Serializable {
    // 底层便是 OnWriteArrayList
    private final CopyOnWriteArrayList<E> al;
    // 无参结构办法
    public CopyOnWriteArraySet() {
        al = new CopyOnWriteArrayList<E>();
    }
    // 带调集的结构办法
    public CopyOnWriteArraySet(Collection<? extends E> c) {
        if (c.getClass() == CopyOnWriteArraySet.class) {
            // 入参是 CopyOnWriteArraySet，说明是不重复的，直接增加
            CopyOnWriteArraySet<E> cc = (CopyOnWriteArraySet<E>)c;
            al = new CopyOnWriteArrayList<E>(cc.al);
        }
        else {
            // 运用 addAllAbsent 增加不重复的元素
            al = new CopyOnWriteArrayList<E>();
            al.addAllAbsent(c);
        }
    }
    public int size() {
        return al.size();
    }
}

4.2 CopyOnWriteArraySet 的操作办法

CopyOnWriteArraySet 的办法基本上都是交给 CopyOnWriteArraySet 代理的，因为没有运用哈希思维，所以操作的时刻复杂度是 O(n)。

CopyOnWriteArraySet.java

public boolean add(E e) {
    return al.addIfAbsent(e);
}
public boolean contains(Object o) {
    return al.contains(o);
}

CopyOnWriteArrayList.java

public boolean addIfAbsent(E e) {
    Object[] snapshot = getArray();
    return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false : addIfAbsent(e, snapshot);
}
public boolean contains(Object o) {
    Object[] elements = getArray();
    return indexOf(o, elements, 0, elements.length) >= 0;
}
// 经过线性扫描匹配元素位置，而不是计算哈希匹配，时刻复杂度是 O(n)
private static int indexOf(Object o, Object[] elements, int index, int fence) {
    if (o == null) {
        for (int i = index; i < fence; i++)
            if (elements[i] == null) return i;
    } else {
        for (int i = index; i < fence; i++)
            if (o.equals(elements[i])) return i;
    }
    return -1;
}

5. 总结

1、CopyOnWriteArrayList 和 ArrayList 都是根据数组的动态数组，封装了操作数组时的转移和扩容等逻辑；
2、CopyOnWriteArrayList 仍是 “读写别离” 和 “写时仿制” 的计划处理线程安全问题；
3、运用 CopyOnWriteArrayList 的场景一定要确保是 “读多写少” 且数据量不大的场景，并且在写入数据的时分，要做到批量操作；
4、CopyOnWriteArrayList 的迭代器是 “弱数据共同性的” 的，迭代器会持有 “底层数组” 的引证，而 CopyOnWriteArrayList 的写入操作是写入到新数组，因而迭代器是无法感知到的；
5、CopyOnWriteArraySet 是根据 CopyOnWriteArrayList 动态数组的，并没有运用哈希思维。

版权声明

本文为稀土技能社区首发签约文章，14天内禁止转载，14天后未获授权禁止转载，侵权必究！

Java 数据结构：CopyOnWriteArrayList 是如何保证线程安全的？

前语

1. 回忆 ArrayList

2. CopyOnWriteArrayList 的特点

3. CopyOnWriteArrayList 源码剖析

3.1 CopyOnWriteArrayList 的特点

3.2 CopyOnWriteArrayList 的结构办法

3.3 CopyOnWriteArrayList 的写办法

3.4 CopyOnWriteArrayList 的读取办法

3.5 CopyOnWriteArrayList 的迭代器

3.6 CopyOnWriteArraySet 的序列化进程

3.7 CopyOnWriteArraySet 的 clone() 进程

4. CopyOnWriteArraySet 源码剖析

4.1 CopyOnWriteArraySet 的结构办法

4.2 CopyOnWriteArraySet 的操作办法

5. 总结

版权声明

作者信息

推广

Java 数据结构：CopyOnWriteArrayList 是如何保证线程安全的？

前语

1. 回忆 ArrayList

2. CopyOnWriteArrayList 的特点

3. CopyOnWriteArrayList 源码剖析

3.1 CopyOnWriteArrayList 的特点

3.2 CopyOnWriteArrayList 的结构办法

3.3 CopyOnWriteArrayList 的写办法

3.4 CopyOnWriteArrayList 的读取办法

3.5 CopyOnWriteArrayList 的迭代器

3.6 CopyOnWriteArraySet 的序列化进程

3.7 CopyOnWriteArraySet 的 clone() 进程

4. CopyOnWriteArraySet 源码剖析

4.1 CopyOnWriteArraySet 的结构办法

4.2 CopyOnWriteArraySet 的操作办法

5. 总结

版权声明

相关文章

《吐血整理》10种延迟任务的实现方式汇总！附详细代码（强烈推荐）

Compose跨平台第一弹：体验Compose for Desktop

演进实录｜不同阶段的企业如何搭建监控体系？

并发与保护详解（理论篇）

作者信息

推广