一、数据模型

Parquet 采用了一个类似 Google Protobuf 的协议来描述存储数据的 schema。如下是 Parquet 数据 schema 的简单示例：

schema 的最上层是 message，里面可以包含一系列字段。其内部每个字段包含三部分：字段类型、数据类型、字段名称。每个字段都拥有 3 个属性：重复性 （repetition）、类型（type）以及名称（name）。字段类型可以是一个 group 或者原子类型 （如 int、boolean、string 等），group 可以用来表示数据的嵌套结构。通过数据类型group来表达层级关系时，将字段类型分为三种，来表达空或数组的概念。

• required：有且出现一次
• optional: 出现 0 或 1 次 
• repeated: 出现次数大于等于零次，可多次出现

parquet使用列式存储格式。Dremel/Parquet 中，提出以树状层级的形式组织 schema 中的字段，其中树的叶子结点对应实际的存储字段，也就是物理意义上的列，这样这个模型能同时覆盖扁平结构和嵌套结构数据。嵌套字段的完整路径使用简单的点分符号表示，如，contacts.name。 列存连续的存储一个字段的值，以便进行高效的编码压缩及快速的读取。Dremel 中行存 vs 列存 的图示如下：

该图片引用自《Dremel: Interactive Analysis of Web-Scale Datasets》

 parquet利用Dremel 提出的(R, D, V)模型用于嵌套数据存储，其中V表示数据值，D和R分别表示Definition Level和Repetition Level。

二、Repetition Levels和Definition Levels

Repetition Levels：用以表示在该字段路径上哪个节点进行了重复，即该字段当前值与上一个值在哪一个节点上是不共享的。在读取的时候根据该值可以推导出哪一层上需要创建一个新的节点。

Definition Levels：用以表示该字段路径上有多少可选的字段实际进行了定义，当该字段已定义时，Definition Levels表示字段嵌套深度。

关于Repetition Levels和Definition Levels的具体例子如下。

Document表示一个兴趣小组的记录，小组具有required属性的id号，每个小组可能有一个指导老师，也可能没有，小组中有不定数量的组员，每个组员的固有属性为姓名，除此之外每个组员还拥有不定数量的联系人，每个联系人都可能有姓名和电话号码。该嵌套结构的树状表示如下图所示。

首先看DocuId这一列，对于r1，DocId=10，由于它是记录的开始，所以r=0，是required属性并且已定义，所以d=0，同样r2中的DocId=20，r=0，d=0。

对于Teachername这一列，在r1中，Teachername已定义，且它是第一条出现的记录，所以R=0，d为当前定义深度，d=1。R2中与r1情况相同。

对于Student.studentName这一列，在r1中第一条出现的记录为'Monkey'，并且为required属性，因此value1='Monkey'，r=0，d为当前定义深度减1，因此d=1；value2='Marry'，和上一个值value1在Student这一层是不相同的，换句话说，由于Student的重复导致value的重复，所以R=1，d=1；value3='Lucy'，和上一个值value2在Student这一层是不相同的，所以R=1，d=1。r2中该列只有一个值value=’a‘，R=0，D=1。

对于Student.contacts.Name这一列，r1中value1='Mather'，它是r1中的第一个值并且是已定义的，所以R=0，D=3；value2=’Father’，它和value1在contacts这个节点是不共享的，所以R=2，D=3；继续向下发现Name的上上级节点Students有重复的定义，因此用NULL值占位value3=NULL，它和前一个值在Students这个节点是不共享的，所以r=1，d=1；value4=’Bob’，它和前一个值在Students这一层不共享，并且该层为深度3的repeated属性值，所以R=1，D=3。在r2中该列有一个值，它是未定义的，但是Students这一层是已定义的，所以value=NUILL，R=0，D=1。

最后看一下Student.contacts.phonenumber这一列，r1中，value1=’123456’，它是r1中的第一个值并且是已定义的，所以R=0，D=3；value2='666666'，它与上一个记录相比在phonenumber这一层有所分别，所以R=3，D=3。接下来定义了一个重复的contacts，但并未定义phonenumber，因此用NULL占位，r=2，d=2；Value4=NULL，因为发现Students已定义，但contacts以及它的下级节点并未定义，所以R=1，D=1；value5='654321'，它和前一个值在Students这一层不共享，所以R=1，D=3。在r2中该列有一个值，它是未定义的，但是Students这一层是已定义的，所以value=NUILL，R=0，D=1。

三、Striping/Assembly算法

在Document中存在多个非required列，由于Parquet一条记录的数据分散的存储在不同的列中，如何组合不同的列值组成一条记录是由Striping/Assembly算法决定的，在该算法中列的每一个值都包含三部分：value、repetition level和definition level。

还是使用上述Document例子说明Striping/Assembly算法。

利用字段Student.contacts.Name来演示拆分和重组记录的striping and assembly 算法

首先计算出r,d的值。

因此最终存储的记录数据如下：

记录重组时根据表格构建记录：

• R=0, D=3, Value = “Mather”:
• R = 0 表示新记录。从根重新创建嵌套记录，直到定义级别（此处为 3），这是最大值。定义并插入该值。
• R=2, D=3:
• R = 2 表示级别为2的contacts列表中的新条目，则加入contacts新枝，定义级别3处插入该值。

R=1, D=1:

d小于最大定义级别，意味着该值为空值，而d=1表示定义了Students，所以只创建一个空的Students。

• R=1, D=3:
• R = 1 指级别为1的Students列表中的新条目，则加入Students新枝，定义级别3处插入该值。
• R=0, D=1: • R = 0 表示新记录。从根创建嵌套记录，直到定义级别 D = 1 。

参考资料

    [1] Dremel: Interactive Analysis of WebScale Datasets

    [2] 一文讲透大数据列存标准格式 - Parquet

    [3] Apache Parquet Documentation

    [4] 大数据：Parquet文件存储格式