Protocol Buffersは遅いのか

# はじめに
Protocol Buffers でググると「[Protocol Buffersは遅い](http://frsyuki.hatenablog.com/entry/20081116/p1)」という記事が上位にヒットし、（記事公開から7年以上立っている現在でも）これをもって「Protocol Buffers は遅くて非効率」という印象を持たれることが多いようです。

しかし、この記事のベンチマーク実装は Protocol Buffers の性能特性を十分に活かしきれておらず、不公平な比較となっているように思われます。この記事では Protocol Buffers 寄りの視点で Protocol Buffers と MessagePack 比較を試みます。

## で、遅いんですか？
わかりません。遅いんじゃないでしょうか？（！）

今回はシリアライズ速度の比較は行いません。計測がめんどくさいのと、私は [ScalaPB](http://trueaccord.github.io/ScalaPB/) を使っているので C++ 実装のシリアライズ速度にあまり興味がないためです。

この記事では、 [Protocol Buffersは遅い](http://frsyuki.hatenablog.com/entry/20081116/p1) の読者が抱くであろう以下の疑問点について掘り下げます。

* なぜ protobuf エンコーディングのサイズは大きいのか
* 結局どういう用途に protobuf が適していて、どういう用途に MessagePack が適しているのか

（追記 - 2016/08/25）
ベンチマークをとってくれた人がいました。2016年時点でのC++実装では別に遅くないという結論だそうです。なるほど。
* [Protocol Buffersが本当に遅いのか確かめてみた](http://nojima.hatenablog.com/entry/2016/08/24/215002) 


# Wire format の比較
## 負数のエンコーディング
ベンチマーク結果でまず目を引くのが、符号付き整数のバイナリサイズです。MessagePack の8倍弱、protobuf の符号なしと比較しても4倍以上大きいというのは明らかに変です。

これは varint と呼ばれる protobuf の可変長の整数エンコーディング [^1] に起因します。varint では小さな数ほど少ないバイト数で表現されますが、負数は2の補数表現では最上位ビットが立っているために、常に 10 バイト消費するのです。

負になりうるフィールドには、`int32`/`int64` ではなく `sint32`/`sint64` を使うことが推奨されています。これは絶対値の小さな数ほど少ないバイト数で表現するので、このベンチマークのような入力に適しています。

```:test.proto
message Test2 {
    // (ベンチマークではタグ番号はファイル内でユニークになっているが、
    // 同一メッセージ内でユニークであれば十分)
    required int32 a = 3;
    required int32 b = 4;
}

message Test2Sint {
    required sint32 a = 3;
    required sint32 b = 4;
}
```


```:Console
scala> printMessage(Test2(-1, -2))
a: -1
b: -2
 -> 18 ff ff ff ff ff ff ff ff ff 01 20 fe ff ff ff ff ff ff ff ff 01 (22 bytes)

scala> printMessage(Test2Sint(-1, -2))
a: -1
b: -2
 -> 18 01 20 03 (4 bytes)
```

（完全な実装は [こちら](https://github.com/tayama0324/protobuf-benchmark) ）


ベンチマークと同等のコードを書いてみると、`Test2Sint` のサイズは 40MB となって `Test1` のサイズと一致しました。これは仕様に照らし合わせても妥当な結果です。

MessagePack でも同様の最適化は行われています。MessagePack の wire format では、7ビット以下の正の整数や5ビット以下の負の整数は、それぞれ型情報を含めて 1 バイトで表現できるようになっています。

## 型体系
protobuf では、`int32` を選ぶか `sint32` を選ぶかはプログラマの責任です。`int32` で定義したフィールドを `sint32` に変えることも、その逆も、シリアライザの互換性を損なうことになります。これは、`int32` も `sint32` も wire format 上では varint であるという情報しか持っていないためです。`int32` はそのまま varint としてシリアライズされ、`sint32` は `0 -> 0, -1 -> 1, 1 -> 2, -2 -> 3, 2 -> 4, ...` というようにマップ [^2] されたあと varint としてシリアライズされます。そのフィールドが `int32` か `sint32` かという情報はシリアライザ側にしかないので、`int32` でシリアライズしたものを `sint32` として読むことはできないのです。

一方 MessagePack フォーマットの型情報はもっと詳細で、整数型だけでも

* 7-bit positive
* 5-bit negative integer
* 8, 16, 32, 64-bit signed/unsigned integer

の10通り用意されています。このため wire format の型情報とペイロードのみから完全にデシリアライズできます。それだけでなく、プログラマはこれらの型の使い分けを意識する必要はなく、MessagePack ライブラリはシリアライズされる整数の値域に応じて最適な型を使い分けることさえできるのです[^3]。

MessagePack はデータのサイズや（プログラム上での）型に応じて wire format の型を使い分ける方針を取っていて、全部で 36 の型が定義されています。これは、varint, byte array, 32-bit fixed, 64-bit fixed のわずか 4 つ [^4] しか定義されていない Protocol Buffer フォーマットとは対照的です。Protobuf は必要最小限の型情報をバイナリに乗せ、残りはIDL/シリアライザで補う方針を取っているのです。

賢明な読者の皆さんはますます混乱してきたものと思います。先ほどの負数のメッセージは、 `int32` を `sint32` に変えたあとでさえ 40MB あり、わずか 24MB しかなかった MessagePack の倍近くあるのです。それでいて型情報も貧弱となれば、protobuf は一体どんな空間の無駄遣いをしているのでしょうか。

もちろんただ無駄遣いをしているわけではありません。Protobuf の wire format にはタグと呼ばれる情報が付与されています。

## タグ
Protocol Buffers では、たとえば 100 個の整数をシリアライズしたいからと言って 100 個の varint を直接ストリームに書くようなことはなく、基本的に `message` 単位でシリアライズします。

`message` のシリアライズ形式は、`(タグ, 型) -> ペイロード` という key-value ペアの列です。例えば、以下のスキーマ

```
message Test2 {
    required int32 a = 3;
    required int32 b = 4;
}
```

における `a = 1, b = 2` というメッセージをシリアライズしたとき、バイナリには `[(3, varint) -> 1, (4, varint) -> 2]` に相当する情報が載ることになります。タグは `message` の各フィールドの識別子となる整数です。長いフィールド名を直接シリアライズしては非効率なので、代わりにタグをシリアライズするわけです。40 - 24 = 16MB のオーバーヘッドはこのタグが占めているのです。

要するに、protobuf `message` は本質的に map なのです。MessagePack にも map はありますが、protobuf フォーマットは map を表現するために最適化されています。タグ番号が4ビット以下で表現できる場合、型情報の3ビットと合わせて1バイトに押し込みます。したがって protobuf の `message` と同等の情報を MessagePack map で表現した場合、value の型や値域にもよりますが、おおむね protobuf と同じか大きくなるでしょう。

シリアライズの単位が事実上 `message` 一択である protobuf と違って、MessagePack では array, int, string など任意の型のオブジェクトを直接シリアライズし交換したり永続化したりできます。これを考えると、protobuf message と MessagePack map を比べるのもまた不公平と言えるかもしれません。ただし、map の代わりに array などを使うのは拡張性に難があることにも留意すべきです。

3つのパラメータからなるオブジェクトを、長さ 3 の MessagePack array で表現するとしましょう。それらのパラメータが optional である場合、存在しないことを表すのに1バイトを消費して `Nil` を入れなければなりません。また、あるパラメータが deprecate された場合、そのパラメータの場所に永久に `Nil` を入れっぱなしにするか、それが嫌なら互換性を崩してシリアライザのバージョンを上げなければなりません。一方 map ならば、値が存在しないことを示すのには1バイトも使いません。Test2 のベンチマークで MessagePack が達成した 24MB というサイズは array を使ったもののように見えますが、このあたりの事情も差し引いて評価すべきでしょう。

要するに、バイナリサイズは一概に比較できるものではなく、選定基準に影響するほどの決定的な差もないといっていいでしょう。強いて言うならば、構造が複雑でシリアライザの互換性を保ったまま拡張していきたいものは protobuf、比較的単純で互換性を考慮する必要のない短命のものは MessagePack、 という使い分けはできるかもしれません。

が、使い分けにあたって真っ先に考慮すべきは IDL の存在です。

# IDL
Protobuf では IDL からシリアライザ実装を生成します。この IDL の最も重要なメリットは、異なる言語間でのデータの交換を安全に行えることにあります。

MessagePack で RPC をすることを考えてみましょう。サーバーとクライアントが同じ（あるいは、互換な）シリアライザを使わないと当然動作しませんが、これはどのように保証すれば良いでしょうか。サーバーとクライアントが同じ言語で書かれていれば話は簡単で、サーバーとクライアントが同じソースコードをコンパイルして使えば良い。ですが言語が異なる場合はそうもいかず、それぞれのシリアライズ形式が互換であることをプログラマが保証しなければなりません。

Protobuf ではその心配はありません。Protobuf ベースの RPC ではサーバーとクライアントが IDL を共有するのが一般的なので、相互運用性は簡単に保証できます。

IDL のもう一つのメリットは、それ自身がドキュメントになれることでしょう。MessagePack の場合、シリアライズされるオブジェクトのデータ構造を読み解くには、大抵シリアライズする言語の知識が要求されます。異なる言語を使いたいプログラマやチーム間で MessagePack を使うならば、データ構造のドキュメンテーションはどうしても必要になるはずです。一方 Protobuf では、IDL 文法は簡潔で読みやすく、インラインコメントを補えば十分にドキュメントとしての役割を果たします。このように、異なる言語間でデータを交換する場合には protobuf はかなり有利です。

IDL であることのデメリットもあります。IDL コンパイラを導入し、ビルド時に IDL コンパイルフェーズを挟まなければいけないのは、開発環境によっては面倒です。ただ、たとえば Java/Scala では Gradle/Maven/SBT プラグインが公開されているので、この手間は無視できるほど小さいです。

# まとめ
以下のような状況は MessagePack に有利に働きます。

* データ構造が比較的単純である
* データ構造の拡張性を考える必要がないか、滅多に拡張されない
* データの交換相手が十分狭い範囲に限られている
* 利用する言語が一つに定まっている
* 導入コストをできるだけ小さく抑えたい
* Protocol Buffers よりも少ない時間・空間計算量でシリアライズでき、その差が致命的である

Protocol Buffers が有利なのはその逆と言えるでしょう。

* データ構造が複雑である
* 将来、シリアライザの互換性を保ったままデータ構造を拡張したくなりそうである
* 多くのサービスとデータを交換する
* そのデータを利用する言語が多岐に渡る

一言で言えば、手軽に使いたいなら MessagePack、運用を見据えるなら Protocol Buffers ということになると思います。上手く使い分けていきましょう。

[^1]: 簡単な説明: 整数を7ビットごとに区切って追加の1ビットを補い、リトルエンディアンで並べる。補われる1ビットは、最上位バイトならば 0 、それ以外なら 1 である。

[^2]: この変換は `(n << 1) ^ (n >> 31)` でできます。

[^3]: 私は MessagePack を使ったことがないので既存の実装が本当にそうなっているかどうかわかりませんが、原理的にはそうであるはずです。間違っていたら突っ込みお願いします。

[^4]: 正確には、他に deprecated となった "group start", "group end" の2つが存在します。