TLV 格式 及 VARINT 数值压缩存储方法

迁移的之前的文章

最近需要使用 Thrift 格式进行数据序列化反序列化,遇到一些问题,所以看了下 thrift 的 java 库以及 python 库,学习了下 thrift 的存储格式,主要使用 thrift 的 TCompactProtocol。
发现该序列化方式主要使用了 TLV 格式式来存储每个字段,使用 VARINT 来表示其中的 L。

TLV 格式

很简单,Type-length-value(类型 - 长度 - 值)。在一串字节中,使用该方式标示出一个自定义的字段。
三个域的表示方式均可自定义。如使用 1 个字节标示数据类型 T,使用 4 个字节标示数据长度 L,之后使用 L 个字节来表示数据的值。(其实 Thrift 的 TBinaryProtocol 就是这种方式)

VARINT 数值压缩存储

c 中 int 使用 4 个固定字节表式,即使数字很小。假如使用 int16,则不能表示较大的数字。
而 VARINT 是一种可变长度的表示数字的方法,当数字较小时可以使用 1 个字节,如果比较大需要利用 5 个。
int 转为 varint,TCompact 的 java 实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
private void writeVarint32(int n) { int idx = 0;
while (true) {
if ((n & ~0x7F) == 0) {
i32buf[idx++] = (byte)n;
break;
} else {
i32buf[idx++] = (byte)((n & 0x7F) | 0x80);
n >>>= 7;
}
}
trans_.write(i32buf, 0, idx); // trans_不用管,可以看作字节流
}

其实就是,依次从字节串的末尾选取 7 位,最高位添加 1 或 0 构造出 1 个字节。并且,只有最后一次选取时最高位置为 0,此时剩余的位构成到数字是小于 1000 0000,的所以添加 0 并不会影响其大小。如下:

1
2
3
4
5
6
7
10 进制: 296
16 进制: x01 x28
2 进制: 0000 0001 0010 1000
a --- ---- ==> 1010 1000 选择末 7 位,最高位置为 1
b -- ---- - ==> 1010 1000 0000 0010 右移 7 位,选择末 7 位,最高位置为 0
VARINT: 1010 1000 0000 0010
16 进制:xa8 x02

很明显,通过这种方法,我们得到的 VARINT,依次读取每个字节,只有表示该 VARINT 的最后一个字节,最高位为 0。所以,当我们读取 VARINT 时,只要读取到最高位为 0 的字节时,就表示已经是 VARINT 的最后一个字节了。

结合 TLV 就是:先读取 1 个字节得到类型 T;然后读取 n 个字节计算出长度 L,其中第 n 个字节的最高位为 0;然后读取 L 个字节,表示我们的 V。

最后,我们看下读取 VARINT 时,python 的处理方法:

1
2
3
4
5
6
7
8
9
10
def readVarint(trans):
result = 0
shift = 0
while True:
x = trans.readAll(1) // 读取下一个字符
byte = ord(x) // 转成整数表示
result |= (byte & 0x7f) << shift // 将该字节去掉最高位放在已有结果的左侧
if byte >> 7 == 0: // 如果该字节最高位是0,结束
return result
shift += 7