RLE 编码在 Apache ORC 中的实现

最近刚学习了 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 BITS	ENCODED VALUE	NOTES
0	0	for delta encoding
1	0	for non-delta encoding
2	1
4	3
8	7
16	15
24	23
32	27
40	28
48	29
56	30
64	31
3	2	deprecated
5 <= x <= 7	x – 1	deprecated
9 <= x <= 15	x – 1	deprecated
17 <= x <= 21	x – 1	deprecated
26	24	deprecated
28	25	deprecated
30	26	deprecated

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 <= 24	x
25	26
26	26
27	28
28	28
29	30
30	30
31	32
32	32
33 <= x <= 40	40
41 <= x <= 48	48
49 <= x <= 56	56
57 <= x <= 64	64

下面以无符号的数字序列：[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，以此类推，分别是，0010，0100，0010，0100，0010，0100 和 0110。

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

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

附录

• 在线进制转换：https://8jz.cn/
• Apache ORC 官方文档：https://orc.apache.org/specification/ORCv1/