Go to Qiita Advent Calendar 2024 Top
LoginSignup
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@haruyama480

Protocol Buffersのエンコード

Posted at

はじめに

protocol buffersに触れ、そのエンコード方法が気になったので https://developers.google.com/protocol-buffers/docs/encoding を翻訳しました。

元の英文にパラフレーズが多く、難しい日本語になりそうだったので表記ゆれを適当に統一しています。翻訳には一部google翻訳を利用しました。

以下、翻訳。

エンコーディング

  • 単純なmessageの例
  • 基礎となるvarint
  • messageの構造
  • その他の値型
  • embedded message
  • optional & repeated
  • フィールドの順序

このドキュメントでは、プロトコルバッファにおけるmessageのワイヤフォーマットについて説明します。 アプリケーションでプロトコルバッファを使用するのにこれを理解する必要はありませんが、異なるプロトコルバッファのフォーマットが、シリアライズ後のmessageのサイズにどのように影響するかを知ることは非常に役立ちます。

単純なmessageの例

次の非常に単純なmessage定義があるとします。1

message Test1 {
  optional int32 a = 1;
}

あるアプリケーションで、Test1というmessageを作成し、フィールドaに150をセットします。次に、このmessageをシリアライズしてバイト列にします。バイト列を調べてみると、次の3バイトになることがわかります。

08 96 01

一見小さな数の羅列ですが、どういう意味でしょうか？
これを説明していきます。

基礎となるvarint 2

単純なプロトコルバッファのエンコーディングを理解するには、最初にvarint3を理解する必要があります。varintは、任意の整数を1つ以上のバイト列にシリアライズする方法です。数値が小さいほど、バイト数も小さくなります。

末端のバイトを除くvarintの各バイトは、最上位ビット(msb)が設定されます。msbは、より多くのバイトが次に連なる(後続する)ことを示します。残りの下位7ビットは、数値を2の補数表現にしたときの7ビットのグループを格納するために使用されます。最下位グループほど最初のバイトで表現されます。4

例えば、数値1のvarintを考えます。これは以下の1バイトになります。1バイトなので、msbは設定されていません。

0000 0001

もう少し複雑な例として、300のvarintを見てみましょう。次の2バイトになります。

1010 1100 0000 0010

どうしたらこれが300だと理解できるでしょうか。まず、各バイトからmsbを削除します。これは、数値の終わりに到達したかどうかを示すためだけにあります。(この例だと、varintは2バイトあるため、最初のバイトに設定されています)

 1010 1100 0000 0010
→ 010 1100  000 0010

varintは最下位グループのを最初に格納するため、7ビットの2つのグループを逆順にします。 次に、それらを連結して最終的な値を取得します。

000 0010  010 1100
→  000 0010 ++ 010 1100
→  100101100
→  256 + 32 + 8 + 4 = 300

messageの構造

ご存知の通り、プロトコルバッファのmessageはkey-valueペアの連続です。messageのシリアライズでは、keyとしてフィールド番号(field number)が使用されます。各フィールドの名前と型は、デコード側のmessage定義(つまり、.protoファイル)を参照することによってのみ決定されます。

messageがシリアライズされると、key-valueペアが連結されてバイト列になります。messageがデコードされている間、パーサーは認識できないフィールド(unknown field5)をスキップできる必要があります。このようにして、messageの更新を知らない古いプログラムをクラッシュさせることなく、新しいフィールドを追加できます。これを実現するため、messageはワイヤフォーマットを採用しています。ワイヤフォーマットでは、各ペアの"key"は次の2つの値を含みます。.protoファイルで宣言されたフィールド番号と、後続のvalueの長さを知るのに必要なワイヤタイプ(wire type)です。 ほとんどの言語実装では、このkeyをタグと呼びます。

使用可能なワイヤタイプは次のとおりです。

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

シリアライズされたmessageの各keyは、(field_number << 3)| wire_typeの値を持ったvarintです。つまり、下位3ビットにワイヤタイプを格納します。

それでは、「単純なmessageの例」を振り返ってみましょう。バイト列の最初の数字は常にvarintで表現されたkeyであり、ここでは08です。msbを削除すると次になります。

000 1000

最後の3ビットからワイヤタイプ(0)を、次に3ビット右シフトしてフィールド番号(1)を取得します。 よって、フィールド番号が1で、次にくるvalueがvarintであることがわかりました。 前のセクションで示したvarintのデコーディング方法から、次の2バイトに値150が格納されていることがわかります。

96 01 = 1001 0110  0000 0001
       → 000 0001  ++  001 0110 (drop the msb and reverse the groups of 7 bits)
       → 10010110
       → 128 + 16 + 4 + 2 = 150

その他の値型

符号付き整数

前のセクションで見たように、ワイヤタイプ0に関連付けられているすべてのプロトコルバッファの型は、同じvarintとしてシリアライズされます。 しかし、負数のエンコーディングになると同じvarintでも、符号付きint型(sint32およびsint64)と標準的なint型(int32およびint64)の間に大きな違いがあります。int32またはint64の型を使用した場合、負数のvarintは常に10バイト使用します。実は、負数は非常に大きな符号なし整数と同等に扱われます。符号付きint型を使用した場合、ZigZagエンコーディングがvarintに使用されます。これははるかに効率的です。

ZigZagエンコーディングは、絶対値の小さい(たとえば、-1)整数が小さいvarintにシリアライズされるように、符号付き整数を符号なし整数にマップします。 これは、正と負の整数を前後に「ジグザグ」する方法で行われます。例えば、-1は1としてシリアライズされ、1は2としてシリアライズされ、-2は3としてシリアライズされます。これは次の表で確認できます。

Signed Original Encoded As
0 0
-1 1
1 2
-2 3
2147483647 4294967294
-2147483648 4294967295

つまり、値nは次のようにシリアライズされます。
(sint32の場合)

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

(sint64の場合)

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

2番目のシフト(n >> 31の部分)は算術シフトであることに注意してください。 言い換えると、そのシフトの結果は、すべてゼロビット(nが正の場合)またはすべて1ビット(nが負の場合)のいずれかです。

sint32またはsint64がパースされると、その値はデコードされて元の符号付き整数に戻ります。

非varint数値

非varint数値は単純です。ワイヤタイプ1(doubleとfixed64)は、固定の64ビットのデータを期待するようにパーサーに指示します。 同様に、ワイヤタイプ5(floatとfixed32)は、32ビットを期待するように指示します。どちらの場合も、リトルエンディアンの順序で値が格納されます。

文字列

ワイヤタイプ2(length-delimited)は、valueに次の2つのバイト列が来ることを示します。1つ目はvarintにシリアライズされたバイト数で、2つ目は指定されたバイト数分のデータです。

message Test2 {
  optional string b = 2;
}

bに「testing」をsetすると、次のようになります。

12 07 [74 65 73 74 69 6e 67]

[]内のバイトは「testing」のUTF-8です。 ここでのkeyは0x12です。 次のようにパースされます。

0x12
→ 0001 0010  (binary representation)
→ 00010 010  (regroup bits)
→ field_number = 2, wire_type = 2

バイト数を示すvarintには7が入っています。さらに読み進めると、私達がsetした7バイトの文字列が見つかります。

embedded message

Test1のmessageが埋め込まれたmessage定義があるとします。

message Test3 {
  optional Test1 c = 3;
}

再びTest1のフィールドaに150をsetし、シリアライズされた結果を見てみましょう。

1a 03 08 96 01

ご覧のとおり、最後の3バイトは最初の例(08 96 01)とまったく同じであり、その前に番号3が付いています。embedded messageは文字列とまったく同じように扱われます(ワイヤタイプ2)。

optional & repeated

proto2において、message定義にrepeatedフィールドがある場合([packed = true]オプションなし)、そのフィールド番号に対応するkey-valueペアは、シリアライズされたmessage内に0個以上存在し得ます。これらの繰り返されたkey-valueペアは、連続して現れる必要はありません。これらは他のフィールドに割り込まれる可能性があります。フィールド間の順序は失われますが、フィールド内の要素の順序はパース時に再現されます。proto3は、repeated フィールドにpacked エンコーディングを適用します。これについては後述します。

proto3の非repeatedフィールド、またはproto2のoptionalフィールドの場合、シリアライズされたmessage内に、そのフィールド番号に対応するkey-valueペアが0または1個存在します。

通常、シリアライズされたmessage内に、非repeatedフィールドのkey-valueペアが複数含まれることはありません。しかし、パーサーはそのケースに対処することが期待されます。数値タイプと文字列の場合、同じフィールドが複数回現れると、パーサーは最後に現れた値を受け入れます。埋め込まれた(embedded) messageフィールドの場合、パーサーは、Message::MergeFromメソッドと同様に、同じフィールドのkey-valueペアをマージしていきます。言い換えると、スカラーフィールドは既出のインスタンスが後出のインスタンスにより置き換えられ、単一のembedded messageはマージされ、repeatedフィールドは連結されます。これらのルールにより次の特性が得られます。2つのシリアライズされたmessageを連結してパースする処理と、2つのmessageを別々にパースしてその結果をマージする処理は、同じ結果を生みます。つまり、以下の２つの処理は同じです。6

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

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

この特性を利用すると、型がわからなくても2つのmessageをマージできるため、便利なケースがあります。

packed repeatedフィールド

バージョン2.1.0では、packed repeatedフィールドが導入されました。proto2では、[packed = true]オプションを用いて、packed repeatedフィールドを宣言します。proto3では、スカラー数値タイプのrepeatedフィールドがデフォルトでパックされます。packedはrepeatedフィールドのように機能しますが、シリアライズが異なります。1つも要素が存在しないpacked repeatedフィールドは、シリアライズされたメッセージ内に出現しません。 1つでも存在する場合は、フィールドの全要素は、ワイヤタイプ2(長さ区切り)の単一key-valueペアに詰め込まれます。 各要素は、前にキーがないことを除いて、通常と同じ方法でシリアライズされます。

たとえば、メッセージタイプが次のようになっているとします。

message Test4 {
  repeated int32 d = 4 [packed=true];
}

ここで、repeatedフィールドdに値3, 270, 86942を与えてTest4を作成するとします。 次に、シリアライズされた出力は次のようになります。

22        // key (field number 4, wire type 2)
06        // payload size (6 bytes)
03        // first element (varint 3)
8E 02     // second element (varint 270)
9E A7 05  // third element (varint 86942)

packed repeatedとして宣言できるのは、プリミティブ数値タイプ(varint、32ビット、または64ビットのワイヤータイプを使用する型)のみです。

通常、packed repeatedフィールドに対して複数のkey-valueペアをシリアライズする理由はありませんが、エンコーダーはそのケースを受け入れるように準備する必要があることに注意してください。この場合、payloadは連結されるべきです。各key-valueペアは、その要素数を含む必要があります。

プロトコルバッファのパーサーは、実際にpackedと宣言されてないrepeatedフィールドを、packedとしてパースできる必要があります。逆も然りです。これにより、前方互換性と後方互換性のある形で、既存のフィールドに[packed = true]を追加できます。

フィールドの順序

フィールド番号は、.protoファイル内で任意の順序で使用できます。その順序は、messageのシリアライズに影響しません。

messageのシリアライズ時、既知または未知のフィールド(unknown field)がどの順序で書き込まれるかは保証されません。シリアライズ順は実装依存であり、その実装は将来変更される可能性があります。 したがって、プロトコルバッファのパーサーはフィールドを任意の順序で解析できる必要があります。

含意

  • シリアライズされたmessageのバイト出力が安定していると想定しないでください。これは特に、シリアライズされた他のmessageを横流しするために、byteフィールドを持ったmessageで当てはまります。
  • デフォルトでは、同じmessageインスタンスに対してシリアライズ関数を呼び出しても、同じバイト出力が再現されない場合があります。 つまり、デフォルトのシリアライズは決定論的ではありません。
    • 決定論的なシリアライズは、特定のバイナリに対して同一のバイト出力がされることを保証します。 バイト出力は、バイナリのバージョンによって異なる場合があります。
  • 次のチェックは、messageのインスタンスfooに対して失敗する可能性があります
    • foo.SerializeAsString() == foo.SerializeAsString()
    • Hash(foo.SerializeAsString()) == Hash(foo.SerializeAsString())
    • CRC(foo.SerializeAsString()) == CRC(foo.SerializeAsString())
    • FingerPrint(foo.SerializeAsString()) == FingerPrint(foo.SerializeAsString())
  • 論理的に同等な２つのmessagefooとbarが、異なるバイト列にシリアライズされる可能性があるシナリオをいくつか例示します。
    • 一部のフィールドをunknownとして扱う古いサーバーが、barをシリアライズします。
    • 異なるプログラミング言語で実装され、フィールドを異なる順序でシリアライズするサーバーが、barをシリアライズします。
    • barに、非決定論的な方法でシリアライズされるフィールドがあります。
    • barに、シリアライズが再現されないmessageのバイト列を格納するフィールドがあります。
    • 実装の変更により異なる順序でフィールドをシリアライズする新しいサーバーが、barをシリアライズします。
    • fooとbarはどちらも個々のmessageを連結したものですが、連結順序が異なります。

  1. optionalはproto3で一時削除されましたが、v3.15で復活したようです https://qiita.com/disc99/items/a8ac2a264f322bc6d6e5 ↩

  2. 原題だと「Base 128 Varints」です。1バイトでmsbを除いて128まで表現できることから、このような原題になっていそうです ↩

  3. varintは、protocol buffers固有の概念です。variantとvar intがかかっていて気持ちのいい命名ですね ↩

  4. つまり、リトルエンディアンの順序でシリアライズされます ↩

  5. proto2ではデフォルトで保持 https://developers.google.com/protocol-buffers/docs/proto#updating proto3ではv3.5以上で保持 https://developers.google.com/protocol-buffers/docs/proto3#unknowns ↩

  6. 分配法則的と表現できます。parse(s1 + s2) == parse(s1) + parse(s2) ↩

1
1
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?