技術文章 » 【protobuf原始碼探祕】編碼、序列化

【protobuf原始碼探祕】編碼、序列化

2021-12-31 23:00:02

請新增圖片描述

文章目錄

為什麼要寫這篇？

早就想寫了，不過前面有redis原始碼學習的系列在，就一直拖著。
在我學protobuf的時候，在網上看到一個部落格，說的挺好，但是偏偏插了這麼一句：fixed 和 int 相比，fixed重時間、int重空間。所以如果對空間效能有要求的話就使用int… 吧啦吧啦的。

然後我還就真信了。然後還就把我畢設專案協定裡的int32全換成fixed32了，給我一頓操作猛如虎啊。

後來，由於前面學的不全面，我又去了protobuf的官網檢視官方檔案，就想著看看那個人說的是不是對的。好傢伙，翻來翻去，人家只是說，如果大數出現頻繁的業務，考慮使用fixed，並沒有說什麼哪個快哪個慢。。。

然後我整個人就懵了，要知道我的畢設裡可幾乎都是小數啊（8位元數以下），那到底他說的是對的還是錯的啊？？？

想來想去，還是看原始碼裡怎麼寫的吧。

編碼

編碼結構

在這裡插入圖片描述

這裡的 [Length] 是可選的，含義是針對不同型別的資料編碼結構可能會變成 Tag - Value 的形式，如果變成這樣的形式，沒有了 Length 我們該如何確定 Value 的邊界？

注意其中的 Start group 和 End group 兩種型別已被遺棄。

這樣：
在這裡插入圖片描述

對 sint32、sint64 又會有一些特別編碼（ZigTag 編碼）處理，相當於 Varint 這個編碼型別裡又存在兩種不同編碼。

現在來模擬一下，我們接收到了一串序列化的二進位制資料，我們先讀一個 Varints 編碼塊，進行 Varints 解碼，讀取最後 3 bit 得到 wire_type（由此可知是後面的 Value 採用的哪種編碼），隨後獲取到 field_number （由此可知是哪一個欄位）。依據 wire_type 來正確讀取後面的 Value。接著繼續讀取下一個欄位 field…

Varints 編碼

1、在每個位元組開頭的 bit 設定了 msb(most significant bit )，標識是否需要繼續讀取下一個位元組
2、儲存數位對應的二進位制二補數
3、二補數的低位排在前面

看個例子：

int32 val =  1;  // 設定一個 int32 的欄位的值 val = 1; 這時編碼的結果如下
原碼：0000 ... 0000 0001  // 1 的原碼錶示
二補數：0000 ... 0000 0001  // 1 的二補數表示
Varints 編碼：0#000 0001（0x01）  // 1 的 Varints 編碼，其中第一個位元組的 msb = 0

編碼過程：
數位 1 對應二補數 0000 … 0000 0001（規則 2），從末端開始取每 7 位一組並且反轉排序（規則 3），因為 0000 … 0000 0001 除了第一個取出的 7 位組（即原數列的後 7 位），剩下的均為 0。所以只需取第一個 7 位組，無需再取下一個 7 bit，那麼第一個 7 位組的 msb = 0。最終得到：

0 | 000 0001（0x01）

解碼過程：
數位 1 的 Varints 編碼中 msb = 0，所以只需要讀完第一個位元組無需再讀。去掉 msb 之後，剩下的 000 0001 就是二補數的逆序，但是這裡只有一個位元組，所以無需反轉，直接解釋二補數 000 0001，還原即為數位 1。

這裡編碼數位 1，Varints 只使用了 1 個位元組。而正常情況下 int32 將使用 4 個位元組儲存數位 1。

msb 實際上就起到了 Length 的作用，正因為有了 msb（Length），所以我們可以擺脫原來那種無論數位大小都必須分配四個位元組的窘境。通過 Varints 我們可以讓小的數位用更少的位元組表示。從而提高了空間利用和效率。

負數的 Varints 編碼情況

不多說，直接上例子：

int32 val = -1
原碼：1000 ... 0001  // 注意這裡是 8 個位元組
二補數：1111 ... 1111  // 注意這裡是 8 個位元組

再次複習 Varints 編碼：對二補數取 7 bit 一組，低位放在前面。
上述二補數 8 個位元組共 64 bit，可分 9 組（負數的二補數和正數不一樣）且這 9 組均為 1，這 9 組的 msb 均為 1，最後剩下一個 bit 的 1，用 0 補齊作為最後一組放在最後，最後得到 Varints 編碼：

1#1111111 ... 0#000 0001 （FF FF FF FF FF FF FF FF FF 01）

注意，因為負數必須在最高位（符號位）置 1，這一點意味著無論如何，負數都必須佔用所有位元組，所以它的二補數總是佔滿 8 個位元組。你沒法像正數那樣去掉多餘的高位（都是 0）。再加上 msb，最終 Varints 編碼的結果將固定在 10 個位元組。

這也就是說為什麼在 protoc 裡直接用 int 儲存負數不好。

ZigZag 編碼

儲存負數推薦 sint 族，在使用 sint 的時候，預設採用 ZigZag 編碼。

一張圖其實就明白了：
在這裡插入圖片描述

這裡的「對映」是以移位實現的。

bool

當 boolVal = false 時，其編碼結果為空。
這裡是 ProtoBuf 為了提高效率做的又一個小技巧：規定一個預設值機制，當讀出來的欄位為空的時候就設定欄位的值為預設值。而 bool 型別的預設值為 false。也就是說將 false 編碼然後傳遞（消耗一個位元組），不如直接不輸出任何編碼結果（空），終端解析時發現該欄位為空，它會按照規定設定其值為預設值（也就是 false）。如此，可進一步節省空間提高效率。

fixed族

Varints 編碼在一定範圍內是有高效的，超過某一個數位佔用位元組反而更多，效率更低。如果現在有場景是存在大量的大數位，那麼使用 Varints 就不太合適了。具體的，如果數值比 2^56 大的話，fixed64 這個型別比 uint64 高效，如果數值比 2^28 大的話，fixed32 這個型別比 uint32 高效。

example.set_fixed64val(1)
example.set_sfixed64val(-1)
example.set_doubleval(1.2)

// 編碼結果，總是 8 個位元組
09 # 01 00 00 00 00 00 00 00
11 # FF FF FF FF FF FF FF FF （沒有 ZigZag 編碼）
19 # 33 33 33 33 33 33 F3 3F

fixed32、sfixed32、float 與 64-bit 同理

不定長資料型別

string、bytes、EmbeddedMessage、repeated。Length-delimited 型別的編碼結構為 Tag - Length - Value：

syntax = "proto3";

// message 定義
message Example1 {
    string stringVal = 1;
    bytes bytesVal = 2;
}



Example1 example1;
example1.set_stringval("hello,world");
example1.set_bytesval("are you ok?");




0A 0B 68 65 6C 6C 6F 2C 77 6F 72 6C 64 
12 0B 61 72 65 20 79 6F 75 20 6F 6B 3F

repeat

原先的 repeated 欄位的編碼結構為 Tag-Length-Value-Tag-Length-Value-Tag-Length-Value…，因為這些 Tag 都是相同的（同一欄位），因此可以將這些欄位的 Value 打包，即將編碼結構變為 Tag-Length-Value-Value-Value…

syntax = "proto3";

// message 定義
message Example1 {
    repeated int32 repeatedInt32Val = 4;
    repeated string repeatedStringVal = 5;
}

example1.add_repeatedint32val(2);
example1.add_repeatedint32val(3);
example1.add_repeatedstringval("repeated1");
example1.add_repeatedstringval("repeated2");

22 02 02 03
2A 09 72 65 70 65 61 74 65 64 31 2A 09 72 65 70 65 61 74 65 64 32

repeatedInt32Val 欄位的編碼結果為：

22 | 02 02 03

22 即 00100010 -> wire_type = 2(Length-delimited), field_number = 4(repeatedInt32Val 欄位)，02 位元組長度為 2，則讀取兩個位元組，之後按照 Varints 解碼出數位 2 和 3。

repeated string 不進行預設 packed

  1. 因為int32採用的是varints編碼，省去了TLV中的 L，實際上是TV格式的，所以 repeated int32 是 TLVVV 格式的
  2. string採用的是 TLV 編碼，故 repeated string 採用的是TLVLVLV格式

巢狀欄位

上文沒有提及巢狀欄位，因為：

依據元資訊(即 .proto 檔案，使用 protoc 編譯時，.proto 檔案會被編譯成字串儲存在程式碼 xxx.pb.cc 中）可以區分該欄位是否是巢狀欄位。簡單來說，你是無法直接從 pb 二進位制資料直接解碼出資訊的，一定是需要有 .proto 檔案的配合。只是在程式碼層面， .proto 檔案早就在 protoc 的時候就已經以某種形式存在於 protobuf 生成的使用者端程式碼中，程式碼可以隨時拿到 .proto 檔案中表達的元資訊，例如一個欄位是否為巢狀欄位。

序列化與反序列化

文章標題寫的是原始碼探祕是吧。是得放點程式碼出來。

SerializeToString

當某個 Message 呼叫 SerializeToString 時，經過一層層呼叫最終會呼叫底層的關鍵編碼函數 WriteVarint32ToArray 或 WriteVarint64ToArray，整個過程如下圖所示：

在這裡插入圖片描述

inline uint8* CodedOutputStream::WriteVarint32ToArray(uint32 value, uint8* target) {
  // 0x80 -> 1000 0000
  // 大於 1000 0000 意味這進行 Varints 編碼時至少需要兩個位元組
  // 如果 value < 0x80，則只需要一個位元組，編碼結果和原值一樣，則沒有迴圈直接返回
  // 如果至少需要兩個位元組
  while (value >= 0x80) {
    // 如果還有後續位元組，則 value | 0x80 將 value 的最後位元組的最高 bit 位設定為 1，並取後七位
    *target = static_cast<uint8>(value | 0x80);
    // 處理完七位，後移，繼續處理下一個七位
    value >>= 7;
    // 指標加一，（陣列後移一位）   
    ++target;
  }
  // 跳出迴圈，則表示已無後續位元組，但還有最後一個位元組

  // 把最後一個位元組放入陣列
  *target = static_cast<uint8>(value);
  // 結束地址指向陣列最後一個元素的末尾
  return target + 1;
}

// Varint64 同理
inline uint8* CodedOutputStream::WriteVarint64ToArray(uint64 value,
                                                      uint8* target) {
  while (value >= 0x80) {
    *target = static_cast<uint8>(value | 0x80);
    value >>= 7;
    ++target;
  }
  *target = static_cast<uint8>(value);
  return target + 1;
}

關於 fixed 族的編碼

inline uint8* WireFormatLite::WriteFixed32ToArray(int field_number,
                                                  uint32 value, uint8* target) {
  // WriteTagToArray: Tag 依然是 Varint 編碼，與上一節 Varint 型別是一致的
  // WriteFixed32NoTagToArray：固定寫四個位元組即可
  target = WriteTagToArray(field_number, WIRETYPE_FIXED32, target);
  return WriteFixed32NoTagToArray(value, target);
}

inline uint8* WireFormatLite::WriteSFixed32NoTagToArray(int32 value,
                                                        uint8* target) {
  return io::CodedOutputStream::WriteLittleEndian32ToArray(
      static_cast<uint32>(value), target);
}

inline uint8* CodedOutputStream::WriteLittleEndian32ToArray(uint32 value,
                                                            uint8* target) {
#if defined(PROTOBUF_LITTLE_ENDIAN)
  memcpy(target, &value, sizeof(value));
#else
  target[0] = static_cast<uint8>(value);
  target[1] = static_cast<uint8>(value >>  8);
  target[2] = static_cast<uint8>(value >> 16);
  target[3] = static_cast<uint8>(value >> 24);
#endif
  return target + sizeof(value);
}

這個會快？不要看上面一個while就以為人家慢了。

Length delimited 欄位序列化

因為其編碼結構為 Tag - Length - Value，所以其欄位完整的序列化會稍微多出一些過程：
在這裡插入圖片描述

其序列化實現的幾個關鍵函數為：

ByteSizeLong：計算物件序列化所需要的空間大小，在記憶體中開闢相應大小的空間
WriteTagToArray：將 Tag 值寫入到之前開闢的記憶體中
WriteStringWithSizeToArray：將 Length + Value 值寫入到之前開闢的記憶體中