官网地址：https://parquet.apache.org/docs
编码：https://www.waitingforcode.com/apache-parquet/encodings-apache-parquet/read
Nested类型编码参考文章：Dremel: interactive analysis of web-scale datasets
Nested类型编码参考解释：https://github.com/julienledem/redelm/wiki/The-striping-and-assembly-algorithms-from-the-Dremel-paper

1. Overview

Parquet是Hadoop生态里面一个比较流行的列存储格式。它存在的意义就是最大化利用压缩的列存储表示。
当然支持各种压缩和编码模式：

• 可以细化到列级别，即每一列用不同算法压缩；
• 甚至支持未来的，尚未发明的压缩技术。

注意，总的来说，Parquet是一个非常底层的文件存储技术，它和任何数据处理技术、软件都是正交的，这些技术也都可以用Parquet来存文件。

Parquet is built from the ground up with complex nested data structures in mind, and uses the [record shredding and assembly algorithm] described in the Dremel paper. We believe this approach is superior to simple flattening of nested name spaces

2. Concepts

• 块：就是hdfs block
• 文件：就是hdfs文件，元数据存于master中。
• 行组(Row group)：逻辑上数据表中的一组行。由于实际上都是列存储，所以在hadoop上找不到所谓的行组，这只是一个逻辑上的概念。
• 列切片(column chunk)：某一列中连续的一片数据。其实是行组的一部分，但是它是物理存在的，在文件中连续存储的。
• 页(page)：页时列切片的一部分。概念上是说不可分的一个单元，是针对于压缩编码来说的。一个列切片里面可能有几个不同类型的页分别压缩。

总结一下这个概念，一个文件可能逻辑上包含若干行组，每个行组中，每个列构成一个列切片，列切片内由多个页构成，页是最小压缩单元。

编者绘制了下图帮助概念理解。

image.png

在并行化级别方面：

• MapReduce是并行文件，也可能是并行行组；
• 系统IO其实是在并行列切片；
• 压缩针对的则是页。

3. File Format

一个文件用Parquet来存，基本格式如下图：

• 首尾的魔数是系统相关的，不细说；
• 文件主体是M个行组，N个列的存储；
  • 比如最开始存第一个行组，把第一个行组的N个列切片，全部存好，然后进入到第二个行组；
• 文件的最后是整个文件的元数据，包含各个行组的位置，各个列切片的位置和一些其它统计信息。
  • 整个文件的元数据放在了文件最后，这是为了写入时能顺序写一遍就完工。
• 具体存放的时候，尾部的元数据可以单独存一个文件，数据文件可以分成几个Parquet files来存放；每个Parquet file可以包含一个或几个行组。
• 数据文件中每个行组中的每个页会有一个页元数据，页有三种，数据页，字典页，索引页。字典页每个列切片最多一个，是该列值的编码字典（编码部分会讲到）；索引页是一个高级功能。
• 读取的时候，首先读取元数据，找到自己想要列切片的位置，然后顺序访问即可。

• Parquet可以保证，对于每个RowGroup只会被一个mapper处理。

  
  
  image.png

3.1 Configurations

对于Parquet，有两个重要的参数配置：

• Row Group Size：行组大小
  • 行组比较大，顺序扫描时就可以有更多的顺序磁盘访问；
  • 行组过大，写入时需要的内存buffer也会比较大。
  • 综合来说，还是会选择比较大，推荐1GB大小。
  • 由于一整个行组可能需要读出来，所以最好是一个Row Group塞进一个HDFS block里面，所以block也推荐1GB大小。
• Page Size：页大小
  • 页大的话，压缩率高，访问也略快；
  • 页小的话，对于细粒度的查询就可以访问更少的数据；
  • 综合一下，推荐8KB。

3.2 Metadata

元数据有三个级别，文件元数据，列（chunk）元数据，页元数据。

3.3 Types

类型支持的原则是尽量少，因为Parquet一般不直接面向用户，这里只关注类型如何在磁盘中存储。更复杂的类型，比如String，可以用BYTE_ARRAY进行支持，再额外加一个注解表名如何解释这个BYTE_ARRAY即可。这样只用实现很少量几种类型的代码，就可以表示多种用户类型。

image.png

3.4 Nested Encoding

这里是说层次化类型的编码。举个例子：
如下图：想json,xml等类型一样，数据文件中的列也可能是嵌套复合类型。这些类型不仅仅是列表，map这么简单，而是组合类型的不断组合，理论上有无限深度的。

• 在下图这个例子里，repeated其实就相当于列表（单一类型），group就相当于一个字典类型（key是固定的，类似C里面的Struct）。
• 具体到存储上，共有6个列：
  • DocId;
  • Links.Backward;
  • Links.Forwad;
  • Name.Language.Code;
  • Name.Language.Country;
  • Name.Url;

image.png

要处理这样类型的列，就需要先展平，编码，用的时候子再解码恢复结构查询。
下面三个小节，分别解决这个过程中的三个问题：

1. 层次化记录的无损表示；
2. 列的快速编码；
3. 高效解码重组。

3.4.1 Repetition and Definition Levels

在一个列式存储文件中，只给定某两个值，我们是没法确定它们是来自一条record还是两条记录的，因为存在重复类型的这个概念（如上图Name列，其实可以理解为列表类型）。为了得以区分，定义了重复级别和定义级别两个概念。

• 举一个例子，对于Name.Language.Code，存下来其实就是连续的一组字符串了，我们需要知道每一个Code，它属于哪一个Language (1个Name有多个Language)，属于哪一个Name （1条记录可能有多个Name）。

3.4.1.1 repetition levels

• 重复级别 (r) 是说当前这个值，是属于一个新纪录（r=0）？或者在同一个记录的第几层 (r=n)？

• 举个例子，比如刚才Name.Language.Code这一列，路径上有Name, Language两个可重复对象（列表），所以r的值在【0,2】。- - 以r1为例，en-us这个值开启一个新对象，它的r是0,；en是在Name.Language这个级别的重复（开启了一个新的Name.Language），r值就是2; en-gb是在Name这个级别的重复（开启了一个新的Name），r值是1。

  
  
  image.png

• 重复级别解决的是可重复类型的问题，如果列的路径上根本没有可重复类型(repeated)，那就不需要定义重复级别。

• 仍然有一个问题是，虽然我们定义清楚了级别，但是没定义清楚位置。比如刚才的en-gb它到底属于第二个name还是第三个name无法推测，因此要在en-gb之前加一个null。

3.4.1.2 definition levels

定义级别是给所有null值的一个属性，把位置定义清楚。定义级别d描述的是null是在哪一级别的缺省。

• 举Name.Language.Country为例子：

  • 第一个null, d=2, 描述的是在一个新的Name.Language中没有country
  • 第二个null, d=1，描述的是在一个新的Name中没有Language，自然也没有country
  • 第三个null，d=1,也是一个新的Name中没有Language，即r2。

• 对于非null值，就赋予正常的嵌套深度。

• 定义级别解决的是可选类型的问题，如果一列的路径上所有类型都是必须的（required），那就没必要定义定义级别。

3.4.1.3 encoding

最终的编码是非常紧凑的。每个列由多个block组成，每个block有两种levels，有具体的数值。这些levels也不是全都按序存储，主要是按需存储，bit能省则省，一些隐含关系都被挖掘出来。

3.4.2 Splitting Records into Columns

本节聚焦于如何将原始数据都覆成列格式：

image.png

3.4.3 Record Assembly

通过一个有限自动机把需要的数据组合起来。
【编者：我自己也没看进去这部分内容，有兴趣的朋友可以参考论文和代码再研究下。】

image.png

3.5 Data Pages

数据页中，包含定义级别，重复级别，和编码后的数据值。如果数据全都是Required，并且不嵌套，那就不需要这两个级别的信息，而只有编码后的数据值。

3.5.1 Encoding

3.5.1.1 Plain

支持所有类型，最简单的存储方式。

• BOOLEAN: Bit Packed, LSB first
• INT32: 4 bytes little endian
• INT64: 8 bytes little endian
• INT96: 12 bytes little endian (deprecated)
• FLOAT: 4 bytes IEEE little endian
• DOUBLE: 8 bytes IEEE little endian
• BYTE_ARRAY: length in 4 bytes little endian followed by the bytes contained in the array
• FIXED_LEN_BYTE_ARRAY: the bytes contained in the array

3.5.1.2 Dictionary Encoding

• 把所有值建字典，key是值，value是id。
• 之前我们说到数据页可能会配备一个字典页，存的就是这个字典；
• 这样数据页中的每一项数据，就可以用一个整数id来存储，最大位宽看基数而定。
• 具体来说，数据页头部第一个字节描述每个值用多宽的bit来存。后面的各个值就是这些id。一般这些id也会进一步用RLE编码。
• 当字典条目太多，或者字典太大，会自动退回plain。

image.png

3.5.1.3 Run Length Encoding / Bit-Packing Hybrid

• RLE的思路下图即可解释：重复次数+重复值。

  
  
  image.png
• bit-packed基本意思是，一个int要32bit，但很多时候用不上32bit，可能10bit就够了（对于512以内的数据），那么就可以缩短宽度存储。

• 这二者混合使用，取决于值字符的重复程度选择其中一个，可以进一步压缩数据页的这些值。

  
  
  image.png

3.5.1.4 Bit-packed (Deprecated)

废弃的bit-packed非常简单，就是每个类型固定宽度，然后按顺序存储就可以了。但注意是bit级别的，粒度是很细的。因为它性能一般，完全不如RLE或者和RLE混合，目前只是为了兼容性而存在。
用于：

• 对定义级别和重复级别的编码。

3.5.1.5 Delta Encoding

支持INT32, INT64，和字节数组类型。

• 其基本思想是，数据的差异一般可能很小，如果只存差异的话，就不需要那么长的bit。这尤其适用于时间、日期、有公共前缀的字符串。

• 数据是分块的，一旦有过大差异，可以通过调整分块来改善。每个分块都有自己的数据宽度。

  
  
  image.png

3.5.1.6 Delta-length byte array

专门用于字节数组。

• 数组长度单独提出来用Delta来压缩；

• 后面跟着纯字节，也利于后续压缩算法。

  
  
  image.png

3.5.1.7 Byte Stream Split

用于浮点数。
把每一位单独抽出来，虽然总体大小没有减少，但是利于后续压缩算法压缩。