为什么ConcurrentHashMap是弱一致的

本文将用到Java内存模型的happens-before偏序关系(下文将简称为hb)以及ConcurrentHashMap的底层模型相关的知识。happens-before相关内容参见:JLS §17.4.5. Happens-before Order深入理解Java内存模型以及Happens before;ConcurrentHashMap的详细介绍以及底层原理见深入分析ConcurrentHashMap。本文将从ConcurrentHashMap的get,clear,iterator(entrySet、keySet、values方法)三个方法来分析它们的弱一致问题。

ConcurrentHashMap#get

get方法是弱一致的,是什么含义?可能你期望往ConcurrentHashMap底层数据结构中加入一个元素后,立马能对get可见,但ConcurrentHashMap并不能如你所愿。换句话说,put操作将一个元素加入到底层数据结构后,get可能在某段时间内还看不到这个元素,若不考虑内存模型,单从代码逻辑上来看,却是应该可以看得到的。

下面将结合代码和java内存模型相关内容来分析下put/get方法(本文中所有ConcurrentHashMap相关的代码均来自hotspot1.6.0_18)。put方法我们只需关注Segment#put,get方法只需关注Segment#get,在继续之前,先要说明一下Segment里有两个volatile变量:counttable;HashEntry里有一个volatile变量:value

Segment#put

V put(K key, int hash, V value, boolean onlyIfAbsent) {
	lock();
	try {
		int c = count;
		if (c++ > threshold) // ensure capacity
			rehash();
		HashEntry<K,V>[] tab = table;
		int index = hash & (tab.length - 1);
		HashEntry<K,V> first = tab[index];
		HashEntry<K,V> e = first;
		while (e != null && (e.hash != hash || !key.equals(e.key)))
			e = e.next;

		V oldValue;
		if (e != null) {
			oldValue = e.value;
			if (!onlyIfAbsent)
				e.value = value;
		}
		else {
			oldValue = null;
			++modCount;
			tab[index] = new HashEntry<K,V>(key, hash, first, value);
			count = c; // write-volatile
		}
		return oldValue;
	} finally {
		unlock();
	}
}

Segment#get

V get(Object key, int hash) {
	if (count != 0) { // read-volatile
		HashEntry<K,V> e = getFirst(hash);
		while (e != null) {
			if (e.hash == hash && key.equals(e.key)) {
				V v = e.value;
				if (v != null)
					return v;
				return readValueUnderLock(e); // recheck
			}
			e = e.next;
		}
	}
	return null;
}

我们如何确定线程1放入某个变量的值是否对线程2可见?文章开头提到的JLS链接中有说到,当a hb c时,a对c可见,那么我们接下来我们只要寻找put和get之间所有可能的执行轨迹上的hb关系。要找出hb关系,我们需要先找出与hb相关的Action。为方便,这里将两段代码放到了一张图片上。

可以注意到,同一个Segment实例中的put操作是加了锁的,而对应的get却没有。根据hb关系中的线程间Action类别,可以从上图中找出这些Action,主要是volatile读写和加解锁,也就是图中画了横线的那些。

put操作可以分为两种情况,一是key已经存在,修改对应的value;二是key不存在,将一个新的Entry加入底层数据结构。

key已经存在的情况比较简单,即if (e != null)部分,前面已经说过HashEntry的value是个volatile变量,当线程1给value赋值后,会立马对执行get的线程2可见,而不用等到put方法结束。

key不存在的情况稍微复杂一些,新加一个Entry的逻辑在else中。那么将new HashEntry赋值给tab[index]是否能立刻对执行get的线程可见呢?我们只需分析写tab[index]与读取tab[index]之间是否有hb关系即可。

假设执行put的线程与执行get的线程的轨迹是这样的

执行put的线程 执行get的线程
⑧tab[index] = new HashEntry<K,V>(key, hash, first, value)
②count = c
③if (count != 0)
⑨HashEntry e = getFirst(hash);

tab变量是一个普通的变量,虽然给它赋值的是volatile的table。另外,虽然引用类型(数组类型)的变量table是volatile的,但table中的元素不是volatile的,因此⑧只是一个普通的写操作;count变量是volatile的,因此②是一个volatile写;③很显然是一个volatile读;⑨中getFirst方法中读取了table,因此包含一个volatile读。

根据Synchronization Order,对同一个volatile变量,有volatile写 hb volatile读。在这个执行轨迹中,时间上②在③之前发生,且②是写count,③是读count,都是针对同一个volatile变量count,因此有② hb ③;又因为⑧和②是同一个线程中的,③和⑨是同一个线程中的,根据Program Order,有⑧ hb ②,③ hb ⑨。目前我们有了三组关系了⑧ hb ②,② hb ③,③ hb ⑨,再根据hb关系是可传递的(即若有x hb y且y hb z,可得出x hb z),可以得出⑧ hb ⑨。因此,如果按照上述执行轨迹,⑧中写入的数组元素对⑨中的读取操作是可见的。

再考虑这样一个执行轨迹:

执行put的线程 执行get的线程
⑧tab[index] = new HashEntry<K,V>(key, hash, first, value)
③if (count != 0)
②count = c
⑨HashEntry e = getFirst(hash);

这里只是变换了下执行顺序。每条语句的volatile读写含义同上,但它们之间的hb关系却改变了。Program Order是我们一直拥有的,即我们有⑧ hb ②,③ hb ⑨。但这次对volatile的count的读时间上发生在对count的写之前,我们无法得出② hb ⑨这层关系了。因此,通过count变量,在这个轨迹上是无法得出⑧ hb ⑨的。那么,存不存在其它可替换关系,让我们仍能得出⑧ hb ⑨呢?

我们要找的是,在⑧之后有一条语句或指令x,在⑨之前有一条语句或指令y,存在x hb y。这样我们可以有⑧ hb x,x hb y, y hb ⑨。就让我们来找一下是否存在这样的x和y。图中的⑤、⑥、⑦、①存在volatile读写,但是它们在⑧之前,因此对确立⑧ hb ⑨这个关系没有用处;同理,④在⑨之后,我们要找的是⑨之前的,因此也对这个问题无益。前面已经分析过了②,③之间没法确立hb关系。

在⑧之后,我们发现一个unlock操作,如果能在⑨之前找到一个lock操作,那么我们要找的x就是unlock,要找的y就是lock,因为Synchronization Order中有unlock hb lock的关系。但是,很不幸运,⑨之前没有lock操作。因此,对于这样的轨迹,是没有⑧ hb ⑨关系的,也就是说,如果某个Segment实例中的put将一个Entry加入到了table中,在未执行count赋值操作之前有另一个线程执行了同一个Segment实例中的get,来获取这个刚加入的Entry中的value,那么是有可能取不到的!

此外,如果getFirst(hash)先执行,tab[index] = new HashEntry<K,V>(key, hash, first, value)后执行,那么,这个get操作也是看不到put的结果的。

……

正是因为get操作几乎所有时候都是一个无锁操作(get中有一个readValueUnderLock调用,不过这句执行到的几率极小),使得同一个Segment实例上的put和get可以同时进行,这就是get操作是弱一致的根本原因。Java API中对此有一句简单的描述:

Retrievals reflect the results of the most recently completed update operations holding upon their onset.

也就是说API上保证get操作一定能看到已完成的put操作。已完成的put操作肯定在get读取count之前对count做了写入操作。因此,也就是我们第一个轨迹分析的情况。

ConcurrentHashMap#clear

clear方法很简单,看下代码即知。

public void clear() {
	for (int i = 0; i < segments.length; ++i)
		segments[i].clear();
}

因为没有全局的锁,在清除完一个segments之后,正在清理下一个segments的时候,已经清理segments可能又被加入了数据,因此clear返回的时候,ConcurrentHashMap中是可能存在数据的。因此,clear方法是弱一致的。

ConcurrentHashMap中的迭代器

ConcurrentHashMap中的迭代器主要包括entrySet、keySet、values方法。它们大同小异,这里选择entrySet解释。当我们调用entrySet返回值的iterator方法时,返回的是EntryIterator,在EntryIterator上调用next方法时,最终实际调用到了HashIterator.advance()方法,看下这个方法:

final void advance() {
	if (nextEntry != null && (nextEntry = nextEntry.next) != null)
		return;

	while (nextTableIndex >= 0) {
		if ( (nextEntry = currentTable[nextTableIndex--]) != null)
			return;
	}

	while (nextSegmentIndex >= 0) {
		Segment<K,V> seg = segments[nextSegmentIndex--];
		if (seg.count != 0) {
			currentTable = seg.table;
			for (int j = currentTable.length - 1; j >= 0; --j) {
				if ( (nextEntry = currentTable[j]) != null) {
					nextTableIndex = j - 1;
					return;
				}
			}
		}
	}
}

这个方法在遍历底层数组。在遍历过程中,如果已经遍历的数组上的内容变化了,迭代器不会抛出ConcurrentModificationException异常。如果未遍历的数组上的内容发生了变化,则有可能反映到迭代过程中。这就是ConcurrentHashMap迭代器弱一致的表现。

总结

ConcurrentHashMap的弱一致性主要是为了提升效率,是一致性与效率之间的一种权衡。要成为强一致性,就得到处使用锁,甚至是全局锁,这就与Hashtable和同步的HashMap一样了。

原创文章,转载请注明: 转载自并发编程网 – ifeve.com本文链接地址: 为什么ConcurrentHashMap是弱一致的



丁 一

英文名ticmy,本站的翻译主编,主要负责译文的翻译和校对工作,目前就职于阿里巴巴,对并发编程、JVM运行原理、正则等颇有兴趣;个人博客:http://www.ticmy.com/;同时,还是户外摄影爱好者。

Latest posts by 丁 一 (see all)

FavoriteLoading添加本文到我的收藏
  • Trackback are closed
  • Comments (16)
  1. 有用,收藏,下次再来!

  2. 不懂代码的路过。

    • Snway
    • 04/16. 2013 9:59am

    总结得不错,支持一下前辈

    • Snway
    • 04/16. 2013 10:06am

    是否可以通过 外部加锁方式 来避免弱一致性所带来的问题?

    • trytocatch
    • 04/27. 2013 10:06pm

    恕我直言,这样去评论ConcurrentHashMap有点高级黑的味道,没看懂的人还以为它有缺陷呢。
    如果有锁的话,只有一个线程进入同步块,很容易保证前后关系,因为我完成了自己的操作,还没释放锁时,别人都不能进入同步块,本处理所达到的状态肯定没被修改。
    如果去掉锁,那么代码块的关系就变成了点的关系,例子1的put与get的点就是步骤2和步骤3,也就是说如果步骤2先于步骤3执行,那么我必定能看到put的结果(这也是happens-before保证的),但作者非要将这两个点移到步骤8和步骤9上去,这样没意义吧?从现实逻辑上讲也是没意义的。就像是别人执行了一半,还没完呢,我却在这报怨没取到它的结果。从方法这个“宏观”层面来讲,put方法执行完之后,get肯定能看到put的结果,这句话是有意义的,比如在同一个线程里执行这两个操作,肯定是一个方法执行完再执行另一个方法,所以不存在上面说的“问题”。
    无锁并发,就是把原来的竞争块变成了点,为成了一个一个的点,就不存在冲突了,并且前后顺序的关键点不是原来的数据写入或读取,而是用来同步的标记之类的读写,上面就是count变量的读写,是一种思维的转变。如果要保证一个并发工具,在执行某个操作后保持该状态,那这就是锁的使用场景
    如果不对之处,还请指正。

    • 黑它倒是不至于。你说的没错,文中我也引用了API的这句话“Retrievals reflect the results of the most recently completed update operations holding upon their onset”,但是没有考虑这些问题的时候,对这句话不会有太多感受。用一个东西的时候,总是对其知道的越多越有把握。实际上这篇是为了回答http://ifeve.com/concurrenthashmap/这条评论。

      • 貌似理解是一样的,只是觉得您文中的说法有点不妥,我认为使用者完全可不关心这些,这并不影响他正确使用该HashMap。
        因为一旦能观测到(或确定)put先于get执行,那么get肯定能取到put的结果
        另外,像迭代器一样,使用者既然知道该Map使用在多线程环境下,那他也就应该知道,使用过程中,其它进程可能进行修改,如果不想它在迭代过程中发生修改,那就该在相应的地方加上锁,这是很显而易见的事情。
        所以我认为,所谓的“弱一致性”是不会带来任何问题的

          • lis
          • 04/27. 2017 3:19pm

          感觉作者说的没啥不妥的。弱一致性带来的问题就是作者描述的可能会取不到值。加锁来保证强一致性自然是可以解决文章中说的问题。弱一致性的问题本身是来权衡性能和效率的,只不过ConcurrentHashMap的实现为了效率选择了弱一致性

        • lecky
        • 07/15. 2015 3:45pm

        您好,我有一个问题:
        对于这句话:“也就是说API上保证get操作一定能看到已完成的put操作。已完成的put操作肯定在get读取count之前对count做了写入操作。因此,也就是我们第一个轨迹分析的情况。”
        既然上面分析中存在轨迹二的可能,请问jvm是怎么保证get操作一定能看到已完成的put操作的?如果是这样保证的话,那岂不是跟get方法加锁一样的?

        • lecky
        • 07/15. 2015 5:17pm

        最近在学习java并发容器,查了资料,还是无法理解上面这两个问题,请问丁老师能不能帮我解惑:
        concurrentHashMap是怎么解决put方法和get方法在多线程并发访问情况下,get方法可能读取不到put方法修改之后的值的?还是说concurrentHashMap本身的弱一致性就体现在这里,不需要解决,而是在具体使用的过程中根据需求选择使用或者不使用concurrentHashMap?

      • lecky
      • 07/15. 2015 3:57pm

      trytocatch你好,我有几个问题想请教一下:
      对于这一句话:“如果去掉锁,那么代码块的关系就变成了点的关系,例子1的put与get的点就是步骤2和步骤3”
      请问:put和get点在步奏2、步奏3上是怎么确定的?

      对于这一句话:“从方法这个“宏观”层面来讲,put方法执行完之后,get肯定能看到put的结果,这句话是有意义的。比如在同一个线程里执行这两个操作,肯定是一个方法执行完再执行另一个方法,所以不存在上面说的“问题””
      请问:在get方法没有加锁的情况下,是怎么保证作者文章中执行轨迹二不出现的?
      对于后面这个例子
      请问:同一个线程的条件在这里有什么意义?happen-before保证在单线程程序中这个例子的正确定,但是在多线程并发的情况下,这个例子是想说明什么?

      • 1、put和get点在步奏2、步奏3上是怎么确定的?
        这个是根据这两个方法的同步实现方式确定的,它是用volatile变量count,依据happen-before来完成的,我指出的这两个点,只是其中的两个,如果键已存在,put方法走了另外的分支,那还有其它的点。
        2、在get方法没有加锁的情况下,是怎么保证作者文章中执行轨迹二不出现的?
        我已经说了,如果put方法执行完(注意是执行完,不是执行一半),get肯定能看到put的结果,文中的轨迹2是穿插执行。为什么要保证轨迹二不出现?我只是把值放进去了,都还没发通知(volatile写),你们get不到值,这不很正常么?谁告诉你我把值放进去了?取不到值还来骂我?
        要以通知为准!这也就是我上面说的“点”。
        不加锁,是没办法保证轨迹二不出现的,尝试去保证这个,只能说你还停留在同步块的思考方式上。
        3、同一个线程的条件在这里有什么意义?
        同一个线程执行put和get,必定不会出现轨迹二这种穿插执行的情况,这也就是我说的能保证put在get之前执行的一种场景,你还可以用额外happens-before来得出在多线程环境下,put先于get执行的前提,但在此场景下,就必定不会是轨迹二了。

    • cocode
    • 01/13. 2015 1:55pm

    put代码有问题么?

    • cocode
    • 01/13. 2015 1:57pm

    final V put(K key, int hash, V value, boolean onlyIfAbsent) {
    HashEntry node = tryLock() ? null :
    scanAndLockForPut(key, hash, value);
    V oldValue;
    try {
    HashEntry[] tab = table;
    int index = (tab.length – 1) & hash;
    HashEntry first = entryAt(tab, index);
    for (HashEntry e = first;;) {
    if (e != null) {
    K k;
    if ((k = e.key) == key ||
    (e.hash == hash && key.equals(k))) {
    oldValue = e.value;
    if (!onlyIfAbsent) {
    e.value = value;
    ++modCount;
    }
    break;
    }
    e = e.next;
    }
    else {
    if (node != null)
    node.setNext(first);
    else
    node = new HashEntry(hash, key, value, first);
    int c = count + 1;
    if (c > threshold && tab.length < MAXIMUM_CAPACITY)
    rehash(node);
    else
    setEntryAt(tab, index, node);
    ++modCount;
    count = c;
    oldValue = null;
    break;
    }
    }
    } finally {
    unlock();
    }
    return oldValue;
    }

    • OnceIme
    • 10/19. 2016 3:45pm

    JDK1.8将ConcurrentHaspMap修改了很多,弃用了segment了吧,优化了很多

You must be logged in to post a comment.

return top