Apache Orc 压缩原理

前言

orc 作为列式存储,其特点之一就是极高的数据压缩比,这篇文章就来讲讲它的压缩原理。

数据类型

orc 对于每种不同的数据类型,对应着不同的压缩方式。比如 string类型压缩,int 类型压缩,字节类型压缩。下面会依次介绍它们的原理。除此之外,它们还支持在外层共有的压缩格式,可以指定 zlib 或者 snappy。关于压缩配置参数有下面两个:

  1. orc.compress指定了编码格式,默认为zlib。
  2. orc.compress.size指定了编码的buffer大小,默认256KB。

整数类型压缩

整数类型的压缩有三个版本,第一个版本是采用了重复元素编码,第二个版本是采用了等差元素编码。为了提高压缩效率,orc 开发出了第三版。所以本片会直接讲解最新版的压缩。orc 会根据数据的分布情况,采用不同的编码方式。

Short Repeat 编码

如果数据元素都是相同的,并且重复的元素长度大于等于3,还要小于等于10,那么就会采用这种编码。它的存储格式如下:

1
2
3
4
5
-----------------------------------------------------------------
  encoding type   |   重复值的长度  |  重复的元素数目  |   重复值   |     
------------------------------------------------------------------
  2 bits          |    3 bits     |   3 bits       |           |
------------------------------------------------------------------

前面的 encoding type 是通用的头部格式,通过它知道该数据的编码格式为 short repeat。

重复值所占用存储的字节长度用 3 bit 表示,也就是最多能表示 7bytes 的值。

重复的元素数目用 3 bit 表示,因为只有重复元素大于等于3才会触发该编码,所以 7 + 3 = 10。它只能最多表示10个重复元素的编码。

重复值的存储时,也会做一次编码,它采用了 ZigZag 编码,并且会将为零的高位截断。比如有一个数字 15,它只需要使用 1byte 就可以存储了。

Delta 编码

当满足下列条件之一,就会采用 delta 编码。

  1. 重复的元素长度大于10个
  2. 元素排列为等差数列的形式
  3. 元素排列为递增或者递减

delta 编码的通用格式如下:

1
2
3
4
5
-------------------------------------------------------------------
  encoding type   |   值占用的位数 fb  |   元素数目       |   blob   |     
-------------------------------------------------------------------
  2 bits          |    5 bits        |   9 bits        |           |
-------------------------------------------------------------------

如果 fb 等于0,说明元素为重复元素或者等差数列,对应的blob 会使用 zigzag 编码,存储第一个元素的值。接着会只存储等差值。

如果 fb 不等于0,说明是第三种情况。blob 的数据使用 zigzag 编码,存储第一个元素的值。接着会存储相邻元素的差值。

Direct 编码

如果元素的值,它们占用的 bit 位数,相差不大的话,就会采用 direct 编码。那么这个相差不大,是如何判断的。首先它会遍历元素,使用直方图统计出各个 bit 位数对应了多少个元素,如果第90%的元素所占用的 bit 位数,与最大值的元素所占用的 bit 位数相等,那么就认定为相差不大。direct 编码的格式为:

1
2
3
4
5
------------------------------------------------------------------------
  encoding type   |   每个值存储占用的位数  |   元素数目       |   blob   |     
-------------------------------------------------------------------------
  2 bits          |    5 bits           |   9 bits        |           |
------------------------------------------------------------------------

direct 顾名思义,也就是直接编码。所以它仅仅是在存储单个值的时候,使用了 zigzag 编码。每个元素的值经过编码后,存储到 blob 里。

Patch Base 编码

如果元素的分布范围比较大,无法使用 direct 编码时,那么就会使用 patch base 编码。

首先它找出元素中的最小值,然后计算出各个元素与最小值之间的差值。然后计算出差值占用 bit 位数的分布情况,如果第 95% 的元素占用的 bits 位数与最大差值占用的 bit 位数不等的话,就会使用 patch base 编码。然后将数据分为前 95%和后5%两部分。根据前95%的元素,会推算出每个差值占用的存储数据位数。所以对于前95%的元素,可以直接存储。对于后面 5% 的元素,则还额外存储了高位数据。

Byte类型编码

对于字节类型的数据,编码方式比较简单,只是简单的合并重复值,也称为RLE算法。当重复值连续出现3次,才会触发该编码。

1
2
3
4
5
----------------------------
  control byte   |   blob  |      
----------------------------
  1 byte         |----------------------------

当 control byte 的值 小于 0时,表示没有重复值,表示后面数据的数目。后面的 blob 都是存储着数值列表。

当 control byte 的值 大于等于 0时,表示有重复值,表示重复数据的数目。后面的 blob 都是存储着重复数。

字符串类型编码

对于字符串类型的数据,orc 提供了字典编码方式。字典编码的原理是,将去重后的字符串存到一个集合里,然后每行数据只需要记录,自身数据对应集合里的位置。这样对于有重复的字符串是非常高校的。比如有一列表示省份,我们知道省份也就只有30多个,如果该表有几千万行,那么每行只需要记录一个 id 号就行,极大的提高了压缩效率。不过要想触发字典编码,有个orc.dictionary.key.threshold配置项需要注意,默认为 0.8。表示只有去重的数据行数,低于总行数的占比,才能触发字典编码。

updatedupdated2023-07-022023-07-02