Protoc Buffer 是我们比较常用的序列化框架, Protocol Buffer 序列化后的占空间小, 传输高效, 可以在不同编程语言以及平台之间传输. 今天这篇文章主要介绍 Protocol Buffer 使用 VarInt32 减少序列化后的数据大小.
VarInt32 编码
VarInt32 (vary int 32), 即: 长度可变的 32 为整型类型. 一般来说, int 类型的长度固定为 32 字节. 但 VarInt32 类型的数据长度是不固定的, VarInt32 中每个字节的最高位有特殊的含义. 如果最高位为 1 代表下一个字节也是该数字的一部分. 因此, 表示一个整型数字最少用 1 个字节, 最多用 5 个字节表示. 如果某个系统中大部分数字需要>= 4 字节才能表示, 那其实并不适合用 VarInt32 来编码. 下面以一个例子解释 VarInt32 的编码方式:
以 129 为例, 它的二进制为 1000 0001 .
由于每个字节最高位用于特殊标记, 因此只能有 7 位存储数据.
第一个字节存储最后 7 位 (000 0001), 但并没有存下所有的比特, 因此最高位置位 1, 剩下的部分用后续字节表示. 所以, 第一个字节为: 1000 0001
第二个字节只存储一个比特位即可, 因此最高位为 0 , 所以, 第二个字节为: 0000 0001
这样, 我们就不必用 4 字节的整型存储 129 , 可以节省存储空间
在 Protoc buffer 中, 每一个 ProtoBuf 对象都有一个方法 public void writeDelimitedTo(final OutputStream output), 该方法将 ProtoBuf 对象序列化后的长度以及序列化数据本身写入到输出流 output 中. 多个对象调用该方法可以将序列化后的数据写入到同一个输出流. 由于每次写入都有长度, 所以反序列化时先解析长度, 在读取对应长度的字节数据, 即可解析出每个对象. 该方法中对序列化后长度的编码便使用 VarInt32, 因为一个 Protobuf 对象序列化后的长度不会太大, 因此使用 VarInt32 编码能够有效的节省存储空间. 接下来我们看下 Protoc Buffer 中如何实现 VarInt32 编码, 跟进 writeDelimitedTo 方法, 可以看到 VarInt32 编码的源码如下:
- /**
- * Encode and write a varint. {@code value} is treated as
- * unsigned, so it won't be sign-extended if negative.
- */
- public void writeRawVarint32(int value) throws IOException {
- while (true) {
- if ((value & ~0x7F) == 0) {// 代表只有低 7 位有值, 因此只需 1 个字节即可完成编码
- writeRawByte(value);
- return;
- } else {
- writeRawByte((value & 0x7F) | 0x80);// 代表编码不止一个字节, value & 0x7f 只取低 7 位, 与 0x80 进行按位或 (|) 运算为了将最高位置位 1 , 代表后续字节也是改数字的一部分
- value>>>= 7;
- }
- }
- }
该方法对 int 类型的值进行 VarInt32 编码, 可以验证最多 5 个字节即可完成编码.
VarInt32 解码
理解了编码后, 解码就没什么可说的了. 就是从输入字节流中, 读取一个字节判断最高位, 将真实数据位拼接成最终的数字即可. Hadoop RPC 中使用了 Protoc Buffer 作为数据序列化框架. 其中, Hadoop 针对 writeDelimitedTo 方法实现了对 VarInt32 的解码. 源码如下:
- /**
- * Read a variable length integer in the same format that ProtoBufs encodes.
- * @param in the input stream to read from
- * @return the integer
- * @throws IOException if it is malformed or EOF.
- */
- public static int readRawVarint32(DataInput in) throws IOException {
- byte tmp = in.readByte();
- if (tmp>= 0) {// tmp>= 0 代表最高位是 0 , 否则 tmp <0 代表最高位是 1 , 需要继续往下读
- return tmp;
- }
- int result = tmp & 0x7f;
- if ((tmp = in.readByte())>= 0) {
- result |= tmp <<7;
- } else {
- result |= (tmp & 0x7f) << 7;
- if ((tmp = in.readByte())>= 0) {
- result |= tmp <<14;
- } else {
- result |= (tmp & 0x7f) << 14;
- if ((tmp = in.readByte())>= 0) {
- result |= tmp <<21;
- } else {
- result |= (tmp & 0x7f) << 21;
- result |= (tmp = in.readByte()) << 28;
- if (tmp < 0) {// 我们说 VarInt32 最多 5 个字节表示, 当程序执行到这里, tmp < 0, 说明, 编码格式有问题 // Discard upper 32 bits.
- for (int i = 0; i < 5; i++) {
- if (in.readByte()>= 0) {
- return result;
- }
- }
- throw new IOException("Malformed varint");
- }
- }
- }
- }
- return result;
- }
在 Hadoop 源码中并没有使用循环去解码, 而是使用多个 if 条件判断, 根据 tmp 的正负号来判断最高位是否是 1. 如果读取的该数字用了 5 个字节编码, 当读到了第 5 个字节, 理论上 tmp 应该大于 0 . 但是如果 tmp 小于 0 , 说明编码格式有问题. 在 Hadoop 源码中程序会继续往下读, 最多再向下读 5 个字节且丢掉最高位仍然 < 0 的字节. 如果在该过程某个字节最高位为 0 , 便停止读取直接返回. 这个处理逻辑在其他框架源码中也有出现.
看完 Hadoop 的源码, 我们在看看 Protoc Buffer 自己提供的解析源码:
- /**
- * Like {@link #readRawVarint32(InputStream)}, but expects that the caller
- * has already read one byte. This allows the caller to determine if EOF
- * has been reached before attempting to read.
- */
- public static int readRawVarint32(
- final int firstByte, final InputStream input) throws IOException {
- if ((firstByte & 0x80) == 0) {
- return firstByte;
- }
- int result = firstByte & 0x7f;
- int offset = 7;
- for (; offset < 32; offset += 7) {
- final int b = input.read();
- if (b == -1) {
- throw InvalidProtocolBufferException.truncatedMessage();
- }
- result |= (b & 0x7f) << offset;
- if ((b & 0x80) == 0) {
- return result;
- }
- }
- // Keep reading up to 64 bits.
- for (; offset < 64; offset += 7) {
- final int b = input.read();
- if (b == -1) {
- throw InvalidProtocolBufferException.truncatedMessage();
- }
- if ((b & 0x80) == 0) {
- return result;
- }
- }
- throw InvalidProtocolBufferException.malformedVarint();
- }
可以看到 Protoc Buffer 自己提供的解码方式与 Hadoop 是一样的, 包括遇到错误的编码时候的异常处理方式也是一样的.
小结
本篇文章主要介绍了 VarInt32 编解码, VarInt32 表示一个整型数字最少用 1 个字节, 最多用 5 个字节. 所以在传输数字大部分都比较小的场景下适合使用. 当然, 我们也可以用 VarInt64 来表示长整型的数字. 在介绍 VarInt32 的同时我们也看到了 ProtoBuf 和 Hadoop 这样的框架在传输数据的优化上不放过任何一个细节, 值得我们学习.
公众号「渡码」
来源: https://www.cnblogs.com/duma/p/11111427.html