Java 线程总结(八)

Java 线程总结(八) —— 写时拷贝的 List 和 Set

1、Java 并发包中的容器类。注意这个是并发容器，要跟 Collections 返回的同步容器区分开。这里主要学习 CopyOnWriteArrayList 和 CopyOnWriteArraySet 这两个类，Copy-On-Write，即写时拷贝或写时复制，这是解决并发问题的一种重要思路。

2、CopyOnWriteArrayList 基本用法
CopyOnWriteArrayList 实现了 List 接口，它的用法与其他 List 如 ArrayList 基本是一样的，它的区别是：

它是线程安全的，可以被多个线程并发访问。

它的迭代器不支持修改操作，但也不会抛出 ConcurrentModificationException。

它直接以原子方式支持一些复合操作。

3、基于 synchronized 的同步容器迭代时，需要对整个列表对象加锁，否则会抛出 ConcurrentModificationException。但 CopyOnWriteArrayList 没有这个问题，迭代时不需要加锁。因为 CopyOnWriteArrayList 的迭代器根本不支持修改，这也是 CopyOnWriteArrayList 思想的本质，写时拷贝，CopyOnWriteArrayList 有点像 String，一旦创建，内容不可变，变的只是引用。

在 JDK 1.8 之前的实现中，CopyOnWriteArrayList 的迭代器不支持修改操作，也不支持一些依赖迭代器修改方法的操作，比如 Collections 的 sort 方法，因为 Collections.sort 方法依赖迭代器的 set 方法。但是在 JDK 1.8 中，List 接口增加了 sort 方法，并提供了默认实现，而 CopyOnWriteArrayList 重写了该实现，从以下其源码可以看出，加锁了。

public void sort(Comparator<? super E> c) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        Object[] newElements = Arrays.copyOf(elements, elements.length);
        @SuppressWarnings("unchecked") E[] es = (E[])newElements;
        Arrays.sort(es, c);
        setArray(newElements);
    } finally {
        lock.unlock();
    }
}

基于 synchronized 的同步容器的一个问题是复合操作，比如先检查再更新，也需要调用方加锁，而 CopyOnWriteArrayList 直接支持两个原子方法，其本质都是加锁了。

// 不存在才添加，如果添加了，返回 true，否则返回 false
public boolean addIfAbsent(E e)
// 批量添加 c 中的非重复元素，不存在才添加，返回实际添加的个数
public int addAllAbsent(Collection<? extends E> c)

4、CopyOnWriteArrayList 的基本原理
CopyOnWriteArrayList 的内部也是一个数组，但这个数组是以原子方式被整体更新的。每次修改操作，都会新建一个数组，复制原数组的内容到新数组，在新数组上进行需要的修改，然后以原子方式设置内部的数组引用，这就是写时拷贝。

所有的读操作，都是先拿到当前引用的数组，然后直接访问该数组，在读的过程中，可能内部的数组引用已经被修改了，但不会影响读操作，它依旧访问原数组内容。即数组内容是只读的，写操作都是通过新建数组，然后原子性的修改数组引用来实现的。

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    // 内部数组，注意，它声明为了 volatile，这是必需的，保证内存可见性，写操作更改了之后，读操作能看到。
    private transient volatile Object[] array;

    final transient ReentrantLock lock = new ReentrantLock();

    final Object[] getArray() {
        return array;
    }    
    final void setArray(Object[] a) {
        array = a;
    }  
    // 默认构造方法  
    public CopyOnWriteArrayList() {
        setArray(new Object[0]);
    }    
}

在 CopyOnWriteArrayList 中，读不需要锁，可以并行，读和写也可以并行，但多个线程不能同时写，每个写操作都需要先获取锁，CopyOnWriteArrayList 内部使用 ReentrantLock。

5、add() 方法源码解析

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);
        newElements[len] = e;
        // 调用 setArray 原子性的修改内部数组引用
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

解析为什么 add() 方法需要加锁？内部数组 array 是被 volatile 关键字修饰的，其内存可见性是不存在问题的，但是却存在另一个问题 —— 竞态条件，所以通过加锁来解决并发写时的竞态条件问题。此处加锁的目的就是为了解决竞态条件问题。

6、indexOf() 方法源码解析

public int indexOf(Object o) {
    Object[] elements = getArray();
    return indexOf(o, elements, 0, elements.length);
}
-----------------------------
// 这个 indexOf 方法访问的所有数据都是通过参数传递进来的，数组内容也不会被修改，不存在并发问题
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;
}

7、iterator() 迭代器方法源码解析

public Iterator<E> iterator() {
    // COWIterator 是内部类，传递给它的是不变的数组，它也只是读该数组，不支持修改
    return new COWIterator<E>(getArray(), 0);
}
-------------------
static final class COWIterator<E> implements ListIterator<E> {
    /** Snapshot of the array */
    // final 修饰，表明数组的引用不可变，而写时拷贝的特性，表明数组一旦被创建其内容不会再变，所以该数组是不可变的
    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;
    }
}

8、CopyOnWriteArrayList 小结
每次修改都创建一个新数组，然后复制所有内容，如果数组比较大，修改操作又比较频繁，CopyOnWriteArrayList 的性能是很低的。CopyOnWriteArrayList 不适用于数组很大，且修改频繁的场景。它是以优化读操作为目标的，读不需要同步，性能很高，但在优化读的同时就牺牲了写的性能。

保证线程安全的两种思路，一种是锁，使用 synchronized 或 ReentrantLock，另外一种是循环 CAS，写时拷贝体现了保证线程安全的另一种思路。对于绝大部分访问都是读，且有大量并发线程要求读，只有个别线程进行写，且只是偶尔写的场合，这种写时拷贝就是一种很好的解决方案。

写时拷贝是一种重要的思维，用于各种计算机程序中，比如经常用于操作系统内部的进程管理和内存管理。

9、CopyOnWriteArraySet 实现了 Set 接口，不包含重复元素，内部，它是通过 CopyOnWriteArrayList 实现的。

public class CopyOnWriteArraySet<E> extends AbstractSet<E>
        implements java.io.Serializable {
    // 内部实现依赖 CopyOnWriteArrayList      
    private final CopyOnWriteArrayList<E> al;

    public CopyOnWriteArraySet() {
        al = new CopyOnWriteArrayList<E>();
    }    

    // 调用了 CopyOnWriteArrayList 的 addIfAbsent 方法
    public boolean add(E e) {
        return al.addIfAbsent(e);
    }    
}

由于 CopyOnWriteArraySet 是基于 CopyOnWriteArrayList 实现的，所以与 Set 的实现类如 HashSet/TreeSet 相比，它的性能比较低，不适用于元素个数特别多的集合。如果元素个数比较多，可以考虑 ConcurrentHashMap 或 ConcurrentSkipListSet。

ConcurrentHashMap 与 HashMap 类似，适用于不要求排序的场景，ConcurrentSkipListSet 与 TreeSet 类似，适用于要求排序的场景。Java 并发包中没有与 HashSet 对应的并发容器，但可以很容易的基于 ConcurrentHashMap 构建一个，利用 Collections.newSetFromMap 方法即可。

参考博客

Java 编程的逻辑 - 写时拷贝的 List 和 Set