一、概述

Apache Parquet 是由 Twitter 和 Cloudera 最先发起并合作开发的列存项目，也是 2010 年 Google 发表的 Dremel 论文中描述的内部列存格式的开源实现。和一些传统的列式存储系统相比，Dremel/Parquet 最大的贡献是支持嵌套格式数据的列式存储。嵌套格式可以很自然的描述互联网和科学计算等领域的数据，Dremel/Parquet 原生的支持嵌套格式数据减少了规则化、重新组合这些大规模数据的代价。

Parquet 的设计与计算框架、数据模型以及编程语言无关，可以与任意项目集成，因此应用广泛。目前已经是 Hadoop 大数据生态圈列式存储的事实标准。

1.1. 列式存储

列式存储，按列进行存储数据，把某一列的数据连续的存储，每一行中的不同列的值离散分布。

OLAP 场景下的数据大部分情况下都是批量导入，基本上不需要支持单条记录的增删改操作，而查询的时候大多数都是只使用部分列进行过滤、聚合，对少数列进行计算。列式存储可以大大提升这类查询的性能，较之于行是存储，列式存储能够带来这些优化:

由于每一列中的数据类型相同，所以可以针对不同类型的列使用不同的编码和压缩方式，这样可以大大降低数据存储空间。
读取数据的时候可以把映射(Project)下推，只需要读取需要的列，这样可以大大减少每次查询的 I/O 数据量，更甚至可以支持谓词下推，跳过不满足条件的列。
由于每一列的数据类型相同，可以使用更加适合 CPU pipeline 的编码方式，减小 CPU 的缓存失效。

相比传统的行式存储，Hadoop 生态圈近年来也涌现出诸如 RC、ORC、Parquet 的列式存储格式，它们的性能优势主要体现在两个方面：1、更高的压缩比，由于相同类型的数据更容易针对不同类型的列使用高效的编码和压缩方式。2、更小的I/O操作，由于映射下推和谓词下推的使用，可以减少一大部分不必要的数据扫描，尤其是表结构比较庞大的时候更加明显，由此也能够带来更好的查询性能。

二、Parquet File Format

Parquet 文件有 N 个列，划分成了 M 个行组，每个行组都有所有列的一个 Chunk 和其元数据信息。文件的元数据信息存储在数据之后，包含了所有列块元数据信息的起始位置。读取的时候首先从文件末尾读取文件元数据信息，再在其中找到感兴趣的 Column Chunk 信息，并依次读取。文件元数据信息放在文件最后是为了方便数据依序一次性写入。

Parquet 所有的数据被水平切分成 Row group，一个 Row group 包含这个 Row group 对应的区间内的所有列的 column chunk。一个 column chunk 负责存储某一列的数据

一个文件中可以存储多个行组，

一个 $column\ chunk$ 是由 $Page$ 组成的，$Page$ 是压缩和编码的单元，对数据模型来说是透明的。一个 $Parquet$ 文件最后是 $Footer$，存储了文件的元数据信息和统计信息。

Footer length 记录了文件元数据的大小，通过该值和文件长度可以计算出元数据的偏移量，文件的元数据中包括每一个行组的元数据信息和该文件存储数据的 Schema 信息。除了文件中每一个行组的元数据，每一页的开始都会存储该页的元数据。

2.1. 魔数 Magic Number

文件的首位都是该文件的 $Magic\ Number$，用来指示文件类型，校验它是否是一个 Parquet 文件。$Magic\ Number$ 目前有两种变体，分别是 PAR1 和 PARE。其中 PAR1 代表的是普通的 Parquet 文件，PARE 代表的是加密过的 Parquet 文件。

2.2. 行组(Row Group)

按照行将数据物理上划分为多个单元，每一个行组包含一定的行数。一个行组包含这个区间内的所有列的列块。

更大的行组意味着更大的列块，使得能够做更大的序列 IO。建议设置更大的行组(512MB-1GB)。因为一次可能需要读取整个行组，所以想让一个行组刚好在一个 HDFS 块中。因此，HDFS 块的大小也需要被设得更大。一个最优的读设置是: 1GB 的行组，1GB 的 HDFS 块，1 个 HDFS 块放一个 HDFS 文件。

2.2.1. 列块(Column Chunk)

在一个行组中每一列保存在一个列块中。不同的列块可能使用不同的算法进行压缩。一个列块由多个页组成。

页 $Page$

在 $Parquet$ 中，有三种类型的页: DataPage(存储编码后的数据)、DictionaryPage(对于字典编码，DictionaryPage 存储 index 和数据的映射关系，每一个列块中最多包含一个字典页)、IndexPage(MinMaxIndex、BloomFilter)

每一个列块划分为多个页，页是压缩和编码的单元，在同一个列块的不同页可能使用不同的编码方式。
- Page header
- Repetition levels
- Definition levels

Footer 是 Parquet 元数据的大本营，包含了诸如 schema，Block 的 offset 和 size，Column Chunk 的 offset 和 size 等所有重要的元数据。另外 Footer 还承担了整个文件入口的职责，读取 Parquet 文件的第一步就是读取 Footer 信息，转换成元数据之后，再根据这些元数据跳转到对应的 block 和 column，读取真正所要的数据。

为什么 Parquet要把元数据放在文件的末尾而不是开头🤔️?

这主要是为了让文件写入的操作可以在一趟 (one pass) 内完成。因为很多元数据的信息需要把文件基本写完以后才知道(例如总行数，各个 Block 的 offset 等)，如果要写在文件开头，就必须seek 回文件的初始位置，大部分文件系统并不支持这种写入操作(例如 HDFS)。而如果写在文件末尾，那么整个写入过程就不需要任何回退。

Parquet 总共有 3 种类型的元数据：文件元数据、列(块)元数据和 Page header 元数据。所有元数据都采用 thrift 协议存储。具体信息如下所示：

2.3.1. Index

Index 是 Parquet 文件的索引块，主要为了支持 “谓词下推”(Predicate Pushdown)功能。

谓词下推是一种优化查询性能的技术，把查询条件下推到存储层，在存储层做初步的过滤，把不满足查询条件的数据排除掉，从而减少数据的读取和传输量。

举个栗子🌰:

对于 csv 文件，因为不支持谓词下推，Spark 只能把整个文件的数据全部读出来以后，再用 where 条件对数据进行过滤。而如果是 Parquet 文件，因为自带 Max-Min 索引，Spark 就可以根据每个 Page 的 max 和 min 值，选择是否要跳过这个 Page，不用读取这部分数据，也就减少了 IO 的开销。

目前 Parquet 的索引有两种，一种是 Max-Min 统计信息，一种是 BloomFilter。

Max-Min 索引

Max-Min 索引是对每个 Page 都记录它所含数据的最大值和最小值，这样某个 Page 是否不满足查询条件就可以通过这个 Page 的 max 和 min 值来判断。

https://mp.weixin.qq.com/s/1vN711EyiogT_0q_JiJNwA
BloomFilter 索引

BloomFilter 索引是对 Max-Min 索引的补充，针对 value 比较稀疏，max-min 范围比较大的列，用 Max-Min 索引的效果就不太好，BloomFilter 可以加速过滤匹配。开启 Parquet 文件会在每个 ColumnChunk 的头部保存 BloomFilter 数据，并在 Footer 的 ColumnMetaData 记录 BloomFilter 的 page offset。

三、嵌套结构编码

https://mp.weixin.qq.com/s/-6SREjRVxhulvbtqSYcFCg

https://mp.weixin.qq.com/s/HA-1wkSa98DZJEG9elY7qg

Parquet 如何把嵌套结构编码进列式存储🤔️?

Parquet 通过 repetition level 和 definition level 来解决这个问题

举个栗子🌰:

{
  "owner": "Lei Li",
  "ownerPhoneNumbers": ["13354127165", "18819972777"],
  "contacts": [
    {
      "name": "Meimei Han",
      "phoneNumber": "18561628306"
    },
    {
      "name": "Lucy",
      "phoneNumber": "14550091758"
    }
  ]
},
{
  "owner": "Meimei Han",
  "ownerPhoneNumbers": ["15130245254"],
  "contacts": [
    {
      "name": "Lily"
    }，
    {
      "name": "Lucy",
      "phoneNumber": "14550091758"
    }
  ]
}

第三列 contacts.name，它有4个值 “Meimei Han”，”Lucy”，”Lily”，”Lucy”，其中前两个属于前一条 record，后两个属于后一条 record。

Parquet 是如何表达这个信息的呢?

它是用 repetition level 这个值来表达的。

3.1. Repetition Level

repetition level 主要用来表达数组类型字段的长度，但它并不直接记录长度，而是通过记录嵌套层级的变化来间接地表达长度，即如果嵌套层级不变，那么说明数组还在延续，如果嵌套层级变了，说明前一个数组结束了。如果在某个值上嵌套层级由 0 提高到了 1，则这个值的 repetition level 就是 0。如果在某个值的位置嵌套层级不变，则这个值的 repetition level 就是它的嵌套层级。对于上文中的例子，对应的 repetition level 就是:

3.2. Definition Level

与 repetition level 类似，definition level 主要用来表达 null 的位置。因为 Parquet 文件里不会显式地存储 null，所以通过 definition level 来判断某个值是否是 null

Striping/Assembly算法*

1.解决的问题：

如何只读取需要的列？
如何将读到的各列数据组成一行数据？

2.算法

Parquet采用的是Google Dremel的编码方法，核心思想是“record shredding and assembly algorithm”，即模式中的每个原子类型的字段都单独存储为一列，且每个值都需要通过两个整数来对其结构编码，分别是Definition Level(列定义深度)和Repetition Level(列元素重复次数)。

Definition Level指的从根节点到当前位置的路径上有多少可选的节点被定义了，required类型不统计在内。
Definition Level的计算公式如下：当前树深度 - 路径上类型为required的个数 - 1（如果自身为null）
针对repeated类型的Repetition Level等于根节点到达它的路径上的repeated节点的个数。

四、数据压缩

Parquet 格式的主要优势之一是通过应用各种压缩算法来减少文件的内存占用。

有两种主要的编码类型使 Parquet 能够压缩数据并实现惊人的空间节省

4.1. 字典编码

Parquet 创建列中不同值的字典，然后用字典中的索引值替换”真实”值。

4.2. Run-Length-Encoding(RLE)

Run-Length-Encoding with Bit-Packing 当数据包含许多重复值时，Run-Length-Encoding(RLE) 算法可能会带来额外的内存节省。

五、统计信息

5.1. Page 层级

Page层面的统计信息，Page层面的统计信息有过两个版本, 第一个版本的Page的统计信息是跟Page的数据保存在一起的，这个版本的问题在于由于统计信息是分散在所有的Page里面，那么我们必须实际读出每个Page的Header才能获取所有的统计信息，而这些是非连续的IO，如果用户的查询是一个点查的话，这些非连续IO就会严重拖累性能；而目前新的一个版本Page层面统计信息是保存在Parquet文件的footer附近，这样可以一次性的把统计信息读出来，性能相对来说更好。新版本把这个统计信息放在footer附近还有另外一个考虑，如果用户的查询是一个full scan，那么ParquetReder可以直接去读取数据，读的过程中不会去读没必要的统计信息，不会有IO放大的问题。