バイナリシリアライズ形式「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

仕様

※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の整数は1バイトに格納でき、データサイズを小さくすることができます。
フォーマットとしては、数値がそのままデータ型になるところがポイントです。たとえば 125(2進数で01111101)は、そのまま 01111101 になります。同様に -31(2進数で11100001) も、そのまま 11100001 になります。

nil, false, true

nil, false, trueは1バイトに格納します。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)に続いて2バイトの整数が続き、その整数の長さ分だけバイト列が続きます。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)に続いて2バイトの整数が続き、その整数×2個分だけ他のオブジェクトが続きます。オブジェクトは 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と比べてみます。

「整数の配列」と「文字列の配列」の2つのデータを使って比較しました。オブジェクトの生成にかかる時間などを除外して純粋にフォーマット自体の性能を測るため、C言語のライブラリを使って計測しています。

ベンチマークに使ったプログラムはここからダウンロードできます。→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の特徴の1つに、流れてくるデータを順次ストリーム処理していける点があります。
ネットワークプログラミングにありがちな処理で、最初にデータのサイズを受け取り、続いてそのデータのサイズ分だけバイト列を受け取る、という処理があります。CやC++で、あるいはselect(2)やpoll(2)を使ったプログラミングモデルでこのような処理を実装するのは少々面倒なわけですが、MessagePackでデータをシリアライズしておけば、メッセージとメッセージの切れ目を知ることができます。面倒な処理を書くことなく、MessagePoackのデシリアライザにデータを投げ込んでいくだけで、メッセージを1つずつ取り出すことができます。

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にあります。

*1:多倍長整数や日付、時間型なども入れられるかも。まだ決まっていません

*2:Web系のサーバーやクライアントはx86マシンが大半を占めているので、Little endianの方がいいかなと思いつつ…

*3:整数のデシリアライズ時間の多くは関数呼び出しのオーバーヘッドで、インライン化すると2Gbpsを超えます。