F3: 未来のためのオープンソースデータファイルフォーマット [pdf]

背景は複雑なんだ。CMU、清華大学、Meta、CWI、VoltronData、Nvidia、SpiralDBの間で、単一のファイルフォーマットに統一するためのコンソーシアムを作る計画があったんだけど、CMUの弁護士がMetaのNDAの件でパニックになって、Velox Nimbleのプレビューにアクセスするのが難しくなって、結局その計画は頓挫したんだ。私は法律の専門家じゃないけど、MetaのNDAは合理的に思えたな。だから、約1年後に計画がダメになって、みんなそれぞれのフォーマットをリリースしたんだ。→ MetaのNimble: https://github.com/facebookincubator/nimble → CWIのFastLanes: https://github.com/cwida/FastLanes → SpiralDBのVortex: https://vortex.dev → CMU + 清華大学のF3: https://github.com/future-file-format/f3 研究の側では、私たち（CMU + 清華大学）は新しいエンコーダーを開発することには興味がなくて、WASMの埋め込み部分に集中したかったんだ。元々のアイデアは、Hannes@DuckDBからWes McKinney（私たちの共著者）への提案から来たんだ。Vortexの実装を使ったのは、Rustで書かれていて、少し手を加えればほとんどがWASMにコンパイルできたから。VortexはF3プロジェクトとは別のもので、サポートするためのエンジニアリングエネルギーがある。F3は今のところ学術的なプロトタイプなんだ。今年、ドイツ人もWASMを使った独自のファイルフォーマットをリリースしたけど、彼らはファイル全体をWASM化していて、個々のカラムグループではないんだ。→ ドイツ人: https://github.com/AnyBlox

カスタムの小さなベクター埋め込みデータベースをサンドボックス付きで送れるのが大きな勝利なの？ いや、これは将来のエンコーディング変更に向けた互換性レイヤーなんだ。例えば、ORCv2は新機能を新しいフォーマットバージョンにまとめようとしたから、今まで出荷されてないんだ。新しい機能を無効にした状態でライターを出荷して、サポート付きのリーダーを出荷して、最後にライターを新しいフォーマットで書き込むように切り替えるっていう流れだったんだよ。具体的には、浮動小数点エンコーディングの新しい反転ビットバージョンがあって、最大圧縮のために指数、仮数、符号を整数として送信するものだったんだ。もし新しいファイルと一緒にwasmシムを出荷できて、全リーダーがサポートするまでの1年以上の待ち時間をスキップできたら、もっと簡単に出荷できたのに。フォーマットの進展もあっただろうし、古いファイルが独自の情報を持っていれば、互換性を失うことなくコード内のリーダー実装を非推奨にできたんだ。今日、Sparkのバリアントタイプみたいなものはこれから恩恵を受けるだろうね。サブカラム化は、分割されたカラムからのすべての可能な再結合をサポートするインタプリタとしてではなく、バイトコードとして出荷する方がずっと簡単になるだろう。PS: ORCでtpc-hを調整したり、ライターのOOMを修正したりするために多くの夜を費やしたから、ベンチマークでそのビットを保持しているのを見ると心が温まるよ。

確かに、カラムストレージの利点は、すべての行を通してカラム全体をすぐにスキャンできることだよね。OSのバッファリングをうまく活用できるから、例えば「b = 'x'のときのaを選択する」みたいなクエリがすごく早いんだ。

カラム型ストレージは素晴らしいよ。複雑なネストされたスキーマをリーフ値に分解して、プリミティブとして保存できるから。リーフ値に直接アクセスできるから、IOやパースの手間が大幅に減るんだ。これらのフォーマットは実際には最上位レベルで行のグループにパーティション分けされていることに注意してね。ここでの大きな利点は、データページからApache Arrowのバッファを直接取得できること。提供されたWASMを使うか、ネイティブデコーダーを持ち込むことで実現できる。Parquetでは、これが現在非常に複雑なんだ。ParquetはDremelエンコーディングを使っていて、プリミティブ値と二つの整数ストリーム（繰り返しと定義レベル）を一緒に保存して、スキーマから構築された状態機械を使ってレコードを再構築するんだ。これらの整数ストリームを取得するのも難しい。Parquetは「RLE」に決まっていて、これはビットパッキングとランレングスエンコーディングの混合で、リファレンス実装ではビットパッキング部分だけで74,000行の生成コードを使ってる。だから、ParquetからArrowバッファを取得するのはかなりの手間がかかる。F3はこれをずっと簡単にして、将来にも対応できるはず。ここでの提案された利点の一つは、メタデータへのランダムアクセスができること。GeoParquetを使うときは、メタデータをSQLiteにインデックスしてる。そうしないと、例えばOverture Mapsで空間クエリを実行するのに約10分かかるところが、数ミリ秒で済むから。約500ファイルのフッターをパースする必要があって、約150MBのThriftをパースしてクエリしなきゃいけない。でも、GoogleのFlatbuffersを選ぶのはちょっと変だね。FlatBuffersのメモリ安全性は知られている問題だし[1]、これらの脅威を軽減するために生成されたコードが実際のパフォーマンス向上を示すとは思えない。実際、SQLiteデータベースを埋め込んじゃえばいいんじゃない？[1] https://rustsec.org/advisories/RUSTSEC-2021-0122.html

ちょっと同意するけど、もっと全体像があるよ。君が説明している状況は、すでにいろんな圧縮アプローチで起こっていることなんだ。たとえば、一般的な圧縮機を使う代わりにビットパックを選ぶこともあるし、圧縮機を完全に変えることもある。こういうことはWASMなしでも存在していて、ソフトウェアを新しい技術で更新した後にファイルを「トランスコード」つまり書き直さなきゃいけないってことだ。WASMでも同じで、ファイルを書き直すだけなんだ。確かに、これがイテレーションのコストを効率が悪く上に押し上げているのは同意するよ。全体的に見ると、これってかなり高くつくし、将来を見越す価値があるかは不明だね。エクサバイト規模のシステムで働いたことがあるけど、データの大部分を再エンコードするのは良くないと思う。

つまり…最初から10%-30%のパフォーマンス低下を受け入れて、将来的にデコーダーを改善する機会を永遠に失うってことだよね。WASMはバックアップとして使うものなんだ。もしネイティブデコーダーがインストールされているなら（例えば、クレートとして）、システムはそれを優先して使う。そうでなければ、WASMにフォールバックする。10-30%のパフォーマンス低下は、ファイルをまったく読めないよりは価値があるよ。

データとコードを混ぜるのは、典型的なセキュリティのミスだよね。ちょっと知られた個人が関わっているからって、ミスが少なくなるわけじゃないし。