写时复制（COW）技术与其在Linux、Java中的应用
脑子有些累，继续写基础文。
什么是写时复制
中文维基上给出的定义基本准确，抄录如下。
写入时复制（英语：Copy-on-write，简称COW）是一种计算机程序设计领域的优化策略。其核心思想是，如果有多个调用者同时请求相同资源（如内存或磁盘上的数据存储），他们会共同获取相同的指针指向相同的资源，直到某个调用者试图修改资源的内容时，系统才会真正复制一份专用副本（private copy）给该调用者，而其他调用者所见到的最初的资源仍然保持不变。这过程对其他的调用者都是透明的。此作法主要的优点是如果调用者没有修改该资源，就不会有副本被创建，因此多个调用者只是读取操作时可以共享同一份资源。
一言以蔽之，就是读操作直接在正本上进行，一旦有写操作，就复制一份副本出来，并在副本上做修改，再将修改完之后的副本当作正本。
写时复制技术的应用比较广泛，本文举两个例子简单介绍下。
COW in Linux：fork()+exec()
我们知道，在Linux中创建（子）进程的唯一方法就是调用fork()函数。fork()调用会返回两次，在父进程中返回子进程的PID，在子进程中返回0，且调用成功后产生的子进程的内存空间完全是父进程的拷贝（除PID外）。
子进程创建出来之后，默认实现的功能与父进程一致，但是大多数时候子进程需要做别的事情，这时就需要用到exec()函数——“exec()函数”这个名称是一类共6个以exec为前缀的函数的统称，它们都以execve()系统调用为基础。调用exec()函数会加载一个新的可执行程序，用其覆盖掉当前进程内存空间中的进程映像，以实现其他功能。
举个例子，启动一个Shell窗口并执行./my_script.sh命令，实际发生了两件事：
- 当前Shell进程通过调用fork()创建一个子Shell进程；
- 子Shell进程通过调用execve()执行my_script.sh脚本。
基于上面的解释，我们可以用下面的图表示fork()+exec()的过程。注意fork()时会复制和页表和整个地址空间。
但是前面也已经说过，“大多数时候子进程需要做别的事情”，所以fork()时复制给子进程的数据往往立刻就被丢弃，白白浪费资源。
有了写时复制之后，fork()出的子进程的地址空间初始全部指向父进程的地址空间（即只复制页表），同时内核将父进程持有的页设为只读。一旦父、子进程中有一方写只读的内存页，就会立即触发缺页中断（page fault）并进入中断处理例程。内核会将该页复制一份副本，供执行写操作的一方使用。如下面的图所示，内存页B的复制被延迟到了子进程写入它的时候。
如果是fork()+exec()的话，子进程被创建后就立即执行一个executable，父进程内存中的数据对子进程而言没有意义——即父进程的页根本不会被子进程写入。在这种情况下可以完全避免复制，而是直接为子进程分配地址空间，如下图所示。
可见，写时复制减少了很多不必要的复制和资源分配overhead。不过，如果fork()之后不是执行exec()，并且父子进程都要频繁写数据的话，就会造成非常大量的page fault，效率反而会降低，所以要尽量避免这种情况。
有一部分框架（主要是数据库）也会利用系统提供的写时复制特性，最典型的就是Redis。我们知道，在Redis上执行bgsave命令，可以异步地执行rdb dump操作，得到包含其中全量数据的dump.rdb文件。显然，这个过程只需要读内存，并且又是一个相当耗时的操作，通过fork子进程来处理能够充分发挥COW的便利性，效率很高。
COW in Java：CopyOnWriteArrayList/Set
在很久之前的这篇文章里，笔者讲解了ConcurrentModificationException和fail-fast机制，并在最后简单提到了它的counterpart——fail-safe机制，代表就是j.u.c包中支持写时复制的线程安全的集合：CopyOnWriteArrayList、CopyOnWriteArraySet。
下面以CopyOnWriteArrayList为例进行分析，它的核心是一个数组和一把ReentrantLock。
final transient ReentrantLock lock = new ReentrantLock();
private transient volatile Object[] array;
当执行读取操作时，是直接读取正本——即原数组，所以不需要加锁。
public E get(int index) {
return get(getArray(), index);
}
private E get(Object[] a, int index) {
return (E) a[index];
}
final Object[] getArray() {
return array;
}
而当执行写入操作时，首先通过lock加锁，然后调用Arrays.copyOf()方法复制出一个新数组，在新数组上写入数据，最后将原数组array的引用指向新数组，并解锁。JDK中的源码如下所示，以set()方法为例。
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) {
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
setArray(elements);
}
return oldValue;
} finally {
lock.unlock();
}
}
final void setArray(Object[] a) {
array = a;
}
其他写入操作的方法，如add()、remove()、clear()等，原理都是类似的，不再赘述了。
以上就是CopyOnWriteArrayList处理读写操作的基本流程。最后还有一个小问题：它是如何消除并发修改异常的？以下是它所用的迭代器COWIterator的相关代码。
public Iterator<E> iterator() {
return new COWIterator<E>(getArray(), 0);
}
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;
private COWIterator(Object[] elements, int initialCursor) {
cursor = initialCursor;
snapshot = elements;
}
public boolean hasNext() {
return cursor < snapshot.length;
}
public boolean hasPrevious() {
return cursor > 0;
}
@SuppressWarnings("unchecked")
public E next() {
if (! hasNext())
throw new NoSuchElementException();
return (E) snapshot[cursor++];
}
@SuppressWarnings("unchecked")
public E previous() {
if (! hasPrevious())
throw new NoSuchElementException();
return (E) snapshot[--cursor];
}
public int nextIndex() {
return cursor;
}
public int previousIndex() {
return cursor-1;
}
// ...
}
显而易见，COWIterator执行遍历时，操作的都是原数组array的快照snapshot，也就是“旧”数据，自然不会产生并发修改异常了。
与fail-fast的容器相比，fail-safe的COW容器固然安全了很多，但是由于每次写都要复制整个数组，时间和空间的开销都更高，因此只适合读多写少的情景。在写入时，为了保证效率，也应尽量做批量插入或删除，而不是单条操作。并且它的正本和副本有可能不同步，因此无法保证读取的是最新数据，只能保证最终一致性。
The End
刚过了520大促，又来了一波事情，还是去喝两杯放松一下吧。
晚安各位。
