protobuf编解码原理

​ 对性能和流量敏感，或者一些需要长连接的服务，都是自己再造一层应用层，而不是用http协议。自造应用层，绕不开的是用哪种编解码方式，而Protobuf就是其中一种高效的编解码协议。

1. 构造最简单的Protobuf编解码代码

​ 这里跳过编写.proto文件，直接借助jprotobuf这个项目生成对应的Java编解码代码，协议实体如下：

public class ProtobufMessage {
    @Protobuf(order = 2)
    private String name;
    @Protobuf(order = 1)
    private int age;
}

1.1 生成的encode代码

com.google.protobuf.ByteString f_2 = null;
if (!CodedConstant.isNull(t.getName())) {
    f_2 = com.google.protobuf.ByteString.copyFromUtf8(t.getName());
}
Integer f_1 = null;
if (!CodedConstant.isNull(t.getAge())) {
    f_1 = t.getAge();
}
if (f_2 != null) {
    output.writeBytes(2, f_2);
}
if (f_1 != null) {
    output.writeInt32(1, f_1.intValue());
}
output.flush();

直接看writeInt32(1, f_1.intValue())这行代码，里面的操作如下：

@Override
public void writeInt32(final int fieldNumber, final int value) throws IOException {
  writeTag(fieldNumber, WireFormat.WIRETYPE_VARINT);
  writeInt32NoTag(value);
}

首先是写入一个filedNumber，即我们指定的order 顺序，可以看作是key-value里的key，这也意味着pb是可以部分字段解码的（跨版本兼容性），同时，这个key里也指明了这个value的WireFormat类型WIRETYPE_VARINT，这个名词的具体意思下面会介绍。writeTag仅仅是把原始的 order << 3bit，然后 | 类型，只是左移三位，意味着类型满打满算也只有8种，按这个算法，name生成的tag是18，value生成的tag是8，记住这两个数字，在下面的decode是有用的。

static int makeTag(final int fieldNumber, final int wireType) {
  return (fieldNumber << TAG_TYPE_BITS) | wireType;
}

然后是写入具体的value，这个value的写入方式是无符号变长整形写入。

1.2 生成的decode代码

boolean done = false;
Codec codec = null;
while (!done) {
    int tag = input.readTag();
    if (tag == 0) {
        break;
    }
    if (tag == 18) {
        ret.setName(input.readString())
        ;
        continue;
    }
    if (tag == 8) {
        ret.setAge(input.readInt32())
        ;
        continue;
    }
    input.skipField(tag);
}

解码一目了然，先读取一个tag，然后根据tag值调用对应的decode方法，然后再写入实体。

2. protobuf高效编码原理

​ 上面已经把protobuf的编码原理概括完了，就是通过order里标识value类型，然后根据类型，encode/decode对应的字段。

2.1 字段类型WireFormat

类型	意义	使用范围
0	Varint	int32,int64,uint32,uint64,enum,bool
1	64-bit	fixed64,sfixed64,double
2	length-delimited	string,bytes

这三种类型，通常最常使用的是Varint，即变厂编码，下面会详细提到；而64-bit就是定长编码，简单粗暴，但是没有压缩，会占据比较大的带宽；最后一种是length-delimited，这个多用于字符串，上面的栗子中name字段就是用这种编码方式。

2.2 Varint变长编码

​ 1.1的栗子中，如果我们设value=150，那么编码后，这个字段就是:

0x08 96 01

08的意思通过下面这个运算，取得WrieFormat=0，order=1:

WrieFormat = 0x8 && 0b111 = 0;
order = 0x8 >> 3 = 1;	

去掉tag，然后我们要引入msb(most significant bit,即最高位)这个概念，什么叫msb呢？就是每个字节的最高位，如果最高位为1，表明这个字段的value还没读完。显然，96的最高位是1，继续往下读一个字节，而01最高位是0，表明已经到了这个字段的边界了。好了，让我们按这个方式去掉msb：

96 01 = 1001 0110 0000 0001
      =  000 0001  001 0110 (翻转成大端,并且去掉msb)
      = 128 + 16 + 4 + 2 (每一个1代表的权重)
      = 150

需要注意的是，protobuf里面是按小端方式存放多字节类型数据的。

​ 按照Varint变长编码方式，依然用1中的栗子，如果value = 1，正常编码是四个字节，但是用变长编码一个字节就可以搞定，压缩率75，极端情况下value = Integer.MAX_VALUE的话，编码后就变成了5个字节，反而比正常编码更大。当然，我们考虑一般情况下，我们的值并不会很大，所以采用Varint编码还是利大于弊的。但是上面我们仅仅考虑的是非负数的情况，一旦value = -1，那么按照这个编码方式，一样会编码出5个字节的长度。（事实上，所有负数都会编码出5个字节，具体原因想想负数的表示方式。）为了解决这种情况，就要引入ZigZag编码方式了。

2.3 ZigZag编码

ZiaZag将有符号的整形编码成无符号的整形，一定要记住这个无符号概念，方便下面理解。一个绝对值很小的数字(类似-1)可变长编码后也会很小。通过这种通过正负来回摆动的编码方式(ZigZag是蜿蜒的意思)，所以，-1被编码成1,1编码成2,-2编码成3。如下：

编码前有符号数	编码后
0	1
-1	1
1	2
-2	3
214	428
-214	427

负数是 abs(x) * 2 - 1
正数是 x * 2
通过以下这个更高效的位移方式实现：

(n << 1) ^ (n >> 31)

左边的部分是乘以2，

右边部分，如果是非负数的话，异或0，还是本身。
负数的话，异或全1，即是每一位翻转。

还原方式如下：

(n >>> 1) ^ -(n & 1)

左边表示除以2得到中间值nl

右边部分，如果是原值是非负数，那么这个数n就是偶数，n & 1等于0，那么就等于异或0，最后还原的值就是nl。
负数的话，n是个偶数，所以n & 1 = 1，-1的二进制表示全1，异或翻转每一位。

3.总结

Protobuf通过Varint和ZigZag算法压缩数据节省传输带宽，借助预生成encode和decode代码提高性能。

参考资料

• Encoding|Protocol Buffer
• protobuf的编码方式