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呢？我們看一下：
| 類型 | 含義 | 使用場景 |
|---|---|---|
| 0 | 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 | groups (deprecated) |
| 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)
舉個例子：
| 符號整數 | 編碼結果 |
|---|---|
| 0 | 0 |
| -1 | 1 |
| 1 | 2 |
| -2 | 3 |
| 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的基本編碼規則和實現已經講完了。聽起來是不是很奇妙？
本文已收錄於 //www.flydean.com/03-protobuf-encoding/
最通俗的解讀，最深刻的乾貨，最簡潔的教程，眾多你不知道的小技巧等你來發現！
歡迎關注我的公眾號:「程式那些事」,懂技術，更懂你！
