首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >数据库压缩技术简介

数据库压缩技术简介

原创
作者头像
王磊-字节跳动
修改2021-01-17 18:38:10
3.3K0
修改2021-01-17 18:38:10
举报
文章被收录于专栏:01ZOO01ZOO

为什么要压缩

最近接触到一些海量数据存储的需求,为了解决这样的需求,一个想法是对数据进行一定程度的聚合。在应用层的聚合方式,这里不展开。但是让我联想到的是以前学习 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的解压/压缩速度更快。

下面的表格来自阿里云:

业务类型

无压缩表大小

LZO(压缩率/解压速度MB/s)

ZSTD(压缩率/解压速度MB/s)

LZ4(压缩率/解压速度MB/s)

监控类

419.75T

5.82/372

13.09/256

5.19/463.8

日志类

77.26T

4.11/333

6.0/287

4.16/496.1

风控类

147.83T

4.29/297.7

5.93/270

4.19/441.38

消费记录

108.04T

5.93/316.8

10.51/288.3

5.55/520.3

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)的存储方式值得学习。相关的几个有用的参考:

参考

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 为什么要压缩
  • 压缩技术简介
    • 字典压缩 - Dictionary Compression
      • 前缀编码 - Prefix Encoding Compression
        • 游程编码 - Run-length Encoding Compression
          • Cluster Encoding Compression
            • Sparse Encoding Compression
              • mysql 压缩
                • hbase 压缩
                  • mongo 压缩
                    • clickhouse 压缩
                      • prometheus
                      • 参考
                      相关产品与服务
                      数据库
                      云数据库为企业提供了完善的关系型数据库、非关系型数据库、分析型数据库和数据库生态工具。您可以通过产品选择和组合搭建,轻松实现高可靠、高可用性、高性能等数据库需求。云数据库服务也可大幅减少您的运维工作量,更专注于业务发展,让企业一站式享受数据上云及分布式架构的技术红利!
                      领券
                      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档