CopyOnWriteArrayList源码解读——CopyOnWrite思想的利与弊

秒速五厘米 2022-12-30 03:48 192阅读 0赞

更多JUC源码解读系列文章请持续关注[JUC源码解读文章目录JDK8][JUC_JDK8]！

--------------------

### 文章目录 ###

*   *  一、前言
     *  二、何为CopyOnWrite
     *  三、源码分析
     *   *  1、add(E e)添加元素
         *  2、add(int index, E element)在指定位置添加元素
         *  3、set(int index, E element)替换指定位置元素
         *  4、addIfAbsent(E e)添加元素时判断元素是否存在
         *  5、remove(int index)删除指定位置元素
         *  6、remove(Object o)通过元素值删除元素
         *  7、COWIterator迭代器没有\`fail-fast\`检查
     *  四、CopyOnWrite利与弊
     *  五、总结

## 一、前言 ##

`CopyOnWriteArrayList`作为并发容器集合，在窥探其原理之前，先想想，倘若让我们自己来开发一个并发集合，该如何设计？

加`synchronized`？加`ReentrantLock`？在哪加？如何加？

为确保线程安全，在读和写操作的方法上都加上`synchronized`或者`ReentrantLock`，保证在多线程情况下，只有一个线程访问集合。显而易见，读写互斥，读读互斥，写写互斥，性能极其低下，例如老牌并发集合`java.util.Vector`，`java.util.Collections#synchronizedCollection(java.util.Collection<T>)`，都是在读写方法上加了锁。

再者，加读写锁`ReadWriteLock`，读操作加读锁`ReadLock`，写操作加写锁`WriteLock`，读读不互斥，性能上有所提高，但是读写依然互斥，在读多写少的场景，大量的读势必会被一个写阻塞，从而影响性能。

## 二、何为CopyOnWrite ##

对于并发容器集合，`CopyOnWriteArrayList`有更优的解决方案：

`CopyOnWriteArrayList`利用`CopyOnWrite`思想，即在写时复制一份副本进行修改，修改完成后，再将新值赋值给旧值，为保证线程安全，需要在所有的写操作加悲观锁或者乐观锁，而读操作不必加锁，这就使得读写分离，读读不互斥，读写不互斥，空间换时间，性能大大提升。

## 三、源码分析 ##

public class CopyOnWriteArrayList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable { 
        private static final long serialVersionUID = 8673264195747942595L;
    
        /** The lock protecting all mutators */
        final transient ReentrantLock lock = new ReentrantLock();
    
        /** The array, accessed only via getArray/setArray. */
        private transient volatile Object[] array;
        
        ... ... 
    }

`CopyOnWriteArrayList`两个重要的成员变量`lock`和`array`，`lock`为写操作加锁，`array`数组被`volatile`修饰，通过`volatile`的语义write happen-before read，使得在多线程场景下，一线程修改数组可立即通知其他线程数组已修改，获取最新值。

读操作一律没有加锁，所有的写操作加了锁，`CopyOnWrite`的思想也是在写操作中，故而只截取部分写操作的源码进行分析。

### 1、add(E e)添加元素 ###

add添加元素操作贯彻`CopyOnWrite`思想，先复制一份数组到新数组，将元素加到新数组，然后将新数组赋值给旧数组。

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

### 2、add(int index, E element)在指定位置添加元素 ###

如何在指定位置添加元素呢？通过`index`将原数组分成两半复制：

*  先从0开始复制旧数组`index`个元素到新数组的0至`index-1`位置。
 *  然后从index复制旧数组`numMoved（len - index）`个元素到新数组的index+1至最后位置。
 *  新数组空出的`index`位置，放置新元素。
 *  最后将新数组赋值给旧数组。

在`index`位置添加新元素，二次复制，相当于旧数组从`index`位开始元素纷纷向后移动一位。

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)
                // numMoved=0 即是在数组的最后加入element
                newElements = Arrays.copyOf(elements, len + 1);
            else { 
                newElements = new Object[len + 1];
                // elements 从0开始拷贝元素至 newElements（从0开始），length=index
                System.arraycopy(elements, 0, newElements, 0, index);
                // elements 从index开始拷贝元素至 newElements（从index+1开始），length=numMoved
                System.arraycopy(elements, index, newElements, index + 1,
                                 numMoved);
            }
            // newElements的index位置留给新元素element
            newElements[index] = element;
            // newElements 赋值给 旧数组array
            setArray(newElements);
        } finally { 
            lock.unlock();
        }
    }

### 3、set(int index, E element)替换指定位置元素 ###

*  找到旧元素指定位置的元素与新元素比较，不相等则复制替换。
 *  新旧元素相等，则不替换，但是也要进行`setArray`赋值操作，为的是确保`volatile`写语意。

public E set(int index, E element) { 
        final ReentrantLock lock = this.lock;
        lock.lock();
        try { 
            Object[] elements = getArray();
            E oldValue = get(elements, index);
    
            // oldValue和element不相等，进行替换
            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
                // 二者相等，不是完全没有操作;确保volatile写语义，volatile write happen before read
                setArray(elements);
            }
            return oldValue;
        } finally { 
            lock.unlock();
        }
    }

### 4、addIfAbsent(E e)添加元素时判断元素是否存在 ###

`addIfAbsent(E e)`操作是两个操作，先判断数组中是否有新元素，有则返回false不添加，无则继续添加逻辑。添加逻辑是有锁线程安全的，而判断元素是否存在是不安全的，如何保证这两个操作加起来线程安全呢？答案是`double check`！

在单例模式-懒汉式中`double check`思想非常典型，先查该单例是否存在，存在直接返回，不存在，加锁，二次判断单例是否存在，存在则返回，不存在则新建赋值。

`addIfAbsent(E e)`运用了同样的思想：

*  首先获取原数组快照，判断新增元素是否存在，存在则返回false。（first check）
 *  新增元素不存在，则继续添加逻辑`addIfAbsent(e, snapshot)`。
 *  `addIfAbsent(e, snapshot)`方法是加锁的，获取锁后首先判断当前数组和快照是否相等，相等则说明数组没有改动，可以直接进行新增元素的操作。如果有修改，则需要判断当前数组中是否有新增元素，有则返回false，无则新增。（second check）

public boolean addIfAbsent(E e) { 
        // 获取数组快照
        Object[] snapshot = getArray();
        return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false :
            addIfAbsent(e, snapshot);
    }
    private boolean addIfAbsent(E e, Object[] snapshot) { 
        final ReentrantLock lock = this.lock;
        lock.lock();
        try { 
            Object[] current = getArray();
            int len = current.length;
            // 快照与当前数组比较，double-check，
            // 这里1.7和1.8不同，1.8对1.6进行了优化
            // 看源码时需要对比不同版本的差异
            if (snapshot != current) { 
                // 数组可能已经被修改，
                // Optimize for lost race to another addXXX operation
                // remove common=len
                // add common=snapshot.length 先检查current中前snapshot.length个，然后检查新增的
                int common = Math.min(snapshot.length, len);
                for (int i = 0; i < common; i++)
                    if (current[i] != snapshot[i] && eq(e, current[i]))
                        return false;
                if (indexOf(e, current, common, len) >= 0)
                        return false;
            }
            Object[] newElements = Arrays.copyOf(current, len + 1);
            newElements[len] = e;
            setArray(newElements);
            return true;
        } finally { 
            lock.unlock();
        }
    }

注意：java1.8之前的`addIfAbsent(E e)`和java8之后的代码有些许不同，以下摘自java7源码，java7中`addIfAbsent(E e)`并没有使用快照和`double check`的思想，而是直接将两个操作加锁，虽然保证了线程安全，但是因为方法一上来就加锁，性能比较。

所以java8中对其进行了优化，加了`double check`思想，第一次判断元素要是在数组中就不进行添加操作，也就不会加锁；而第二次判断，是先判断快照地址和当前数组地址，地址判断当然比遍历数组性能要高了。

public boolean addIfAbsent(E e) { 
            final java.util.concurrent.locks.ReentrantLock lock = this.lock;
            lock.lock();
            try { 
                // Copy while checking if already present.
                // This wins in the most common case where it is not present
                Object[] elements = getArray();
                int len = elements.length;
                Object[] newElements = new Object[len + 1];
                for (int i = 0; i < len; ++i) { 
                    if (eq(e, elements[i]))
                        return false; // exit, throwing away copy
                    else
                        newElements[i] = elements[i];
                }
                newElements[len] = e;
                setArray(newElements);
                return true;
            } finally { 
                lock.unlock();
            }
    }

### 5、remove(int index)删除指定位置元素 ###

删除中间位置的元素，需要将index后面的元素前移填补空缺，同样使用分两半复制的方式达到删除元素并前移的效果。

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)
                // numMoved == 0 即是删除数组的最后一个元素，则不需要移动其他元素。
                setArray(Arrays.copyOf(elements, len - 1));
            else { 
                // 新数组 length= len-1
                Object[] newElements = new Object[len - 1];
                System.arraycopy(elements, 0, newElements, 0, index);
                // 丢掉旧数组index位置的元素，达到删除的效果
                System.arraycopy(elements, index + 1, newElements, index,
                                 numMoved);
                setArray(newElements);
            }
            return oldValue;
        } finally { 
            lock.unlock();
        }
    }

### 6、remove(Object o)通过元素值删除元素 ###

通过元素值删除元素，需要先查询数组中是否有该元素，无则不做操作，有则继续走删除逻辑，同样使用了`double check`的思想。

public boolean remove(Object o) { 
        // 获取旧数组快照
        Object[] snapshot = getArray();
        // 判断需要删除的元素是否在数组中，不在则直接返回false，是则继续删除操作
        int index = indexOf(o, snapshot, 0, snapshot.length);
        return (index < 0) ? false : remove(o, snapshot, index);
    }
    
    private boolean remove(Object o, Object[] snapshot, int index) { 
        final ReentrantLock lock = this.lock;
        lock.lock();
        try { 
            Object[] current = getArray();
            int len = current.length;
            // double check
            // 快照与当前数组进行比较，不相等说明数组已经被其他线程修改
            if (snapshot != current) findIndex: { 
                int prefix = Math.min(index, len);
                // 遍历查找当前数组中是否有需要删除的元素
                for (int i = 0; i < prefix; i++) { 
                    if (current[i] != snapshot[i] && eq(o, current[i])) { 
                        index = i;
                        // 有则结束判断
                        break findIndex;
                    }
                }
                // 上面找了一遍没有找到
                // index >= len 说明上面查找的是当前整个数组，需要删除的元素已经被修改
                if (index >= len)
                    return false;
                // 当前数组变长了，current index位置的元素依然是需要删除的元素，停止判断
                if (current[index] == o)
                    break findIndex;
                // 走到这了数组变长了，index位置的元素也已经被删除，但是不代表其他线程新增的元素没有需要删除的元素，继续判断
                index = indexOf(o, current, index, len);
                if (index < 0)
                    return false;
            }
            // 新数组长度减一
            Object[] newElements = new Object[len - 1];
            // 从0开始复制旧数组index个元素到新数组的0至index-1位置
            System.arraycopy(current, 0, newElements, 0, index);
            // 跳过index，从index+1复制旧数组剩下的元素到新数组的index至最后的位置。
            System.arraycopy(current, index + 1,
                             newElements, index,
                             len - index - 1);
            // 新数组赋值给旧数组
            setArray(newElements);
            return true;
        } finally { 
            lock.unlock();
        }
    }

### 7、COWIterator迭代器没有`fail-fast`检查 ###

例如`ArrayList`在迭代器遍历想删除元素，只能使用迭代器的删除方法，而使用外部`ArrayList`删除方法会抛`ConcurrentModificationException`异常，为什么呢？

因为`ArrayList`成员变量维护了一个`modCount`，每次修改操作都会`modCount++`，而迭代器中也维护了一个`expectedModCount`，新建迭代器时`modCount`赋值给`expectedModCount`，在迭代器遍历时会检查`modCount != expectedModCount`，不相等则抛出`ConcurrentModificationException`，在迭代器遍历中调用迭代器外部的修改方法只会更新`modCount`，不会更新迭代器的`expectedModCount`，而迭代器内部提供的修改方法既更新了`modCount`，同时也将最新的`modCount`值赋值给`expectedModCount`。

然而这个限制在`COWIterator`中不存在！在使用`COWIterator`迭代器遍历时可以调用外部的修改方法，不会抛出异常。这是因为`COWIterator`迭代器中复制了一份原数组副本，外部修改数组只是修改了原数组，并不会影响迭代器中正在遍历的数组。

同时`COWIterator`迭代器也不支持调用迭代器内部的修改方法，全都会抛出`UnsupportedOperationException`。

如下摘取`COWIterator`部分源码：

static final class COWIterator<E> implements ListIterator<E> { 
        /** Snapshot of the array */
        private final Object[] snapshot;
        /** Index of element to be returned by subsequent call to next. */
        private int cursor;
        /** * Not supported. Always throws UnsupportedOperationException. * @throws UnsupportedOperationException always; {@code remove} * is not supported by this iterator. */
        public void remove() { 
            throw new UnsupportedOperationException();
        }
    
        /** * Not supported. Always throws UnsupportedOperationException. * @throws UnsupportedOperationException always; {@code set} * is not supported by this iterator. */
        public void set(E e) { 
            throw new UnsupportedOperationException();
        }
    
        /** * Not supported. Always throws UnsupportedOperationException. * @throws UnsupportedOperationException always; {@code add} * is not supported by this iterator. */
        public void add(E e) { 
            throw new UnsupportedOperationException();
        }
    
        @Override
        public void forEachRemaining(Consumer<? super E> action) { 
            Objects.requireNonNull(action);
            Object[] elements = snapshot;
            final int size = elements.length;
            for (int i = cursor; i < size; i++) { 
                @SuppressWarnings("unchecked") E e = (E) elements[i];
                action.accept(e);
            }
            cursor = size;
        }
    }

既然`COWIterator`迭代器中遍历的数组是一个副本，修改原数组也不会影响到副本，这就出现一个问题：数据的实时一致性。

## 四、CopyOnWrite利与弊 ##

`CopyOnWrite`利用写时复制副本加锁修改，而读不加锁的思想达到读写分离的效果，以空间换时间，提升性能。而其弊端也正是其思想的体现：

*  内存占用问题：`CopyOnWrite`因为复制副本所以双倍占用内存，可能造成频繁的Yong GC和Full GC。（利用`CopyOnWrite`机制更新大对象需要注意）
 *  数据一致性问题：`CopyOnWrite`只保证了数据最终一致性，数据的实时一致性不能保证，所以读数据可能会有一定的延迟。

缺陷决定了`CopyOnWriteArrayList`使用场景的局限性，`CopyOnWriteArrayList`适合读多写少，复制数据对象不宜过大的场景。

## 五、总结 ##

*  `CopyOnWrite`是一个不错的解决并发安全的思路，在很多开源项目中都有用到类似复制写的思想。
 *  `CopyOnWrite`利用写时复制副本加锁修改，而读不加锁的思想达到读写分离的效果，以空间换时间，提升性能。
 *  `CopyOnWrite`缺陷明显，内存占用问题和数据一致性问题。
 *  `CopyOnWriteArrayList`适合读多写少的场景。
 *  `addIfAbsent` java8中对java7做了优化，使用`double check`的思想保证线程安全。
 *  `COWIterator`迭代器不支持调用迭代器内部修改方法，在`COWIterator`迭代器遍历时因为是遍历副本，所有调用外部修改方法也不会报错，但是也不会读取到最新值。
 *  在使用`CopyOnWriteArrayList`添加、删除元素时，尽量使用`addAll`和`removeAll`批量新增和批量删除操作，因为频繁的复制数组降低性能，同时占用内存，可能会导致频繁gc。

参考：

*  [https://segmentfault.com/a/1190000019787913][https_segmentfault.com_a_1190000019787913]
 *  [https://blog.csdn.net/u013452337/article/details/90238052][https_blog.csdn.net_u013452337_article_details_90238052]

PS: **如若文章中有错误理解，欢迎批评指正，同时非常期待你的评论、点赞和收藏。我是徐同学，愿与你共同进步！**

[JUC_JDK8]: https://stefan.blog.csdn.net/article/details/108934432
[https_segmentfault.com_a_1190000019787913]: https://segmentfault.com/a/1190000019787913
[https_blog.csdn.net_u013452337_article_details_90238052]: https://blog.csdn.net/u013452337/article/details/90238052