Parquet原理

Hadoop生态学习小组
2018-04-08

在互联网大数据应用场景下，通常数据量很大且字段很多，

但每次查询数据只针对其中的少数几个字段，这时候列式存储是极佳的选择。

列式存储要解决的问题：

把IO只给查询需要用到的数据
- 只加载需要被计算的列
空间节省
- 列式的压缩效果更好
- 可以针对数据类型进行编码
开启矢量化的执行引擎(不再1条1条的处理数据，而是一次处理1024条数据)

Parquet和ORC是两种列式存储格式

今天主要介绍Parquet，后面会再介绍一下ORC，及对比

Parquet源码 : https://github.com/apache/parquet-mr

Parquet的设计目标：

适配通用性
存储空间优化
计算时间优化

1. 适配通用性

Parquet只是一种存储格式，它与上层平台、语言无关，不需要与任何一种数据处理框架绑定，目前已经适配的组件包括：

查询引擎：Hive\Impala\Pig\Presto\Drill\Tajo\HAWQ\IBM Big SQL
计算引擎：MapReduce\Spark\Cascading\Crunch\Scalding\Kite
数据模型：Avro\Thrift\Protocol Buffers

2. 存储空间优化

2.1 什么叫列式存储?

传统的思维中是按照一条记录一条记录的组织存储，列式存储是竖过来，按照一列一列的方式组织存储。

2.2 Parquet的数据模型

每条记录中的字段可以包含三种类型：required, repeated, optional。最终由所有叶子节点来代表整个schema。

2.2 Parquet的数据模型

元组的Schema可以转换成树状结构，根节点可以理解为repeated类型
所有叶子结点都是基本类型
没有Map、Array这样的复杂数据结构，但是可以通过repeated和group组合来实现这样的需求

2.3 Striping/Assembly算法

Parquet的一条记录的数据如何分成多少列，又如何组装回来？是由Striping/Assembly算法决定的。

在该算法中，列的每一个值都包含三个部分：

value : 字段值
repetition level : 重复级别
definition level : 定义级别

2.3.1 Repetition Levels

repetition level的设计目标是为了支持repeated类型的节点：

在写入时该值等于它和前面的值从哪一层节点开始是不共享的。
在读取的时候根据该值可以推导出哪一层上需要创建一个新的节点。
例子：对于这样的schema和两条记录：

message nested {
repeated group leve1 {
repeated string leve2;
}
}

r1:[[a,b,c,] , [d,e,f,g]]
r2:[[h] , [i,j]]

计算一下各个值的repetition level。
repetition level计算过程：

value=a是一条记录的开始，和前面的值在根结点上是不共享的，因此repetition level=0
value=b和前面的值共享了level1这个节点，但是在level2这个节点上不共享，因此repetition level=2
同理，value=c的repetition value=2
value=d和前面的值共享了根节点，在level1这个节点是不共享的，因此repetition level=1
同理，value=e,f,g都和自己前面的占共享了level1，没有共享level2，因此repetition level=2
value=h属于另一条记录，和前面不共享任何节点，因此，repetition level=0
value=i跟前面的结点共享了根，但是没有共享level1节点，因此repetition level=1
value-j跟前面的节点共享了level1，但是没有共享level2，因此repetition level=2

在读取时，会顺序读取每个值，然后根据它的repetition level创建对象

当读取value=a时，repeatition level=0，表示需要创建一个新的根节点，
当读取value=b时，repeatition level=2，表示需要创建level2节点
当读取value=c时，repeatition level=2，表示需要创建level2节点
当读取value=d时，repeatition level=1，表示需要创建level1节点
剩下的节点依此类推

几点规律：

repetition level=0表示一条记录的开始
repetition level的值只是针对路径上repeated类型的节点，因此在计算时可以忽略非repeated类型的节点
在写入的时候将其理解为该节点和路径上的哪一个repeated节点是不共享的
读取的时候将其理解为需要在哪一层创建一个新的repeated节点

2.3.2 Definition Levels

有了repetition levle就可以构造出一条记录了，那么为什么还需要definition level呢？

是因为repeated和optional类型的存在，可以一条记录中的某些列是没有值的，如果不记录这样的值，就会导致本该属于下一条记录的值被当做当前记录中的一部分，从而导致数据错误，因此，对于这种情况，需要一个占位符来表示。

definition level的值仅对空值是有效的，表示该值的路径上第几层开始是未定义的；对于非空值它是没有意义的，因为非空值在叶子节点上是有定义的，所有的父节点也一定是有定义的，因此它的值总是等于该列最大的definition level。
例子：对于这样的schema：

message ExampleDefinitionLevel {
optional group a {
optional group b {
optional string c;
}
}
}

它包含一个列a.b.c，这个列的的每一个节点都是optional类型的，当c被定义时a和b肯定都是已定义的，当c未定义时我们就需要标示出在从哪一层开始时未定义的
一条记录的definition level的几种可能的情况如下表：

Value	Definition Level
a:null	0
a:{b:null}	1
a:{b:{c:null}}	2
a:{b:{c:”foo”}}	3(全部定义了)

由于definition level只需要考虑未定义的值，对于required类型的节点，只要父亲节点定义了，该节点就必须定义，因此计算时可以忽略路径上的required类型的节点，这样可以减少definition level的最大值，优化存储。

2.3.3 一个完整的例子

下面使用Dremel论文中给的Document示例和给定的两个值展示计算repeated level和definition level的过程，这里把未定义的值记录为NULL，使用R表示repeated level，D表示definition level。

首先看DocId这一列，r1和r2都只有一值分别是：
- id1=10,由于它是记录开始，并且是已定义的，因此R=0,D=0
- id2=20,由于是新记录的开始，并且是已经定义的，因此R=0,D=0
对于Name.Url这一列，r1中它有三个值，r2中有一个值分别是：
- url1=’http://A‘ ，它是r1中该列的第一个值，并且是定义的，所以R=0,D=2
- url2=’http://B‘ ，它跟上一个值在Name这层是不同的，并且是定义的，所以R=1,D=2
- url3=NULL，它跟上一个值在Name这层是不同的，并且是未定义的，所以R=1,D=1
- url4=’http://C‘ ，它跟上一个值属于不同记录，并且是定义的，所以R=0,D=2
对于Links.Forward这一列，在r1中有三个值，在r2中有1个值，分别是：
- value1=20，它是r1中该列的第一个值，并且是定义的，所以R=0,D=2
- value2=40，它跟上一个值在Links这层是相同的，并且是定义的，所以R=1,D=2
- value3=60，它跟上一个值在Links这层是相同的，并且是定义的，所以R=1,D=2
- value4=80，它是一条新的记录，并且是定义的，所以R=0,D=2
对于Links.Backward这一列，在r1中有一个空值，在r2中两个值，分别是：
- value1=NULL，它是一条新记录，并且是未定义的，父节点Links是定义的，所以R=0,D=1
- value2=10，是一条新记录，并且是定义的，所以R=0,D=2
- value3=30,跟上个值共享父节点，并且是定义的，所以R=1,D=2

2.4 Parquet文件格式

Parquet文件是二进制方式存储的，文件中包含数据和元数据，可以直接进行解析。

先了解一下关于Parquet文件的几个基本概念：

行组(Row Group)：每一个行组包含一定的行数，一般对应一个HDFS文件块，Parquet读写的时候会将整个行组缓存在内存中。
列块(Column Chunk)：在一个行组中每一列保存在一个列块中，一个列块中的值都是相同类型的，不同的列块可能使用不同的算法进行压缩。
页(Page)：每一个列块划分为多个页，一个页是最小的编码的单位，在同一个列块的不同页可能使用不同的编码方式。

Parquet文件组成：

文件开始和结束的4个字节都是Magic Code，用于校验它是否是一个Parquet文件
结束MagicCode前的Footer length是文件元数据的大小，通过该值和文件长度可以计算出元数据Footer的偏移量
再往前推是Footer文件的元数据，里面包含：
- 文件级别的信息：版本，Schema，Extra key/value对等
- 每个行组的元信息，每个行组是由多个列块组成的：
  - 每个列块的元信息：类型，路径，编码方式，第1个数据页的位置，第1个索引页的位置，压缩的、未压缩的尺寸，额外的KV
文件中大部分内容是各个行组信息：
- 一个行组由多个列块组成
  - 一个列块由多个页组成，在Parquet中有三种页：
    - 数据页
      - 一个页由页头、repetition levels\definition levles\valus组成
    - 字典页
      - 存储该列值的编码字典，每一个列块中最多包含一个字典页
    - 索引页
      - 用来存储当前行组下该列的索引，目前Parquet中还不支持索引页，但是在后面的版本中增加

3. 计算时间优化

Parquet的最大价值在于，它提供了一中把IO奉献给查询需要用到的数据。主要的优化有两种：

映射下推(Project PushDown)
谓词下推(Predicate PushDown)

3.1 映射下推

列式存储的最大优势是映射下推，它意味着在获取表中原始数据时只需要扫描查询中需要的列。

Parquet中原生就支持映射下推，执行查询的时候可以通过Configuration传递需要读取的列的信息，在扫描一个行组时，只扫描对应的列。

除此之外，Parquet在读取数据时，会考虑列的存储是否是连接的，对于连续的列，一次读操作就可以把多个列的数据读到内存。

3.2 谓词下推

在RDB中谓词下推是一项非常通用的技术，通过将一些过滤条件尽可能的在最底层执行可以减少每一层交互的数据量，从而提升性能。

例如，
select count(1)
from A Join B
on A.id = B.id
where A.a > 10 and B.b < 100

SQL查询中，如果把过滤条件A.a > 10和B.b < 100分别移到TableScan的时候执行，可以大大降低Join操作的输入数据。

无论是行式存储还是列式存储，都可以做到上面提到的将一些过滤条件尽可能的在最底层执行。

但是Parquet做了更进一步的优化，它对于每个行组中的列都在存储时进行了统计信息的记录，包括最小值，最大值，空值个数。通过这些统计值和该列的过滤条件可以直接判断此行组是否需要扫描。

另外，未来还会增加Bloom Filter和Index等优化数据，更加有效的完成谓词下推。

在使用Parquet的时候可以通过如下两种策略提升查询性能：

类似于关系数据库的主键，对需要频繁过滤的列设置为有序的，这样在导入数据的时候会根据该列的顺序存储数据，这样可以最大化的利用最大值、最小值实现谓词下推。
减小行组大小和页大小，这样增加跳过整个行组的可能性，但是此时需要权衡由于压缩和编码效率下降带来的I/O负载。

4. 性能表现

这里其实还有一个重要的竞争对手没有提到，就是ORC，后面会再单独介绍。

5. Parquet上手探索

使用parquet-tools可以对一个parquet文件进行解析。

parquet-tools下载地址:https://github.com/apache/parquet-mr/tree/master/parquet-tools
yakundeMacBook-Pro:workspace yakun$ java -jar parquet-mr/parquet-tools/target/parquet-tools-1.9.1-SNAPSHOT.jar –help
usage: parquet-tools cat [option…]
where option is one of:
–debug Enable debug output
-h,–help Show this help string
-j,–json Show records in JSON format.
–no-color Disable color output even if supported
where is the parquet file to print to stdout

usage: parquet-tools head [option…]
where option is one of:
–debug Enable debug output
-h,–help Show this help string
-n,–records The number of records to show (default: 5)
–no-color Disable color output even if supported
where is the parquet file to print to stdout

usage: parquet-tools meta [option…]
where option is one of:
–debug Enable debug output
-h,–help Show this help string
–no-color Disable color output even if supported
where is the parquet file to print to stdout

usage: parquet-tools dump [option…]
where option is one of:
-c,–column Dump only the given column, can be specified more than
once
-d,–disable-data Do not dump column data
–debug Enable debug output
-h,–help Show this help string
-m,–disable-meta Do not dump row group and page metadata
-n,–disable-crop Do not crop the output based on console width
–no-color Disable color output even if supported
where is the parquet file to print to stdout

后面再介绍一下最强挑战者，ORC