深入分析CopyOnWriteArrayList的源码设计

CopyOnWriteArrayList提供线程安全性和可伸缩性

可伸缩性指的是一个应用程序在工作负载和可用处理资源增加时其吞吐量的表现情况。

一个可伸缩的程序能够通过使用更多的处理器、内存或者I/O带宽来相应地处理更大的工作负载。

锁住某个共享的资源以获得独占式的访问这种做法会形成可伸缩性瓶颈――它使其他线程不能访问那个资源，即使有空闲的处理器可以调用那些线程也无济于事**。为了取得可伸缩性，我们必须消除或者减少我们对独占式资源锁的依赖。**

CopyOnWriteArrayList

​ CopyOnWriteArrayList是java1.5版本提供的一个线程安全的ArrayList变体，ArrayList具有fast-fail特性，它是值在遍历过程中，如果ArrayList的内容发生过修改，那么会抛出ConcurrentModificationException。

​ 在多线程环境下，这种情况变得尤为突出。不使用迭代器形式而使用下标来遍历就会带来一个问题，读写没有分离。写操作户影响到读的准确性，甚至导致IndexOutOfBoundsException。不直接遍历list，而是把list拷贝一份数组，再行遍历。

​ 写时拷贝，自然实在做写操作时，把原始数据拷贝到一个新的数组，与写操作相关的主要有三个方法：add、remove、set，在每一次add操作里，数组都被拷贝了一个副本，这就是写时拷贝的原理，那么写时拷贝和读时拷贝各有什么优势，如何选择呢？

​ 如果一个list的遍历操作比写入操作更频繁，那么用该使用CopyOnWriteArrayList，如果list的写入操作比遍历操作更频繁，那么应该考虑读时拷贝。

CopyOnWriteArrayList源码原理分析

1 使用场景

• 是用于替代Vector和SynchronizedList的，相较于Vector和SynchronizedList有更好的并发性能
• Copy-on-Write并发容器还包括CopyOnWriteArraySet，用来替代同步Set
• 主要适用于：对于读操作有快速要求的，即是：读快写慢

2 读写规则

• 我们都知道读写锁的规则是：读写互斥，写写互斥
• 而CopyOnWrite则做了一个升级：读取是完全不加锁的，并且写入也不会阻塞读取操作，只有写入和写入之间需要进行同步等待。（读写不互斥，写写互斥）
• 此外，我们可以在迭代中可以进行删改元素，看一个案例

/**
 * CopyOnWriteArrayList可以在迭代中修改数组内容，而ArrayList不行
 * @author yiren
 */
public class CopyOnWriteArrayListExample01 {
    public static void main(String[] args) {
        // ArrayList<String> list = new ArrayList<>();
        CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();

        list.add("1");
        list.add("2");
        list.add("3");
        list.add("4");
        list.add("5");

        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            System.out.println(list);
            String next = iterator.next();
            System.out.println(next);

            if (next.equals("2")) {
                list.remove("3");
            }

            if (next.equals("4")) {
                list.add("3 add");
            }
        }
    }
}

[1, 2, 3, 4, 5]
1
[1, 2, 3, 4, 5]
2
[1, 2, 4, 5]
3
[1, 2, 4, 5]
4
[1, 2, 4, 5, 3 add]
5

Process finished with exit code 0

• 结果输出和list中的元素不对应。CopyOnWriteArrayList是这个思想，迭代你可以改，但是你改你的，我迭代我的，它内部是副本机制，这个和ArrayList的迭代器不一样，ArrList里面有一个modCount值来判断你迭代过程中是否修改的

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

  • 这个expectedModCount是在迭代器创建前，从ArrayList对象中获取的，原有ArrayList对象左右删改，那么modCount就会和expectedModCount不一值，此时就会快速失败了。

3 实现原理

• CopyOnWrite：在写入操作的时候，它会先copy一份到新内存上，然后再修改，修改完成，再把原来的指针指过去，就OK。
• 这个过程就导致了，你在迭代的时候，迭代的内存还是老内存上的值，而不是修改过后的值
• 所以注意：每次修改或添加都会创建新副本，使之读写分离，而旧的内存数据是不会变的。
• 我们再看一个案例

/**
 * @author yiren
 */
public class CopyOnWriteArrayListExample02 {
    public static void main(String[] args) {
        CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();

        list.add("1");
        list.add("2");
        list.add("3");
        Iterator<String> itr1 = list.iterator();
        list.add("4");
        Iterator<String> itr2 = list.iterator();

        itr1.forEachRemaining(System.out::print);
        System.out.println();
        itrforEachRemaining(System.out::print);
    }
}

123
1234
Process finished with exit code 0

• 在CopyOnWrite的迭代器使用上，即使你修改了，它的迭代内容也只取决于他创建时候的集合的数据内容。而不取决于实际list是否修改。
• 所以迭代过程可能会出现数据过期问题

4 存在的缺点

• 数据一致性问题：也就是上面所提到的，它**只能保证最终数据一致性，而不保证数据实时一致性。**如果对写入实时响应的需求，不推荐使用。
• 内存浪费：CopyOnWrite的写是复制的机制，写操作的时候就一定会复制一份。这会很浪费内存

5 源码分析

• 首先CopyOnWriteArrayList是一个数组的列表集合，它的根本存储就是数组

    private transient volatile Object[] array;

• 多线程同时写入的时候是ReentrantLock。

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

• 它的创建，构造函数可想而知，也就是给一个空数组。

    public CopyOnWriteArrayList() {
        setArray(new Object[0]);
    }

• 但是它提供了一个可以直接放集合的构造函数，把数据先放入数组，然后直接指过去

    public CopyOnWriteArrayList(Collection<? extends E> c) {
        Object[] elements;
        if (c.getClass() == CopyOnWriteArrayList.class)
            elements = ((CopyOnWriteArrayList<?>)c).getArray();
        else {
            elements = c.toArray();
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elements.getClass() != Object[].class)
                elements = Arrays.copyOf(elements, elements.length, Object[].class);
        }
        setArray(elements);
    }

• add方法

    public boolean add(E e) {
        final ReentrantLock lock = this.lock;
        //添加的时候先上锁
        lock.lock();
        try {
            // copy一份到新数组，数组长度+1
            Object[] elements = getArray();
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len + 1);
            // 新值放到末尾，把指针指过去
            newElements[len] = e;
            // 最后返回true 并释放锁
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }

• get方法
  • 没有任何加锁，直接返回对应的值

    @SuppressWarnings("unchecked")
    private E get(Object[] a, int index) {
        return (E) a[index];
    }

    /**
     * {@inheritDoc}
     *
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E get(int index) {
        return get(getArray(), index);
    }