百度Noah平台的TSDB，是百度最大规模的时序数据库，它为Noah监控系统提供时序数据存储与查询服务，每天承接多达数万亿次的数据点写入请求，以及数十亿次的查询请求。作为监控系统的后端服务，在如此大规模的写入情况下，保证快速的查询响应非常重要，这对系统提出了巨大挑战。通过对用户日常查询行为进行分析，用户的查询需求与数据的时间轴有强关联，用户更加关心最近产生的数据。因此Noah的TSDB在架构上，利用百度BDRP（百度的Redis平台）构建缓存层，缓存最近几小时的数据，极大提升查询性能，有效降低查询平响。

同样Facebook为了提高其ODS TSDB读写性能，设计了基于内存的Gorilla时序数据库，用作ODS的write-through cache方案缓存数据。可以看出在缓存这层，我们都采用基于内存的方式做数据缓存。采用内存最大的优势是其数据读写速度远快于磁盘速度，然而缺点是需要占用较大的内存空间资源。为了有效节约内存空间，Gorilla设计了时序数据压缩算法对时序数据进行实时压缩。在Gorilla论文[1]中表明，利用其压缩算法，在Facebook的生产环境下平均压缩数据10倍。

我们在对缓存层数据存储设计的时候，结合Noah TSDB的具体情况，借鉴了Gorilla数据压缩算法对数据进行压缩，存储空间资源占用降低了70%，有效降低资源成本。因此本文简单和大家分享一下该压缩算法的基本原理，没准儿也能节约下不少钱呢。

基础介绍

典型的时序数据，是由Key-Value组成的二元组， Key中可能包含如Cluster、Tag、Metric、Timestamp等信息。为了便于理解，这里将时序数据简单理解为Key是时间戳（Timestamp），Value是在该时间戳时的具体数据值。

假设这是某CPU在不同时间的利用率：

以这份数据为例，在后续介绍中我们一边介绍算法，一边采用Gorilla的压缩方法对这个测试数据进行压缩，观察该算法压缩效果。

压缩思想

1基本原则

Gorilla压缩算法，其核心思想建立在时序数据场景下，相邻的时序数据相似度很大这一特点之上。基于这个基本的原则，尽量只保留数据差异的部分，去除相同的部分，来达到压缩数据的目的。

2数据结构

Gorilla将数据组织成一个个数据块(Block)，一个Block保存连续一段时间且经过压缩的时序数据。每次查询的时候会直接读取目标数据所属的Block，对Block解压后返回查询结果。Facebook经验表明，如果一个Block的时间跨度超过2小时，由于解压Block所消耗的资源增加，其压缩收益会逐渐降低，因此将单个Block的时间跨度设置为2小时。

每个Block的Header保存其起始时间戳(Timebase)，例如如果某时序数据产生时间点是2019/2/24 14:30，则以2小时为单位向上取整，该数据所属的Block的Timebase为2019/2/24 14:00，时间戳为1550944800如下图所示。然后以KV的形式依次保存属于该Block的时序数据。

接下来分别介绍对Key和Value的压缩方法。

时间戳压缩

时序数据的产生，大部分都有固定的产生时间间隔，如间隔10s、15s、60s等。即使由于各种因素造成时序数据产生有一定延迟或者提前，但是大部分数据的时间戳间隔都是在非常接近的范围内。因此对时间戳压缩的思想就是不需要存储完整的时间戳，只存储时间戳差值的差值（delta of delta）。具体以本文测试数据的时间戳Key为例介绍时间戳压缩算法。

压缩前

每个秒级的时间戳用Long型存储（8Bytes），本文测试数据中的3条数据时间戳共需要占用388 = 192(Bits)。T均为Unix 时间戳。

Gorilla压缩

对于每个Block：

1.Block的头部Header存储本Block的起始时间戳T-1，不做任何压缩。

2.第一个时间戳存储T0与T-1的差值(Delta)，占用14(Bits)。

3.对于本Block后面的时间戳Tn：

a.计算差值的差值：

b.存在Block中时间戳数据由 [标识位+D值] 组成，根据D的不同范围确定标识位的取值和保存D值所需占用的空间。如下表所示：

具体对于本例而言，采用上述对时间戳的压缩方式后结果如下所示：

利用上述的压缩编码方式对本文的测试数据编码后，其所属的Block内数据如下所示：

其中只填写了T的部分，V的部分由下文进行补充。经过压缩测试数据，总共占用64+14+9+1=88(Bits)，压缩率为88/192=45.8%。

由于本例的测试数据较少，Header空间占比较大，导致压缩收益与实际环境中收益有一定差距。在实际环境中，Header所占有的空间相对于整个Block来说比例较小，压缩收益会更大。根据Facebook线上数据统计，如下图所示，96%的时间戳都被压缩到1个Bit来存储，因此在生产环境将会带来不错的压缩收益（结合数据分布再回过头看编码方式，是不是有点Huffman编码的感觉）。

数据值压缩

对时间戳Key压缩后，接下来对Value进行压缩。与Key类似，通过对历史数据进行分析，发现大部分相邻时间的时序数据的Value值比较接近（可以理解为突增/突降的现象比较少）。而如果Value的值比较接近，则在浮点二进制表示的情况下，相邻数据的Value会有很多相同的位。整数型数据的相同位会更多。相同位比较多，意味着如果进行XOR运算的话会有很多位都为0。

为了便于说明，这里首先定义一个XOR运算后的结果由三部分组成：

Leading Zeros（LZ）: XOR后第一个非零位前面零的个数
Trailing Zeros（TZ）: XOR后最后一个非零位后面零的个数
Meaningful Bits（MB）: 中间有效位的个数

上图是Gorilla论文里给的示例，可以理解该数据为一系列相邻时序数据的Value。可以看出对相邻数据进行XOR运算后，MB、LZ和TZ非常相似。基于此，其压缩方式参考之前其他工作[2,3]已经提出的数据压缩方法，将当前值与前序值取XOR（异或）运算，保存XOR运算结果。具体方式如下：

压缩前

每个浮点类型数据Double型存储占用8Bytes，本文测试数据中的3条数据Value共需要占用388 = 192(Bits)。

Gorilla压缩

在同一个Block内，Value的压缩规则如下：

1.第一个Value的值V0不压缩。

2.对于本数据块后面的Value值Vn：

a.XOR运算结果：

b.对结果进行如下处理：

基于上述压缩编码规则，对本文测试数据的Value进行压缩后结果如下所示，压缩后总共占用64+1+1+14 = 80(Bits)，压缩率为80/256=31.2%。

此时该Block内的数据如下所示：

以上就是对于Value值的压缩方法。与Key的压缩一样，在线上环境数据量较多的情况下压缩效果会更好。根据Facebook线上数据统计，59.06%的value值都被压缩到1个位来存储。

总结

总的来说，利用上述的压缩方式，我们的测试数据由384Bits（Key+Value）变为168Bits，压缩率达到43%，具有不错的压缩效率。当然由于数据量的原因，在实际生产环境下压缩收益会更大。百度Noah的TSDB在应用上述压缩算法的实践中，基于我们的实际情况进行了一定的改造（后续序列文章会另行介绍），存储空间的资源占用减少超过70%，表明这个算法能真实有效对时序数据进行压缩。

另外一点，我们发现在做压缩的时候Gorilla对Key和Value分开进行了压缩处理。将Key和Value分开压缩的好处在于，可以根据Key、Value不同的数据类型、数据特点，选用更适合自己的压缩算法，从而提高压缩效率。在时序场景下，KV分别处理虽然不是一个新的思想，但是可以将该思想应用在多个地方。比如本文提到的Gorilla是将该思想应用在压缩方面，FAST2016年的WiscKey[4]利用KV分离思想优化LSM的IO放大问题。有兴趣的读者可以针对KV分离方法探索一下。

由于本人水平有限，若理解不到位或者大家有任何想法，欢迎指出交流。

作者介绍：
任杰，百度高级研发工程师，负责百度智能运维产品（Noah）的分布式时序数据存储设计研发工作，在大规模分布式存储、NoSQL数据库方面有大量实践经验。

本文转载自公众号AIOps智能运维（ID：AI_Ops）。

原文链接：

https://mp.weixin.qq.com/s/KKnOjvc5PthkRhNkTh6DZA

创作场景

百度时序数据库——存储的省钱之道