2024-09-22

Parquetフォーマット概観

Parquetは便利なファイル形式で、列志向のフォーマットとしてはデファクトの1つと言っても過言ではないでしょう。
ですが、jsonやcsvとは違い、ファイルを見ただけでどんな構造かわかるものではありません。
この記事は、Parquetの具体的な構造について記述します。

はじめに

この投稿は、Parquetの構造について、バイナリを見ながら確認するものです。

ただし、Parquetの大枠に注目した投稿なので、delta encodingやrun-lengthなど、個別の圧縮方法については取り扱いません。

※ Parquetの作成には https://github.com/parquet-go/parquet-go を使用していますが、goの知識は必要ありません

tldr

Parquetは以下の構造を持っています。

ファイルはRowGroupとメタデータに分かれている
- RowGroupの中にはColumnがある
- Columnの中にはPageがある
- Pageの中にデータの本体が入っている
Parquetはネストを全て展開して、全て別の列として扱われる (ネストや配列を入れ子にしていない)
- definition level と repetition level のおかげ

例えば{col1: "val1", col2: {col3: "val2"}}というデータをParquetに書くと、ファイルの構造は下のようになります。

{  
  RowGroups: [  
    {  
      Column(for "col1"): [{  
        Pages: [{  
          Header(thrift形式),  
          Values: [  
            "val1",  
            ...  
          ]  
        }]  
      }]  
    },  
    {  
      Column(for "col2.col3"): [{  
        Pages: [{  
          Header,  
          Values: [  
            "val2",  
            ...  
          ]  
        }]  
      }]  
    }  
  ],  
  MetaData(thrift)  
}

Parquetの特徴

Parquetは人気な形式であり、その中身に興味を持つような人はParquetの特徴をとっくに知っていることでしょう。
ここではこの投稿に必要な特徴だけ紹介します。

列志向である
Dremel(Googleの社内ツール)のファイルのフォーマットを基にしている

Parquetをhexdump

まず、構造を確認するためにファイルを作成します。
jsonで表すと、下のような内容です。(見当がつきやすいようにtext列にはplainエンコーディングを使用しています)

[  
  {"text": "text1"},  
  {"text": "text2"},  
  {"text": "text3"},  
  {"text": "text4"},  
  {"text": "text5"},  
]

ファイル作成のためのgoコード

parquet-goを使用し、以下のようなコードからファイルを作成します。

import (  
    "github.com/parquet-go/parquet-go"  
)  
  
type MyTypeSimple struct {  
    Text string `parquet:"text,plain"`  
}  
  
func write1() {  
    v := []MyTypeSimple{  
        {Text: "text1"},  
        {Text: "text2"},  
        {Text: "text3"},  
        {Text: "text4"},  
        {Text: "text5"},  
    }  
  
    err := parquet.WriteFile("./simple.parquet", v)  
    if err != nil {  
        panic(err)  
    }  
}

ファイル(307バイト)を見ると次のようになります。

$ hexdump -C simple.parquet  
00000000  50 41 52 31 15 06 15 5a  15 5a 15 ab a3 84 b4 03  |PAR1...Z.Z......|  
00000010  4c 15 0a 15 00 15 0a 15  00 15 00 15 00 12 00 00  |L...............|  
00000020  05 00 00 00 74 65 78 74  31 05 00 00 00 74 65 78  |....text1....tex|  
00000030  74 32 05 00 00 00 74 65  78 74 33 05 00 00 00 74  |t2....text3....t|  
00000040  65 78 74 34 05 00 00 00  74 65 78 74 35 19 12 00  |ext4....text5...|  
00000050  19 18 05 74 65 78 74 31  19 18 05 74 65 78 74 35  |...text1...text5|  
00000060  15 00 19 16 00 00 19 1c  16 08 15 92 01 16 00 00  |................|  
00000070  00 15 04 19 2c 48 0c 4d  79 54 79 70 65 53 69 6d  |....,H.MyTypeSim|  
00000080  70 6c 65 15 02 00 15 0c  25 00 18 04 74 65 78 74  |ple.....%...text|  
00000090  25 00 4c 1c 00 00 00 16  0a 19 1c 19 1c 26 00 1c  |%.L..........&..|  
000000a0  15 0c 19 15 00 19 18 04  74 65 78 74 15 00 16 0a  |........text....|  
000000b0  16 92 01 16 92 01 26 08  3c 58 05 74 65 78 74 35  |......&.<X.text5|  
000000c0  18 05 74 65 78 74 31 00  19 1c 15 06 15 00 15 02  |..text1.........|  
000000d0  00 00 16 cc 01 15 16 16  9a 01 15 32 00 16 92 01  |...........2....|  
000000e0  16 0a 19 0c 16 08 16 92  01 00 19 0c 18 37 67 69  |.............7gi|  
000000f0  74 68 75 62 2e 63 6f 6d  2f 70 61 72 71 75 65 74  |thub.com/parquet|  
00000100  2d 67 6f 2f 70 61 72 71  75 65 74 2d 67 6f 20 76  |-go/parquet-go v|  
00000110  65 72 73 69 6f 6e 20 30  2e 32 33 2e 30 28 62 75  |ersion 0.23.0(bu|  
00000120  69 6c 64 20 29 19 1c 1c  00 00 00 ba 00 00 00 50  |ild )..........P|  
00000130  41 52 31                                          |AR1|

ASCIIを見ると、3行目からtext1,text2,text3...とデータが入っていることが確認できます。
このファイルを使ってParquetの中身を紐解いていきます。

※ 見やすさのため、この記事ではバイトの位置を0x00からの値で表記します。例えば、16バイト目(03)は、16(0x0f)と書きます。(0列からf列までが1行、と見る)

メタデータとファイル構造

Parquetは、公式の図にあるように、Magic Number, RowGroup, Footer, Footer length, Magic Numberで構成されています。
この章では、前章で作成したファイルのデータを基に、Parquetのデータ構造を見ていきます。

https://parquet.apache.org/docs/file-format/ より

まず最初に見つかるのが、ファイルの最初と最後にあるMagic Numberです。
前章のhexdumpの結果にも最初と最後に"PAR1(50 41 52 31)"という文字が見つかります。

さて、Parquetを読むには、まずFooterにあるファイル全体のメタデータを参照するところから始まります。
Footerの長さが最後から数えて8~4バイト目にあるので、そこからFooterの場所を計算します。(little endian)
前章のhexdumpの例では、300~303バイト目(0x12b~0x12e)にある、186(ba 00 00 00)がFooterの長さです。

Footerの長さがわかったので、Footerからファイルのメタデータを抜き出します。
といっても、Footerにはメタデータしかないので、実際にはFooterをそのまま抜き出すだけでメタデータが取り出せます。
前章のhexdumpでは長さが186バイトなので、114(0x71)~299(0x12a)バイトがメタデータ部分です(15 04 19 2c ~ 1c 00 00 00部分)

ParquetのメタデータはThriftのThriftCompactProtocol形式でシリアライズされています。
parquet-formatリポジトリにある定義を基にメタデータを読むと、以下の情報が入っているとわかります。

{  
  "version": 2,  
  "schema": [  
    { "name": "MyTypeSimple", "num_children": 1 },  
    {  
      "type": "BYTE_ARRAY",  
      "repetition_type": "REQUIRED",  
      "name": "text",  
      "converted_type": "UTF8",  
      "logicalType": { "STRING": {} }  
    }  
  ],  
  "num_rows": 5,  
  "row_groups": [  
    {  
      "columns": [  
        {  
          "file_offset": 0,  
          "meta_data": {  
            "type": "BYTE_ARRAY",  
            "encodings": ["PLAIN"],  
            "path_in_schema": ["text"],  
            "codec": "UNCOMPRESSED",  
            "num_values": 5,  
            "total_uncompressed_size": 73,  
            "total_compressed_size": 73,  
            "data_page_offset": 4,  
            "statistics": { "max_value": "text5", "min_value": "text1" },  
            "encoding_stats": [  
              { "page_type": "DATA_PAGE_V2", "encoding": "PLAIN", "count": 1 }  
            ]  
          },  
          "offset_index_offset": 102,  
          "offset_index_length": 11,  
          "column_index_offset": 77,  
          "column_index_length": 25  
        }  
      ],  
      "total_byte_size": 73,  
      "num_rows": 5,  
      "file_offset": 4,  
      "total_compressed_size": 73  
    }  
  ],  
  "created_by": "github.com/parquet-go/parquet-go version 0.23.0(build )",  
  "column_orders": [  
    { "TYPE_ORDER": {} }  
  ]  
}

メタデータには色々な情報が入っていますが、本記事ではcolumnsの中の情報が重要です。

RowGroup, Column, Page内容の取得

前節でファイルのメタデータを取得できました。
更にcolumnの情報を取得します。

メタデータを見ると、row_groupsフィールドがあり、その中にcolumnsフィールドがあることがわかります。
columnsフィールドは配列です。今の例ではtext列しかないので、今回は1つです。

そのcolumnの中には最初のPageの始点(data_page_offset=4)とcolumn全体のバイト数(total_compressed_size=73)を表すフィールドがあります。
これが、text列のデータが入っている場所を示しています。
つまり、この例ではファイルの5(0x4)~77(0x4c)バイト目がcolumnの対象です。

ファイルのhexdumpを再掲します。

$ hexdump -C simple.parquet  
00000000  50 41 52 31 15 06 15 5a  15 5a 15 ab a3 84 b4 03  |PAR1...Z.Z......|  
00000010  4c 15 0a 15 00 15 0a 15  00 15 00 15 00 12 00 00  |L...............|  
00000020  05 00 00 00 74 65 78 74  31 05 00 00 00 74 65 78  |....text1....tex|  
00000030  74 32 05 00 00 00 74 65  78 74 33 05 00 00 00 74  |t2....text3....t|  
00000040  65 78 74 34 05 00 00 00  74 65 78 74 35 19 12 00  |ext4....text5...|  
00000050  19 18 05 74 65 78 74 31  19 18 05 74 65 78 74 35  |...text1...text5|  
00000060  15 00 19 16 00 00 19 1c  16 08 15 92 01 16 00 00  |................|  
00000070  00 15 04 19 2c 48 0c 4d  79 54 79 70 65 53 69 6d  |....,H.MyTypeSim|  
00000080  70 6c 65 15 02 00 15 0c  25 00 18 04 74 65 78 74  |ple.....%...text|  
00000090  25 00 4c 1c 00 00 00 16  0a 19 1c 19 1c 26 00 1c  |%.L..........&..|  
000000a0  15 0c 19 15 00 19 18 04  74 65 78 74 15 00 16 0a  |........text....|  
000000b0  16 92 01 16 92 01 26 08  3c 58 05 74 65 78 74 35  |......&.<X.text5|  
000000c0  18 05 74 65 78 74 31 00  19 1c 15 06 15 00 15 02  |..text1.........|  
000000d0  00 00 16 cc 01 15 16 16  9a 01 15 32 00 16 92 01  |...........2....|  
000000e0  16 0a 19 0c 16 08 16 92  01 00 19 0c 18 37 67 69  |.............7gi|  
000000f0  74 68 75 62 2e 63 6f 6d  2f 70 61 72 71 75 65 74  |thub.com/parquet|  
00000100  2d 67 6f 2f 70 61 72 71  75 65 74 2d 67 6f 20 76  |-go/parquet-go v|  
00000110  65 72 73 69 6f 6e 20 30  2e 32 33 2e 30 28 62 75  |ersion 0.23.0(bu|  
00000120  69 6c 64 20 29 19 1c 1c  00 00 00 ba 00 00 00 50  |ild )..........P|  
00000130  41 52 31                                          |AR1|

つまり、15 06 15 5a ~ 65 78 74 35の部分ですね。
更に、columnの最初には最初のpage用のメタデータ(Page Header)が入っています。
このメタデータもparquet-formatで定義されているthriftなので、Footerと同じようにデシリアライズすると、次のデータが取得できます。

{  
  "type": "DATA_PAGE_V2",  
  "uncompressed_page_size": 45,  
  "compressed_page_size": 45,  
  "crc": -457214166,  
  "data_page_header_v2": {  
    "num_values": 5,  
    "num_nulls": 0,  
    "num_rows": 5,  
    "encoding": "PLAIN",  
    "definition_levels_byte_length": 0,  
    "repetition_levels_byte_length": 0,  
    "is_compressed": false  
  }  
}

このthriftが終わるのが32(0x1f)バイト目なので、compressed_page_sizeの値(45)を考えた、33(0x20)から77(0x4c)バイト目がデータの本体だとわかります。(05 00 00 00 ~ 65 78 74 35)

データの取得

前節で33(0x20)から77(0x4c)バイトがデータの部分とわかりました。

データのバイナリは05 00 00 00 74 65 78 74 31 05 00 00 00 74 65 78 74 32...となっています。
このファイルはplainエンコーディングを使用しているので、最初に4バイトで文字長があり、その後に文字が続きます。
つまり、最初が5バイトのテキスト(74 65 78 74 31=text1)、次も5バイトのテキスト・・・と続きます。
なので、データには[text1, text2, text3, text4, text5]が入っているとわかるわけです。

ファイルには以下のデータを入れているので、データが正しく取得できたことがわかります。

[  
  {"text": "text1"},  
  {"text": "text2"},  
  {"text": "text3"},  
  {"text": "text4"},  
  {"text": "text5"},  
]

データにアクセスできた

これで、Parquetからデータを取り出すことができました。
Parquetには「列の値が連続で格納されている」ことと「メタデータを辿ることでデータにアクセスできる」ことがわかりました。

これで大まかな構造がわかりました。

しかし、これだけではありません。
Parquetはネストと配列がサポートされています。
ネストや配列のデータを取り出すには、更にもう1段階深堀りする必要があります。

更に先に進むため、章を分けて、もう少し続きます。

複雑なデータ構造に対応する

前章では簡単なデータ構造を持つParquetの構造を見ました。
しかし、Parquetはネストと配列を扱うことができます。
これらは、definition levelとrepetition levelという仕組みによって、通常のフィールドと同じように1列で表されています。

つまり、下のようにネストや配列があっても

{  
  col1: "val1",  
  col2: {col3: "val3"},  
  col4: {col5: {col6: [1,2,3]}}  
}

下のように同じレベルで保存されるのです。

{  
  "col1": ["val1"],  
  "col2.col3": ["val3"],  
  "col4.col5.col6": [1,2,3]  
}

この章ではdefinition levelとrepetition levelという仕組みを理解して、複雑なデータ構造を持つParquetを読み解きます。

ちなみに、この2つのレベルに関する説明はParquetのドキュメントには見つからなかったのですが、Dremelの論文をあたるとわかります
https://research.google/pubs/dremel-interactive-analysis-of-web-scale-datasets-2/

definition levelとrepetition level

まず、definition levelとrepetition levelの仕組みについて説明します。

雑に言うと、
definition levelはnullable(optional)なのにnullならなかった親フィールドの数で、
repetition levelは繰り返しがあったフィールドのレベルを表しています。

意味がわからないと思うので例をつけて解説します。

definition level

まず、definition levelについて。
次のjsonで表されるデータが入っているとします、全てのフィールドがoptional(nullable)です。

{  
  nest1: {  
    nest2: {  
      value: "hello" // D: 3  
    }  
  },  
},  
{  
  nest1: {  
    nest2: {  
      value: null // D: 2  
    }  
  },  
},  
{  
  nest1: {  
    nest2: null // D: 1  
  }  
},  
{  
  nest1: null // D: 0  
},  
{} // D: 0

このとき、各フィールドのdefinition levelはフィールド横のコメントの値(3,2,1,0,0)です。

definition levelを求めると、
最初の値(hello)は「nest1, nest2, valueの3フィールドがoptionalなのにnullではなかったから、definition levelは3」となります。
同様に、2つめは「nest1, nest2がoptionalなのにnullではなかったから2(valueはnullだからカウントしない)」となります。
3つ目は「nest1だけnullじゃないから1」です。
最後の2つはnest1すらnullなので0です。

このように、optionalな親フィールドの数を表すのがdefinition levelです。
この仕組みによって、対象columnだけをスキャンしてもdefinition levelをみればどこの親までnullになっているかがわかります。

repetition level

次に、repetition levelについて。
次のjsonで表されるデータが入っているとします。

{  
  repeated1: [  
    {  
      repeated2: [  
        "value1-1", // R: 0  
        "value1-2", // R: 2  
        "value1-3" // R: 2  
      ],  
      normalField2: "v1" // R: 0  
    },  
    {  
      repeated2: [  
        "value2-1", // R: 1  
        "value2-2" // R: 2  
      ]  
      normalField2: "v2" // R: 1  
    },  
    {  
      repeated2: [  
        "value3-1", // R: 1  
      ],  
      normalField2: "v3" // R: 1  
    }  
  ],  
  normalField1: "v4" // R: 0  
},

このとき、repetition levelはコメントにあるRの値です。

repetition levelを求めると、
最初のvalue1-1は「それ以前に配列(repeated)のフィールドがなかったから0」です。
次のvalue1-2は「repeated2の親のrepeated1も配列であるから、repeated2のレベルは2。value1-1があるから、repeated2には繰り返しがあった。よって、value1-2のrepetition levelはrepeated2のレベルから、2」となります。
次のvalue1-3も「value1-2があるから、repeated2に繰り返しがあった。よって2」です。
対して、value2-1は「repeated2には繰り返しがないが、repeated1には繰り返しがある(value1-1などの分の要素がある)。repeated1のレベルから、1」。
更にvalue2-2は「value2-1があるから、repeated2に繰り返しがあった。よって2」。
value3-1はvalue2-1と同様に、「repeated2には繰り返しがないが、repeated1には繰り返しがある。repeated1のレベルから、1」。
と決定します。

また、自身が配列でない場合でも親に配列があれば影響されるので、
v1は「それ以前に配列(repeated)のフィールドがなかったから0」
v2とv3は「repeated1が配列として機能しているから、repeated1のレベルから、1」
v4は「親に配列がないから、0」。と、repetition levelの値が付きます。

このように、配列として機能したフィールドのレベルを表すのがrepetition levelです。
この仕組みによって、対象columnだけをスキャンしてもrepetition levelを参照することで配列の最初かどうか、親が変わったか、などがわかります。

hexdump

これまでdefinition levelとrepetition levelについて見てきたので、ネストや配列があるファイルを読むことができるようになりました。
実際のデータをバイナリで見てみましょう。

以下のデータを使用します。

[  
  {  
    "nest": {  
      "nest": "nest1",  
      "repeated": [  
        {"nest": {"repeated": ["nestRep1", "nestRep2", "nestRep3"]}},  
        {"nest": {"repeated": ["nestRep4", "nestRep5"]}},  
      ]  
    },  
  },  
  {  
    "nest": {  
      "nest": "nest2",  
      "repeated": [  
        {"nest": {"repeated": ["nestRep6"]}},  
      ]  
    },  
  },  
  {  
    "nest": {  
      "nest": null,  
      "repeated": []  
    },  
  },  
]

このデータはparquet内では次のようなイメージで配置され、それぞれの値にdefinition levelとrepetition levelの値が振られます。

[  
  {"nest.nest": [  
    "nest1", // D: 2, R: 0  
    "nest2", // D: 2, R: 0  
    null,    // D: 1, R: 0  
  ]},  
  {"nest.repeated.nest.repeated": [  
    "nestRep1", // D: 4, R: 0  
    "nestRep2", // D: 4, R: 2  
    "nestRep3", // D: 4, R: 2  
    "nestRep4", // D: 4, R: 1  
    "nestRep5", // D: 4, R: 2  
    "nestRep6", // D: 4, R: 0  
    null        // D: 1, R: 0  
  ]}  
]

この情報をparquetから確認します。

データをparquetにしてhexdumpで見ると、下のようになっています。

00000000  50 41 52 31 15 06 15 2c  15 2c 15 df cf fe db 0d  |PAR1...,.,......|  
00000010  4c 15 06 15 02 15 06 15  00 15 08 15 00 12 00 00  |L...............|  
00000020  04 02 02 01 05 00 00 00  6e 65 73 74 31 05 00 00  |........nest1...|  
00000030  00 6e 65 73 74 32 15 06  15 ac 01 15 ac 01 15 bc  |.nest2..........|  
00000040  81 ac e6 09 4c 15 0e 15  02 15 06 15 00 15 08 15  |....L...........|  
00000050  14 12 00 00 02 00 04 02  02 01 02 02 04 00 0c 04  |................|  
00000060  02 01 08 00 00 00 6e 65  73 74 52 65 70 31 08 00  |......nestRep1..|  
00000070  00 00 6e 65 73 74 52 65  70 32 08 00 00 00 6e 65  |..nestRep2....ne|  
00000080  73 74 52 65 70 33 08 00  00 00 6e 65 73 74 52 65  |stRep3....nestRe|  
00000090  70 34 08 00 00 00 6e 65  73 74 52 65 70 35 08 00  |p4....nestRep5..|  
000000a0  00 00 6e 65 73 74 52 65  70 36 19 12 00 19 18 05  |..nestRep6......|  
000000b0  6e 65 73 74 31 19 18 05  6e 65 73 74 32 15 00 19  |nest1...nest2...|  
000000c0  16 02 00 19 12 00 19 18  08 6e 65 73 74 52 65 70  |.........nestRep|  
000000d0  31 19 18 08 6e 65 73 74  52 65 70 36 15 00 19 16  |1...nestRep6....|  
000000e0  02 00 19 1c 16 08 15 64  16 00 00 00 19 1c 16 6c  |.......d.......l|  
000000f0  15 e8 01 16 00 00 00 15  04 19 6c 48 06 4d 79 44  |..........lH.MyD|  
00000100  65 65 70 15 02 00 35 02  18 04 6e 65 73 74 15 04  |eep...5...nest..|  
00000110  00 15 0c 25 02 18 04 6e  65 73 74 25 00 4c 1c 00  |...%...nest%.L..|  
00000120  00 00 35 04 18 08 72 65  70 65 61 74 65 64 15 02  |..5...repeated..|  
00000130  00 35 02 18 04 6e 65 73  74 15 02 00 15 0c 25 04  |.5...nest.....%.|  
00000140  18 08 72 65 70 65 61 74  65 64 25 00 4c 1c 00 00  |..repeated%.L...|  
00000150  00 16 06 19 1c 19 2c 26  00 1c 15 0c 19 25 00 06  |......,&.....%..|  
00000160  19 28 04 6e 65 73 74 04  6e 65 73 74 15 00 16 06  |.(.nest.nest....|  
00000170  16 64 16 64 26 08 3c 36  02 28 05 6e 65 73 74 32  |.d.d&.<6.(.nest2|  
00000180  18 05 6e 65 73 74 31 00  19 1c 15 06 15 00 15 02  |..nest1.........|  
00000190  00 00 16 c4 03 15 14 16  d4 02 15 32 00 26 00 1c  |...........2.&..|  
000001a0  15 0c 19 25 00 06 19 48  04 6e 65 73 74 08 72 65  |...%...H.nest.re|  
000001b0  70 65 61 74 65 64 04 6e  65 73 74 08 72 65 70 65  |peated.nest.repe|  
000001c0  61 74 65 64 15 00 16 0e  16 e8 01 16 e8 01 26 6c  |ated..........&l|  
000001d0  3c 36 02 28 08 6e 65 73  74 52 65 70 36 18 08 6e  |<6.(.nestRep6..n|  
000001e0  65 73 74 52 65 70 31 00  19 1c 15 06 15 00 15 02  |estRep1.........|  
000001f0  00 00 16 d8 03 15 16 16  86 03 15 3e 00 16 cc 02  |...........>....|  
00000200  16 06 19 0c 16 08 16 cc  02 00 19 0c 18 37 67 69  |.............7gi|  
00000210  74 68 75 62 2e 63 6f 6d  2f 70 61 72 71 75 65 74  |thub.com/parquet|  
00000220  2d 67 6f 2f 70 61 72 71  75 65 74 2d 67 6f 20 76  |-go/parquet-go v|  
00000230  65 72 73 69 6f 6e 20 30  2e 32 33 2e 30 28 62 75  |ersion 0.23.0(bu|  
00000240  69 6c 64 20 29 19 2c 1c  00 00 1c 00 00 00 57 01  |ild ).,.......W.|  
00000250  00 00 50 41 52 31                                 |..PAR1|  
00000256

最初に、フッターのメタデータは343(0x0157)バイトあるので、248(0xf7=598-343-8+1)バイト目から(15 04 19 6cから)始まることがわかります。
このメタデータをthriftにしてcolumnの情報に注目すると、

{  
  "version": 2,  
  "row_groups": [  
    {  
      "columns": [  
        {  
          "meta_data": {  
            "path_in_schema": ["nest", "nest"],  
            "total_compressed_size": 50,  
            "data_page_offset": 4,  
          },  
        },  
        {  
          "meta_data": {  
            "path_in_schema": ["nest", "repeated", "nest", "repeated"],  
            "total_compressed_size": 121,  
            "data_page_offset": 54,  
          },  
        }  
      ],  
    }  
  ],  
}

と書いてあります。

そこから更に"nest.nest"のcolumnのメタデータ(5バイト目から始まる)にあるカラムの情報を見ると、

{  
  "data_page_header_v2": {  
    "num_values": 3,  
    "num_nulls": 1,  
    "num_rows": 3,  
    "encoding": "PLAIN",  
    "definition_levels_byte_length": 4,  
    "repetition_levels_byte_length": 0,  
    "is_compressed": false  
  }  
}

と書かれていて、definition levelの4バイトで表され、repetition levelは書かれていない(0バイト)ことがわかります。
repetition levelが書かれていないのは、全てがゼロなので、省略されているからです。
definition levelは4バイトで、33バイト目から36バイト目(0x20~0x23)の04 02 02 01が該当箇所です。

04 02 02 01は2進数にすると00000100 00000010 00000010 00000001です。
definition levelとrepetition levelはRunLengthかBitPackingエンコーディングされています。
https://parquet.apache.org/docs/file-format/data-pages/encodings/ を見ると、データはヘッダーと値の2バイトで構成されていて、ヘッダー(前半1バイト)の8ビット目が0のときRunLengthエンコーディングされていて、1ならBitPackエンコーディングされているとわかります。

今回の例では1バイト目と3バイト目のヘッダーは両方0で終わるのでRunLengthで、ヘッダーの最後尾1ビットを除くことで0000010(0) 00000010 0000001(0) 00000001は「2(0b10)回2(0b10)の後、1(0b1)回1(0b1)」と解釈してdefinition levelは2,2,1とわかります。

次に"nest.repeated.nest.repeated"のcolumnのメタデータの情報を見ると

{  
  "data_page_header_v2": {  
    "num_values": 7,  
    "num_nulls": 1,  
    "num_rows": 3,  
    "encoding": "PLAIN",  
    "definition_levels_byte_length": 4,  
    "repetition_levels_byte_length": 10,  
    "is_compressed": false  
  }  
}

と書かれていて、definition levelが4バイトで、repetition levelが10バイトとわかります。
repetition levelが先に書かれるのでrepetition levelから見ると、
データは85(0x54)バイト目から始まるので、repetition levelは85(0x54)~94(0x5d)バイト目で、0000001(0) 00000000 0000010(0) 00000010 0000001(0) 00000001 0000001(0) 00000010 0000010(0) 00000000(02 00 04 02 02 01 02 02 04 00)です。
展開すると0,2,2,1,2,0,0です。
definition levelはその後の4バイトなので、95(0x5e)~98(0x61)0000110(0) 00000100 0000001(0) 00000001(0C 04 02 01)です。展開すると4,4,4,4,4,4,1とわかります。

まとめると、

"nest.nest"の列はdefinition levelが2,2,1、repetition levelが0,0,0
"nest.repeated.nest.repeated"の列はdefinition levelが4,4,4,4,4,4,1、repetition levelが0,2,2,1,2,0,0

と読むことができました。

これらの値は、はじめに出したDとRに一致しています。

[  
  {"nest.nest": [  
    "nest1", // D: 2, R: 0  
    "nest2", // D: 2, R: 0  
    null,    // D: 1, R: 0  
  ]},  
  {"nest.repeated.nest.repeated": [  
    "nestRep1", // D: 4, R: 0  
    "nestRep2", // D: 4, R: 2  
    "nestRep3", // D: 4, R: 2  
    "nestRep4", // D: 4, R: 1  
    "nestRep5", // D: 4, R: 2  
    "nestRep6", // D: 4, R: 0  
    null        // D: 1, R: 0  
  ]}  
]

これで、ネストや配列があってもparquetを読み解けるようになりました。

最後に

これで、Paruetファイルはメタデータが含まれていて、各フィールドは全て列で表されていることがわかりました。

より詳細な話は、以下のページを参考にしてください。
https://parquet.apache.org/docs/file-format/
https://github.com/apache/parquet-format

また、ParquetはDremelの中で使われているファイルのフォーマットを参考にしていることから、公式にも「Dremelのxxxを使って・・・」という話が出てきます(特にdefinition levelとrepetition level)。その場合は、Dremelの論文を読むとわかります。
Dremel: Interactive Analysis of Web-Scale Datasets
https://research.google/pubs/dremel-a-decade-of-interactive-sql-analysis-at-web-scale/

以上、Parquetの構造の紹介でした。

2020-05-12

Azureにおけるデプロイ停止の取り組み - Gandalf

はじめに

バグのないコードは書けないません。
それを前提に、ブルーグリーンデプロイやカナリアリリースが実践されています。
それらの方法ではどのように問題を発見するかが重要になります。
この記事で紹介するGandalfは、Azure内で稼働する障害検知のためのシステムです。

Azureはクラウドサービスとして、安全なデプロイを行うために以下のような４層のチェックを入れています
f:id:mrasu:20200512221429j:plain

テスト環境でのクオリティコントロール
安全にデプロイするためのポリシー
コンポーネント単位での監視
全体の監視

Gandalfは、最後の「全体の監視」のためのシステムです。

今回の記事では、「Gandalf: An Intelligent, End-To-End Analytics Service for Safe Deployment in Large-Scale Cloud Infrastructure」から、Gandalfの仕組みを紹介します。

この論文によると、Azureでは1日に100以上のロールアウトが行われ、そのうちの20%以上が1000分以上かかるそうです。そのため、複数のロールアウトが同期間に実行されることは避けられません。
そのため、Gandalfは

障害の検知
障害を引き起こしているロールアウトの推定

という過程を通して、問題のあるロールアウトを停止します。
以下では、それぞれに使われている方法を紹介します。

Gandalf概要

f:id:mrasu:20200512221512j:plain
Gandalfでは、各ノードから送られてくるデータを使用し、上図のように

各ノードのデプロイ前後1時間のデータのみを使用する分析 (Speed Layer)
長期間(30日)のデータと複雑なモデルを使用する分析 (Batch Layer)

という２種類の分析を同時に行い、異常を探します。
ロールアウト開始直後に発生する問題もあれば、長期間動かさなければ発生しない問題もあるため、長期と短期の両方を分析対象としています。
異常を検知した場合にはロールアウトを停止すると共に、開発者への情報提供も行います。

障害検知

Gandalfは各ノードからOSのイベント情報やログ、APIのステータスなどを収集しています。
しかし、ハードウェア障害のようにソフトウェアの変更とは関係のない問題も発生します。
そのため、デプロイに起因した障害を抽出する必要があります。

そのために、

エラーのグルーピング例えば、エラーコードとエラーメッセージを受け取る場合、エラーコードは複数のエラーで重複し、メッセージは構造化されていません。そのため、エラーメッセージからIDなどを除外し、Incremental hierachial clusteringを使用することで、エラーをまとめています。
エラー傾向を予測し、ハズレ値を取るものを検出する
まとまったそれぞれのエラーに対して、Holt-Winters法を使用して障害の発生数を予測します。その予測と4シグマ離れていた場合、対象のエラーがロールアウトに起因すると判定します。

上の２つの段階を経ることで、ロールアウトに関係したエラーを監視します。

原因検知

障害を発見したら、原因のロールアウトを特定します。
Gandalfは以下の方法でロールアウトと障害の関係度(correlation)を計算しています。

ノードを変更した時間と障害発生時間の差から、各ロールアウトと障害の関係度を取る
障害が発生したノードの数とロールアウト期間に発生した数の割合を求め、障害に関係するロールアウトをピックアップする
最近のロールアウトをより重視するための重み付けをする

こうして得られた値から、障害と最も関係のあるロールアウトを割り出し、開発者に伝えます。
さらに、影響する顧客数やノード数などを基にロールアウトの停止もGandalfが判断します。

終わりに

このように、Azureではロールアウト中に障害を検知し、ロールアウトを停止しています。
この記事では障害検知の仕組みのみを説明しましたが、論文では計算式やその背景、Gandalfが発見したエラーの具体例なども書かれているので、興味が湧いたらぜひ読んでみてください。

2019-12-31

非同期で大量データをさばく

論文・読み物プログラミング

はじめに

最近、マイクロサービスの拡大と共にキューやストリームを使用した非同期処理が増えたと思います。
この記事では、Netflix・Pinterest・Airbnbが公開した、各社の非同期処理の具体例を紹介します。
(各事例は簡単な概要の紹介しか書かないので、より詳細な内容は元記事を覗いてみてください。)

Netflix: 別サービスへのデータ更新の伝播

元記事: Delta: A Data Synchronization and Enrichment Platform

最初はNetflixが社内で使用しているデータ同期ツールDeltaの紹介です。
Webサービスでは、RDBにデータ(Source of truth)を置きつつ、検索やキャッシュ用に別ツールにも同じデータをコピーするという構成を取るということが有りますが、Netflixもこれをやっています。
Netflixでは、どのように同期するかという問題に対して、「データ変更を検知した時に、変更を別サービスに通知する」という仕組みを作って解決しています。

f:id:mrasu:20191231175911p:plain

上図のように、データが更新されると、Delta-connectorを介してKafkaに情報が送られた後に各種伝播が発生するようになっています。

参考

また、NetflixはDeltaだけでなく、関連ツールについてもブログにしています。

DBLog (DeltaにRDBの変更を通知しているツール。UPDATEを使って開始時のログの場所を確認することで、RDBからのダンプと変更検知を可能にしている)
Keystone (Deltaで使うキュー。社内のリアルタイム処理プラットフォーム)

Pinterest: ユーザーイベントの保管・解析

元記事: Real-time User Signal Serving for Feature Engineering

次は、Pinterestによるユーザーイベントの解析についてです。
Pinterestではユーザー行動(クリックや検索)を解析するために、ユーザーイベントをキューが受けた後に集計とその結果の保存を簡単に行えるようにしています。

f:id:mrasu:20191231175955p:plain

上図のように、最初にイベント情報が「User Events」キューに入った後、順次計算を行い結果を保存します。その後、クライアントがViewのデータを取り出せるようになっています。

Airbnb: ２段SQSによるキューのスケジューリング

元記事: Dynein: Building an Open-source Distributed Delayed Job Queueing System

最後は、Airbnbによるスケジューリングについてです。
AirbnbはResqueを使っていましたが、性能やat-most-onceな特性などが問題となっていました。そのため、SQSを多段にしたスケジューリングツール(Dynein)を作ったそうです。

f:id:mrasu:20191231180027p:plain

上図がDyneinの動きです(赤いアイコンがAWS SQS, 青がDynamodb)。
SQSを多段にし、間にスケジューリング用のコンポーネントを作ることで、使用者にとってはSQSでありながらスケジューリングも出来るようになっています。

終わりに

以上、３社の非同期処理例を紹介しました。
また、直接的な例ではないですが、先日リリースされたThe Amazon Builders' Libraryの乗り越えられないキューバックログの回避という記事も面白い内容をもっています。

発明のための再発明

Webプログラマーが、プログラムの内部動作を通してプログラムを作る時の参考になるような情報を書くブログ(サーバーサイドやDevOpsメイン)

Parquetフォーマット概観

はじめに

tldr

Parquetの特徴

Parquetをhexdump

メタデータとファイル構造

Footer length

Footer (FileMetaData) の取得

RowGroup, Column, Page内容の取得

データの取得

データにアクセスできた

複雑なデータ構造に対応する

definition levelとrepetition level

definition level

repetition level

hexdump

最後に

Azureにおけるデプロイ停止の取り組み - Gandalf

はじめに

Gandalf概要

障害検知

原因検知

終わりに

非同期で大量データをさばく

はじめに

Netflix: 別サービスへのデータ更新の伝播

参考

Pinterest: ユーザーイベントの保管・解析

Airbnb: ２段SQSによるキューのスケジューリング

終わりに