Protocol Buffersとは、キーとバリューを持つ構造化されたデータを小さく速く簡潔にシリアライズ/デシリアライズするための特定のプログラミング言語によらないメカニズムである。シリアライズ時にはバイナリになる。そのバイナリ化ひととおりの流れを日本語で私なりに説明する。ここに書いた情報は公式ページの Encoding に書いてあるし、ここに書いていない情報も公式ページにある。もし興味を持ったらそちらを読むとさらに理解できる。

この記事は 2019-06-01 にErlang & Elixir Fest 2019で「Protocol Buffers(proto3) を Elixir で実装する」という発表をするための資料を書いていたら生まれた。

Protocol Buffersではキーとバリューを持つ構造化された情報を扱う。キーとバリューの定義情報はprotoファイルと呼ばれるフォーマットに記載する。簡潔なprotoファイルは以下のようになる。

message Test1 {
  optional int32 a = 1;
}

Protocol Buffersではprotoファイルとデータの2つを元にシリアライズしてバイナリを生成する。
逆にデシリアライズするときは、protoファイルとバイナリの2つを元にデータを復元する。

Test1 の a に 150 を設定したデータをProtocol Buffersでシリアライズするとわずか3バイト、2進数表現では 00001000_10010110_00000001 となる。Protocol Buffersにおける整数表現と、キーとバリューの扱い方という2点がわかれば、どうしてこうなるかを説明できる。

整数(Varint)の表現

整数の 1 という値は 00000001 で表現される。想像通りだろう。 300 はどうだろうか。その場合は 10101100_00000010 で表現される。よくある数え方だと 32768 + 8192 + 2048 + 1024 + 2 = 44034 だ。なぜこれが 300 になるのだろうか。

Protocol Buffersの整数は、最後の1バイト以外、最上位のビットmsb(Most Significant Bit)が 1 になっている。つまりmsbを左から1バイト毎にチェックしていき、そのバイトのmsbが 1 だと次のバイトも値の一部であるとわかる。msbが 0 だとそのバイトで値の表現が終わるとわかる。つまりmsbをみればバイナリのどこに値の切れ目があるか判断できる。

10101100_00000010 を左からバイト単位にみていくと、10101100 は最上位のビットが 1 なので次のバイトも数値の構成要素だと判断できる。続いて 00000010 は最上位のビットが 0 なのでこのバイトで数値の構成要素が途切れると判断できる。

整数を表すバイトがどこまで続くかわかったら、次に全てのmsbを取り除く。つまり7ビットにする。

   10101100_00000010
->  0101100  0000010

そして7ビットのグループをひっくり返す。最下位(Last Significant)の7ビットグループが最上位に、右から二番目の7ビットグループが左から二番目に……という形だ。

   0101100  0000010
-> 0000010  0101100

最後にこれを単なるバイト列として足し合わせて数値に読みかえる。繋ぎあわせた最上位のビットで桁が足りなくて空白になったところは 0 とみなしていい。

    0000010  0101100
->   000001_00101100
-> 00000001_00101100

すると 256 + 32 + 8 + 4 = 300 となる。というわけでProtocol Buffersでは 300 という整数を 10101100_00000010 と表現できる。

ここまでの知識で先程のべた Test1 の a に 150 を設定したデータの表現 00001000_10010110_00000001 の下位2ビット 10010110_00000001 が 150 を示していることを下記のとおり説明できる。

   10010110_00000001
->  0010110  0000001 msbを除去した
->  0000001  0010110 7ビットのグループをひっくり返した
->   000000_10010110 8ビットずつになるように右へ詰めた
-> 00000000_10010110 空白に0を埋めた

128 + 16 + 4 + 2 = 150

残りの上位1ビットは想像のとおり「Test1のa」を表している。次に説明しよう。

キーとバリューの表現

Protocol Buffersではデータをキーとバリューで表現するのだが、まだバリューに利用可能な整数表現しか学んでいない。キーとバリューの組み合わせをどのように行うか。実はProtocol Buffersのキー部分を深くみると2つの情報が含まれている。キー自身の情報とバリューの型表現だ。一つずつ説明しよう。

最初にキー自身の情報だ。Protocol Buffersでは、キーは整数として表現される。Protocol Buffersの設定ファイルprotoを再掲する。

message Test1 {
  optional int32 a = 1;
}

a = 1 と書いてある。a というフィールドはバイナリ表現にしたときに 1 番へ割り当てるという宣言だ。バイナリ表現には a という情報はどこにもなく、バイナリとprotoファイルを組み合わせないと元のデータへは復元できない。不便な面もあるものの、バイナリサイズを小さくするためにこうなっているのだろう。

次にバリューの型表現だ。これはキーに続くバリューの長さを把握できるように含まれている。先程の例 int32 a = 1 を例にとるとバリューの型表現は int32 に該当する。

つまり一対のキーとバリューを表したバイナリには、キーの整数表現、バリューの型表現、バリューの3要素が含まれている。

キーの整数表現はこれまでみてきた整数表現と変わらない。ただし通常とは異なり最後の3ビットだけはバリューの型表現に割り当てられている。バリューの型表現に3ビット持てると0-7まで8種類の型を表現できるがProtocol Buffersでは以下の表のとおり0-5の6種類が型として定義されている。そのうち3番と4番は利用しないので実質4種類だ。

Bits	Meaning	Used For
`000` (0)	Varint	int32, int64, uint32, uint64, sint32, sint64, bool, enum
`001` (1)	64-bit	fixed64, sfixed64, double
`010` (2)	Length-delimited	string, bytes, embedded messages, packed repeated fields
`011` (3)	Start group	groups (deprecated)
`100` (4)	End group	groups (deprecated)
`101` (5)	32-bit	fixed32, sfixed32, float

これを踏まえてTest1のaに150を設定したデータをProtocol Buffersでシリアライズした 00001000_10010110_00000001 をチェックすると最初のバイト 00001000 のmsbが1ではないので、1バイト目で情報が途切れている。この1バイトがキー(キーの整数表現、バリューの型表現)部分、残りはバリュー部分となる。

次にキー 00001000 のうち、最後の3ビット 000 はバリューの型表現である。表によりバリューは Varint 型であることがわかる。
残りがキー番号になる。そして残りの 00001 を数値に換算すると 1 となる。

つまりProtocol Buffersのバイナリ 00001000_10010110_00000001 はキー番号1番、バリューの型はVarint、そして前述したように残り2ビットのバリューは150を表しているということになるのだ。

ProtocolBuffersをより深く知るための参考リンク

Protocol Buffers のエンコーディング仕様の解説
今さらProtocol Buffersと、手に馴染む道具の話
この記事では話さなかったけど公式リンクにはある話
- 負の整数などをどう扱うか - ZigZag encoding という名前がかっこいい
- Protocol Buffersでの文字列
- Protocol Buffersの中にProtocol Buffersを埋め込める。そのバイナリ表現
- Protocol Buffersのフィールドは配列にもできる。そのバイナリ表現