CopyOnWriteArrayList

作者: 星空怎样 | 来源:发表于2020-05-28 17:56 被阅读0次

[toc]

前言

CopyOnWriteArrayList是一个线程安全的集合，原理就是：在保证线程安全的前提下，牺牲掉写操作的效率来保证读操作的高效。所谓的CopyOnwrite就是通过赋值方式来完成对数据的修改，在进行修改的时候，复制一个新数组，在新数组上面进行修改操作，这样保证了不改变老数组，实现了读写分离，但是因为是通过复制方式对数据进行修改，所以不能保证数据实的实时性，只能保证最终的一致性。

定义

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {

在定义上和ArrayList的定义差不多，不在过多解释。

属性

/** The lock protecting all mutators */
//一把锁
transient final ReentrantLock lock = new ReentrantLock();

/** The array, accessed only via getArray/setArray. */
//一个对象数组，只从方法getArray/setArray处接受值
private volatile transient Object[] array;

lock属性是CopyOnWriteArrayList中的锁，通过lock对add()、set()、remove()等方法进行锁操作
array是CopyOnWriteArrayList存放数据的数组只能通过getArray/setArray处理值
注CopyOnWriteArrayList是没有size属性的因为不需要,因为每次修改都是拷贝一份正好可以存储目标个数的元素的数组，所以size=array.length，不像ArrayList数组长度实际要大于集合大小。

初始化

无参的构造方法

CopyOnWriteArrayList的初始容量是0。
无参的构造方法会调用setArray()，参数是一个空的数组，然后通过setArray把这个数组赋值给array

    public CopyOnWriteArrayList() {
        setArray(new Object[0]);
    }
    final void setArray(Object[] a) {
        array = a;
    }

使用另一个集合的Collection的构造方法

    public CopyOnWriteArrayList(Collection<? extends E> c) {
        //定义数组
        Object[] elements;
        if (c.getClass() == CopyOnWriteArrayList.class)
            //如果参数的类型恰好就是CopyOnWriteArrayList，那么直接将c强转成CopyOnWriteArrayList，然后在获取底层数组赋值到elements中
            elements = ((CopyOnWriteArrayList<?>)c).getArray();
        else {
            //参数不是CopyOnWriteArrayList
            elements = c.toArray();
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            //如果elements不是一个Object[]类型数组，那么就将原数组变为Object[]类型数组,如果是Object[]数组，那么不需要转换直接赋值即可
            if (elements.getClass() != Object[].class)
                elements = Arrays.copyOf(elements, elements.length, Object[].class);
        }
        //赋值属性
        setArray(elements);
    }

该构造方法执行流程如下：

判断传入集合c的类型是否为CopyOnWriteArrayList类型，若是，则将获取该集合类型的底层数组。直接设置当前的CopyOnWriteArrayList的Object[]
如果不是CopyOnWriteArrayList，那么将集合转化为数组elements，判断elements的类型是否为Object[]类型(toArray方法可能不会返回Object[]类型数组)，若不是，则将elements转化为Object[]类型的数组
设置当前CopyOnWriteArrrayList的Object[]为elements

参数是一个数组

public CopyOnWriteArrayList(E[] toCopyIn) {
        //直接赋值给array属性中
        setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
    }

核心函数

copyOf函数(该函数是Arrays中的)

注：该函数是Arrays中的因为会被大量使用所以提前拿出来说明一下
该函数用于复制数组，截取或用null来填充(如果有必要)，是副本具有指定的长度。属于浅拷贝

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        @SuppressWarnings("unchecked")
        //确定copy的拷贝类型(将newTye转化为Object类型，将Object[].class转化为Object类型，判断两者是否相等，若相等则生成指定长度Object数组)
        //如果不相等生成指定类型的数组
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

添加元素的add()

从add方法中可以看到CopyOnWrite是如何实现的，在需要修改的时候，复制一个新数组，在新数组上修改，修改结束后取代老数组，这样保证了修改操作不影响正常读取，另外修改操作是加锁的，也就是说没有了线程不完全的问题，和ArrrayList相比，效率比较低，因为每一次添加元素都需要赋值数组，随着CopyOnWriteArrayList中元素真你感觉，修改代价将会越来越大

在集合末尾添加一个元素

public boolean add(E e) {
        //可重入锁
        final ReentrantLock lock = this.lock;
        //获取锁
        lock.lock();
        try {
            //获取数组
            Object[] elements = getArray();
            //获取数组长度
            int len = elements.length;
            //进行数组拷贝，长度是len+1，因需要添加一个新的元素
            Object[] newElements = Arrays.copyOf(elements, len + 1);
            //将对应元素放到新的数组中
            newElements[len] = e;
            //设置数组
            setArray(newElements);
            return true;
        } finally {
            //释放锁
            lock.unlock();
        }
    }

此函数处理流程：

获取锁(保证多线程的安全访问)，获取当前的Object数组，获取数组长度
根据Object数组赋值长度为length+1的数组为newElements(此时newElements[length]=null)
将newElements[length]设置为元素e
将newElements设置为CopyOnWriteArrayList的数组
释放锁

在指定角标位置添加元素

    public void add(int index, E element) {
        final ReentrantLock lock = this.lock;
        获取锁
        lock.lock();
        try {
            //获取数组
            Object[] elements = getArray();
            //获取数组长度
            int len = elements.length;
            //判断index是否数组越界
            if (index > len || index < 0)
                throw new IndexOutOfBoundsException("Index: "+index+
                                                    ", Size: "+len);
                                        
            //新的数组                            
            Object[] newElements;
            //如果等于0说明本身就在末尾添加，直接整个数组进行拷贝
            int numMoved = len - index;
            if (numMoved == 0)
                newElements = Arrays.copyOf(elements, len + 1);
            else {
                //numMoved>0说明是在中间所以要分两次拷贝，并且把index的位置空出来
                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();
        }
    }

执行流程同上，只是如果index在中间位置，需要复制两次，把index的位置空出来。

set()

次方法用于指定的元素替代此列表指定位置上的元素，也是基于数组复制来实现的,原理和add类型

    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) {
                //copy一个新的数组
                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
                //如果oldValue==element那么直接设置数组(这个设置不太懂什么原因，因为elements没有变化只是又重新设置了一下)
                setArray(elements);
            }
            return oldValue;
        } finally {
        //释放锁
            lock.unlock();
        }
    }

其实整个过程也是对数组进行了拷贝，在拷贝的数组上面进行修改

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);
            //numMoved==0说明是删除末尾元素，numMoved>0说明是中间元素，不会出现小于0，小于0情况说明index>len删除的index不存在(不明白为什么没有做数组越界判断)
            int numMoved = len - index - 1;
            if (numMoved == 0)
                //数组拷贝直接将某位元素剔除 setArray(Arrays.copyOf(elements, len - 1));
            else {
                //两次拷贝数组剔除index的元素
                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();
        }
    }

整个过程其实和在指定位置添加一个元素过程一样，只是两次复制数组时候是将数组长度减一，把index上面对应的元素移除出去

总结

读写分离，我们修改的是新的数组，读取的是老的数组，不是一个对象，实现了读写分离，这种技术数据库用的非常多，在高并发下未了环境数据库的压力，即使做了缓存也要对数据进行读写分离，读的时候使用读库，写的时候使用写库，然后读库、写库，进行一定同步，这样就避免同一个库上，读、写IO操作太多
使用场景读操作远多于修改操作(因为每一次修改面临着，对原数组进行拷贝，随着数组越来越大，时间消耗就越来远长)

缺点

写操作时候，需要数组拷贝，会很消耗内存，如果原数组内容比较多的情况下，可能导致young gc或full gc
不能用于实时读取场景，拷贝数组都需要时间，所以调用一个set或者add方法后，读取到数据有可能还是旧的，也就是说CopyOnWriteArrayList只实现了最终一致性，但是没有满足实时的一致性

适用场景

就是读操作远远大于写操作的场景，不过也要慎用，不保证数据放多少情况，万一数据非常多，每一次add/set等操作都需要复制数组代价太高