protocol buffer的高效編碼方式

簡介

protocol buffer這種優秀的編碼方式，究竟底層是怎麼工作的呢？為什麼它可以實作高效快速的資料傳輸呢？這一切都要從它的編碼方式說起。

定義一個簡單的message

我們知道protocol buffer的主體就是message,接下來我們從一個簡單的message出發，詳細講解protobuf中的編碼方式。

比如下面的一個非常簡單的消息對象：

message Student {
  optional int32 age = 1;
}
           

在上面的例子中，我們定義了一個Student消息對象，并給他定義了一個名叫age的字段,并給它設定一個值叫做22。然後使用protobuf将其進行序列化，這麼大的一個對象，對其序列化之後的位元組如下所示：

08 96 00
           

很簡單，使用三個位元組就可以表示一個messag對象，資料量非常小。

那麼這三個位元組到底表示什麼意思呢？一起來看看吧 。

Base 128 Varints

在解釋上面的三個位元組的含義之前，我們需要了解一個varints的概念。

什麼叫Varints呢？就是序列化整數的時候，占用的空間大小是不一樣的，小的整數占用的空間小，大的整數占用的空間大，這樣不用固定一個具體的長度，可以減少資料的長度，但是會帶來解析的複雜度。

那麼怎麼知道這個資料到底需要幾個byte呢？在protobuf中，每個byte的最高位是一個判斷位，如果這個位被置位1，則表示後面一個byte和該byte是一起的，表示同一個數，如果這個位被置位0，則表示後面一個byte和該byte沒有關系，資料到這個byte就結束了。

舉個例子，一個byte是8位，如果表示的是整數1，那麼可以用下面的byte來表示：

0000 0001
           

如果一個byte裝不下的整數，那麼就需要使用多個byte來進行連接配接操作，比如下面的資料表示的是300：

1010 1100 0000 0010
           

為什麼是300呢？首先看第一個byte，它的首位是1，表示後面還有一個byte。再看第二個byte，它的首位是0，表示到此就結束了。我們把判斷位去掉，變成下面的數字：

010 1100 000 0010
           

這時候還不能計算資料的值，因為在protobuf中，byte的位數是反過來的，是以我們需要把上面的兩個byte交換一下位置：

000 0010 010 1100 
           

也就是：

10 010 1100 
           

=256 + 32 + 8 + 4 = 300

消息體的結構

從message的定義可以知道，protobuf中的消息體的結構是key=value的形式，其中的key就是message中定義的字段的整數值1，2，3，4等。而value就是真正對其設定的值。

當一個消息被編碼之後，這些key和value會被連接配接在一起，組成一個byte stream。當要對其進行解析的時候，需要定位到key和value的具體長度，是以在key中需要包含兩部分，第一個部分就是字段在proto檔案中的值，第二個部分就是value部分占用的長度大小。

隻有通過這兩個部分的值結合起來，解析器才能夠正确的對字段進行解析。

key的這種格式，被稱為 wire types，有哪些 wire types呢？我們看一下：

類型	含義	使用場景
Varint	int32, int64, uint32, uint64, sint32, sint64, bool, enum
1	64-bit	fixed64, sfixed64, double
2	Length-delimited	string, bytes, embedded messages, packed repeated fields
3	Start group	groups (deprecated)
4	End group
5	32-bit	fixed32, sfixed32, float

可以看到除了3，4兩種類型之外，其他的類型可以分為三類，一類是固定長度的類型，如1，5，他們分别是64位和32位的數字。

第二類是0，表示Varint，這是一種可變類型，用來表示通用的數字類型，bool類型和枚舉類型。第三類2，表示長度區分的類型，這種類型通常用來表示字元串，位元組數字等。

所有的key都是一個varint類型，它的值是：

(field_number << 3) | wire_type

，也就是說key的最後三個位，用來存儲wire類型。

上面我們例子中的key的值是08，用二進制表示：

000 1000
           

最後三位是0，表示是一個Varint類型，将08右移三位，得到1，表示key表示的字段是1這個字段，也就是age。

然後我們看下剩下的部分96 00，換成二進制是：

96 00 = 1001 0110  0000 0000
           

根據Varint的定義，第一位表示的是連接配接位，表示第二個位元組的内容和第一個位元組的内容是一起的。對于Varint來說，需要将低位的位元組和高位的位元組進行交換，如下：

1001 0110  0000 0000 去掉最高位的1 ：
001 0110  0000 0000  交換低位位元組和高位位元組：
0000 0000  001 0110 
           

上面的值是

16 + 4 + 2 = 22

這樣我們就得到了值為1的key，對應的value是22。

符号整數

我們知道有兩種表示符号整數的方式，一種是标準的int類型：int32 和 int64，一種是帶符号的int類型：sint32 和 sint64。

這兩種類型的差別在于對應負整數的表示上。對于int32和int64來說，所有的負整數都是以十個位元組來表示的，是以占用的空間會比較大，不适合用來表示負整數。

如果使用sint32 和 sint64，那麼使用的編碼方式是ZigZag，對于負整數來說更加有效。

ZigZag将帶符号的整數和無符号的整數進行映射，對于每個n來說，将會使用下面的公式來編碼：

(n << 1) ^ (n >> 31)
           

對于sint64來說就是：

(n << 1) ^ (n >> 64)
           

舉個例子：

	編碼結果
-1
-2
2147483647	4294967294
-2147483648	4294967295

# 字元串

字元串的wire類型是2，說明它的值是一個varint編碼的長度。舉個例子：

message Student {
  optional string name = 2;
}

           

上我們給Student定義了第二個屬性name，假如給name指派 “testing” ，那麼得到的編碼是：

12 07 [74 65 73 74 69 6e 67]
           

中括号的編碼就是”testing”的UTF8表示。

0x12 可以這樣解析：

0x12
→ 0001 0010  (binary representation)
→ 00010 010  (regroup bits)
→ field_number = 2, wire_type = 2
           

0x12表示字段2的類型是2，後面跟着的07就表示後續byte位元組的長度了。

嵌套的消息

消息中可以嵌套消息，我們看一個例子：

message Teacher {
  optional Student s = 3;
}
           

假如我們把s的age字段設定為22，就和第一個例子一樣，那麼上面的編碼就是：

1a 03 08 96 00
           

可以看到後面的三個位元組和第一個例子是一樣的。前面兩個位元組的判斷方式和字元串是一值的，這樣就不再多講。

總結

好了，protobuf的基本編碼規則和實作已經講完了。聽起來是不是很奇妙？