压缩算法

时序数据规模很大，且可能存在大量冗余，因而在时序数据库中经常使用压缩方法来节约存储空间和查询执行时的I/O代价，下面将讨论一些时序数据库中常见的压缩技术。

不同时序数据库的具体存储结构与压缩算法在设计上相差很大。以Open TSDB为代表的分布式时序数据库底层依托HBase集群存储，存在基本的时序数据模型，根据时序数据的基本特征对时序数据进行压缩存储。Open TSDB使用类字典压缩算法，通过将索引名称和每个序列名称的每个标签，通过进行编码来减少序列内存使用。然而依然存在很多无用的字段，无法有效的压缩，聚合能力比较弱。InfluxDB具有更丰富的数据类型，InfluxDB在整型数据采用整型编码，整数编码的压缩具体取决于原始数值的范围。时间戳为独立的数据类型，并且具有一定的规律可循，在InfluxDB中，针对时间戳数据先执行排序操作后使用delta算法进行编码，然后再根据编码结果采用不同的算法进行处理。有关 CnosDB 的压缩算法，下面的内容将帮您对其有更清楚的了解。

DELTA

主要用于时间戳，整型以及无符号整型。

原理

首先进行差分，即第一个数据不变，其他数据转化为与上一个数据的delta，再将所有数字进行zigzag处理，即将i64映射到u64，具体为0映射到0，负数映射到奇数，正数映射到偶数，例如[0，-1，1，-2]经过zigzag处理后变为[0，1，2，3]，并计算出最大公约数。之后判断一下如果所有的delta都相同，就直接使用游程编码，即只需要记录第一个值，delta和数据的数量。否则就将所有的delta值除以最大公约数（最大公约数也会编码进数据），然后使用simple8b进行编码。

simple8b是一种将多个整数打包到一个64位整数的压缩算法，前4位作为selector，用于指定剩余60位中储存的整数的个数和有效位长度，后60位用于储存多个整数。另外当delta的大小超过simple8b能编码的最大范围（超过1<<60 - 1，一般情况下不会出现）则不进行压缩，直接储存数组。

适用情况

在一些定时采集的数据，假设每5秒采集一次数据，时间戳的delta为5，通过游程编码仅仅通过三个数字就可以复原所有的时间戳，压缩比极高，而一些delta不能保证一致的场景，即在使用simple8b的情况下，更适用于范围较小的，浮动较小的数据。

在不指定压缩算法的情况下，我们默认为时间戳，整型和无符号整型使用这种压缩算法，压缩率与压缩效率都比较高。

GORILLA

主要用于浮点型。

原理

gorilla的原理与差分类似，区别在于差分是两个数据的差，gorilla则是异或。编码时第一个数据不进行处理，计算后一个的数据与前一个数据的异或，如果异或值为0，则与上一个数据重复，写一个补位用来表示重复，如果不为零，则计算异或值delta的前导零和后导零个数，如果个数相同，则只编码中间有效位，如果个数不同则前导零写5位，后导零写6位，然后再写中间有效位。

适用情况

与delta类型，同样比较适用于时序数据场景下，我们可能在不同地点采集数据，但同一地点采集的数据的地名相关信息大体上是一致的，在这种场景下，压缩率与压缩效率都比较高。

在不指定压缩算法的情况下，我们默认为浮点型指定这种压缩算法。

QUANTILE

主要用于时间戳，整型，无符号整型以及浮点数。

原理

quantile支持多种级别压缩，CnosDB 目前采用默认的压缩等级。

通过哈夫曼编码和偏移量描述每个数据，用哈夫曼码对应数据所在的范围[lower, upper]，偏移量指定该范围内的确切位置。对于每个块的压缩首先进行差分处理，用差分后的数据来代替现在的数据，然后将当前的数组大致以128为间隔分割成多个块，每个块确定一个范围与关联的元数据，同时计算每个块的最大公约数，根据情况使用最大公约数优化，以及合并一些相邻的块，再根据每个块在数据中的权重确定其哈夫曼编码，最后使用这些块对数据进行编码。

适用情况

相比较于delta算法与gorilla算法，由于同样使用了差分算法，在适用数据的选择上大致相同，由于quantile算法采用了更复杂的编码方式，导致压缩效率比较低，大约有5到10倍的差距，相对地，压缩率则稍优于delta与gorilla算法。

图片纵轴为压缩比，时间只比较相对值。

BITPACK

主要用于布尔类型。

原理

一个bool类型的数据的大小是一个字节，而对于bool所表示的信息，其实只需要1位就可以表示，这样我们可以将8个bool类型的数据组装成1个字节的数据。

适用情况

无论任何数据，都可以保证接近8倍的压缩比，在不指定压缩算法的情况下，我们默认为布尔类型指定这种压缩算法。

字符串压缩算法

目前支持的字符串压缩算法压缩比如下：

以及压缩时间和解压缩时间，单位为us

SNAPPY

snappy算法不旨在最大程度地压缩，也不旨在与任何其他压缩库兼容。相反，它的目标是非常高的压缩效率和合理的压缩率，所以在更加需要效率的情况下推荐使用snappy。

在不指定字符串压缩算法的情况下，我们默认指定这种压缩算法。

ZSTD

zstd支持多种压缩等级，CnosDB 目前采用默认的压缩等级。

Zstd 全称叫 Zstandard，是一个提供高压缩比的快速压缩算法，Zstd 采用了有限状态熵编码器。提供了非常强大的压缩速度/压缩率的折中方案。

GZIP/ZLIB

gzip与zlib比较相似，对于要压缩的文件，首先使用LZ77算法的一个变种进行压缩，对得到的结果再使用Huffman编码的方法进行压缩，压缩率很高，但同样比较耗时。这两种算法使用均比较广泛，性能相似，可以根据情况选择。

BZIP

与其他几种算法比较，压缩率更高，但是压缩效率也更低，可以用于需要极致压缩率的场景，一般情况下不太推荐使用。