我要评论
文章目录
1、写时复制的介绍
写时复制（copy-on-write，简称cow）是一种计算机程序设计领域的优化策略。
其核心思想是：如果有多个调用者同时请求相同资源（如内存或磁盘上的数据存储），他们会共同获取相同的指针指向相同的资源，直到某个调用者试图修改资源的内容时，系统才会真正复制一份专用副本给该调用者，而其他调用者所见到的最初的资源仍然保持不变。这一过程对其他的调用者都是透明的。
- 当对容器进行写操作（这里的写可以理解为 “增、删、改”）时，为了避免读写操作同时进行而导致的线程安全问题
我们将原始容器中的数据复制一份放入新创建的容器，然后对新创建的容器进行写操作； - 而读操作继续在原始容器上进行，这样读写操作之间便不会存在数据访问冲突，也就不存在线程安全问题
当写操作执行完成之后，新创建的容器替代原始容器，原始容器便废弃。
写时复制的主要优点是，如果调用者没有修改该资源，就不会有副本被创建，因此多个调用者只是进行读取操作时可以共享同一份资源。这种策略不仅优化了内存使用，还保护了数据，因为在写操作之前，原始数据不会被覆盖或修改，从而避免了数据丢失的风险。
在 java 中，copyonwritearraylist 和 copyonwritearrayset 就是使用了这种策略的两个类。这两个类都位于java.util.concurrent 包下，是线程安全的集合类。当需要修改集合中的元素时，它们不会直接在原集合上进行修改，而是复制一份新的集合，然后在新的集合上进行修改。修改完成后，再将指向原集合的引用指向新的集合。这种设计使得读操作可以在不加锁的情况下进行，从而提高了并发性能。
总的来说，写时复制是一种适用于读多写少场景的优化策略，它通过复制数据的方式实现了读写分离，提高了并发性能。但是，它也存在一些潜在的性能问题，如内存占用增加、写操作性能下降以及频繁的垃圾回收。因此，在使用时需要根据具体场景进行权衡和选择。
2、写时复制的实现
2.1、copyonwritearraylist 数据结构
copyonwritearraylist 是 java 中的一种线程安全的 list 实现，它通过每次写操作时复制底层数组来保证线程安全。copyonwritearraylist 跟 arraylist 一样，也实现了 list 接口：
public class copyonwritearraylist<e> implements list<e>, randomaccess, cloneable {
// reentrantlock用于保证在多线程环境下的线程安全
final transient reentrantlock lock = new reentrantlock();
// 持有实际元素的数组，通过volatile修饰保证在多线程环境下的可见性
private transient volatile object[] array;
// 默认构造函数，初始化一个空数组
public copyonwritearraylist() {
this.array = new object[0];
}
// 省略其他方法和实现细节...
}
可以看到，copyonwritearraylist 底层的数据结构是一个数组（object[] array）。这个数组通过 volatile 修饰，保证在多线程环境下的可见性。当数组内容发生变化时，其他线程能够立即看到最新的数组内容。
2.2、copyonwritearraylist 读操作
读操作不需要加锁，因为写操作总是会生成新的数组副本，并且数组引用是 volatile 的，所以读操作总能读取到最新的数组内容。这使得读操作非常高效，适用于读多写少的场景。
public e get(int index) {
return (e) this.array[index];
}
get() 函数实现了 copyonwritearraylist 的读操作，代码逻辑非常简单，直接按照下标访问 array 数组从代码中我们可以发现，读操作没有加锁，因此即便在多线程环境下，效率也非常高
2.2、copyonwritearraylist 写时复制
当对 copyonwritearraylist 进行写操作（如 add, set, remove）时，都会创建底层数组的新副本。在新的副本上进行修改操作，修改完成后再将引用指向新的数组。这种写时复制的机制保证了在进行写操作时不会影响到正在进行读操作的线程。
2.2.1、add() 函数
add() 函数的代码实现如下所示，add() 函数包含写时复制逻辑，因此相对于 get() 函数，要复杂一些
public boolean add(e e) {
// 获取锁，确保在多线程环境下只有一个线程能进行写操作
lock.lock();
try {
// 获取当前数组的长度
int len = array.length;
// 使用 arrays.copyof() 方法创建一个新数组，并将现有数组的元素复制到新数组中
// arrays.copyof() 方法底层依赖 native 方法 system.arraycopy() 来实现复制操作，速度较快
object[] newelements = arrays.copyof(array, len + 1);
// 将新元素添加到新数组的最后一个位置
newelements[len] = e;
// 将底层数组引用指向新数组
array = newelements;
// 返回 true 表示添加成功
return true;
} finally {
// 释放锁
lock.unlock();
}
}
当往容器中添加数据时，并非直接将数据添加到原始数组中，而是创建一个长度比原始数组大一的数组 newelements，将原始数组中的数据拷贝到 newelements。然后将数据添加到 newelements 的末尾，最后修改 array 引用指向 newelements。
除此之外，我们可以看到，为了保证写操作的线程安全性，避免两个线程同时执行写时复制，写操作通过加锁（lock.lock();）来串行执行也就是说：读读、读写都可以并行执行，唯独写写不可以并行执行.
2.2.2、remove() 函数
remove() 函数的代码实现如下所示：
public e remove(int index) {
// 获取锁，确保在多线程环境下只有一个线程能进行写操作
lock.lock();
try {
// 获取当前数组的长度
int len = array.length;
// 获取指定索引处的元素，该元素将在稍后被移除
e oldvalue = get(array, index);
// 计算从指定索引到数组末尾之间的元素个数
int nummoved = len - index - 1;
if (nummoved == 0) {
// 如果要移除的元素是数组的最后一个元素，直接创建一个长度为 len - 1 的新数组
array = arrays.copyof(array, len - 1);
} else {
// 如果要移除的元素在数组的中间位置
object[] newelements = new object[len - 1];
// 将原数组中从索引 0 到 index-1 的元素复制到新数组中
system.arraycopy(array, 0, newelements, 0, index); // array[0, index - 1]
// 将原数组中从索引 index+1 到末尾的元素复制到新数组中，从 index 位置开始
system.arraycopy(array, index + 1, newelements, index, nummoved);
// 更新底层数组引用为新数组
array = newelements;
}
// 返回被移除的元素
return oldvalue;
} finally {
// 释放锁
lock.unlock();
}
}
remove() 函数的处理逻辑跟 add() 函数类似：先通过加锁保证写时复制操作的线程安全性，然后申请一个大小比原始数组大小小一的新数组 newelements。除了待删除数据之外，我们将原始数组中的其他数据统统拷贝到 newelements，拷贝完成之后，我们将 array 引用指向 newelements。
2.2.3、set() 函数
set() 函数的代码实现如下所示
public e set(int index, e element) {
// 获取锁，确保在多线程环境下只有一个线程能进行写操作
lock.lock();
try {
// 获取指定索引处的旧值
e oldvalue = get(array, index);
// 如果旧值与新值不同，才进行更新操作
if (oldvalue != element) {
// 获取当前数组的长度
int len = array.length;
// 使用 arrays.copyof() 方法创建一个新数组，并将现有数组的元素复制到新数组中
// arrays.copyof() 方法底层依赖 native 方法 system.arraycopy() 来实现复制操作，速度较快
object[] newelements = arrays.copyof(array, len);
// 将新元素放置到指定索引处
newelements[index] = element;
// 更新底层数组引用为新数组
array = newelements;
}
// 返回旧值
return oldvalue;
} finally {
// 释放锁
lock.unlock();
}
}
在 set() 函数中，跟 add() 函数、remove() 函数的类似，通过加锁确保线程安全，在旧值与新值不同时复制底层数组并替换指定索引处的元素，最后更新数组引用并释放锁。
2.3、copyonwritearrayset 的实现
copyonwritearrayset 使用 copyonwritearraylist 作为底层数据结构，通过写时复制的方式保证线程安全。
public class copyonwritearrayset<e> extends abstractset<e> {
// 底层数据结构使用 copyonwritearraylist 来存储元素
private final copyonwritearraylist<e> al;
// 默认构造函数，初始化底层的 copyonwritearraylist
public copyonwritearrayset() {
al = new copyonwritearraylist<e>();
}
// 添加元素到集合中，如果元素不存在则添加并返回 true，否则返回 false
public boolean add(e e) {
return al.addifabsent(e);
}
// 从集合中移除指定元素，如果移除成功则返回 true，否则返回 false
public boolean remove(object o) {
return al.remove(o);
}
// 判断集合中是否包含指定元素，如果包含则返回 true，否则返回 false
public boolean contains(object o) {
return al.contains(o);
}
// 省略其他方法和实现细节...
}
添加元素时，只有在元素不存在时才会添加；移除和检查元素的方法直接委托给底层的 copyonwritearraylist 实现。整个实现确保了高并发环境下的安全性和一致性。
3、写实复制的特性
3.1、读多写少
从上述 copyonwritearraylist 的源码和性能测试结果可以得出以下结论：
-
写操作需要加锁：所有的写操作（如
add、set、remove等）都需要获取锁，确保线程安全性，因此这些操作只能串行执行； -
写时复制：每次写操作都需要创建数组副本并进行数据拷贝，这涉及大量的数据搬移，导致写操作的执行效率非常低；
-
读多写少的场景：由于写操作的高开销，
copyonwritearraylist适用于读多写少的应用场景。在这种场景下，读操作可以并发执行，且无需加锁。
以下是一个性能测试的示例代码，用于比较 copyonwritearraylist 和 arraylist 在执行大量写操作时的耗时：
public class demo {
public static void main(string[] args) {
list<integer> cowlist = new copyonwritearraylist<>();
long starttime = system.currenttimemillis();
for (int i = 0; i < 100000; i++) {
cowlist.add(i);
}
system.out.println("copyonwritearraylist耗时: " + (system.currenttimemillis() - starttime) + " 毫秒");
list<integer> list = new arraylist<>();
starttime = system.currenttimemillis();
for (int i = 0; i < 100000; i++) {
list.add(i);
}
system.out.println("arraylist耗时: " + (system.currenttimemillis() - starttime) + " 毫秒");
}
}
这里我执行的结果是：copyonwritearraylist 执行 100000 次写操作耗时约 2098 毫秒。arraylist 执行同样数量的写操作仅耗时约 2 毫秒。copyonwritearraylist 的耗时是 arraylist 的 1000 多倍，说明在写操作频繁的场景下，copyonwritearraylist 的性能表现非常差。
3.2、弱一致性
copyonwritearraylist 由于写时复制的特性，写操作的结果并不会立即对读操作可见。写操作在新数组上执行，而读操作在原始数组上执行，这就导致在 array 引用指向新数组之前，读操作只能读取到旧的数据。这种现象被称为弱一致性。
在示例代码中，存在两个线程：一个线程调用 add() 函数添加数据，另一个线程调用 sum() 函数遍历容器求和。
public class demo {
private list<integer> scores = new copyonwritearraylist<>();
public void add(int idx, int score) {
scores.add(idx, score); // 将数据插入到 idx 下标位置
}
public int sum() {
int ret = 0;
for (int i = 0; i < scores.size(); i++) {
ret += scores.get(i);
}
return ret;
}
}
重复统计问题的产生：假设一个线程在执行 add(int idx, int score) 方法向 scores 列表中添加数据的同时，另一个线程在执行 sum() 方法遍历 scores 列表求和。这种情况下，可能会发生以下情况：
-
线程 a 执行
add()方法：线程 a 调用scores.add(idx, score)方法，底层会创建一个新的数组并将原数组的内容复制到新数组，然后将新元素添加到新数组中； -
线程 b 执行
sum()方法：在scores列表的array引用更新之前，线程 b 开始遍历原数组；
- 写时复制导致的数据不一致：由于写时复制的特性，线程 a 操作的是新数组，而线程 b 读取的是旧数组。此时，如果线程 a 更新了
array引用，指向了新数组，而线程 b 仍然在遍历旧数组，可能会产生数据不一致的问题。
假设 scores 列表中有 n 个元素，线程 a 在第 i 个位置添加新元素，而线程 b 正在遍历第 i 个元素。如果 array 引用在此时更新，指向了新数组，线程 b 会继续遍历旧数组并重复统计第 i 个元素。这就导致了 sum() 方法可能会多统计一次该元素的值，产生错误的求和结果。
迭代器实现与弱一致性问题的解决：copyonwritearraylist 提供了一个专门的迭代器，用于遍历容器。这个迭代器在创建时，将原始数组赋值给 snapshot 引用，之后的遍历操作都是在 snapshot 上进行的。这样，即使 array 引用指向新的数组，也不会影响到 snapshot 引用继续指向原始数组，从而解决了弱一致性带来的问题。
以下是 copyonwritearraylist 中迭代器的实现代码：
// 位于 copyonwritearraylist.java 中
public iterator<e> iterator() {
return new cowiterator<e>(getarray(), 0);
}
static final class cowiterator<e> implements listiterator<e> {
private final object[] snapshot; // 指向原始数组
private int cursor;
private cowiterator(object[] elements, int initialcursor) {
cursor = initialcursor;
snapshot = elements;
}
public boolean hasnext() {
return cursor < snapshot.length;
}
@suppresswarnings("unchecked")
public e next() {
if (!hasnext()) throw new nosuchelementexception();
return (e) snapshot[cursor++];
}
// ... 省略其他方法 ...
}
使用迭代器来重构 sum() 方法，使其在遍历过程中避免重复统计的问题。重构后的代码如下：
public int sum() {
int ret = 0;
iterator<integer> itr = scores.iterator();
while (itr.hasnext()) {
ret += itr.next();
}
return ret;
}
重构后的优点：
-
避免数据不一致：由于迭代器在创建时将原始数组赋值给
snapshot，遍历操作都是在snapshot上进行，即使array引用指向新的数组，遍历过程中的数据也不会改变，从而避免了重复统计的问题； -
线程安全：迭代器提供了一种线程安全的遍历方式，确保在高并发环境下能够正确读取数据；
-
简洁代码：使用迭代器使得遍历代码更加简洁和易读，同时保证了代码的正确性和性能。
3.3、连续存储
在本篇开头，我们提到了 juc 提供了 copyonwritearraylist、copyonwritearrayset 却没有提供 copyonwritelinkedlist、copyonwritehashmap 等其他类型的写时复制容器，这是出于什么样的考虑呢？
3.3.1、数组容器
在写时复制的处理逻辑中，每次执行写操作时，哪怕只添加、修改、删除一个数据，都需要大动干戈，把原始数据重新拷贝一份。如果原始数据比较大，那么对于链表、哈希表来说，因为数据在内存中不是连续存储的，因此拷贝的耗时将非常大，写操作的性能将无法满足一个工业级通用类对性能的要求。
而 copyonwritearraylist 和 copyonwritearrayset 底层都是基于数组来实现的，数组在内存中是连续存储的
juc 使用 jvm 提供的 native 方法，如下所示，通过 c++ 代码中的指针实现了内存块的快速拷贝，因此写操作的性能在可接受范围之内。
而在平时的业务开发中，对于一些读多写少的业务场景，在确保性能满足业务要求的前提下，我们仍然可以使用写时复制技术来提高读操作性能。
// 位于 system.java 中
public static native void arraycopy(object src, int srcpos, object dest, int destpos, int length);
3.3.3、非数组容器
juc 没有提供非数组类型的写时复制容器，是出于对于一个工业级通用类的性能的考量对于非数组类型的容器，我们需要自己去开发相应的写时复制逻辑，
假设系统配置存储在文件中，在系统启动时，配置文件被解析加载到内存中的 hashmap 容器中，之后 hashmap 容器中的配置会频繁地被用到系统支持配置热更新，在不重启系统的情况下，我们希望能较实时地更新内存中的配置，让其跟文件中的配置保持一致
为了实现热更新这个功能，我们在系统中创建一个单独的线程，定时从配置文件中加载解析配置，更新到内存中的 hashmap 容器中
对于这样一个读多写少的应用场景，我们就可以使用写时复制技术，如下代码所示在更新内存中的配置时，使用写时复制技术，避免写操作和读操作互相影响。相对于 concurrenthashmap 来说，读操作完全不需要加锁，甚至连 cas 操作都不需要，因此读操作的性能更高。
public class configuration {
private static final map<string, string> map = new hashmap<>();
// 热更新, 这里不需要加锁(只有一个线程调用此函数), 也不需要拷贝(全量更新配置)
public void reload() {
map<string, string> newmap = new hashmap<>();
// ... 从配置文件加载配置, 并解析放入 newmap
map = newmap;
}
}
发表评论