时序数据库技术体系 – InfluxDB TSM存储引擎之TSMFile

为了更加系统的对时序数据库技术进行全方位解读,笔者打算再写一个系列专题(嘿嘿,好像之前事务专题还有几篇关于分布式事务的文章没有写完,后续一定会补上)-时序数据库技术专题,详细解读当前主流时序数据库中会涉及到的相关技术点。这个专题前面已经写过三篇暖场文章:

时序数据库 – 为万物互联插上一双翅膀》 - 介绍时序数据库的应用场景、时序数据库关注的核心技术点以及主流的几款时序数据库调研

时序数据库技术体系 – 时序数据库存储模型设计》-介绍主流的几款时序数据库在顶层设计层面的取舍,嗯,非常重要

时序数据库技术体系 – 初识InfluxDB》-介绍InfluxDB的一些基本概念、系统体系架构,为InfluxDB之后技术文章做个铺垫

接下来笔者将会用5篇左右的文章结合源码详细解读InfluxDB和Druid这两款时序数据库的核心技术实现,大体的文章脉络为:

《时序数据库技术体系 – InfluxDB TSM存储引擎之TSMFile》- 介绍InfluxDB中时序数据存储的文件格式,TSM存储引擎的核心

《时序数据库技术体系 – InfluxDB 多维查询之倒排索引》- 介绍InfluxDB如何使用倒排索引实现多维查询,倒排索引如何实现

《时序数据库技术体系 – InfluxDB 写入流程全解析》- 介绍时序数据写入InfluxDB之后的整个流程,包括WAL、写入内存、flush到文件三个基本部分

《时序数据库技术体系 – InfluxDB 读取流程全解析》- 介绍InfluxDB如何实现基本查询、多维度查询、聚合查询等

《时序数据库技术体系 – Druid 多维查询之Bitmap索引》- 介绍Druid系统最核心的Bitmap索引实现机制以及如何基于Bitmap索引实现多维表查询




言归正传,本篇文章主要介绍InfluxDB TSM存储引擎之TSMFile。为了保证时序数据写入的高效,InfluxDB采用LSM结构,数据先写入内存以及WAL,当内存容量达到一定阈值之后flush成文件,文件数超过一定阈值执行合并。这个套路与其他LSM系统(比如HBase)大同小异。不过,InfluxDB在LSM体系架构的基础上针对时序数据做了针对性的存储改进,官方称改进后的存储引擎为TSM(Time-Structured Merge Tree)结构引擎。本篇文章主要集中介绍TSM引擎中文件格式针对时序数据做了哪些针对性的改进,才使得InfluxDB在处理时序数据存储、读写方面表现的如此优秀。

TSM引擎核心基石-时间线

时序系列文章之时序数据存储模型设计介绍了InfluxDB时间线的概念以及相比其他时序数据库在数据模型设计上的优势,有兴趣的童鞋可以详细阅读上篇文章。这里做一个简单的概括,InfluxDB在时序数据模型设计方面提出了一个非常重要的概念:SeriesKey。SeriesKey实际上就是measurement+datasource(tags)。时序数据写入内存之后按照SeriesKey进行组织:



1

我们可以认为SeriesKey就是一个数据源,源源不断的产生时序数据,只要数据源还在,时序数据就会一直产生。举个简单的例子,SeriesKey可以认为是智能手环,智能手环可以有多个采集组件,比如说心跳采集器、脉搏采集器等,每个采集器好比上图中field1、field2和field3。心跳采集器可以不间断的采集用户的心跳信息,心跳信息就是紫色方框表示的时序数据序列。当然,智能手环非常之多,使用SeriesKey要唯一表示某个智能手环,就必须使用标签唯一刻画出该智能手环,所以SeriesKey设计为measurement+tags,其中measurement表示智能手环(类似于通常意义上的表),tags用多组维度来唯一表示该智能手环,比如用智能手环用户+智能手环型号两个标签来表示。

TSM引擎工作原理-时序数据写入

InfluxDB在内存中使用一个Map来存储时间线数据,这个Map可以表示为<Key, List<Timestamp|Value>>。其中Key表示为seriesKey+fieldKey,Map中一个Key对应一个List,List中存储时间线数据。其实这是个非常自然的想法,并没有什么高深的难点。基于Map这样的数据结构,时序数据写入内存流程可以表示为如下三步:

1. 时间序列数据进入系统之后首先根据measurement + datasource(tags)拼成seriesKey

2. 根据这个seriesKey以及待查fieldKey拼成Key,再在Map中根据Key找到对应的时间序列集合,如果没有的话就新建一个新的List

3. 找到之后将Timestamp|Value组合值追加写入时间线数据链表中

TSM文件结构

每隔一段时间,内存中的时序数据就会执行flush操作将数据写入到文件(称为TSM文件),整个文件的组织和HBase中HFile基本相同,对HFile文件比较了解的童鞋会很容易理解。相同点主要在于两个方面:

1. 数据都是以Block为最小读取单元存储在文件中

2. 文件数据块都有相应的类B+树索引,而且数据块和索引结构存储在同一个文件中

笔者参考InfluxDB最新代码按照自己的理解将文件结构表示为:

2

TSM文件最核心的由Series Data Section以及Series Index Section两个部分组成,其中前者表示存储时序数据的Block,而后者存储文件级别B+树索引Block,用于在文件中快速查询时间序列数据块。

Series Data Block

上文说到时序数据在内存中表示为一个Map:<Key, List<Timestamp|Value>>, 其中Key = seriesKey + fieldKey。这个Map执行flush操作形成TSM文件。

Map中一个Key对应一系列时序数据,因此能想到的最简单的flush策略是将这一系列时序数据在内存中构建成一个Block并持久化到文件。然而,有可能一个Key对应的时序数据非常之多,导致一个Block非常之大,超过Block大小阈值,因此在实际实现中有可能会将同一个Key对应的时序数据构建成多个连续的Block。但是,在任何时候,同一个Block中只会存储同一种Key的数据。

另一个需要关注的点在于,Map会按照Key顺序排列并执行flush,这是构建索引的需求。Series Data Block文件结构如下图所示:

3

Series Data Block由四部分构成:Type、Length、Timestamps以及Values,分别表示意义如下:

1. Type:表示该seriesKey对应的时间序列的数据类型,数值数据类型通常为int、long、float以及double等。不同的数据类型对应不同的编码方式。

2. Length:len(Timestamps),用于读取Timestamps区域数据,解析Block。

时序数据的时间值以及指标值在一个Block内部是按照列式存储的:所有的时间值存储在一起,所有的指标值存储在一起。使用列式存储可以极大提高系统的压缩效率。

3. Timestamps:时间值存储在一起形成的数据集,通常来说,时间序列中时间值的间隔都是比较固定的,比如每隔一秒钟采集一次的时间值间隔都是1s,这种具有固定间隔值的时间序列压缩非常高效,TSM采用了Facebook开源的Geringei系统中对时序时间的压缩算法:delta-delta编码。

4. Values:指标值存储在一起形成的数据集,同一种Key对应的指标值数据类型都是相同的,由Type字段表征,相同类型的数据值可以很好的压缩,而且时序数据的特点决定了这些相邻时间序列的数据值基本都相差不大,因此也可以非常高效的压缩。需要注意的是,不同数据类型对应不同的编码算法。

Series Index Block

很多时候用户需要根据Key查询某段时间(比如最近一小时)的时序数据,如果没有索引,就会需要将整个TSM文件加载到内存中才能一个Data Block一个Data Block查找,这样一方面非常占用内存,另一方面查询效率非常之低。为了在不占用太多内存的前提下提高查询效率,TSM文件引入了索引,其实TSM文件索引和HFile文件索引基本相同。TSM文件索引数据由一系列索引Block组成,每个索引Block的结构如下图所示:

4

Series Index Block由Index Block Meta以及一系列Index Entry构成:

1. Index Block Meta最核心的字段是Key,表示这个索引Block内所有IndexEntry所索引的时序数据块都是该Key对应的时序数据。

2. Index Entry表示一个索引字段,指向对应的Series Data Block。指向的Data Block由Offset唯一确定,Offset表示该Data Block在文件中的偏移量,Size表示指向的Data Block大小。Min Time和Max Time表示指向的Data Block中时序数据集合的最小时间以及最大时间,用户在根据时间范围查找时可以根据这两个字段进行过滤。

TSM文件总体结构

上文我们分别就Series Data Block以及Series Index Block进行了微观的分析,回过头我们再从宏观的角度将整个TSM文件表示为下图:

5

TSM引擎工作原理-时序数据读取

基于对TSM文件的了解,在一个文件内部根据Key查找一个某个时间范围的时序数据就会变得很简单,整个过程如下图所示:

6

上图中中间部分为索引层,TSM在启动之后就会将TSM文件的索引部分加载到内存,数据部分因为太大并不会直接加载到内存。用户查询可以分为三步:

1. 首先根据Key找到对应的SeriesIndex Block,因为Key是有序的,所以可以使用二分查找来具体实现

2. 找到SeriesIndex Block之后再根据查找的时间范围,使用[MinTime, MaxTime]索引定位到可能的Series Data Block列表

3. 将满足条件的Series Data Block加载到内存中解压进一步使用二分查找算法查找即可找到

文章总结

本文对InfluxDB的存储引擎TSM进行分析,主要介绍了TSM针对时序数据如何在内存中存储、在文件中存储,又如何根据文件索引实现在文件中查找时序数据。TSM存储引擎基于LSM存储引擎针对时序数据做了相应的优化,确实是一款相当专业的时序数据库!

参考文献

https://github.com/influxdata/influxdb/blob/master/tsdb/engine/tsm1/DESIGN.md

https://docs.influxdata.com/influxdb/v1.3/concepts/key_concepts/

https://docs.influxdata.com/influxdb/v1.3/concepts/storage_engine/

http://blog.fatedier.com/2016/08/05/detailed-in-influxdb-tsm-storage-engine-one/

http://blog.fatedier.com/2016/08/15/detailed-in-influxdb-tsm-storage-engine-two/

范欣欣

网易杭州研究院技术专家。负责网易内部Hadoop&HBase等组件内核开发运维工作,擅长大数据领域架构设计,性能优化以及问题诊断。 著有《HBase原理与实践》一书。 微信公众号:大数据基建。 邮箱:libisthanks@gmail.com。

在 “时序数据库技术体系 – InfluxDB TSM存储引擎之TSMFile” 上有 23 条评论

  1. 找到SeriesIndex Block之后再根据查找的时间范围

    这里只是一个TSM文件的情况下的路径吧,看起来服务器启动的时候需要加载所有文件的index,然后根据key进行分组,然后才能按照上面的流程进行读取。这样的话,最后一张图就稍微有点问题了

    1. 是的 最后一张图是针对一个TSM文件解释的 后面会有一篇文章会把整个查询流程的所有过程串起来

  2. 你好,我看文章开头提到了B+ 树:

    “而后者存储文件级别B+树索引Block”

    但是在查询过程中,这个是怎么用的呢?

    1. 文件级别B+树索引会加快Block的检索 这个在查询过程中使用就在下一片文章介绍 很快就会发布了 敬请期待 哈哈哈

  3. 文章写得非常棒,谢谢

    提一个小小的笔误,TSM全程应该是Time-Structured Merge Tree,文章中写成了`Timestamp Segments Merged Tree`

  4. 大佬好,请教一个问题。我看influxdb官方文档介绍了存储引擎演进的背景,leveldb存在问题是 每个shard是一个leveldb库,而单个库又有很多sstable文件导致文件句柄被占满。 tsm引擎为什么没有这个问题呢, 我看tsm也是每个shard下会有多个tsm data file

  5. 请教一个问题,从TSM文件的写入是追加写入吗?
    不同时间线的写入速度不同,会不会在写入data block数据时会有调整不同key的block的写入位置。
    例如:
    1、key=5的先在cache中达到阈值先flush写入datablock
    2、但是一段时间后key=2的数据才在cache中写满到阈值准备flush到磁盘
    3、此时写入key=2的data block的时候是不是要放在key=5的前面

    1. 同一个TSM文件中的数据是按照顺序排序的,不同TSM文件是不保证顺序的,所以查询涉及到多个TSM文件需要归并排序

  6. 1. 首先根据Key找到对应的SeriesIndex Block,因为Key是有序的,所以可以使用二分查找来具体实现
    这点不太明白,Key是由seriesKey+fieldKey组成,那么在一个SeriesIndex Section中就应该会有不同key组的SeriesIndex Block吧?这里如何二分查找?

发表评论

邮箱地址不会被公开。 必填项已用*标注