Multiple Dimension Spreadのご紹介

>100 Views

November 19, 18

スライド概要

MDS（Multiple Dimension Spread）は、スキーマレスのカラム型ストレージフォーマットです。
JSONのような柔軟な表現と、他のカラム型ストレージフォーマットに似た効率的な読み込みを提供します。

OSSとして公開しています。
興味がある方は気軽にご連絡ください！

GitHub:
https://github.com/yahoojapan/multiple-dimension-spread

Yahoo!デベロッパーネットワーク

@ydnjp

スライド一覧

2023年10月からSpeaker Deckに移行しました。最新情報はこちらをご覧ください。 https://speakerdeck.com/lycorptech_jp

またはPlayer版

埋め込む »CMSなどでJSが使えない場合

関連スライド

深層学習による自然言語処理入門: word2vecからBERT, GPT-3まで

Yahoo!デベロッパーネットワーク 135.6K

ゼロから始める転移学習

Yahoo!デベロッパーネットワーク 75.7K

ヤフーにおける WebAuthn と Passkey の UX の紹介と考察 #idcon #fidcon

idcon fidcon

Yahoo!デベロッパーネットワーク 65.2K

OpenID Connectとネイティブアプリを取り巻く仕様と動向 Yahoo! JAPANの取り組み #openid #openid_tokyo

openid openid_tokyo

Yahoo!デベロッパーネットワーク 52.6K

運用業務とスクラムは本当に組み合わせにくいのか︖運用業務が大半を占めるプロダクト開発での試行錯誤

devsumi

Yahoo!デベロッパーネットワーク 28.4K

ヤフーのオンプレ機械学習基盤AIPFについて #ml_kubernetes

ml_kubernetes

Yahoo!デベロッパーネットワーク 26.1K

各ページのテキスト

http://www.soumu.go.jp/johotsusintokei/whitepaper/ja/h29/html/nc121210.html

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

効率 • 処理で必要最小限の読み込み Col-1 Col-2 Col-3 Col-4 Col-5 Col-1 Col-2 Col-3 Col-4 Col-5 Network,Disk/IO Col-1 Col-4 Col-1 Col-4 Col-1 Col-4 Decompress/Copy InputStream Main Processing In-Memory Storage Volume Copyright (C) 2018 Yahoo Japan Corporation. All Rights Reserved. 19

20.

21.

22.

23.

24.

25.

26.

ファイルレイアウト File File Header Block-1 Block Metadata MDS形式のファイルとして認識するための情報や読み込みに必要な設定が含まれる。 Spread-1 Spread-2 … Spread-X Block-2 Block Metadata Spread-1 Block-X ファイルは複数のブロックで構成される。ブロックはカラムの構成や統計情報を保持するメタデータと複数の Spread で構成される。 Block Metadata Spread-1 … Copyright (C) 2018 Yahoo Japan Corporation. All Rights Reserved. Spread は複数の Column で構成される。 26

27.

Spread Root Spread は Root を持つ木構造で表現される。 Root Spread Col Col Col Child Spread Col Col Col 単一の Spread は Column[] と同等の意味を持つ。 Child Spread Col Copyright (C) 2018 Yahoo Japan Corporation. All Rights Reserved. Column は子を持つことができる。そのノード以下は子 Spread として表現される。 Col 27

28.

Column String : encoding class name String : compress class name Root String : column name ColumnType : column type Int : row count Col Col Col Int : raw data size Int : logical data size Int : cardinality Int : binary start offset Int : binary length Byte[] : data Copyright (C) 2018 Yahoo Japan Corporation. All Rights Reserved. 28

29.

File Header File File Header Magic BlockSize Class name length of BlockReader Byte[] 4byte Int 4byte Int 4byte Copyright (C) 2018 Yahoo Japan Corporation. All Rights Reserved. Class name of BlockReader Char[] Xbyte 29

30.

Block Block-1 Block index Byte[] Xbyte Copyright (C) 2018 Yahoo Japan Corporation. All Rights Reserved. Block Metadata Number of spread Int 4byte Spread row counts Metadata length Int[] Xbyte Int 4byte 30

31.

32.

Write/Read ETL Message deserializer serializer Message object MDSRecordReader Spread Spread MDSReader MDSWriter IColumnBinaryMaker IColumnBinaryMaker IBlockReader IBlockMaker Byte[] Spread List<ColumnBinary> List<ColumnBinary> Copyright (C) 2018 Yahoo Japan Corporation. All Rights Reserved. Processing Message object MDSRecordWriter Spread Message MDS File Byte[] 32

33.

Message のシリアライズ/デシリアライズ • 同時に開発したスキーマライブラリを利用 https://github.com/yahoojapan/dataplatform-schema-lib Avro JSON Etc… Reader AvroReader JsonReader Writer IParser AvroWriter JsonWriter Avro JSON Etc… 共通のインターフェースを通じてデータのアクセスと変換を提供 Copyright (C) 2018 Yahoo Japan Corporation. All Rights Reserved. 33

https://github.com/yahoojapan/dataplatform-schema-lib

34.

入力データからデータ構造を構築初期状態では何もデータ構造をもっていない、入力データに応じた構造が構築される。 Col-3 { “col-3” : “val” } Col-1 Null { “col-1” : “val” , “col-5” : “val” } Col-5 入力データで新規に出現したキーがある場合には、データ構造に追加される。 Null Null { “col-2” : “val” , “col-4” : “val” , “col-5” : “val” } message Col-3 Col-1 Col-2 Null Null Null Null Col-3 Null Col-4 Col-5 Null Null Null これによりスキーマレスな書き込みを実現。 Null Spread Copyright (C) 2018 Yahoo Japan Corporation. All Rights Reserved. 34

35.

カラム毎の独立したエンコーディング Col-1 Null Null Column Col-2 Null Null Column Copyright (C) 2018 Yahoo Japan Corporation. All Rights Reserved. Col-1 IColumnBinaryMaker Encoder ICompressor Col-1 ColumnBinary Col-2 IColumnBinaryMaker Encoder ICompressor Col-2 ColumnBinary 35

36.

オプティマイザ Column Analyzer カラムを解析し統計情報を（rows, cardinality…）を取得する。 IColumnAnalizeResult MDSWriter IColumnAnalizeResult IOptimizer 統計情報に応じてエンコーディング方式を選定する。 IColumnBinaryMaker Copyright (C) 2018 Yahoo Japan Corporation. All Rights Reserved. 36

37.

高速なファイルのマージ deserializer MDS File Message object File Header MDSRecordWriter Block-1 Spread Block-2 MDSWriter IColumnBinaryMaker MDS File File Header Block-1 List<ColumnBinary> List<ColumnBinary> IBlockMaker ファイルのマージはメッセージのデシリアライズ、カラムのエンコーディング/圧縮をスキップできる。ボトルネックをディスク/ネットワークIOとする事により HDFS 上に数GB単位のファイルを作成する事が可能。 Block-2 Byte[] Copyright (C) 2018 Yahoo Japan Corporation. All Rights Reserved. MDS File 37

38.

Splitable MDS File Processing File Header 128MB Block-1 128MB Block-2 128MB Block-3 128MB Block-4 XMB Block-5 Processing Processing MDS はブロック単位で並列して処理が可能。ブロックサイズはファイルのオプションで設定できる。デフォルトは128MBとなる。 Processing Processing Copyright (C) 2018 Yahoo Japan Corporation. All Rights Reserved. 38

39.

Projection Pushdown MDS File 読み込むカラムを設定 File Header Block-1 Spread-1 Processing [ col2 , col5] Skip Read Col-1 Col-2 Skip Col-3 Col-4 List<ColumnBinary> [ col-2,col-3] MDSReader Spread Read Col-5 ストレージから必要なカラムのデータのみを読み込み Copyright (C) 2018 Yahoo Japan Corporation. All Rights Reserved. 39

40.

Predicate Pushdown 入力に必要なデータの条件を設定 MDS File File Header Block-1 Skip Spread-1 Read Spread-2 Block-2 Skip Spread-1 List<ColumnBinary> MDSReader Spread-1 Spread-2 Spread Col-1 Spread-2 Block-3 Read Processing Col-1 < X and Col-3 = X Col-2 Col-3 Col-4 Col-5 Read Skip Read 確実にデータが含まれない行をスキップ確実にデータが含まれない Block , Spread をスキップ Copyright (C) 2018 Yahoo Japan Corporation. All Rights Reserved. 40

41.

Expand 展開したいArray要素のカラムを設定 Items (ARRAY) timestamp (BIGINT) total_price (BIGINT) 1516773762 1000 1516773765 200 Expand ‘items’ Items (Struct) item_id (STRING) price (BIGINT) number (INT) I_001 300 1 I_005 350 2 I_002 50 4 Spread Processing MDSReader Spread timestamp (BIGINT) total_price (BIGINT) 1516773762 Items (STRUCT) item_id (STRING) price (BIGINT) number (INT) 1000 I_001 300 1 1516773762 1000 I_005 350 2 1516773765 200 I_002 50 4 Expand Spread 指定されたカラムを展開した Spread を作成 Copyright (C) 2018 Yahoo Japan Corporation. All Rights Reserved. 41

42.

Flatten 平坦化したいカラムを設定 timestamp (BIGINT) total_price (BIGINT) 1516773762 Flatten items.item_id -> item_id items.price -> price items.number -> number Items (STRUCT) item_id (STRING) price (BIGINT) number (INT) 1000 I_001 300 1 1516773762 1000 I_005 350 2 1516773765 200 I_002 50 4 Spread MDSReader Processing Spread timestamp (BIGINT) total_price (BIGINT) item_id (STRING) price (BIGINT) number (INT) 1516773762 1000 I_001 300 1 1516773762 1000 I_005 350 2 1516773765 200 I_002 50 4 Flatten Spread 指定されたカラムを平坦化した Spread を作成 Copyright (C) 2018 Yahoo Japan Corporation. All Rights Reserved. 42

43.

Expand & Flatten Expand , Flatten を設定 Items (ARRAY) timestamp (BIGINT) total_price (BIGINT) 1516773762 1000 1516773765 200 Items (Struct) Processing Expand ‘items’ item_id (STRING) price (BIGINT) number (INT) I_001 300 1 I_005 350 2 I_002 50 4 Flatten items.item_id -> item_id items.price -> price items.number -> number MDSReader Spread timestamp (BIGINT) total_price (BIGINT) 1516773762 Spread Items (STRUCT) item_id (STRING) price (BIGINT) number (INT) timestamp (BIGINT) total_price (BIGINT) item_id (STRING) price (BIGINT) number (INT) 1000 I_001 300 1 1516773762 1000 I_001 300 1 1516773762 1000 I_005 350 2 1516773762 1000 I_005 350 2 1516773765 200 I_002 50 4 1516773765 200 I_002 50 4 Expand Spread Copyright (C) 2018 Yahoo Japan Corporation. All Rights Reserved. Expand & Flatten Spread 43

44.

45.

環境構築 $ git clone https://github.com/yahoojapan/multiple-dimension-spread.git $ cd multiple-dimension-spread/ $ mvn package $ bin/setup.sh Copyright (C) 2018 Yahoo Japan Corporation. All Rights Reserved.

46.

[beta]

JSON メッセージの変換
$ bin/mds.sh create -i src/example/src/main/resources/sample_json.txt -f
json -o /tmp/sample.mds
$ bin/mds.sh cat -i /tmp/sample.mds -o '-' # show whole data
{"summary":{"total_price":550,"total_weight":412},"number":5,"price":110
,"name":"apple","class":"fruits"}
{"summary":{"total_price":800,"total_weight":600},"number":10,"price":80
,"name":"orange","class":"fruits"}

Copyright (C) 2018 Yahoo Japan Corporation. All Rights Reserved.

47.

[beta]

Hive テーブルの作成
$ hive -i jars/mds/add_jar.hql
> create database test;
> use test;
> create external table sample_json (
summary struct<total_price: bigint, total_weight: bigint>,
number bigint,
price bigint,
name string,
class string
)
ROW FORMAT SERDE 'jp.co.yahoo.dataplatform.mds.hadoop.hive.MDSSerde‘
STORED AS INPUTFORMAT 'jp.co.yahoo.dataplatform.mds.hadoop.hive.io.MDSHiveLineInputFormat‘
OUTPUTFORMAT 'jp.co.yahoo.dataplatform.mds.hadoop.hive.io.MDSHiveParserOutputFormat‘
LOCATION '/tmp/ss';
> select * from sample_json;
{"total_price":550,"total_weight":412} 5 110 apple fruits
{"total_price":800,"total_weight":600} 10 80 orange fruits

Copyright (C) 2018 Yahoo Japan Corporation. All Rights Reserved.

47

48.

49.

機能機能 Row Store Compress Data type specific Change by column base Format Splittable Vectorization Pushdown Projection Predication Copyright (C) 2018 Yahoo Japan Corporation. All Rights Reserved. MDS ORC Text, JSON, ORC, Avro Text, Sequence, Avro ○ ○ ○ ☓ GZIP,LZ4,ZSTD ZLIB, SNAPPY, LZO ○ ○ ○ ○ ○ ○ ○ ○

50.

データ型基本型 Boolean Byte Bytes Short Integer Long Float Double String Null 説明 true/false 8ビット整数バイト列 16ビット整数 32ビット整数 64ビット整数 32ビット単精度浮動小数点数 64ビット倍精度浮動小数点数文字列欠損データ Copyright (C) 2018 Yahoo Japan Corporation. All Rights Reserved. 複合型 Array Map Struct Union 説明配列マップ構造体共用体(異なる型を保持)

51.

MDSの対応エコシステムエコシステム Hive Spark Presto Drill Impala Arrow 対応 ○ △※１ △※１ ☓ ☓ ○ URL hive.apache.org spark.apache.org prestodb.io drill.apache.org impala.apache.org arrow.apache.org ※１：本資料公開時にはOSSには公開していません Copyright (C) 2018 Yahoo Japan Corporation. All Rights Reserved.

52.

53.

54.

55.

56.

TPC-H 1000 - テーブル別のサイズテーブル別データサイズ（GB） 180 160 140 120 100 Law is better 80 60 40 20 0 region nation supplier part MDS Copyright (C) 2018 Yahoo Japan Corporation. All Rights Reserved. Apache ORC customer partsupp orders lineitem Apache parquet 56

57.

TPC-H 1000 - Hive CPU TIME(SEC) 100000 90000 80000 70000 60000 50000 Law is better 40000 30000 20000 10000 0 q6 q16 q14 q1 q15 q11 q22 q2 q12 MDS q20 Apache ORC ※テーブルスキャンオペレーション（Map）のみ計測 ※q19：いずれも実行に時間がかかりすぎたため計測を断念 Copyright (C) 2018 Yahoo Japan Corporation. All Rights Reserved. q13 q10 q4 q3 q7 q8 q5 q9 q17 q18 q21 Apache parquet 57

58.

TPC-H 1000 - Spark Executor CPU TIME(SEC) 80000 70000 60000 50000 40000 Law is better 30000 20000 10000 0 q6 q14 q12 q1 q10 q13 q3 MDS Apache ORC q20 q8 q7 q9 q4 q17 Apache parquet ※q2,11,15,18,21,22：テーブル作成の HQL を書き換えなければいけないため断念 ※q16,19：いずれも実行に時間がかかりすぎたため計測を断念 Copyright (C) 2018 Yahoo Japan Corporation. All Rights Reserved. q5 58

59.

Expand&Flatten 社内で利用しているArrayを使って状態を表しているログを利用元のデータ構造のまま SQL で展開して処理する場合と、利用するフィールドだけフラットにして単純な SQL を実行した場合の速度を比較する Items (ARRAY) timestamp (BIGINT) MDS File Copyright (C) 2018 Yahoo Japan Corporation. All Rights Reserved. total_price (BIGINT) Items (Struct) item_id (STRING) price (BIGINT) number (INT) I_001 300 1 I_005 350 2 151677376 2 1000 timestamp (BIGINT) total_price (BIGINT) item_id (STRING) price (BIGINT) number (INT) 1516773762 1000 I_001 300 1 1516773762 1000 I_005 350 2 Array 展開のSQL SQL ※図は処理のイメージであり実際に利用されているログではありません。 59

60.

61.

62.

63.

64.

65.

66.