Java进阶系列：由CopyOnWriteArrayList讲到一种高效并发数据结构
AI内容生成2019-09-05 22:05
目录
1. 概览2. CopyOnWriteArrayList简述3. CopyOnWriteArrayList深入分析3.4.1 迭代的时候插入3.4.2 迭代删除/添加3.1 主要数据结构3.2 获取3.3 插入（可窥其原理）3.4 迭代3.5 CopyOnWriteArrayList特性总结4. 改进：一种常见的双buffer缓冲设计5. 总结
1. 概览
本文来探究一个有意思的类： CopyOnWriteArrayList
所在包：java.util.concurrent：所以它是一个与并发相关的类父类/接口：List，Cloneable，Serializable，RandomAccess：是list可序列化2. CopyOnWriteArrayList简述
CopyOnWriteArrayList用了一个有意思的技术实现了线程安全（不需要synchronization）。
内部数据会被copy当调用这个类的任何有关修改的操作的时候（比如add，remove），CopyOnWriteArrayList里面整个的内容都会被重新copy一份读写分离所以当我们做修改操作的时候，我们修改的是重新copy的一份数据同时依旧可以顺畅的迭代读取数组里面的内容。因为当我们调用iterator()函数的时候，其实得到也是一个CopyOnWriteArrayList内部内容的snapshot。可能的数据延迟这个snapshot是从iterator()调用的时刻起，被创建的，所以如果在同时有其他线程add or remove元素，这次迭代是看不到的,只有在后续操作中才可以。
上面我画了一个大概的示意图，应该挺好懂的。
这种特性让这个数据结构非常适合：读多写少的场景。
因为如果修改数据的场景比较频繁，每次操作都copy内容，那这样的开销是受不了的
留一个问题后面讲：有没有一种改进办法，改进上面的问题？
3. CopyOnWriteArrayList深入分析
3.1 主要数据结构
lock：用于操作的时候加锁，transient修饰，不序列化array：内部真正的数组数据，volatile修饰表示一个线程对这个字段的修改，另外的线程立马可见所以可见：这个类本身的某些操作，会通过加锁来保证同步
3.2 获取
以上没有什么好分析的，看一下代码，很简单。
3.3 插入（可窥其原理）
我们来分析一个add方法（其他方法类似）
从源码，我们可以看到：
先加锁拷贝当前数组（old array）内容为新数组（new array）在新数组上执行插入使用新的替换老的所以：
整个过程对当前数组（old array）没有任何修改，当然这个时候在add的过程中，读取元素是读取的old array的数据咯。写操作会阻塞，会先得到lock，才能执行。3.4 迭代
先看一下迭代器的源码：
从源码可见：
迭代器是一个当前内容的snapshot（拷贝）（The returned iterator provides a snapshot of the state of the list）由内部类COWIterator来实现看一下COWIterator的基本结构：
果然如此。
3.4.1 迭代的时候插入
让我们来实践一下，迭代的时候插入会怎么样
首先：创建一个CopyOnWriteArrayListCopyOnWriteArrayList<Integer> myNumbers = new CopyOnWriteArrayList<>(new Integer[]{10, 13, 25, 81});
然后：拿到迭代器Iterator<Integer> myIterator = myNumbers.iterator();
其次：在创建了myIterator之后，我们往myNumbers添加数据：myNumbers.add(235);
这个时候，我们遍历myIterator，看看输出：
结果里面并没有235，因为我们要时刻记住：通过iterator()我们拿到的是，当前创建迭代器这一刻的内容的snapshot
3.4.2 迭代删除/添加
由于我们之前讲的，迭代器是一个snapshot，所以使用迭代器去删除/添加，这样的操作是不允许的（因为这样做也没有意义，根本无法改变数组本身的值，该的只是snapshot拷贝的这一份内容的），可以看一下源码实现：完全是直接抛出异常。
3.5 CopyOnWriteArrayList特性总结
opyOnWriteArrayList不保证实时一致性opyOnWriteArrayList写操作都要先拷贝一份new array，在new array中做修改，修改完了再用new array替换老数组，所以性能比较低下；opyOnWriteArrayList读操作支持随机访问，时间复杂度为O(1)；opyOnWriteArrayList读写分离，读不加锁，写加锁，且写操作会copy原数组，内存占用大；适用于读多写少的场合；opyOnWriteArrayList使用ReentrantLock做线程安全；4. 改进：一种常见的双buffer缓冲设计
第2小节，我们提了一个问题：CopyOnWriteArrayList的缺点很明显：每次写都要copy，这样如果写场景比较频繁，显然性能低下。
那么有没有更好的设计方案？
显然是有的，一种真正基于双buffer的实现方案：
在内存中维护俩分数据buffer1，buffer2（空间换时间思想），通过读写锁来控制读和写通过游标index来控制当前使用的哪一份数据每次写的时候，先加锁修改未激活的buffer1，然后切换index，加锁修改另一份数据buffer2
双buffer操作示意图这样就不需要每次修改操作，都拷贝一份内存数据，效率会高出很多。这样的设计，经常使用到高并发里面。
5. 总结
通过CopyOnWriteArrayList，学了其内部实现机制，并且知其优缺点，给出了另外一种常见双buffer设计。
其实通过本文，可以学到一种计算机朴素的思想：通过空间换时间。计算机发展到现在，层出不穷架构也好、思维也好，其他大部分都是在空间（资源占用）、时间（效率性能）之间做平衡（比如分布式思想）。
举报/反馈
0
0
收藏
分享
