ClickHouse源码分析-压缩算法大揭秘

2021-12-03 06:26:31

前言

ClickHouse在近年来增加了很多压缩算法，最主要的改进还是为了更好的适应时序场景，提高压缩率，节省存储空间。本期就给大家带来ClickHouse的压缩算法介绍。

算法分类

ClickHouse的压缩/解压代码相对比较清晰，抽象做的很好，这样对于后续增加、变更某种压缩算法会非常的方便。这里就不给大家介绍代码结构，直接从比较核心的算法讲起。目前ClickHouse中提供的压缩算法非常丰富，总体上可以划分为三类：

通用压缩算法：适用于所有数据的压缩，包括：None、LZ4、ZSTD。
列/时序压缩算法：适合按列存储数据，尤其适合时序场景，需要知道每列的特性来选择，包括：T64、Delta、DoubleDelta、Gorilla。
组合压缩算法：这种压缩本身并不包含任何压缩算法，实际上是将以上算法组合使用，使综合压缩率进一步提升。

None

Clickhouse是支持完全不压缩的，带来的好处就是读取不消耗CPU，但是相对存储量会大很多，IO也会有巨大的开销，一般不建议使用这种模式。

注：为了兼容压缩逻辑，内部实现为memcpy。

LZ4

非常高效的压缩算法，在SLS内部大量使用，压缩和解压性能都极强，尤其是解压性能可达到单核4GB/s。缺点是压缩率有点低（但是在日志场景可以达到5-15倍的压缩率，还是非常适用的）。

LZ4的压缩原理是按照4字节窗口扫描，查找与之前的值是否匹配，如果匹配按照贪心算法匹配最长值，压缩格式的示例如下。LZ4的格式非常简单，因此解压只需要顺序扫描一遍，做一些memcpy即可完成，因此解压速度极快。具体的细节可以参考 https://github.com/lz4/lz4。

raw：abcde_bcdefgh_abcdefghxxxxxxx
compressed：abcde_(5,4)fgh_(14,5)fghxxxxxxx

lz4里面和压缩性能息息相关的是Hash函数，官网是用了xxHash，性能也是非常棒，SLS内部很多和Hash有关的代码都是用xxHash。实现可以参考：https://github.com/lz4/lz4/blob/dev/lib/xxhash.h。

ZSTD

虽然压缩/解压效率不如LZ4，但是也可以达到单核400M/s的压缩和1G/s左右的解压（具体需要看数据特性以及机器规格）。和LZ4相比最好的是压缩率，我们测试了实际的线上数据，压缩率相比LZ4可以提升30%，也就是说可以节省30%的存储空间。而SLS当前的机器CPU使用率比较低，但是存储水位比较高，所以我们将部分数据改为了ZSTD以节省磁盘。相比LZ4它可以根据参数调整压缩速度（速度提升带来的效果就是压缩率会变低）。

基准测试可以参考：https://github.com/facebook/zstd。ZSTD背后的男人其实是一个熵编码器（论文：https://arxiv.org/abs/1311.2540，代码：https://github.com/Cyan4973/FiniteStateEntropy），作者叫他FSE（Finite State Entropy）（有限状态熵）。

T64

2019年新引入的编码方式，T64只支持int/uint类型的压缩。首先压缩前拿到数据类型，然后会计算数据的Max Min，根据Max Min获得有效的bit位，然后把数据映射到64*bit位的空间，由于64是固定的，因此叫做T64（transpose 64 bit matrix）。这种压缩方式对于变化不大或很小的数据有很高的压缩率，但是因为只去掉了头部的bit位，剩下的可能还有很多重复的部分，因此大部分场景下还是嵌套一个LZ4/ZSTD来使用（嵌套的压缩方式下面会介绍）。

T64压缩中有个选项是控制转换的粒度，默认是按照字节来转换（及满1个字节的直接按照1个字节来拷贝，字节内的bit不做转换），如果是bit模式的话每个字节还会做一个转换，这样的情况下每个字节都会多一次反转，还是很耗费性能的，但是搭配ZSTD会具有较高的压缩率（如果搭配LZ4的效果反而会差）。之所以是这样还是因为LZ4和ZSTD实现机制的不同，额外做一轮Bit的转换，是让相同的bit能够更加集中，熵编码的效果会更好，但是带来的后果就是字节之间的连贯性会变差，LZ4是查找Byte的相同点，转换后基本都不一样了，所以效果会变差。

Delta

Delta编码存储一个基础值以及后续相邻两个数据的差值，对于有恒定/变化特别小差值的情况下效果比较好，一般情况下Delta编码需要配合LZ4或者ZSTD来吧后面的插值部分进一步压缩。

raw : 5 6 7 8 9 10 11 12 13 ....
Delta : 5(Base) 1 1 1 1 1 1 1 1 ....

Double Delta

最早出现于Facebook的Gorilla中（http://www.vldb.org/pvldb/vol8/p1816-teller.pdf），存储的是Delta后的Delta，对于恒定增加/减小的值，Delta一般是一个固定值，但是这个值可大可小，存储起来还是占用比较大的空间，如果再次对Delta计算Delta，则大多数情况下为0。对于大数据场景，尤其是监控场景中，这一类数据非常常见，比如时间列通常都是固定的N秒一个点；自增列每次都是加1；请求次数/流量等累加值，通常变化也会比较平均。对于Delta of Delta的编码细节还是很多的，主要的目的还是减少存储的数据量，增大信息熵，有兴趣的同学可以看看论文。

raw : 1589636543 1589636553 1589636563 1589636573 1589636583 1589636594 1589636603...
Delta of Delta : 1589636543(Base) 10(Delta) 0 0 0 1 -1 ...

注意：Double Delta还一个特性是支持Compressed read（也就是不解压出原始的数据，直接在压缩的block上读取想要的数据），但由于ClickHouse把压缩做了一层抽象，所以只能解压后再读。

Gorilla

Double Delta主要适应于int类型的压缩，而对于Double Gorilla中也提出一个专门的压缩算法，但没有起一个特性的名称，最后大家都叫它Gorilla算法。

符号位	指数位	尾数位
1 bit	11 bits	52 bits

对于一个64位float，有1个符号位，11个指数位和52个尾数位，纯粹从每个部分来看变化都很小，但float通常用来表示某个实际意义的值（比如GPS、温度、请求成功率），直接按照每个部分计算Double Delta再编码效果会很差。而Gorilla算法是通过异或的形式来计算前后的Delta，然后再看异或值的前后0个数，最后只保存前后0个数、中间有效位。而Delta之间则先比较异或值前后0个数，如果相同则只需要写中间的有效位。

具体的结构可以参考：

注意：ClickHose的Gorilla算法也一样不支持Compressed read。

Multiple

Multiple其实并不是一个压缩算法，而是一个包装类，能够组合N个前种算法。例如组合T64、ZSTD，这个Multiple就会在压缩的时候先调用T64，然后调用ZSTD，解压的时候调用LZ4解压然后再调用T64解压。

compress :  T64 -> ZSTD
uncompress : ZSTD -> T64

多种压缩算法搭配使用的情况也非常常见，SLS内部有很多就是用了类似的算法，SLS中很多索引的编码都是用了2-3套压缩算法组合，像在时序引擎上面的压缩算法种类更多，有些会用4-5种算法组合。

总结

ClickHouse新增的T64、Delta、Double Delta、Gorilla算法其实主要还是针对时序场景，这些算法基本上都是针对前后变化不大的数据设计，因此在时序场景中会获得非常高的压缩比。

唯一的缺憾是：由于ClickHouse对压缩/解压做了一层抽象，一些能够支持压缩读的算法还是需要解压读，效率上会有所损失。

此外还有一些比较常用的Prefix编码、RLE等其实也非常好用，且性能极高，也支持压缩读，希望ClickHouse也会支持。

码农公寓

前言