背景

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 / s696_427 record / s

堆外内存hashmap快的原因是它一开始就固定了分区，不会随着插入rehash，内存拷贝次数少

查询性能（get）

原生HashMap堆外内存hashMap
795_924 record / s701_283 record / s

堆外内存hashmap bucket数量手动优化的很好，每次查询复杂度为10个record，查询复杂度不高，但是由于其序列化和反序列化耗时，故查询性能稍差

内存占用

原生HashMap堆外内存hashMap
1.48GB1.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();
  }
}



  • No labels