聊聊并发-Java中的Copy-On-Write容器

Copy-On-Write简称COW,是一种用于程序设计中的优化策略。其基本思路是,从一开始大家都在共享同一个内容,当某个人想要修改这个内容的时候,才会真正把内容Copy出去形成一个新的内容然后再改,这是一种延时懒惰策略。从JDK1.5开始Java并发包里提供了两个使用CopyOnWrite机制实现的并发容器,它们是CopyOnWriteArrayList和CopyOnWriteArraySet。CopyOnWrite容器非常有用,可以在非常多的并发场景中使用到。

什么是CopyOnWrite容器

CopyOnWrite容器即写时复制的容器。通俗的理解是当我们往一个容器添加元素的时候,不直接往当前容器添加,而是先将当前容器进行Copy,复制出一个新的容器,然后新的容器里添加元素,添加完元素之后,再将原容器的引用指向新的容器。这样做的好处是我们可以对CopyOnWrite容器进行并发的读,而不需要加锁,因为当前容器不会添加任何元素。所以CopyOnWrite容器也是一种读写分离的思想,读和写不同的容器。

CopyOnWriteArrayList的实现原理

在使用CopyOnWriteArrayList之前,我们先阅读其源码了解下它是如何实现的。以下代码是向ArrayList里添加元素,可以发现在添加的时候是需要加锁的,否则多线程写的时候会Copy出N个副本出来。

public boolean add(T 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();

    }

}

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

读的时候不需要加锁,如果读的时候有多个线程正在向ArrayList添加数据,读还是会读到旧的数据,因为写的时候不会锁住旧的ArrayList。

public E get(int index) {
    return get(getArray(), index);
}

JDK中并没有提供CopyOnWriteMap,我们可以参考CopyOnWriteArrayList来实现一个,基本代码如下:


import java.util.Collection;
import java.util.Map;
import java.util.Set;

public class CopyOnWriteMap<K, V> implements Map<K, V>, Cloneable {
    private volatile Map<K, V> internalMap;

    public CopyOnWriteMap() {
        internalMap = new HashMap<K, V>();
    }

    public V put(K key, V value) {

        synchronized (this) {
            Map<K, V> newMap = new HashMap<K, V>(internalMap);
            V val = newMap.put(key, value);
            internalMap = newMap;
            return val;
        }
    }

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

    public void putAll(Map<? extends K, ? extends V> newData) {
        synchronized (this) {
            Map<K, V> newMap = new HashMap<K, V>(internalMap);
            newMap.putAll(newData);
            internalMap = newMap;
        }
    }
}

实现很简单,只要了解了CopyOnWrite机制,我们可以实现各种CopyOnWrite容器,并且在不同的应用场景中使用。

CopyOnWrite的应用场景

CopyOnWrite并发容器用于读多写少的并发场景。比如白名单,黑名单,商品类目的访问和更新场景,假如我们有一个搜索网站,用户在这个网站的搜索框中,输入关键字搜索内容,但是某些关键字不允许被搜索。这些不能被搜索的关键字会被放在一个黑名单当中,黑名单每天晚上更新一次。当用户搜索时,会检查当前关键字在不在黑名单当中,如果在,则提示不能搜索。实现代码如下:

package com.ifeve.book;

import java.util.Map;

import com.ifeve.book.forkjoin.CopyOnWriteMap;

/**
 * 黑名单服务
 *
 * @author fangtengfei
 *
 */
public class BlackListServiceImpl {

    private static CopyOnWriteMap<String, Boolean> blackListMap = new CopyOnWriteMap<String, Boolean>(
            1000);

    public static boolean isBlackList(String id) {
        return blackListMap.get(id) == null ? false : true;
    }

    public static void addBlackList(String id) {
        blackListMap.put(id, Boolean.TRUE);
    }

    /**
     * 批量添加黑名单
     *
     * @param ids
     */
    public static void addBlackList(Map<String,Boolean> ids) {
        blackListMap.putAll(ids);
    }

}

代码很简单,但是使用CopyOnWriteMap需要注意两件事情:

1. 减少扩容开销。根据实际需要,初始化CopyOnWriteMap的大小,避免写时CopyOnWriteMap扩容的开销。

2. 使用批量添加。因为每次添加,容器每次都会进行复制,所以减少添加次数,可以减少容器的复制次数。如使用上面代码里的addBlackList方法。

CopyOnWrite的缺点

CopyOnWrite容器有很多优点,但是同时也存在两个问题,即内存占用问题和数据一致性问题。所以在开发的时候需要注意一下。

内存占用问题。因为CopyOnWrite的写时复制机制,所以在进行写操作的时候,内存里会同时驻扎两个对象的内存,旧的对象和新写入的对象(注意:在复制的时候只是复制容器里的引用,只是在写的时候会创建新对象添加到新容器里,而旧容器的对象还在使用,所以有两份对象内存)。如果这些对象占用的内存比较大,比如说200M左右,那么再写入100M数据进去,内存就会占用300M,那么这个时候很有可能造成频繁的Yong GC和Full GC。之前我们系统中使用了一个服务由于每晚使用CopyOnWrite机制更新大对象,造成了每晚15秒的Full GC,应用响应时间也随之变长。

针对内存占用问题,可以通过压缩容器中的元素的方法来减少大对象的内存消耗,比如,如果元素全是10进制的数字,可以考虑把它压缩成36进制或64进制。或者不使用CopyOnWrite容器,而使用其他的并发容器,如ConcurrentHashMap

数据一致性问题。CopyOnWrite容器只能保证数据的最终一致性,不能保证数据的实时一致性。所以如果你希望写入的的数据,马上能读到,请不要使用CopyOnWrite容器。

关于C++的STL中,曾经也有过Copy-On-Write的玩法,参见陈皓的《C++ STL String类中的Copy-On-Write》,后来,因为有很多线程安全上的事,就被去掉了。

原创文章,转载请注明: 转载自并发编程网 – ifeve.com本文链接地址: 聊聊并发-Java中的Copy-On-Write容器



方 腾飞

花名清英,并发网(ifeve.com)创始人,畅销书《Java并发编程的艺术》作者,蚂蚁金服技术专家。目前工作于支付宝微贷事业部,关注互联网金融,并发编程和敏捷实践。微信公众号aliqinying。
FavoriteLoading添加本文到我的收藏
  • Trackback are closed
  • Comments (17)
    • sqtds
    • 03/09. 2014 2:59pm

    本来很想点赞的,一直没发现点赞 的地方。。。

    • sunny_yk
    • 03/09. 2014 9:41pm

    1. 减少扩容开销。根据实际需要,初始化CopyOnWriteMap的大小,避免写时CopyOnWriteMap扩容的开销

    这点有点不理解,其实每次put的时候都会开辟一块全新的空间出来做copy,所以不存在在对原有内存空间的扩容,那么map的初始大小其实没啥用吧???

    • hint
    • 03/24. 2014 12:02pm

    没明白这个例子为什么一定要用copyOnWriteMap,直接用map会有什么问题吗?map的putall方法为什么不行?

    • Storm
    • 04/17. 2014 5:30pm

    对内存占用问题有些不同的看法。括号中的说明,开始说容器复制只是复制了对象的引用,最后却说两份对象内存。应该是有两份对象引用,而引用占用的空间是固定的,所以往CopyOnWriteArrayList里无论加大对象还是小对象,对于CopyOnWriteArrayList本身来说,产生垃圾的大小是一致的。频繁的GC只是因为频繁修改CopyOnWriteArrayList的数据造成的。

    • 是的。频繁的GC是因为修改CopyOnWriteArrayList里大量的元素造成的。两份对象内存是指修改前和修改后两个元素内存。

  1. 比如,如果元素全是10进制的数字,可以考虑把它压缩成36进制或64进制 这个压缩没太懂,再详细点?

    • iamliming
    • 04/17. 2015 5:59pm

    在方法里面
    transient final ReentrantLock lock = new ReentrantLock();
    public boolean add(T e) {
    final ReentrantLock lock = this.lock;
    lock.lock();

    }

    public boolean add(T e) {
    lock.lock();

    }
    有什么区别?

    • plx927
    • 08/13. 2015 10:59pm

    赞,写得很好!

    • dapeng
    • 05/25. 2016 3:38pm

    您好:
    关于“ 读的时候不需要加锁,如果读的时候有多个线程正在向CopyOnWriteArrayList添加数据,读还是会读到旧的数据,因为写的时候不会锁住旧的CopyOnWriteArrayList。”

    JDK文档上的说明:内存一致性效果:当存在其他并发 collection 时,将对象放入 CopyOnWriteArrayList 之前的线程中的操作 happen-before 随后通过另一线程从 CopyOnWriteArrayList 中访问或移除该元素的操作。

    按JDK说明,应该是不会读到脏数据的吧?

    • Lucifer
    • 11/28. 2016 9:21am

    写得不错,cow的精髓都解释出来了

    • Comple
    • 03/21. 2017 11:24am

    所以这里的COW的作用主要体现在写操作上,在写的时候会在一个副本上进行写,然后会被刷新到共享内存中。同时,为了保证最终的一致性,写操作是加锁的,这样不会有不一致的数据被刷新到共享内存中。所谓第二线程读到旧值,是指在某一线程在写,并且还未刷新到共享内存之前。

    • 雁过留影
    • 04/10. 2017 2:32pm

    文章中说:如果读的时候有多个线程正在向ArrayList添加数据,读还是会读到旧的数据,因为写的时候不会锁住旧的ArrayList。
    但是,如果一个线程在写(add)元素,当调用过setArray(newElements)后,这时候锁还没有释放,但是内部数据的引用已经变成新的数据了,另个线程来get,这时候,get到的就是新的数据了啊。我理解的没错吧

    • hehe
    • 05/26. 2017 11:44am

    请教一下, 为什么需要复制呢? 如果将array 数组设定为volitile的, 写操作加锁,读不加锁 是不是也可以满足需要呢 , 类似concurrentMap的单个桶的操作

      • whoiam8485
      • 10/27. 2017 3:00pm

      A slight complication of Java volatile fields, and one sometimes overlooked, is that declaring an array volatile does not give volatile access to its fields!. At least, it doesn’t when elements of the array are accessed with “normal” Java syntax. In other words:

      it is unsafe to call arr[x] = y on an array (even if declared volatile) in one thread and then expect arr[x] to return y from another thread;
      on the other hand, it is safe to call arr = new int[] (or whatever) and expect another thread to then read the new array as that referenced by arr: this is what is meant by declaring the array reference volatile.

You must be logged in to post a comment.

return top