从零实现一个CopyOnWrite写时复制的map，同时了解写时复制的使用场景。

概念

wiki:

Copy-on-write (COW), sometimes referred to as implicit sharing[1] or shadowing,[2] is a resource-management technique used in computer programming to efficiently implement a “duplicate” or “copy” operation on modifiable resources.[3] If a resource is duplicated but not modified, it is not necessary to create a new resource; the resource can be shared between the copy and the original. Modifications must still create a copy, hence the technique: the copy operation is deferred until the first write. By sharing resources in this way, it is possible to significantly reduce the resource consumption of unmodified copies, while adding a small overhead to resource-modifying operations.

CopyOnWrite算法，一般中文叫「写时复制」。

核心思想：

  • 延迟写；
    • 将写开销延迟到真正数据变化的时刻；
    • 修改数据时，不直接修改原资源引用，而是拷贝一份副本，在副本上更新数据，之后将数据引用直接指向副本，在此之前读取到旧数据的地方仍然引用旧的数据引用；
  • 而读取则共享一份资源；

适用场景：

  • 由于有多个读写操作，因此适用于多 worker（进程、线程） 上下文（JVM中我们考虑多线程场景）；
  • 读多写少；
  • 可容忍读取快照，对数据一致性要求较低；

实现

我们实现一个适用于很少更新场景的配置类map，如黑白名单的更新很少。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

public class COWMap<K, V> {

    /**
     * volatile 提供JVM可见性、有序性语义，保证集合有写入后，其他线程可以感知到变化
     */
    private volatile Map<K, V> internalMap;

    public COWMap() {
        internalMap = new HashMap<>();
    }

    public COWMap(Map<K, V> map) {
        internalMap = map;
    }

    public V get(K key) {
        return internalMap.get(key);
    }

    public void put(K key, V val) {
        synchronized (this) {
            // 先拷贝一份副本
            Map<K, V> snapshot = new HashMap<>(internalMap);
            // 副本修改数据
            snapshot.put(key, val);
            // 直接将 internalMap 替换为副本，这里写入保障可见性语义
            internalMap = snapshot;
        }
    }

}

关键操作

get读数据

多个线程读取数据时公用一份资源，即internalMap。

同时为了明确JVM提供的读写一致语义，我们用volatile修饰。

put写数据

更新数据时，上锁，保证同一时刻只有一个线程进入更新逻辑。

步骤：

  1. 先拷贝一份副本；
  2. 副本修改数据；
  3. 直接将 internalMap 替换为副本，这里写入保障可见性语义；

应用场景

通过例子可以更好地理解CopyOnWrite。

虚拟内存管理

之前在 研究一下fork函数 中正好对Linux的fork调用做了一些解读。

简单理解： 主进程调用fork生成子进程。在没有新数据更新的情况下，子进程共享父进程的页表映射，主进程内存发生修改时，子进程才将对应更新的页进行拷贝、更新子进程持有的页表。

此例中的页表、内存，即为共享的资源。

数据无修改时，多个进程间读取同一份内存。

fork调用过程

C++ STL String类中的写时复制

参考：C++ STL String类中的Copy-On-Write 。

总结

以上，实现了CopyOnWrite最核心的逻辑，并且列举了主流的一些应用场景。

写时复制在大多数场景中用处不多，在集合场景也不太适用，但是底层的延迟写、快照思想非常值得学习。

Ref