Gunosyデータ分析ブログ

Gunosyで働くデータエンジニアが知見を共有するブログです。

社内勉強会での発表内容の紹介 〜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 は 28 -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   |
+--------+~~~~~~~~~~~~~~~~~+

MessagePack の仕様を読んだ所感

MessagePack のフォーマットを見ていくと、可能な限り Prefix の 1 byte に情報を詰め込んでおり、設計が洗練されていると感じました。
普段の業務ではフォーマットなどの内部を意識せずに使用していますが、アルゴリズム勉強会のような機会で深掘りすると面白いですね。

おわりに

Gunosy ではアルゴリズム勉強会の他にも様々な社内勉強会が開催されているため、今後も積極的に参加してエンジニアとしての引き出しを増やしていこうと思います!

明日は UT さんのコスト削減に関する記事です!お楽しみに!!

*1:言語は python で、ライブラリは json と msgpack を使用しました

*2:JSON で 9 byte だと 999999999 < 232 までしか保存できない