作者：carmark

本文將在proto3語(yǔ)法背景下，介紹protobuf的編碼原理，并結(jié)合業(yè)務(wù)場(chǎng)景探討部分優(yōu)化技巧。

1、Protobuf編碼原理介紹

序列化算法被廣泛應(yīng)用于各種通信協(xié)議中，本文對(duì)序列化算法進(jìn)行狹義定義：

將某個(gè)struct或class的內(nèi)存數(shù)據(jù)和通信數(shù)據(jù)鏈路上的字節(jié)流進(jìn)行互相轉(zhuǎn)化的算法。

基于這個(gè)定義序列化算法具有兩個(gè)行為：

1、序列化：內(nèi)存數(shù)據(jù)->通信鏈路字節(jié)流

2、反序列化：通信鏈路字節(jié)流->內(nèi)存數(shù)據(jù)

常用的序列化算法有：json、xml、protobuf 等，將這些算法進(jìn)行歸納不難發(fā)現(xiàn)這些算法主要是對(duì)三種基本類型（原子性、不可被拆分）和三種復(fù)合類型（由基本類型和其他符合類型構(gòu)成）進(jìn)行序列化和反序列化。

1、基本類型：定點(diǎn)數(shù)值類型、浮點(diǎn)數(shù)值類型、字符串類型

2、復(fù)合類型：結(jié)構(gòu)體類型、數(shù)組類型、map類型

protobuf也是對(duì)這些類型進(jìn)行序列化的，下文將在proto3語(yǔ)法的背景下介紹protobuf對(duì)不同類型的編碼原理。

1.1 基本類型

1.1.1 定點(diǎn)數(shù)值類型

proto3語(yǔ)法中：int32、int64、uint32、uint64、sint32、sint64、fixed32、fixed64、sfixed32、sfixed64、bool、enum屬于定點(diǎn)數(shù)值類型。對(duì)于int32、int64、uint32、uint64會(huì)直接使用varint編碼，bool類型會(huì)直接使用一個(gè)字節(jié)存儲(chǔ)，enum可以看成是一個(gè)int32類型。對(duì)于sint32、sint64類型會(huì)先進(jìn)行zigzag編碼，再進(jìn)行varint編碼，對(duì)于fixed32、fixed64、sfixed32、sfixed64類型會(huì)使用定長(zhǎng)的四個(gè)或八個(gè)字節(jié)進(jìn)行存儲(chǔ)。

關(guān)于varint編碼和zigzag編碼的細(xì)節(jié)可以參考文檔
https://protobuf.dev/programming-guides/encoding/ ，本文直接給出兩種編碼的性質(zhì)：

varint編碼：變長(zhǎng)編碼，對(duì)于小正整數(shù)有較好的壓縮效果，對(duì)于大整數(shù)或負(fù)數(shù)編碼后字節(jié)流長(zhǎng)度會(huì)變大。

zigzag編碼：定長(zhǎng)編碼，將小正整數(shù)和小負(fù)整數(shù)轉(zhuǎn)換到小正整數(shù)再進(jìn)行varint編碼，對(duì)絕對(duì)值較小的整數(shù)有良好的壓縮效果。

1.1.2 浮點(diǎn)數(shù)值類型

proto3語(yǔ)法中：float和double屬于浮點(diǎn)數(shù)據(jù)類型，使用定長(zhǎng)的四個(gè)字節(jié)或八個(gè)字節(jié)存儲(chǔ)，數(shù)據(jù)直接用IEEE754標(biāo)準(zhǔn)表示。

1.1.3 字符串類型

proto3語(yǔ)法中：string、bytes屬于字符串類型，字符串類型序列化后的字節(jié)流為其原始內(nèi)容本身。這兩種類型的不同之處在于string內(nèi)的字節(jié)流必須是utf8編碼，bytes沒(méi)有這種要求。

1.2 復(fù)合類型

1.2.1 結(jié)構(gòu)體類型

proto3語(yǔ)法中使用message定義結(jié)構(gòu)體類型，結(jié)構(gòu)體類型有多個(gè)不同tagid構(gòu)成的字段，字段可以是基本類型或復(fù)合類型，甚至可以是這個(gè)結(jié)構(gòu)體類型本身。結(jié)構(gòu)體每個(gè)字段底層都使用這種格式進(jìn)行存儲(chǔ)，需要注意的是typeid、length、data三部分長(zhǎng)度會(huì)根據(jù)實(shí)際情況發(fā)生改變。

typeid    length   data
+--------+--------+--------+
|xxxxxxxx|xxxxxxxx|xxxxxxxx|
+--------+--------+--------+

typeid用于存儲(chǔ)結(jié)構(gòu)體字段編號(hào)（tagNum）和字段類型（tagType），tagNum為字段“=”后的數(shù)字，tagNum也使用varint進(jìn)行編碼，因此如果“=”后的數(shù)字很大，則可能導(dǎo)致tagNum編碼變大，tagid占用多個(gè)字節(jié)。而tagType則指明數(shù)據(jù)類型，這部分固定占用三個(gè)bit。

|tagNum        |tagType|
+----------------------+
|x  x  x  x  x  x  x  x|
+----------------------+
 7              2     0 

下表記錄了不同字段類型對(duì)應(yīng)的tagType值：

tagType類型0int32、int64、uint32、uint64、sint32、sint64、bool、enum1fixed64、sfixed64、double2string、bytes、結(jié)構(gòu)體類型、數(shù)組類型、map類型3棄用4棄用5fixed32、sfixed32、float

length部分表示data部分的長(zhǎng)度，同樣使用變長(zhǎng)varint編碼，需要注意的是如果字段類型是數(shù)值類型，則length部分不會(huì)出序列化后的字節(jié)流中。

data部分為原始數(shù)據(jù)，可以是基本類型和復(fù)合類型序列化后的字節(jié)流，算法通常遞歸的對(duì)這些字段進(jìn)行處理。

1.2.1 數(shù)組類型

proto3語(yǔ)法中使用repeated為前綴的字段即為數(shù)組類型，也就是說(shuō)repeated關(guān)鍵字是用來(lái)修飾結(jié)構(gòu)體類型的字段的。

如果repeated修飾的是定點(diǎn)數(shù)值類型或浮點(diǎn)數(shù)值類型，在proto3語(yǔ)法下會(huì)默認(rèn)按照下圖方式將這些數(shù)值排列在一起，length部分記錄data1~dataN所有數(shù)值的字節(jié)數(shù)之和。

typeid    length   data1    data2       dataN
+--------+--------+--------+--------+~~+--------+
|xxxxxxxx|xxxxxxxx|xxxxxxxx|xxxxxxxx|  |xxxxxxxx|
+--------+--------+--------+--------+~~+--------+

如果修飾的是其他類型則會(huì)按照以下方式組織這些數(shù)據(jù)（其中field1為數(shù)組類型），需要注意的是屬于同一個(gè)數(shù)組的不同元素中間可能有其他字段的元素插入。

typeid1   length1  data1     typeid2  length2  data2     typeid1  length3  data3    
+--------+--------+--------++--------+--------+--------++--------+--------+--------+
|xxxxxxxx|xxxxxxxx|xxxxxxxx||xxxxxxxx|xxxxxxxx|xxxxxxxx||xxxxxxxx|xxxxxxxx|xxxxxxxx|
+--------+--------+--------++--------+--------+--------++--------+--------+--------+
|   field1     ||   field2     ||   field1     |

1.2.2 map類型

proto3語(yǔ)法中map也是一種修飾符，修飾結(jié)構(gòu)體類型的字段。map類型的key必須為定點(diǎn)數(shù)值類型或string類型，map的底層存儲(chǔ)key-value鍵值對(duì)，采用和數(shù)組類型一樣的存儲(chǔ)方法，數(shù)組中每個(gè)元素是kv鍵值對(duì)。以下數(shù)據(jù)定義中，message A和message B有完全相同的底層存儲(chǔ)結(jié)構(gòu)。

message A{
 map<int32,float> mp = 1;
}

message KV{
 int32 K = 1;
 float V = 2;
}

message B{
 repeated KV mp = 1;
}

1.3 類型默認(rèn)值

如果類型為默認(rèn)值，則該字段tagid+length+data不會(huì)出現(xiàn)在序列化后的字節(jié)流中。

類型默認(rèn)值int32、int64、uint32、uint64、fixed32、fixed64、sfixed32、sfixed64、float、double0enum0對(duì)應(yīng)的枚舉值boolfalsestring""bytes空字節(jié)流結(jié)構(gòu)體類型null (對(duì)應(yīng)字段的指針為空)數(shù)組類型空數(shù)組map類型空map

需要注意的是如果某個(gè)字段是結(jié)構(gòu)體類型，該字段對(duì)應(yīng)的結(jié)構(gòu)體中的所有元素均為默認(rèn)值，這種情況下該字段的data部分會(huì)被省略，只保留tagid和length部分，當(dāng)然length部分值為0。如果字段的指針為空，則該字段不會(huì)有任何內(nèi)容出現(xiàn)在序列化后的字節(jié)流中。

1.4 舉例

enum C {
  C1 = 0;
  C2 = 1;
}

message B {
  int32 X = 1;
  sint32 Y = 2;
  C Z = 3;
}

message A {
  repeated float F1 = 1;
  map<string, B> F2 = 20;
}

message A 內(nèi)存中的數(shù)值:
F1:1.2  F1:2.3  F2:{key:"123"  value:{X:1  Y:-1  Z:C2}}

message A 序列化后的字節(jié)流:
0XA,0X8,0X9A,0X99,0X99,0X3F,0X33,0X33,0X13,0X40,0XA2,0X1,0XD,0XA,0X3,0X31,0X32,0X33,0X12,0X6,0X8,0X1,0X10,0X1,0X18,0X1
|---------------------A.F1---------------------|-------------------------------A.F2----------------------------------|
       |-------1.2---------|---------2.3------|A.F2.tagid|+----------|----"123"----|-------------|1|------|-1|----|C2|

需要注意的是message A 的 F2字段的tagNum是20，而tagType值是2，按照上文討論的編碼原理A.F2.tagid編碼如下：

+----------------------+ +----------------------+
|0  0  0  0  0  0  0  1| |1  0  1  0  0  0  1  0|
+----------------------+ +----------------------+
 15                                      2     0 
|typeNum                                |tagType|
|varint編碼，編碼前：00010100，值為20     |值為2  |

從這個(gè)例子還可以看出，protobuf序列化之后低地址字節(jié)在前，高地址字節(jié)在后。

1.5 QA～

Q: protobuf既然有了int32 為什么還要用sint32 和 fixed32 ？

A: int32使用varint編碼，對(duì)于小正數(shù)有較好的壓縮效果，對(duì)于大整數(shù)和負(fù)數(shù)會(huì)導(dǎo)致額外的字節(jié)開(kāi)銷。因此引入fixed32，該類型不會(huì)對(duì)數(shù)值進(jìn)行任何編碼，對(duì)大于2^28-1的整數(shù)比int32占用更少的字節(jié)。而對(duì)于負(fù)數(shù)使用zigzag編碼，這樣絕對(duì)值較小的負(fù)數(shù)都能被有效壓縮。

Q: 為什么數(shù)組類型每個(gè)元素都要用tagid+length+data這種格式進(jìn)行存儲(chǔ)？

A: 其實(shí)我也覺(jué)得這點(diǎn)設(shè)計(jì)不太合理，為什么不設(shè)計(jì)成tagid+元素個(gè)數(shù)+{length+data}...這種格式呢？

Q: map類型是不是盡量別用？

A: 如果你的業(yè)務(wù)對(duì)序列化后的字節(jié)流長(zhǎng)度有要求，能不用就別用吧。

Q: 為什么數(shù)組類型和map類型的元素中間可能插入其他字節(jié)流？

A: 不清楚，不過(guò)這倒是解釋了第二個(gè)問(wèn)題。

Q: 既然通信雙方都使用.proto文件約定了字段的類型，為什么tagid字段還要包含type信息？

A: 不清楚，不過(guò)可能和不同版本協(xié)議的兼容性有關(guān)。

2、 優(yōu)化技巧探討

通過(guò)分析protobuf的編碼原理，可以發(fā)現(xiàn)如果對(duì)序列化后的字節(jié)流長(zhǎng)度有要求，無(wú)腦地定義數(shù)據(jù)結(jié)構(gòu)是很不理智的，本節(jié)將討論部分優(yōu)化技巧。

2.1 類型優(yōu)化

上文中多次提到過(guò)varint編碼和zigzag編碼，不同的數(shù)據(jù)類型使用不同的編碼方法，那應(yīng)該如何選擇呢？首先給出正整數(shù)經(jīng)過(guò)varint編碼后占用字節(jié)數(shù)的算式，其中x表示待計(jì)算的正整數(shù)，y表示占用字節(jié)數(shù)。

對(duì)于zigzag編碼需要明確一點(diǎn)：zigzag編碼需要和varint編碼一起使用。zigzag編碼可以看作將正負(fù)交替的數(shù)值序列映射至正整數(shù)序列，之后再由varint對(duì)正整數(shù)進(jìn)行編碼。

原始數(shù)值: 0,-1,1,-2,2,-3,3,-4,4...

映射數(shù)值: 0,1,2,3,4,5,6,7,8...

現(xiàn)在考慮使用varint編碼后4字節(jié)能表示的最大無(wú)符號(hào)整數(shù)，根據(jù)算式：令y=4，易得x最大值為2^28^-1。因此可以得到結(jié)論，對(duì)于小于2^28^-1的無(wú)符號(hào)整數(shù)推薦使用varint編碼，對(duì)于大于2^28^-1的無(wú)符號(hào)整數(shù)使用varint編碼會(huì)導(dǎo)致編碼后字節(jié)數(shù)變長(zhǎng)。

然后討論使用zigzag+varint編碼后4字節(jié)能表示的正負(fù)數(shù)范圍，結(jié)合以上分析不難得出4字節(jié)能表示的正負(fù)數(shù)范圍是[-2^14^ , 2^14^-1]。因此對(duì)于在此范圍內(nèi)的數(shù)值，經(jīng)過(guò)zigzag+varint編號(hào)后的字節(jié)流長(zhǎng)度小于四個(gè)字節(jié)。

基于以上分析下表給出不同數(shù)值范圍的定點(diǎn)數(shù)值推薦類型（以下推薦類型都是基于最小字節(jié)流長(zhǎng)度為目標(biāo)，編解碼過(guò)程會(huì)存在一定cpu消耗）

數(shù)據(jù)范圍推薦類型[-2^63^,-2^31^)sfixed64[-2^31^,-2^28^)sfixed32[-2^28^,-2^14^)sint64[-2^14^,2^14^-1]sint32(2^14^-1,2^28^-1]uint32或int32(2^28^-1,2^32^-1]fixed32(2^32^-1,2^56^-1]uint64或int64(2^56^-1,2^64^-1]fixed64

2.2 結(jié)構(gòu)優(yōu)化

從對(duì)protobuf編碼原理的介紹那部分可以看出，protobuf因?yàn)榭紤]兼容性原因，存儲(chǔ)了很多tagid、length這些記錄結(jié)構(gòu)信息的字段。在實(shí)際應(yīng)用場(chǎng)景中如果數(shù)據(jù)的結(jié)構(gòu)較為緊密（這個(gè)詞暫時(shí)還無(wú)較為精確的定義），多個(gè)字段都有相同的結(jié)構(gòu)是否能去掉記錄結(jié)構(gòu)信息的字段，只保留內(nèi)容信息的字段，從而減少數(shù)據(jù)長(zhǎng)度呢？本文提供一種優(yōu)化思路。

優(yōu)化前：

message A{
 int32 x = 1;
 int32 y = 2;
}

message B{
 int32 z = 1;
}

message C{
 repeated A as = 1;
 B b = 2 ;
}

message C 序列化后字節(jié)流：
0XA,0X4,0X8,0X1,0X10,0X2,0XA,0X4,0X8,0X1,0X10,0X2,0XA,0X4,0X8,0X1,0X10,0X2,0X12,0X2,0X8,0X3

message C 內(nèi)存中數(shù)值：
as:{x:1 y:2} as:{x:1 y:2} as:{x:1 y:2} b:{z:3}

優(yōu)化后：

message C{
 repeated int32 xs = 1;
 repeated int32 ys = 2;
 int32 z = 3;
}

message C 序列化后字節(jié)流：
0XA,0X3,0X1,0X1,0X1,0X12,0X3,0X2,0X2,0X2,0X18,0X3

message C 內(nèi)存中數(shù)值：
xs:1  xs:1  xs:1  ys:2  ys:2  ys:2  z:3

前后對(duì)比可看在傳輸相同的信息情況下字節(jié)流長(zhǎng)度減半，這主要因?yàn)樯釛壛撕芏鄑agID字段。當(dāng)然這種優(yōu)化思路是基于數(shù)據(jù)的結(jié)構(gòu)較為緊密這一假設(shè)：優(yōu)化前大部分message A中的X、Y字段均非默認(rèn)值，這樣就可以省略大量結(jié)構(gòu)信息，從而減少字節(jié)流長(zhǎng)度。實(shí)際應(yīng)用中可以大量應(yīng)用這種技巧，來(lái)優(yōu)化編解碼性能。

2.3 數(shù)據(jù)優(yōu)化

除了結(jié)構(gòu)信息是否有其他信息可以被省略掉呢？當(dāng)然，除了結(jié)構(gòu)信息還有數(shù)據(jù)信息，即為data字段記錄的值。根據(jù)信息論的基本觀點(diǎn)，如果一組數(shù)據(jù)分布范圍很廣，每個(gè)數(shù)據(jù)點(diǎn)現(xiàn)頻率幾乎相同則需要用較多bit對(duì)這組數(shù)據(jù)進(jìn)行編碼。如果這組數(shù)據(jù)分布較為單一，某些數(shù)據(jù)點(diǎn)出現(xiàn)頻率較高，這種數(shù)據(jù)分布能較好地使用變長(zhǎng)編碼表示。

推廣到實(shí)際業(yè)務(wù)場(chǎng)景中，如果發(fā)現(xiàn)某組數(shù)據(jù)的某些字段滿足某些分布特征，比如：時(shí)間戳、交易ID，這種分布范圍較小，重復(fù)性較高的數(shù)據(jù)，最簡(jiǎn)單的方法是：使用一個(gè)int64存儲(chǔ)這組數(shù)據(jù)的最小值，然后對(duì)于這組數(shù)據(jù)中的其他元素分別計(jì)算和這個(gè)最小值的差值。因?yàn)閿?shù)據(jù)分布范圍較小，因此差值也不會(huì)很大，從而減少整體編碼長(zhǎng)度。

優(yōu)化前：

message A { repeated int64 timestamps = 1; }

message A 序列化后字節(jié)流：
0XA,0X1E,0XCA,0XDE,0XA5,0XAF,0XAD,0X31,0XCE,0XDE,0XA5,0XAF,0XAD,0X31,0XD2,0XDE,0XA5,0XAF,0XAD,0X31,0XD6,0XDE,0XA5,0XAF,0XAD,0X31,0XDA,0XDE,0XA5,0XAF,0XAD,0X31,

message A 內(nèi)存中數(shù)值：
timestamps:1695805960010  timestamps:1695805960014  timestamps:1695805960018  timestamps:1695805960022  timestamps:1695805960026

優(yōu)化后：

message A {
  int64 base = 1;
  repeated int64 timestamps = 2;
}

message A 序列化后字節(jié)流：
0X8,0XCA,0XDE,0XA5,0XAF,0XAD,0X31,0X12,0X5,0X0,0X4,0X8,0XC,0X10,

message A 內(nèi)存中數(shù)值：
base:1695805960010 timestamps:0 timestamps:4 timestamps:8 timestamps:12 timestamps:16

由于差值通常較小，在此基礎(chǔ)上可以繼續(xù)進(jìn)行bit優(yōu)化，比如最大差值是15則最多用4個(gè)bit表示一個(gè)差值即可，這樣一個(gè)字節(jié)就可以記錄兩個(gè)差值的信息，從而進(jìn)一步壓縮序列化字節(jié)流。

3、 未來(lái)工作展望

基于上述分析和實(shí)踐，不難發(fā)現(xiàn)protobuf進(jìn)行序列化的過(guò)程中，需要儲(chǔ)存結(jié)構(gòu)信息和數(shù)據(jù)信息。對(duì)于結(jié)構(gòu)緊密的數(shù)據(jù)，protobuf會(huì)導(dǎo)致大量bit用于表征結(jié)構(gòu)信息。而如果數(shù)據(jù)信息中存在某些先驗(yàn)數(shù)據(jù)分布或規(guī)律，protobuf也會(huì)存儲(chǔ)較多冗余信息。那么是否有算法能較好地結(jié)合待序列化數(shù)據(jù)的特性，進(jìn)而防止信息冗余呢？這個(gè)可能需要進(jìn)一步的研究...