バイナリシリアライズ形式「MessagePack」
Googleが公開したバイナリエンコード手法であるProtocol Buffersは、クライアントとサーバーの両方でシリアライズ形式を取り決めておき（IDL）、双方がそれに従ってデータをやりとりするようにします。
この方法では高速なデータのやりとりができる反面、IDLを書かなければならない、仕様を変えるたびにIDLを書き直さなければならない（あらかじめしっかりとIDLを設計しておかないとプログラミングを始められない）という面倒さがあります。
※追記：Protocol BuffersのデシリアライザはIDLに記述されていないデータが来ても無視するので（Updating A Message Type - Protocol Buffers Language Guide）、仕様を拡張していっても問題ないようです。
一方JSONやYAMLなどのシリアライズ形式では、何も考えずにシリアライズしたデータを投げつけることができます。しかしJSONやYAMLはシリアライズ/デシリアライズに時間がかかるため、高速なスループット・低遅延を必要とするサーバー間の通信やプロセス間RPCなどでは、使いにくいと言えます。
そこで、JSONのように汎用的なシリアライズ形式でありつつ、バイナリベースで高速なシリアライズ形式MessagePackを開発しています。
MessagePackの特徴：
※追記：C++ APIではフォーマットを定義して型チェックもできるようになりました：サンプルコード
同じようなアプローチでBISON (Binary JSON)がありますが、MessagePackは仕様の美しさよりもバイナリ的な美しさを指向した感じになっています (^_^;
使い方はJSONとほぼ同じで、整数、Boolean、文字列、配列、連想配列、nilをバイト列にシリアライズすることができ、逆にシリアライズされたバイト列から元のオブジェクトを復元することができます。*1
Rubyでは↓こんな感じです。
require 'msgpack' packed = [0, true, false, nil].to_msgpack p MessagePack::unpack(packed) #=> [0, true, false, nil]
今のところCとRuby用のライブラリを開発しています。シンプルなフォーマットなので、他の言語用のシリアライザ/デシリアライザも比較的簡単に作れるはずです。
Ruby用のライブラリはgemでインストールできます。
$ gem install msgpack
- MessagePackのプロジェクトページ
- MessagePackのドキュメント
- 2008-11-10: msgpack-0.2.0
- 2008-12-06: msgpack-0.2.1
- 2008-12-10: msgpack-0.2.2
- 2009-03-01: msgpack-0.3.0
仕様
※2009-03-01追記：最新の仕様はドキュメントを参照してください：http://msgpack.sourceforge.jp/spec
//まだまだ固まっているわけではありませんが、今のところ考えている仕様はこんな感じです：
基本的には データ型, データ（整数やfloat、double）、または データ型, 長さ, データ, データ, データ, …（Raw、Array、Map）という形でシリアライズします。エンディアンはネットワークバイトオーダー（Big endian）です*2。
データ型には以下の種類があります
| 2進数 | 16進数 | |
|---|---|---|
| Positive FixNum | 0xxxxxxx | 0x00 - 0x7f |
| Negative FixNum | 111xxxxx | 0xe0 - 0xff |
| Variable | 110xxxxx | 0xc0 - 0xdf |
| nil | 11000000 | 0xc0 |
| (string ?) | 11000001 | 0xc1 |
| false | 11000010 | 0xc2 |
| true | 11000011 | 0xc3 |
| 11000100 | 0xc4 | |
| 11000101 | 0xc5 | |
| 11000110 | 0xc6 | |
| 11000111 | 0xc7 | |
| 11001000 | 0xc8 | |
| 11001001 | 0xc9 | |
| float | 11001010 | 0xca |
| double | 11001011 | 0xcb |
| uint 8 | 11001100 | 0xcc |
| uint 16 | 11001101 | 0xcd |
| uint 32 | 11001110 | 0xce |
| uint 64 | 11001111 | 0xcf |
| int 8 | 11010000 | 0xd0 |
| int 16 | 11010001 | 0xd1 |
| int 32 | 11010010 | 0xd2 |
| int 64 | 11010011 | 0xd3 |
| 11010100 | 0xd4 | |
| 11010101 | 0xd5 | |
| (big float 16 ?) | 11010110 | 0xd6 |
| (big float 32 ?) | 11010111 | 0xd7 |
| (big integer 16 ?) | 11011000 | 0xd8 |
| (big integer 32 ?) | 11011001 | 0xd9 |
| raw 16 | 11011010 | 0xda |
| raw 32 | 11011011 | 0xdb |
| array 16 | 11011100 | 0xdc |
| array 32 | 11011101 | 0xdd |
| map 16 | 11011110 | 0xde |
| map 32 | 11011111 | 0xdf |
| FixRaw | 101xxxxx | 0xa0 - 0xbf |
| FixArray | 1001xxxx | 0x90 - 0x9f |
| FixMap | 1000xxxx | 0x80 - 0x8f |
Positive FixNum, Negative FixNum
-31〜127の整数は１バイトに格納でき、データサイズを小さくすることができます。
フォーマットとしては、数値がそのままデータ型になるところがポイントです。たとえば 125（2進数で01111101）は、そのまま 01111101 になります。同様に -31（2進数で11100001） も、そのまま 11100001 になります。
nil, false, true
nil, false, trueは１バイトに格納します。nilは 0xc0 、falseは 0xc2 、trueは 0xc3 です。
float, double
IEEE 754形式の浮動小数点を格納します。
floatはデータ型+2バイトで 0xca 0xXX 0xXX 、doubleはデータ型+4バイトで 0xcb 0xXX 0xXX 0xXX 0xXX となります。
uintX, intX
整数は8ビット、16ビット、32ビット、64ビットの4つのサイズがあり、それぞれに符号付きと符号無しがあります。
FixNum、uintX、intXは、数値を入れられる最小のデータ型を選べばデータサイズを小さくすることができますが、シリアライズ速度を重視して大きなデータ型に入れてしまうこともできます。
フォーマットとしては、float、double、uintX、intXは、（1<<（データ型の下位2ビット））がそのままデータ長になっている点がポイントです。たとえば（1<<（uint 16の下位2ビット 01）= 2バイト、（1<<（int 32の下位2ビット 10）） = 4バイト です。
raw 16, raw 32
raw 16はデータ型（0xde）に続いて２バイトの整数が続き、その整数の長さ分だけバイト列が続きます。raw 32はデータの長さを表す整数が4バイトになります。
array 16, array 32
array 16はデータ型（0xdc）に続いて2バイトの整数が続き、その整数の長さ分だけ他のオブジェクトが続きます。array 32はデータの長さを表す整数が4バイトになります。
たとえば 0xdc 0x00 0x01 0x03 は、データ型がarray 16、長さが1で、要素は整数の3（FixNum） です。
arrayの中にarrayを入れたり、arrayの中にmapを入れたりすることができます。
map 16, map 32
mapは連想配列です。map 16はデータ型（0xde）に続いて２バイトの整数が続き、その整数×２個分だけ他のオブジェクトが続きます。オブジェクトは key, value, key, value, ... の順で並び、偶数番目がkeyで、そのkeyの次のオブジェクトがvalueです。
フォーマットとしては、raw X、array X、map Xは、（2<<（データ型の下位1ビット））がそのままデータ長（またはオブジェクトの数）になっている点がポイントです。
FixRaw, FixArray, FixMap
長さが0〜31のバイト列は、raw 16/32を使う代わりに、長さを表す整数をデータ型の部分に埋め込むことができます。
同じように長さが0〜15の配列や連想配列は、array 16/32やmap 16/32を使う代わりに、長さを表す整数をデータ型の部分に埋め込むことができます。
たとえば 0xa2 'a' 'b' は長さ2のバイト列で、中身は 'a' 'b' です。
ベンチマーク
MessagePackの性能をJSONと比べてみます。
「整数の配列」と「文字列の配列」の２つのデータを使って比較しました。オブジェクトの生成にかかる時間などを除外して純粋にフォーマット自体の性能を測るため、C言語のライブラリを使って計測しています。
- MacBook 2GHz CPU 2GB memory
- Mac OS X 10.5.4
- MessagePack C API 0.0.1
- YAJL (Yet Another JSON Library) 0.4.0
ベンチマークに使ったプログラムはここからダウンロードできます。→bench.c
整数
[0, 1, 2, 3, ..., 2^24]という整数の配列をバイト列にシリアライズするのにかかった時間と、そのバイト列をもう一度元の配列に戻すのにかかった時間を計測しました。
| サイズ | 時間 | 速度 | |
|---|---|---|---|
| MessagePack シリアライズ | 79.9MB | 0.701秒 | 912Mbps |
| MessagePack デシリアライズ | 79.9MB | 0.484秒 | 1320Mbps |
| JSON シリアライズ | 133MB | 8.11秒 | 132Mbps |
| JSON デシリアライズ | 133MB | 5.83秒 | 183Mbps |
MessagePackはJSONと比べて60%程度のサイズで済んでいます。JSONは32ビットの整数を保存するのに最大で10バイト（2^32 = 4294967296は10桁）必要ですが、MessagePackは最大でも5バイト（データ型1バイト+4バイト）で済みます（128までの整数はデータ型の部分に埋め込めるので、最小は1バイトで済みます）。
速度もJSONと比べるとずっと高速であることが分かります。デシリアライズ速度は1Gbpsを突破しており、多数のクライアントからメッセージを受け取ってもサーバー側の負荷は低そうです。*3
文字列
["", "a", "aa", "aaa", ..., "a"*2^15]という文字列の配列を使って、整数の場合と同じように計測しました。
| サイズ | 時間 | 速度 | |
|---|---|---|---|
| MessagePack シリアライズ | 512MB | 0.829秒 | 4939Mbps |
| MessagePack デシリアライズ | 512MB | 0.00581秒 | 705000Mbps |
| JSON シリアライズ | 512MB | 7.18秒 | 571Mbps |
| JSON デシリアライズ | 512MB | 8.87秒 | 462Mbps |
文字列の場合はMessagePackもJSONも、データサイズはほとんど変わりません。
一方速度では、突出したMessagePackのデシリアライズ速度が目立ちます。測定ミスではないハズ (^_^;
JSONの文字列のフォーマットは、「"aaa"」のように「"」から次の「"」が出現するまでが文字列になるので、1万バイトの文字列であれば1万回も「"」であるかどうかの比較が必要になります（さらにエスケープされた文字の処理も必要になります）。
一方MessagePackは「文字列の長さ, 文字列」というフォーマットになっているので、1万バイトの文字列であっても一度も比較せずにデシリアライズすることができます。この違いが影響していると思われます。
数KB、数MBという長さのバイト列をやりとりするような場面でも、MessagePackなら十分実用になる速度で使えそうです。
MessagePackのシリアライズ時間の大半は、memcpy()とrealloc()にかかった時間だと思われます。この辺りの処理をもっと賢くやれば、さらに高速化できそうです。
Stream parsing
MessagePackの特徴の１つに、流れてくるデータを順次ストリーム処理していける点があります。
ネットワークプログラミングにありがちな処理で、最初にデータのサイズを受け取り、続いてそのデータのサイズ分だけバイト列を受け取る、という処理があります。CやC++で、あるいはselect(2)やpoll(2)を使ったプログラミングモデルでこのような処理を実装するのは少々面倒なわけですが、MessagePackでデータをシリアライズしておけば、メッセージとメッセージの切れ目を知ることができます。面倒な処理を書くことなく、MessagePoackのデシリアライザにデータを投げ込んでいくだけで、メッセージを１つずつ取り出すことができます。
Rubyでは↓こんな感じでサーバープログラムが書けます。
require 'msgpack' class Server def initialize(sock) @sock = sock @mupk = MessagePack::Unpacker.new # MessagePackデシリアライザ @buffer = '' # バッファ @nread = 0 # @buffer内のデシリアライズ済みのバイト数 end # データが来たら呼ばれる def receive_data(data) # 到達したデータをバッファに追記 @buffer << data while true # @bufferをストリーム処理 @nread = @mupk.execute(@buffer, @nread) if @mupk.finished? # オブジェクトが復元できたら msg = @mupk.data # オブジェクトを取り出す log "message reached: #{msg.inspect}" @mupk.reset # デシリアライザをリセット @buffer.slice!(0, @nread) # デシリアライズが完了したバッファを捨てる @nread = 0 next unless @buffer.empty? # まだ@bufferが残っていれば再度デシリアライズする end break end rescue log "error while deserializing buffer (#{$!})" end def run while true begin data = @sock.sysread(1024) rescue log "connection closed (#{$!})" return end receive_data(data) end end def log(msg) puts "Server: #{msg}" end end rpipe, wpipe = IO.pipe # 別のスレッドでサーバーを立ち上げる thread = Thread.new( Server.new(rpipe) ) {|srv| srv.run } # サーバーにMessagePackでシリアライズしたデータを送る wpipe.write ["put", "apple", "red"].to_msgpack wpipe.write ["put", "lemon", "yellow"].to_msgpack wpipe.write ["get", "apple"].to_msgpack wpipe.close thread.join
このプログラムを少し改造して、RPCを実装するのもそれほど難しくないハズです。「オブジェクトを取り出す」のところでメソッドを呼び出したり、返り値を返すようにすればOK。
JSON-RPCの実装を参考にしつつ、デシリアライザの部分をMessagePackに変えれば、非同期なRPCも比較的簡単に実装できるはず。
困った点
- 文字列とバイト列を分けるか否か
- 多倍長整数や多倍長浮動小数点はどうするか
- 日付型とか入れる？
- C++のAPIはどのようなインターフェイスにするか
- Little endianにするかBig endianにするか
今の仕様では、文字列とバイト列は同じデータ型になっています。文字列とバイト列の違いは？と言うと、文字コードを入れるか否かくらいしか無いと思うのですが、それもUTF-8で統一だ、と決めてしまえばいいだけのように思います。実際にJSONはUTF-8しか入りません。（と言うよりJSONにはバイト列を入れられないだけ？）
多倍長整数や多倍長浮動小数点は、使う場面がよくわからないので未定です (^_^;
SQLにはdateやdatetimeなどの型がありますが、それを入れるかどうかも未定です。
MessagePackの特長を生かそうとすると、言語はC++などの高速な静的型付けなものを使うことになりそうですが、動的型付けなMessagePackと、静的型付けな言語をどのようなインターフェイスですりあわせるかは難しいところです。boost::anyやdynamic_castを使う？
エンディアンの問題は微妙です。ネットワークでやりとりするデータはBig endianが普通ですが、MessagePackを組み込み系やスーパーコンピュータなどで使うことはまず無さそうなので、Little endianのマシンで使うことになりそうです。そうするとバイトオーダーの変換が無駄になるわけですが、そのオーバーヘッドがそれほど大きいわけでもなく…。
MessagePackのソースコードはCodeRepos://lang/c/msgpackにあります。
