(Chinese) Aligned Timeseries Memory Storage Implementation Summary

对齐时间序列内存存储结构开发总结

一、问题背景

某用户有这样的测试场景，模拟100万设备，每个设备包含27列测点，共2700万个测点，每个测点每秒采集1条数据，每个设备27个测点数据采集的时间戳完全相同。

在现有的存储模型里，每个时间序列均会存储一列时间戳和一列值。由于设备内各序列时间戳相同，因此 27 列时间戳完全相同。因此，在内存中对于可按时间对齐的序列仅存储一列时间戳即可，即对齐的时间序列。在本场景中即可减少26次重复时间戳的写入，优化后写入数据量可减少至 28/54。

同样，原有非对齐序列，需要对各个序列按时间单独排序。排序也仅需要对唯一的时间列进行排序，排序的工作量可降低至1/27。

二、方案设计

针对上述背景，优化的主要思路为对多个时间戳相同的时间序列只存储一个时间戳列。为此分别设计了如下几种方案。

方案1: 行式存储（Object）

1. 将一行对齐的时间序列（Vector）作为一个measurement，写入memtable时一行Aligned Timeseries为一个时间戳加一个TsPrimitiveType类的数组。
2. 内存控制模块在写入前根据Vector每个子项的数据类型检查内存增量，进行内存统计
3. PrimitiveArrayManager增加Vector类的数组统计，类似目前TEXT类型的管理，只统计统计 TsPrimitiveType数组 的引用
4. 新增VectorTVList，结构为一个long型时间戳数组和一个Object类型数组

1. 写入Memtable时将放入VectorTVList中，VectorTVList在扩容时向PrimitiveArrayManager申请。
2. VectorTVList的其他接口参考BinaryTVList；
3. Flush时，按时间戳进行排序，再按行遍历时间戳和每个value，将这一行数据传给TsFile的ChunkWriter进行encoding。

方案2: 列式存储（Primitive Array）

1. 将对齐时间序列的内存结构作为一组PrimitiveArray的合集（时间列、索引列和多个值列）；
2. 内存控制模块在写入前根据Vector每个子项的数据类型检查是否需要向PrimitiveArrayManager申请新增Array，进行内存统计；
3. 新增VectorTVList，结构为一个long型时间Array和多个其他类型Array，同时每列维护bitmap用来记录空值， 和一个int 类型数组记录各个值列的rowIndex。bitmap默认为空指针，当客户端传入空值（insertRecord）或者传入代表空值的bitmap（insertTablet）时再创建出来；
4. 写入Memtable时，将insertPlan里的值放入VectorTVList中，VectorTVList在扩容时需向PrimitiveArrayManager申请需要的Array类型；
5. VectorTVList排序时只需要排时间列和rowIndex列；
6. Flush时，按时间戳进行排序时间戳列和rowIndex列，之后的遍历方式为先找到一个时间戳，和对应的rowIndex，再根据rowIndex和bitMap找到各个值列对应的真实值和是否为null，将这一行数据传给TsFile的ChunkWriter进行encoding。

方案3: 行式存储（bytes版）

1. 将一行Vector作为一个measurement，写入memtable时，一行Vector为一个时间戳和多个值序列化成的一个byte数组，同时使用bitmap记录每一行的空值情况。
2. 内存控制模块在写入前根据Vector每个子项的数据类型检查内存增量，进行内存统计
3. 新增VectorTVList，结构为一个long型时间戳数组和一个bytes数组，每行维护一个bitmap记录空值
4. PrimitiveArrayManager增加Vector类的数组统计，类似目前TEXT类型管理，只统计 byte数组的引用；
5. 写入Memtable后放入VectorTVList中，VectorTVList在扩容时向PrimitiveArrayManager申请；
6. VectorTVList的其他接口参考BinaryTVList
7. Flush时，按时间戳进行排序，再按行遍历时间戳并将对应的bytes值反序列化成具体的值，将这一行数据传给TsFile的ChunkWriter进行encoding。

三、方案评估

方案1行式存储优点 ：

1. 对null友好，无需维护bitmap记录空值
2. 排序逻辑与现有其他类型完全相同，排序时会实际更新值列

方案1行式存储缺点：

1. 需要将数据装箱，内存利用率较低。以int类型为例，需要先装箱为TsPrimitiveType，再装箱为TsPrimitiveType数组，内存占用为实际内存占用的3倍，会导致一个Chunk太小，影响写入性能。
2. 不能复用ArrayPool管理内存

方案2列式存储优点：

1. 节省对象装箱，节省内存占用
2. 可复用现有的PrimitiveArrayPool管理数组
3. 排序时可通过排rowIndex，节省排序开销

方案2列式存储缺点：

1. 需要维护bitmap用来记录空值
2. 根据rowIndex去索引真实值可能造成encoding速度下降

方案3行式存储（bytes版）优点 ：

1. 解决方案1内存占用过大的问题
2. 排序逻辑与现有其他类型完全相同，排序时会实际更新值列

方案3行式存储（bytes版）缺点：

1. 需要编码解码来读取数据，效率低下
2. 不能复用ArrayPool管理内存
3. 对空值不友好
4. 对TEXT类型的数据不友好，需要找到bytes 中对应的offset和length来读取

四、实验验证

1.目标

比较行式和列式存储在排序和遍历功能上的时间开销，以及存储的性能开销

2.Vector测试代码

排序均使用快速排序，模拟真实写入遍历场景，所以三种方式的主要不同有一下几点：

• 存储字段定义
• 排序交换方法
• 查询方法

（1）行式存储

字段定义：

long[] timeList;

Object[][] valueList;

排序交换方法：

private void swap(int start, int end){

  long temp = timeList[start];

  timeList[start] = timeList[end];

  timeList[end] = temp;

  Object[] tempO = valueList[start];

  valueList[start] = valueList[end];

  valueList[end] = tempO;

}

查询方法：

// loc: column index

public List<Integer> query(int loc){

  List<Integer> res = new ArrayList<>();

  for (int i = 0; i < timeList.length; i++) {

      res.add((Integer) valueList[i][loc]);

  }

  return res;

}

（2）列式存储

字段定义（其中index列用来存储排序后的下标）：

long[] timeList;

List<int[]> valueList;

int[] indexList;

排序交换方法：

private void swap(int start, int end) {

  long temp = timeList[start];

  timeList[start] = timeList[end];

  timeList[end] = temp;

  int indexTemp = indexList[start];

  indexList[start] = indexList[end];

  indexList[end] = indexTemp;

}

查询方法：

// loc: column index

public List<Integer> query(int loc){

  List<Integer> res = new ArrayList<>();

  int[] col = valueList.get(loc);

  for (int j = 0; j < timeList.length; j++) {

    res.add(col[indexList[j]]);

  }

  return res;

}

（3）列式存储（bytes版）

字段定义（其中index列用来存储排序后的下标）：

long[] timeList;

ByteBuffer[] valueList;

排序交换方法：

private void swap(int start, int end){

  long temp = timeList[start];

  timeList[start] = timeList[end];

  timeList[end] = temp;

  ByteBuffer tempO = valueList[start];

  valueList[start] = valueList[end];

  valueList[end] = tempO;

}

查询方法：

// loc: column index

public List<Integer> query(int loc){

  List<Integer> res = new ArrayList<>();

  for (int i = 0; i < timeList.length; i++) {

    ByteBuffer cur = valueList[i];

    cur.position(loc * 4);

    res.add(cur.getInt());

    cur.position(0);

  }

  return res;

}

1. 应用场景

写入场景

模拟实际应用场景，用户按行写入的场景较多，乱序数据较多。

查询场景

用户可能查对齐时间序列内的1列、30列、100列等等。

测试重点关注：内存占用、write 速度、sort速度、遍历速度、查询

4.内存测试

在行数为10,000，列数为3,200，数据类型均为int的情况，内存测试结果如下：

结论：由于方案一存Object的行式存储占用空间过大（是列式的5倍），所以直接排除掉了，下面只测试列式和行式（byte数组）方式。

5.写入性能测试

在多种情况下测试结果基本一致（指两者的对比一致，不是绝对数值），放出一组数据共参考

行数：10,000

列数：3,200

查询列数：30

乱序比例：10%

写入方式：列式按列写入，行式按行写入

结论：方案二列式存储与方案三行式存储（bytes版）在排序和查询过程的耗时基本相同。但在写入过程中，方案三行式存储为方案二耗时的4倍。因此，方案二的性能更符合要求。

五、最终结论

经综合比较，由于方案一内存浪费过大，方案三写入耗时较高、性能较差，最终选择方案二列式存储方案作为Vector数据类型内存存储结构。