数据库压缩技术简介

为什么要压缩

最近接触到一些海量数据存储的需求，为了解决这样的需求，一个想法是对数据进行一定程度的聚合。在应用层的聚合方式，这里不展开。但是让我联想到的是以前学习 prometheus tsdb的时候接触到的压缩技术。即使本质上来讲，应用层的数据聚合，就是一种数据压缩技术。而 tsdb 使用的 gorilla 技术令人印象深刻。有兴趣的可以详细看一下 prometheus 作者的这篇博客, 以及其使用的技术 gorilla 的 paper. 简而言之 prometheus 的 tsdb 简洁强大，受益于其高效的压缩【gorilla 平均能压缩 16 byte samples to an average of 1.37 bytes】和查询效率，其单机的设计并没有影响他在众多场景中的广泛使用。

从这个例子可以看出，好的压缩技术对于 data intensive applications 是非常关键的【建议新版 ddia 加一章】。总结来说，对数据库数据的压缩，至少有以下的好处：

1. 使用更小的空间，节约成本，有调研认为，实际上存储的成本要高于 cpu 和内存，尽管单价更低，然而存储需求空间的膨胀高于对计算的需求。
2. 更小的空间意味着更小的 seek distance，更多的单次读出数据，对磁盘的查询效率会更高【当然数据更小，数据库也可以做更多优化，比如更智能的 clustering of related objects into physically near locations】。
3. 提高各种单位带宽的传输数据，这些带宽包括不限于：磁盘与内存，内存与 cpu 缓存，Client-Server 系统中的客户端和存储服务端之间的数据传输，这些对于访问数据库的端到端性能非常关键【这里面还包含了各级缓存的 hit rate 的提高】。

关于为什么要压缩，一篇比较老的论文 【Data Compression and Database Performance】给出了一些实际低数据，证明即使在传统的 (row based) 数据库领域，压缩往往也是很有好处的。更不用说各种列式数据库或者时序数据库了【由于其数据特点，往往更适合压缩】

压缩技术简介

由于数据库的特殊场景，和 generic 的数据压缩技术相比，应用的数据库中还需要考虑下面几点

1. 应用在什么层次，row、column、page、field？
2. 对于取数据的影响如何，比如 projection、join 查询，query 之前是否要先解压缩，如果是固定压缩方式，往往不需要先解压缩，这样效率就会高很多
3. 对于不同的数据库，比如关系型、nosql、列式数据、时序，压缩方式往往有所不同，尽管有一些技术是通用的。

下面会介绍先一些常用的传统技术，然后介绍在各种数据库中使用的压缩方式。

字典压缩 - Dictionary Compression

这种技术很简单，即把不同的字段值转成一组数字，用数字来存储，这样就是大幅的压缩空间。比如下面这个例子。

# 原始数据
China
America
China
China
Japan
China

# 使用字典将数据转成 ID
China -> 1
America -> 2
Japan -> 3


# 压缩后的数据
1
2
1
1
3
1

这种技术很常用，尤其是对于文本的数据压缩，还可以利用类似 Huffman encoding 的技术对出现的 value 按照出现频率进行变长编码，可以进一步的优化空间。

前缀编码 - Prefix Encoding Compression

这种技术和下面的游程编码很类似，不同的是一般只对相同前缀进行压缩。比如对于一组文本，本身在存储的时候已经排序：user, used, useful, useless, 他们的前缀都相同，那么在存储的时候只需要存固定前缀和 r, d, ful, less。对于一些常见的场景，比如时间字符串，phone number，固定前缀是很常见的。

游程编码 - Run-length Encoding Compression

这种技术古老常见，看下面的例子

# 原始数据
AAAABBAACCC

# 压缩数据
A4B2A2C3

# 也可能是分开存储
数据：ABAC
开始位置: 0468

Cluster Encoding Compression

将数据分成多个 block，如果一个 block 里面的数据都一样，那么就替换成一个数字，比如下面的例子

# 原始数据
4444 4333 3333 1100

# 压缩数据
4 4333 3 1100

元数据 bit vector： 1010 其中1表示用一个数字做了整个 block 的替换

Sparse Encoding Compression

一种稀疏数据的压缩方式，思想就是先移除出现最多的数据，然后新增一个 bit vector 表示出现最多的数据的位置，比如下面的例子

# 原始数据
444332114444112

# 压缩数据
33211112
元数据：4 111000001111000  1 表示4出现在对应的位置

mysql 压缩

• InnoDB 中默认使用 zlib 算法进行压缩，也可以选择 snappy、quicklz 等，详细的对比可以参考这里的一篇文章，简而言之： snappy 和 quicklz在压缩比和cpu消耗上保存了较好的平衡，这两种算法在新开发的软件中使用更为广泛，包括TokuDB、MongoDB等。
• rocksdb 引擎的压缩率一般更高，其使用了 前缀编码和零填充行元数据的技术，提高了数据的压缩率，myrocks 的文档里面给了这样一个例子, 同样的数据在 InnoDB 占用 1172GB，在 MyRocks 中占用 574GB。

hbase 压缩

目前 HBase 可以支持的压缩方式有 GZ（GZIP）、LZO、LZ4 以及 Snappy。 它们之间的区别如下：

• GZ：用于冷数据压缩，与 Snappy 和 LZO 相比，GZIP 的压缩率更高，但是更消耗 CPU，解压/压缩速度更慢。
• Snappy 和 LZO：用于热数据压缩，占用 CPU 少，解压/压缩速度比 GZ 快，但是压缩率不如 GZ 高。
• Snappy 与 LZO 相比，Snappy 整体性能优于 LZO，Snappy 压缩率比 LZO 更低，但是解压/压缩速度更快。
• LZ4 与 LZO 相比，LZ4 的压缩率和 LZO 的压缩率相差不多，但是LZ4的解压/压缩速度更快。

下面的表格来自阿里云：

mongo 压缩

在MongoDB 中，WiredTiger为集合提供三个压缩选项：

• 无压缩
• Snappy（默认启用） – 很不错的压缩，有效利用资源【在各种文本测试场景中，压缩率约在54%~55%】
• zlib（类似gzip） – 出色的压缩，但需要占用更多资源
• zstd（从MongoDB 4.2开始支持）

clickhouse 压缩

其中使用的 通用压缩算法其实和别的数据库差不多，比如：

• LZ4：非常高效的压缩算法，在SLS内部大量使用，压缩和解压性能都极强，尤其是解压性能可达到单核4GB/s。缺点是压缩率有点低（但是在日志场景可以达到5-15倍的压缩率，还是非常适用的）
• ZSTD：虽然压缩/解压效率不如LZ4，但是也可以达到单核400M/s的压缩和1G/s左右的解压

列/时序压缩算法：适合按列存储数据，尤其适合时序场景，我们已经看到了 gorilla 在prometheus tsdb 中的成功应用，在适合的场景下，这种算法的压缩效果可能会达到惊人的 10% 甚至 1%，这部分的压缩方式和设计思想尤其值得我们学习。

• Delta，其思想就是存储变化值，比如这样的数据: 1, 2, 3, 3, 2, 4, 会被压缩成 1(base), 1, 1, 0, -1, 2
• DoubleDelta：存储的是 delta 的 delta，比如 1589636543 1589636553 1589636563 1589636573 1589636583 1589636594 1589636603, 会被压缩成 1589636543(Base) 10(Delta) 0 0 0 1 -1 ...
• Gorilla: 其实 DoubleDelta 是参考的 facebook 的 Gorilla 论文，而 clickhouse 中的 gorilla 则是针对 double 数值的一种变化。通过异或的形式来计算前后的 Delta，来解决 DoubleDelta 对于 double 数据压缩很差的问题。
• T64：2019年新引入的编码方式，T64只支持int/uint类型的压缩。首先压缩前拿到数据类型，然后会计算数据的Max Min，根据Max Min获得有效的bit位，然后把数据映射到64*bit位的空间，由于64是固定的，因此叫做T64。

类似 Delta、DoubleDelta 的算法存在的一个问题是，取数据需要一整块全部取出来，才能恢复出数据，有点类似视频压缩中，需要关键帧，仅仅用 p 帧无法恢复数据。

在 clickhouse 中往往是几种算法组合使用。效果可以参考这篇文章。

prometheus

其实在上面的 clickhouse 里面已经介绍了 prometheus 使用的压缩算法，即 DoubleDelta，不过作为一个比较简洁的基于 lsm tree 的时序数据库实现，其中的比如 compaction 方式、文件存储方式、标签（label）的存储方式值得学习。相关的几个有用的参考：

• https://www.zhihu.com/question/19887265)
• The NoSQL Ecosystem
• Key-Value stores:a practical overview

参考

• Data Compression and Database Performance (Goetz Graefe, Leonard D. Shapiro)
• A SHORT SURVEY OF DATA COMPRESSION TECHNIQUES FOR COLUMN ORIENTED DATABASES (Priyanka Raichand* and Rinkle Rani Aggarwal)
• Writing a Time Series Database from Scratch
• Compression Techniques in SAP HANA
• database-compression
• Hbase在数据压缩与编码中的实际应用
• MongoDB 3.0新增的压缩选项
• ClickHouse源码分析-压缩算法大揭秘