本文由腾讯PCG后台开发工程师的SG4YK分享，进行了修订和和少量改动。
1、引言
近日学习了 Protobuf 的编码实现技术原理，借此机会，正好总结一下并整理成文。
接上篇《由浅入深，从根上理解Protobuf的编解码原理》，本篇将从Base64再到Base128编码，带你一起从底层来理解Protobuf的数据编码原理。
本文结构总体与 Protobuf 官方文档相似，不少内容也来自官方文档，并在官方文档的基础上添加作者理解的内容（确保不那么枯燥），如有出入请以官方文档为准。
学习交流：
（本文已同步发布于：http://www.52im.net/thread-4093-1-1.html）
2、系列文章
本文是系列文章中的第 4 篇，本系列总目录如下：
3、写在前面
在上篇《由浅入深，从根上理解Protobuf的编解码原理》中，我们已经由浅入深地探讨了Protobuf的编解码技术实现实现，但实际上在初学者看来，Protobuf的编码原理到底源自哪里又去向何方，看起来还是有点蒙，我们或许可以从Protobuf与经典字符编码技术的关系上能更好的理解这些。
好了，不卖关子了。。。
实际上，Protobuf 的编码是基于变种的 Base128的。
在学习 Protobuf 编码或是 Base128 之前，我们先来了解下 Base64 编码。
4、什么是Base 64
4.1 技术背景
当我们在计算机之间传输数据时，数据本质上是一串字节流。
TCP 协议可以保证被发送的字节流正确地达到目的地（至少在出错时有一定的纠错机制），所以本文不讨论因网络因素造成的数据损坏。
但数据到达目标机器之后，由于不同机器采用的字符集不同等原因，我们并不能保证目标机器能够正确地“理解”字节流。
Base 64 最初被设计用于在邮件中嵌入文件（作为 MIME 的一部分）：它可以将任何形式的字节流编码为“安全”的字节流。
何为“安全“的字节？先来看看 Base 64 是如何工作的。
4.2 工作原理
假设这里有四个字节，代表你要传输的二进制数据：
首先将这字节流按每 6 个 bit 为一组进行分组，剩下少于 6 bits 的低位补 0：
然后在每一组 6 bits 的高位补两个 0：
下面这张图是 Base 64 的编码对照表：
对照 Base 64 的编码对照表，字节流可以用ognC0w来表示。
另外：Base64 编码是按照 6 bits 为一组进行编码，每 3 个字节的原始数据要用 4 个字节来储存，编码后的长度要为 4 的整数倍，不足 4 字节的部分要使用 pad 补齐，所以最终的编码结果为ognC0w==。
任意的字节流均可以使用 Base 64 进行编码，编码之后所有字节均可以用数字、字母和 + / = 号进行表示，这些都是可以被正常显示的 ascii 字符，即“安全”的字节。绝大部分的计算机和操作系统都对 ascii 有着良好的支持，保证了编码之后的字节流能被正确地复制、传播、解析。
注：下文关于字节顺序内容均基于机器采用小端模式的前提进行讨论（关于大小端字节序，可以阅读《面试必考，史上最通俗大小端字节序详解》）。
5、什么是Base 128
Base 64 存在的问题就是：编码后的每一个字节的最高两位总是 0，在不考虑 pad 的情况下，有效 bit 只占 bit 总数的 75%，造成大量的空间浪费。
是否可以进一步提高信息密度呢？
意识到这一点，你就很自然能想象出 Base 128 的大致实现思路了：将字节流按 7 bits 进行分组，然后低位补 0。
但问题来了：Base 64 实际上用了 64+1 个 ascii 字符，按照这个思路 Base 128 需要使用 128+1 个 ascii 个字符，但是 ascii 字符一共只有 128 个。
另外：即使不考虑 pad，ascii 中包含了一些不可以正常打印的控制字符，编码之后的字符还可能包含会被不同操作系统转换的换行符号（10 和 13）。因此，Base 64 至今依然没有被 Base 128 替代。
Base 64 的规则因为上述限制不能完美地扩展到 Base 128，所以现有基于 Base 64 扩展而来的编码方式大部分都属于变种：如 LEB128（Little-Endian Base 128）、 Base 85 （Ascii 85），以及本文的主角：Base 128 Varints。
6、什么是Base 128 Varints
6.1 基本概念
Base 128 Varints 是 Google 开发的序列化库 Protocol Buffers 所用的编码方式。
以下为 Protobuf 官方文档中对于 Varints 的解释：
Varints are a method of serializing integers using one or more bytes. Smaller numbers take a smaller number of bytes.
即：使用一个或多个字节对整数进行序列化，小的数字占用更少的字节。
简单来说，Base 128 Varints 编码原理就是尽量只储存整数的有效位，高位的 0 尽可能抛弃。
Base 128 Varints 有两个需要注意的细节：
- 1）只能对一部分数据结构进行编码，不适用于所有字节流（当然你可以把任意字节流转换为 string，但不是所有语言都支持这个 trick）。否则无法识别哪部分是无效的 bits；
- 2）编码后的字节可以不存在于 Ascii 表中，因为和 Base 64 使用场景不同，不用考虑是否能正常打印。
下面以例子进行说明 Base 128 Varints 的编码实现。
6.2 举个例子
对于Base 128 Varints 编码后的每个字节，低 7 位用于储存数据，最高位用来标识当前字节是否是当前整数的最后一个字节，称为最高有效位（most significant bit, 简称msb）。msb 为 1 时，代表着后面还有数据；msb 为 0 时代表着当前字节是当前整数的最后一个字节。
下面我们用实际的例子来更好的理解它。
下图是编码后的整数1：1 只需要用一个字节就能表示完全，所以 msb 为 0。
对于需要多个字节来储存的数据，如 300 (0b100101100)，有效位数为 9，编码后需要两个字节储存。
下图是编码后的整数300：第一个字节的 msb 为 1，最后一个字节的 msb 为 0。
要将这两个字节解码成整数，需要三个步骤：
- 1）去除 msb；
- 2）将字节流逆序（msb 为 0 的字节储存原始数据的高位部分，小端模式）；
- 3）最后拼接所有的 bits。
6.3 对整数进行编码的例子
下面这个例子展示如何将使用 Base 128 Varints 对整数进行编码。
具体过程是：
- 1）将数据按每 7 bits 一组拆分；
- 2）逆序每一个组；
- 3）添加 msb。
需要注意的是：无论是编码还是解码，逆序字节流这一步在机器处理中实际是不存在的，机器采用小端模式处理数据，此处逆序仅是为了符合人的阅读习惯而写出。
下面展示 Go 版本的 protobuf 中关于 Base 128 Varints 的实现：
// google.golang.org/protobuf@v1.25.0/encoding/protowire/wire.go
// AppendVarint appends v to b as a varint-encoded uint64.
funcAppendVarint(b []byte, v uint64) []byte{
switch{
casev < 1<<7:
b = append(b, byte(v))
casev < 1<<14:
b = append(b,
byte((v>>0)&0x7f|0x80),
byte(v>>7))
casev < 1<<21:
b = append(b,
byte((v>>0)&0x7f|0x80),
byte((v>>7)&0x7f|0x80),
byte(v>>14))
casev < 1<<28:
b = append(b,
byte((v>>0)&0x7f|0x80),
byte((v>>7)&0x7f|0x80),
byte((v>>14)&0x7f|0x80),
byte(v>>21))
casev < 1<<35:
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))
casev < 1<<42:
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))
casev < 1<<49:
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))
casev < 1<<56:
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))
casev < 1<<63:
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))
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)
}
returnb
}
从源码中可以看出：protobuf 的 varints 最多可以编码 8 字节的数据，这是因为绝大部分的现代计算机最高支持处理 64 位的整型。
7、Protobuf支持的数据类型
7.1 概述
Protobuf 不仅支持整数类型，下图列出 protobuf 支持的数据类型（wire type）。
在上一小节中展示的编码与解码的例子中的“整数”并不是我们一般理解的整数（编程语言中的 int32，uint32 等），而是对应着上图中的 Varint。
当实际编程中使用 protobuf 进行编码时经过了两步处理：
- 1）将编程语言的数据结构转化为 wire type；
- 2）根据不同的 wire type 使用对应的方法编码（前文所提到的 Base 128 Varints 用来编码 varint 类型的数据，其他 wire type 则使用其他编码方式）。
{obj} -> {wire type} -> {encoded bytestream}
uint32-> wire type0 -> varint
int32-> wire type0 -> varint
bool-> wire type0 -> varint
string-> wire type2 -> length-delimited
...
不同语言中 wire type 实际上也可能采用了语言中的某种类型来储存 wire type 的数据。例如 Go 中使用了 uint64 来储存 wire type 0。
一般来说，大多数语言中的无符号整型被转换为 varints 之后，有效位上的内容并没有改变。
下面说明部分其他数据类型到 wire type 的转换规则。
7.2 有符号整型
Protobuf中有符号整型采用 ZigZag 编码来将 sint32 和 sint64 转换为 wire type 0。
下面是 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
下图展示了部分 ZigZag 编码的例子：
如果不先采用 ZigZag 编码成 wire type，负值 sint64 直接使用 Base 128 Varints 编码之后的长度始终为ceil(64/7)=10bytes，浪费大量空间。
使用 ZigZag 编码后，绝对值较小的负数的长度能够被显著压缩：
对于 -234(sint32) 这个例子，编码成 varints 之前采用 ZigZag 编码，比直接编码成 varints 少用了 60%的空间。
当然，ZigZag 编码也不是完美的方法。当你尝试把 sint32 或 sint64 范围内所有的整数都编码成 varints 字节流，使用 ZigZag 已经不能压缩字节数量了。
ZigZag 虽然能压缩部分负数的空间，但同时正数变得需要更多的空间来储存。
因此，建议在业务场景允许的场景下尽量用无符号整型，有助于进一步压缩编码后的空间。
7.3 定长数据（64-bit）
Protobuf中定长数据直接采用小端模式储存，不作转换。
7.4 字符串
以字符串"testing"为例：
Protobuf编码后的 value 分为两部分：
- 1）蓝色：表示字符串采用 UTF-8 编码后字节流的长度（bytes），采用 Base 128 Varints 进行编码；
- 2）白色：字符串用 UTF-8 编码后的字节流。
8、Protobuf的消息结构
Protobuf 采用 proto3 作为 DSL 来描述其支持的消息结构。
就像下面这样：
syntax = "proto3";
message SearchRequest {
stringquery = 1;
int32page_number = 2;
int32result_per_page = 3;
}
设想一下这样的场景：数据的发送方在业务迭代之后需要在消息内携带更多的字段，而有的接收方并没有更新自己的 proto 文件。要保持较好的兼容性，接收方分辨出哪些字段是自己可以识别的，哪些是不能识别的新增字段。要做到这一点，发送方在编码消息时还必须附带每个字段的 key，客户端读取到未知的 key 时，可以直接跳过对应的 value。
proto3 中每一个字段后面都有一个 = x，比如：
stringquery = 1;
这里的等号并不是用于赋值，而是给每一个字段指定一个 ID，称为 field number。消息内同一层次字段的 field number 必须各不相同。
上面所说的 key，在 protobuf 源码中被称为 tag。
tag 由 field number 和 type 两部分组成：
- 1）field number 左移 3 bits；
- 2）在最低 3 bits 写入 wire type。
下面展示一个生成 tag 例子：
Go 版本 Protobuf 中生成 tag 的源码：
// google.golang.org/protobuf@v1.25.0/encoding/protowire/wire.go
// EncodeTag encodes the field Number and wire Type into its unified form.
funcEncodeTag(num Number, typ Type) uint64{
returnuint64(num)<<3 | uint64(typ&7)
}
源码中生成的 tag 是 uint64，代表着 field number 可以使用 61 个 bit 吗？
并非如此！
事实上：tag 的长度不能超过 32 bits，意味着 field number 的最大取值为 2^29-1 (536870911)。
而且在这个范围内，有一些数是不能被使用的：
- 1）0 ：protobuf 规定 field number 必须为正整数；
- 2）19000 到 19999： protobuf 仅供内部使用的保留位。
理解了生成 tag 的规则之后，不难得出以下结论：
- 1）field number 不必从 1 开始，可以从合法范围内的任意数字开始；
- 2）不同字段间的 field number 不必连续，只要合法且不同即可。
但是实际上：大多数人分配 field number 还是会从 1 开始，因为 tag 最终要经过 Base 128 Varints 编码，较小的 field number 有助于压缩空间，field number 为 1 到 15 的 tag 最终仅需占用一个字节。
当你的 message 有超过 15 个字段时，Google 也不建议你将 1 到 15 立马用完。如果你的业务日后有新增字段的可能，并且新增的字段使用比较频繁，你应该在 1 到 15 内预留一部分供新增的字段使用。
当你修改的 proto 文件需要注意：
- 1）field number 一旦被分配了就不应该被更改，除非你能保证所有的接收方都能更新到最新的 proto 文件；
- 2）由于 tag 中不携带 field name 信息，更改 field name 并不会改变消息的结构。
发送方认为的 apple 到接受方可能会被识别成 pear。双方把字段读取成哪个名字完全由双方自己的 proto 文件决定，只要字段的 wire type 和 field number 相同即可。
由于 tag 中携带的类型是 wire type，不是语言中具体的某个数据结构，而同一个 wire type 可以被解码成多种数据结构，具体解码成哪一种是根据接收方自己的 proto 文件定义的。
修改 proto 文件中的类型，有可能导致错误：
最后用一个比前面复杂一点的例子来结束本节内容：
9、Protobuf中的嵌套消息
嵌套消息的实现并不复杂。
在上一节展示的 protobuf 的 wire type 中，wire type2 （length-delimited）不仅支持 string，也支持 embedded messages。
对于嵌套消息：首先你要将被嵌套的消息进行编码成字节流，然后你就可以像处理 UTF-8 编码的字符串一样处理这些字节流：在字节流前面加入使用 Base 128 Varints 编码的长度即可。
10、Protobuf中重复消息的编码规则
假设接收方的 proto3 中定义了某个字段（假设 field number=1），当接收方从字节流中读取到多个 field number=1 的字段时，会执行 merge 操作。
merge 的规则如下：
- 1）如果字段为不可分割的类型，则直接覆盖；
- 2）如果字段为 repeated，则 append 到已有字段；
- 3）如果字段为嵌套消息，则递归执行 merge；
如果字段的 field number 相同但是结构不同，则出现 error。
以下为 Go 版本 Protobuf 中 merge 的部分：
// google.golang.org/protobuf@v1.25.0/proto/merge.go
// Merge merges src into dst, which must be a message with the same descriptor.
//
// Populated scalar fields in src are copied to dst, while populated
// singular messages in src are merged into dst by recursively calling Merge.
// The elements of every list field in src is appended to the corresponded
// list fields in dst. The entries of every map field in src is copied into
// the corresponding map field in dst, possibly replacing existing entries.
// The unknown fields of src are appended to the unknown fields of dst.
//
// It is semantically equivalent to unmarshaling the encoded form of src
// into dst with the UnmarshalOptions.Merge option specified.
funcMerge(dst, src Message) {
// TODO: Should nil src be treated as semantically equivalent to a
// untyped, read-only, empty message? What about a nil dst?
dstMsg, srcMsg := dst.ProtoReflect(), src.ProtoReflect()
ifdstMsg.Descriptor() != srcMsg.Descriptor() {
ifgot, want := dstMsg.Descriptor().FullName(), srcMsg.Descriptor().FullName(); got != want {
panic(fmt.Sprintf("descriptor mismatch: %v != %v", got, want))
}
panic("descriptor mismatch")
}
mergeOptions{}.mergeMessage(dstMsg, srcMsg)
}
func(o mergeOptions) mergeMessage(dst, src protoreflect.Message) {
methods := protoMethods(dst)
ifmethods != nil&& methods.Merge != nil{
in := protoiface.MergeInput{
Destination: dst,
Source: src,
}
out := methods.Merge(in)
ifout.Flags&protoiface.MergeComplete != 0 {
return
}
}
if!dst.IsValid() {
panic(fmt.Sprintf("cannot merge into invalid %v message", dst.Descriptor().FullName()))
}
src.Range(func(fd protoreflect.FieldDescriptor, v protoreflect.Value) bool{
switch{
casefd.IsList():
o.mergeList(dst.Mutable(fd).List(), v.List(), fd)
casefd.IsMap():
o.mergeMap(dst.Mutable(fd).Map(), v.Map(), fd.MapValue())
casefd.Message() != nil:
o.mergeMessage(dst.Mutable(fd).Message(), v.Message())
casefd.Kind() == protoreflect.BytesKind:
dst.Set(fd, o.cloneBytes(v))
default:
dst.Set(fd, v)
}
returntrue
})
iflen(src.GetUnknown()) > 0 {
dst.SetUnknown(append(dst.GetUnknown(), src.GetUnknown()...))
}
}
11、Protobuf的字段顺序
11.1 编码结果与字段顺序无关
Proto 文件中定义字段的顺序与最终编码结果的字段顺序无关，两者有可能相同也可能不同。
当消息被编码时，Protobuf 无法保证消息的顺序，消息的顺序可能随着版本或者不同的实现而变化。任何 Protobuf 的实现都应该保证字段以任意顺序编码的结果都能被读取。
以下是使用Protobuf时的一些常识：
- 1）序列化后的消息字段顺序是不稳定的；
- 2）对同一段字节流进行解码，不同实现或版本的 Protobuf 解码得到的结果不一定完全相同（bytes 层面），只能保证相同版本相同实现的 Protobuf 对同一段字节流多次解码得到的结果相同；
- 3）假设有一条消息foo，有几种关系可能是不成立的（下方会接着详细说明）。
针对上述第 3）点，这几种关系可能是不成立的：
foo.SerializeAsString() == foo.SerializeAsString()
Hash(foo.SerializeAsString()) == Hash(foo.SerializeAsString())
CRC(foo.SerializeAsString()) == CRC(foo.SerializeAsString())
FingerPrint(foo.SerializeAsString()) == FingerPrint(foo.SerializeAsString())
11.2 相等消息编码后结果可能不同
假设有两条逻辑上相等的消息，但是序列化之后的内容（bytes 层面）不相同，原因有很多种可能。
比如下面这些原因：
- 1）其中一条消息可能使用了较老版本的 protobuf，不能处理某些类型的字段，设为 unknwon；
- 2）使用了不同语言实现的 Protobuf，并且以不同的顺序编码字段；
- 3）消息中的字段使用了不稳定的算法进行序列化；
- 4）某条消息中有 bytes 类型的字段，用于储存另一条消息使用 Protobuf 序列化的结果，而这个 bytes 使用了不同的 Protobuf 进行序列化；
- 5）使用了新版本的 Protobuf，序列化实现不同；
- 6）消息字段顺序不同。
12、参考资料
[1] Protobuf官方编码资料
[2] Protobuf官方手册
[3] Why do we use Base64？
[4] The Base16, Base32, and Base64 Data Encodings
[5]Protobuf从入门到精通，一篇就够！
[6]如何选择即时通讯应用的数据传输格式
[7]强列建议将Protobuf作为你的即时通讯应用数据传输格式
[8]APP与后台通信数据格式的演进：从文本协议到二进制协议
[9]面试必考，史上最通俗大小端字节序详解
[10]移动端IM开发需要面对的技术问题（含通信协议选择）
[11]简述移动端IM开发的那些坑：架构设计、通信协议和客户端
[12]理论联系实际：一套典型的IM通信协议设计详解
[13]58到家实时消息系统的协议设计等技术实践分享
（本文已同步发布于：http://www.52im.net/thread-4093-1-1.html）