并发场景下HashMap.get导致cpu耗光的原因分析

上一条微信消息中发了两个在并发场景下错误使用HashMap,导致出现了HashMap.get把CPU耗光的现象,虽然讲了是由于HashMap.get里面的for循环出现了无限循环,但没有讲明白为什么这个地方会出现无限循环,刚好博客上@fish也给我发了个专业的解释:“出现死循环是因为map中的桶链表出现了循环链表,循环链表是因为并发put操作造成的,同时进行了resize();如果只有一个线程进行put操作,是不会出现循环链表,所以读写并发不会出现死循环,只有写写并发才有可能出现死循环。”

@fish说的这个确实是根本原因,要造成HashMap.get中的那段for循环无限循环,只能是修改过e.next才有可能,而HashMap的代码中,主要是transfer方法中会进行修改,transfer就是在resize的时候才会触发,transfer方法的代码如下:
[code]
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);
}
}
}
[/code]
这样纯粹看代码挺难看出根本原因,毕竟人脑是串行的,这里举例(这个例子来源于老外的一篇讲HashMap infinite loop的根本原因的文章)来说明下。

假设一个初始容量大小为2的HashMap(大多数人应该知道HashMap是采用数组的方式来存储key,value对象,基于对key的hashcode的hash来决定存储到数组的位置,冲突的情况下采用开放链表的方式来解决),目前里面有两个Entry,假设其存储在数组的同一位置,存储结构类似如下:
Entry[0] = A(.next) –> B(.next) –> null

假设同时有两个线程调用了put,同时触发resize。
第二个线程目前执行到Entry next = e.next这一行,此时其获取到的e为A,next为B。

第一个线程已执行完transfer动作,但还没执行完resize的剩余动作,如A和B在容量扩大为4时hash到的位置仍然相同,那么此时transfer中的newTable的结构变成:
Entry[0] = B(.next) –> A(.next) –> null

此时第二个线程继续执行,进入这段代码:
[code]
do {
// 此时e为A,e.next为B,此行相当于next = B;
Entry next = e.next;
// 假设i=0
int i = indexFor(e.hash, newCapacity);
// newTable[0]为null,此行相当于A.next = null;
e.next = newTable[i];
// 此行相当于newTable[0] = A;
newTable[i] = e;
// 此行相当于e = B;
e = next;
} while (e != null);
[/code]
此时newTable的结构为:
Entry[0] = A(.next) –> null

e不为null,继续执行:
[code]
do {
// 此时e为B,e.next为A(第一个线程修改的),此行相当于next = A;
Entry next = e.next;
// 假设i = 0
int i = indexFor(e.hash, newCapacity);
// newTable[0]为A,此行相当于B.next = A;
e.next = newTable[i];
// 此行相当于newTable[0] = B;
newTable[i] = e;
// 此行相当于e = A;
e = next;
} while (e != null);
[/code]
此时newTable的结构为:
Entry[0] = B(.next) –> A(.next) –> null

e不为null,继续执行:
[code]
do {
// 此时e为A,A.next为null,此行相当于next = null
Entry next = e.next;
// 假设i = 0
int i = indexFor(e.hash, newCapacity);
// newTable[0]为B,此行相当于A.next = B;
e.next = newTable[i];
// 此行相当于newTable[0] = A;
newTable[i] = e;
// 此行相当于e = null;
e = next;
} while (e != null);
[/code]
此时newTable的结构为:
Entry[0] = A(.next) <--> B(.next)
无限循环就此造成,此时如果有线程要执行HashMap.get(A) ,就会直接进入无限循环,耗光CPU。

从上面的分析可以看出,要导致HashMap.get出现无限循环,还真有些不容易,至少要有两个线程在同时进行put,同时触发resize,并且之前一个桶里的两个相邻的对象在容量变了后仍然hash到了同样的数组位置中,这样才有可能导致问题,因此这现象只偶尔出现(不过我们以前曾经悲催的出现过一个集群重启,全部碰到了Velocity的那个错误使用HashMap的bug,导致严重故障)。

另外,关于之前发的Auto Box/Unbox,博客上@yongchun推荐了一篇不错的讲Java 5里Auto Box/Unbox的文章:
http://www.xyzws.com/Javafaq/what-should-i-know-about-autoboxing-and-unboxing-in-java-50/132

=============================
欢迎关注微信公众号:hellojavacases
关于此微信号:
用于分享Java的一些小知识点,Java问题排查的Cases,Java业界的动态,以及和大家一起互动讨论一些Java的场景和问题。

公众号上发布的消息都存放在http://hellojava.info上。

又一起并发场景下错误使用HashMap的Case

之前某天中午的时候突然收到一堆报警,有几台机器load过500了,赶紧到机器上排查是什么问题,先top看了下,cpu us接近100%,于是shift h看看线程的状况,发现没什么消耗高的线程,基本都在0.7%左右,但线程总数看起来很多,于是ps -eLf | grep java -c统计了下,总共有700+个线程,连续执行了几次jstack,然后先重启避免故障持续太久,重启完后看起来好了,查看之前jstack出来的线程信息,发现其中有600个线程处于RUNNABLE状态,并且都在执行HashMap.get,根据以往的经验,基本可以确定是在并发场景下错误使用HashMap造成的(关于常见的Java问题的排查方法可见此贴)。

根据堆栈信息找到相应的出问题的类名,然后根据classloader的装载机制(例如web应用通常在应用的war包/WEB-INF/lib下)找到相应的jar,用jd-gui反编译看了下相应的代码,代码中使用此HashMap的方式类似如下:
[code]
public class xxxxx{
private static Map> caches = new HashMap>();
public void load(){
caches = new HashMap>();
// 往此caches放东西
for…{
caches.put(…
}
}

public List get(String key){
return caches.get(key);
}
}
[/code]

当时堆栈中的信息显示600个线程均在执行caches.get(key),写这段代码的同学之前之所以在这个地方使用HashMap,并且没有加锁,是因为认为load这个方法只会在spring初始化当前这个bean的时候执行一次,但不幸的是后来由于业务发展,这个load方法在数据变更的时候会触发,于是就可能会出现正在往caches里put东西的时候,其他的线程在get,直接就导致并发问题,HashMap.get的并发问题有可能会导致get方法中的下面这段代码进入死循环:
[code]
for (Entry e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
[/code]
当然,出现这个现象不是HashMap的问题,主要还是使用的问题,因此这个问题的修复也很容易,就是用ConcurrentHashMap来替换。

这几天又在另外一个应用里造成出现了这个bug,有问题的代码类似如下:
[code]
private static Map… cache = new HashMap…

Object object = cache.get(key);

if(object == null){

object = 一个比较耗资源的获取Object动作…

cache.put(key,object);

}
[/code]
这段代码是在并发场景下执行的,因此同样是典型的bug,这段代码改造起来稍微麻烦点,即使是使用ConcurrentHashMap,也需要慎重处理,因此上面的整个动作是非原子性的操作(这个时候通常要引入Future)。

high cpu usage in hashmap.get是Google搜hashmap相关的词中的热词,可见这错误是挺容易犯的,诸如著名的Velocity、Hessian都犯过类似的错。
Hessian老版本中的类似bug:http://bugs.caucho.com/view.php?id=1588
Velocity老版本中的类似bug:https://issues.apache.org/jira/browse/VELOCITY-718

=====================华丽的分隔线

欢迎关注微信公众号:hellojavacases
关于此微信号:
用于分享Java的一些小知识点,Java问题排查的Cases,Java业界的动态,以及和大家一起互动讨论一些Java的场景和问题。

公众号上发布的消息都存放在http://hellojava.info上。

Java中容易踩到的”坑”系列之Auto Box/Unbox

Java中的Auto Box/Unbox对写代码带来了便利性,但也挺容易就踩进”坑“里。

例如这是最典型的Auto Box/Unbox的代码:
[code]
Integer i = 100;
int j = i;
[/code]
Auto Box/Unbox在有些场景下容易产生NPE,例如假设有一个这样的方法:
public void execute(int code)…
假设调用方是从一个Map或其他地方获取到的Integer,如果忘记判断是否为null,直接传给execute的方法,就有可能导致NPE。

下面这个关于Integer的Case也是比较常见的:
Integer i = 100;
Integer j = 100;
Integer m = 200;
Integer n = 200;
System.out.println(i == j);
System.out.println(m == n);
其执行结果为:true,false
原因是Integer会cache -128(-127)~127的Integer对象(感谢@yongchun的纠正),而不在这个范围的则会每次new Integer。

在JavaOne 2010大会上,还有一段关于Auto Box/Unbox带来的频繁YGC的案例代码,代码的关键信息如下:
[code]
public class A{
private int code;
public A(int code){
this.code = code;
}
public int get(){
return code;
}
}
public class Demo{
public statice void main(String[] args) throws Exception{
Map map = new HashMap();
// 往map里放1w个从1开始的A对象

while(true){
Collection values = map.values();
for(A a: values){
if(!map.containsKey(a.getId())){
// 不可能发生,所以可以随便打点什么
}
Thread.sleep(1);
}
}
}
}
[/code]
在上面的代码中,其实只需要把A中的private int code和public int get中的int改为Integer,就可以避免频繁的YGC,因此在写代码时还是要稍微注意下Auto Box/Unbox带来的影响。

————-互动问答—————–
问:能讲讲sun.misc.Unsafe的用法吗?
答:通常直接使用到Unsafe的都是一些特殊场景,例如对性能要求很高,或内存消耗很大的等等。
常见的是使用Unsafe来做反射的优化、内存的管理。
代码中通常有很多需要通过反射get/set来操作bean中的field,如果操作非常频繁的话,可以通过Unsafe来进行优化(在eclipse里使用Unsafe时需要修改下配置,否则会不能import,修改方法:Window->Preference->Java->Compiler->Errors/Warnings->Deprecated and restricted API -> Forbidden Reference 修改成Warning或Ignore),主要是通过Unsafe.objectFieldOffset和Unsafe.getXXX(例如getInt)来实现,代码如下:
[code]
public class User {

private String name;

public String getName() {
return name;
}

public void setName(String name) {
this.name = name;
}

}

import sun.misc.Unsafe;
import java.lang.reflect.Field;

public class UserTestForUnsafe {

private static final Unsafe unsafe;

static {
try {
Field field = Unsafe.class.getDeclaredField(“theUnsafe”);
field.setAccessible(true);
unsafe = (Unsafe) field.get(null);
}
catch (Exception e) {
throw new RuntimeException(“get unsafe fail”, e);
}
}

private static final Field nameField;
static {
try {
nameField = User.class.getDeclaredField(“name”);
}
catch (Exception e) {
throw new IllegalStateException(“get User.name error”, e);
}
}

public static final Field getNameField() {
return nameField;
}

public static void main(String[] args) throws Exception{
User user = new User();
user.setName(“bluedavy”);
long offset = unsafe.objectFieldOffset(nameField);
System.out.println(unsafe.getObject(user, offset));
}

}
[/code]
关于使用Unsafe直接进行内存管理,可参考这篇文章:
http://highlyscalable.wordpress.com/2012/02/02/direct-memory-access-in-java/

=============================
欢迎关注微信公众号:hellojavacases

关于此微信号:
用于分享Java的一些小知识点,Java问题排查的Cases,Java业界的动态,以及和大家一起互动讨论一些Java的场景和问题。

公众号上发布的消息都存放在http://hellojava.info上。

Java中容易踩到的“坑”系列之线程池篇

在有了java.util.concurrent包后,通常都会采用Executors或ThreadPoolExecutor来创建线程池,但这两个类都挺容易用错,如果不仔细阅读它的API或源码的话,很容易就踩进坑里。

通过new ThreadPoolExecutor可创建相应配置的线程池,但这个接口挺容易被误用,也许会导致行为和你想要的不太一样,之前在微博上我出了下面这道题。

有以下两个线程池:
ThreadPoolExecutor aPool = new ThreadPoolExecutor(10,20,5,TimeUnit.MINUTES,new SynchronousQueue<Runnable>());
ThreadPoolExecutor bPool = new ThreadPoolExecutor(10,20,5,TimeUnit.MINUTES,new ArrayBlockingQueue<Runnable>(10));
目前已有10个请求正在处理中,请问当第11个请求进来时aPool和bPool分别会如何处理?

从评论上来看,答错的人还是有一些的,这道题的正确答案是:
当第11个请求进来时,aPool会启动线程来立刻处理,bPool会放入BlockingQueue,等待前面的线程处理完才会被处理。

原因是ThreadPoolExecutor的实现机制为当目前运行的线程数 >= corePoolSize(也就是上面的10)时,ThreadPoolExecutor会将请求放进Queue中(例如上面的aPool是SynchronousQueue),如放失败且目前的线程数 < maxPoolSize(也就是上面的20),那么就直接启动新线程来处理,如目前运行的线程数等于maxPoolSize,则执行对应的策略,上面的aPool和bPool使用的都是默认的拒绝并跑出异常的策略;如放成功则进行再次的检查(例如线程池是否被shutdown、运行的线程数是否小于corePoolSize),然后返回。

SynchronousQueue是一个很特殊的Queue,当往这个Queue放东西时,必须有另外一个线程在从这个Queue里拿,如没有,则直接失败,在上面的场景中,当第11个请求进来时,往这个Queue中放就将失败,而这个时候运行的线程数又小于maxPoolSize,因此将启动新线程进行处理。
而bPool采用的是ArrayBlockingQueue,put将成功,可见在bPool的情况下,想要运行的线程数增加到11个,必须是10个线程已经在处理中,并且ArrayBlockingQueue已经排队了10个请求,那么这个时候如果再有第21个请求进来,才会启动第11个线程进行处理,刚用这个API时,很容易会认为只有当线程数已经达到了maxPoolSize后才会往Queue里放。

Executors是ThreadPoolExecutor的包装,基于它可以更简单的去创建线程池,但在使用它创建线程池也要特别的注意,下面就说说这个类中常用的几个方法创建的线程池的一些特征:

1. newCachedThreadPool
这种方式创建出来的线程池corePoolSize为0,maxPoolSize为Integer.MAX_VALUE,BlockingQueue为SynchronousQueue,因此这个线程池的行为为如线程均在运行中,新任务需要执行,则直接启动线程,直到运行的线程数达到Integer.MAX_VALUE。
这种线程池在某些情况下可能会创建非常大量的线程,鉴于这个原因,不推荐使用。
2. newFixedThreadPool
这种方式创建出来的线程池corePoolSize和maxPoolSize均为指定的大小,BlockingQueue为LinkedBlockingQueue,因此这个线程池的行为为如同时处理的请求小于指定的大小,那么就创建新的线程来处理,如达到了指定的大小,则放入Queue中。
这种线程池在某些情况下可能会出现Queue中堆积了很多的任务,导致内存被耗光的现象,因此也不推荐使用,如有类似需求,建议使用限定大小的ArrayBlockingQueue等。

最后无论是用哪种方式创建的线程池,最好都增加下名字,可通过实现ThreadPoolFactory接口来做到(例如这个),否则的话当线程池的线程处于等待任务处理时,如这个时候jstack,会看到一堆类似pool-x-thread-y的线程名字,类似如下:
[code]
“pool-19-thread-1” prio=10 tid=0x00007fe6676f8000 nid=0x17df7 waiting on condition [0x0000000072bee000]
java.lang.Thread.State: TIMED_WAITING (parking)
at sun.misc.Unsafe.park(Native Method)
– parking to wait for <0x00000000b0412c98> (a java.util.concurrent.locks.AbstractQueuedSynchronizer$ConditionObject)
at java.util.concurrent.locks.LockSupport.parkNanos(LockSupport.java:196)
at java.util.concurrent.locks.AbstractQueuedSynchronizer$ConditionObject.awaitNanos(AbstractQueuedSynchronizer.java:2025)
at java.util.concurrent.DelayQueue.take(DelayQueue.java:164)
at java.util.concurrent.ScheduledThreadPoolExecutor$DelayedWorkQueue.take(ScheduledThreadPoolExecutor.java:609)
at java.util.concurrent.ScheduledThreadPoolExecutor$DelayedWorkQueue.take(ScheduledThreadPoolExecutor.java:602)
at java.util.concurrent.ThreadPoolExecutor.getTask(ThreadPoolExecutor.java:947)
at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:907)
at java.lang.Thread.run(Thread.java:662)
[/code]
如这个时候问题出在这个线程池创建的线程过多时,那排查起来就比较麻烦些(那就只能挂起btrace来跟踪)。

=============================
欢迎关注微信公众号:hellojavacases
关于此微信号:
用于分享Java的一些小知识点,Java问题排查的Cases,Java业界的动态,以及和大家一起互动讨论一些Java的场景和问题。
公众号上发布的消息都存放在http://hellojava.info上。

答:Java线程创建相关的几个小知识点问题

昨天问题收到的两个典型答复如下:
1. 一个线程占用1m的空间,一直循环下去将会导致内存空间不足,进而占用swap区域,因此报第一个错;第二个错是因为swap区域亦不足,导致ls等命令都无空间可运行。
2. xss是一个线程的分配空间。题目设置的1m 一共2w 4w个当然会报内存溢出。

这两个回答都不正确。
正确的答案和原因是:
1. 当用-Xss1m执行时,VIRT会占用20000M左右,RES会很少,原因是线程启动后,只是会去先占用相应的栈大小的地址空间,但不会真正去占用内存,只有在真正需要使用的时候才会去占用;如果是在32bit机器上执行,Java进程会直接crash,原因是32 bit的linux默认每个进程最多申请3G的地址空间;

2. 可能会出现java.lang.OutOfMemoryError:unable to create new native thread的原因不是因为内存被耗光,而是因为os对每个用户能创建的最多进程/线程数的限制,限制的个数是多少可以通过ulimit -u进行查看,当创建的线程个数超过了os的这个值的限制,也会抛出上面的异常;

3. 可能会出现Resource temporarily unavailable的原因同样不是内存被耗光,像linux 2.6.18/32等内核默认的kernel.pid_max的值为32768,意味着在单台机器上最多创建32768个线程,即使ulimit -u的值超过32768也没用,因此如果在未调过kernel.pid_max的机器上执行创建4w个线程的代码,就会出现Resource temporarily unavailable。

之前微博上的九州-姬野之前给我分享了一个cpu sy高的排查case,挺有意思的,这里有个类似的case,感兴趣的可以看看:
http://structureddata.org/2012/06/18/linux-6-transparent-huge-pages-and-hadoop-workloads/

Java线程创建相关的几个小知识点问题

请问下面的这段代码:
[code]
public static void main(String[] args) throws Exception{

for(int i=0;i<20000;i++){

new Thread(new Runnable(){

public void run(){

try{

Thread.sleep(100000);

}

catch(Exception e){

// ignore

}

}

}).start();

}

}
[/code]
假设OS环境为Linux,JDK为Oracle JDK5/6/7,并采用此参数执行时:-Xss1m此Java进程占用的VIRT和RES分别会是多少,原因是?

另外,在执行此段代码时,可能会出现java.lang.OutOfMemoryError: unable to create new native thread,请问如出现此异常,可能是什么原因造成的?

如将上面的i<20000改为i<40000,再执行时(慎重执行此操作),同样可能会出现java.lang.OutOfMemoryError: unable to create new native thread,并且此时在shell中执行ls等操作时,可能会出现Resource temporarily unavailable,可能是什么原因造成的?

明天将来发文对上面的问题进行回答。