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对象占用多少内存呢？看一下源码：

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，我们来看看这两个东西：

// 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和持久化都做了支持。

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

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

// 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个对象头。所以这种多维数组还是要悠着点，不然可能连对象头都装不下。

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