Java高性能编程串讲-容易忽略的对象头

〇、前言(碎碎念)

哇好久没写博客了,不是我忘了,只是这段时间实在太忙了,再一个也想多积累积累,这样写出来的东西更厚实一点,这段时间看了netty和dubbo的一些源码(当然spring的一些其他的代码也有看),有空给大家分享一下。

这次主要讲下java的性能优化,涉及多线程,内存,磁盘,CPU等,不成体系,都是一些用到的小点,在这里做个记录。

内存篇

最近有一个需求,在业务中需要频繁的判断某些用户是否属于活跃用户,并找出非活跃用户,用户用id唯一标识,id是一个long,并且这批用户需要实时更新,因为离当前时间点越近操作过的用户越活跃。

这个问题可以转换为,n个long在内存中实现快速查找,并实现快速更新。

很快就能想到,用一个Set< Long>对所有活跃用户的id进行缓存,Set的查找速度非常之快,并且接口十分方便我们进行查找和添加操作,看起来是一个最优的选择。

真的如此简单吗?这一个学Java半天的程序员也能解决吧?

当然没这么简单,对于Set来说,如果这批用户量比较小,只有几W,那也没有什么问题,但是活跃用户量可能达到100W级别(数字脱敏),并根据不同的时间尺度数量级会发生很大的变化,时间尺度越大,人数可能更多。那放在Set里面有什么问题呢?

到linux服务器上,java -version,一般来说现在都是使用64位的JDK,64位的JDK有16B的对象头(数组对象有24B的对象头,多一个字节保存数组长度),HashSet本质上是一个value是一个固定的Object引用的HashMap,HashMap使用的是一个Entry<K, V>[]存储数据,那么100W个数据,就有100W个Entry对象,一个Entry对象占用多少内存呢?看一下源码:

1
2
3
4
5
6
7
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
...
}
  • int hash4B
  • K key是一个对于Long的引用,64位下占用8B,同时上面的hash内存对齐,hash实际占用8字节
  • V value是一个对于Object的引用(见Set源码),占用8字节
  • next是一个对Node的引用,占用8B
  • long被包装成了Long,占用16B的对象头+8字节的long value

你以为这就完了吗?naive,JDK8之后,hashmap会自动转换成红黑树,所有的Node数据结构也被转为TreeNode,TreeNode继承自LinkedHashMap.Entry,我们来看看这两个东西:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// LinkedHashMap.Entry
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
}

继续来看内存占用情况:

  • before, after两个引用占16B
  • parent, left, right, prev 四个引用占32B
  • red虽然内存边界是对的,但是整体数据结构需要内存对齐,故也占用8B

好来统计一下,Set里面装一个long需要多少字节呢?答案是128B,内存利用率是 8/128 = 6.25%。鼻血是不是都要出来了,那100W个数据需要多少内存呢?就是128MB,这显然是不能接受的。(你硬要说能接受也行8,内存大也没毛病)

好了,那用Set行不通了,怎么办呢,这么多对象头,这么多引用,太浪费了,直接用一个long[]不就搞定了吗?long[]只有一个对象,所以只有一个对象头,要查找的话,100W个数据在内存中二分查找的效率也是非常棒的(稍逊色于HashSet)。其实这已经可以当做是一个可选方案了(后面我们会讨论二分的效率问题),我们只需要8M的内存就解决了问题,并且效率也非常不错,但是添加数据会比较麻烦。

有没有更好的方法呢?仔细审题,我们重点是要找出非活跃用户,但其实这里没那么严格,100W个用户少找出10来非活跃用户个不会有任何区别,基于这个特点,我的脑海中浮现出了一个神奇的算法,叫做布隆过滤器。

布隆过滤器

布隆过滤器的原理大致讲一下,布隆过滤器用一个bit数组存储数据,对于一个加入布隆过滤器的元素,会进过k个哈希函数,然后布隆过滤器把k个散列的结果位都置为1,当要判断一个元素是否在布隆过滤器中时,先对这个元素进行k次散列,然后检查所有的散列结果在bit数组中的值是否全为1,如果都为1,则这个元素可能在布隆过滤器中,如果不都为1,则这个元素一定不在布隆过滤器中。

好了怎么用呢?目前实现比较好的布隆过滤器算法是guava,建议使用27版本以上,因为布隆过滤器一直被标位开发中,但是27版本以上的实现已经相当完备了,例如ThreadSafe和持久化都做了支持。

1
2
private static BloomFilter<Long> BLOOM = BloomFilter.create(
Funnels.longFunnel(), 1000000, 0.001);

这段代码的意思是说,预计有100W个元素会进入布隆过滤器,误判率为0.1%,这样,布隆过滤器会根据自身的算法计算出hash函数的最佳个数以及存储需要的bit数组,这里不做推导,虽然我会,嘻嘻~

1
2
3
4
// 1) Optimal k = b * ln2
// 2) p = (1 - e ^ (-kn/m))^k
// 3) For optimal k: p = 2 ^ (-k) ~= 0.6185^b
// 4) For optimal k: m = -nlnp / ((ln2) ^ 2)
  • k代表hash函数的个数
  • b代表m/n
  • m bit数组的大小
  • n 我们传入的100W
  • p 误判率

所以可以直接算出m的大小为不到146W,也就是说,内存占用量只用了1.8MB。并且其写入性能要稍优于HashSet,查询性能也非常快,只计算k个hash函数以及读几个bit位,guava使用的是murmur哈希算法,这个算法目前是性能以及散列效果最好的一个算法,这里不多介绍。

总结:

对于Java内存的使用,对象头是一个很容易忽略的细节,对于这种大量小数据结构的数据来说,使用HashSet是非常奢侈的,还有一个点,二维数组也是有n多个对象头的,long[1000][10]这种数组有1000个对象头,并且数组的对象头比非数组要多出8个字节(32位是4个),但是long[10][1000]只有10个对象头。所以这种多维数组还是要悠着点,不然可能连对象头都装不下。

二分法的搜索的性能问题下章会讲。

我不喝咖啡,但是我相信知识有价。