社内勉強会での発表内容の紹介〜MessagePackの仕様を読む〜

こんにちは、 ML チームの k.oshiro です。

この記事は Gunosy Advent Calendar 2023 の 17 日目の記事です。
昨日の記事は yamayu さんの「サードパーティ Cookie を使わない広告効果計測〜Privacy Sandbox の Attribution Reporting API について〜」でした。

本記事では、社内勉強会の1つであるアルゴリズム勉強会で発表した「MessagePack の仕様を読む」を紹介します。

アルゴリズム勉強会とは

Gunosy では様々な社内勉強会が定期的に開催されており、アルゴリズム勉強会はそのうちの一つです。
その名の通りアルゴリズムを勉強する会で、最近では「フロイドの循環検出法」「レーティングアルゴリズム」などの発表がありました。
過去のブログでも社内勉強会について取り上げているので、そちらも読んでいただけると幸いです。

MessagePackの仕様を理解する

記事配信システムのキャッシュデータなどは MessagePack を使ってバイナリに変換して保存していることが多く、フォーマットについて興味が出たので調べたことを発表しました。

アルゴリズム勉強会の発表では、ざっと MessagePack の概要を紹介した後、 MessagePack Specification を読んでいくような流れで進めました。

MessagePack の概要

MessagePack は JSON 形式のオブジェクトを高速にシリアライズ、デシリアライズするためのデータ交換の仕様です。
JSON と同様に Array, Map (Object) という 2 つのデータ構造を持ち、リストと辞書の両方を扱うことができます。
特徴として、 MessagePack 形式での保存は JSON よりもファイルサイズが小さく、高速にデータ交換を行うことができます。

具体的には、JSON は文字列ベースでデータを保存しているためにファイルサイズが大きくなりやすく、読み書きに時間がかかりますが、MessagePack はバイナリでデータを保存しているため、ファイルサイズが小さく、読み書きも高速に行えます。
極端な例ですが、ユーザーあたり 500 記事を割り当て、ユーザー数が 10 万だった場合のダミーデータを用意し、速度計測を行いました*1。
下の表の計測結果から、 MessagePack が JSON よりも高速であることがわかります。

計測項目	JSON	MessagePack
書き込み時間	9.807s	0.713s
読み込み時間	3.279s	1.156s
ファイルサイズ	287M	144M

型システム

MessagePack で扱えるデータ型は 7 つあります。
加えて、今後拡張に使用するための extension 型があり、 Timestamp 型は extension を利用して追加されています。

型の種類

Integer
Nil
Bool
Float
Raw
- String
- Binary
Array
Map
Extension
- Timestamp

型の種類を確認した後は、MessagePack でこれらをどのように識別しているのか確認していきました。

MessagePack のデータフォーマット

MessagePack はデータ型の識別のために先頭 1byte に型ごとの Prefix を用意しています。
加えて、String や Binary、Array、Map などのデータ長が必要なデータ型に関しては、データ長を表すための 1~4 byte が付与されます。

例として、32 ~ 255 個の文字を含んだ String を保存する際のフォーマットを以下に示しました。
ここで、先頭 1 byte の 0xd9 は 2⁸ -1 個まで格納できる String 型を表します。
先頭から 2 byte 目の YYYYYYYY はその文字列（ data ）の文字数を表します。

このように、MessagePack では先頭 1byte で型を識別し、可変長のデータの長さを 1~4 byte 付与して表しているのです。
これらのフォーマットは msgpack/spec.md#formats にまとめられています。

+--------+--------+========+
|  0xd9  |YYYYYYYY|  data  |
+--------+--------+========+

データ量の削減

それぞれの型ごとにフォーマットを確認して、データ量の削減度合いを大雑把に把握します。

まずは Nil, Bool 型で考えます。
JSON の場合、Nil は null となり、Bool は false または true となります。
ASCII では 1 文字 1 byte であるため、Nil が 4 byte、Bool は 4 か 5 byte になります。
これを MessagePack では Nil を 0xc0 、Bool は 0xc2 または 0xc3 で表すためそれぞれ 1 byte しか使用しません。
Nil, Bool では 75% 程度削減されており、かなりデータ量が削減されていることがわかります。

また、Integer では正の整数 0~127 の範囲であれば、こちらも 0x00 から 0x7f の 1 byte だけで表現することできます。
逆に、負の整数であれば -1~31 までを 0xe0 から 0xff の 1 byte で表すことができます。
それ以外の値（例えば負数や Float など）は Prefix の 1byte に加えてデータ格納のための 1~8 byte が必要になります。
数値に制限はありますが、容量は最大でも 9 byte と軽量になることがわかります*2 。

一方で、Raw 型である String や Binary オブジェクトは byte 列をそのまま保持するため、データ量はほとんど変わりません。

Array, Map 構造の表現

Array, Map に関しても他のデータ型と同じで、Prefix を用いてデータ型を表しています。
ただし、 Map は key-value のペアで 1 つとして数えるため、実際のデータ数は 2 倍になります。
key-value には順序があり、偶数番目のオブジェクトが key になり、その次のオブジェクトが value になるような対応になっています。

# 要素数が15個以下の Array
+--------+~~~~~~~~~~~~~~~~~+
|1001XXXX|    N objects    |
+--------+~~~~~~~~~~~~~~~~~+

# 要素（key-valueの組）数が15個以下の Map
+--------+~~~~~~~~~~~~~~~~~+
|1000XXXX|   N*2 objects   |
+--------+~~~~~~~~~~~~~~~~~+