IM通訊協(xié)議專題學(xué)習(xí)(三)：由淺入深，從根上理解Protobuf的編解碼原理
本文由碼農(nóng)的荒島求生陸小風(fēng)分享，為了提升閱讀體驗(yàn)，進(jìn)行了較多修訂和排版。
1、引言
搞即時(shí)通訊IM方面開發(fā)的程序員，在談到通訊層實(shí)現(xiàn)時(shí)，必然會提到網(wǎng)絡(luò)編程。那么計(jì)算機(jī)網(wǎng)絡(luò)編程中的一個非?；镜膯栴}：到底該怎樣組織Client與server之間交互的數(shù)據(jù)呢？
本篇文章我們不討論IM系統(tǒng)中的那些高端技術(shù)話題，我們回歸到通訊的本質(zhì)——也就是數(shù)據(jù)在網(wǎng)絡(luò)中交互時(shí)的編解碼原理，并由淺入深從底層理解Protobuf的編解碼技術(shù)實(shí)現(xiàn)。
學(xué)習(xí)交流：
- 移動端IM開發(fā)入門文章：《新手入門一篇就夠：從零開發(fā)移動端IM》
- 開源IM框架源碼：https://github.com/JackJiang2011/MobileIMSDK（備用地址點(diǎn)此）
（本文已同步發(fā)布于：http://www.52im.net/thread-4088-1-1.html）
2、系列文章
本文是系列文章中的第?3?篇，本系列總目錄如下：
《IM通訊協(xié)議專題學(xué)習(xí)(一)：Protobuf從入門到精通，一篇就夠！》
《IM通訊協(xié)議專題學(xué)習(xí)(二)：快速理解Protobuf的背景、原理、使用、優(yōu)缺點(diǎn)》
《IM通訊協(xié)議專題學(xué)習(xí)(三)：由淺入深，從根上理解Protobuf的編解碼原理》（* 本文）
《IM通訊協(xié)議專題學(xué)習(xí)(四)：從Base64到Protobuf，詳解Protobuf的數(shù)據(jù)編碼原理》（稍后發(fā)布..）
《IM通訊協(xié)議專題學(xué)習(xí)(五)：Protobuf到底比JSON快幾倍？請看全方位實(shí)測！》（稍后發(fā)布..）
《IM通訊協(xié)議專題學(xué)習(xí)(六)：手把手教你如何在Android上從零使用Protobuf》（稍后發(fā)布..）
《IM通訊協(xié)議專題學(xué)習(xí)(七)：手把手教你如何在NodeJS中從零使用Protobuf》（稍后發(fā)布..）
《IM通訊協(xié)議專題學(xué)習(xí)(八)：金蝶隨手記團(tuán)隊(duì)的Protobuf應(yīng)用實(shí)踐(原理篇)??》（稍后發(fā)布..）
《IM通訊協(xié)議專題學(xué)習(xí)(九)：金蝶隨手記團(tuán)隊(duì)的Protobuf應(yīng)用實(shí)踐(實(shí)戰(zhàn)篇) 》（稍后發(fā)布..）
3、共識與協(xié)議
針對引言中引出的“到底該怎樣組織Client與Server之間交互的數(shù)據(jù)呢？”。
這個問題可不像看上去那樣簡單，因?yàn)镃lient進(jìn)程和Server進(jìn)程運(yùn)行在不同的機(jī)器上，這些機(jī)器可能運(yùn)行在不同的處理器平臺、可能運(yùn)行在不同的操作系統(tǒng)、可能是由不同的編程語言編寫的，Server要怎樣才能識別出Client發(fā)送的是什么數(shù)據(jù)呢？
就像這樣：
如上圖所示，Client給Server發(fā)送了一段數(shù)據(jù)：
0101000100100001
Server怎么能知道該怎樣“解讀”這段數(shù)據(jù)呢？
顯然：Client和Server在發(fā)送數(shù)據(jù)之前必須首先達(dá)成某種關(guān)于怎樣解讀數(shù)據(jù)的共識，這就是所謂的協(xié)議。
這里的協(xié)議可以是這樣的：“將每8個比特為一個單位解釋為無符號數(shù)字”。
如果協(xié)議是上面這樣定義的：那么Server接收到這串二進(jìn)制后就會將其解析為?81(01010001)?與?33(00100001)。
當(dāng)然，這里的協(xié)議也可以是這樣的：“將每8個比特為一個單位解釋為ASCII字符”，那么Server接收到這串二進(jìn)制后就將其解析為“Q!”。
可見：同樣一串二進(jìn)制在不同的“上下文/協(xié)議”下有完全不一樣的解讀，這也是為什么計(jì)算機(jī)明明只認(rèn)知0和1但是卻能處理非常復(fù)雜任務(wù)的根本原因，因?yàn)橐磺卸伎梢跃幋a為0和1，同樣的我們也可以從0和1中解析出我們想要的信息，這就是所謂的編解碼技術(shù)。
實(shí)際上不止0和1，我們也可以將信息編碼為摩斯密碼（Morse code）等，只不過計(jì)算機(jī)擅長處理0和1而已。
扯遠(yuǎn)了，回到本文的主題。
4、一個例子：遠(yuǎn)程過程調(diào)用（RPC）
作為程序員我們知道，Client以及Server之間不會簡單傳遞一串?dāng)?shù)字以及字符這樣簡單，尤其在互聯(lián)網(wǎng)大廠后端服務(wù)這種場景下。
當(dāng)我們在電商App里搜索商品、打車App里呼叫出租車以及刷短視頻時(shí)，每一次請求的背后在后端都涉及大量服務(wù)之間的交互。
就像這樣：
完成一次客戶端請求gateway這個服務(wù)要“調(diào)用”N多個下游服務(wù)，所謂“調(diào)用”是說A服務(wù)向B服務(wù)發(fā)送一段數(shù)據(jù)（請求），B服務(wù)接收到這段數(shù)據(jù)后執(zhí)行相應(yīng)的函數(shù)，并將結(jié)果返回給A服務(wù)。
只不過對于服務(wù)A來說并不想關(guān)心網(wǎng)絡(luò)傳輸這樣的底層細(xì)節(jié)，如果能像調(diào)用本地函數(shù)一樣調(diào)用遠(yuǎn)程服務(wù)就好了，這就是所謂的RPC。
經(jīng)典的實(shí)現(xiàn)方式是這樣的：
RPC對上層提供和普通函數(shù)一樣的接口，只不過在實(shí)現(xiàn)上封裝了底層復(fù)雜的網(wǎng)絡(luò)通信（當(dāng)然也包括協(xié)議的定義，協(xié)議的解解碼等）。RPC框架是當(dāng)前互聯(lián)網(wǎng)后端的基石之一，很多所謂互聯(lián)網(wǎng)后端的職位無非就是在此基礎(chǔ)之上堆業(yè)務(wù)邏輯。
本文我們不關(guān)心其中的細(xì)節(jié)，我們只關(guān)心在網(wǎng)絡(luò)層Client是怎樣對請求參數(shù)進(jìn)行編碼、Server怎樣對請求參數(shù)進(jìn)行解碼的，也就是本文開頭提出的問題。
5、信息的編解碼
5.1純文本的編解碼對人類很友好
在思考怎樣進(jìn)行編解碼之前，我們必須意識到：
1）Client和Server可能是用不同語言編寫的（你的編解碼方案必須通用且不能和語言綁定）；
2）編解碼方法的性能問題必須要考慮（尤其是對時(shí)間要求苛刻的服務(wù)）。
首先，我們最應(yīng)該能想到的就是以純文本的形式來表示。
純文本從來都是一種非常有友好的信息載體。為什么？很簡單，因?yàn)槿祟悾ㄎ覀儯┛梢灾苯涌炊?/p>
就像這段：
{
?"widget": {
??"window": {
???"title": "Sample Konfabulator Widget",
???"name": "main_window",
???"width": 500,
???"height": 500
??},
??"image": {
???"src": "Images/Sun.png",
???"name": "sun1",
???"hOffset": 250,
???"vOffset": 250,
??},
?}
}
是不是一目了然：只要我們實(shí)現(xiàn)約定好文本的結(jié)構(gòu)（也就是語法），那么Client和Server就能利用這種文本進(jìn)行信息的編碼以及解碼，不管Client和Server是運(yùn)行在x86還是ARM、是32位的還是64位的、運(yùn)行在Linux上還是Windows上、是大端還是小端，都可以無障礙交流。
因此：在這里，文本的語法就是一種協(xié)議（如下圖所示）。
順便說一句：你都規(guī)定好了文本的語法，實(shí)際上就相當(dāng)于發(fā)明了一種語言。
這里用來舉例用的語言就是所謂的JSON，只不過JSON這種語言不是用來表示邏輯（代碼）而是用來存儲數(shù)據(jù)的。
JSON就是這個老頭提出來的：
除了JSON，另一種利用文本存儲數(shù)據(jù)的表示方法是XML。
來一段XML感受下：
<note>
<to>Tove</to>
<from>Jani</from>
<heading>Reminder</heading>
<body>Don't forget me this weekend!</body>
</note>
相對JSON來說是不是就沒那么容易看懂了，自從JSON出現(xiàn)后在Web領(lǐng)域就逐漸取代了XML。
當(dāng)兩段數(shù)據(jù)量很少的時(shí)候——就像瀏覽器和服務(wù)端的交互，JSON可以工作的非常好（如下圖所示）。
這個場景就是這樣：
在這里是JSON的天下。
5.2純文本對計(jì)算機(jī)來說不夠友好
在上小節(jié)中我們知道，JSON這類純文本的編解碼方式對于人類非常友好。
但對于后端服務(wù)之間的交互（或者具體如IM里Client和Server之間的交互）來說就不一樣了，后端服務(wù)之間的RPC調(diào)用可能會傳輸大量數(shù)據(jù)，如果全部用純文本的形式來表示數(shù)據(jù)那么不管是網(wǎng)絡(luò)帶寬還是性能可能都會差強(qiáng)人意。
在這種場景下，JSON并不是最好的選項(xiàng)，主要原因之一就在于性能以及數(shù)據(jù)的體積。
我們知道：文本表示對人類是最友好的，對機(jī)器來說則不是這樣，對機(jī)器來說最好的還是01二進(jìn)制。
那么有沒有二進(jìn)制的編碼方法嗎？答案是肯定的，這就是當(dāng)前互聯(lián)網(wǎng)后端中流行的Protobuf，Google公司開源項(xiàng)目。
那么Protobuf有什么神奇之處嗎？
假設(shè)Client端想給Server端傳輸這樣一段信息：“我有一個id，其值為43”。
那么在XML下是這樣表示的：
<id>43</id>
數(shù)一數(shù)這這段數(shù)據(jù)占據(jù)了多少字節(jié)，很顯然是11字節(jié)。
而如果用JSON來表示呢？
{"id":43}
數(shù)一數(shù)這段數(shù)據(jù)占據(jù)了多少字節(jié)，顯然是9字節(jié)。
而如果用Protobuf來表示呢? 是這樣的：
//消息定義
message Msg {
??optional int32 id= 1;
}
?
//實(shí)例化
Msg msg;
msg.set_id(43);
其中Msg的定義看上去比JSON和XML更加復(fù)雜了，但這些只是給人看的，這些還會被protbuf進(jìn)一步處理。
最終被Protobuf編碼為：
1082b
也就是0x08與0x2b，這占據(jù)了多少字節(jié)呢？答案是2字節(jié)。
從JSON的9字節(jié)到Protobuf的2字節(jié)，數(shù)據(jù)大小減少了4倍多。
數(shù)據(jù)量的減少意味著：
1）更少的網(wǎng)絡(luò)帶寬；
2）更快的解析速度。
那么，Protobuf是怎樣做到這一點(diǎn)的呢？
6、Protobuf是怎樣實(shí)現(xiàn)編解碼的？
首先，我們來思考最簡單的情況，正常情況下，我們該怎樣表示數(shù)字。
你可能會想這還不簡單，統(tǒng)一用固定長度，比如用64個比特（8字節(jié)）。
這種方法可行，但問題是不論一個數(shù)字有多小，比方2，那么用這種方法表示2也需要占據(jù)64個比特（8字節(jié)），如下所示。
明明只要一個字節(jié)就能表示而我們卻用了8個，前面的全都是0，這也太奢侈太浪費(fèi)了吧。
顯然，在這里我們不能使用固定長度來表示數(shù)字，而需要使用變長方法來表示。
什么叫變長？意思是說如果數(shù)字本身比較大，那么其使用的比特位可以較多，但如果數(shù)字很小那么就應(yīng)該使用較少的比特位來表示，這就叫變長，隨機(jī)應(yīng)變，不死板。
那怎樣變長呢？
我們規(guī)定：對于每一個字節(jié)來說，第一個比特位如果是1那么表示接下來的一個比特依然要用來解釋為一個數(shù)字，如果第一個比特為0，那么說明接下來的一個字節(jié)不是用來表示該數(shù)字的。
也就是說對于每個8個比特（1字節(jié)）來說，它的有效載荷是7個比特，第一個比特僅僅用來標(biāo)記是否還應(yīng)該把接下來的一個字節(jié)解析為數(shù)字。
根據(jù)這個規(guī)定，假設(shè)來了這樣一串01二進(jìn)制：
1010110000000010
根據(jù)規(guī)定，我們首先取出第一個字節(jié)，也就是：
10101100
此時(shí)我們發(fā)現(xiàn)第一個比特位是1，因此我們知道接下來的一個字節(jié)也屬于該數(shù)字。
將當(dāng)前字節(jié)的1去掉就是：
0101100
然后我們看下一個字節(jié)：
00000010
我們發(fā)現(xiàn)第一個bit為0，因此我們知道下一個字節(jié)不屬于該數(shù)字了。
接下來我們將解析到的0101100（第一個字節(jié)去掉第一個比特位）以及第二個字節(jié)0000010（第二個字節(jié)去掉第一個比特位）翻轉(zhuǎn)之后拼接到一起（這里之所以翻轉(zhuǎn)是因?yàn)槲覀円?guī)定數(shù)字的高位在后）。
這個過程就是：
? ? ?1010110000000010?
->? 10101100 | 00000010 //解析得到兩個字節(jié)
????_????????? _
?
->? 0101100? |? 0000010? //各自去掉最高位
->? 0000010? |? 0101100? //兩個字節(jié)翻轉(zhuǎn)順序
?
????0000010? +? 0101100
->? 100101100?????????? //拼接
最后我們得到了100101100，這一串二進(jìn)制表示數(shù)字300。
這種數(shù)字的變長表示方法在Protobuf中被稱之為varint。
因此在這種表示方法下，如果數(shù)字較大，那么使用的比特就多，如果數(shù)字較小那么使用比特就少，聰明吧。
有的同學(xué)看到這里可能會問題，剛才講解的方法只能表示無符號數(shù)字，那么有符號數(shù)字該怎么表示呢？比如-2該怎么表示？
7、Protobuf的有符號數(shù)表示
按照剛才變長編碼的思想，-2147483646使用的比特位應(yīng)該比-2要少。
然而我們知道在計(jì)算機(jī)世界中負(fù)數(shù)使用補(bǔ)碼表示的，也就是說最高位（最左側(cè)的比特位）一定是1，假設(shè)我們使用64位來表示數(shù)字，那么如果我們依然用補(bǔ)碼來表示數(shù)字的話那么無論這個負(fù)數(shù)有多大還是多小都需要占據(jù)10個字節(jié)的空間。
為什么是10個字節(jié)呢？
不要忘了varint每個字節(jié)的有效負(fù)荷是7個比特，那么對于需要64位表示的數(shù)字來說就需要64/7向上取整也就是10個字節(jié)來表示。
這顯然不能滿足我們對數(shù)字變長存儲的要求。
該怎么解決這個問題呢？
既然無符號數(shù)字可以方便的進(jìn)行變長編碼，那么我們將有符號數(shù)字映射稱為無符號數(shù)字不就可以了，這就是所謂的ZigZag編碼，是不是很聰明。
ZigZag編碼就像這樣：
原始信息????? 編碼后
0??????????? 0
-1?????????? 1
1??????????? 2
-2?????????? 3
2??????????? 4
-3?????????? 5
3??????????? 6
?
...????????? ...
?
2147483647?? 4294967294
-2147483648? 4294967295
這樣我們就可以將有符號數(shù)字轉(zhuǎn)為無符號數(shù)字，接收方接收到該數(shù)據(jù)后再恢復(fù)出有符號數(shù)字。
現(xiàn)在數(shù)字的問題徹底解決了，但這僅僅是萬里長征第一步。
8、Protobuf的字段名稱與字段類型
對于任何一個有用的信息都包含這樣幾部分：
1）字段名稱；
2）字段類型；
3）字段值。
就像C/C++中定義變量時(shí)：
int i = 100;
在這里，字段名稱就是i，字段類型是int，字段值是100。
剛才我們用varint以及ZigZag編碼解決了字段值表示的問題，那么該怎樣表示字段名稱和字段類型呢？
首先，對于字段類型還比較簡單，因?yàn)樽侄晤愋途湍敲炊唷?/p>
Protobuf中定義了6種字段類型：
對于6種字段類型我們使用3個比特位來表示就足夠了。
接下來比較有趣的是字段名稱該怎么表示呢？
假設(shè)我們需要傳遞這樣一個字段：
int long_long_name = 100;
那么我們真的需要把“l(fā)ong_long_name”這么多字符通過網(wǎng)絡(luò)傳遞給對端嗎？
既然通信雙方需要協(xié)議，那么“l(fā)ong_long_name”這字段其實(shí)是Client和Server都知道的，它們唯一不知道的就是“哪些值屬于哪些字段”。
為解決這個問題，我們給每個字段都進(jìn)行編號，比如通信雙方都知道“l(fā)ong_long_name”這個字段的編號是2。那么對于“int long_long_name = 100;?”我們該怎么表示呢。
這個信息我們只需要傳遞：
1）字段名稱：2 (2對應(yīng)字段“l(fā)ong_long_name”)；
2）字段類型：0 (0表示varint類型，參見上圖)；
3）字段值：100。
所以我們可以看到，無論你用多么復(fù)雜的字段名稱也不會影響編碼后占據(jù)的空間，字段名稱根本就不會出現(xiàn)在編碼后的信息中，so clever。
9、從宏觀上看Protobuf的編碼原理
我們已經(jīng)在Protobuf中看到了數(shù)字以及字段名稱以及字段類型是怎么表示了，現(xiàn)在是時(shí)候從宏觀角度來看看多個字段該怎么編碼了。
從本質(zhì)上講，Protobuf被編碼后形成一系列的key-value，每個key-value對應(yīng)一個proto中的字段。
也就是鍵值對：
其中value比較簡單，也就是字段值；而字段名稱和字段類型會被拼接成key。Protobuf中共有6種類型，因此只需要3個比特位即可。字段名稱只需要存儲對應(yīng)的編號。
這樣就可以這樣編碼：
(字段編號 << 3) | 字段類型
假設(shè)Server接收到了一個key為0x08，其二進(jìn)制的表示為：
0000 1000
由于key也是利用varint編碼的，因此需要將第一個比特位去掉。
這樣我的得到：
000 1000
根據(jù)key的編碼方式，其后三個比特位表示字段類型，即：
000
也就是0，這樣我們知道該key的類型是Varint(第0號類型)，而字段編號為抹掉后3個比特位的值，即：
0001
這樣，我們就知道了該key對應(yīng)的字段編號為1，得到編號我們就能根據(jù)編號找到對應(yīng)的編號名稱。
10、Protobuf的嵌套數(shù)據(jù)
與JSON和XML類似，Protobuf中也支持嵌套消息.
就像這樣：
message SubMsg {
??optional int32 id= 1;
}
message Msg {
??optional SubMsg msg = 1;
}
其實(shí)現(xiàn)也比較簡單，這依然遵循被編碼后形成一系列的key-value，只不過對于嵌套類型的key來說，其value是由子消息的key-value組成，如下圖所示。
11、Protobuf與編譯語言
與JSON一樣，Protobuf也是一門語言，兼具了文本的可讀性以及二進(jìn)制的高效。
Protobuf之所以能做到這一點(diǎn)，就好比C語言與機(jī)器指令。
C語言是給程序員看的，可讀性好。而機(jī)器指令是給硬件使用的，性能好。編譯器會將C語言程序轉(zhuǎn)為機(jī)器可執(zhí)行的機(jī)器指令。
而Protobuf也一樣，Protobuf也是一門語言，會將可讀性較好的消息編碼為二進(jìn)制從而可以在網(wǎng)絡(luò)中進(jìn)行傳播，而對端也可以將其解碼回來。
在這里Protobuf中定義的消息就好比C語言，編碼后的二進(jìn)制消息就好比機(jī)器指令。
而Protobuf作為事實(shí)上語言必然有自己的語法。
其語法就是這樣：
怎么樣，還覺得編譯原理沒什么用嗎？
不理解編譯原理是不可能發(fā)明Protobuf這種技術(shù)的。
12、本文小結(jié)
我在寫這篇文章時(shí)不斷感嘆，Google的這項(xiàng)技術(shù)節(jié)省了多少程序員的時(shí)間，同時(shí)我們也能看到這種基石般的技術(shù)依賴的底層原理卻非常古老。
比如下面這些：
1）信息的編解碼；
2）編譯原理。
怎么樣，這些是不是遠(yuǎn)遠(yuǎn)沒有IT界各種流行的技術(shù)聽上去時(shí)髦有趣，而正是這種樸素的技術(shù)支撐起了工業(yè)界，現(xiàn)在你也應(yīng)該能明白底層技術(shù)的重要性了吧。
13、參考資料
[1]Protobuf官方網(wǎng)站
[2]Protobuf從入門到精通，一篇就夠！
[3]如何選擇即時(shí)通訊應(yīng)用的數(shù)據(jù)傳輸格式
[4]強(qiáng)列建議將Protobuf作為你的即時(shí)通訊應(yīng)用數(shù)據(jù)傳輸格式
[5]APP與后臺通信數(shù)據(jù)格式的演進(jìn)：從文本協(xié)議到二進(jìn)制協(xié)議
[6]面試必考，史上最通俗大小端字節(jié)序詳解
[7]移動端IM開發(fā)需要面對的技術(shù)問題（含通信協(xié)議選擇）
[8]簡述移動端IM開發(fā)的那些坑：架構(gòu)設(shè)計(jì)、通信協(xié)議和客戶端
[9]理論聯(lián)系實(shí)際：一套典型的IM通信協(xié)議設(shè)計(jì)詳解
[10]58到家實(shí)時(shí)消息系統(tǒng)的協(xié)議設(shè)計(jì)等技術(shù)實(shí)踐分享
（本文已同步發(fā)布于：http://www.52im.net/thread-4088-1-1.html）
