CodeMilk

life is not just live

什么是fail-fast与fail-safe

fail-fast与fail-safe

在Collection集合的各个类中,有线程安全和线程不安全这2大类的版本。

对于线程不安全的类,并发情况下可能会出现fail-fast情况;而线程安全的类,可能出现fail-safe的情况。

快速失败(fail—fast)是java集合中的一种机制, 在用迭代器遍历一个集合对象时,如果遍历过程中对集合对象的内容进行了修改(增加、删除、修改),则会抛出Concurrent Modification Exception。

安全失败(fail-sage)保存了该集合对象的一个快照副本。你可以并发读取,不会抛出异常,但是不保证你遍历读取的值和当前集合对象的状态是一致的!

fail-fast

来看一下线程不安全的类ArrayList,它实现fail-fast主要靠一个字段modCount。来从头认识一下它。

首先找到引用它的地方:

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
32
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}

private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private void ensureExplicitCapacity(int minCapacity) {
modCount++;

// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}

public E remove(int index) {
rangeCheck(index);

modCount++;
E oldValue = elementData(index);

int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work

return oldValue;
}

可以看出,在增加元素,删除元素时都会对modCount值加一。当我们查看更新,查找的代码时并没有找到对modCount的修改。

modCount字段翻译过来就是修改次数,再结合上面的代码可以了解到只有在结构发生变化,数量增减的时候才会修改。查找不会对结构发生变化也不用修改,至于更新操作,虽然它修改了值,但是在结构上总体的数量没有改变,结构上指的是:是谁不重要,有就行。

我们继续查找用到modCount字段的地方:

1
2
3
4
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}

找到这样的一段代码,判断modCount与另一个值是否相同,如果不相同就抛出异常!再来找到expectedModCount定义的地方。

1
2
3
4
5
6
7
8
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;

Itr() {}
...
}

从这里看到expectedModCount=modCount。小朋友你是否有很多疑惑?为什么这里将modCount赋值给expectedModCount,后面又需要判断它们是否相等呢?

其实我们将这两个字段翻译过来,一个是修改数量,一个是期望的修改数量。当我们看到这两个词时脑子里应该有了一些猜想。

这个expectedModCount是迭代器在子类实现中定义的一个成员变量。当我们使用迭代器后就将这个变量值初始化完成了,如果我们在使用迭代器期间结构发生了变化,那么就会遇到两者不一样的情况。

我们来看这样的一段代码,演示一下这种错误情况:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void main(String[] args) {
List list = new ArrayList();
list.add("a");
list.add("b");
list.add("c");
list.add("d");
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
String s = iterator.next();
System.out.println(s);
// 修改集合结构
if ("b".equals(s)) {
list.remove(s);
}
}
}

这段代码中,我先添加了4条数据,添加完成后listmodCount=4。这时我调用了迭代器方法,此时iterator中的expectedModCount=4

然后我利用迭代器的方法进行取值,删除了其中一个数据,这时listmodCount=3,当我们下一次使用迭代器循环时,检测到expectedModCount=4 != modCount,这时就会抛出异常。

fail-safe

上面的代码是线程不安全的ArrayList的源码,接下来看一下线程安全的类ConcurrentHashMap是怎样实现的。

1
2
3
4
public Set<Map.Entry<K,V>> entrySet() {
EntrySetView<K,V> es;
return (es = entrySet) != null ? es : (entrySet = new EntrySetView<K,V>(this));
}

调用map的迭代时选择了entrySet方法,这里会先进行判断一个变量es是否为空,不为空则返回,为空则进行了一个实例化,并且传入了当前对象,即传入了当前的ConcurrentHashMap对象,找一下调用的这个方法。

1
2
3
4
5
6
static final class EntrySetView<K,V> extends CollectionView<K,V,Map.Entry<K,V>>
implements Set<Map.Entry<K,V>>, java.io.Serializable {

EntrySetView(ConcurrentHashMap<K,V> map) { super(map); }
...
}

在这个构造函数中又调用了父类的构造函数,我们还需要继续向上找

1
2
3
4
5
6
7
8
9
10
abstract static class CollectionView<K,V,E>
implements Collection<E>, java.io.Serializable {
private static final long serialVersionUID = 7249069246763182397L;
final ConcurrentHashMap<K,V> map;
CollectionView(ConcurrentHashMap<K,V> map) { this.map = map; }

public abstract Iterator<E> iterator();

...
}

找到了这个父类,它在这里将我们上面穿入的ConcurrentHashMap对象实例赋值到成员变量map上。

并且有一个抽象方法iterator(),并且这个方法有3个实现,分别是EntrySetView,KeySetView,ValueSetView,这也是分别对应entrySet(),keySet()valueSet()的实现。进入到EntrySetView中看一下:

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
static final class EntrySetView<K,V> extends CollectionView<K,V,Map.Entry<K,V>>
implements Set<Map.Entry<K,V>>, java.io.Serializable {
private static final long serialVersionUID = 2249069246763182397L;
EntrySetView(ConcurrentHashMap<K,V> map) { super(map); }

public Iterator<Map.Entry<K,V>> iterator() {
ConcurrentHashMap<K,V> m = map;
Node<K,V>[] t;
int f = (t = m.table) == null ? 0 : t.length;
return new EntryIterator<K,V>(t, f, 0, f, m);
}
}

static final class EntryIterator<K,V> extends BaseIterator<K,V>
implements Iterator<Map.Entry<K,V>> {
EntryIterator(Node<K,V>[] tab, int index, int size, int limit,
ConcurrentHashMap<K,V> map) {
super(tab, index, size, limit, map);
}

public final Map.Entry<K,V> next() {
Node<K,V> p;
if ((p = next) == null)
throw new NoSuchElementException();
K k = p.key;
V v = p.val;
lastReturned = p;
advance();
return new MapEntry<K,V>(k, v, map);
}
}

经过上面的代码,可以看出在这里它将当前实例赋值到一个新的map中,相当于在调用entrySet时做了一个镜像,然后操作时是在镜像上进行操作,在操作时如果对数据有修改,也不会影响到镜像里面的内容。但是同样的,在镜像里面做迭代也不会有创建镜像后新增的数据。

总结

在线程不安全的类中使用使用fail-fast来尽最大努力抛出ConcurrentModificationException异常,因为在更新时虽然数据发生了变化,但是在结构上并没变化,只能在增加,删除时保证了安全。

在线程安全的类中,比如java.util.concurrent包下的容器都是fail-safe。它内部实现是保存了创建一个快照副本,读取这个快照副本的数据。它的缺点是不能保证返回集合更新后的数据,另外创建新的快照也需要一些相应的时间空间开销。