性能大揭秘（之二）！CirroData-TimeS时序数据库文件格式的演化
如下图所示，TsFile文件格式分为几大块：
1、文件头（magic number）
2、数据部分
3、元数据部分（索引部分）
4、文件尾（magic number）
读取的流程如下：
1、读取文件元数据信息，把所有的deviceIndexMetadata都反序列化到内存中；
2、二分查找deviceIndexMetadata，找到对应的device的ChunkGroupMetadata；
3、读取该device下所有的ChunkMetaData到内存中；
4、二分查找ChunkMetaData，然后读取对应的数据。
实际生产过程中会遇到一个设备有几十万的传感器的情况，此时会加载大量与当前查询无关的ChunkMetaData信息，对查询性能也会有巨大的性能开销。
如何进行优化？
2.1 索引结构
既然每次查询时，一次性序列化一个设备下所有的传感器的元数据非常费时，比较直观的方式是再抽象一层索引出来，提高查询准确度，降低需要反序列化的元数据数量，带来的性能开销。
这里有一个权衡：是多读一次磁盘开销比较大，还是一次反序列化许多对象的时间比较大？
测试表明，当反序列化30万元数据对象时大概耗时250ms，而读一次磁盘大概也就8ms左右。因此当反序列化的对象比较多的时候，其开销超过了读磁盘的开销，那此时进行元数据分层索引来降低反序列化的对象个数，收益更大。
因此做第二代文件格式设计上做两点考虑：
第二代文件格式如下图所示：
有三个变化：
1、之前的deviceIndexData改成多层级索引树结构，分为internal_device和leaf_device两种节点：
internal_device属于中间层次的设备级索引，指向的是下一级internal_device或者leaf_device；
leaf_device是末尾的设备级索引，指向的是传感器级的索引，即internal_measurement或leaf_measurement。
2、添加新的索引层级，传感器级索引，分为internal_measurement和leaf_measurement两种节点：
internal_measurement属于中间层次的传感器级索引，指向的是下一级internal_measurement或者leaf_measurement；
leaf_measurement是末尾的传感器级索引，指向的是传感器级的元数据，即TimeseriesMetadata。
3、去掉chunkGroupMetaData，新增TimeseriesMetadata，之前是每个设备下的一批传感器的所有chunkMetaData索引在一起，现在改成按传感器来索引ChunkMetaData。这样组织，在只查询某个传感器的数据时，可以只加载与此传感器相关的数据，对于只是关注某个传感器的某段时间数据的查询比较友好。
分析下新文件格式中的io次数。
读取的流程如下：
1、读取文件元数据信息，把层的设备级索引都反序列化到内存中；
2、二分查找设备级索引，找到对应的传感器层的索引；
3、读取传感器层的索引，反序列化到内存中；
4、二分查找传感器层的索引，找到并读取该传感器下TimeseriesMetaData；
5、根据TimeseriesMetadata读取所有的ChunkMetaData到内存中；
6、二分查找ChunkMetaData，然后读取对应的数据。
可以看到比文件格式的版要多一次io，但是其序列化的元数据列表因为只跟要查询的传感器相关，会比较小，综合来看，查询性能会提升。
2.2 文件格式
如下图所示，TsFile文件格式仍然分为四大块：
1、文件头（magic number）
2、数据部分
3、元数据部分（索引部分）
4、文件尾（magic number）
2.2.1 文件头&文件尾
都是magic number，共12字节TsFile000002
2.2.2 数据部分
ChunkGroup
代表一个设备（device）的一段时间的数据，包含一系列Chunk，末尾还有一个ChunkFooter（用来记录deviceId信息）。
Chunk
代表一个传感器一段时间的数据，包含一个ChunkHeader和一系列Page。
Page
代表一个传感器一小段时间的数据，包含一个PageHeader和一系列点数据。其中点数据包含是时间列和数值列，一一对应。
2.3.3 元数据部分
ChunkMetaData
某个传感器某段时间的数据索引。
Timeseriesmetadata
某个传感器所有的数据元数据（chunkMetaData）索引。
TsFileMetadata
整个文件元数据根，包括索引树，版本信息，bloom过滤器等。
MetadataIndexNode
索引树的根，分层级架构，如上图所示。
目前实时数据库领域的有损压缩方法主要分为两大类：死区压缩和趋势压缩。
1、死区压缩：是将新值与上一次的记录值进行比较，当两者差的值小于误差允许阈值时，就抛弃该数据，反之保留该数据。死区压缩算法简单，但是压缩比低，很难满足实时数据库系统的要求。
2、趋势压缩：是根据测点的阶段性趋势进行压缩，原则上只记录满足趋势条件的起点和终点。趋势算法以PI公司的旋转门算法为代表，旋转门算法大大提高了实时数据库的压缩率，一般可以达到30:1的压缩比。
在设计第二代文件格式过程中，还引入了旋转门压缩算法来进一步提高压缩效果。
3.1 旋转门压缩算法
3.1.1 名词解释
3.1.2 算法流程说明
3.1.2.1 相关说明
绿色虚线：upperDoor, lowerDoor
灰色虚线：新节点加入时重新计算的upperDoor，lowerDoor
lowerDoor：当前segment 所有数据小的下斜率
upperDoor：当前segment 所有数据大的上斜率
红色实线：segment，实际上是存储 startpoint endpoint，后续解压缩时使用
lastStored：上一次保存的点，包含time和value，即lastStoredVal, lastStoredTime
lastRead：上一次读取的点，包含time和value
上下斜率计算方式：
3.1.2.2 压缩过程如下
如上图，数据加入及压缩流程：
1、新加入数据点p0，设置为lastStored，并保存下来
lastStored = p0 当数据为个数据或者超过CD时，标记lastStored，并加入compressedList；
2、upperDoor, lowerDoor 起始默认为关闭的（绿色虚线）
upperDoor 只能逆时针打开，lowerDoor 只能顺时针打开；
3、新加入数据点p1，计算p1 的 upperSlope，lowerSlope；
4、当前计算的upperSlope > upperDoor，lowerSlope < lowerDoor
两扇门分别打开，并更新其大小值；
因为p1 在CD 范围内，不会被保存，标记为lastRead。lastStored 依旧为 p0；
5、新加入数据点p2，重新计算upperSlope，lowerSlope。并更新upperDoor，lowerDoor；
6、新加入数据点p3，重新计算upperSlope，lowerSlope。并更新upperDoor。不更新lowerDoor，因为 lowerSlope > lowerDoor，lowerDoor 只能顺时针打开；
7、新加入数据点p4，重新计算upperSlope，lowerSlope。并更新lowerDoor，不更新upperDoor；
8、每次计算完上下斜率，进行upperDoor lowerDoor 检查是否超过平行；
9、加入p4 的时候。发现upperDoor >= lowerDoor，两扇门超过平行水平，数据范围已经超过了CD，需要保存上一个数据点lastRead p3
标记 lastStored = p3，compressedList 加入p3；
p3 作为segment0 endpoint；
p3 作为segment1 startpoint；
p4 和p3 进行比较，重新计算upperDoor，lowerDoor（绿色虚线）。
3.1.3 算法总结
1、个数据点需要保存；
2、第二个及以后的数据点，通过比较last read point
计算当前到segment startpoint 的上斜率，并和upperDoor 进行比较；
计算当前到segment startpoint 的下斜率，并和lowerDoor进行比较；
3、upperDoor 只能逆时针打开，lowerDoor 只能顺时针打开；
4、若两扇门处于或超过平行状态，并且当前点和上一存储点的时间间隔 >= comp min，存储last read point，并开启新的segment；
5、新的segment upperDoor，lowerDoor 计算通过当前数据和上一个segment endpoint 进行比较；
6、若当前点和上一存储点的时间间隔 >= comp max，存储当前点，开启新的segment；
7、若当前点和上一存储点的时间间隔 <= comp min，不存储当前点，防止noisy point；
8、若全部rawData 读取完毕，compressedList 只有个数据（所有数据偏差不超过CD）则加入后一个读取的数据点。
我们在原有的一些编码压缩方式上，再加上SDT压缩，混合起来可以获得超过30:1的压缩比，进一步节约存储成本。
到本篇为止，已经介绍完了代和第二代的文件格式。后续我们将继续介绍基于文件的读写逻辑，分析下一些分析数据框架如何基于文件对接。
来源：https://mp.weixin.qq.com/s/_LkzR-rlRQhOAlHae8vQUA
相关文章