プロトコルバッファのバイナリアルゴリズムへの深いダイブ

人間理解可能な形式が優先されていない場合、バイナリを考えるのがベストです.Protocol Buffers , また、ProtobufsやProtosとして知られている、オープンソースのインターフェイス記述言語は、Googleとは、JSONのようなデータメッセージを可能にするライブラリは、不要なバラストなしでワイヤを介して送信することができますライブラリ開発されます.今日、それは文脈の中で最も関連性がありますgRPC , どこRPC 任意のプログラミング言語のためのサーバーとクライアントコードは、プロトコルバッファー記述に基づいて生成されます.
プロトコルバッファは主にネットワーク上で強く型付けられたキー値メッセージオブジェクトのトランスミッションをスピードアップすることを目標として開発されました.そして、それは順番にAからBまでワイヤーで伝送される必要があるデータの量を減らすことを意味します.
REST and RPC つの概念は、現在、ウェブ開発でAPIを開発する事実上の方法の一種と考えられます.クライアントとサーバの間の通信は、主にデータを転送することですJSON 形式.これは、ユーザーフレンドリーですが、非常にネットワークレベルでsuboptimtimalです.したがって、人々はそのような圧縮メカニズムを開発しました、しかし、あなたが本当に何かを最適化したいならば、あなたはネットワーク層でゼロから始めなければならなくて、それから他の方法ではなく、ユーザー部分にそこからあなたの方法を働かせなければなりません.
ApacheなどのJSONのようなデータを送るための様々な選択肢がありますBond プロトコル( Apache )SBE , Bincode , CBir , MsgPack , Cap'n Proto , Flatbuffers などが挙げられる.これらのすべては、少なくともネットワークレベルで同じ問題に対する解決策です.ワイヤーの上で強くタイプされたメッセージに関して、プロトコルバッファは最も最適化されたプロトコルのうちの1つで、特にKubernetes と同様のコミュニティ.実際には、それは明白な選択になります良いと人気のソリューションです.
プロトコルバッファーは単純なプロトコルであり、普通の紙で説明できる.ドキュメントはかなり緩やかに定式化されますが、実装中に遭遇するすべての質問には答えません.プロトコルバッファは幸いにもオープンソースであり、主な作者が書いたソースコードを見ることによってどんな疑いもクリアできます.
エンコーダとデコーダは、入力キーから縮小されたバイナリ形式と背中にメッセージを変換します.プロパティ名は、プロトコルバッファではなく、文字列で一意の数字で表されます.生のJSON形式と比較して、これはすでにワイヤーの上に送られるメッセージの最終的なサイズに重要な影響を及ぼします.

+-------------------+------------------+-------------------+
+      1. JSON      +   2. Transform   +     3. Encode     + 
+-------------------+------------------+-------------------+
+ {                 +                  +                   +
+   "name": "John", + 1, John          + 0a 04 4a 6f 68 6e +
+   "age": 35       + 2, 35            + 10 23             +
+ }                 +                  +                   +
+-------------------+------------------+-------------------+
+      6. JSON      +    5. Rebuild    +     4. Decode     + 
+-------------------+------------------+-------------------+

さらに、プロトコルバッファカバー4 ワイヤの種類18 表示されるデータ型.
種類
意味
使用する
0
Varint
Int 32 , Int 64 , UInt 32 , UInt 64 , Sint 32 , Sint 64 , bool , enum
1
64ビット
fixed 64 , Sfixed 64 , double
2
長さ区切り
文字列、バイト、埋め込みメッセージ、パックされた繰り返しフィールド
5
32ビット
fixed 32 , sfixed 32 , float
エンコーダはメッセージをバイナリ形式に変換します.メッセージは、それからコード化されたキー値特性の平坦化されたシーケンスの種類としてワイヤーで表されます.キーと値は別々にエンコードされます.それぞれのワイヤータイプはそれ自身の規則、したがって、それ自身の符号化方法を持っています.

[key1][value1][key2][value2] ... [keyN][valueN]

キーはAとしてエンコードされますuint32 Varint型、最後に3 ビットT ) ワイヤータイプを含みます.したがって、キーのフィールドタグは1 and 2^29 - 1 = 536,870,911 ( 0 が有効なタグ番号ではない).

tag = 12345 (unsigned 32-bit), type = 1 (Varint)

11001000 10000011 00000110 ... on the wire
CNNNNNNN CNNNNNNN CNNNNTTT ... bits per type

C = Contiunation, X = Number, T = Type

varintsは1バイト以上の整数を直列化する方法です.ここで使用するアルゴリズムはLEB128 . 最後を除く全てのバイトは最上位ビット( MSB )集合を持っています(C ), デコーダが値がどこで終わるかについて決定することができるように.その他7 ビットN ) 各バイトの数を表すために意図されます.
LEB 128はバイトが小さなエンディアン系列で配置される任意の長さの整数をコード化するためのアルゴリズムです.しかし、プロトコルバッファはサポートされているデータ型に数値のサイズを制限します.

value = 150 (unsigned 32-bit)

Standard varint encoding:
   XXXXXXXX 10010110 ... Number 150 in bytes.
   X0000001 X0010110 ... Split to 7-bit sequence.
   X0010110 X0000001 ... Revert the array of bytes.
   10010110 00000001 ... Add MSB (1=continuation, 0=last byte).

Standard varint decoding:
   10010110 00000001 ... Encoded number.
   00000001 10010110 ... Revert the array of bytes.
   X0000001 X0010110 ... Remove MSB.
   XXXXXXXX 10010110 ... Merge bits together (number 150 in bytes).

符号付き整数型の間には大きな違いがありますsint32 and sint64 ) と"標準"整数型int32 and int64 ). あなたが使うならばint32 or int64 負の数値の型として、結果は常に10バイト長いです.値が最も負の値であることを知っている場合は、結果を最適化し、結果として使用されるvarintを使用している符号型のいずれかを使用できますZigZag 効率のための符号化本質的には、これは正と負の整数がそのようにジグザグされていることを意味する-1 は1 , 1 AS2 , -2 AS3 , など.

value = -12345 (signed 32-bit)

Signed 32-bit varint encoding:
   -12345 ... Unsigned 32-bit integer.
    24689 ... ZigZag value using (value << 1) ^ (value >> 31).
          ... Continue with the standard varint encoding.
Signed 32-bit varint decoding:
          ... Start with the standard varint decoding.
    24689 ... ZigZag value using (value >> 1) ^ -(value & 1).
   -12345 ... Unsigned 32-bit integer.

value = -54321 (signed 64-bit)

Signed 64-bit varint encoding:
   -54321 ... Unsigned 64-bit integer.
   108641 ... ZigZag value using (val << 1) ^ (val >> 63).
          ... Continue with the standard varint encoding.
Signed 64-bit varint decoding:
          ... Start with the standard varint decoding.
   108641 ... ZigZag value using (value >> 1) ^ -(value & 1).
   -54321 ... Unsigned 64-bit integer.

番号はまた、ワイヤの種類によって表されることができます1 or 5 . これらは32-bit データ型float , fixed32 and sfixed32 and 64-bit データ型double , fixed64 and sfixed64 . これらの数字は単にリトルエンディアンバイトオーダーのバイトで表されます(したがって、逆の順序で).

value = 12345 (signed 32-bit)

Fixed-size encoding:
   00000000 00000000 00110000 00111001 ... Value in (big-endian) bytes.
   00111001 00110000 00000000 00000000 ... Reverse bytes to little-endian order.
Fixed-size decoding:
   00111001 00110000 00000000 00000000 ... Encoded value in (little-endian) order.
   00000000 00000000 00110000 00111001 ... Value in (big-endian) bytes.

ワイヤタイプは2 ? 「長さ区切り」とは、値がVarint符号化長で、データのバイト数が指定されたことを意味します.このことはstrings , embedded メッセージ(ネストしたオブジェクト)とrawbytes データ型.

value = "foo"

Length-delimited encoding:
   00000011 XXXXXXXX XXXXXXXX XXXXXXXX ... Encode message size (3 bytes) as standard 32-bit varint.
   00000011 01100110 01101111 01101111 ... Append string (foo) in bytes.

最後に繰り返しフィールドについて述べた.これらは1つのデータ型の配列を表します.配列の各要素が別々のキー値符号化ストリームとして送られるという規則以外の特別な符号化規則はありません.
さて、上記のすべては完全に真実ではありません.配列が数値型の要素を含んでいる場合、配列は“pack”符号化と呼ばれるものに縮小されます.ここで、キーは一度だけ送信されます.どのようにコードがエンコードされて覚えていますか?数のために、これは可能です、デコーダが常に単一の数が終わるところを決めることができるので.文字列と関連するデータ型では、これはできません.

Packed repeated fields:
   [key][value1][value2]...[valueN]

Unpacked repeated fields:
   [key][value1][key][value2]...[key][valueN]

見ることができるように、プロトコルバッファは、クライアントとサーバの間で可能な限り小さなデータが送信されるように、ワイヤ上のデータ型の表現を最適化することで詳細に対処します.
私のブログの大部分と同様に、これらは再び私の個人的なメモと洞察力を私はRust . 私は、彼らが他の人にも同様に使用することを望みます.ライブラリは再びオープンソースパッケージとしてリリースされ、ソースコードはGitHub .