从CopyOnWriteArrayList的面试题和源码说优缺点和使用场景

JAVA herman 396浏览
公告:“业余草”微信公众号提供免费CSDN下载服务(只下Java资源),关注业余草微信公众号,添加作者微信:xmtxtt,发送下载链接帮助你免费下载!
本博客日IP超过1800,PV 2600 左右,急需赞助商。
极客时间所有课程通过我的二维码购买后返现24元微信红包,请加博主新的微信号:xttblog,之前的微信号好友位已满,备注:返现
所有面试题(java、前端、数据库、springboot等)一网打尽,请关注文末小程序

CopyOnWriteArrayList 是一个并发容器。有很多人称它是线程安全的,我认为这句话不严谨,缺少一个前提条件,那就是非复合场景下操作它是线程安全的。

Copy-On-Write 简称 COW,是一种用于程序设计中的优化策略。其基本思路是,从一开始大家都在共享同一个内容,当某个人想要修改这个内容的时候,才会真正把内容 Copy 出去形成一个新的内容然后再改,这是一种延时懒惰策略。

CopyOnWriteArrayList 你都不知道,还怎么拿 Offer

Java 并发包提供了很多线程安全的集合,有了他们的存在,使得我们在多线程开发下,大大简化了多线程开发的难度,但是如果不知道其中的原理,可能会引发意想不到的问题,所以知道其中的原理还是很有必要的。

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

下面我们看看它的 add 方法的源码:

public boolean add(E e) {
    //1.获得独占锁
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();//2.获得Object[]
        int len = elements.length;//3.获得elements的长度
        Object[] newElements = Arrays.copyOf(elements, len + 1);//4.复制到新的数组
        newElements[len] = e;//5.将add的元素添加到新元素
        setArray(newElements);//6.替换之前的数据
        return true;
    } finally {
        lock.unlock();//7.释放独占锁
    }
}
final Object[] getArray() {
    return array;
}

CopyOnWrite 的名字就是这样来的。在写的时候,先 copy 一个,操作新的对象。然后在覆盖旧的对象,保证 volatile 语义。

看完这个源码后,我们来看几个常见的面试题。

CopyOnWriteArrayList 有什么优点?

读写分离,适合写少读多的场景。使用了独占锁,支持多线程下的并发写。

CopyOnWriteArrayList 是如何保证写时线程安全的?

因为用了 ReentrantLock 独占锁,保证同时只有一个线程对集合进行修改操作。

CopyOnWrite 怎么理解?

写时复制。就是在写的时候,先 copy 一个,操作新的对象。然后在覆盖旧的对象,保证 volatile 语义。新数组的长度等于旧数组的长度 + 1。

从 add 方法的源码中你可以看出  CopyOnWriteArrayList 的缺点是什么?

占用内存,写时 copy 效率低。因为 CopyOnWrite 的写时复制机制,所以在进行写操作的时候,内存里会同时驻扎两个对象的内存,旧的对象和新写入的对象(注意:在复制的时候只是复制容器里的引用,只是在写的时候会创建新对象添加到新容器里,而旧容器的对象还在使用,所以有两份对象内存)。如果这些对象占用的内存比较大,比如说 200M 左右,那么再写入 100M 数据进去,内存就会占用 300M,那么这个时候很有可能造成频繁的 Yong GC 和 Full GC。

get 的源码分析。

public E get(int index) {
    return get(getArray(), index);
}
final Object[] getArray() {
    return array;
}

get 方法很简单。但是会出现一个很致命的问题,那就是一致性问题。

当我们获得了 array 后,由于整个 get 方法没有独占锁,所以另外一个线程还可以继续执行修改的操作,比如执行了 remove 的操作,remove 和 add 一样,也会申请独占锁,并且复制出新的数组,删除元素后,替换掉旧的数组。而这一切 get 方法是不知道的,它不知道 array 数组已经发生了天翻地覆的变化。就像微信一样,虽然对方已经把你给删了,但是你不知道。这就是一个一致性问题。

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

set 方法解读。

public E set(int index, E element) {
    //(1)获得独占锁
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();//(2)获得array
        E oldValue = get(elements, index);//(3)根据下标,获得旧的元素

        if (oldValue != element) {//(4)如果旧的元素不等于新的元素
            int len = elements.length;//(5)获得旧数组的长度
            Object[] newElements = Arrays.copyOf(elements, len);//(6)复制出新的数组
            newElements[index] = element;//(7)修改
            setArray(newElements);//(8)替换
        } else {
            //(9)为了保证volatile 语义,即使没有修改,也要替换成新的数组
            // Not quite a no-op; ensures volatile write semantics
            setArray(elements);
        }
        return oldValue;
    } finally {
        lock.unlock();//(10)释放独占锁
    }
}

上面的代码,我写的都有注释,相信大家都能看明白。

set 的时候,同样的会获得一个独占锁,来保证写的线程安全。修改操作,实际上操作的是 array 的一个副本,最后才把 array 给替换掉。所以,修改和 add 很相似。set、add、remove 是互斥的。

remove 方法解读。

public E remove(int index) {
    final ReentrantLock lock = this.lock;//获得独占锁
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;// 旧数组的长度
        E oldValue = get(elements, index);
        int numMoved = len - index - 1;
        if (numMoved == 0)//判断是否是删除数组尾部的最后一个元素
            //则复制出一个长度为【旧数组的长度-1】的新数组
            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);
        }
        return oldValue;
    } finally {
        lock.unlock();
    }
}

研究 java 自带的一些数据结构,你会发现设计的都很巧妙。大师就是大师啊。

迭代器的主要源码如下:

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

调用 iterator 方法获取迭代器,内部会调用 COWIterator 的构造方法,此构造方法有两个参数,第一个参数就是 array 数组,第二个参数是下标,就是 0。随后构造方法中会把 array 数组赋值给snapshot变量。snapshot 是“快照”的意思,如果 Java 基础尚可的话,应该知道数组是引用类型,传递的是指针,如果有其他地方修改了数组,这里应该马上就可以反应出来,那为什么又会是 snapshot这样的命名呢?没错,如果其他线程没有对 CopyOnWriteArrayList 进行增删改的操作,那么 snapshot 就是本身的 array,但是如果其他线程对 CopyOnWriteArrayList 进行了增删改的操作,旧的数组会被新的数组给替换掉,但是 snapshot 还是原来旧的数组的引用。也就是说 当我们使用迭代器便利 CopyOnWriteArrayList 的时候,不能保证拿到的数据是最新的,这也是一致性问题。

CopyOnWriteArrayList 的使用场景

通过源码分析,我们看出它的优缺点比较明显,所以使用场景也就比较明显。就是合适读多写少的场景。

CopyOnWriteArrayList 的缺点

  1. 由于写操作的时候,需要拷贝数组,会消耗内存,如果原数组的内容比较多的情况下,可能导致 young gc 或者 full gc。
  2. 不能用于实时读的场景,像拷贝数组、新增元素都需要时间,所以调用一个 set 操作后,读取到数据可能还是旧的,虽然CopyOnWriteArrayList 能做到最终一致性,但是还是没法满足实时性要求。
  3. 由于实际使用中可能没法保证 CopyOnWriteArrayList 到底要放置多少数据,万一数据稍微有点多,每次 add/set 都要重新复制数组,这个代价实在太高昂了。在高性能的互联网应用中,这种操作分分钟引起故障。

CopyOnWriteArrayList 的设计思想

  1. 读写分离,读和写分开
  2. 最终一致性
  3. 使用另外开辟空间的思路,来解决并发冲突

史上最牛逼的 Java 个人简历

以上内容希望能够在面试或者工作中帮助到大家!

业余草公众号

最后,欢迎关注我的个人微信公众号:业余草(yyucao)!可加QQ1群:135430763(2000人群已满),QQ2群:454796847(已满),QQ3群:187424846(已满)。QQ群进群密码:xttblog,想加微信群的朋友,之前的微信号好友已满,请加博主新的微信号:xttblog,备注:“xttblog”,添加博主微信拉你进群。备注错误不会同意好友申请。再次感谢您的关注!后续有精彩内容会第一时间发给您!原创文章投稿请发送至532009913@qq.com邮箱。商务合作可添加助理微信进行沟通!

本文原文出处:业余草: » 从CopyOnWriteArrayList的面试题和源码说优缺点和使用场景