【运维填坑】高并发下如何用HashMap搞挂一台服务器

技术博客 / 运维   2016-11-28 01:05:16  阅读量: 8332
  运维   Java   优化   Debug  

前几天手里边管的一台hp-ux的服务器,从上周某一天起,CPU使用率较平常多出了10%左右,这台机器上起了5个java服务,查进程发现占用CPU高的就一个服务,8颗CPU里占满了整整一颗的资源,用jstack分析线程的heap dump,发现有一个线程java.util.HashMap.getEntry和java.util.HashMap.containsKey这两个方法的trace比较奇怪,trace特别长,然后用top看这个占CPU高的进程的线程调用资源情况,发现占用CPU高的线程就一个,就是那个奇怪的线程,感觉就是HashMap的调用哪个地方有点问题造成了死循环,导致一直占着CPU资源,但由于只多占用了10%的资源,就没特别关注。

但等到周一下午,这台机器的CPU突然飙升到了99%触发了报警,赶紧到机房分析heap dump,发现之前怀疑有问题的线程突然冒出七八个,一个线程占用掉1颗CPU的资源,瞬间就把8颗CPU资源全部占满,赶紧把heap dump文件交给开发一起分析,然后重启那个服务,CPU立马降下来了,暂时没啥问题。

后来经分析,确认该问题是由于多线程并发下造成的死循环问题,具体来说就是多线程对HashMap进行put操作后,get操作造成死循环

经查资料,造成该问题的原因大概可以参考如下连接:

http://blog.csdn.net/zhousenshan/article/details/52895874

http://coolshell.cn/articles/9606.html

大概可以做如下分析:

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 Collision DoS 问题》)。

所以,Hash表的尺寸和容量非常的重要。一般来说,Hash表这个容器当有数据要插入时,都会检查容量有没有超过设定的thredhold,如果超过,需要增大Hash表的尺寸,但是这样一来,整个Hash表里的无素都需要被重算一遍。这叫rehash,这个成本相当的大。

然后可以分析下HashMap各种方法的源码:

put:

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

检查容量是否超标:

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

如果容量超标,需要进行resize操作,将容量扩容为之前两倍:

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

问题就出在transfer这个函数上

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

在单线程情况下,当HashMap<K,V>的容量不够之后的扩容操作,将旧表中的数据赋给新表中的数据。正常情况下,新表的数据就会很正常,并且还需要说的一点就是,进行扩容操作之后,在旧表中key值相同的数据块在新表中数据块的连接方式会逆向。

尝试分析下多线程状况下该函数的调用:


       假设原来oldTable里存放a1,a2的hash值是一样的,那么entry链表顺序是:
       P1:oldTable[i]->a1->a2->null                 P2:oldTable[i]->a1->a2->null
       线程P1运行到上面transfer函数时,e=a1(a1.next=a2),继续运行,next=a2。这个时候切换到线程P2,线程P2执行完这个链表的循环。如果恰a1,a2在新的table中的hash值又是一样的,那么此时的链表顺序是: 
       主存:newTable[i]->a2->a1->null
       注意这个时候,a1,a2连接顺序已经反了。现在cpu重新切回P1,e.next = newTable[i];即:              a1.next=newTable[i];
       newTable[i]=a1;
       e=a2;
       开始第二次while循环(e=a2,next=a1):
       a2.next=newTable[i];//也就是a2.next=a1
       newTable[i]=a2
       e=a1
       开始第三次while循环(e=a1,next=null)
       a1.next=newTable[i];//也就是a1.next=a2
       这个时候a1.next=a2,a2.next=a1,形成回环了,这样就造成了死循环,在get操作的时候next永远不为null,造成死循环。

       put()过程造成了环形链表,但是它没有发生错误。一旦再调用get()就悲剧了。


周一下午出问题,恰恰是因为周一下午是业务高峰时间,并发量较大,导致上面的死循环发生概率增加,导致有多个有问题的线程,直接撑爆CPU。

后来开发得到解决方法将HashMap改为使用ConcurrentHashMap,通过把整个Map分为N个Segment(类似HashTable),可以提供相同的线程安全,但是效率提升N倍,默认提升16倍。

总结下这次填坑,这次这个问题,因为是java底层方法调用问题,如果不做heap dump分析线程的话,其实并不容易从现象发现问题原因,然后这个问题其实在测试环境并不容易重现,因为高并发多线程下触发这个问题并不容易,幸好叫早发现了多出10%的CPU占用提前分析过有了准备,加上已经有前辈踩过这个坑,留下了不少资料,要不然每次出问题只能通过重启服务来撑一段时间,不改HashMap调用的话根本不能从根本上解决问题。另外要感谢负载均衡这种架构,让出这种问题导致一台机器基本出于瘫痪状态时不会中断服务。