写时复制

title: Copy-on-write的介绍与应用 categories:

数据结构

本文目录

什么是写时复制
写时复制的应用场景
写时复制的实现

在并发编程中，如果需要实现对资源的冲突处理，一般采用互斥锁，队列、不可变来实现。上面的技术实现在很多书籍中都有，不过今天介绍的是一种新的方法--写时复制(Copy-on-write, COW)。

关键词: COW, Copy on write, Redis

如果看的懂英文就直接看这里：

Copy on write (COW) is an optimization strategy that avoids copying large sized objects.

In a lot of real world programs, a value is copied to another variable and often is never written to. In most languages other than C++, all large sized objects are actually references. When you copy an object, all you copy is a pointer (shallow copy semantics). In such languages, COW is implemented at the language/runtime level, and not in the standard library.

In C++, copies are deep copies by default (value semantics), thus assigning large structures and strings are expensive, because the entire data is duplicated.

To avoid this, one can make a system where a copy is always shallow, but when you modify a copied object, the underlying object is duplicated, and then the changes are applied to the new copy.

总的来说，COW通过浅拷贝(shallow copy)只复制引用而避免复制值；当的确需要进行写入操作时，首先进行值拷贝，再对拷贝后的值执行写入操作，这样减少了无谓的复制耗时。

特点如下

读取安全（但是不保证缓存一致性），写入安全（代价是加了锁，而且需要全量复制）
不建议用于频繁读写场景下，全量复制很容易造成GC停顿，因此建议使用平时的ConcurrentXX包来实现。
适用于对象空间占用大，修改次数少，而且对数据实效性要求不高的场景。

这里的安全指在进行读取或者写入的过程中，数据不被修改。

写时复制的应用场景

写时复制最擅长的是并发读取场景，即多个线程/进程可以通过对一份相同快照，去处理实效性要求不是很高但是仍然要做的业务（比如实现FS\DB备份、日志、分布式路由），举例如下。

1. Unix下的fork()系统调用

fork()是一个系统调用，用于创建新的进程(process)。

fork() creates a new process by duplicating the calling process. The new process, referred to as the child, is an exact duplicate of the calling process, referred to as the parent.

在以前的文章中说过，fork内部实际上是对clone()系统函数的调用，它的参数CLONE_FLAG决定了需要共享哪些数据。在fork中，没有CLONE_VM参数，也就意味着不会共享\竞争同一个内存，而是复制一个内存快照给子进程，这个内存在32位下是4G的大小，占用空间相当的大，如果通过类似memcpy进行内存复制的话，fork调用的耗时将相当显著，甚至阻塞业务，那么为什么在真正开发调用时却没有发生呢？因为内部也是通过COW机制实现的。

内核实现：

在内核侧，在进行了内存“复制”后，子进程与父进程指向同一个只读的Page分页。当子进程或者父进程发送修改内存请求后，由于是分页是只读的，OS此时才将内存进行复制为两份，并将这两份内存设置为可写权限，最后再处理刚刚发送的修改内存请求。通过上述策略，实现了延迟复制，进程的创建是不是变快了？

2. Redis的持久化

Redis是一个基于KV的MemCache框架，可以将数据全部存储在内存中，特别适用于抢购、红包等高并发场景，当你希望对数据进行全量Dump(bgsave)到文件中或者进行主从同步时，将进行下面的步骤。

Redis forks. We now have a child and a parent process.
The child starts to write the dataset to a temporary RDB file.
When the child is done writing the new RDB file, it replaces the old one.

可以看出，Redis通过fork()系统调用实现了写时复制，而没有自己去造轮子

int rdbSaveBackground(char *filename) {
    pid_t childpid;
    long long start;

    if (server.aof_child_pid != -1 || server.rdb_child_pid != -1) return C_ERR;

    server.dirty_before_bgsave = server.dirty;
    server.lastbgsave_try = time(NULL);

    start = ustime();
    //指向子线程的pid如果为0，表示fork成功，为正表示为parent线程
    if ((childpid = fork()) == 0) {
        int retval;

        /* Child进程要执行的代码 */
        closeListeningSockets(0);
        redisSetProcTitle("redis-rdb-bgsave");
        retval = rdbSave(filename);
        if (retval == C_OK) {
            size_t private_dirty = zmalloc_get_private_dirty();

            if (private_dirty) {
                serverLog(LL_NOTICE,
                    "RDB: %zu MB of memory used by copy-on-write",
                    private_dirty/(1024*1024));
            }
        }
        exitFromChild((retval == C_OK) ? 0 : 1);
    } else {
        /* Parent */
        ...
        return C_OK;
    }
    return C_OK; /* unreached */
}

在rdbSave中(目前已经为子线程中)，具体实现如下，代码太长就不贴了

创建了一个temp-${getPid()}.rdb的文件
调用rioInitWithFile(rio *r, FILE *tmp)，将r初始化为rioBufferIO
对全局变量server进行forEach反序列化，并保持到缓存r中，并写入文件，注意这个Server指针已经与父进程无关了
进行fflush、fsync、fclose系统调用清除OS的FS缓存（这也是OS内部的COW优化）
进行rename系统调用，进行重命名

系统调用都是默认线程安全的，所以不用担心多次重命名等问题

可以看出，在Redis中没有memcpy等内存复制过程，而是直接使用server指针进行读取并写入文件，因为在fork时，已经duplicated了快照。

写时复制的实现

以Java为例，在CopyOnWriteArrayList中，写数据在锁的保护下，而读取可以任意进行，代码如下。

private transient volatile Object[] array;


public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        //类似于memcpy，构造一个新的对象
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        //重新设置引用
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}

public E get(int index) {
	//获取到的数据没有实效性
    return get(getArray(), index);
}

final Object[] getArray() {
        return array;
}

其它可能需要深入了解的技能

#####1. 如何实现String\Map的写时复制？

这个一般只在糟糕的面试题中出现，因为写时复制主要用于处理大的数据，而大型的字符串、Map却很少见到场景(如果说非要来一个场景的话，就是Zookeeper中读取服务时，可能需要一个Map<String,Class>来实现)。在C++中，写时复制的String已经被废弃，并且Redis中设计的字符串可以更加优雅地扩容，在Java中，各类并发库已经很成熟，写时复制主要用于实现安全迭代，而没有String或者Map的需求。

如果非要让你写，可以这样处理:

在构造函数、写入函数中实现深拷贝，并加锁，比如put中就再包装一道HashMap。
在getter函数，实现无锁直接获取。

#####2. ConcurrentHashXXX与CopyOnWriteXXX的对比？

一个适用于写入量大的场景，一个适用于读取量大的场景，它们的线程安全关系如下

	Normal	Concurrent	COW
Read	Unsafe	Safe	Safe, may dirtyData
Write	Unsafe	Safe	Safe, may slowest

写时复制的应用场景

1. Unix下的fork()系统调用

2. Redis的持久化

写时复制的实现

其它可能需要深入了解的技能

Ref