RCFile，Parquet，ORCFile

この2ヶ月で，Cloudera/Twitter，Hortonworks からそれぞれ別の列指向ファイルフォーマットが公開されました．Parquet と ORCFile です．

この記事では，まず RCFile の復習をして，その後 Parquet と ORCFile それぞれの共通点と違いをおおまかに見ていこうと思います．コードレベルの詳細な違いについては，次回以降で見ていきます．

RCFile の復習

RCFile は　Record Columnar File の略で，Hive から利用できるストレージフォーマットです．特に，HDFS や S3 といった分散ストレージ上でパフォーマンスがでるように設計されています．

HDFS/S3 といったストレージでは，基本的にデータを計算機間で同じ負荷になるようにデータを分散配置します．このため，従来の列指向ストレージフォーマットのように適当に列毎にデータを分割してしまうと，1レコードにアクセスする度に，異なる計算機にアクセスしてデータを読み込む必要があります．これは，Hadoop が Vertica などの分散DB異なり，スキーマを持っているデータを処理するとは限らないために発生する問題です(スキーマがある場合は，ロード時にデータ配置の初期化ができる)．

RCFile では，複数の Record をまとめて固定長の row group として扱い，かつそれを列毎に並び替えます．row group の HDFS/S3のブロックサイズは，HDFSやS3のブロックサイズより小さいです．このように設定することで，ブロックが複数計算機に分割配置されることを抑えつつ，

1. オブジェクトのデシリアライズ・解凍を lazy に行うことができる．

2. 圧縮を効きやすくする．

という利点を得ることができます．RCFile の論文を見ると，この辺りの詳細を知ることができます．

ORCFile -The successor of RCFile-

次に，ORCFile の特徴について述べます．ORCFile は，RCFile の苦手な操作を克服するためにメタデータを追加したファイルフォーマットです．

ORCFile の提案がされた JIRA 上の資料によると，以下の違いがあるようです:

* RCFile では列の中で blob として保存されていたため，型ごとに圧縮をしたり，列の読み飛ばし(SQL 内で where を使ったりした場合)ができなかった．ORCFile ではメタ情報に 型と index を追加することにより，列ごとの圧縮や読み飛ばしができるようになった．

* RCFile では row group の先頭を見つけ出すためにフルスキャンが必要であったが，ORCFile ではメタデータの追加によりスキャンしなくても分割ができる．

RCFile は，row groups という単位で row を分割していたのに対して，ORCFile では row を stripes という単位で分割します．stripes ごとに index と footer がついており，そこにメタデータが入っています．また，1つの ORFile ごとに 1つの Postscript  というメタデータが保持されています．

index には各列のMin/Maxの値が入っており，Min/Max といった集計処理を効率的に処理するためのメタデータと，データの読み飛ばしを効率的に行うための10000レコードごとのポインタが入っています．

footer には stripes の一覧と，型と行番号，Count， min， max， sum といった集計処理用を効率的に処理するための一時結果が入っています(index と footer に同じデータが入っているのは，CPU 効率を上げるため?)．2014/4/23 追記: @maropu さんのご指摘で，index には stripe ごとの， footer はファイル全体の Min，Max etc. の情報が入っているとのことでした．これにより，特定の列の数値の合計を footer 全体の scan を避けて取得することができたりします．

postscript には，圧縮パラメータと footer の圧縮サイズが含まれています．

ORCFile は，2013/3/18 時点で，既に Hive にマージされています．また，ORCFile を Hive から便利に，効率良く使えるようにするための開発が Hive コミュニティ内で行われている最中です．

Parquet -Dremel's nested columnar storage -

次に，Parquet の特徴について述べます．

Parquet は，Dremel の Columnar Storage clone の列指向フォーマットです．Dremel の論文の中で述べられているネスト構造の列指向ストレージが実装されているのが特徴です．

Parquet を利用することにより，以下の利点が発生します:

1. JSON/XMLと比較して，ネスト構造のデータを非常に効率良く保存できる．これは，Dremel の論文の中で述べられている definition/repetition levels を用いたストレージフォーマットの効果による．

2. Null を多く含むような粗なデータについて，高い圧縮率を達成できる．これは Dremel の論文の中で述べられている Null を skip する最適化による．

encoding/decoding の仕方については，Dremel の論文と Parquet のドキュメント  が参考になります．

Parquet では，シリアライゼーションフォーマットとして Thrift を採用しています．なので，

https://github.com/Parquet/parquet-format/blob/master/src/thrift/parquet.thrift

を読むことで内容を理解できます．また，ドキュメント内にストレージフォーマットのイメージ画像があるので，これを見ると理解しやすいです．

RCFile は，row groups という単位でファイル内の row を分割していたのに対して，Parquet では row group という分け方を明示的にはしません．その代わりに列を Column Chunk という単位で分割して，保存します．

なので，厳密には列をまたがった read は計算機をまたぐ可能性がありますが，Column Chunk の大きさを HDFS/S3 のサイズより十分に小さな値に設定することで，ある程度通信は抑えられます(ファイル内で列同士はすべてとなりあっているため，Column chunk のサイズを調整することで間接的に row group を指定できる)．

Column Chunk は Page という単位で構成されています．デフォルトでは，1 Page は 8KB のようです．

parquet-format 自体は単なるファイル形式の定義なので，それを読み込み，encoding/decoding する部分が必要となります．

この部分は， parquet-mr として公開されています．parquet-mr のドキュメントを見ると，主要な処理系(Pig/hadoop MR)のサポートが既に公開されているようです，

また，シリアライズする際の型ですが，公式ドキュメントによると以下の型がサポートされているようです(なぜ INT96という型があるんだろう…?)．

BOOLEAN: 1 bit boolean

INT32: 32 bit signed ints

INT64: 64 bit signed ints

INT96: 96 bit signed ints

FLOAT: IEEE 32-bit floating point values

DOUBLE: IEEE 64-bit floating point values

BYTE_ARRAY: arbitrarily long byte arrays.

Impala と同時に公開された Apache Trevni との差分が気になる人が居ると思います(自分が気になった)．Cloudera の記事 によると，Apache Trevni との差分はAvro への依存を取り除き，Thrift を用いているという点です．

つまり，定義さえすれば，protobuf/avro/msgpack でも実装可能です．ただし，msgpack に関していえば， int 96 がネイティブの型として存在しないので，raw type を拡張するなどする必要がありそうです．

Parquet，ORCFile 間の共通点

Parquet と ORCFile は共に列指向のファイルフォーマットであり，読み込み時に不必要な列(カラム)のオブジェクト生成コストを飛ばすことで，raw file と比較してCPU コストを削減することができます．また，似たデータ・同じ型のデータが連続するため，圧縮が効きやすくなり，IO コストの削減が見込めます．

両者は，ともに HDFS や S3 といった分散ストレージ上のファイルとして利用可能です．これらのストレージの上で，従来の列指向DBのように列ごとにファイルをわけて実装を行うと，計算機をまたがって通信してしまう可能性がありますが，Parquet・ORCFile 共に通信コストをなるべく抑えるように1つのファイル内で row groups のように行ごとにデータを分割しています．

まとめ

RCFile の復習と，Parquet・ORCFileの概要について触れました．両フォーマットとも，分散ストレージ上でのアクセスを意識した効率の高い列指向のストレージフォーマットです．

次回はコードを読んでいきたいと思います．この文章は，WIP の文章などを基に構成しました．なるべく情報ソースを明らかにして構成したつもりですが，誤っている箇所などありましたら，是非ご指摘ください．