神奇的Google二進(jìn)制編解碼技術(shù):Protobuf
計(jì)算機(jī)網(wǎng)絡(luò)編程中一個(gè)非常基本的問(wèn)題:該怎樣表示client與server之間交互的數(shù)據(jù),在往下看之前先想一想這個(gè)問(wèn)題。
共識(shí)與協(xié)議
這個(gè)問(wèn)題可不像看上去的那樣簡(jiǎn)單,因?yàn)閏lient進(jìn)程和server進(jìn)程運(yùn)行在不同的機(jī)器上,這些機(jī)器可能運(yùn)行在不同的處理器平臺(tái)、可能運(yùn)行在不同的操作系統(tǒng)、可能是由不同的編程語(yǔ)言編寫的,server要怎樣才能識(shí)別出client發(fā)送的是什么數(shù)據(jù)呢?就像這樣:client給server發(fā)送了一段數(shù)據(jù):
0101000100100001
server怎么能知道該怎樣“解讀”這段數(shù)據(jù)呢?
顯然,client和server在發(fā)送數(shù)據(jù)之前必須首先達(dá)成某種關(guān)于怎樣解讀數(shù)據(jù)的共識(shí),這就是所謂的協(xié)議。
這里的協(xié)議可以是這樣的:“將每8個(gè)比特為一個(gè)單位解釋為無(wú)符號(hào)數(shù)字”,如果協(xié)議是這樣的,那么server接收到這串二進(jìn)制后就會(huì)將其解析為81(01010001)與33(00100001)。
當(dāng)然,這里的協(xié)議也可以是這樣的:“將每8個(gè)比特為一個(gè)單位解釋為ASCII字符”,那么server接收到這串二進(jìn)制后就將其解析為“Q!”。
可見(jiàn),同樣一串二進(jìn)制在不同的“上下文/協(xié)議”下有完全不一樣的解讀,這也是為什么計(jì)算機(jī)明明只認(rèn)知0和1但是卻能處理非常復(fù)雜任務(wù)的根本原因,因?yàn)橐磺卸伎梢跃幋a為0和1,同樣的我們也可以從0和1中解析出我們想要的信息,這就是所謂的編解碼技術(shù)。
實(shí)際上不止0和1,我們也可以將信息編碼為摩斯密碼(Morse code)等,只不過(guò)計(jì)算機(jī)擅長(zhǎng)處理0和1而已。
扯遠(yuǎn)了,回到本文的主題。
遠(yuǎn)程過(guò)程調(diào)用:RPC
作為程序員我們知道,client以及server之間不會(huì)簡(jiǎn)單傳遞一串?dāng)?shù)字以及字符這樣簡(jiǎn)單,尤其在互聯(lián)網(wǎng)大廠后端服務(wù)這種場(chǎng)景下。
當(dāng)我們?cè)陔娚藺pp搜索商品、打車App呼叫出租車以及刷短視頻時(shí),每一次請(qǐng)求的背后在后端都涉及大量服務(wù)之間的交互,就像這樣:
完成一次客戶端請(qǐng)求gateway這個(gè)服務(wù)要調(diào)用N多個(gè)下游服務(wù),所謂調(diào)用是說(shuō)A服務(wù)向B服務(wù)發(fā)送一段數(shù)據(jù)(請(qǐng)求),B服務(wù)接收到這段數(shù)據(jù)后執(zhí)行相應(yīng)的函數(shù),并將結(jié)果返回給A服務(wù)。
只不過(guò)對(duì)于服務(wù)A來(lái)說(shuō)并不想關(guān)心網(wǎng)絡(luò)傳輸這樣的底層細(xì)節(jié),如果能像調(diào)用本地函數(shù)一樣調(diào)用遠(yuǎn)程服務(wù)就好了,這就是所謂的RPC,經(jīng)典的實(shí)現(xiàn)方式是這樣的:
RPC對(duì)上層提供和普通函數(shù)一樣的接口,只不過(guò)在實(shí)現(xiàn)上封裝了底層復(fù)雜的網(wǎng)絡(luò)通信,RPC框架是當(dāng)前互聯(lián)網(wǎng)后端的基石之一,很多所謂互聯(lián)網(wǎng)后端的職位無(wú)非就是在此基礎(chǔ)之上堆業(yè)務(wù)邏輯。
本文我們不關(guān)心其中的細(xì)節(jié),這里我們只關(guān)心在網(wǎng)絡(luò)層client是怎樣對(duì)請(qǐng)求參數(shù)進(jìn)行編碼、server怎樣對(duì)請(qǐng)求參數(shù)進(jìn)行解碼的,也就是本文開(kāi)頭提出的問(wèn)題。
信息的編解碼
在思考怎樣進(jìn)行編解碼之前我們必須意識(shí)到:
- client和server可能是用不同語(yǔ)言編寫的,你的編解碼方案必須通用且不能和語(yǔ)言綁定
- 編解碼方法的性能問(wèn)題,尤其是對(duì)時(shí)間要求苛刻的服務(wù)
首先,我們最應(yīng)該能想到的就是以純文本的形式來(lái)表示。
純文本從來(lái)都是一種非常有友好的信息載體,為什么?很簡(jiǎn)單,因?yàn)槿祟?我們)可以直接看懂,就像這段:
{ "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)(也就是語(yǔ)法),那么client和server就能利用這種文本進(jìn)行信息的編碼以及解碼,不管client和server是運(yùn)行在x86還是Arm、是32位的還是64位的、運(yùn)行在Linux上還是windows上、是大端還是小端,都可以無(wú)障礙交流。
因此在這里,文本的語(yǔ)法就是一種協(xié)議。順便說(shuō)一句,你都規(guī)定好了文本的語(yǔ)法,實(shí)際上就相當(dāng)于發(fā)明了一種語(yǔ)言。
這里用來(lái)舉例用的語(yǔ)言就是所謂的Json,只不過(guò)json這種語(yǔ)言不是用來(lái)表示邏輯(代碼)而是用來(lái)存儲(chǔ)數(shù)據(jù)的。
Json就是這個(gè)老頭提出來(lái)的:
除了Json,另一種利用文本存儲(chǔ)數(shù)據(jù)的表示方法是XML,來(lái)一段感受下:
ToveJaniReminderDon't forget me this weekend!
相對(duì)Json來(lái)說(shuō)是不是就沒(méi)那么容易看懂了,Json出現(xiàn)后在web領(lǐng)域逐漸取代了XML。
當(dāng)兩段數(shù)據(jù)量很少的時(shí)候——就像瀏覽器和服務(wù)端的交互,Json可以工作的非常好,這個(gè)場(chǎng)景就是這里:在這里是json的天下。
但對(duì)于后端服務(wù)之間的交互來(lái)說(shuō)就不一樣了,后端服務(wù)之間的RPC調(diào)用可能會(huì)傳輸大量數(shù)據(jù),如果全部用純文本的形式來(lái)表示數(shù)據(jù)那么不管是網(wǎng)絡(luò)帶寬還是性能可能都會(huì)差強(qiáng)人意。
在這種場(chǎng)景下,Json并不是最好的選項(xiàng),主要原因之一就在于性能以及數(shù)據(jù)的體積。
我們知道,文本表示對(duì)人類是最友好的,對(duì)機(jī)器來(lái)說(shuō)則不是這樣,對(duì)機(jī)器來(lái)說(shuō)最好的還是01二進(jìn)制。
那么有沒(méi)有二進(jìn)制的編碼方法嗎?答案是肯定的,這就是當(dāng)前互聯(lián)網(wǎng)后端中流行的protobuf,Google公司開(kāi)源項(xiàng)目。
那么protobuf有什么神奇之處嗎?
假設(shè)client端想給server端傳輸這樣一段信息:“我有一個(gè)id,其值為43”,那么在XML下是這樣表示的:
43
數(shù)一數(shù)這這段數(shù)據(jù)占據(jù)了多少字節(jié),很顯然是11字節(jié);
而如果用json來(lái)表示呢?
{"id":43}
數(shù)一數(shù)這段數(shù)據(jù)占據(jù)了多少字節(jié),顯然是9字節(jié);
而如果用protobuf來(lái)表示呢? 是這樣的:
// 消息定義 message Msg { optional int32 id = 1; } // 實(shí)例化 Msg msg; msg.set_id(43);
其中Msg的定義看上去比Json和XML更加復(fù)雜了,但這些只是給人看的,這些還會(huì)被protbuf進(jìn)一步處理,最終被編碼為:
082b
也就是0x08與0x2b,這占據(jù)了多少字節(jié)呢?答案是2字節(jié)。
從json的9字節(jié)到protobuf的2字節(jié),數(shù)據(jù)大小減少了4倍多,數(shù)據(jù)量的減少意味著:
- 更少的網(wǎng)絡(luò)帶寬
- 更快的解析速度
那么protobuf是怎樣做到這一點(diǎn)的呢?
protobuf是怎樣實(shí)現(xiàn)的?
首先,我們來(lái)思考最簡(jiǎn)單的情況,該怎樣表示數(shù)字。
你可能會(huì)想這還不簡(jiǎn)單,統(tǒng)一用固定長(zhǎng)度,比如用64個(gè)比特(8字節(jié)),這種方法可行,但問(wèn)題是不論一個(gè)數(shù)字有多小,比方2,那么用這種方法表示2也需要占據(jù)64個(gè)比特(8字節(jié)):
明明只要一個(gè)字節(jié)就能表示而我們卻用了8個(gè),前面的全都是0,這也太奢侈太浪費(fèi)了吧。
顯然,在這里我們不能使用固定長(zhǎng)度來(lái)表示數(shù)字,而需要使用變長(zhǎng)方法來(lái)表示。
什么叫變長(zhǎng)?意思是說(shuō)如果數(shù)字本身比較大,那么其使用的比特位可以較多,但如果數(shù)字很小那么就應(yīng)該使用較少的比特位來(lái)表示,這就叫變長(zhǎng),隨機(jī)應(yīng)變,不死板。
那怎樣變長(zhǎng)呢?
我們規(guī)定:對(duì)于每一個(gè)字節(jié)來(lái)說(shuō),第一個(gè)比特位如果是1那么表示接下來(lái)的一個(gè)比特依然要用來(lái)解釋為一個(gè)數(shù)字,如果第一個(gè)比特為0,那么說(shuō)明接下來(lái)的一個(gè)字節(jié)不是用來(lái)表示該數(shù)字的。
也就是說(shuō)對(duì)于每個(gè)8個(gè)比特(1字節(jié))來(lái)說(shuō),它的有效載荷是7個(gè)比特,第一個(gè)比特僅僅用來(lái)標(biāo)記是否還應(yīng)該把接下來(lái)的一個(gè)字節(jié)解析為數(shù)字。
根據(jù)這個(gè)規(guī)定假設(shè)來(lái)了這樣一串01二進(jìn)制:
1010110000000010
根據(jù)規(guī)定,我們首先取出第一個(gè)字節(jié),也就是:
10101100
此時(shí)我們發(fā)現(xiàn)第一個(gè)比特位是1,因此我們知道接下來(lái)的一個(gè)字節(jié)也屬于該數(shù)字,將當(dāng)前字節(jié)的1去掉就是:
0101100
然后我們看下一個(gè)字節(jié):
00000010
我們發(fā)現(xiàn)第一個(gè)bit為0,因此我們知道下一個(gè)字節(jié)不屬于該數(shù)字了。
接下來(lái)我們將解析到的0101100(第一個(gè)字節(jié)去掉第一個(gè)比特位)以及第二個(gè)字節(jié)0000010(第二個(gè)字節(jié)去掉第一個(gè)比特位)翻轉(zhuǎn)之后拼接到一起,這里之所以翻轉(zhuǎn)是因?yàn)槲覀円?guī)定數(shù)字的高位在后。
這個(gè)過(guò)程就是:
1010110000000010 -> 10101100 | 00000010 // 解析得到兩個(gè)字節(jié) _ _ -> 0101100 | 0000010 // 各自去掉最高位 -> 0000010 | 0101100 // 兩個(gè)字節(jié)翻轉(zhuǎn)順序 0000010 + 0101100 -> 100101100 // 拼接
最后我們得到了100101100,這一串二進(jìn)制表示數(shù)字300。
這種數(shù)字的變長(zhǎng)表示方法在protobuf中被稱之為varint。
因此在這種表示方法下,如果數(shù)字較大,那么使用的比特就多,如果數(shù)字較小那么使用比特就少,聰明吧。
有的同學(xué)看到這里可能會(huì)問(wèn)題,剛才講解的方法只能表示無(wú)符號(hào)數(shù)字,那么有符號(hào)數(shù)字該怎么表示呢?比如-2該怎么表示?
有符號(hào)數(shù)的表示
按照剛才變長(zhǎng)編碼的思想,-2147483646使用的比特位應(yīng)該比-2要少。
然而我們知道在計(jì)算機(jī)世界中負(fù)數(shù)使用補(bǔ)碼表示的,也就是說(shuō)最高位(最左側(cè)的比特位)一定是1,假設(shè)我們使用64位來(lái)表示數(shù)字,那么如果我們依然用補(bǔ)碼來(lái)表示數(shù)字的話那么無(wú)論這個(gè)負(fù)數(shù)有多大還是多小都需要占據(jù)10個(gè)字節(jié)的空間。
為什么是10個(gè)字節(jié)呢?
不要忘了varint每個(gè)字節(jié)的有效負(fù)荷是7個(gè)比特,那么對(duì)于需要64位表示的數(shù)字來(lái)說(shuō)就需要64/7向上取整也就是10個(gè)字節(jié)來(lái)表示。
這顯然不能滿足我們對(duì)數(shù)字變長(zhǎng)存儲(chǔ)的要求。
該怎么解決這個(gè)問(wèn)題呢?
既然無(wú)符號(hào)數(shù)字可以方便的進(jìn)行變長(zhǎng)編碼,那么我們將有符號(hào)數(shù)字映射稱為無(wú)符號(hào)數(shù)字不就可以了,這就是所謂的ZigZag編碼,是不是很聰明,就像這樣:
原始信息 編碼后 0 0 -1 1 1 2 -2 3 2 4 -3 5 3 6 ... ... 2147483647 4294967294 -2147483648 4294967295
這樣我們就可以將有符號(hào)數(shù)字轉(zhuǎn)為無(wú)符號(hào)數(shù)字,接收方接收到該數(shù)據(jù)后再恢復(fù)出有符號(hào)數(shù)字。
現(xiàn)在數(shù)字的問(wèn)題徹底解決了,但這僅僅是萬(wàn)里長(zhǎng)征第一步。
字段名稱與字段類型
對(duì)于任何一個(gè)有用的信息都包含這樣幾部分:
- 字段名稱
- 字段類型
- 字段值
就像C/C++中定義變量時(shí):
int i = 100;
在這里,字段名稱就是i,字段類型是int,字段值是100。
剛才我們用varint以及ZigZag編碼解決了字段值表示的問(wèn)題,那么該怎樣表示字段名稱和字段類型呢?
首先,對(duì)于字段類型還比較簡(jiǎn)單,因?yàn)樽侄晤愋途湍敲炊?,protobuf中定義了6種字段類型:
對(duì)于6種字段類型我們使用3個(gè)比特位來(lái)表示就足夠了。
接下來(lái)比較有趣的是字段名稱該怎么表示呢?假設(shè)我們需要傳遞這樣一個(gè)字段:
int long_long_name = 100;
那么我們真的需要把“l(fā)ong_long_name”這么多字符通過(guò)網(wǎng)絡(luò)傳遞給對(duì)端嗎?
既然通信雙方需要協(xié)議,那么“l(fā)ong_long_name”這字段其實(shí)是client和server都知道的,它們唯一不知道的就是“哪些值屬于哪些字段”。
為解決這個(gè)問(wèn)題,我們給每個(gè)字段都進(jìn)行編號(hào),比如通信雙方都知道“l(fā)ong_long_name”這個(gè)字段的編號(hào)是2,那么對(duì)于:
int long_long_name = 100;
這個(gè)信息我們只需要傳遞:
- 字段名稱:2 (2對(duì)應(yīng)字段“l(fā)ong_long_name”)
- 字段類型:0 (0表示varint類型,參見(jiàn)上圖)
- 字段值:100
所以我們可以看到,無(wú)論你用多么復(fù)雜的字段名稱也不會(huì)影響編碼后占據(jù)的空間,字段名稱根本就不會(huì)出現(xiàn)在編碼后的信息中,so clever。
從宏觀上看
我們已經(jīng)在protobuf中看到了數(shù)字以及字段名稱以及字段類型是怎么表示了,現(xiàn)在是時(shí)候從宏觀角度來(lái)看看多個(gè)字段該怎么編碼了。
從本質(zhì)上講,protobuf被編碼后形成一系列的key-value,每個(gè)key-value對(duì)應(yīng)一個(gè)proto中的字段。
也就是鍵值對(duì):
其中value比較簡(jiǎn)單,也就是字段值;而字段名稱和字段類型會(huì)被拼接成key,protobuf中共有6種類型,因此只需要3個(gè)比特位即可;字段名稱只需要存儲(chǔ)對(duì)應(yīng)的編號(hào),這樣可以就可以這樣編碼:
(字段編號(hào) << 3) | 字段類型
假設(shè)server接收到了一個(gè)key為0x08,其二進(jìn)制的表示為:
0000 1000
由于key也是利用varint編碼的,因此需要將第一個(gè)比特位去掉,這樣我的得到:
000 1000