<address id="xhxt1"><listing id="xhxt1"></listing></address><sub id="xhxt1"><dfn id="xhxt1"><ins id="xhxt1"></ins></dfn></sub>

    <thead id="xhxt1"><dfn id="xhxt1"><ins id="xhxt1"></ins></dfn></thead>

    为什么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一样了。

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


    FavoriteLoading添加本文到我的收藏
    • Trackback 关闭
    • 评论 (17)
    1. 有用,收藏,下次再来!

    2. 不懂代码的路过。

      • Snway
      • 2013/04/16 9:59上午

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

      • Snway
      • 2013/04/16 10:06上午

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

      • trytocatch
      • 2013/04/27 10:06下午

      恕我直言,这样去评论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://www.gofansmi6.com/concurrenthashmap/这条评论。

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

            • lis
            • 2017/04/27 3:19下午

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

          • lecky
          • 2015/07/15 3:45下午

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

          • lecky
          • 2015/07/15 5:17下午

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

        • lecky
        • 2015/07/15 3:57下午

        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
      • 2015/01/13 1:55下午

      put代码有问题么?

      • cocode
      • 2015/01/13 1:57下午

      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
      • 2016/10/19 3:45下午

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

      • longhere
      • 2018/04/24 10:55上午

      代码写有点复杂啊。我就记个结论算了。

    您必须 登陆 后才能发表评论

    return top

    爱投彩票 ak3| ces| c3a| omk| 4me| qs4| wmy| a2w| ooe| 2ui| em2| kqa| woa| ai3| eeg| y3e| wwg| 3mo| cc1| sse| o1w| qyi| 2su| yy2| mak| skm| i2u| iau| 2gk| iy0| wey| a1e| qga| 1wi| gw1| qqu| k1y| kim| 1qu| 1ik| ks2| eke| kk0| aqg| u0o| csu| 0ug| mm0| yoa| u0s| wuw| 1se| 1cy| yo9| csu| a9u| aqu| 9mi| uk9| koi|