Retty Tech Blog

実名口コミグルメサービスRettyのエンジニアによるTech Blogです。プロダクト開発にまつわるナレッジをアウトプットして、世の中がHappyになっていくようなコンテンツを発信します。

カラムナフォーマットのきほん 〜データウェアハウスを支える技術〜

分析基盤

こんにちは、Retty.Inc ソフトウェアエンジニア兼データサイエンティストのchie（@chie8842）です。 好きなたべものは焼肉とみかんです。

現在Rettyでは、次世代分析基盤を構築しています。Rettyでは、サービス拡大に伴いログの急増や分析需要の拡大が見込まれるため、高いスループットとコストパフォーマンスを両立する、スケールするアーキテクチャ設計が求められています。

今回は、こうしたスケールするアーキテクチャ設計の実現のために理解しておくべきDWHのコア技術の一つである、カラムナフォーマットに焦点を当てて紹介します。

はじめに - カラムナフォーマットとは

カラムナフォーマットとは、データベースの分析用途に利用されるファイルフォーマットの種類の一つです。大量のデータを扱う際に効率的に圧縮してストレージコストを下げたり、計算時に必要なデータだけを取り出して計算コストを小さくできる設計がされています。
本稿では、分析基盤で利用されるファイルフォーマットの概要を紹介し、 そのあとに、カラムナフォーマットにおける符号化方式、データモデル、ファイルフォーマットについて説明しようと思います。

分析基盤で利用されるフォーマット

最近は分析基盤用途として、Hive、Presto、Sparkといった並列分散処理プロダクトやそれらのマネージドシステムであるAmazonのEMRやAthena、GCPのDataProc、そしてフルマネージドなBigQueryやRedShiftが利用されるようになりました。

これらのプロダクトで取り扱えるフォーマットは、大きく以下3つに分けることができます。

  • テキストフォーマット（例：CSV、JSON）
  • 行指向フォーマット（例：AVRO）
  • 列指向（カラムナ）フォーマット（例：Parquet、ORC）1

CSVやJSONといったテキストフォーマットは、人間からの可視性が高い、アプリケーション連携がやりやすいというメリットがあります。しかしながら、データベース用途のフォーマットとしては、人間からの可視性よりも、保存時の圧縮効率や機械による処理のしやすさを追求する必要があります。データベース用途に向いているフォーマットの種類としては、行指向フォーマットと列指向フォーマットがあります。
行指向フォーマットと列指向フォーマットの違いは、データの格納方式です。
行指向フォーマットは、行方向に連続してデータを格納するため、一つの行をまとめて操作することの多いOLTP処理に向いています。従来のデータベースはもともとこの行指向フォーマットが利用されてきました。
ストレージ技術などの発展により、DWH用途での利用を行うようになって、注目されるようになったのが列指向フォーマットです。列指向フォーマットは、列方向に連続してデータを格納する方式で、列単位でデータを取り出す分析用途に向いています。

主要なOSSのカラムナフォーマットのライブラリとしては、ParquetとORCがあります。
ParquetはTwitter社とCloudera社が、2010年のGoogleの論文Dremel: Interactive Analysis of Web-Scale Datasets（以下Dremel Paper）におけるデータレイアウトに関する内容をOSS実装したもので、ORCはもとはApache Hiveのためのフォーマットとして実装されたという背景の違いがあります。

カラムナフォーマットにおける符号化方式の基礎

カラムナフォーマットでは、データ型やカーディナリティ等の特性に応じて、様々な符号化方式から決定木等によって各列に最適なエンコード方式を選択します。これらの符号化技術自体は、行指向フォーマットでも利用されるものですが、カラムナフォーマットでは、型が同じデータが並んだり、規則的にインクリメントするデータが並ぶなど、符号化によるデータ圧縮が効きやすいというメリットがあります。

ここで符号化方式の一部を紹介します。

Null Suppression

これは、nullの多い列の圧縮に大きく寄与する技術です。nullの値を埋め込む代わりに、どこにいくつnullが存在するかの情報を保持することで、データサイズを小さくします。

Dictionary Encoding

以下の図のように、辞書情報を作成して、その辞書情報を利用して符号化する方式です。
データのカーディナリティの低いString形式のデータに有効ですが、データのカーディナリティが高くなると、辞書情報が肥大化して圧縮率は低くなります。 スクリーンショット 2017-06-05 2.25.22.png

Run-Length Encoding（RLE）

RLEは、繰り返しが続くデータに対して、下図のように繰り返し項目をまとめて保存する方法です。
繰り返しの長さが長くなるほど、圧縮率が高くなる特徴があります。
スクリーンショット 2017-06-05 2.24.41.png

Delta Encoding

Delta EncodingはTimestamp型などのインクリメンタルなデータで効果的なエンコード方式です。
Delta Encodingでは、まず最初に参照値を決め、それ以外の値をブロックに分けます。
それぞれのデータにおいて、一つ左隣の値との差分をとります。
この値の最も小さい値を使って標準化し、最後にビット数に直します。
図の例だと、最初の112bitから40bitと、3分の1程度に圧縮されていますが、データ量が多くなるほど圧縮率が高くなります。^2 スクリーンショット 2017-06-05 2.28.10.png

Bit-Vector Encoding

Bit-Vector Encodingは、Boolean型などの限られた値をとるデータに用いるエンコード方式です。
ある値と合致するかどうかを1と0で表したものを保持します。データのカーディナリティが著しく低い場合に有効です。
スクリーンショット 2017-06-05 2.34.59.png

Dremelのデータモデル

次に、BigQueryやParquetで実装されている、Dremelのデータモデルについて紹介します。
カラムナフォーマットについて書かれた論文に、GoogleのDremel Paperがあります。BigQueryはこのDremelの外部公開版であり、また、Parquetもこの論文をOSS実装したものです。
Dremelの新規性として、ネストされたデータに対応できる柔軟なデータモデルが挙げられます。下図（Dremel PaperのFigure1を引用）の左のように、record orientedな方式では、ネストされた型や特性の異なるデータが、並ぶ形となり、上記で述べたエンコードの効果を受けにくく、またネストされた一部のフィールドを利用する際にも、不必要なフィールドも含めてデコードする必要があります。対して右のcolumn orientedな方式では、同じフィールドのデータをまとめて保存でき、ネストされたデータの一部を利用する際には、木構造をたどることで必要なフィールドのみを抽出することができます。

スクリーンショット 2017-06-05 2.49.04.png

しかし、１つの行に何回同じフィールドが出現するかわからないようなrepetableなデータを扱う場合、そのデータ構造を欠落させることなく小さいオーバヘッドで木構造のデータを保持するための工夫が必要となります。
Dremelでは、下図（Dremel PaperのFigure2,3を引用）のように、反復レベル（Figure3の表におけるr列）と定義レベル（Figure3におけるd列）をもつことで、データ構造を復元できるようにしています。
スクリーンショット 2017-06-05 2.49.18.png 反復レベルと定義レベルの説明は以下のとおりです。

  • 反復レベル
    • あるレコードにおいてそのフィールドが初めて出現する場合は0とする
    • 2つ目以降については、親フィールド配下での反復回数を表す
  • 定義レベル
    • 一意でないフィールドの階層を表す

BigQueryでは、repetableなデータで構成されるデータを対象とした分析を行う場合などにこのデータモデルによるクエリ速度向上が見込まれます。

ただし、私個人の意見としては、Parquetの場合はクエリエンジン側がこのようなデータモデルに対応したものである必要があることもあり、現状でこのデータモデルの恩恵が生かされている例は少ないのではないかと考えています。

ファイルフォーマット

ParquetやORCでは、分散処理を行うことを前提として、Encoding/Compressionの単位、IOの単位、MapReduceの単位で処理しやすいようにデータが分割配置の工夫がされています。
以下の図はParquetのファイルフォーマットの説明図です。
スクリーンショット 2017-06-05 2.51.28.png File/Row Group/Column/Pageといった単位でデータを分割配置されていることがわかります。
また、上記の分割単位ごとに、ヘッダ/フッタにメタ情報を持っています。メタ情報の内容としては、

  • レコード数
  • データの最大値/最小値
  • メモリに展開した際のサイズ

などがあげられます。
メタデータを利用することで、データを読み込む際に、必要のないデータを読み飛ばすことができます。たとえば、

SELECT tbl1.colA, tbl2.colB FROM tbl1 JOIN tbl2 ON tbl1.colA == tbl2.colA;

といったクエリの場合、最終的に必要となるのは、tbl1のcolA、tbl2のcolAとcolBだけとなります。ParquetやORCを利用すると、ファイルスキャンの段階で、これらの必要なデータのみを抽出することが可能になります。
ただし、メタデータによる最適化が利用されるかどうかはクエリエンジンのオプティマイザによって作られる実行プランに依存します。

分析基盤におけるフォーマットの選定について

ここまでカラムナフォーマットのアーキテクチャと分析基盤における有効性についてざっくり説明しました。
上述したとおり、カラムナフォーマットにはクエリパフォーマンスをあげるための仕掛けが施されています。ただし、フォーマットはあくまで最適化しやすいデータ形式であって、それらを活かし切るかどうかは実際に処理を行うクエリエンジン側に依存します。
データの特性や利用するプロダクト、実行するクエリパターンによって、フォーマットを適切に使い分けることができるとよいと考えます。

まとめ

以上、目新しい技術というわけではないですが、分析基盤の縁の下の力持ち的なカラムナフォーマットの技術について、淡々と述べてみました。

尚、本稿の内容については、5/18のBIGDATA-JAWSにて、「カラムナフォーマットのきほん」というタイトルで発表をさせていただきました。

speakerdeck.com

Rettyでは、DWH技術を学びたい技術者を募集しています。
www.wantedly.com よろしくお願いいたします！

参考資料

  1. BigQueryとRedShiftも内部的にカラムナフォーマットが用いられている。 ↩