Skip to content

Instantly share code, notes, and snippets.

@frsyuki

frsyuki/m5.md

Last active December 14, 2015 18:09
Show Gist options
  • Save frsyuki/5127658 to your computer and use it in GitHub Desktop.
Save frsyuki/5127658 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
m5.md

msgpackの変更案について-5

提案の目的

  • 互換性の影響を最小限にしつつ、文字列を透過的に扱えるようにする方法を提供する
  • MessagePackから分離された上位レイヤーが、MessagePackの仕様に変更を加えずに、独自の型を定義できるようにする
  • 将来的にMessagePackに新たな機能が追加されても、既存のコードに影響を与えないようにする

概要

  • Extension型を新設する
    • フォーマットとして FixExt, ext 8, ext 16, ext 32 を追加する
    • Extension型の一部（extension type=0）としてBinary型を定義する
  • アプリケーションは、Extension型を使って独自の型を定義できる
  • binary_extensionを有効にしたデシリアライザは、バイナリと文字列を区別して扱う
    • binary_extensionを有効にしていないデシリアライザは、既存のデータと実装と完全な互換性を維持する
  • Raw型は、曖昧なデータを格納する型にしたまま変更しない

文字列とバイト列

プログラムは3つの区分に分類することができる：

  • weak-string code: 文字列とバイト列の区別が曖昧なプログラム
    • 例：文字列とバイト列を区別する型がそもそも無い言語（PHP, C++, Erlang, OCaml, etc）で書かれたプログラム
    • 例：文字列を表すためにフラグ等の付加情報が使われるが、文字列なのに付加情報が付与されていないケースも存在する言語（Perl, etc）で書かれたプログラム
  • statically-typed strong-string code: 文字列とバイト列を明確に区別するプログラムで、プログラムが期待するオブジェクトの型情報が実行前に与えられている
  • dynamically-typed strong-string code: 文字列とバイト列を明確に区別するプログラムで、プログラムが期待するオブジェクトの型情報が実行前に与えられていない

weak-string code では、すべての文字列に対して「これは文字列である」とマーカを付与する、あるいはすべてのバイト列に「これはバイト列である」というマーカを新たに付与する作業は手間がかかる。従ってこれらの言語で書かれたプログラムで、文字列とバイト列が明確に区別できることを期待することは現実的ではない。

また、シリアライズ時にvalidateを行うと性能にインパクトがある。さらに、全言語のシリアライザにUnicodeの正しい取り扱いを実装にさせるには、Unicodeは複雑すぎる。従って、UTF-8文字列を格納する型があったとしても、そこに必ずvalidなUTF-8文字列しか入っていないと常に仮定することはできない。

しかし、 dynamically-typed strong-string code が受信者となる オブジェクトのやりとりでは、文字列として送信/保存したデータを文字列として、バイト列として送信/保存したバイト列をバイト列として、透過的に復元したいという要求が存在する。この要求は、その他の組み合わせの通信では存在しない。

この問題に対して、アプリケーションには2つの選択肢がある：

  • ambiguity-tolerant behavior: デシリアライズ側で、文字列とバイト列が区別されていないケースを許容する。シリアライズ側には文字列とバイト列を明確に区別することを要求しない。（今のmsgpackと同じ）
  • ambiguity-strict behavior: デシリアライズ側で、文字列とバイナリと列が明確に区別されていると仮定する 。シリアライズ側には文字列とバイト列を明確に区別することを要求する。

解決策

ambiguity-tolerant behavior と ambiguity-strict behavior が混在するケースは存在しないと仮定する。

  • ambiguity-strict behavior を採用するデシリアライザが存在する場合、すべてのデータで文字列とバイト列が明確に区別されていなければならない
  • そうでなければ、すべてのデシリアライザが ambiguity-tolerant behavior を採用しなければならない

ambiguity-strict behavior を採用するデシリアライザは、Raw型にはvalidなUTF-8文字列しか含まれていないと仮定し、バイト列は新設されるBinary型で保存されていると仮定する。

この制約によって、次の利点が得られる：

  • Raw型に加えてString型とBinary型の2つを追加する必要が無くなり、文字列を小さくシリアライズできる
  • バイト列を扱わないアプリケーションでは、文字列とバイト列の曖昧さを考慮する必要が無い
    • バイト列を扱わないアプリケーションは、文字列を扱わないプログラムよりずっと多いと仮定する
  • 型システムをシンプルに保つことができる

一方で、次の欠点がある：

  • デシリアライザを ambiguity-strict behavior に移行することが難しい
    • ambiguity-tolerant behavior を採用し続けるか、すべてのプログラムを更新し、すべてのデータを変換しなければならない

Note: 他の手法でも、この問題の解決は簡単にならないのでは？

型システムの変更

  • Extension: Extension tagと呼ばれる整数値とバイト列のタプルを表す
  • Binary: Extension型の一部（Extension tag=0）。バイト列を表す
  • Raw: UTF-8でエンコードされた文字列、もしくはバイト列を表す
    • アプリケーションは、Raw型にはUTF-8でエンコードされたvalidな文字列しか含まれていないと取り決めても良い（ambiguity-strict behavior）
    • それらのアプリケーションでは、Raw型にはvalidなUTF-8文字列しか含まれていないと仮定し、バイト列はBinary型で保存されていると仮定する

Raw型にUTF-8でエンコードされたvalidな文字列しか含まれていないと仮定しているアプリケーションで、デシリアライザがUTF-8としてinvalidなバイトシーケンスを含むRaw型のオブジェクトを受け取った場合の挙動は、実装に依存する。

フォーマットの変更

0xc0 11000000 nil          (Nil type)
0xc1 11000001 (never used)
0xc2 11000010 false        (Boolean type)
0xc3 11000011 true         (Boolean type)

0xc4 11000100 FixExt 4     (Extension type 4byte)   // new
0xc5 11000101 FixExt 5     (Extension type 5byte)   // new
0xc6 11000110 FixExt 6     (Extension type 6byte)   // new
0xc7 11000111 FixExt 7     (Extension type 7byte)   // new
0xc8 11001000 FixExt 8     (Extension type 8byte)   // new

0xc9 11001001 ext 8        (Extension type 8bit)    // new

...

0xd4 11010100 FixExt 0     (Extension type 0byte)   // new
0xd5 11010101 FixExt 1     (Extension type 1byte)   // new
0xd6 11010110 FixExt 2     (Extension type 2byte)   // new
0xd7 11010111 FixExt 3     (Extension type 3byte)   // new

0xd8 11011000 ext 16       (Extension type 16bit)   // new
0xd9 11011001 ext 32       (Extension type 32bit)   // new

0xda 11011010 raw 16       (Raw type 16bit)
0xdb 11011011 raw 32       (Raw type 32bit)

0xdc 11011100 array 16     (Array type 16bit)
0xdb 11011101 array 32     (Array type 32bit)

0xde 11011110 map 16       (Map type 16bit)
0xdf 11011111 map 32       (Map type 32bit)

Extension型

Extension型のフォーマットは次のようになる：

FixExt 1
    +--------+--------+--------+
    |  0xd5  |  0xTT  |XXXXXXXX|
    +--------+--------+--------+
    => 1 bytes of application-specific object

ext 8
    +--------+--------+--------+--------
    |  0xc9  |  0xTT  |XXXXXXXX|...N bytes
    +--------+--------+--------+--------
    => XXXXXXXX (=N) bytes of application-specific object

0xTT はExtension tagを表現する1バイトの整数である。

Binary型

Binary型はExtension型の一部であり、Extension tag == 0 であるデータである。

実装のガイドライン

シリアライザとデシリアライザは、アプリケーションが ambiguity-strict behavior と ambiguity-tolerant behavior を選択できるようにオプションを提供するべきである：

  • シリアライザ：
    • binary_extension=falseなら、バイト列はRaw型として保存する
    • binary_extension=trueなら、明確に区別できるバイト列はBinary型（Extension型 where tag=0）として保存する
    • weak-string code において文字列とバイト列を明確に区別できない場合、シリアライザは binary_extensionオプションに関わらずRaw型として保存する
    • 文字列とバイト列を明確に区別する方法が無いか一般的でない言語では、MessagePackのライブラリがバイト列にマーカーを付与するする方法を提供する（例えばラッパークラスのようなもの）
  • デシリアライザ
    • binary_extension=falseなら、Raw型を復元する際に、validationを一切行わない。文字列オブジェクトにvalidなUnicode文字列しか格納できない言語では、Raw型を文字列オブジェクトに復元しない（ambiguity-tolerant behavior）
    • binary_extension=falseなら、Binary型とRaw型を同一の型を使って復元しても良い
    • binary_extension=trueなら、Raw型を復元する際に、文字列型を返す（ambiguity-strict behavior）
    • binary_extension=trueなら、Raw型を復元する際に、validationを行っても良い。不正なバイト列を発見した場合の挙動は実装に依存するが、アプリケーションに操作を委譲する機能を実装することが推奨される。次のような実装が考えられる：
      • invalidなバイトシーケンスを発見したら、そのオリジナルのバイト列をフィールドに持つ特殊なオブジェクトのインスタンスを返す
      • invalidなバイトシーケンスを発見したら指定されていたコールバック関数を呼び出し、その関数の返値を返す

MessagePackの一般的な実装では、binary_extensionのデフォルト値はtrueになるだろう。binary_extensionをデフォルトで有効にしている実装は、ドキュメントで明示しなければならない。

将来の拡張

もし将来的に型が追加された場合は、次のような実装になるだろう（Time型を追加した場合の挙動）：

  • シリアライザ：
    • time_extension=trueなら、時刻オブジェクトを自動的にTime型を使用してシリアライズする
    • time_extension=falseなら、Time型は使用しない
  • デシリアライザ：
    • time_extension=trueなら、Time型を時刻オブジェクトとして返す
    • time_extension=falseなら、Time型は整数値とバイト列のタプルとして返す

MessagePackのラッパライブラリは、Extension型を使用してMessagePackの仕様に影響を与えずに独自の型を定義できる。

プロファイル

Basic Profile

Extension型（Binary型を含む）を除いたものを、MessagePack Basic Profile と呼ぶ。 アプリケーションは ambiguity-tolerant behavior を採用することが求められる。

Basic Profile に従って作成されたデータは、プログラムの実装に関わらず同じデータになり、アプリケーションから完全に疎結合化される。

Note: 既存のMessagePackの実装は、Basic Profileしかサポートしていない実装とまったく同一である

Application Profile

Extension型を加えた物を、MessagePack Application Profile と呼ぶ。 アプリケーションは ambiguity-strict behavior と ambiguity-tolerant behavior のどちらかを選択することができる。

アプリケーションは Extension型を使用して独自の型を追加できる。

Canonical Profile

Note: これは将来の議論である

  • mapのキーをRaw型に限定する
  • mapのキーをバイト順でソートする
  • Raw,Array,Map,整数のシリアライズで常にデータサイズが最小になるフォーマットを使用する

既存の実装のリリースに関するガイドライン

  • マイナーバージョンアップで、デシリアライザでExtension型tag=0（Binary型）にのみ対応し、Raw型と同様に扱うようにする
  • メジャーバージョンアップで、binary_extensionオプションに対応する
    • binary_extensionのデフォルト値をtrueにする場合は、リリースノートなどのドキュメントに明示する
  • メジャーバージョンアップで、シリアライザはExtension型に対応し、（MessagePack::Extensionのような）独自クラスのインスタンス、2要素の配列、または2要素のタプルを返す
  • メジャーバージョンアップで、デシリアライザはExtension型に対応し、（MessagePack::Extensionのような）独自クラスのインスタンスをExtension型を使用してシリアライズする

Q&A

FixExtの配置に意味はあるのか

デシリアライザとシリアライザの実装を簡潔にするため。

デシリアライザでは、次のようにして実装を最適化できる：

int length;
switch(b) {
case 0xc4..0xc8:
    length = b & 0x0f;
    goto fixext;
case 0xd4..0xd7:
    length = b & 0x03;
fixext:
    // …
    break;
}

もしくは：

if((0xc4 <= b && b <= 0xc8) || (0xc4 <= && b == 0xd7)) {
    length = (b & 0b1111) ^ ((b & 0b10000) >> 2);
    // …
}

シリアライザでは、次のようにして実装を最適化できる：

if(length <= 4) {
    int b = 0xd4 | length;
    // …
} else if(length <= 8) {
    int b = 0xc0 | length;
    // …
} else {
    …
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment