Protobuf编码原理
⭐⭐⭐⭐⭐⭐
Github主页👉https://github.com/A-BigTree
笔记链接👉https://github.com/A-BigTree/Code_Learning
⭐⭐⭐⭐⭐⭐
Spring专栏👉https://blog.csdn.net/weixin_53580595/category_12279588.html
SpringMVC专栏👉https://blog.csdn.net/weixin_53580595/category_12281721.html
Mybatis专栏👉https://blog.csdn.net/weixin_53580595/category_12279566.html
如果可以，麻烦各位看官顺手点个star~😊
如果文章对你有所帮助，可以点赞👍收藏⭐支持一下博主~😆
1 前言
Protobuf的编码是基于变种的Base128的，在学习Protobuf编码或者是Base128之前，先来了解下Base64编码。
2 Base 64
2.1 技术背景
当我们在计算机之间传输数据时，数据本质上是一串字节流。TCP 协议可以保证被发送的字节流正确地达到目的地（至少在出错时有一定的纠错机制），所以本文不讨论因网络因素造成的数据损坏。
但数据到达目标机器之后，由于不同机器采用的字符集不同等原因，我们并不能保证目标机器能够正确地“理解”字节流。Base 64 最初被设计用于在邮件中嵌入文件（作为 MIME 的一部分）：它可以将任何形式的字节流编码为“安全”的字节流。
**何为“安全“的字节？**先来看看 Base 64 是如何工作的。
2.2 工作原理
假设这里有四个字节，代表要传输的数据：
10100010 00001001 11000010 11010011
首先将这字节流按每 6 个 bit 为一组进行分组，剩下少于 6 bits 的低位补 0：
101000 100000 100111 000010 110100 110000
然后在每一组 6 bits 的高位补两个 0：
00101000 00100000 00100111 00000010 00110100 00110000
Base 64编码对照表如下图：
对照Base 64的编码对照表，字节流可以用ognC0w来表示。
另外： Base64 编码是按照 6 bits 为一组进行编码，每 3 个字节的原始数据要用 4 个字节来储存，编码后的长度要为 4 的整数倍，不足 4 字节的部分要使用 pad 补齐，所以最终的编码结果为ognC0w==；
任意的字节流均可以使用 Base 64 进行编码，编码之后所有字节均可以用数字、字母和 + / = 号进行表示，这些都是可以被正常显示的 ascii 字符，即“安全”的字节。绝大部分的计算机和操作系统都对 ascii 有着良好的支持，保证了编码之后的字节流能被正确地复制、传播、解析。
3 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。
4 Base 128 Varints
4.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 有两个需要注意的细节：
- 只能对一部分数据结构进行编码，不适用于所有字节流（当然你可以把任意字节流转换为 string，但不是所有语言都支持这个 trick）。否则无法识别哪部分是无效的 bits；
- 编码后的字节可以不存在于 ASCII 表中，因为和 Base 64 使用场景不同，不用考虑是否能正常打印；
4.2 例子
对于Base 128 Varints 编码后的每个字节，低 7 位用于储存数据，最高位用来标识当前字节是否是当前整数的最后一个字节，称为最高有效位（most significant bit, 简称msb）。msb 为 1 时，代表着后面还有数据；msb 为 0 时代表着当前字节是当前整数的最后一个字节。
下图是编码后的整数300： 第一个字节的 msb 为 1，最后一个字节的 msb 为 0。
10101100 00000010
要将这两个字节解码成整数，需要三个步骤：
- 去除 msb；
- 将字节流逆序（msb 为 0 的字节储存原始数据的高位部分，小端模式）；
- 最后拼接所有的 bits;
- 10101100 00000010
- 0101100 0000010
- 0000010 0101100
- 00000100101100
- 300(integer)
4.3 对整数进行编码
具体过程是：
- 将数据按每 7 bits 一组拆分；
- 逆序每一个组；
- 添加 msb；
- 124856(integer)
- 111 1001111 0111000
- 0000111 1001111 0111000
- 0111000 1001111 0000111
- 10111000 11001111 00000111
需要注意的是： 无论是编码还是解码，逆序字节流这一步在机器处理中实际是不存在的，机器采用小端模式处理数据，此处逆序仅是为了符合人的阅读习惯而写出。
5 Protobuf编码
Protobuf支持数据类型及其编码方式：
| ID | Name | Used For |
|---|---|---|
| 0 | VARINT | int32, int64, uint32, uint64, sint32, sint64, bool, enum |
| 1 | I64 | fixed64, sfixed64, double |
| 2 | LEN | string, bytes, embedded messages, packed repeated fields |
| 3 | SGROUP | group start (deprecated) |
| 4 | EGROUP | group end (deprecated) |
| 5 | I32 | fixed32, sfixed32, float |
5.1 有符号整型
按照刚才变长编码的思想，-2147483646使用的比特位应该比-2要少。然而我们知道在计算机世界中负数使用补码表示的，也就是说最高位（最左侧的比特位）一定是1，假设我们使用64位来表示数字，那么如果我们依然用补码来表示数字的话那么无论这个负数有多大还是多小都需要占据10个字节的空间。
为什么是10个字节呢？
不要忘了varint每个字节的有效负荷是7个比特，那么对于需要64位表示的数字来说就需要64/7向上取整也就是10个字节来表示。这显然不能满足我们对数字变长存储的要求。
该怎么解决这个问题呢？
既然无符号数字可以方便的进行变长编码，那么我们将有符号数字映射称为无符号数字不就可以了，这就是所谓的ZigZag编码。
ZigZag编码就像这样：
原始信息 编码后
0 0
-1 1
1 2
-2 3
2 4
-3 5
3 6
... ...
2147483647 4294967294
-2147483648 4294967295
ZigZag编码规则：
(n << 1) ^ (n >> 31) # for 32-bit signed integer
(n << 1) ^ (n >> 63) # for 64-bit signed integer
5.2 定长数据
Protobuf中定长数据直接采用小端模式储存，不作转换。
5.3 字符串
以字符串"testing"为例，编码为16进制后结果如下：
07 74 65 73 74 69 6e 67
- 第一个字节表示字符串采用 UTF-8 编码后字节流的长度（bytes），采用 Base 128 Varints 进行编码；
- 后面字符串用UTF-8编码后的字节流；
5.4 字段类型和字段名称
字段类型有限可以用简单的3个比特位来表示（一共六种编码方式），有意思的是字段名称该怎么表示？
既然通信双方需要协议，那么某个字段其实是Client和Server都知道的，它们唯一不知道的就是“哪些值属于哪些字段”。为解决这个问题，我们给每个字段都进行编号，如protobuf消息定义：
syntax = "proto3";
message SearchRequest {
string query = 1;
int32 page_number = 2;
int32 result_per_page = 3;
}
这里的等号并不是用于赋值，而是给每一个字段指定一个 ID，称为 field number。消息内同一层次字段的 field number 必须各不相同。
一个键值key，在 protobuf 源码中被称为 tag，tag 由 field number 和 type 两部分组成：
- field number 左移 3 bits；
- 在最低 3 bits 写入 wire type（字段类型）；
源码中生成的 tag 是 uint64，代表着 field number 可以使用 61 个 bit 吗？
并非如此！事实上： tag 的长度不能超过 32 bits，意味着 field number 的最大取值为 2 29 − 1 ( 536870911 ) 2^{29}-1 (536870911) 229−1(536870911)。
而且在这个范围内，有一些数是不能被使用的：
-
0：protobuf 规定 field number 必须为正整数； -
19000~19999： protobuf 仅供内部使用的保留位；
理解了生成 tag 的规则之后，不难得出以下结论：
- field number 不必从1开始，可以从合法范围内的任意数字开始；
- 不同字段间的field number不必连续，只要合法且不同即可；
但是实际上： 大多数人分配 field number 还是会从 1 开始，因为 tag 最终要经过 Base 128 Varints 编码，较小的 field number 有助于压缩空间，field number 为 1 到 15 的 tag 最终仅需占用一个字节。
当你的 message 有超过 15 个字段时，Google 也不建议你将 1 到 15 立马用完。如果你的业务日后有新增字段的可能，并且新增的字段使用比较频繁，你应该在 1 到 15 内预留一部分供新增的字段使用。
当你修改的 proto 文件需要注意：
- field number 一旦被分配了就不应该被更改，除非你能保证所有的接收方都能更新到最新的 proto 文件；
- 由于 tag 中不携带 field name 信息，更改 field name 并不会改变消息的结构；
发送方认为的 apple 到接受方可能会被识别成 pear。双方把字段读取成哪个名字完全由双方自己的 proto 文件决定，只要字段的 wire type 和 field number 相同即可。由于 tag 中携带的类型是 wire type，不是语言中具体的某个数据结构，而同一个 wire type 可以被解码成多种数据结构，具体解码成哪一种是根据接收方自己的 proto 文件定义的。
5.5 嵌套消息
嵌套消息的实现并不复杂。在 protobuf 的 wire type 中，wire type2 （length-delimited）不仅支持 string，也支持 embedded messages。
对于嵌套消息： 首先你要将被嵌套的消息进行编码成字节流，然后你就可以像处理 UTF-8 编码的字符串一样处理这些字节流：在字节流前面加入使用 Base 128 Varints 编码的长度即可。
一个字段可以理解为K-V格式，嵌套消息可以理解为K-(K-(K-…V))
5.6 重复消息编码规则
假设接收方的 proto3 中定义了某个字段（假设 field number=1），当接收方从字节流中读取到多个 field number=1 的字段时，会执行 merge 操作。
merge 的规则如下：
- 如果字段为不可分割的类型，则直接覆盖；
- 如果字段为 repeated，则 append 到已有字段；
- 如果字段为嵌套消息，则递归执行 merge；
如果字段的 field number 相同但是结构不同，则出现 error。
5.7 字段顺序
编码结果与字段顺序无关
Proto 文件中定义字段的顺序与最终编码结果的字段顺序无关，两者有可能相同也可能不同。
当消息被编码时，Protobuf 无法保证消息的顺序，消息的顺序可能随着版本或者不同的实现而变化。任何 Protobuf 的实现都应该保证字段以任意顺序编码的结果都能被读取。
以下是使用Protobuf时的一些常识：
- 序列化后的消息字段顺序是不稳定的；
- 对同一段字节流进行解码，不同实现或版本的 Protobuf 解码得到的结果不一定完全相同（bytes 层面），只能保证相同版本相同实现的 Protobuf 对同一段字节流多次解码得到的结果相同；
- 假设有一条消息foo，有几种关系可能是不成立的；
相等消息编码后结果可能不同
假设有两条逻辑上相等的消息，但是序列化之后的内容（bytes 层面）不相同，原因有很多种可能。文章来源：https://www.toymoban.com/news/detail-535772.html
比如下面这些原因：文章来源地址https://www.toymoban.com/news/detail-535772.html
- 其中一条消息可能使用了较老版本的 protobuf，不能处理某些类型的字段，设为 unknwon；
- 使用了不同语言实现的 Protobuf，并且以不同的顺序编码字段；
- 消息中的字段使用了不稳定的算法进行序列化；
- 某条消息中有 bytes 类型的字段，用于储存另一条消息使用 Protobuf 序列化的结果，而这个 bytes 使用了不同的 Protobuf 进行序列化；
- 使用了新版本的 Protobuf，序列化实现不同；
- 消息字段顺序不同；
到了这里，关于【RPC】—Protobuf编码原理的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
