net网站开发的步骤txt,广州商城型网站建设,做网站编写代码,wordpress 投票网站在时序数据库概述一文中#xff0c;笔者提到时序数据库的基础技术栈主要包括高吞吐写入实现、数据分级存储#xff5c;TTL、数据高压缩率、多维度查询能力以及高效聚合能力等#xff0c;上文《时序数据库技术体系 – InfluxDB存储引擎TSM》基于InfluxDB存储引擎TSM介绍了时序…在时序数据库概述一文中笔者提到时序数据库的基础技术栈主要包括高吞吐写入实现、数据分级存储TTL、数据高压缩率、多维度查询能力以及高效聚合能力等上文《时序数据库技术体系 – InfluxDB存储引擎TSM》基于InfluxDB存储引擎TSM介绍了时序数据库的高性能写入能力以及基于列式存储的数据高压缩率实现。接下来两篇文章分别基于InfluxDB系统的倒排索引实现以及Druid系统的Bitmap索引实现介绍时序数据库的多维度查询实现原理。
InfluxDB系统TSM存储引擎个人认为有两个最核心的工作模块其一是TSM针对时序数据在内存以及文件格式上做了针对性的优化优雅地实现了时序数据的高效率写入以及高压缩率存储同时文件级别的B树索引可以有效提高时序数据根据SeriesKey查询时间序列的性能其二是InfluxDB系统还实现了内存以及文件级别的倒排索引有效实现了根据给定维度fieldKey查询对应SeriesKey的功能这样再根据SeriesKey、fieldKey和时间间隔就可以在文件中查找到对应的时序数据集合。
上文笔者提到SeriesKey等于measurementtags(datasources)其中measurement表示一张时序数据表tags多组维度值唯一确定了数据源。用户的查询通常有以下两种查询场景以广告时序数据平台来说
1. 查看最近一小时某一个广告数据源总的点击量典型的根据SereisKey、fieldKey(点击量)和时间范围查找时序数据再做聚合sum。
2. 统计最近一天网易考拉指定广告商发布在网易云音乐指定广告平台的所有广告总的点击量。这种统计查询并没有给出具体的广告SeriesKey仅指定了两个广告维度广告商和广告平台以及查询指标 – 点击量。这种查询就首先需要使用倒排索引根据measurement以及部分维度组合广告商网易考拉广告平台网易云音乐找到所有对应的广告源假如网易考拉在网易云音乐上发布了100个广告就需要查找到这100个广告点击量对应的SeriesKey再分别针对所有SeriesKey在最近一天这个时间范围查找点击量数据最后做sum聚合。
如何根据measurement以及部分维度组合查找到所有满足条件的SeriesKeyInfluxDB给出了倒排索引的实现称之为TimeSeries Index意为TimeSeries的索引简称TSI。InfluxDB TSI在1.3版本之前仅支持Memory-Based Index实现1.3之后又实现了Disk-Based Index实现。
Memory-Based Index
Memory-Based Index方案将所有TimeSeries索引加载到内存提供服务核心数据结构主要有 其中seriesByTagKeyValue是一个双重map即maptagkey, maptagvalue, ListSeriesID。以上文中广告商网易考拉为例来解释
tagkey为广告商广告商可以有网易考拉还可能有网易严选所以一个广告商这个tagkey对应一个map。map的key是tagvaluevalue是SeriesID集合。示例中tagvalue为网易考拉映射的值为SeriesID集合。
因此上文中第二种查询场景就可以通过下述步骤完成
1. 通过seriesByTagKeyValue这个内存结构以及给定的维度值广告商网易考拉找到所有包含该维度值的SeriesID集合
2. 同样的方法通过seriesByTagKeyValue以及给定的维度值广告平台网易云音乐找到包含该维度值的SeriesID集合
3. 两个SeriesID集合再做交集就是同时满足广告商网易考拉广告平台网易云音乐的所有SeriesID
4. 再在SeriesByID – mapSeriesID, SeriesKey中根据SeriesID集合映射查找到SeriesKey集合
5. 最后根据SeriesKey集合以及时间范围找到所有满足条件的时序数据集合
这里为什么使用SeriesID作为跳板找到SeriesKey而不是直接映射得到SeriesKey因为seriesByTagKeyValue这个结构中索引到的SeriesKey会有大量冗余一个SeriesKey包含多少Tag组合就会有多少份冗余。举个简单的例子
假如现在有3个Tag组合形成一个seriesKeymeasurementmm,tagk1tagv1,tagk2tagv2,tagk3tagv3。那么构造形成的双重Map结构seriesByTagKeyValue就会为
tagk1, tagv1, seriesKey
tagk2, tagv2, seriesKey
tagk3, tagv3, seriesKey
此时假如用户想找tagk1tagv1这个维度条件下的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 Index。Disk-Based Index方案会将索引持久化到磁盘在使用时再加载到内存。InfluxDB官网对Disk-Based Index实现方案做了如下说明 不难看出InfluxDB中倒排索引和时序数据使用了相同的存储机制 – LSM引擎。因此倒排索引也是先写入内存以及WAL内存中达到一定阈值或者满足某些条件之后会执行持久化操作将内存中的索引写入文件。当磁盘上文件数超过一定阈值会执行Compaction操作进行合并。实际实现中时序数据点写入系统后会抽出Measurement、Tags并拼成SeriesKey在系统中查看该SeriesKey是否已经存在如果存在就忽略否则写入内存中相应结构参考log_file文件中变量InMemory Index。接着内存中的数据会flush到文件参考log_file文件中CompactTo方法接下来笔者将会重点介绍TSI文件格式如下图所示 TSI文件主要由4个部分组成Index File TrailerMeasurement BlockTag Block以及Series Block。
1. File Trailer主要记录Measurement Block、Tag Block以及Series Block在TSI文件中的偏移量以及数据大小。
2. Measurement Block存储数据库中表的信息通常来说Measurement不会太多一个Block也就够了。
3. Tag Block实际上是seriesByTagKeyValue这个双重map – maptagkey, maptagvalue, ListSeriesID在文件中的实际存储。
4. Series Block存储了数据库中所有SeriesKey。
Measurement Block Measurement Block存储数据库中所有时序数据表表名信息Block主要由三部分组成Block Trailer Section、Hash Index Section以及Measurement Entry Section。
1. Block Trailer Section记录了Hash Index Section以及Measurement Data Section在文件中的偏移量以及数据大小是Measurement Block读取解析的入口。
2. Hash Index是一个Hash索引。实现机制很简单就是一个Map结构 – mapmeasurement, 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下的Tags。Tag Block由三部分组成Block Trailer、Tag Key Section以及Tag Value Section
1. Block Trailer存储Tag Key Hash Index的offset以及sizeTagKey Section的offset以及sizeTagValue Section的offset以及size。通过解析Trailer可以快速找到Block中各个部分的解析入口。
2. Tag Key Section存储指定Measurement下所有维度名信息比如广告时序数据有publisher、advertiser、gender、country等维度。每个Tag Key由多个字段组成是一个复合结构如下图所示 其中key字段表示维度名TagValue相关字段TagValue.offset、TagValue.size…表示该维度下所有维度值在文件中的存储区域。
3. Tag Value Section存储某个维度下的所有维度值。比如广告时序数据中advertiser这个维度可能有多个值比如google.com、baidu.com、163music.com等等一系列值所有这些值会集中存储在一起这个区域就是advertiser维度对应的Tag Value Section。同理其他维度诸如publisher、gender、country等都会有对应的Tag Value Section。Tag Value Section中每个Tag Value也是一个复合结构如下图所示 其中value字段和series.data两个字段是需要重点关注的两个字段。前者表示具体的维度值后者表示这个维度值对应的一系列SeriesKey。注意存储的时候并没有直接存储SeriesKey而是存储SeriesID。上文重点说明了存储SeriesID而不直接存储SeriesKey的原因。
关于Tag Block笔者在思考的时候一直在思考两个问题
1. Tag Block中每个数据Section都有对应的Hash Index用来加速查找。但是有没有注意到Hash Index只能实现等值查找加速但是不能实现范围查找比如大于、小于条件查找。假如现在用户想要根据维度advertiser163music.com查找对应的所有seriesKey可以很容易
1在Tag Key Section的Hash Index一下子就找到对应Tag Keyadvertiser在文件中的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
但是如果用户想查询advertiser163music.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 Trailer、Bloom Filter Section、Series Index Chunk以及一系列SeriesKeyChunk。
1. Block Trailer和其他Block Trailer一样主要存储该Block中其他Section在文件中的偏移量以及大小是读取解析Block的入口。
2. Bloom Filter Section和Hash Index基本一样的原理不过Bloom Filter只用来表征给定seriesKey是否已经在文件中存在。
3. Series Index ChunkB树索引由多个Index Entry组成每个Index Entry又由三个部分构成分别是Capacity、MinSeriesKey、HashIndex。如下图所示 其中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在文件中不存在需要将其写入内存。这里可以将内存中的结构理解为两个核心数据结构
1measurement, ListtagKey表示时序表与对应维度集合的映射
2seriesByTagKeyValue那样一个双重Map结构tagKey, tagValue, ListSeriesKey
倒排索引flush成文件
1. measurement, ListtagKey以及tagKey, tagValue, ListSeriesKey都需要经过排序处理排序的意义在于有序数据可以结合Hash Index实现范围查询另外Series Block中B树的构建也需要SeriesKey排序。
2. 在排序的基础上首先持久化tagKey, tagValue, ListSeriesKey结构中所有的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, ListSeriesKey结构中所有的SeriesKey由第二步SeriesKey, SeriesKeyOffset 中的SeriesKeyOffset代替。形成新的结构tagKey, tagValue, ListSeriesKeyOffset。为什么要这么处理还记得上文中提到的SeriesID与SeriesKey的映射关系么如果还记得你一定会恍然大悟新结构其实就是tagKey, tagValue, ListSeriesKeyID。
4. 在新结构tagKey, tagValue, ListSeriesKeyId的基础上首先持久化tagValue将同一个tagKey下的所有tagValue持久化在一起并生成对应Hash Index写入文件接着持久话写下一个tagKey的的所有tagValue。
5. 所有tagValue都持久话完成之后再以此持久化所有的tagKey形成Tag Block。最后持久化measurement形成Measurement Block。
使用倒排索引加速维度条件过滤查询
上文提到TSI体系也是LSM结构所以倒排索引文件会不止一个这些文件会根据一定规则触发compaction形成一些大文件。如果用户想根据某个表的部分维度查询某个时间段的所有时序数据的话where tagk1tagv1 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. 根据SeriesKey、fieldKey以及时间范围在TSM文件中查找对应的满足查询条件的时间序列具体见上篇文章《时序数据库技术体系 – InfluxDB存储引擎TSM》。
文章总结
InfluxDB的倒排索引是一个很有代表性的实现方案方案中文件格式定义、Hash Index以及B树索引的使用、全局编码的实现都很有借鉴意义。但是Disk-Based Index倒排索引相比其他系统来说还是有很多不同的
1. Disk-Based Index是一个完整的LSM结构LSM系统需要做的事情它都需要实现比如flush、compaction等。因此可以把它看作一个独立的系统与原数据没有任何耦合。
2. Disk-Based Index仅仅实现了Tag到SeriesKey的映射而没有实现Tag到SeriesKeyFieldKeyTimestamp映射。这能保证InfluxDB的倒排文件比较小可以有效利用缓存否则倒排索引文件将会变的非常之大。而且会引入索引数据失效过期的问题比如某些很久以前的时序过期了索引对应的数据集就需要相应的调整。 参考文献
https://github.com/influxdata/influxdb/blob/master/tsdb/index/tsi1/doc.go?spm5176.100239.blogcont158312.24.NUvEu3filedoc.go
https://yq.aliyun.com/articles/158312?spm5176.100239.blogrightarea106382.21.PmSguT
http://blog.fatedier.com/2016/08/15/detailed-in-influxdb-tsm-storage-engine-two/
