极客时间 ——《Java并发编程实战》 29 | Copy-On-Write模式：不是延迟策略的COW

上篇提到String这个类在实现 replace() 方法的时候并没有修改类中char[] 的内容，而是创建了一个新的字符串对象返回。这种方法在解决不可变对象的修改问题时经常用到，上面的 replace 本质上就是一个 Copy-on-Write 写时复制 方法，经常被缩写为 COW 或 CoW。

不可变对象的写操作往往都是使用 Copy-on-Write 方法解决的，并且CoW 的应用领域并不局限于 Immutability 不变性模式中，下面是对其应用领域的介绍。

Copy-on-Write 模式的应用领域

{% post_link 读书笔记/极客时间/Java并发编程实战/第二部分—并发工具类/20|并发容器 20|并发容器 %}

中介绍过 Java 中的 CopyOnWriteArrayList 和 CopyOnWriteArraySet 这两个并发容器的设思想就是写时复制 Copy-on-Write。通过这种设计，使这两个容器实现的读操作是无锁的，所以可以将读操作的性能发挥到最大。

除了 Java 领域，Cow 模式在操作系统领域也被广泛应用：类 Unix 操作系统创建进程的 API 是 fork。

传统fork 函数：创建一个完整的父进程副本，如果父进程此时用了 1G 的内存空间，则 fork() 子进程时也要复制整个父进程的地址空间，导致整个过程非常耗时。

Linux 中的 fork 函数：fork() 子进程时不复制整个进程的地址空间，而是让父子进程共享一个地址空间，当父进程/子进程需要写入内存时才真正进行地址空间的复制，这也是一种延迟操作策略。

本质上来说，父子进程的内存空间以及数据都是要隔离的，使用 Copy-on-Write 更多的是体现了一个延迟策略，等到真正开始写入数据时才进行复制操作，而不是一开始就复制。并且 CoW 还支持按需复制，所以 CoW 在操作系统领域的作用是提升性能。

而 Java 中的 CoW 修改时会复制整个容器，所以在提升读性能的前提下牺牲了内存【空间换时间】，可以看到，在不同的场景下，同样使用 CoW 对性能的影响并不相同。

除了创建进程，文件系统也同样用到了 CoW，例如： Btrfs（B-Tree File System）、aufs（advance multi-layerd unification filesysytem）。

其他使用到 CoW 的领域：

Docker 容器的镜像设计（底层向上层层构建，上一层并不对底层进行修改）
Git（背后的设计思想）

CoW 最大的应用领域：函数式编程。函数式编程的基础是不可变性（Immutability），所以函数式编程里的所有修改操作都需要 Copy-on-Write 来解决。但是这也带来了性能问题，早起函数式编程没有流行起来与硬件的性能有关，但是现在随着性能的提升，已经变得可以接受了。

并且函数式编程中的 CoW 并不像 Java中的 CopyOnWriteArrayList 那样笨重：整个数组都复制了一遍。 CoW 是可以按需复制的，这里作者推荐了一本书：Purely Functional Data Structures，这本书描述了各种具备不变性数据结构的实现。

一个真实的案例

作者这里举了一个 RPC 框架的例子，类似 Dubbo。服务提供方是多实例分布式部署的。客户端调用 RPC 时选定一个服务实例进行调用，这个选定的过程本质就是在做负载均衡， 负载均衡的前提是客户端有全部的路由信息。

例如下图中，A 服务有3个实例，客户端在调用 A 服务之前，从这三个中选择一个进行调用，然后通过 RPC 将请求发送给选中的实例。

RPC 框架的一个核心人物就是维护服务的路由关系，可以将路由关系简化成下面这张表，而当服务提供方上限或者下线的时候，就需要更新这张路由表：

接口	服务提供方IP	服务提供方端口	状态
io.service.helloword	192.168.1.1	7890	ONLINE
io.service.helloword	192.168.1.2	7890	ONLINE
io.service.helloword	192.168.1.3	7890	ONLINE

下面是实现分析：

每次 RPC 调用都要访问路由表，所以这个读操作的性能要求很高，但是一致性要求并不高。所以这个路由表是典型的读多写少类问题，写操作相比于读操作少很多。

通过以上分析：对读的性能要求高，弱一致性，综合在一起就发现 CopyOnWriteArrayList 和 CopyOnWriteArraySet 天生适合这种场景，下面的示例代码使用了ConcurrentHashMap<String, CopyOnWriteArraySet<Router>> 这个数据结构来描述路由表：

Key 是接口名，Value 是路由集合，用 CopyOnWriteArraySet 表示。

下面是 Router 的设计思路：服务方每一次上线/下线都会更新路由信息，有两种实现选择：

更新 Router 的状态位进行标识，但是这样的话所有访问该状态的地方都需要使用同步机制，对性能影响很大
使用 Immutability 模式，每次上/下线都创建一个新的 Router 对象或者删除对应的 Router 对象。

由于上下线的频率很低，所以后者是更好的选择。

Router 类的实际代码如下，是一种典型的 Immutability 模式的实现。需要注意的是对 equals 方法的重写，这样 CopyOnArraySet 的 add() 和 remove() 方法才能正常工作。

// 路由信息数据类
public class Router {
    private final String ip;
    private final Integer port;
    private final String iface;

    public Router(String ip, Integer port, String iface) {
        this.ip = ip;
        this.port = port;
        this.iface = iface;
    }

    // 重写 equals 方法 需要对比三个字段完全一致才能认定两个路由对象一致
    @Override
    public boolean equals(Object obj) {
        if (obj instanceof Router) {
            Router r = (Router) obj;
            return iface.equals(r.iface) &&
                    ip.equals(r.ip) &&
                    port.equals(r.port);
        }
        return false;
    }

    @Override
    public int hashCode() {
        return Objects.hash(ip, port, iface);
    }

    // 路由表信息

    public class RouterTable {
        // key:接口名
        // Value:路由集合
        ConcurrentHashMap<String, CopyOnWriteArraySet<Router>> rt = new ConcurrentHashMap<>();

        // 根据接口名获取路由表
        public Set<Router> getRouter(String iface) {
            return rt.get(iface);
        }

        // 删除路由
        public void remove(Router router) {
            Set<Router> set = rt.get(router.iface);
            if (set != null) {
                set.remove(router);
            }
        }

        // 增加路由 todo 这里 ConcurrentHashMap 的 computeIfAbsent 需要看源码学习一下
        public void add(Router router) {
            Set<Router> set = rt.computeIfAbsent(router.iface, r -> new CopyOnWriteArraySet<>());
            set.add(router);
        }
    }
}