时序数据库

即时间序列数据库，相信大家都知道MySQL之列的关系型数据库，也了解redis等nosql数据库，可是时间序列数据库，你了解多少呢？

这类时间序列数据库最多，使用也最广泛。一般人们谈论时间序列数据库的时候指代的就是这一类存储。按照底层技术不同可以划分为三类。

直接基于文件的简单存储：RRD Tool，Graphite Whisper。这类工具附属于监控告警工具，底层没有一个正规的数据库引擎。只是简单的有一个二进制的文件结构。

基于K/V数据库构建：opentsdb（基于hbase），blueflood，kairosDB（基于cassandra），influxdb，prometheus（基于leveldb）

基于关系型数据库构建：mysql，postgresql 都可以用来保存时间序列数据

另外一类数据库其表结构是：

[timestamp] [d1] [d2] .. [dn] [v1] [v2] .. [vn]

其优化的查询方式不限于查询原始数据，而是可以组合查询条件并且做聚合计算，比如：

SELECT d2, sum(v1) / sum(v2) FROM metric WHERE d1 =
 “A” AND timestamp >= B AND timestamp < C GROUP BY d2

我们希望时间序列数据库不仅仅可以提供原始数据的查询，而且要支持对原始数据的聚合能力。这种聚合可以是在入库阶段完成的，所谓物化视图。也可以是在查询阶段完成，所谓实时聚合。根据实际情况，可以在这两种方式中进行取舍。

想要在在查询阶段做数据的聚合和转换，需要能够支持以下三点。

• 用索引检索出行号：能够从上亿条数据中快速过滤出几百万的数据。
• 从主存储按行号加载：能够快速加载这过滤出的几百万条数据到内存里。
• 分布式计算：能够把这些数据按照GROUP BY 和 SELECT 的要求计算出最终的结果集。

要想尽可能快的完成整个查询过程，需要在三个环节上都有绝招。传统上说，这三个步骤是三个不同的技术领域。

• 检索：这是搜索引擎最擅长的领域。代表产品是Lucene。其核心技术是基于高效率数据结构和算法的倒排索引。
• 加载：这是分析型数据库最擅长的领域。代表产品是C-store和Monetdb。其核心技术是按列组织的磁盘存储结构。
• 分布式计算：这是大数据计算引擎最擅长的领域。代表产品是Hadoop和spark。其核心技术是sharding 和 map/reduce等等。

前面提到的时间序列库（比如opentsdb）有不少从功能上来说是没有问题。它们都支持过滤，也支持过滤之后的聚合计算。在数据量小的时候勉强是可用的。但是如果要实时从十亿条里取百万记录出来，再做聚合运算，对于这样的数据量可能就勉为其难了。满足海量数据实时聚合要求的数据库不多，比较常见的有这么几种：

• 基于Lucene构建的“搜索引擎”：Elasticsearch, Crate.io（虽然是基于Elasticsearch，但是聚合逻辑是自己实现的），Solr；
• 列式存储数据库：Vertica（C-store的后裔）Actian（Monetdb的后裔）等；
• Druid.io。

其中Elasticsearch是目前市场上比较很少有的，能够在检索加载和分布式计算三个方面都做得一流的数据库。而且是开源并且免费的。它使用了很多技术来达到飞一般的速度。这些主要的优化措施可以列举如下。

• Lucene的inverted index可以比mysql的b-tree检索更快。
• 在 Mysql中给两个字段独立建立的索引无法联合起来使用，必须对联合查询的场景建立复合索引。而lucene可以任何AND或者OR组合使用索引进行检索。
• Elasticsearch支持nested document，可以把一批数据点嵌套存储为一个document block，减少需要索引的文档数。
• Opentsdb不支持二级索引，只有一个基于hbase rowkey的主索引，可以按行的排序顺序scan。这使得Opentsdb的tag实现从检索效率上来说很慢。
• Mysql 如果经过索引过滤之后仍然要加载很多行的话，出于效率考虑query planner经常会选择进行全表扫描。所以Mysql的存储时间序列的最佳实践是不使用二级索引，只使用clustered index扫描主表。类似于Opentsdb。
• Lucene 从 4.0 开始支持 DocValues，极大降低了内存的占用，减少了磁盘上的尺寸并且提高了加载数据到内存计算的吞吐能力。
• Lucene支持分segment，Elasticsearch支持分index。Elasticsearch可以把分开的数据当成一张表来查询和聚合。相比之下Mysql如果自己做分库分表的时候，联合查询不方便。
• Elasticsearch 从1.0开始支持aggregation，基本上有了普通SQL的聚合能力。从 2.0 开始支持 pipeline aggregation，可以支持类似SQL sub query的嵌套聚合的能力。这种聚合能力相比Crate.io，Solr等同门师兄弟要强大得多。

如何快速检索？

Elasticsearch是通过Lucene的倒排索引技术实现比关系型数据库更快的过滤。特别是它对多条件的过滤支持非常好，比如年龄在18和30之间，性别为女性这样的组合查询。倒排索引很多地方都有介绍，但是其比关系型数据库的b-tree索引快在哪里？到底为什么快呢？

笼统的来说，b-tree索引是为写入优化的索引结构。当我们不需要支持快速的更新的时候，可以用预先排序等方式换取更小的存储空间，更快的检索速度等好处，其代价就是更新慢。要进一步深入的化，还是要看一下Lucene的倒排索引是怎么构成的。

这里有好几个概念。我们来看一个实际的例子，假设有如下的数据：

这里每一行是一个document。每个document都有一个docid。那么给这些document建立的倒排索引就是：

年龄:

性别:

可以看到，倒排索引是per field的，一个字段由一个自己的倒排索引。18,20这些叫做 term，而[1,3]就是posting list。Posting list就是一个int的数组，存储了所有符合某个term的文档id。那么什么是term dictionary 和 term index？

假设我们有很多个term，比如：

Carla,Sara,Elin,Ada,Patty,Kate,Selena

如果按照这样的顺序排列，找出某个特定的term一定很慢，因为term没有排序，需要全部过滤一遍才能找出特定的term。排序之后就变成了：

Ada,Carla,Elin,Kate,Patty,Sara,Selena

这样我们可以用二分查找的方式，比全遍历更快地找出目标的term。这个就是 term dictionary。有了term dictionary之后，可以用 logN 次磁盘查找得到目标。但是磁盘的随机读操作仍然是非常昂贵的（一次random access大概需要10ms的时间）。所以尽量少的读磁盘，有必要把一些数据缓存到内存里。但是整个term dictionary本身又太大了，无法完整地放到内存里。于是就有了term index。term index有点像一本字典的大的章节表。比如：

A开头的term ……………. Xxx页

C开头的term ……………. Xxx页

E开头的term ……………. Xxx页

如果所有的term都是英文字符的话，可能这个term index就真的是26个英文字符表构成的了。但是实际的情况是，term未必都是英文字符，term可以是任意的byte数组。而且26个英文字符也未必是每一个字符都有均等的term，比如x字符开头的term可能一个都没有，而s开头的term又特别多。实际的term index是一棵trie 树：

例子是一个包含 "A", "to", "tea", "ted", "ten", "i", "in", 和 "inn" 的 trie 树。这棵树不会包含所有的term，它包含的是term的一些前缀。通过term index可以快速地定位到term dictionary的某个offset，然后从这个位置再往后顺序查找。再加上一些压缩技术（搜索 Lucene Finite State Transducers） term index 的尺寸可以只有所有term的尺寸的几十分之一，使得用内存缓存整个term index变成可能。整体上来说就是这样的效果。

现在我们可以回答“为什么Elasticsearch/Lucene检索可以比mysql快了。Mysql只有term dictionary这一层，是以b-tree排序的方式存储在磁盘上的。检索一个term需要若干次的random access的磁盘操作。而Lucene在term dictionary的基础上添加了term index来加速检索，term index以树的形式缓存在内存中。从term index查到对应的term dictionary的block位置之后，再去磁盘上找term，大大减少了磁盘的random access次数。

额外值得一提的两点是：term index在内存中是以FST（finite state transducers）的形式保存的，其特点是非常节省内存。Term dictionary在磁盘上是以分block的方式保存的，一个block内部利用公共前缀压缩，比如都是Ab开头的单词就可以把Ab省去。这样term dictionary可以比b-tree更节约磁盘空间。

如何联合索引查询？

所以给定查询过滤条件 age=18 的过程就是先从term index找到18在term dictionary的大概位置，然后再从term dictionary里精确地找到18这个term，然后得到一个posting list或者一个指向posting list位置的指针。然后再查询 gender=女 的过程也是类似的。最后得出 age=18 AND gender=女 就是把两个 posting list 做一个“与”的合并。

这个理论上的“与”合并的操作可不容易。对于mysql来说，如果你给age和gender两个字段都建立了索引，查询的时候只会选择其中最selective的来用，然后另外一个条件是在遍历行的过程中在内存中计算之后过滤掉。那么要如何才能联合使用两个索引呢？有两种办法：

• 使用skip list数据结构。同时遍历gender和age的posting list，互相skip；
• 使用bitset数据结构，对gender和age两个filter分别求出bitset，对两个bitset做AN操作。

PostgreSQL 从 8.4 版本开始支持通过bitmap联合使用两个索引，就是利用了bitset数据结构来做到的。当然一些商业的关系型数据库也支持类似的联合索引的功能。Elasticsearch支持以上两种的联合索引方式，如果查询的filter缓存到了内存中（以bitset的形式），那么合并就是两个bitset的AND。如果查询的filter没有缓存，那么就用skip list的方式去遍历两个on disk的posting list。

利用 Skip List 合并:

以上是三个posting list。我们现在需要把它们用AND的关系合并，得出posting list的交集。首先选择最短的posting list，然后从小到大遍历。遍历的过程可以跳过一些元素，比如我们遍历到绿色的13的时候，就可以跳过蓝色的3了，因为3比13要小。

整个过程如下：

Next -> 2
Advance(2) -> 13
Advance(13) -> 13
Already on 13
Advance(13) -> 13 MATCH!!!
Next -> 17
Advance(17) -> 22
Advance(22) -> 98
Advance(98) -> 98
Advance(98) -> 98 MATCH!!!

最后得出的交集是[13,98]，所需的时间比完整遍历三个posting list要快得多。但是前提是每个list需要指出Advance这个操作，快速移动指向的位置。什么样的list可以这样Advance往前做蛙跳？skip list：

从概念上来说，对于一个很长的posting list，比如：

[1,3,13,101,105,108,255,256,257]

我们可以把这个list分成三个block：

[1,3,13] [101,105,108] [255,256,257]

然后可以构建出skip list的第二层：

[1,101,255]

1,101,255分别指向自己对应的block。这样就可以很快地跨block的移动指向位置了。

Lucene自然会对这个block再次进行压缩。其压缩方式叫做Frame Of Reference编码。示例如下：

考虑到频繁出现的term（所谓low cardinality的值），比如gender里的男或者女。如果有1百万个文档，那么性别为男的posting list里就会有50万个int值。用Frame of Reference编码进行压缩可以极大减少磁盘占用。这个优化对于减少索引尺寸有非常重要的意义。当然mysql b-tree里也有一个类似的posting list的东西，是未经过这样压缩的。

因为这个Frame of Reference的编码是有解压缩成本的。利用skip list，除了跳过了遍历的成本，也跳过了解压缩这些压缩过的block的过程，从而节省了cpu。

利用bitset合并

Bitset是一种很直观的数据结构，对应posting list如：

[1,3,4,7,10]

对应的bitset就是：

[1,0,1,1,0,0,1,0,0,1]

每个文档按照文档id排序对应其中的一个bit。Bitset自身就有压缩的特点，其用一个byte就可以代表8个文档。所以100万个文档只需要12.5万个byte。但是考虑到文档可能有数十亿之多，在内存里保存bitset仍然是很奢侈的事情。而且对于个每一个filter都要消耗一个bitset，比如age=18缓存起来的话是一个bitset，18<=age<25是另外一个filter缓存起来也要一个bitset。

所以秘诀就在于需要有一个数据结构：

• 可以很压缩地保存上亿个bit代表对应的文档是否匹配filter；
• 这个压缩的bitset仍然可以很快地进行AND和 OR的逻辑操作。

Lucene使用的这个数据结构叫做 Roaring Bitmap。

其压缩的思路其实很简单。与其保存100个0，占用100个bit。还不如保存0一次，然后声明这个0重复了100遍。

这两种合并使用索引的方式都有其用途。Elasticsearch对其性能有详细的对比（https://www.elastic.co/blog/frame-of-reference-and-roaring-bitmaps）。简单的结论是：因为Frame of Reference编码是如此高效，对于简单的相等条件的过滤缓存成纯内存的bitset还不如需要访问磁盘的skip list的方式要快。

如何减少文档数？

一种常见的压缩存储时间序列的方式是把多个数据点合并成一行。Opentsdb支持海量数据的一个绝招就是定期把很多行数据合并成一行，这个过程叫compaction。类似的vivdcortext使用mysql存储的时候，也把一分钟的很多数据点合并存储到mysql的一行里以减少行数。

这个过程可以示例如下：

合并之后就变成了：

可以看到，行变成了列了。每一列可以代表这一分钟内一秒的数据。

Elasticsearch有一个功能可以实现类似的优化效果，那就是Nested Document。我们可以把一段时间的很多个数据点打包存储到一个父文档里，变成其嵌套的子文档。示例如下：

{timestamp:12:05:01, idc:sz, value1:10,value2:11}
{timestamp:12:05:02, idc:sz, value1:9,value2:9}
{timestamp:12:05:02, idc:sz, value1:18,value:17}

可以打包成：

{
max_timestamp:12:05:02, min_timestamp: 1205:01, idc:sz,
records: [
 {timestamp:12:05:01, value1:10,value2:11}
{timestamp:12:05:02, value1:9,value2:9}
{timestamp:12:05:02, value1:18,value:17}
]
}

这样可以把数据点公共的维度字段上移到父文档里，而不用在每个子文档里重复存储，从而减少索引的尺寸。

在存储的时候，无论父文档还是子文档，对于Lucene来说都是文档，都会有文档Id。但是对于嵌套文档来说，可以保存起子文档和父文档的文档id是连续的，而且父文档总是最后一个。有这样一个排序性作为保障，那么有一个所有父文档的posting list就可以跟踪所有的父子关系。也可以很容易地在父子文档id之间做转换。把父子关系也理解为一个filter，那么查询时检索的时候不过是又AND了另外一个filter而已。前面我们已经看到了Elasticsearch可以非常高效地处理多filter的情况，充分利用底层的索引。

使用了嵌套文档之后，对于term的posting list只需要保存父文档的doc id就可以了，可以比保存所有的数据点的doc id要少很多。如果我们可以在一个父文档里塞入50个嵌套文档，那么posting list可以变成之前的1/50。

如何利用索引和主存储，是一种两难的选择。

• 选择不使用索引，只使用主存储：除非查询的字段就是主存储的排序字段，否则就需要顺序扫描整个主存储。
• 选择使用索引，然后用找到的row id去主存储加载数据：这样会导致很多碎片化的随机读操作。

没有所谓完美的解决方案。MySQL支持索引，一般索引检索出来的行数也就是在1~100条之间。如果索引检索出来很多行，很有可能MySQL会选择不使用索引而直接扫描主存储，这就是因为用row id去主存储里读取行的内容是碎片化的随机读操作，这在普通磁盘上很慢。

Opentsdb是另外一个极端，它完全没有索引，只有主存储。使用Opentsdb可以按照主存储的排序顺序快速地扫描很多条记录。但是访问的不是按主存储的排序顺序仍然要面对随机读的问题。

Elasticsearch/Lucene的解决办法是让主存储的随机读操作变得很快，从而可以充分利用索引，而不用惧怕从主存储里随机读加载几百万行带来的代价。

Opentsdb 的弱点

Opentsdb没有索引，主存储是Hbase。所有的数据点按照时间顺序排列存储在Hbase中。Hbase是一种支持排序的存储引擎，其排序的方式是根据每个row的rowkey（就是关系数据库里的主键的概念）。MySQL存储时间序列的最佳实践是利用MySQL的Innodb的clustered index特性，使用它去模仿类似Hbase按rowkey排序的效果。所以Opentsdb的弱点也基本适用于MySQL。Opentsdb的rowkey的设计大致如下：

[metric_name][timestamp][tags]

举例而言：

Proc.load_avg.1m 12:05:00 ip=10.0.0.1
Proc.load_avg.1m 12:05:00 ip=10.0.0.2
Proc.load_avg.1m 12:05:01 ip=10.0.0.1
Proc.load_avg.1m 12:05:01 ip=10.0.0.2
Proc.load_avg.5m 12:05:00 ip=10.0.0.1
Proc.load_avg:5m 12:05:00 ip=10.0.0.2

也就是行是先按照metric_name排序，再按照timestamp排序，再按照tags来排序。

对于这样的rowkey设计，获取一个metric在一个时间范围内的所有数据是很快的，比如Proc.load_avg.1m在12:05到12:10之间的所有数据。先找到Proc.load_avg.1m 12:05:00的行号，然后按顺序扫描就可以了。

但是以下两种情况就麻烦了。

• 获取12:05 到 12:10 所有 Proc.load_avg.* 的数据，如果预先知道所有的metric name包括Proc.load_avg.1m，Proc.load_avg.5m，Proc.load_avg.15m。这样会导致很多的随机读。如果不预先知道所有的metric name，就无法知道Proc.load_avg.*代表了什么。
• 获取指定ip的数据。因为ip是做为tags保存的。即便是访问一个ip的数据，也要把所有其他的ip数据读取出来再过滤掉。如果ip总数有十多万个，那么查询的效率也会非常低。为了让这样的查询变得更快，需要把ip编码到metric_name里去。比如ip.10.0.0.1.Proc.load_avg.1m 这样。

所以结论是，不用索引是不行的。如果希望支持任意条件的组合查询，只有主存储的排序是无法对所有查询条件进行优化的。但是如果查询条件是固定的一种，那么可以像Opentsdb这样只有一个主存储，做针对性的优化。

DocValues为什么快？

DocValues是一种按列组织的存储格式，这种存储方式降低了随机读的成本。传统的按行存储是这样的：

1和2代表的是docid。颜色代表的是不同的字段。

改成按列存储是这样的：

按列存储的话会把一个文件分成多个文件，每个列一个。对于每个文件，都是按照docid排序的。这样一来，只要知道docid，就可以计算出这个docid在这个文件里的偏移量。也就是对于每个docid需要一次随机读操作。

那么这种排列是如何让随机读更快的呢？秘密在于Lucene底层读取文件的方式是基于memory mApped byte buffer的，也就是mmap。这种文件访问的方式是由操作系统去缓存这个文件到内存里。这样在内存足够的情况下，访问文件就相当于访问内存。那么随机读操作也就不再是磁盘操作了，而是对内存的随机读。

那么为什么按行存储不能用mmap的方式呢？因为按行存储的方式一个文件里包含了很多列的数据，这个文件尺寸往往很大，超过了操作系统的文件缓存的大小。而按列存储的方式把不同列分成了很多文件，可以只缓存用到的那些列，而不让很少使用的列数据浪费内存。

按列存储之后，一个列的数据和前面的posting list就差不多了。很多应用在posting list上的压缩技术也可以应用到DocValues上。这不但减少了文件尺寸，而且提高数据加载的速度。因为我们知道从磁盘到内存的带宽是很小的，普通磁盘也就每秒100MB的读速度。利用压缩，我们可以把数据以压缩的方式读取出来，然后在内存里再进行解压，从而获得比读取原始数据更高的效率。

如果内存不够是不是会使得随机读的速度变慢？肯定会的。但是mmap是操作系统实现的API，其内部有预读取机制。如果读取offset为100的文件位置，默认会把后面16k的文件内容都预读取出来都缓存在内存里。因为DocValues是只读，而且顺序排序存储的。相比b-tree等存储结构，在磁盘上没有空洞和碎片。而随机读的时候也是按照DocId排序的。所以如果读取的DocId是紧密相连的，实际上也相当于把随机读变成了顺序读了。Random_read(100), Random_read(101), Random_read(102)就相当于Scan(100~102)了。

分布式计算

分布式聚合如何做得快？Elasticsearch/Lucene从最底层就支持数据分片，查询的时候可以自动把不同分片的查询结果合并起来。Elasticsearch的document都有一个uid，默认策略是按照uid 的 hash把文档进行分片。

一个Elasticsearch Index相当于一个MySQL里的表，不同Index的数据是物理上隔离开来的。Elasticsearch的Index会分成多个Shard存储，一部分Shard是Replica备份。一个Shard是一份本地的存储（一个本地磁盘上的目录），也就是一个Lucene的Index。不同的Shard可能会被分配到不同的主机节点上。一个Lucene Index会存储很多的doc，为了好管理，Lucene把Index再拆成了Segment存储（子目录）。Segment内的doc数量上限是1的31次方，这样doc id就只需要一个int就可以存储。Segment对应了一些列文件存储索引（倒排表等）和主存储（DocValues等），这些文件内部又分为小的Block进行压缩。

时间序列数据一般按照日期分成多个Elasticsearch Index来存储，比如logstash-2014.08.02。查询的时候可以指定多个Elasticsearch Index作为查找的范围，也可以用logstash-*做模糊匹配。

美妙之处在于，虽然数据被拆得七零八落的，在查询聚合的时候甚至需要分为两个阶段完成。但是对于最终用户来说，使用起来就好像是一个数据库表一样。所有的合并查询的细节都是隐藏起来的。

对于聚合查询，其处理是分两阶段完成的：

• Shard本地的Lucene Index并行计算出局部的聚合结果；
• 收到所有的Shard的局部聚合结果，聚合出最终的聚合结果。

这种两阶段聚合的架构使得每个shard不用把原数据返回，而只用返回数据量小得多的聚合结果。相比Opentsdb这样的数据库设计更合理。Opentsdb其聚合只在最终节点处完成，所有的分片数据要汇聚到一个地方进行计算，这样带来大量的网络带宽消耗。所以Influxdb等更新的时间序列数据库选择把分布式计算模块和存储引擎进行同机部署，以减少网络带宽的影响。

除此之外Elasticsearch还有另外一个减少聚合过程中网络传输量的优化，那就是Hyperloglog算法。在计算unique visitor（uv）这样的场景下，经常需要按用户id去重之后统计人数。最简单的实现是用一个hashset保存这些用户id。但是用set保存所有的用户id做去重需要消耗大量的内存，同时分布式聚合的时候也要消耗大量的网络带宽。Hyperloglog算法以一定的误差做为代价，可以用很小的数据量保存这个set，从而减少网络传输消耗。

为什么时间序列需要更复杂的聚合？

关系型数据库支持一些很复杂的聚合查询逻辑，比如：

• Join两张表；
• Group by之后用Having再对聚合结果进行过滤；
• 用子查询对聚合结果进行二次聚合。

在使用时间序列数据库的时候，我们经常会怀念这些SQL的查询能力。在时间序列里有一个特别常见的需求就是降频和降维。举例如下：

12:05:05 湖南 81
12:05:07 江西 30
12:05:11 湖南 80
12:05:12 江西 32
12:05:16 湖南 80
12:05:16 江西 30

按1分钟频率进行max的降频操作得出的结果是：

12:05 湖南 81
12:05 江西 32

这种按max进行降频的最常见的场景是采样点的归一化。不同的采集器采样的时间点是不同的，为了避免漏点也会加大采样率。这样就可能导致一分钟内采样多次，而且采样点的时间都不对齐。在查询的时候按max进行降频可以得出一个统一时间点的数据。

按sum进行降维的结果是：

12:05 113

经常我们需要舍弃掉某些维度进行一个加和的统计。这个统计需要在时间点对齐之后再进行计算。这就导致一个查询需要做两次，上面的例子里：

• 先按1分钟，用max做降频；
• 再去掉省份维度，用sum做降维。

如果仅仅能做一次聚合，要么用sum做聚合，要么用max做聚合。无法满足业务逻辑的需求。为了避免在一个查询里做两次聚合，大部分的时间序列数据库都要求数据在入库的时候已经是整点整分的。这就要求数据不能直接从采集点直接入库，而要经过一个实时计算管道进行处理。如果能够在查询的时候同时完成降频和降维，那就可以带来一些使用上的便利。

这个功能看似简单，其实非常难以实现。很多所谓的支持大数据的数据库都只支持简单的一次聚合操作。Elasticsearch 将要发布的 2.0 版本的最重量级的新特性是Pipeline Aggregation，它支持数据在聚合之后再做聚合。类似SQL的子查询和Having等功能都将被支持。