Java 中的写时复制容器

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。

CopyOnWrite 的应用场景

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

CopyOnWrite 的缺点

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

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

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

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

CopyOnWriteArraySet 简介

它是线程安全的无序的集合，可以将它理解成线程安全的 HashSet。有意思的是，CopyOnWriteArraySet 和 HashSet 虽然都继承于共同的父类 AbstractSet；但是，HashSet 是通过散列表(HashMap)”实现的，而 CopyOnWriteArraySet 则是通过“动态数组(CopyOnWriteArrayList)”实现的，并不是散列表。
和 CopyOnWriteArrayList 类似，CopyOnWriteArraySet 具有以下特性：
1. 它最适合于具有以下特征的应用程序：Set 大小通常保持很小，只读操作远多于可变操作，需要在遍历期间防止线程间的冲突。
2. 它是线程安全的。
3. 因为通常需要复制整个基础数组，所以可变操作（add()、set() 和 remove() 等等）的开销很大。
4. 迭代器支持 hasNext(), next()等不可变操作，但不支持可变 remove()等 操作。
5. 使用迭代器进行遍历的速度很快，并且不会与其他线程发生冲突。在构造迭代器时，迭代器依赖于不变的数组快照。
6. CopyOnWriteArraySet 的“线程安全”机制，和 CopyOnWriteArrayList 一样，是通过 volatile 和互斥锁来实现的。

CopyOnWriteArrayList 简介

它相当于线程安全的 ArrayList。和 ArrayList 一样，它是个可变数组；但是和 ArrayList 不同的时，它具有以下特性：
1. 它最适合于具有以下特征的应用程序：List 大小通常保持很小，只读操作远多于可变操作，需要在遍历期间防止线程间的冲突。
2. 它是线程安全的。
3. 因为通常需要复制整个基础数组，所以可变操作（add()、set() 和 remove() 等等）的开销很大。
4. 迭代器支持 hasNext(), next()等不可变操作，但不支持可变 remove()等操作。
5. 使用迭代器进行遍历的速度很快，并且不会与其他线程发生冲突。在构造迭代器时，迭代器依赖于不变的数组快照。

CopyOnWriteArrayList 原理和数据结构

CopyOnWriteArrayList 的数据结构，如下文所示：

CopyOnWriteArrayList 实现 List 接口
成员 lock reentrantlock
volatile array[]:object
说明：
1. CopyOnWriteArrayList 实现了 List 接口，因此它是一个队列。
2. CopyOnWriteArrayList 包含了成员 lock。每一个 CopyOnWriteArrayList 都和一个互斥锁 lock 绑定，通过 lock，实现了对 CopyOnWriteArrayList 的互斥访问。
3. CopyOnWriteArrayList 包含了成员 array 数组，这说明 CopyOnWriteArrayList 本质上通过数组实现的。

下面从“动态数组”和“线程安全”两个方面进一步对 CopyOnWriteArrayList 的原理进行说明。

1. CopyOnWriteArrayList 的“动态数组”机制 -- 它内部有个“volatile 数组”(array)来保持数据。在“添加/修改/删除”数据时，都会新建一个数组，并将更新后的数据拷贝到新建的数组中，最后再将该数组赋值给“volatile 数组”。这就是它叫做 CopyOnWriteArrayList 的原因！CopyOnWriteArrayList 就是通过这种方式实现的动态数组；不过正由于它在“添加/修改/删除”数据时，都会新建数组，所以涉及到修改数据的操作，CopyOnWriteArrayList 效率很
   低；但是单单只是进行遍历查找的话，效率比较高。
2. CopyOnWriteArrayList 的“线程安全”机制 -- 是通过 volatile 和互斥锁来实现的。(01) CopyOnWriteArrayList 是通过“volatile 数组”来保存数据的。一个线程读取 volatile 数组时，总能看到其它线程对该 volatile 变量最后的写入；就这样，通过 volatile 提供了“读取到的数据总是最新的”这个机制的
   保证。(02) CopyOnWriteArrayList 通过互斥锁来保护数据。在“添加/修改/删除”数据时，会先“获取互斥锁”，再修改完毕之后，先将数据更新到“volatile 数组”中，然后再“释放互斥锁”；这样，就达到了保护数据的目的。

接下来这几个方法是cowset实现时用到的

不存在则添加元素，可以发是直接新建一个数组，边判断边添加，若发现相同，则返回false，丢弃新建的数组
public boolean addIfAbsent(E e) {
          final 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();
         }
     }

将所有不存在的元素加入到list中，index方法在下方
public int addAllAbsent(Collectionextends E> c) {
    Object[] cs = c.toArray();
 if (cs.length == 0)
        return 0;
  Object[] uniq = new Object[cs.length];
 final ReentrantLock lock = this.lock;
  lock.lock();
 try {
        Object[] elements = getArray();
 int len = elements.length;
 int added = 0;
 for (int i = 0; i < cs.length; ++i) { // scan for duplicates
  Object e = cs[i];
 if (indexOf(e, elements, 0, len) < 0 &&
                indexOf(e, uniq, 0, added) < 0)
                uniq[added++] = e;
  }
        if (added > 0) {
            Object[] newElements = Arrays.copyOf(elements, len + added);
  System.arraycopy(uniq, 0, newElements, len, added);
  setArray(newElements);
  }
        return added;
  } finally {
        lock.unlock();
  }
}

元素查重 重复返回-1
* @param o element to search for
 * @param elements the array
 * @param index first index to search
 * @param fence one past last index to search
 * @return index of element, or -1 if absent
 */private static int indexOf(Object o, Object[] elements,
 int index, int fence) {
    if (o == null) {
        for (int i = index; i < fence; i++)
            if (elements[i] == null)
                return i;
  } else {
        for (int i = index; i < fence; i++)
            if (o.equals(elements[i]))
                return i;
  }
    return -1;
}