标签归档:collection

scala雾中风景(20): MutableList迭代器的bug

上一篇,这个问题还没完,泽斌给出这个问题是因另一个问题引发的:Scala 的 for each,为什么会有且仅有一次 recursion? 引用原问题:

Scala 2.10/2.11 中,运行

val l = MutableList(16)

for (i<-l) {
    val p = i/2
    if (!(l contains p)) { 
        l += p 
    }
}

l

得到的是

MutableList[Int](16, 8, 4)

如果是返回 (16, 8)(如同 JavaScript 或 PHP)的话我能理解。或者是返回 (16, 8, 4, 2, 1, 0)(如同 Python 或 Ruby) 我也能够理解。但是返回 (16, 8, 4) 是为什么呢?

这得看看MutableList的迭代器实现了, 它在scala.collection.LinearSeqOptimized里面:

override /*IterableLike*/
def foreach[B](f: A => B) {
    var these = this
    while (!these.isEmpty) {
      f(these.head)
      these = these.tail
    }
}

不太容易直接看出来这块的问题,断点的时候发现这里会导致调试器在展示值时调用toString引起异常,我是复制了一份MutableList的代码在foreach里增加一些打印信息发现的。

我们在repl下模拟这个迭代过程,刚开始foreach的时候元素只有1个,对16进行处理,追加一个新元素8:

scala> val l = scala.collection.mutable.MutableList(16)
l: scala.collection.mutable.MutableList[Int] = MutableList(16)

scala> l += 8
res0: l.type = MutableList(16, 8)

这个追加的行为对应foreach里面的f(these.head)这一句,之后把指针指向后续链表节点:

scala> var these = l.tail
these: scala.collection.mutable.MutableList[Int] = MutableList(8)

因为刚开始var these=this,所以这次these=these.tail会得到链表的第二个元素8,然后传入8,原链表又被追加了一个元素4:

scala> l += 4
res1: l.type = MutableList(16, 8, 4)

接着继续移动指针,但这次these对象已经不是this而是单节点链表,取它的tail会得到空,导致foreach终止。所以最终原链表里有3个元素:

scala> these = these.tail
these: scala.collection.mutable.MutableList[Int] = MutableList()

虽然,这里的these与原链表是复用的,它size虽然为0,但实际可以访问后续元素:

scala> these(0)
res3: Int = 4

我觉得应该算是MutableList迭代器的bug了,它不应该使用LinearSeqOptimized里的实现,那个里面的逻辑没有考虑到集合长度可变的情况。

scala雾中风景(19): MutableList与mutable.LinkedList的问题

群里看到的问题:

scala> import scala.collection._

scala> val l = mutable.MutableList(1,2)
l: scala.collection.mutable.MutableList[Int] = MutableList(1, 2)

scala> val t = l.tail
t: scala.collection.mutable.MutableList[Int] = MutableList(2)

scala>  l += 3
res0: l.type = MutableList(1, 2, 3)

scala> t.length
res1: Int = 1

这里显示 t 的长度没有问题,但显示t的值的时候,却不是预期的:

scala> t
res2: scala.collection.mutable.MutableList[Int] = MutableList(2, 3)

怎么把l列表后来增加的3也给包含进去了。这要看这个MutableListtail方法的实现是怎么回事了。

scala.collection.mutable.MutableList里为了实现scala.collection.GenTraversableLike特质里的head, tail等方法,是通过链表scala.collection.mutable.LinkedList来存储数据。它的tail方法实现如下:

override def tail: MutableList[A] = {
    val tl = new MutableList[A]
    tailImpl(tl)
    tl
}

// this method must be private for binary compatibility
private final def tailImpl(tl: MutableList[A]) {
    require(nonEmpty, "tail of empty list")
    tl.first0 = first0.tail
    tl.len = len - 1
    tl.last0 = if (tl.len == 0) tl.first0 else last0
}

这里面要看看 tl.first0 = first0.tail 的实现是什么,在LinkedListLike里:

override def tail: This = {
    require(nonEmpty, "tail of empty list")
    next
}

它直接返回当前链表的下一个节点引用。所以当原链表末尾附加新的值时,这个 tl 链表也是可以引用到的,因为它们是复用的。

不过因为对这个tl的len设置过了,所以迭代的时候,并不会越界。并且toString方法也不会多展示不属于它的数据的:

scala> t.toString
res14: String = MutableList(2)

scala> t.foreach(print)
2

但在repl的展示上,就没有做的很严谨了,它没有调用这个对象的toString来展示它的值,而是自己把这个节点及链表后续节点的值都展示了:

scala> t
res15: scala.collection.mutable.MutableList[Int] = MutableList(2, 3)

这应该算是repl展示层面的不严谨吧。不过MutableList的实现也不太严谨,这个t虽然length是1,但后边节点如果有值的话也是可以索引到的:

scala> t(0)
res17: Int = 2

scala> t(1)
res18: Int = 3

scala> l += 4
res19: l.type = MutableList(1, 2, 3, 4)

scala> t(2)
res20: Int = 4

这也算是一个陷阱吧,mutable的集合在使用的时候要清楚它的场景和限制。

通过List.apply方法构造List的背后逻辑

通过List伴生对象的apply方法来创建实例: List("A","B") 过程发生了什么

首先,List伴生对象的apply方法接收的是一个可变参数列表,即数组:

override def apply[A](xs: A*): List[A] = xs.toList

而我们传入的Array("A","B")数组会被隐式转换为 WrappedArray 的子类型,这是在LowPriorityImplicits里定义的:

// Since the JVM thinks arrays are covariant, one 0-length Array[AnyRef]
// is as good as another for all T <: AnyRef.  Instead of creating 100,000,000
// unique ones by way of this implicit, let's share one.

implicit def wrapRefArray[T <: AnyRef](xs: Array[T]): WrappedArray[T] = {
    if (xs eq null) null
    else if (xs.length == 0) WrappedArray.empty[T]
    else new WrappedArray.ofRef[T](xs)
}

随后对这个WrappedArray 的子类型ofRef[String]类型,调用 toList 方法

不过在进行toList时用到了隐式参数CanBuildFrom,我们先看一下List伴生对象中定义的,用于生成CanBuildFrom信息的隐式方法:

/** $genericCanBuildFromInfo */
implicit def canBuildFrom[A]: CanBuildFrom[Coll, A, List[A]] =
    ReusableCBF.asInstanceOf[GenericCanBuildFrom[A]]

现在来追踪toList的执行过程,在父类TraversableOncetoList方法里调用了to方法,而这个to方法里有声明一个隐式参数。

用隐式参数CanBuildFrom构造了一个List类型的容器,把数据填充进去,再返回result

里面的隐式参数:

implicit cbf: CanBuildFrom[Nothing, A, Col[A @uV]] 

先不用管里面难懂的类型参数,编译在寻找对应的隐式参数值时,通过上面的 to[List]声明的目标类型是List,所以从List的伴生对象中去寻找,通过 canBuildFrom隐式函数得到了需要的参数,它是把一个可复用的对象造型成我们需要的CBF类型:

ReusableCBF.asInstanceOf[GenericCanBuildFrom[A]]

ReusableCBF的意思是可复用的CanBuildFrom,它在 GenTraversableFactory里定义:

通过这个CBF隐式参数帮我们构造了一个新的容器,然后把当前集合里的数据放进去,最后再调用新容器的result来得到List

通过断点,发现 b.result 时进入了 ListBuffer.toList 的代码里,也就是说这个隐式参数构造出来的新容器类型是 ListBuffer 的子类型。

最终,它返回ListBuffer类里的start成员,这个start是一个 :: 类型(List的子类)

不正当使用HashMap导致cpu 100%的问题追究

因最近hashmap误用引起的死循环又发生了一些案例,左耳朵浩子写了一篇blog 疫苗:Java HashMap的死循环,看了一下,大家的分析如出一辙。这篇blog也是好几年前写的了,之前在平台技术部的博客上贴过,随着组织结构的调整,那个博客可能不再维护,把这篇文章在这儿也保存一下。

李鹏同学在blog里写了篇关于HashMap死锁模拟的文章: http://blog.csdn.net/madding/archive/2010/08/25/5838477.aspx 做个纠正,那个不是死锁问题,而是死循环。

这个问题,我们以前讨论过。 校长之前的博客和淘宝的毕玄的《分布式Java应用:基础与实践》一书中都提到过 velocity导致cpu 100% 的bug,起因是HashMap的使用不当所致。

在之前的邮件列表里,校长提出过这个问题,当时我没仔细看,不清楚这个问题究竟是对 HashMap的误用,还是HashMap的潜在问题, 当时感觉不太可能是HashMap自身的问题,否则问题大了。应该是属于在并发的场景下错误的 使用了HashMap。昨天看了李鹏的blog后,觉得这个事情还是应该搞清楚一下;虽然我推测是链表形成闭环,但 没有去证明过。从网上找了一下: http://blog.csdn.net/autoinspired/archive/2008/07/16/2662290.aspx 里面也有提到:

产生这个死循环的根源在于对一个未保护的共享变量 — 一个”HashMap”数据结构的操作。当在 所有操作的方法上加了”synchronized”后,一切恢复了正常。检查”HashMap”(Java SE 5.0)的源 码,我们发现有潜在的破坏其内部结构最终造成死循环的可能。在下面的代码中,如果我们使得 HashMap中的entries进入循环,那 么”e.next()”永远都不会为null。
不仅get()方法会这样,put()以及其他对外暴露的方法都会有这个风险,这算jvm的bug吗?应该说不是的,这个现象很早以前就报告出来了(详细见: http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6423457)。Sun的工程师并不认为这 是bug,而是建议在这样的场景下应用”ConcurrentHashMap”,在构建可扩展的系统时应将这点 纳入规范中。

这篇翻译提到了对HashMap的误用,但它没有点破HashMap内部结构在什么样误用情况下怎么被 破坏的;我想要一个有力的场景来弄清楚。再从李鹏的blog来看,用了2个线程来put就模拟出来了,最后堆栈是在 transfer 方法上(该方法是数据扩容时将数据从旧容器转移到新容器)。 仔细分析了一下里面的代码,基本得出了原因,证明了我之前的推测。

假设扩容时的一个场景如下(右边的容器是一个长度 2 倍于当前容器的数组) 单线程情况。

我们分析数据转移的过程,主要是链表的转移。

执行过一次后的状态:

最终的结果:

两个线程并发情况下,扩容时可能会创建出 2 个新数组容器

顺利的话,最终转移完可能是这样的结果

但并发情况下,出现死循环的可能场景是什么呢? 还要详细的分析一下代码,下面的代码中重点在 do/while 循环结构中(完成链 表的转移)。

// 扩容操作,从一个数组转移到另一个数组
void transfer(Entry[] newTable) { 
    Entry[] src = table;
    int newCapacity = newTable.length; 
    for (int j = 0; j < src.length; j++) {
        Entry<K,V> e = src[j]; 
        if (e != null) {
            src[j] = null; 
            do {
                Entry<K,V> next = e.next; //假设第一个线程执行到这里 
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            } while (e != null); // 可能导致死循环
        }
    }
}

2 个线程并发情况下, 当线程 1 执行到上面第 9 行时,而线程 2 已经完成了一 轮 do/while 操作,那么它的状态如下图:
(上面的数组时线程 1 的,已经完成了链表数据的转移;下面的是线程 2 的,它 即将开始进行对链表数据的转移,此时它记录 E1 和 E2 的首位已经被线程 1 翻 转了)

后续的步骤如下:

1) 插入 E1 节点,E1 节点的 next 指向新容器索引位置上的值(null 或 entry)

2) 插入 E2 节点,E2 的 next 指向当前索引位置上的引用值 E1

3)因为 next 不为 null,链表继续移动,此时 2 节点之间形成了闭环。造成了 死循环。

上面只是一种情况,造成单线程死循环,双核 cpu 的话占用率是 50%,还有导致 100%的情况,应该也都是链表的闭环所致。

最终,这并不是 HashMap 的问题,是使用场景的不当,在并发情况下选择非线程 安全的容器是没有保障的。

相关阅读:深入剖析ConcurrentHashMap(1)深入剖析ConcurrentHashMap(2)

scala中集合的交集、并集、差集

scala中有一些api设计的很人性化,集合的这几个操作是个代表:

交集:

scala> Set(1,2,3) & Set(2,4)   // &方法等同于interset方法
scala> Set(1,2,3) intersect Set(2,4)

并集:

scala> Set(1,2,3) ++ Set(2,4)
scala> Set(1,2,3) | Set(2,4)   // |方法等同于union方法
scala> Set(1,2,3) union Set(2,4)

差集:

scala> Set(1,2,3) -- Set(2,4) //得到 Set(1,3)
scala> Set(1,2,3) &~ Set(2,4) 
scala> Set(1,2,3) diff Set(2,4)

添加或删除元素,可以直接用+,-方法来操作,添加删除多个元素可以用元组来封装:

scala> Set(1,2,3) + (2,4)
scala> Set(1,2,3) - (2,4)

另外,对于非Set集合,在做交集、并集、差集时必须转换为Set,否则元素不去重没有意义。
而对于非Set类型集合元素去重,也有个很好的方法:distinct,定义在 GenSeqLike 特质中

这个方法的好处是集合在去重后类型不变,比用Set去重更简洁

scala> List(1,2,2,3).distinct
scala> List(1,2,2,3).toSet.toList 

补充,原用于去重的方法removeDuplicates已不鼓励使用。

foldLeft与foldRight

1) 先看一个例子: 求1到100的总和

用右折叠:

Range(1,101).foldRight(0)((x,y)=>x+y)

可缩写为

(Range(1,101):\0)(_+_)

用左折叠:

Range(1,101).foldLeft(0)((x,y)=>x+y)

可缩写为

(0/:Range(1,101))(_+_)

将所有字符串解析为Int,并进行求和(右折叠):

(Array("1","2","3").map(Integer.parseInt):\0) (_+_)

2) foldLeft和foldRight方法是在GenTraversableOnce特质里定义的
实现是在GenTraversableOnce 里:

def foldLeft[B](z: B)(op: (B, A) => B): B = {
    var result = z
    this.seq foreach (x => result = op(result, x))
    result
}

假设容器里有a,b,c 三个元素,实现上等同于 op(op(op(z,a),b),c)

返回值的类型是传入的初始值z的类型

3) 右折叠的使用与左折叠不同,
初始参数位置就不同,一个在左(逆序),一个在右
并且效率不同,foldLeft应该效率更高,需要做个测试验证一下。

4) 另一个很大的不同,可能是内存的使用方式,foldRight容易内存溢出:

scala>  println(Range(1,100000001).foldLeft(0) (_+_))
        987459712

scala>  println(Range(1,100000001).foldRight(0) (_+_))
java.lang.OutOfMemoryError: Java heap space
at scala.collection.immutable.List.$colon$colon(List.scala:67)
at scala.collection.TraversableOnce$$anonfun$reversed$1.apply(TraversableOnce.scala:88)
at scala.collection.TraversableOnce$$anonfun$reversed$1.apply(TraversableOnce.scala:88)
at scala.collection.Iterator$class.foreach(Iterator.scala:631)
at scala.collection.IndexedSeqLike$Elements.foreach(IndexedSeqLike.scala:52)
at scala.collection.TraversableOnce$class.reversed(TraversableOnce.scala:88)
at scala.collection.IndexedSeqLike$Elements.reversed(IndexedSeqLike.scala:52)
at scala.collection.TraversableOnce$class.foldRight(TraversableOnce.scala:195)
at scala.collection.IndexedSeqLike$Elements.foldRight(IndexedSeqLike.scala:52)
at scala.collection.IterableLike$class.foldRight(It...

补充,foldRight的实现是非尾递归的(tail-recursive)。

深入剖析ConcurrentHashMap(2)

经过之前的铺垫,现在可以进入正题了。
我们关注的操作有:get,put,remove 这3个操作。

对于哈希表,Java中采用链表的方式来解决hash冲突的。
一个HashMap的数据结构看起来类似下图:

实现了同步的HashTable也是这样的结构,它的同步使用锁来保证的,并且所有同步操作使用的是同一个锁对象。这样若有n个线程同时在get时,这n个线程要串行的等待来获取锁。

ConcurrentHashMap中对这个数据结构,针对并发稍微做了一点调整。
它把区间按照并发级别(concurrentLevel),分成了若干个segment。默认情况下内部按并发级别为16来创建。对于每个segment的容量,默认情况也是16。当然并发级别(concurrentLevel)和每个段(segment)的初始容量都是可以通过构造函数设定的。

创建好默认的ConcurrentHashMap之后,它的结构大致如下图:

看起来只是把以前HashTable的一个hash bucket创建了16份而已。有什么特别的吗?没啥特别的。

继续看每个segment是怎么定义的:

static final class Segment<K,V> extends ReentrantLock implements Serializable 

Segment继承了ReentrantLock,表明每个segment都可以当做一个锁。(ReentrantLock前文已经提到,不了解的话就把当做synchronized的替代者吧)这样对每个segment中的数据需要同步操作的话都是使用每个segment容器对象自身的锁来实现。只有对全局需要改变时锁定的是所有的segment。

上面的这种做法,就称之为“分离锁(lock striping)”。有必要对“分拆锁”“分离锁”的概念描述一下:

分拆锁(lock spliting)就是若原先的程序中多处逻辑都采用同一个锁,但各个逻辑之间又相互独立,就可以拆(Spliting)为使用多个锁,每个锁守护不同的逻辑。
分拆锁有时候可以被扩展,分成可大可小加锁块的集合,并且它们归属于相互独立的对象,这样的情况就是分离锁(lock striping)。(摘自《Java并发编程实践》)

看上去,单是这样就已经能大大提高多线程并发的性能了。还没完,继续看我们关注的get,put,remove这三个函数怎么保证数据同步的。

先看get方法:

public V get(Object key) {
    int hash = hash(key); // throws NullPointerException if key null
    return segmentFor(hash).get(key, hash);
}

它没有使用同步控制,交给segment去找,再看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;
}

它也没有使用锁来同步,只是判断获取的entry的value是否为null,为null时才使用加锁的方式再次去获取。

这个实现很微妙,没有锁同步的话,靠什么保证同步呢?我们一步步分析。

第一步,先判断一下 count != 0;count变量表示segment中存在entry的个数。如果为0就不用找了。
假设这个时候恰好另一个线程put或者remove了这个segment中的一个entry,会不会导致两个线程看到的count值不一致呢?
看一下count变量的定义: transient volatile int count;
它使用了volatile来修改。我们前文说过,Java5之后,JMM实现了对volatile的保证:对volatile域的写入操作happens-before于每一个后续对同一个域的读写操作。
所以,每次判断count变量的时候,即使恰好其他线程改变了segment也会体现出来。

第二步,获取到要该key所在segment中的索引地址,如果该地址有相同的hash对象,顺着链表一直比较下去找到该entry。当找到entry的时候,先做了一次比较: if(v != null) 我们用红色注释的地方。
这是为何呢?

考虑一下,如果这个时候,另一个线程恰好新增/删除了entry,或者改变了entry的value,会如何?

先看一下HashEntry类结构。

static final class HashEntry<K,V> {
    final K key;
    final int hash;
    volatile V value;
    final HashEntry<K,V> next;
    。。。
}

除了 value,其它成员都是final修饰的,也就是说value可以被改变,其它都不可以改变,包括指向下一个HashEntry的next也不能被改变。(那删除一个entry时怎么办?后续会讲到。)

1) 在get代码的①和②之间,另一个线程新增了一个entry
如果另一个线程新增的这个entry又恰好是我们要get的,这事儿就比较微妙了。

下图大致描述了put 一个新的entry的过程。

因为每个HashEntry中的next也是final的,没法对链表最后一个元素增加一个后续entry
所以新增一个entry的实现方式只能通过头结点来插入了。

newEntry对象是通过 new HashEntry(K k , V v, HashEntry next) 来创建的。如果另一个线程刚好new 这个对象时,当前线程来get它。因为没有同步,就可能会出现当前线程得到的newEntry对象是一个没有完全构造好的对象引用。

回想一下我们之前讨论的DCL的问题,这里也一样,没有锁同步的话,new 一个对象对于多线程看到这个对象的状态是没有保障的,这里同样有可能一个线程new这个对象的时候还没有执行完构造函数就被另一个线程得到这个对象引用。
所以才需要判断一下:if (v != null) 如果确实是一个不完整的对象,则使用锁的方式再次get一次。

有没有可能会put进一个value为null的entry? 不会的,已经做了检查,这种情况会抛出异常,所以 ②处的判断完全是出于对多线程下访问一个new出来的对象的状态检测。

2) 在get代码的①和②之间,另一个线程修改了一个entry的value
value是用volitale修饰的,可以保证读取时获取到的是修改后的值。

3) 在get代码的①之后,另一个线程删除了一个entry

假设我们的链表元素是:e1-> e2 -> e3 -> e4 我们要删除 e3这个entry
因为HashEntry中next的不可变,所以我们无法直接把e2的next指向e4,而是将要删除的节点之前的节点复制一份,形成新的链表。它的实现大致如下图所示:

如果我们get的也恰巧是e3,可能我们顺着链表刚找到e1,这时另一个线程就执行了删除e3的操作,而我们线程还会继续沿着旧的链表找到e3返回。
这里没有办法实时保证了。

我们第①处就判断了count变量,它保障了在 ①处能看到其他线程修改后的。
①之后到②之间,如果再次发生了其他线程再删除了entry节点,就没法保证看到最新的了。

不过这也没什么关系,即使我们返回e3的时候,它被其他线程删除了,暴漏出去的e3也不会对我们新的链表造成影响。

这其实是一种乐观设计,设计者假设 ①之后到②之间 发生被其它线程增、删、改的操作可能性很小,所以不采用同步设计,而是采用了事后(其它线程这期间也来操作,并且可能发生非安全事件)弥补的方式。
而因为其他线程的“改”和“删”对我们的数据都不会造成影响,所以只有对“新增”操作进行了安全检查,就是②处的非null检查,如果确认不安全事件发生,则采用加锁的方式再次get。

这样做减少了使用互斥锁对并发性能的影响。可能有人怀疑remove操作中复制链表的方式是否代价太大,这里我没有深入比较,不过既然Java5中这么实现,我想new一个对象的代价应该已经没有早期认为的那么严重。

我们基本分析完了get操作。对于put和remove操作,是使用锁同步来进行的,不过是用的ReentrantLock而不是synchronized,性能上要更高一些。它们的实现前文都已经提到过,就没什么可分析的了。

我们还需要知道一点,ConcurrentHashMap的迭代器不是Fast-Fail的方式,所以在迭代的过程中别其他线程添加/删除了元素,不会抛出异常,也不能体现出元素的改动。但也没有关系,因为每个entry的成员除了value都是final修饰的,暴漏出去也不会对其他元素造成影响。

最后,再来看一下Java6文档中对ConcurrentHashMap的描述(我们分析过的地方或者需要注意的使用了红色字体):

支持获取的完全并发和更新的所期望可调整并发的哈希表。此类遵守与 Hashtable 相同的功能规范,并且包括对应于 Hashtable 的每个方法的方法版本。不过,尽管所有操作都是线程安全的,但获取操作不 必锁定,并且不 支持以某种防止所有访问的方式锁定整个表。此类可以通过程序完全与 Hashtable 进行互操作,这取决于其线程安全,而与其同步细节无关。

获取操作(包括 get)通常不会受阻塞,因此,可能与更新操作交迭(包括 put 和 remove)。获取会影响最近完成的 更新操作的结果。对于一些聚合操作,比如 putAll 和 clear,并发获取可能只影响某些条目的插入和移除。类似地,在创建迭代器/枚举时或自此之后,Iterators 和 Enumerations 返回在某一时间点上影响哈希表状态的元素。它们不会 抛出 ConcurrentModificationException。不过,迭代器被设计成每次仅由一个线程使用。

这允许通过可选的 concurrencyLevel 构造方法参数(默认值为 16)来引导更新操作之间的并发,该参数用作内部调整大小的一个提示。表是在内部进行分区的,试图允许指示无争用并发更新的数量。因为哈希表中的位置基本上是随意的,所以实际的并发将各不相同。理想情况下,应该选择一个尽可能多地容纳并发修改该表的线程的值。使用一个比所需要的值高很多的值可能会浪费空间和时间,而使用一个显然低很多的值可能导致线程争用。对数量级估计过高或估计过低通常都会带来非常显著的影响。当仅有一个线程将执行修改操作,而其他所有线程都只是执行读取操作时,才认为某个值是合适的。此外,重新调整此类或其他任何种类哈希表的大小都是一个相对较慢的操作,因此,在可能的时候,提供构造方法中期望表大小的估计值是一个好主意。

参考:
http://www.javaeye.com/topic/344876

本来我的分析已经结束,不过正好看到Concurrency-interest邮件组中的一个问题,可以加深一下我们队ConcurrentHashMap的理解,同时也反驳了我刚开始所说的“ConcurrentHashMap完全可以替代HashTable”,我必须纠正一下。先看例子:

ConcurrentHashMap<String, Boolean> map = new ...;
Thread a = new Thread {
    void run() {
        map.put("first", true);
        map.put("second", true);
    }
};

Thread b = new Thread {
    void run() {
        map.clear();
    }
};

a.start();
b.start();
a.join();
b.join();

I would expect that one of the following scenarios to be true (for the contents of the map) after this code runs:

Map("first" -> true, "second" -> true)
Map("second" -> true)
Map()

However, upon inspection of ConcurrentHashMap, it seems to me that the following scenario might also be true:

Map("first" -> true) ???

This seems surprising because “first” gets put before “second”, so if “second” is cleared, then surely “first” should be cleared too.

Likewise, consider the following code:

ConcurrentHashMap<String, Boolean> map = new ...;
List<String> myKeys = new ...;

Thread a = new Thread {
    void run() {
        map.put("first", true);
        // more stuff
        map.remove("first");
        map.put("second", true);
    }
};

Thread b = new Thread {
    void run() {
        Set<String> keys = map.keySet();
        for (String key : keys) {
            myKeys.add(key);
        }
    }
};

a.start();
b.start();
a.join();
b.join();

I would expect one of the following scenarios to be true for the contents of myKeys after this code has run:

List()
List("first")
List("second")

However, upon closer inspection, it seems that the following scenario might also be true:

List("first", "second") ???

This is surprising because “second” is only ever put into the map after “first” is removed. They should never be in the map simultaneously, but an iterator might perceive them to be so.

对于这两个现象的解释:ConcurrentHashMap中的clear方法:

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

如果线程b先执行了clear,清空了一部分segment的时候,线程a执行了put且正好把“first”放入了“清空过”的segment中,而把“second”放到了还没有清空过的segment中,就会出现上面的情况。

第二段代码,如果线程b执行了迭代遍历到first,而此时线程a还没有remove掉first,那么即使后续删除了first,迭代器里不会反应出来,也不抛出异常,这种迭代器被称为“弱一致性”(weakly consistent)迭代器。

Doug Lea 对这个问题的回复中提到:

We leave the tradeoff of consistency-strength versus scalability
as a user decision, so offer both synchronized and concurrent versions
of most collections, as discussed in the j.u.c package docs
http://java.sun.com/javase/6/docs/api/java/util/concurrent/package-summary.html

大意是我们将“一致性强度”和“扩展性”之间的对比交给用户来权衡,所以大多数集合都提供了synchronized和concurrent两个版本。

通过他的说法,我必须纠正我一开始以为ConcurrentHashMap完全可以代替HashTable的说法,如果你的环境要求“强一致性”的话,就不能用ConcurrentHashMap了,它的get,clear方法和迭代器都是“弱一致性”的。不过真正需要“强一致性”的场景可能非常少,我们大多应用中ConcurrentHashMap是满足的。

深入剖析ConcurrentHashMap(1)

原文是09年时写的,在公司的邮件列表发过,同事一粟清英 创建的并发编程网 对这方面概念和实战有更好的文章,贴出来仅供参考。pdf格式在:http://www.slideshare.net/hongjiang/concurrent-hashmap 可以获取

ConcurrentHashMap是Java5中新增加的一个线程安全的Map集合,可以用来完全替代HashTable(这句话不严谨,第二篇会补充)。对于ConcurrentHashMap是如何提高其效率的,可能大多人只是知道它使用了多个锁代替HashTable中的单个锁,也就是锁分离技术(Lock Stripping)。实际上,ConcurrentHashMap对提高并发方面的优化,还有一些其它的技巧在里面(比如你是否知道在get操作的时候,它是否也使用了锁来保护?)。

我会试图用通俗一点的方法讲解一下 ConcurrentHashMap的实现方式,不过因为水平有限,在整理这篇文档的过程中,发现了更多自己未曾深入思考过的地方,使得我不得不从新调整了自己的讲解方式。我假设受众者大多是对Java存储模型(JMM)认识并不很深的(我本人也是)。如果我们不断的对ConcurrentHashMap中一些实现追问下去,最终还是要归到JMM层面甚至更底层的。这篇文章的关注点主要在同步方面,并不去分析HashMap中的一些数据结构方面的实现。

ConcurrentHashMap实现了ConcurrentMap接口,先看看 ConcurrentMap 接口的文档说明:

提供其他原子 putIfAbsent、remove、replace 方法的 Map。

内存一致性效果:当存在其他并发 collection 时,将对象放入 ConcurrentMap 之前的线程中的操作 happen-before 随后通过另一线程从 ConcurrentMap 中访问或移除该元素的操作。

我们不关心ConcurrentMap中新增的接口,重点理解一下内存一致性效果中的“happens-before”是怎么回事。因为要想从根本上讲明白,这个是无法避开的。这又不得不从Java存储模型来谈起了。

1. 理解JAVA存储模型(JMM)的Happens-Before规则。

在解释该规则之前,我们先看一段多线程访问数据的代码例子:

public class Test1 {
    private int a=1, b=2;

    public void foo(){  // 线程1 
        a=3;
        b=4;
    }

    public int getA(){ // 线程2
        return a;
    }    
    public int getB(){ // 线程2
        return b;
    }
}

上面的代码,当线程1执行foo方法的时候,线程2访问getA和getB会得到什么样的结果?
答案:

A:a=1, b=2  // 都未改变
B:a=3, b=4  // 都改变了
C:a=3, b=2  //  a改变了,b未改变
D:a=1, b=4  //  b改变了,a未改变

上面的A,B,C都好理解,但是D可能会出乎一些人的预料。
一些不了解JMM的同学可能会问怎么可能 b=4语句会先于 a=3 执行?

这是一个多线程之间内存可见性(Visibility)顺序不一致的问题。有两种可能会造成上面的D选项。

1) Java编译器的重排序(Reording)操作有可能导致执行顺序和代码顺序不一致。
关于Reording:

Java语言规范规定了JVM要维护内部线程类似顺序化语义(within-thread as-is-serial semantics):只要程序的最终结果等同于它在严格的顺序化环境中执行的结果,那么上述所有的行为都是允许的。

上面的话是《Java并发编程实践》一书中引自Java语言规范的,感觉翻译的不太好。简单的说:假设代码有两条语句,代码顺序是语句1先于语句2执行;那么只要语句2不依赖于语句1的结果,打乱它们的顺序对最终的结果没有影响的话,那么真正交给CPU去执行时,他们的顺序可以是没有限制的。可以允许语句2先于语句1被CPU执行,和代码中的顺序不一致。

重排序(Reordering)是JVM针对现代CPU的一种优化,Reordering后的指令会在性能上有很大提升。(不知道这种优化对于多核CPU是否更加明显,也或许和单核多核没有关系。)

因为我们例子中的两条赋值语句,并没有依赖关系,无论谁先谁后结果都是一样的,所以就可能有Reordering的情况,这种情况下,对于其他线程来说就可能造成了可见性顺序不一致的问题。

2) 从线程工作内存写回主存时顺序无法保证。
下图描述了JVM中主存和线程工作内存之间的交互:

JLS中对线程和主存互操作定义了6个行为,分别为load,save,read,write,assign和use,这些操作行为具有原子性,且相互依赖,有明确的调用先后顺序。这个细节也比较繁琐,我们暂不深入追究。先简单认为线程在修改一个变量时,先拷贝入线程工作内存中,在线程工作内存修改后再写回主存(Main Memery)中。

假设例子中Reording后顺序仍与代码中的顺序一致,那么接下来呢?
有意思的事情就发生在线程把Working Copy Memery中的变量写回Main Memery的时刻。
线程1把变量写回Main Memery的过程对线程2的可见性顺序也是无法保证的。
上面的列子,a=3; b=4; 这两个语句在 Working Copy Memery中执行后,写回主存的过程对于线程2来说同样可能出现先b=4;后a=3;这样的相反顺序。

正因为上面的那些问题,JMM中一个重要问题就是:如何让多线程之间,对象的状态对于各线程的“可视性”是顺序一致的。
它的解决方式就是 Happens-before 规则:
JMM为所有程序内部动作定义了一个偏序关系,叫做happens-before。要想保证执行动作B的线程看到动作A的结果(无论A和B是否发生在同一个线程中),A和B之间就必须满足happens-before关系。

我们现在来看一下“Happens-before”规则都有哪些(摘自《Java并发编程实践》):

① 程序次序法则:线程中的每个动作A都happens-before于该线程中的每一个动作B,其中,在程序中,所有的动作B都能出现在A之后。
② 监视器锁法则:对一个监视器锁的解锁 happens-before于每一个后续对同一监视器锁的加锁。
③ volatile变量法则:对volatile域的写入操作happens-before于每一个后续对同一个域的读写操作。
④ 线程启动法则:在一个线程里,对Thread.start的调用会happens-before于每个启动线程的动作。
⑤ 线程终结法则:线程中的任何动作都happens-before于其他线程检测到这个线程已经终结、或者从Thread.join调用中成功返回,或Thread.isAlive返回false。
⑥ 中断法则:一个线程调用另一个线程的interrupt happens-before于被中断的线程发现中断。
⑦ 终结法则:一个对象的构造函数的结束happens-before于这个对象finalizer的开始。
⑧ 传递性:如果A happens-before于B,且B happens-before于C,则A happens-before于C
(更多关于happens-before描述见附注2)

我们重点关注的是②,③,这两条也是我们通常编程中常用的。
后续分析ConcurrenHashMap时也会看到使用到锁(ReentrantLock),Volatile,final等手段来保证happens-before规则的。

使用锁方式实现“Happens-before”是最简单,容易理解的。

早期Java中的锁只有最基本的synchronized,它是一种互斥的实现方式。在Java5之后,增加了一些其它锁,比如ReentrantLock,它基本作用和synchronized相似,但提供了更多的操作方式,比如在获取锁时不必像synchronized那样只是傻等,可以设置定时,轮询,或者中断,这些方法使得它在获取多个锁的情况可以避免死锁操作。

而我们需要了解的是ReentrantLock的性能相对synchronized来说有很大的提高。(不过据说Java6后对synchronized进行了优化,两者已经接近了。)在ConcurrentHashMap中,每个hash区间使用的锁正是ReentrantLock。

Volatile可以看做一种轻量级的锁,但又和锁有些不同。
a) 它对于多线程,不是一种互斥(mutex)关系。
b) 用volatile修饰的变量,不能保证该变量状态的改变对于其他线程来说是一种“原子化操作”。

在Java5之前,JMM对Volatile的定义是:保证读写volatile都直接发生在main memory中,线程的working memory不进行缓存。
它只承诺了读和写过程的可见性,并没有对Reording做限制,所以旧的Volatile并不太可靠。
在Java5之后,JMM对volatile的语义进行了增强。就是我们看到的③ volatile变量法则

那对于“原子化操作”怎么理解呢?看下面例子:

private static volatile int nextSerialNum = 0;

public static int generateSerialNumber(){
    return nextSerialNum++;
}

上面代码中对nextSerialNum使用了volatile来修饰,根据前面“Happens-Before”法则的第三条Volatile变量法则,看似不同线程都会得到一个新的serialNumber

问题出在了 nextSerialNum++ 这条语句上,它不是一个原子化的,实际上是read-modify-write三项操作,这就有可能使得在线程1在write之前,线程2也访问到了nextSerialNum,造成了线程1和线程2得到一样的serialNumber。
所以,在使用Volatile时,需要注意
a) 需不需要互斥;
b)对象状态的改变是不是原子化的。

最后也说一下final 关键字。
不变模式(immutable)是多线程安全里最简单的一种保障方式。因为你拿他没有办法,想改变它也没有机会。
不变模式主要通过final关键字来限定的。
在JMM中final关键字还有特殊的语义。Final域使得确保初始化安全性(initialization safety)成为可能,初始化安全性让不可变形对象不需要同步就能自由地被访问和共享。

2)经过前面的了解,下面我们用Happens-Before规则理解一个经典问题:双重检测锁(DCL)为什么在java中不适用?

public class LazySingleton {
    private int                  someField;
    private static LazySingleton instance;

    private LazySingleton(){
        this.someField = new Random().nextInt(200) + 1; // (1)
    }

    public static LazySingleton getInstance() {
        if (instance == null) {// (2)
            synchronized (LazySingleton.class) { // (3)
              if (instance == null) { // (4)
                instance = new LazySingleton(); // (5)
              }
            }
        }
        return instance; // (6)
    }

    public int getSomeField() {
        return this.someField;  // (7)
    }
}

这里例子的详细解释可以看这里:http://www.javaeye.com/topic/260515?page=1
他解释的太详细了,是基于数学证明来分析的,看似更严谨一些,他的证明是因为那几条语句之间不存在Happens-before约束,所以它们不能保证可见性顺序。理解起来有些抽象,对于经验不多的程序员来说缺乏更有效的说服力。

我想简单的用对象创建期间的实际场景来分析一下:(注意,这种场景是我个人的理解,所看的资料也是非官方的,不完全保证正确。如果发现不对请指出。见附注1)

假设线程1执行完(5)时,线程2正好执行到了(2);
看看 new LazySingleton(); 这个语句的执行过程: 它不是一个原子操作,实际是由多个步骤,我们从我们关注的角度简化一下,简单的认为它主要有2步操作好了:
a) 在内存中分配空间,并将引用指向该内存空间。
b) 执行对象的初始化的逻辑(操作),完成对象的构建。

此时因为线程1和线程2没有用同步,他们之间不存在“Happens-Before”规则的约束,所以在线程1创建LazySingleton对象的 a),b)这两个步骤对于线程2来说会有可能出现a)可见,b)不可见
造成了线程2获取到了一个未创建完整的lazySingleton对象引用,为后边埋下隐患。

之所以这里举到 DCL这个例子,是因为我们后边分析ConcurrentHashMap时,也会遇到相似的情况。
对于对象的创建,出于乐观考虑,两个线程之间没有用“Happens-Before规则来约束”另一个线程可能会得到一个未创建完整的对象,这种情况必须要检测,后续分析ConcurrentHashMap时再讨论。

附注1:
我所定义的场景,是基于对以下资料了解的,比较低层,没有细看。
原文:http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html
其中分析一个对象创建过程的部分摘抄如下:

singletons[i].reference = new Singleton();

to the following (note that the Symantec JIT using a handle-based object allocation system).

0206106A   mov         eax,0F97E78h
0206106F   call        01F6B210                  ; allocate space for
                                             ; Singleton, return result in eax
02061074   mov         dword ptr [ebp],eax       ; EBP is &singletons[i].reference 
                                            ; store the unconstructed object here.
02061077   mov         ecx,dword ptr [eax]       ; dereference the handle to
                                             ; get the raw pointer
02061079   mov         dword ptr [ecx],100h      ; Next 4 lines are
0206107F   mov         dword ptr [ecx+4],200h    ; Singleton's inlined constructor
02061086   mov         dword ptr [ecx+8],400h
0206108D   mov         dword ptr [ecx+0Ch],0F84030h

As you can see, the assignment to singletons[i].reference is performed before the constructor for Singleton is called. This is completely legal under the existing Java memory model, and also legal in C and C++ (since neither of them have a memory model).

另外,从JVM创建一个对象的过程来看,分为:“装载”,“连接”,“初始化”三个步骤。
在连接步骤中包含“验证”,“准备”,“解析”这几个环节。
为一个对象分配内存的过程是在连接步骤的准备环节,它是先于“初始化”步骤的,而构造函数的执行是在“初始化”步骤中的。

附注2:
Java6 API文档中对于内存一致性(Memory Consistency Properties)的描述:

内存一致性属性

Java Language Specification 第 17 章定义了内存操作(如共享变量的读写)的 happen-before 关系。只有写入操作 happen-before 读取操作时,才保证一个线程写入的结果对另一个线程的读取是可视的。synchronized 和 volatile 构造 happen-before 关系,Thread.start() 和 Thread.join() 方法形成 happen-before 关系。尤其是:

1) 线程中的每个操作 happen-before 稍后按程序顺序传入的该线程中的每个操作。
2) 一个解除锁监视器的(synchronized 阻塞或方法退出)happen-before 相同监视器的每个后续锁(synchronized 阻塞或方法进入)。并且因为 happen-before 关系是可传递的,所以解除锁定之前的线程的所有操作 happen-before 锁定该监视器的任何线程后续的所有操作。
3) 写入 volatile 字段 happen-before 每个后续读取相同字段。volatile 字段的读取和写入与进入和退出监视器具有相似的内存一致性效果,但不 需要互斥锁。
4) 在线程上调用 start happen-before 已启动的线程中的任何线程。
5) 线程中的所有操作 happen-before 从该线程上的 join 成功返回的任何其他线程。
java.util.concurrent 中所有类的方法及其子包扩展了这些对更高级别同步的保证。尤其是:
6) 线程中将一个对象放入任何并发 collection 之前的操作 happen-before 从另一线程中的 collection 访问或移除该元素的后续操作。
7) 线程中向 Executor 提交 Runnable 之前的操作 happen-before 其执行开始。同样适用于向 ExecutorService 提交 Callables。
8) 异步计算(由 Future 表示)所采取的操作 happen-before 通过另一线程中 Future.get() 获取结果后续的操作。
9) “释放”同步储存方法(如 Lock.unlock、Semaphore.release 和 CountDownLatch.countDown)之前的操作 happen-before 另一线程中相同同步储存对象成功“获取”方法(如 Lock.lock、Semaphore.acquire、Condition.await 和 CountDownLatch.await)的后续操作。
10) 对于通过 Exchanger 成功交换对象的每个线程对,每个线程中 exchange() 之前的操作 happen-before 另一线程中对应 exchange() 后续的操作。
11) 调用 CyclicBarrier.await 之前的操作 happen-before 屏障操作所执行的操作,屏障操作所执行的操作 happen-before 从另一线程中对应 await 成功返回的后续操作。

后续补充:
附注一种所引用的文章(Double-Checked Locking is Broken)是一篇比较著名的文章,但也比较早;他所使用的JIT还是Symantec(赛门铁克)JIT,这是一个很古老的JIT,早已经退出了Java舞台,不过我了解了一下历史,在SUN的HotSpot JIT出现之前,Symantec JIT曾是市场上编译最快的JIT。

Symantec的JIT反汇编后证明的逻辑,并不一定证明其他其他JIT也是这样的,我不清楚用什么工具能将java执行过程用汇编语言表达出来。没有去证明其他的编译器。

所以我所描述的new一个对象的场景不一定是完全正确的(不同的编译器未必都和Symantec的实现方式一致),但是始终存在reording 优化,即使编译器没有做,也有可能在cpu级去做,所以new一个对象的过程对多线程访问始终存在不确定性。