J.U.C并发框架之CopyOnWrite

发表于 | 分类于 | 阅读次数:
字数统计: 872 | 阅读时长 ≈ 4

本篇研究CopyOnWrite的实现原理，并为后续研究其它“写时复制”的问题进行预热。

更改键对应的值，也会在内部复制数组吗？存在数据一致性的问题吗？写时不复制不可以吗？这篇文章会解答诸如此类的问题。

按照惯例，先放出示例代码：

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
public class CopyOnWriteDemo {
    public static void main(String[] args) {
        Map cmap =new CopyOnWriteMap();
        cmap.put(1, "a");
        new Thread(() ->
        {
            cmap.put(1, "new a");
            System.out.println(cmap.get(1));
        }).start();
        System.out.println(cmap.get(1));
    }
}
class CopyOnWriteMap<K, V> extends HashMap<K, V> implements Cloneable {
    private volatile Map<K, V> internalMap;
    private final ReentrantLock lock = new ReentrantLock();
    public CopyOnWriteMap() {
        internalMap = new HashMap<K, V>();
    }
    public V put(K key, V value) {
        lock.lock();
        try {
            Map<K, V> newMap = new HashMap<K, V>(internalMap);
            Thread.sleep(3000);
            V val = newMap.put(key, value);
            internalMap = newMap;
            return val;
        } catch (InterruptedException e) {
            e.printStackTrace();
        } finally {
            lock.unlock();
        }
        return null;
    }
    public V get(Object key) {
        return internalMap.get(key);
    }
    public void putAll(Map<? extends K, ? extends V> newData) {
        lock.lock();
        try {
            Map<K, V> newMap = new HashMap<K, V>(internalMap);
            newMap.putAll(newData);
            internalMap = newMap;
        } finally {
            lock.unlock();
        }
    }
}

输出结果是：

1
2
a
new a

大约三秒后输出a，接着又过三秒输出new a。这个方法没有采用java的juc包提供的工具，是自己实现的一个CopyOnWriteMap容器。

主体思想

主题思想就是四个字：写时复制。

比如在上述程序中，读是直接返回内部维护的一个map，并未做更多的处理：

1
2
3
public V get(Object key) {
    return internalMap.get(key);
}

而在添加元素的时候，首先加锁，然后复制旧的map数据到新的map，对新的map添加键值对，操作完成后，将指向旧的map对象的指针指向新的map对象，最后释放锁。用代码描述就是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public V put(K key, V value) {
    lock.lock();
    try {
        Map<K, V> newMap = new HashMap<K, V>(internalMap);
        Thread.sleep(3000);
        V val = newMap.put(key, value);
        internalMap = newMap;
        return val;
    } catch (InterruptedException e) {
        e.printStackTrace();
    } finally {
        lock.unlock();
    }
    return null;
}

为了模拟延迟操作，添加了睡眠事件。

J.U.C的实现

框架提供了CopyOnWriteArrayList、CopyOnWriteArraySet，下面以CopyOnWriteArrayList为例进行探讨。

更改键对应的值，也会在内部复制数组吗？

CopyOnWriteArrayList用set更新：

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

所以，如果更新的value和原本旧的value相同，则不会复制新的数组，反之则会复制。

存在数据一致性的问题吗？

在示例中添加睡眠事件就是为了说明这个问题(虽然是自研容器，但是原理一样)。一言以蔽之：COW保证最终一致性，但是不保证实时一致。

写时不复制不可以吗？

容器在迭代的时候，不允许修改元素，否则会抛出异常，以ArrayList为例，它的迭代器内部有如下代码：

1
2
3
4
final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

而set add等方法中也都会添加判断rangeCheck(index);(这也可以进步一说明set内部复制数组的问题)。

所以写时进行复制是必要的。

优缺点及场景

前面已经分析了CopyOnWrite不能保证数据实时一致，同时，它在写的时候要开辟额外的存储空间。这就预示着，它比较适合：

  • 读多写少
  • 实时性要求不高
  • 扩容添加不频繁

小结

通过本篇分析，了解了CopyOnWrite的实现原理，并解决了一些小问题。