背景
Java原生的HashMap受限于Java对象限制,对key和value都必须抽象封装为一个类,其实现为闭地址法哈希+红黑树,hash槽中的节点为Node,需要存储左右孩子节点等信息,连同其引用一个Node占用内存为32字节。综上,每存储一个键值对就需要额外48字节的对象头及指针,内存空间开销大。
目标
调研开源的基于堆外内存或内存buffer的Java hashmap实现,避免对象头及指针的额外内存开销
实现
https://github.com/cfelde/BinaryOffheapHashMap/blob/master/README.md
实现原理
使用堆外内存+开地址法散列,将key和value都序列化为二进制数组,利用unsafe模块直接申请堆外内存存储,每次插入需要序列化,每次查询需要反序列化,由于存储的内容为序列化的二进制数组,不包含指针和对象头,避免了额外的内存开销
实验
实验场景
基于海量时间序列元数据场景,测试在内存ID表中两者的性能
每时间序列标识长度为200字节,共有1000万时间序列,其中有10万个device,每个device下有100个measurement,其中measurement占用20字节
数据结构为:Map<DeviceID, Map<String, SchemaEntry>>
其中map分别使用java原生HashMap及基于堆外内存的map实现
堆外内存的HashMap由于使用开地址法,需要设置bucket数量,本实验中按照每10个元素分配一个bucket
实验设置
共有1000万时间序列,其中有10万个device,每个device下有100个measurement,其中measurement占用20字节
将1000万时间序列写入map中,并进行一千万次查询,测试其插入和查询性能,最后观察其内存占用情况
实验目标
堆外内存map与java原生HashMap在以下方面的性能:
- 插入性能(put)
- 查询性能(get)
- 内存占用
实验结果
插入性能(put)
原生HashMap | 堆外内存hashMap |
---|---|
594_212 record / s | 696_427 record / s |
堆外内存hashmap快的原因是它一开始就固定了分区,不会随着插入rehash,内存拷贝次数少
查询性能(get)
原生HashMap | 堆外内存hashMap |
---|---|
795_924 record / s | 701_283 record / s |
堆外内存hashmap bucket数量手动优化的很好,每次查询复杂度为10个record,查询复杂度不高,但是由于其序列化和反序列化耗时,故查询性能稍差
内存占用
原生HashMap | 堆外内存hashMap |
---|---|
1.48GB | 1.15 GB |
堆外内存hashmap节省了内存中每个record的HashMap Node的32字节的内存占用,共10M个record,故节省了320MB左右的内存
实验结论
(1)堆外哈希表需要手动设置bucket数量,且之后不能动态扩容,在预先知道record数量的时候进行合理调参,插入时不用rehash,可以在插入性能上超过原生哈希表
(2)堆外哈希表每次查询都需要反序列化,导致查询性能不如原生HashMap
(3)堆外哈希表的性能很大程度上取决于bucket的数量是否设置合理,太小会导致写入和查询性能下滑,太大会浪费内存,在record数量不确定的情况下bucket参数不好确定
(4)内存占用方面堆外哈希表节省了原生HashMap Node的内存开销,每时间序列可以减少32字节内存开销
实验源码
import java.io.IOException; import java.util.Map; import schema_id.bohmap.BOHMap; import schema_id.bohmap.OHMap; public class Main { static Map<DeviceID, Map<String, SchemaEntry>> map; private static final int deviceNum = 100_000; private static final int sensorName = 100; private static final int sensorLen = 10; public static void main(String[] args) throws InterruptedException, IOException { putMap(); getMap(); // for checking memory Thread.sleep(100000000); } private static void putMap() { long curTime = System.nanoTime(); for (int i = 0; i < deviceNum; i++) { //Map<String, SchemaEntry> cur = new HashMap<>(128, 1f); Map<String, SchemaEntry> cur = new OHMap<String, SchemaEntry>(new BOHMap(10), Serializer::stringSer, Serializer::stringDes, Serializer::schemaSer, Serializer::schemaDes); map.put(new DeviceID(i), cur); for (int j = 0; j < sensorName; j++) { cur.put(buildString(i, j), new SchemaEntry(1,1,1,1)); } } System.out.println(map.size()); int count = 0; for(Map<String, SchemaEntry> inner : map.values()){ count += inner.size(); } System.out.println(count); long finishTime = System.nanoTime(); System.out.println("write finished time: " + (finishTime - curTime) / 1000 / 1000 + " ms."); } private static void getMap() { long curTime = System.nanoTime(); long count = 0; for (int i = 0; i < deviceNum; i++) { Map<String, SchemaEntry> cur = map.get(new DeviceID(i)); for (int j = 0; j < sensorName; j++) { SchemaEntry schemaEntry = cur.get(buildString(i, j)); count += schemaEntry.lastTime; } } long finishTime = System.nanoTime(); System.out.println(count); System.out.println("read finished time: " + (finishTime - curTime) / 1000 / 1000 + " ms."); } private static String buildString(int d, int s){ StringBuilder sb = new StringBuilder(); sb.append(d); sb.append("_"); sb.append(s); while (sb.length() < sensorLen){ sb.append('c'); } return sb.toString(); } }