Java 写时复制容器

Java

读多写少下场景下，快照避免读写冲突

原理

多线程下读写冲突

  • 一个线程遍历过程中，很可能其他线程有更改需求，遍历时长不固定，完全取决于外部逻辑控制，修改需求一直等待不现实
  • 一个线程写数据，多个读线程都要等待

解决方案是任何修改都会产生一个全新副本，重量级操作，适合读多写少场景

  1. 当一个线程遍历集合时，集合实际数据为A，遍历迭代器基于数据A引用
  2. 遍历过程中另一线程发起修改，数据A拷贝生成数据B，集合实际数据被替换为B
  3. 虽然集合数据变化，但是遍历迭代器依然基于数据A，即遍历无视后续集合变化，以发起遍历时刻为准
  4. 遍历过程中可能同时存在多个副本，结束后数据A被回收，集合持有数据B，集合永远持有最新的一份

CopyOnWriteArrayList

底层是一个普通数组外加一个重入锁

CopyOnWriteArrayList.java
1
2
3
4
5
6
7
public class CopyOnWriteArrayList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    final transient ReentrantLock lock = new ReentrantLock();

    //volatile快速感知变化
    private transient volatile Object[] array;
    //...
}

尾部增加比较直观，先上锁，分配新数组容量，完整拷贝后新值设到末尾

CopyOnWriteArrayList.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

指定位置插入稍微复杂一点，位置前后两段拷贝，再加上新元素拼合

CopyOnWriteArrayList.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public void add(int index, E element) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        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)
            //退化成尾部插入
            newElements = Arrays.copyOf(elements, len + 1);
        else {
            //新分配空间两段拷贝
            newElements = new Object[len + 1];
            System.arraycopy(elements, 0, newElements, 0, index);
            System.arraycopy(elements, index, newElements, index + 1, numMoved);
        }
        newElements[index] = element;
        setArray(newElements);
    } finally {
        lock.unlock();
    }
}

Set操作虽然不会造成数组容量变化，但是依然整体拷贝后替换

CopyOnWriteArrayList.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public E set(int index, E element) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        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);
        }
        return oldValue;
    } finally {
        lock.unlock();
    }
}

遍历使用的迭代器是基于创建时的底层数组，不受修改影响

CopyOnWriteArrayList.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public Iterator<E> iterator() {
    //传入创建时的底层数组引用，后续引用变化不受影响
    return new COWIterator<E>(getArray(), 0);
}

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;
    }

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

    @SuppressWarnings("unchecked")
    public E next() {
        if (! hasNext())
            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();
    }
    //...
}

普通读操作没有锁保护，因为array引用可能随时被替换，读不是直接在底层array上操作，而是先取array引用即拿到当前数组，后续再替换也无关，相当于一个固定操作

CopyOnWriteArrayList.java
1
2
3
public E get(int index) {
    return get(getArray(), index);
}

CopyOnWriteArraySet

完全基于CopyOnWriteArrayList实现，不同的是添加时保持无重复

CopyOnWriteArraySet.java
1
2
3
4
5
6
7
8
9
10
11
12
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);
    }
    //...
}

版权声明

This site by Linest is licensed under a Creative Commons BY-NC-ND 4.0 International License.
由Linest创作并维护的博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证。

本文永久链接：http://linest.github.io/2018/01/07/java-multithread-copy-on-write/