HashMap 多线程并发问题分析

并发问题的症状

多线程 put 后可能导致 get 死循环

从前我们的 Java 代码因为一些原因使用了 HashMap 这个东西,但是当时的程序是单线程的,一切都没有问题。后来,我们的程序性能有问题,所以需要变成多线程的,于是,变成多线程后到了线上,发现程序经常占了 100% 的 CPU,查看堆栈,你会发现程序都 Hang 在了 HashMap.get () 这个方法上了,重启程序后问题消失。但是过段时间又会来。而且,这个问题在测试环境里可能很难重现。

我们简单的看一下我们自己的代码,我们就知道 HashMap 被多个线程操作。而 Java 的文档说 HashMap 是非线程安全的,应该用 ConcurrentHashMap。但是在这里我们可以来研究一下原因。简单代码如下:

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
package com.king.hashmap;

import java.util.HashMap;

public class TestLock {

private HashMap map = new HashMap();

public TestLock() {
Thread t1 = new Thread() {
public void run() {
for (int i = 0; i < 50000; i++) {
map.put(new Integer(i), i);
}
System.out.println("t1 over");
}
};

Thread t2 = new Thread() {
public void run() {
for (int i = 0; i < 50000; i++) {
map.put(new Integer(i), i);
}

System.out.println("t2 over");
}
};

Thread t3 = new Thread() {
public void run() {
for (int i = 0; i < 50000; i++) {
map.put(new Integer(i), i);
}

System.out.println("t3 over");
}
};

Thread t4 = new Thread() {
public void run() {
for (int i = 0; i < 50000; i++) {
map.put(new Integer(i), i);
}

System.out.println("t4 over");
}
};

Thread t5 = new Thread() {
public void run() {
for (int i = 0; i < 50000; i++) {
map.put(new Integer(i), i);
}

System.out.println("t5 over");
}
};

Thread t6 = new Thread() {
public void run() {
for (int i = 0; i < 50000; i++) {
map.get(new Integer(i));
}

System.out.println("t6 over");
}
};

Thread t7 = new Thread() {
public void run() {
for (int i = 0; i < 50000; i++) {
map.get(new Integer(i));
}

System.out.println("t7 over");
}
};

Thread t8 = new Thread() {
public void run() {
for (int i = 0; i < 50000; i++) {
map.get(new Integer(i));
}

System.out.println("t8 over");
}
};

Thread t9 = new Thread() {
public void run() {
for (int i = 0; i < 50000; i++) {
map.get(new Integer(i));
}

System.out.println("t9 over");
}
};

Thread t10 = new Thread() {
public void run() {
for (int i = 0; i < 50000; i++) {
map.get(new Integer(i));
}

System.out.println("t10 over");
}
};

t1.start();
t2.start();
t3.start();
t4.start();
t5.start();

t6.start();
t7.start();
t8.start();
t9.start();
t10.start();
}

public static void main(String[] args) {
new TestLock();
}
}

就是启了 10 个线程,不断的往一个非线程安全的 HashMap 中 put 内容 /get 内容,put 的内容很简单,key 和 value 都是从 0 自增的整数(这个 put 的内容做的并不好,以致于后来干扰了我分析问题的思路)。对 HashMap 做并发写操作,我原以为只不过会产生脏数据的情况,但反复运行这个程序,会出现线程 t1、t2 被 hang 住的情况,多数情况下是一个线程被 hang 住另一个成功结束,偶尔会 10 个线程都被 hang 住。 产生这个死循环的根源在于对一个未保护的共享变量 — 一个”HashMap” 数据结构的操作。当在所有操作的方法上加了”synchronized” 后,一切恢复了正常。这算 jvm 的 bug 吗?应该说不是的,这个现象很早以前就报告出来了。Sun 的工程师并不认为这是 bug,而是建议在这样的场景下应采用”ConcurrentHashMap”, CPU 利用率过高一般是因为出现了出现了死循环,导致部分线程一直运行,占用 cpu 时间。问题原因就是 HashMap 是非线程安全的,多个线程 put 的时候造成了某个 key 值 Entry key List 的死循环,问题就这么产生了。 当另外一个线程 get 这个 Entry List 死循环的 key 的时候,这个 get 也会一直执行。最后结果是越来越多的线程死循环,最后导致服务器 dang 掉。我们一般认为 HashMap 重复插入某个值的时候,会覆盖之前的值,这个没错。但是对于多线程访问的时候,由于其内部实现机制 (在多线程环境且未作同步的情况下,对同一个 HashMap 做 put 操作可能导致两个或以上线程同时做 rehash 动作,就可能导致循环键表出现,一旦出现线程将无法终止,持续占用 CPU,导致 CPU 使用率居高不下),就可能出现安全问题了。 使用 jstack 工具 dump 出问题的那台服务器的栈信息。死循环的话,首先查找 RUNNABLE 的线程,找到问题代码如下:

java.lang.Thread.State:RUNNABLE at java.util.HashMap.get (HashMap.java:303) at com.sohu.twap.service.logic.TransformTweeter.doTransformTweetT5 (TransformTweeter.java:183) 共出现了 23 次。 java.lang.Thread.State:RUNNABLE at java.util.HashMap.put (HashMap.java:374) at com.sohu.twap.service.logic.TransformTweeter.transformT5 (TransformTweeter.java:816) 共出现了 3 次。

注意:不合理使用 HashMap 导致出现的是死循环而不是死锁。

多线程 put 的时候可能导致元素丢失

主要问题出在 addEntry 方法的 new Entry<K,V>(hash, key, value, e),如果两个线程都同时取得了 e, 则他们下一个元素都是 e,然后赋值给 table 元素的时候有一个成功有一个丢失。

put 非 null 元素后 get 出来的却是 null

在 transfer 方法中代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {
Entry e = src[j];
if (e != null) {
src[j] = null;
do {
Entry next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}

在这个方法里,将旧数组赋值给 src,遍历 src,当 src 的元素非 null 时,就将 src 中的该元素置 null,即将旧数组中的元素置 null 了,也就是这一句:

1
2
if (e != null) {
src[j] = null;

此时若有 get 方法访问这个 key,它取得的还是旧数组,当然就取不到其对应的 value 了。 总结:HashMap 未同步时在并发程序中会产生许多微妙的问题,难以从表层找到原因。所以使用 HashMap 出现了违反直觉的现象,那么可能就是并发导致的了。

HashMap 数据结构

我需要简单地说一下 HashMap 这个经典的数据结构。 HashMap 通常会用一个指针数组(假设为 table [])来做分散所有的 key,当一个 key 被加入时,会通过 Hash 算法通过 key 算出这个数组的下标 i,然后就把这个 < key, value> 插到 table [i] 中,如果有两个不同的 key 被算在了同一个 i,那么就叫冲突,又叫碰撞,这样会在 table [i] 上形成一个链表。 我们知道,如果 table [] 的尺寸很小,比如只有 2 个,如果要放进 10 个 keys 的话,那么碰撞非常频繁,于是一个 O (1) 的查找算法,就变成了链表遍历,性能变成了 O (n),这是 Hash 表的缺陷。 所以,Hash 表的尺寸和容量非常的重要。一般来说,Hash 表这个容器当有数据要插入时,都会检查容量有没有超过设定的 thredhold,如果超过,需要增大 Hash 表的尺寸,但是这样一来,整个 Hash 表里的元素都需要被重算一遍。这叫 rehash,这个成本相当的大。

HashMap 的 rehash 源代码

下面,我们来看一下 Java 的 HashMap 的源代码。Put 一个 Key,Value 对到 Hash 表中:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public V put(K key, V value)
{
......
//算Hash值
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
//如果该key已被插入,则替换掉旧的value (链接操作)
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//该key不存在,需要增加一个结点
addEntry(hash, key, value, i);
return null;
}

检查容量是否超标:

1
2
3
4
5
6
7
8
void addEntry(int hash, K key, V value, int bucketIndex)
{
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
//查看当前的size是否超过了我们设定的阈值threshold,如果超过,需要resize
if (size++ >= threshold)
resize(2 * table.length);
}

新建一个更大尺寸的 hash 表,然后把数据从老的 Hash 表中迁移到新的 Hash 表中。

1
2
3
4
5
6
7
8
9
10
11
12
void resize(int newCapacity)
{
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
......
//创建一个新的Hash Table
Entry[] newTable = new Entry[newCapacity];
//将Old Hash Table上的数据迁移到New Hash Table上
transfer(newTable);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}

迁移的源代码,注意高亮处:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void transfer(Entry[] newTable)
{
Entry[] src = table;
int newCapacity = newTable.length;
//下面这段代码的意思是:
// 从OldTable里摘一个元素出来,然后放到NewTable中
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);
}
}
}

好了,这个代码算是比较正常的。而且没有什么问题。

正常的 ReHash 过程

画了个图做了个演示。

  1. 我假设了我们的 hash 算法就是简单的用 key mod 一下表的大小(也就是数组的长度)。
  2. 最上面的是 old hash 表,其中的 Hash 表的 size=2, 所以 key = 3, 7, 5,在 mod 2 以后都冲突在 table1 这里了。
  3. 接下来的三个步骤是 Hash 表 resize 成 4,然后所有的 <key,value> 重新 rehash 的过程。

并发的 Rehash 过程

(1)假设我们有两个线程。我用红色和浅蓝色标注了一下。我们再回头看一下我们的 transfer 代码中的这个细节:

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);

而我们的线程二执行完成了。于是我们有下面的这个样子。

注意:因为 Thread1 的 e 指向了 key (3),而 next 指向了 key (7),其在线程二 rehash 后,指向了线程二重组后的链表。我们可以看到链表的顺序被反转后。

(2)线程一被调度回来执行。

  1. 先是执行 newTalbe [i] = e。
  2. 然后是 e = next,导致了 e 指向了 key (7)。
  3. 而下一次循环的 next = e.next 导致了 next 指向了 key (3)。

(3)一切安好。 线程一接着工作。把 key (7) 摘下来,放到 newTable [i] 的第一个,然后把 e 和 next 往下移。

(4)环形链接出现。 e.next = newTable [i] 导致 key (3).next 指向了 key (7)。注意:此时的 key (7).next 已经指向了 key (3), 环形链表就这样出现了。

于是,当我们的线程一调用到,HashTable.get (11) 时,悲剧就出现了 ——Infinite Loop。

三种解决方案

Hashtable 替换 HashMap

Hashtable 是同步的,但由迭代器返回的 Iterator 和由所有 Hashtable 的 “collection 视图方法” 返回的 Collection 的 listIterator 方法都是快速失败的:在创建 Iterator 之后,如果从结构上对 Hashtable 进行修改,除非通过 Iterator 自身的移除或添加方法,否则在任何时间以任何方式对其进行修改,Iterator 都将抛出 ConcurrentModificationException。因此,面对并发的修改,Iterator 很快就会完全失败,而不冒在将来某个不确定的时间发生任意不确定行为的风险。由 Hashtable 的键和值方法返回的 Enumeration 不是快速失败的。 注意,迭代器的快速失败行为无法得到保证,因为一般来说,不可能对是否出现不同步并发修改做出任何硬性保证。快速失败迭代器会尽最大努力抛出 ConcurrentModificationException。因此,为提高这类迭代器的正确性而编写一个依赖于此异常的程序是错误做法:迭代器的快速失败行为应该仅用于检测程序错误。

Collections.synchronizedMap 将 HashMap 包装起来

返回由指定映射支持的同步(线程安全的)映射。为了保证按顺序访问,必须通过返回的映射完成对底层映射的所有访问。在返回的映射或其任意 collection 视图上进行迭代时,强制用户手工在返回的映射上进行同步:

1
2
3
4
5
6
7
8
9
Map m = Collections.synchronizedMap(new HashMap());
...
Set s = m.keySet(); // Needn't be in synchronized block
...
synchronized(m) { // Synchronizing on m, not s!
Iterator i = s.iterator(); // Must be in synchronized block
while (i.hasNext())
foo(i.next());
}

不遵从此建议将导致无法确定的行为。如果指定映射是可序列化的,则返回的映射也将是可序列化的。

ConcurrentHashMap 替换 HashMap

支持检索的完全并发和更新的所期望可调整并发的哈希表。此类遵守与 Hashtable 相同的功能规范,并且包括对应于 Hashtable 的每个方法的方法版本。不过,尽管所有操作都是线程安全的,但检索操作不必锁定,并且不支持以某种防止所有访问的方式锁定整个表。此类可以通过程序完全与 Hashtable 进行互操作,这取决于其线程安全,而与其同步细节无关。 检索操作(包括 get)通常不会受阻塞,因此,可能与更新操作交迭(包括 put 和 remove)。检索会影响最近完成的更新操作的结果。对于一些聚合操作,比如 putAll 和 clear,并发检索可能只影响某些条目的插入和移除。类似地,在创建迭代器 / 枚举时或自此之后,Iterators 和 Enumerations 返回在某一时间点上影响哈希表状态的元素。它们不会抛出 ConcurrentModificationException。不过,迭代器被设计成每次仅由一个线程使用。

来自:陶邦仁的个人空间 - 开源中国社区
作者:陶邦仁
链接:http://my.oschina.net/xianggao/blog/393990