本文由騰訊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）