在时序数据库概述一文中, 笔者提到时序数据库的基础技术栈主要包括高吞吐写入实现数据分级存储|TTL 数据高压缩率多维度查询能力以及高效聚合能力等, 上文时序数据库技术体系 InfluxDB 存储引擎 TSM 基于 InfluxDB 存储引擎 TSM 介绍了时序数据库的高性能写入能力以及基于列式存储的数据高压缩率实现接下来两篇文章分别基于 InfluxDB 系统的倒排索引实现以及 Druid 系统的 Bitmap 索引实现介绍时序数据库的多维度查询实现原理
InfluxDB 系统 TSM 存储引擎个人认为有两个最核心的工作模块, 其一是 TSM 针对时序数据在内存以及文件格式上做了针对性的优化, 优雅地实现了时序数据的高效率写入以及高压缩率存储, 同时文件级别的 B + 树索引可以有效提高时序数据根据 SeriesKey 查询时间序列的性能; 其二是 InfluxDB 系统还实现了内存以及文件级别的倒排索引, 有效实现了根据给定维度 fieldKey 查询对应 SeriesKey 的功能, 这样再根据 SeriesKeyfieldKey 和时间间隔就可以在文件中查找到对应的时序数据集合
上文笔者提到 SeriesKey 等于 measurement+tags(datasources), 其中 measurement 表示一张时序数据表, tags(多组维度值)唯一确定了数据源用户的查询通常有以下两种查询场景, 以广告时序数据平台来说:
1. 查看最近一小时某一个广告 (数据源) 总的点击量, 典型的根据 SereisKeyfieldKey(点击量)和时间范围查找时序数据, 再做聚合(sum)
2. 统计最近一天网易考拉 (指定广告商) 发布在网易云音乐 (指定广告平台) 的所有广告总的点击量这种统计查询并没有给出具体的广告 (SeriesKey), 仅指定了两个广告维度(广告商和广告平台) 以及查询指标 点击量这种查询就首先需要使用倒排索引根据 measurement 以及部分维度组合 (广告商 = 网易考拉, 广告平台 = 网易云音乐) 找到所有对应的广告源, 假如网易考拉在网易云音乐上发布了 100 个广告, 就需要查找到这 100 个广告点击量对应的 SeriesKey, 再分别针对所有 SeriesKey 在最近一天这个时间范围查找点击量数据, 最后做 sum 聚合
如何根据 measurement 以及部分维度组合查找到所有满足条件的 SeriesKey?InfluxDB 给出了倒排索引的实现, 称之为 TimeSeries Index, 意为 TimeSeries 的索引, 简称 TSIInfluxDB TSI 在 1.3 版本之前仅支持 Memory-Based Index 实现, 1.3 之后又实现了 Disk-Based Index 实现
Memory-Based Index
Memory-Based Index 方案将所有 TimeSeries 索引加载到内存提供服务, 核心数据结构主要有:
其中 seriesByTagKeyValue 是一个双重 map, 即 map<tagkey, map<tagvalue, List<SeriesID>>>以上文中广告商 = 网易考拉为例来解释:
tagkey 为广告商, 广告商可以有网易考拉, 还可能有网易严选, 所以一个广告商这个 tagkey 对应一个 mapmap 的 key 是 tagvalue,value 是 SeriesID 集合示例中 tagvalue 为网易考拉, 映射的值为 SeriesID 集合
因此上文中第二种查询场景就可以通过下述步骤完成:
1. 通过 seriesByTagKeyValue 这个内存结构以及给定的维度值广告商 = 网易考拉找到所有包含该维度值的 SeriesID 集合
2. 同样的方法, 通过 seriesByTagKeyValue 以及给定的维度值广告平台 = 网易云音乐找到包含该维度值的 SeriesID 集合
3. 两个 SeriesID 集合再做交集就是同时满足广告商 = 网易考拉, 广告平台 = 网易云音乐的所有 SeriesID
4. 再在 SeriesByID map<SeriesID, SeriesKey > 中根据 SeriesID 集合映射查找到 SeriesKey 集合
5. 最后根据 SeriesKey 集合以及时间范围找到所有满足条件的时序数据集合
这里为什么使用 SeriesID 作为跳板找到 SeriesKey, 而不是直接映射得到 SeriesKey? 因为 seriesByTagKeyValue 这个结构中索引到的 SeriesKey 会有大量冗余, 一个 SeriesKey 包含多少 Tag 组合, 就会有多少份冗余举个简单的例子:
假如现在有 3 个 Tag 组合形成一个 seriesKey:measurement=mm,tagk1=tagv1,tagk2=tagv2,tagk3=tagv3 那么构造形成的双重 Map 结构 seriesByTagKeyValue 就会为:
- <tagk1, <tagv1, seriesKey>>
- <tagk2, <tagv2, seriesKey>>
- <tagk3, <tagv3, seriesKey>>
此时, 假如用户想找 tagk1=tagv1 这个维度条件下的 seriesKey, 那第一个 map 就满足条件很显然, 这种场景下 3 个 Tag 组成的 seriesKey, 最终形成的 seriesByTagKeyValue 就会有 3 重 seriesKey 冗余
因此使用 Int 类型的 SeriesID 对 SeriesKey 进行编码, 将长长的 SeriesKey 编码成短短的 SeriesID, 可以有效减少索引在内存中的存储量另外, SeriesID 集中存储在一起可以使用 Int 集合编码有效压缩
Memory-Based Index 实现方案好处是可以根据 tag 查找 SeriesKey 会非常高效, 但是缺点也非常明显:
1. 受限于内存大小, 无法支持大量的 TimeSeries 尤其对于某些基数非常大的维度, 会产生大量的 SeriesKey, 使用 Memory-Based Index 并不合适
2. 一旦 InfluxDB 进程宕掉, 需要扫描解析所有 TSM 文件并在内存中全量构建 TSI 结构, 恢复时间会很长
Disk-Based Index
正因为 Memory-Based Index 存在如此重大的缺陷, InfluxDB 1.3 之后实现了 Disk-Based IndexDisk-Based Index 方案会将索引持久化到磁盘, 在使用时再加载到内存 InfluxDB 官网对 Disk-Based Index 实现方案做了如下说明:
不难看出, InfluxDB 中倒排索引和时序数据使用了相同的存储机制 LSM 引擎因此倒排索引也是先写入内存以及 WAL, 内存中达到一定阈值或者满足某些条件之后会执行持久化操作, 将内存中的索引写入文件当磁盘上文件数超过一定阈值会执行 Compaction 操作进行合并实际实现中, 时序数据点写入系统后会抽出 MeasurementTags 并拼成 SeriesKey, 在系统中查看该 SeriesKey 是否已经存在, 如果存在就忽略, 否则写入内存中相应结构 (参考 log_file 文件中变量 InMemory Index) 接着内存中的数据会 flush 到文件(参考 log_file 文件中 CompactTo 方法), 接下来笔者将会重点介绍 TSI 文件格式, 如下图所示:
TSI 文件主要由 4 个部分组成: Index File Trailer,Measurement Block,Tag Block 以及 Series Block
1. File Trailer 主要记录 Measurement BlockTag Block 以及 Series Block 在 TSI 文件中的偏移量以及数据大小
2. Measurement Block 存储数据库中表的信息, 通常来说 Measurement 不会太多, 一个 Block 也就够了
3. Tag Block 实际上是 seriesByTagKeyValue 这个双重 map map<tagkey, map<tagvalue, List<SeriesID>>>在文件中的实际存储
4. Series Block 存储了数据库中所有 SeriesKey
Measurement Block
Measurement Block 存储数据库中所有时序数据表表名信息, Block 主要由三部分组成: Block Trailer SectionHash Index Section 以及 Measurement Entry Section
1. Block Trailer Section 记录了 Hash Index Section 以及 Measurement Data Section 在文件中的偏移量以及数据大小, 是 Measurement Block 读取解析的入口
2. Hash Index 是一个 Hash 索引实现机制很简单, 就是一个 Map 结构 map<measurement, offset > 使用 Hash 函数将给定 measurement 映射到数组的特定位置, 将该特定数组位的值置为该 measurement 在文件中的实际偏移量 Hash Index 主要有两个核心作用:
(1)加快 Measurement 的查找效率正常情况下在 Block 中查找某个 Measurement Entry 只能依次遍历查找, 或者二分查找, 而使用 Hash 索引可以直接在 o(1)复杂度找到待查 Measurement
(2)减小内存开销如果没有 Hash Index, 在 Measurement Block 中查找一个 Measurement Entry, 需要将该 Block 全部加载到内存再查找 Measurement Block 本身大小不特定, 有可能很大, 也可能很小, 一旦 Block 很大的话内存开销会非常之大而使用 Hash Index 的话, 只需要将 Hash Index 加载到内存, 根据 Hash Index 定位到 Measurement Entry 具体的 offset, 直接根据偏移量加载具体的待查找 measurement
3. Measuremen 是具体的时序数据表, 比如广告信息表等 Measurement 是一个复合结构, 由一系列字段组成, 其中 name 表示指标名, TagBlock offset 以及 TagBlock size 表示该 Measurement 所对应的 TagBlock 在索引文件中的偏移量以及大小因此可以使用 Measurement 过滤掉大量不属于该 Measurement 的 Tags
Tag Block
TagBlock 中存储同一个 Measurement 下的 TagsTag Block 由三部分组成: Block TrailerTag Key Section 以及 Tag Value Section:
1. Block Trailer: 存储 Tag Key Hash Index 的 offset 以及 size,TagKey Section 的 offset 以及 size,TagValue Section 的 offset 以及 size 通过解析 Trailer, 可以快速找到 Block 中各个部分的解析入口
2. Tag Key Section: 存储指定 Measurement 下所有维度名信息, 比如广告时序数据有 publisheradvertisergendercountry 等维度每个 Tag Key 由多个字段组成, 是一个复合结构, 如下图所示:
其中 key 字段表示维度名, TagValue 相关字段 (TagValue.offsetTagValue.size,) 表示该维度下所有维度值在文件中的存储区域
3. Tag Value Section: 存储某个维度下的所有维度值比如广告时序数据中 advertiser 这个维度可能有多个值, 比如 google.combaidu.com163music.com 等等一系列值, 所有这些值会集中存储在一起, 这个区域就是 advertiser 维度对应的 Tag Value Section 同理, 其他维度诸如 publishergendercountry 等都会有对应的 Tag Value SectionTag Value Section 中每个 Tag Value 也是一个复合结构, 如下图所示:
其中 value 字段和 series.data 两个字段是需要重点关注的两个字段前者表示具体的维度值, 后者表示这个维度值对应的一系列 SeriesKey 注意, 存储的时候并没有直接存储 SeriesKey, 而是存储 SeriesID 上文重点说明了存储 SeriesID 而不直接存储 SeriesKey 的原因
关于 Tag Block, 笔者在思考的时候一直在思考两个问题:
1. Tag Block 中每个数据 Section 都有对应的 Hash Index, 用来加速查找但是有没有注意到 Hash Index 只能实现等值查找加速, 但是不能实现范围查找, 比如大于小于条件查找假如现在用户想要根据维度 advertiser=163music.com 查找对应的所有 seriesKey, 可以很容易:
(1)在 Tag Key Section 的 Hash Index 一下子就找到对应 Tag Key(advertiser)在文件中的 offset
(2)再从文件中加载出 Tag Key, 解析出 advertiser 对应的 Tag Value Section 在文件中的 offset
(3)根据 Tag Vlaue Section 在文件中的 offset 加载出 Tag Value Section 对应的 Hash Index, 使用 163music.com 在 Hash Index 中就可以一下子找到对应的 Tag Value 的 offset
(4)根据 offset 加载出 Tag Value 对应的 series.data, 即对应的一系列 SeriesID, 即一系列 SeriesKey
但是, 如果用户想查询 advertiser>163music.com 对应的所有 seriesKey, 怎么玩? 很显然, 只根据 Hash Index 是玩不转的 (有一种结构可以玩的转 B + 树, 上篇文章有提到过), 这里教大家一招, 如果能够保证数据(Tag Value Section 中 Tag Value 有序存储) 的有序, 就可以玩的转了也就是说, Hash Index + 有序就可以实现 B + 树可以实现的快速范围查找这一招很有用!
2. 根据 SeriesID 如何找到对应的 SeriesKey? 首先 SeriesKey 是如何映射为 SeriesID 的(即字典编码的实现), 其次 SeriesID 与 SeriesKey 的对应关系是否需要存储下来? 读完下文才会明白
Series Block
Series Block 用来存储整个数据库中所有 SeriesKey, 有的童鞋肯定会说了整个数据库中辣么多 SeriesKey, 只放在一个 Block 中是不是不合适? 笔者之前也是如此想的, 不过了解了 Series Block 的结构之后就释然了 Series Block 主要由四部分构成: Block TrailerBloom Filter SectionSeries Index Chunk 以及一系列 SeriesKeyChunk
1. Block Trailer: 和其他 Block Trailer 一样, 主要存储该 Block 中其他 Section 在文件中的偏移量以及大小, 是读取解析 Block 的入口
2. Bloom Filter Section: 和 Hash Index 基本一样的原理, 不过 Bloom Filter 只用来表征给定 seriesKey 是否已经在文件中存在
3. Series Index Chunk:B + 树索引, 由多个 Index Entry 组成, 每个 Index Entry 又由三个部分构成, 分别是 CapacityMinSeriesKeyHashIndex 如下图所示:
其中 MinSeriesKey 作为 B + 树的节点值, 用来与给定检索值进行对比, 比之大则继续查找右子树, 比之小则查找左子树 HashIndex 又是一个 Hash 索引, 如果确定待检索 seriesKey 的叶子索引节点就是该 Index Entry, 就使用该 Hash Index 直接进行定位
4. Series Key Chunk: 存储 SeriesKey 集合, 如下图所示, SeriesKey 字段是一个复合结构, 字段中记录所有包含的 Tag 信息以及 seriesKey 的命名
了解完 Series Block 的结构之后, 你就知道这个 Block 可不一般, 一个 Block 内部竟然有 B + 树索引, 这个配置可是有点高级的而且索引节点中竟然有 Hash Index 可见这个 Block 的配置绝对是文件级别的配置如果对 HBase 中 HFile 熟悉的童鞋很容易明白, 这个 Block 的结构和 HFile 的结构其实很像
内存中倒排索引构建
1. 时序数据写入到系统之后先将 measurement 和所有的维度值拼成一个 seriesKey
2. 在文件中确认该 seriesKey 是否已经存在, 如果已经存在就忽略, 不需要再将其加入到内存倒排索引那问题转化为如何在文件中查找某个 seriesKey 是否已经存在? 这就是 Series Block 中 Bloom Filter 的核心作用
(1)首先使用 Bloom Filter 进行判断, 如果不存在, 肯定不存在如果存在, 不一定存在, 需要进一步判断
(2)使用 B + 树以及 HashIndex 进一步判断
3. 如果 seriesKey 在文件中不存在, 需要将其写入内存这里可以将内存中的结构理解为两个核心数据结构:
(1)<measurement, List<tagKey>>, 表示时序表与对应维度集合的映射
(2)seriesByTagKeyValue 那样一个双重 Map 结构:<tagKey, <tagValue, List<SeriesKey>>>
倒排索引 flush 成文件
1. <measurement, List<tagKey>>以及 < tagKey, <tagValue, List<SeriesKey>>都需要经过排序处理, 排序的意义在于有序数据可以结合 Hash Index 实现范围查询, 另外 Series Block 中 B + 树的构建也需要 SeriesKey 排序
2. 在排序的基础上首先持久化 < tagKey, tagValue, List<SeriesKey>>结构中所有的 SeriesKey, 也就是先构建 Series Block 以此持久化 SeriesKey 到 SeriesKeyChunk, 当 Chunk 满了之后, 根据 Chunk 中最小的 SeriesKey 构建 B + 树中的 Index Entry 节点当然, Hash Index 以及 Bloom Filter 是需要实时构建的这个过程类似于 HFile 的构建过程以及上篇文章 TSM 文件的构建过程但与 TSM 文件构建过程不一样的是, Series Block 在构建的同时需要记录下 SeriesKey 与该 Key 在文件中偏移量的对应关系, 即 < SeriesKey, SeriesKeyOffset>, 这一点至关重要
3. 将 < tagKey, <tagValue, List<SeriesKey>>结构中所有的 SeriesKey 由第二步 < SeriesKey, SeriesKeyOffset >中的 SeriesKeyOffset 代替形成新的结构:<tagKey, <tagValue, List<SeriesKeyOffset>>为什么要这么处理? 还记得上文中提到的 SeriesID 与 SeriesKey 的映射关系么, 如果还记得, 你一定会恍然大悟, 新结构其实就是 < tagKey, <tagValue, List<SeriesKeyID>>>
4. 在新结构 < tagKey, <tagValue, List<SeriesKeyId>>>的基础上首先持久化 tagValue, 将同一个 tagKey 下的所有 tagValue 持久化在一起并生成对应 Hash Index 写入文件, 接着持久话写下一个 tagKey 的的所有 tagValue
5. 所有 tagValue 都持久话完成之后再以此持久化所有的 tagKey, 形成 Tag Block 最后持久化 measurement 形成 Measurement Block
使用倒排索引加速维度条件过滤查询
上文提到 TSI 体系也是 LSM 结构, 所以倒排索引文件会不止一个, 这些文件会根据一定规则触发 compaction 形成一些大文件如果用户想根据某个表的部分维度查询某个时间段的所有时序数据的话(where tagk1=tagv1 from measurement1), 是首先需要到所有 TSI 文件中查找的, 为了方便起见, 这里假设只有一个 TSI 文件:
1. 根据 measurement1 在 Measument Block 进行过滤, 可以直接定位到该 measurement1 对应的所有维度值所在的文件区域
2. 加载出该 measurement1 对应 tag key 区域的 Hash Index, 使用 tagk1 进行 hash 可以直接定位到该 tagk1 对应的 tag value 的存储区域
3. 加载出 tagk1 对应 tag value 区域的 Hash Index, 使用 tagv1 进行 hash 可以直接定位到该 tagv1 对应的所有 SeriesID
4. SeriesID 就是对应 SeriesKey 在索引文件中的 offset, 直接根据 SeriesID 可以加载出对应的 SeriesKey
5. 根据 SeriesKeyfieldKey 以及时间范围在 TSM 文件中查找对应的满足查询条件的时间序列, 具体见上篇文章时序数据库技术体系 InfluxDB 存储引擎 TSM
文章总结
InfluxDB 的倒排索引是一个很有代表性的实现方案, 方案中文件格式定义 Hash Index 以及 B + 树索引的使用全局编码的实现都很有借鉴意义但是, Disk-Based Index 倒排索引相比其他系统来说还是有很多不同的:
1. Disk-Based Index 是一个完整的 LSM 结构, LSM 系统需要做的事情它都需要实现, 比如 flushcompaction 等因此可以把它看作一个独立的系统, 与原数据没有任何耦合
2. Disk-Based Index 仅仅实现了 Tag 到 SeriesKey 的映射, 而没有实现 Tag 到 SeriesKey+FieldKey+Timestamp 映射这能保证 InfluxDB 的倒排文件比较小, 可以有效利用缓存, 否则倒排索引文件将会变的非常之大而且会引入索引数据失效过期的问题, 比如某些很久以前的时序过期了, 索引对应的数据集就需要相应的调整
参考文献
- https://github.com/influxdata/influxdb/blob/master/tsdb/index/tsi1/doc.go?spm=5176.100239.blogcont158312.24.NUvEu3&file=doc.go
- https://yq.aliyun.com/articles/158312?spm=5176.100239.blogrightarea106382.21.PmSguT
- http://blog.fatedier.com/2016/08/15/detailed-in-influxdb-tsm-storage-engine-two/
来源: http://hbasefly.com/2018/02/09/timeseries-database-5/