RLE 编码在 Apache ORC 中的实现

介绍 Apache ORC 中 RLE v1 和 RLE v2 的具体算法实现。

最近刚学习了 Zigzag(浅谈 Apache ORC 之 Decimal 存储),那就干脆趁热打铁,再学一下 Apache ORC 里面的 RLE 吧。

RLE(Run Length Encoding) 说说简单,比如 [1, 1, 1, 1] 四个 int32,本来需要 4 * 4 = 16 bytes 的空间。但是如果使用 (4, 1) 表示,4 表示重复次数,1 表示被重复的数字,那么就只需要 2 * 4 = 8 bytes 的空间就够了。

当然这说的是最简单的 RLE,实际上不可能这么简单,我们可以借由 ORC RLE 编码的实现,来看看 RLE 能被玩的多花。

ORC 有两种 RLE,分别是 version 1 和 version 2。其中 version 1 实现的比较简单,适合入门学习。

前置知识

比如一组数字序列 [1, 1, 1, 1, 2, 2 ,2 ],它使用 RLE 编码压缩后有两个 group,分别是 [1, 1, 1 ,1] 和 [2, 2, 2]。然后每个 RLE group 开始都会有一个 header,相当于这个 group 的 metadata。Header 里面通常会存储这个 group 元素的个数,每个元素 bit width 等信息。

在 ORC 的 RLE 实现中,只有当数字重复次数大于 3 次时,才会使用 RLE 编码。

RLE Version 1

Varint

ORC 在引入了 varint 概念,其实这个和 zigzag 有点像。

计算机中 int 是 32 位,占用 4 bytes。但是如果只是存储一个 int a=1 这样的小数字,那这 4 个 bytes 的空间是大大的浪费,毕竟明明一个 bit 就够了。

Varint 就是为了解决这个问题,其规则很简单。规定一个 byte 中,低 7 位用于存储真实的数据,最高位表示后面是否还存在有效 byte。

Varint 无符号和有符号有着不同处理方式:

无符号

比如 16385,二进制是 [01000000, 00000001]

首先按照 7bit 拆分成三组: [1, 0000000, 0000001。Varint 以小端格式存储,也就是说从低位开始处理。

  1. 先处理 0000001,因为后面还存在有效 byte,所以最高位是 1,即变成 10000001(0x81)。
  2. 再处理 0000000,因为后面还存在有效 byte,所以最高位是 1,即变成 10000000(0x80)。
  3. 最后处理 1,因为后面没有有效 byte 了,所以最高位是 0,即变成 00000001(0x01)。

所以最后实际存储的 byte 数组就是 [0x81, 0x80, 0x01],3 个 byte,比原来 int32 的 4 bytes 省了 1 个 byte。

C++ decode 的代码如下:

  uint64_t RleDecoderV1::readLong() {
    uint64_t result = 0;
    int64_t offset = 0;
    signed char ch = readByte();
    if (ch >= 0) {
      // 正数意味着高位是 0,即后面没有有效数字了。
      result = static_cast<uint64_t>(ch);
    } else {
      // 负数意味着高位是 1,即后面还有有效数字。
      result = static_cast<uint64_t>(ch) &  0x7f;
      while ((ch = readByte()) < 0) {
        offset += 7;
        result |= (static_cast<uint64_t>(ch) &  0x7f) << offset;
      }
      result |= static_cast<uint64_t>(ch) << (offset + 7);
    }
    return result;
  }

有符号

有符号的话,按照上面这个方法就不行了,比如 -1,它存储的二进制是 [11111111, 11111111, 11111111, 11111111](计算机负数按照补码存储),一堆 1,按照上面的方法根本就没法压缩了。不过这个问题 zigzag 能很好的解决,具体见 浅谈 Apache ORC 之 Decimal 存储

RLE 规则

RLE 会把一组数字序列划分成多个 Group,每个 Group 都有一个 header,header 占用 1 个 byte。

Header 为正数:

表示该 Group 是有规律的,其 header 的值 + 3 表示该 group 有多少个数字(之所以加 3 是因为 RLE 保底就有 3 个数字)。

第二个 byte 表示 delta,delta 用于处理递增、减序列,1 表示递增 1,-1 表示递减 1,0 表示都是重复的数字。最大能表示 -128 to 127 的范围。

后面的一个数字以 varint 格式存储。

比如 100 个 7,会表示成:

  • header:该 group 有 100 个数字,但是因为保底有 3 个,所以 header 值是 100-3=97(0x61)。
  • delta:因为没有递增关系,所以 delta 为 0(0x00)。
  • varint:7(0x07)。

所以这个 RLE Group 由 3 个 byte 表示,存储为 [0x61, 0x00, 0x07]

再比如递减序列 [100, 99, ... 1] 表示成:

  • header:该 Group 有 100 个数字,100-3=97(0x61)。
  • delta:每次减一,所以 delta 为 -1(0xFF)。
  • varint:100(0x64)。

所以这个 RLE Group 由 3 个 byte 表示,存储为 [0x61, 0xFF, 0x64]

Header 为负数:

表示该 group 的数字序列是没有规律的,它的绝对值表示该 group 所含数字的个数。然后它没有 delta。后面的数字同样以 varint 格式存储。

比如 [2, 3, 6, 7, 11] 这 6 个没有规律的数字,表示成:

  • header:有 5 个数字,用 -5 (0xFB)表示。
  • varint:有 5 个数字,均以 varint 格式存储,分别是 2(0x02),3(0x03), 6(0x06), 7(0x07), 11(0x0B)。

所以这个 RLE Group 由 6 个 byte 表示: [0xFB, 0x02, 0x03, 0x06, 0x07, 0x0B]

当然上面说的都是 unsigned 的情况,如果是 signed 的数字序列,那么就不是用 varint 存储数字,而是 zigzag 编码了。

RLE Version 2

RLE version 2 就要上强度了,焊死车门,坐稳了。

RLE version 2 引入了四种编码方式,分别是:

  • Short Repeat – 用于处理重复值,但是一个 group 能表达的数字个数不多,只有 3~10 个。
  • Direct – 表达随机数字序列,但是要求每个数字都用固定的位宽(bit width)表示。
  • Patched Base – 和 Direct 一样表示随机数字序列,但是针对的是每个数字 bit width 不固定的情况。
  • Delta – 用于处理递增或者递减的数字序列。

在 RLE header 中,最高两位 bit 用于表示 encoding type。

Short Repeat 是(00),Direct 是 (01),Patched Base 是(10),Delta 是(11)。

Shot Repeat

Header 占用 1 bytes:

  • 2 bit 表示 encoding type。
  • 3 bit 表示每个数字所需 bytes,3 bit 最多只能表示 0~7 bytes,但是因为 ORC bit width 从 1 开始算,所以能表示 1~8 bytes。数字以 big endian 形式存储。如果是有符号数字,则采用 zigzag 编码。
  • 3 bit 表示该 group 数字的个数,3 bit 最多只能表示 0~7。但是因为 ORC RLE 从 3 个开始起步,所以 shot repeat 最多能表示 3~10 个数字。

Bit width 和 group 数字个数都是二进制对应的数值得再额外加上一个基础值(起步价),后面很多地方都这样。

比如无符号的数字序列 [10000, 10000, 10000, 10000, 10000]

10000 的二进制是 [00100111, 00010000],正常来说需要 2 bytes 的空间。

那么 1 byte header 是 00001010(0x0A):

  • 00,表示 encoding type(0)。
  • 001,1,但是位宽从 1 byte 开始起步计算,所以这里表示的数字位宽是 2(1 + 1) bytes。
  • 010,2,表示该 group 有 5(2 + 3) 个数字。

后面 2 bytes 是:[00100111, 00010000](0x27,0x10),即 10000 的二进制。

所以 [10000, 10000, 10000, 10000, 10000] 压缩后的 bytes 是 [0x0A, 0x27, 0x10]。

Direct

Direct 引入了一个 5 bit width encoding table,二进制中实际存储的是 encoded value,然后通过查阅这个表,得知对应的 bit width 是多少。表格先在这里贴出来,Direct,Patched Base 和 Delta 都会用到。

WIDTH IN BITSENCODED VALUENOTES
00for delta encoding
10for non-delta encoding
21
43
87
1615
2423
3227
4028
4829
5630
6431
32deprecated
5 <= x <= 7x – 1deprecated
9 <= x <= 15x – 1deprecated
17 <= x <= 21x – 1deprecated
2624deprecated
2825deprecated
3026deprecated

Header 占用 2 bytes:

  • 2 bits 表示 encoding type,Direct 的 encoding type 是 1。
  • 5 bits 表示 encoded value,你可以根据上面的表格,找到对应的 bit width(W),表示该 group 中每个数字的位宽。
  • 9 bits 表示这个 group 数字的个数(L),能表示 1~512 个。

Header 后面会跟随 W*L bits(末尾会按照 byte 对齐),以大端格式存储。如果该 group 的数字是 signed,那么采用 zigzag 编码。之所以末尾需要 byte 对齐,因为所有的 RLE header 都是按照 byte 对齐的,你前面的屁股不对其,后面的 RLE group 没法读了。

举个例子,压缩 [23713, 43806, 57005, 48879] 这 4 个随机数字:

23713:101110010100001 (15 bit)

43806:1010101100011110(16 bit)

57005:1101111010101101(16 bit)

48879:1011111011101111(16 bit)

由上可知,最大需要 bit width = 16 bits。根据 5 bit width encoding table 查阅,得知 ENCODED VALUE 是 15。

所以 2 byte header 如下:

  • 01,1 是 Direct 的 encoding type。
  • 01111,15,是 encoded value。
  • 000000011,3,表示有 4(3 + 1)个数字(因为起步价就有 1 个数字,需要 + 1)。

所以这 2 byte header 是 [01011110, 00000011],即 [0x5E, 0x03]。

后面的数字:

23713([01011100, 10100001]), [0x5C, 0xA1]。

43806([10101011, 00011110]),[0xAB, 0x1E]。

57005([11011110, 10101101]),[0xDE, 0xAD]。

48879([10111110, 11101111]),[0xBE, 0xEF]。

所以这一组数字压缩后是:[0x5E, 0x03, 0x5C, 0xA1, 0xAB, 0x1E, 0xDE, 0xAD, 0xBE, 0xEF]。

Patched Base

Direct 只能用于压缩固定 bit width 的数字数列,如果当一组数字中,有些数字特别大,所需位宽特别多的时候,Direct 就没法用了。

Patched base 相当于 Direct 的加强版,能有效解决数字间 bit width 差距很大的情况。

Patched base 首先会选择一组数字序列中最小的数字,作为 base value,之后存储的数字都是与 base value 的差值。这样的好处就是能减少每个数值占用的位宽。

然后它会按照 90% 的分水岭选择 bit width(W),即保证 90% 的数字都可以用 W bits 装下,剩下 10% 的数字则通过额外打 patch 的方式扩展 bit width。

Patch list 是在 RLE group 的末尾,patch list 的结构是 [[patch gap + patch], [patch gap patch], ….]。每一个超长度的数字都会有一个对应的 [patch gap + patch]。

Patch gap 是距离上一个被打 patch 数字的间隔。比如 [1, 2, 3, 100, 4, 1000],其中 100 和 1000 需要打 patch。100 的 patch gap 是 4,1000 的 patch 是 2。

Patch 就是多出来的 bit,以 100 为例,它的二进制是 1100100,假设 90% 数字的 bit width 是 2,也就是说按照 bit width = 2 已经存了 00 两个 bit 了。后面 11001 则是 patch。

4 bytes header:

  • 2 bits 表示 encoding 类型,patched base 是 2。
  • 5 bits 用于表示满足90% 数字的 encoded value(1~64bits),和 Direct 一样,通过 5 bit width encoding table 可以查阅得到对应的 bit width(W)。
  • 9 bits 表示这个 group 所含数字个数(L)(1~512个)。
  • 3 bits 表示 base value 的长度(BW),单位是 bytes(1 ~ 8 bytes)。
  • 5 bits 表示 patch 的 encoded value (1 ~ 64 bits) ,同样通过 5 bit width encoding table 进行查阅得到对应的 bit width(PW)。
  • 3 bits 表示 patch gap width(PGW)(1 ~ 8 bits)。
  • 5 bits 表示 patch list 的长度(PLL),即有多少个 patch。 (0 to 31 patches)。

Base value 按照大端存储。如果 base value 是负数,那么首个 bit 会被设置为 1。

Data values 的总长度等于 W * L bits,末尾按照 byte 对齐。Data value 里面存储的数字一定是 >= 0 的,因为它存储的是与 base value 之间的差值。

Patch list 的长度是 PLL * closestFixedBits(PGW + PW) bits。(PGW + PW)同样有对齐,参照下面的表格即可。

(PGW + PW)CLOSESTFIXEDBITS(PGW + PW)
1 <= x <= 24x
2526
2626
2728
2828
2930
3030
3132
3232
33 <= x <= 4040
41 <= x <= 4848
49 <= x <= 5656
57 <= x <= 6464

下面以无符号的数字序列:[2030, 2000, 2020, 1000000, 2040, 2050, 2060, 2070, 2080, 2090, 2100, 2110, 2120, 2130, 2140, 2150, 2160, 2170, 2180, 2190] 为例。

首先进行如下分析:

  1. 采用 patched base 编码,所以 encoding type 是 2。
  2. 最小数字是 2000,所以 2000 作为 base value。2000 需要 11 个 bit,也就是 base value 的 bit width = 2 bytes。
  3. 所有数字减去 2000 后是:[30, 0, 20, 998000, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150, 160, 170, 180, 190]。
  4. 除了 998000,其余所有数字都可以用 8 个 bit 装下。根据 5 bit width encoding table 查阅得知,encoded value 是 7。
  5. 总共有 20 个数字,所以 group 长度为 20。
  6. 998000 总共需要 20 个 bit 存储,然后我们已经存储了 8 bit 存储,所以只是额外再需要 12 个 bit 作为 patch。
  7. 998000 前面有 3 个数字,所以 patch gap width 用 2 bit 就够存 3 这个 gap 了。
  8. 同时因为只有 998000 这个数字需要打 patch,所以 patch list 长度(PLL)为 1。

Header:

  • 10,encoding type = 2。
  • 00111,encoded value = 7,表达出 90% 的数字都能用 8 bits 装下。
  • 000010011,group length,这里是 19,能表达出 20 的意思(19 + 1)。
  • 001,base value 的 bit width,这里是 1,能表达出 2 bytes 的意思(1 + 1)。
  • 01011,patch 的 encoded value,这里是 11,查阅 5 bit width encoding table 得知对应的 patch bit width = 12 bits。
  • 001,patch 的 gap width,这里是 1,表达的是 2(1 + 1)。
  • 00001,patch list 的长度,是 1,只有 998000 需要打 patch。

综上,header 是:[10001110, 00010011, 00101011, 00100001],即 [0x8E, 0x13, 0x2B, 0x21]。

后面是 base value,2000 是 [00000111, 11010000],即 [0x07, 0xD0]。

后面的 20 个数字,按照 8 bits 的宽度存储,分别是:

[0x1E, 0x00, 0x14, 0x70, 0x28, 0x32, 0x3C, 0x46, 0x50, 0x5A, 0x64, 0x6E, 0x78, 0x82, 0x8C, 0x96, 0xA0, 0xAA, 0xB4, 0xBE]。

注意,998000 只需要存储低 8 位 01110000(0x70) 就够了。高 12 位放在 patch 那里。

后面跟着一个 patch gap,998000 前面有 3 个数,所以 gap = 3,即 11。后面则是 998000 高 12 位的内容,是 111100111010

所以整个 patch list 是 [11111100, 111010],末尾 111010 需要按照 byte 对齐,就变成 11101000。所以最后 patch list 就是 [11111100, 11101000],即 [0xFC, 0xE8]。

Delta

存储递增或递减数字序列。第一和第二个数字不能相同,因为第一个 delta 叫 delta base,它是有符号的,决定了整个数字序列是递增还是递减的。

2 bytes header:

  • 2 bits 用于表示 encoding 类型,delta 是 3。
  • 5 bits 用于表示 delta 的 encoded value (0 to 64 bits),同样通过 5 bit width encoding table 查阅可以得到对应的 bit width。
  • 9 bits 表示该 group 数字的个数 L (1 to 512)。

Base value – 初始数字序列,以无符号以 varint 形式编码,有符号以 zigzag 编码。

Delta base – 第一个 delta,以 zigzag 编码。

Delta values – 后续的 delta,均是无符号的,采用 varint 形式编码。

比如无符号的数字序列:[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]。

分析 base value 为 2,delta base 为 1,delta values 为 [2, 2, 4, 2, 4, 2, 4, 6]。

2 bytes header 编码成:

  • 11,delta encoding = 3
  • 00011,delta 用 4 bits 存储就能存储下,根据 5 bit width encoding table 得知 encoded value 为 3。
  • 000001001,这里是 9,表示 group 有 10(9 + 1) 个数字。

所以 2 bytes header 为:[11000110, 00001001],为 [0xC6, 0x09]。

Base value 为 2, 00000010,即 [0x02]。

第二个元素 3 和 base value 2 之间的 delta 为 1,因为其是第一个 delta,也就是 delta base,需要采用 zigzag 编码。1 zigzag 编码后,是 00000010,也就是 [0x02]。

第三个元素 5 和 第二个元素 3 之间的 delta 为 2,所以是 0010,以此类推,分别是,0010010000100100001001000110

所以压缩后的二进制就是:header [0xC6, 0x09], base value [0x02],delta base [0x02] 和 delta values

[00100010, 01000010, 01000010, 01000110],即 [0x22, 0x42, 0x42, 0x46]。

附录

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
搜索