Java 容器 - 集合世界的fail-fast机制 和 CopyOnWriteArrayList 源码详解

Richard_Yi 2019年07月17日 105次浏览

带你了解集合世界的fail-fast机制 和 CopyOnWriteArrayList 源码详解

前言

知识点概览:

  • 容器中的设计模式

  • 从Arrays.asList() 看集合与数组的关系

  • 集合世界中的 fail-fast 机制

    • 什么是 fail-fast 机制
    • ArrayList.sublist() 有什么坑?
    • foreach 循环里为什么不能进行元素的 remove/add 操作?
  • 集合世界中的 fail-safe 机制

    • copy-on-write 机制
  • CopyOnWriteArrayList

    • 关键知识点
    • 读写操作
    • 遍历 - COWIterator
    • 缺点 和 使用时需要注意的点
    • 提问

容器中的设计模式

1.迭代器模式

迭代器模式指的就是 提供一种方法顺序访问一个聚合对象中各个元素, 而又无须暴露该对象的内部表示,为遍历不同的聚合结构提供一个统一的接口。

  • Collection 继承了 Iterable 接口,其中的 iterator() 方法能够产生一个 Iterator 对象,通过这个对象就可以迭代遍历 Collection 中的元素。
  • 从 JDK 1.5 之后可以使用foreach 方法来遍历实现了 Iterable 接口的聚合对象

2. 适配器模式

适配器模式使得原本由于接口不兼容而不能一起工作的那些类可以一起工作。

Arrays.asList(T... a)体现的就是适配器模式。

拿生活中的例子作比方:我很早以前用的是3.5mm耳机孔的耳机,后面我换手机了,只能用type-c的耳机,通过type-c转接头我以前的耳机还是能用,这里面就用了适配器模式;在上面的例子中,入参数组就是3. 5mm耳机,Arrays.asList()这整个方法就是起到适配器type-c转接头的作用,List就是支持我type-c口的耳机

从 Arrays.asList() 看集合与数组的关系(内含坑)

数组与集合都是用来存储对象的容器,前者性质单一、简单易用;后者类型安全,功能强大,而两者之间必然有相互转换的方式。

由于两者的特性存在很大的差别,所以在转换过程当中,如果不去详细了解背后的转换方式,很容易产生意料之外的问题。

在数组转集合的过程中,需要注意是否使用了视图方式

这里说的视图,指的就是一个具有限制的集合对象,只是把原有数据展现出来给你看,例如不可更改视图,子视图等等,这些视图对于原对象具有不同的操作权限。

Arrays.asList() 为例,它把数组转成集合时,不能修改其修改集合相关的内容。它的add/remove/clear方法会抛出UnsupportedOperationException

上述代码可以证明可以通过set方法修改元素的值,原有数组相应位置的值同时也会被修改,但是不能进行修改元素个数的任何操作,否则就会抛异常。

有的人可能就会问了,返回的是ArrayList类,为什么不能对这个集合进行修改呢?

因为这个ArrayList并不是我们平常使用的ArrayList类,这里是个冒牌货,是Arrays工具类中的一个内部类而已。

这个类非常的简单,仅提供了改和查相关方法的实现,让我们来看一下:

至于增删的操作会抛出会抛出UnsupportedOperationException,是在这个假类的父类AbstractList中实现的

所以当你的业务场景中,数组转成集合之后,如果可能会对集合进行增和删的操作,请使用真ArrayList来创建一个新集合。

List<Object> list = new java.util.ArrayList<Object>(Arrays.asList(数组对象))

集合世界中的 fail-fast 机制

fail-fast 机制 集合世界中比较常见的错误检测机制,防止在对集合进行遍历过程当中,出现意料之外的修改,会通过Unchecked 异常暴力的反应出来。

实现的方式就是:

当前线程会维护一个计数比较器,即 expectedModCount,记录已经修改的次数。在进入遍历时,会把实时修改次数 modCount赋值给 expectedModCount,如果这两个数据不相等,则抛出异常。

java.util下的集合类都是属于fail-fast的,而相对应的,j.u.c下的集合类都是fail-safe,fail-safe在之后会介绍。

**需要注意的是,即使不是多线程环境,如果单线程违反了规则,同样也有可能会抛出改异常。**比如ArrayList.subList()场景,比如foreach loop 中对集合进行add/remove操作。

ArrayList.sublist() 有什么坑?

subList()场景在《阿里开发手册》上也是强制要求重点注意的一个规定。

List masterList = new ArrayList();
// ... 对 masterList 进行一系列的set()操作,此处省略
List branchList = masterList.subList(0,3);

如上述场景,当我们需要从一个主列表master中获取子列表branch时,原集合元素个数的修改,会导致子列表的遍历、增加、删除均会产生ConcurrentModificationException

foreach 循环里为什么不能进行元素的 remove/add 操作?

这也是《阿里开发手册》中对集合处理的一个强制规约。

原因在于,foreach循环这样的写法,其实是Java本身给我们的一个语法糖,当你对编译之后class文件进行反编译之后,你会发现,增强的for循环,其实是依赖了while循环和Iterator实现的。

Iterator iterator = list.iterator();
do
{
    if(!iterator.hasNext())
        break;
    Object obj = iterator.next();
    // 业务逻辑 瞎编的
    if(canExecute()) {
    	list.remove(object)    
    }
} while(true);

在增强for循环中,集合遍历是通过iterator进行的。

foreach循环这里要注意哦,你如果在foreach循环中调用了 集合的add/remove 方法,最后编译出来的还是调用的逻辑是没有变化的。

而在增强for循环中,集合遍历是通过iterator进行的。

冲突点就发生了,ArrayList 和 LinkedList中 add/remove方法的源码中,虽然实现不一定相同,但是都会调用modCount++,这行代码,当你通过iterator进行迭代时,每一次调用next()方法,都会调用一次checkForComodification()方法检查集合在遍历过程当中被修改。

关键就在于集合自带的add/remove方法不会去更新迭代器自身的expectedModCount值啊。

手册里面为什么让你使用Iterator的add/remove方法?因为除了调用对应集合的对应add/remove方法的同时,它还会去修改自身的expectedModCount值.

一言以蔽之,会抛出ConcurrentModificationException异常,是因为我们的代码中使用了增强for循环,而在增强for循环中,集合遍历是通过iterator进行的,但是元素的add/remove却是直接使用的集合类自己的方法。这就导致iterator在遍历的时候,会发现有一个元素在自己不知不觉的情况下就被删除/添加了,就会抛出一个异常,用来提示用户,可能发生了并发修改

上述案例应引起对删除元素时的 fail-fast 警觉。我们可以使用Iterator机制进行遍历时的删除,如果是多线程并发情况的话,还需要在Iterator遍历时加锁,如下源码。

Iterator<String> iterator = list.iterator();
while(it.hasNext()) {
    synchronized(对象) {
        String item = iterator.next();
        if (删除元素的条件) {
            iterator.remove();
        }
    }
}

或者,可以直接使用JUC下对应的线程安全集合,CopyOnWriteArrayList来代替。使用迭代器遍历的时候就不用额外加锁,也不会抛出ConcurrentModificationException异常。

集合世界中的 fail-safe 机制

与 fail-fast 相对应的,就是 fail-safe 机制;在J.U.C包中集合都是有这种机制实现的。

fail-safe 指的是:在安全的副本(或者没有提供修改操作的正本)上进行遍历,集合修改和副本的遍历是没有任何关系的,但是缺点也很明显,就是读取不到最新的数据

这也是 CAP 理论中 C (Consistency) 和 A (Availability) 的矛盾,即一致性与可用性之间的矛盾。

CAP 定理的含义 -- 阮一峰

copy-on-write 机制

Copy-on-write 是解决并发的的一种思路,也是指的是实行读写分离,如果执行的是写操作,则复制一个新集合,在新集合内添加或者删除元素。待一切修改完成之后,再将原集合的引用指向新的集合

这样的好处就是,可以高并发地对COW进行读和遍历操作,而不需要加锁。因为当前集合不会添加任何元素。

前面我们有提到过线程安全的集合Vector,但是Vector的加锁粒度太大,性能差,所以在并发环境下,推荐JUC包下的的CopyOnWriteArrayList来代替。CopyOnWriteArrayList就是COW家族中的一员。

一般我们认为,CopyOnWriteArrayList 是 同步List 的替代品,CopyOnWriteArraySet 是同步Set 的替代品。

By the way,关于**写时复制(copy-on-write)**的这种思想,这种机制,并不是始于Java集合之中,在Linux、Redis、文件系统中都有相应思想的设计,是一种计算机程序设计领域的优化策略。

详见本篇文章 COW奶牛!Copy On Write机制了解一下

CopyOnWriteArrayList

前面讲的实际大多是概念性的东西,下面详细剖析下CopyOnWriteArrayList ,读一读部分源码,并且探讨几个在学习过程中的疑问。

关键知识点

  • 核心理念就是读写分离。
  • 写操作在一个复制的数组上进行,读操作还是在原始操作上进行,读写分离,互不影响。
  • 写操作需要加锁,防止并发写入时导致数据丢失。
  • 写操作结束之后需要把 原始数组 指向新的复制数组。

读写操作

以写 - add() 方法 和 读 - get() 方法为例

通过代码我们可以知道:写操作加锁,防止并发写入时导致数据丢失,并复制一个新数组,增加操作在新数组上完成,将array指向到新数组中,最后解锁。

至于读操作,则是直接读取array数组中的元素。

遍历 - COWIterator

到现在,实际上还是没有解释为什么CopyOnWriteArrayList 在遍历时,对其进行修改而不抛出异常?

前面我们知道,不管是foreach 循环还是Iterator方式遍历,实际上都是使用Iterator遍历。那么就直接来看下CopyOnWriteArrayList 的iterator()方法。

 	public Iterator<E> iterator() {
        return new COWIterator<E>(getArray(), 0);
    }

可以看到对应的迭代器是COWIterator,看这个名字就可以知道这个是基于COW机制的,那么具体呢?

可以看到COWIterator的构造方法,将集合的array数组传入,实际上就是COWIterator内部维护了一个对象指向集合的数组。

也就是说你使用COWIterator进行遍历的时候,如果你修改了集合,集合内部的array就指向了新的一个数组对象,而COWIterator内部的那个array还是指向初始化时传进来的旧数组,所以不会抛异常,因为旧数组永远没变过。

缺点 和 使用时需要注意的点

看完上面的解析,大概就能知道CopyOnWriteArrayList 在使用过程中的一些缺点了(实际上就是COW机制的缺点):

  • 内存占用:因为CopyOnWriteArrayList 的每次写操作,都会复制一个新集合,所以如果对其进行频繁写入,会在短时间内造成大量的内存占用。
  • 数据一致性:这个前面提到过,再提一遍,CopyOnWrite容器只能保证数据的最终一致性,不能保证数据的实时一致性

使用时注意的点:

  • 尽量在读多写少的场景下去使用CopyOnWriteArrayList
  • 尽量设置合理的容量初始值,因为扩容代价大
  • 使用批量删除或批量添加方法,如addAll()或removeAll()操作,在高并发请求下,可以攒一下要添加或者删除的元素,避免增加一个元素复制整个集合的情况

提问

Q: 为什么使用final ReentrantLock lock = this.lock这样的写法?

我在看CopyOnWriteArrayList 源码的时候,发现写操作相关的方法内部,都是先将实例变量的lock对象引用赋值给方法的局部变量,然后再进行锁操作。

我那时候就纳闷了很久,为什么要这么写?直接调用实例中lock对象进行锁操作不是就可以了吗?为什么要“多此一举”呢?

查阅了Stack Overflow上相关的问题才知道,这实际上就是小小的性能优化技巧。

理论上,访问局部变量比访问字段更快,也可能只占用更小的字节码。 但是HotSpot编译器实际上可以优化对寄存器调用的字段访问,所以这种写法和直接访问字段目前来说应该没有什么差别。

btw,CopyOnWriteArrayList 是jdk1.5之后引进的。体现了Doug Lea的性能优化的极致追求。

实际上目前的JVM性能优化的技术,两种写法的性能已经是没有差别了。

在JDK11 中,这个实际上已经无用的操作,已经被删去了。

最后

本章的内容到这里结束了,希望能对你有所帮助。如果有什么想要探讨的随时欢迎评论区留言。

参考

  1. 《码出高效》
  2. 《阿里巴巴Java开发手册》
  3. github cs-note
  4. https://juejin.im/post/5c8717ad5188257dda56c381#heading-3
  5. Why CopyOnWriteArrayList use getArray() to access an array reference?