エンコーディング − Protocol Buffers

Ruby版作るために部分的に訳してたので、せっかくだから完成させました。Protocol Buffersのバイナリエンコーディング詳細です。この情報が必要な人はあんまりいないとおもいますが、よろしければどうぞ。

http://code.google.com/apis/protocolbuffers/docs/encoding.html

エンコーディング

このドキュメントはプロトコルバッファメッセージのバイナリ・ワイヤ形式について説明しています。アプリケーションでプロトコルバッファを使用するだけであれば気にする必要はありませんが、プロトコルバッファの様々なフォーマットがエンコードされたメッセージのサイズにどう影響するかを理解することは非常に役に立つでしょう。

簡単なメッセージ

次のとても簡単なメッセージ定義があるとしましょう:

message Test1 {
  required int32 a = 1;
}

アプリケーションでTest1メッセージを作成し、aに150を設定します。それからメッセージをシリアライズして出力ストリームに流します。エンコードされたメッセージを見たとすると、次の3バイトが目に入るでしょう:

08 96 01

とりあえず、とても小さくて数字だけなのは分かりました − で、この意味は？それはこの先をみてください...

Base 128 可変長整数

単純なプロトコルバッファエンコーディングを理解するには、まず最初に可変長整数を理解する必要があります。可変長整数は1以上のバイトを使って整数をシリアライズする方法で、小さな数ほど少ないバイト数で済みます。

最終バイトを除いた可変長整数に含まれるバイトそれぞれには最上位ビット(most significant bit: msb)がセットされ、まだ続きのバイトがあることが分かります。それぞれのバイトの下位7ビットはare used to store the two's complement representation of the number in groups of 7 bits, least significant group first.

では、ここでは例として数値の1を考えます。これは一バイトなので最上位ビットはセットされません。

  0000 0001

さらに130を見てみます。これはもう少し複雑です。

  1000 0010 0000 0001

これが130であるとどうして分かるのでしょうか？まずそれぞれのバイトの最上位ビットは単に数値が最後まで到達したかどうかを示すだけなので除きます(見て分かるように、可変長変数がもう一バイト続いているので最初のバイトがセットされています):

  1000 0010 0000 0001
	→ 000 0010 000 0001

次に、先に書いたとおり、可変長整数は数値を最下位ビットを先に保存するので7ビットを一グループとして順番を入れ替えます。その後、それらを結合して最終的な値を得ます:

  000 0010 000 0001
	→ 000 0001 ++ 000 0010
	→ 10000010
	→ 128 + 2 = 130

メッセージ構造

ご存知のとおり、プロトコルバッファメッセージは一連のキー-値ペアです。バイナリバージョンのメッセージはキーとして単にフィールドの番号を使います。それぞれの名前と宣言された型はメッセージ型定義(つまり.protoファイル)を参照してでコードの最後に決定されます。

メッセージがエンコードされるとキーと値は一つのバイト列にまとめられます。メッセージがデコードされるときはパーサは理解できないフィールドをスキップしなければいけません。そうすれば、メッセージに新しいフィールドが付け加えられたとしても、そのことを知らない古いプログラムを妨げずに済みます。そのために、物理フォーマットでのメッセージそれぞれのペアにおける"キー"は次の二つの値からなります: .protoファイルに書かれているフィールド番号と、続く値の長さを得るのに必要な情報だけを含むワイヤタイプ

使用可能なワイヤタイプは以下の通りです:

タイプ	意味	対象
0	可変長整数	int32, int64, int32, int64, uint32, uint64, sint32, sint64, bool, enum
1	64ビット	fixed64, sfixed64, double
2	length-delimited	string, bytes, embedded messages
3	グループ開始	groups (deprecated)
4	グループ終了	groups (deprecated)
5	32ビット	fixed32, sfixed32, float

ストリームされるメッセージのキーは (field_number << 3) | wire_type という値を持つ可変長整数です。つまり、この数の最後の3ビットにワイヤタイプが収められています。

もう一度簡単な例を見てみましょう。ストリームの最初の数が常に可変長整数のキーであることはお分かりだと思います。ここではその数は08、つまり(最上位を除くと)次のようになります:

  000 1000

最後の3ビットからワイヤタイプ(0)を取り出して、右に3ビットシフトするとフィールド番号(1)が得られます。これでタグが1で続く値は可変長整数であることが分かりました。先のセクションで理解した可変長引数のデコード方法を使えば、次のバイトに格納されている値が150だと分かります。

  96 01 = 1001 0110 0000 0001
	        → 000 0001 ++ 001 0110 (最上位ビットを除いたあと7ビットごとに並びを逆にする)
	        → 10010110
	        → 2 + 4 + 16 + 128 = 150

値の型についてさらに

符号付整数

これまでのセクションから分かるように、ワイヤタイプ0に関連付けられているプロトコルバッファータイプは全て可変長引数にエンコードされます。しかし符号付整数型(sint32とsint64)と"標準的な"整数型(int32とint64)には負の値をエンコードする際、重要な違いがあります。もし負数にint32やint64を使ったら、それらは巨大な符号無し整数を効率的に扱うためのものなので、結果の可変長整数は常に10バイト長くなります。符号付の型を使えば、結果の可変長整数にはもっとずっと効率的なZigZagエンコーディングが使用されます。

ZigZagエンコーディングは符号付整数を符号無しの整数にマップして、絶対値が小さな数(例えば-1)は小さな可変長引数にエンコードされます。正数と負数を"zig-zag"に行ったり来たりして、次の表のように-1は1にエンコードされ、1は2に、-2は3に、と続きます。

符号付オリジナル	エンコードされた値
0	0
-1	1
1	2
-2	3
2147483647	4294967294
-2147483648	4294967295

つまりsint32ではnをエンコードするのに

  (n << 1) ^ (n >> 31)

が使用され、64ビット版では

  (n << 1) ^ (n >> 63)

が使用されます。

後半のシフト部分 −(n >> 31)の部分 − は算術シフトであることに注意してください。つまり、シフトの結果は(nが正のときは)全て0または(nが負のときは)全て1になります。

sint32やsint64がパースされると、値は元の符号付の値にデコードされます。

可変長整数以外の数

可変長整数以外の数値型は簡単です。ワイヤタイプ1のdoubleとfloatであればパーサはデータ長が64ビット固定だと期待でき、ワイヤタイプ5のfloatとfixed32のときも同様に32ビットだと期待できます。いずれの場合も値はリトルエンディアンバイトオーダーで格納されます。

文字列

ワイヤタイプ2(length-delimited)は、値部が可変長整数のデータ長の後にその長さのデータバイトが続くと言う意味です。

message Test2 {
  required string b = 2;
}

bの値を"testing"にすると次のようになります:

12 07 <span style="color:#ff0000">74 65 73 74 69 6e 67</span>

赤い部分がUTF8の"testing"です。ここではキーは0x12→tag=2, type=2になります。値の中にある長さを示す可変長整数は7で、lo and behold、7バイトの文字列が後に続くことが分かります。

組み込みメッセージ

これは例に出てきた型Test1が組み込まれたメッセージの定義です:

message Test3 {
  required Test1 c = 3;
}

エンコードされた形は以下です:

  1a 03 <span style="color:#FF0000;">08 96 01</span>

後半の3バイトは最初の例と全く同じ(08 96 01)であることが見てとれると思います。さらにその前には数値の3があります − 組み込みメッセージは文字列(wire type=2)と全く同じように処理されます。

オプショナル要素と繰返し要素

メッセージ定義に繰返し要素があるなら、エンコードされたメッセージには同じタグ番号からなる一つ以上のキー:値ペアが含まれます。繰返しの値は連続している必要はありません。他のフィールドが間に入ることもありえます。繰り返される要素の順番はパース時と同じになりますが、他のフィールドとの順番は失われます。

要素がオプショナルなら、エンコードされたメッセージにはそのタグ番号を持つキー:値ペアがあるかもしれないし、ないかもしれません。

通常であれば、エンコードされたメッセージにはオプショナルだったり繰り返されたりするフィールドのインスタンスが一つ以上含まれることはありません。けれども、パーサはそういった場合でも正しく処理できることが求められます。数値型と文字列型は、同じ値がなんども現れた場合、パーサは最後の値だけが有効であると見なします。組み込みメッセージフィールドの場合、パーサはMessage::MergeFromメソッドが呼ばれるのと同じように、複数のインスタンスを同じフィールドにマージします。つまり、後者のインスタンスにある単体のスカラフィールドは前者のもので置き換えられ、組み込みメッセージはマージされ、繰返しフィールドは結合されます。このルールの結果、エンコードされた二つのメッセージの結合は、二つのメッセージを別々にパースして結果のオブジェクトをマージするのと全く同じになります。つまり、以下は:

MyMessage message;
message.ParseFromString(str1 + str2);

次と全く同じです:

MyMessage message, message2;
message.ParseFromString(str1);
message2.ParseFromString(str2);
message.MergeFrom(message2);

この性質は時により有益で、タイプを知らない二つのメッセージをマージすることもできます。

フィールドの順序

.proto内でフィールド番号をどんな順序につけようと、メッセージがシリアライズされると、既知のフィールドは生成されるC++, Java, Pythonコードの中でフィールド番号に沿った順序になっていなければいけません。そうすることでコードをパースする時にフィールド番号が順に並んでいることに依存した最適化を行うことができます。ただし、プロトコルバッファーのパーサーはフィールドがどんな順序であってもパースできなければいけません。全てのメッセージが単純に一つのオブジェクトをシリアライズしたものからなるわけではなく、例えば、二つのメッセージを単純に結合してマージすることも時として有用だからです。

メッセージに不明なフィールドが存在したときは、現在のところJavaとC++の実装ではそれらを順序良く並んだ既知のフィールドの後に任意の順番で書き込みます。今のPythonの実装では不明なフィールドについては何も行いません。