浅谈Protobuf编码

见贤思齐

作者：SG4YK，腾讯PCG后台开发工程师近日简单学习了Protobuf中的编码实现，总结并整理成文。本文结构总体与Protobuf官方文档相似，不少内容也来自官方文档，并在官方文档的基础上添加作者理解的内容，如有出入请以官方文档为准。作者水平有限，难免有疏漏之处，欢迎指正并分享您的意见。0x00Beforeyoustart简单来说，Protobuf的编码是基于变种的Base128。在学习Protobuf编码或是Base128之前，先来了解下Base64编码。0x01Base64当我们在计算机之间传输数据时，数据本质上是一串字节流。TCP协议可以保证被发送的字节流正确地达到目的地（至少在出错时有一定的纠错机制），所以本文不讨论因网络因素造成的数据损坏。但数据到达目标机器之后，由于不同机器采用的字符集不同等原因，我们并不能保证目标机器能够正确地“理解”字节流。Base64最初被设计是用于在邮件中嵌入文件（作为MIME的一部分）。它可以将任何形式的字节流编码为“安全”的字节流。何为“安全“的字节？先来看看Base64是如何工作的。假设这里有四个字节,代表你要传输的二进制数据。首先将这个字节流按每6个bit为一组进行分组,剩下少于6bits的低位补0。然后在每一组6bits的高位补两个0。对照Base64table，字节流可以用ognC0w来表示。另外，Base64编码是按照6bits为一组进行编码，每3个字节的原始数据要用4个字节来储存，编码后的长度要为4的整数倍，不足4字节的部分要使用pad补齐，所以最终的编码结果为ognC0w==。任意的字节流均可以使用Base64进行编码，编码之后所有字节均可以用数字、字母和+/=号进行表示，这些都是可以被正常显示的ascii字符，即“安全”的字节。绝大部分的计算机和操作系统都对ascii有着良好的支持，保证了编码之后的字节流能被正确地复制、传播、解析。注：下文关于字节顺序内容均基于机器采用小端模式的前提进行讨论。0x02Base128?Base64存在的问题就是，编码后的每一个字节的最高两位总是0，在不考虑pad的情况下，有效bit只占bit总数的75%，造成大量的空间浪费。是否可以进一步提高信息密度呢？意识到这一点，你就很自然能想象出Base128的大致实现思路了，将字节流按7bits进行分组，然后低位补0。但问题来了，Base64实际上用了64+1个ascii字符，按照这个思路Base128需要使用128+1个ascii个字符，但是ascii字符一共只有128个。另外，即使不考虑pad，ascii中包含了一些不可以正常打印的控制字符，编码之后的字符还可能包含会被不同操作系统转换的换行符号（10和13）。因此，Base64至今依然没有被Base128替代。Base64的规则因为上述限制不能完美地扩展到Base128，所以现有基于Base64扩展而来的编码方式大部分都属于变种。如LEB128（Little-EndianBase128），Base85（Ascii85），以及本文的主角：Base128Varints。注：下文关于字节顺序内容均基于机器采用小端模式的前提进行讨论。0x03Base128VarintsBase128Varints是Google开发的序列化库ProtocolBuffers所用的编码方式。以下为Protobuf官方文档中对于Varints的解释：Varintsareamethodofserializingintegersusingoneormorebytes.Smallernumberstakeasmallernumberofbytes.使用一个或多个字节对整数进行序列化。小的数字占用更少的字节。简单来说，就是尽量只储存整数的有效位，高位的0尽可能抛弃。有两个需要注意的细节：Base128Varints只能对一部分数据结构进行编码，不适用于所有字节流（当然你可以把任意字节流转换为string，但不是所有语言都支持这个trick）。否则无法识别哪部分是无效的bits。Base128Varints编码后的字节可以不存在于Ascii表中，因为和Base64使用场景不同，不用考虑是否能正常打印。下面以例子进行说明Base128Varints的编码实现。对于编码后的每个字节，低7位用于储存数据，最高位用来标识当前字节是否是当前整数的最后一个字节，称为最高有效位（mostsignificantbit,msb）。msb为1时，代表着后面还有数据；msb为0时代表着当前字节是当前整数的最后一个字节。举个例子，下面是编码后的整数1。1只需要用一个字节就能表示完全，所以msb为0。对于需要多个字节来储存的数据，如300(0b100101100)，有效位数为9，编码后需要两个字节储存。下面是编码后的整数300。第一个字节的msb为1，最后一个字节的msb为0。要将这两个字节解码成整数,需要三个步骤：去除msb第二步，将字节流逆序（msb为0的字节储存原始数据的高位部分，小端模式）最后拼接所有的bits。下面一个例子展示如何将使用Base128Varints对整数进行编码。将数据按每7bits一组拆分逆序每一个组添加msb需要注意的是，无论是编码还是解码，逆序字节流这一步在机器处理中实际是不存在的，机器采用小端模式处理数据，此处逆序仅是为了符合人的阅读习惯而写出。下面展示Go版本的protobuf中关于Base128Varints的实现：// google.golang.org/protobuf@v1.25.0/encoding/protowire/wire.go// AppendVarint appends v to b as a varint-encoded uint64.func AppendVarint(b []byte, v uint64) []byte { switch { case v >0)&0x7f|0x80),   byte(v>>7)) case v >0)&0x7f|0x80),   byte((v>>7)&0x7f|0x80),   byte(v>>14)) case v >0)&0x7f|0x80),   byte((v>>7)&0x7f|0x80),   byte((v>>14)&0x7f|0x80),   byte(v>>21)) case v >0)&0x7f|0x80),   byte((v>>7)&0x7f|0x80),   byte((v>>14)&0x7f|0x80),   byte((v>>21)&0x7f|0x80),   byte(v>>28)) case v >0)&0x7f|0x80),   byte((v>>7)&0x7f|0x80),   byte((v>>14)&0x7f|0x80),   byte((v>>21)&0x7f|0x80),   byte((v>>28)&0x7f|0x80),   byte(v>>35)) case v >0)&0x7f|0x80),   byte((v>>7)&0x7f|0x80),   byte((v>>14)&0x7f|0x80),   byte((v>>21)&0x7f|0x80),   byte((v>>28)&0x7f|0x80),   byte((v>>35)&0x7f|0x80),   byte(v>>42)) case v >0)&0x7f|0x80),   byte((v>>7)&0x7f|0x80),   byte((v>>14)&0x7f|0x80),   byte((v>>21)&0x7f|0x80),   byte((v>>28)&0x7f|0x80),   byte((v>>35)&0x7f|0x80),   byte((v>>42)&0x7f|0x80),   byte(v>>49)) case v >0)&0x7f|0x80),   byte((v>>7)&0x7f|0x80),   byte((v>>14)&0x7f|0x80),   byte((v>>21)&0x7f|0x80),   byte((v>>28)&0x7f|0x80),   byte((v>>35)&0x7f|0x80),   byte((v>>42)&0x7f|0x80),   byte((v>>49)&0x7f|0x80),   byte(v>>56)) default:  b = append(b,   byte((v>>0)&0x7f|0x80),   byte((v>>7)&0x7f|0x80),   byte((v>>14)&0x7f|0x80),   byte((v>>21)&0x7f|0x80),   byte((v>>28)&0x7f|0x80),   byte((v>>35)&0x7f|0x80),   byte((v>>42)&0x7f|0x80),   byte((v>>49)&0x7f|0x80),   byte((v>>56)&0x7f|0x80),   1) } return b}从源码中可以看出，protobuf的varints最多可以编码8字节的数据，这是因为绝大部分的现代计算机最高支持处理64位的整型。0x04其他类型Protobuf不仅支持整数类型，下图列出protobuf支持的数据类型（wiretype）。在上一小节中展示的编码与解码的例子中的“整数”并不是我们一般理解的整数（编程语言中的int32，uint32等），而是对应着上图中的Varint。当实际使用编程语言使用protobuf进行编码时经过了两步处理：将编程语言的数据结构转化为wiretype。根据不同的wiretype使用对应的方法编码。前文所提到的Base128Varints用来编码varint类型的数据，其他wiretype则使用其他编码方式。    {obj}  -> {wire type} -> {encoded byte stream}    uint32 -> wire type 0 -> varint    int32  -> wire type 0 -> varint    bool   -> wire type 0 -> varint    string -> wire type 2 -> length-delimited    ...不同语言中wiretype实际上也可能采用了语言中的某种类型来储存wiretype的数据。例如，Go中使用了uint64来储存wiretype0。一般来说，大多数语言中的无符号整型被转换为varints之后，有效位上的内容并没有改变。下面说明部分其他数据类型到wiretype的转换规则：有符号整型采用ZigZag编码来将sint32和sint64转换为wiretype0。下面是ZigZag编码的规则（注意是算术位移）：    (n << 1) ^ (n >> 31)  // for 32-bit signed integer    (n << 1) ^ (n >> 63)  // for 64-bit signed integer或者从数学意义来理解：    n * 2       // when n >= 0    -n * 2 - 1  // when n  0 {  dst.SetUnknown(append(dst.GetUnknown(), src.GetUnknown()...)) }}0x08字段顺序Proto文件中定义字段的顺序与最终编码结果的字段顺序无关，两者有可能相同也可能不同。当消息被编码时，Protobuf无法保证消息的顺序，消息的顺序可能随着版本或者不同的实现而变化。任何Protobuf的实现都应该保证字段以任意顺序编码的结果都能被读取。序列化后的消息字段顺序是不稳定的。对同一段字节流进行解码，不同实现或版本的Protobuf解码得到的结果不一定完全相同（bytes层面）。只能保证相同版本相同实现的Protobuf对同一段字节流多次解码得到的结果相同。假设有一条消息foo，以下关系可能不成立：foo.SerializeAsString() == foo.SerializeAsString()Hash(foo.SerializeAsString()) == Hash(foo.SerializeAsString())CRC(foo.SerializeAsString()) == CRC(foo.SerializeAsString())FingerPrint(foo.SerializeAsString()) == FingerPrint(foo.SerializeAsString())假设有两条逻辑上相等消息，但是序列化之后的内容（bytes层面）不相同，部分可能的原因有：其中一条消息可能使用了较老版本的protobuf，不能处理某些类型的字段，设为unknwon。+使用了不同语言实现的Protobuf，并且以不同的顺序编码字段。+消息中的字段使用了不稳定的算法进行序列化。+某条消息中有bytes类型的字段，用于储存另一条消息使用Protobuf序列化的结果，而这个bytes使用了不同的Protobuf进行序列化。+使用了新版本的Protobuf，序列化实现不同。+消息字段顺序不同。Referenceshttps://datatracker.ietf.org/doc/html/rfc4648https://developers.google.com/protocol-buffers/docs/encodinghttps://developers.google.com/protocol-buffers/docs/proto3https://stackoverflow.com/questions/3538021/why-do-we-use-base64最近其他文章：gRPC基础概念详解深入浅出Linux惊群：现象、原因和解决方案不吹不擂，一文揭秘鸿蒙操作系统最新视频好用专业的新款网页版视频剪辑工具