数据库筑基课 - 列存之 Parquet

文中参考文档可点击阅读原文打开, 推荐《最好的PostgreSQL学习镜像》

数据库筑基课 - 列存之 Parquet

往期

• 数据库筑基课 - 大纲

• 数据库筑基课 - 行存之heap 表
  

• 数据库筑基课 - 行列混存之zedstore
  

本节: 列存之 Parquet

简介

Apache Parquet 是一种开源的列式数据文件格式，旨在实现高效的数据存储和检索。它提供高性能压缩和编码方案来批量处理复杂数据(包括基础类型数值、时间、字符串、布尔、数组、字节流等, Parquet 从一开始就考虑到了复杂的嵌套数据结构, 也支持嵌套类型例如JSON、list、map、dictionary等)，并且受到许多编程语言和分析工具的支持。

大规模分析型数据处理已经应用的越来越广泛，尤其是当前可以用廉价存储来保存海量业务数据的情况下。如何让分析师和工程师便捷的利用这些数据也变得越来越重要。列式存储（Column-oriented Storage）是大数据场景面向分析型数据的主流存储方式。与行式存储相比，列存由于可以只提取部分数据列、同列同数据类型使得拥有更好的编码及压缩方式对数据进行存储和计算，在 OLAP 场景下也能提供更好的 IO 性能。

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

Parquet 旨在支持非常高效的压缩和编码方案及扩展能力。多个项目已经证明了对数据应用正确的压缩和编码方案对性能的影响。Parquet 允许在每列级别指定压缩方案，并且具有面向未来性，未来如果发明或实现了更多编码时可以添加至Parquet项目中进行支持(这个怎么做到的呢? 可以简单理解为在meta信息里编入了密语, 用户可以通过密语来找到需要什么lib来支持数据页的加密、压缩、逻辑类型编解码等等, 相当于可以扩展加密、压缩、逻辑类型编解码lib库)。

虽然是文件, 但是Parquet还内置了索引, 包括BRIN范围索引、bloom 索引等. 索引是在往parquet文件写入数据时自动构建的, 索引信息被append到parquet文件末尾(也可以扩展为独立存储). 有了索引, 在读取数据时就可以高效的根据条件过滤不需要访问的page, 大幅提高访问速度.

再次提醒: 不要本能的以为parquet是简单的和text,csv类似的数据文件, 例如我们在一个text文件中搜索时, 肯定是需要整个文件遍历的. 但是Parquet文件内部有自己的数据组织, 有head、row group、column chunk、page、foot(meta + column index存储了索引min,max bound及指向parquet file内的page offset(或换算值). + bloom data(每个page内的column values计算得出的bloom filter mask, 以及指向parquet file内的page offset(或换算值))等). 使得使用parquet能高效存储、检索数据. 而且parquet的封装协议还能升级改进, 也就是说未来可能还能有更高效的组织形式.

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

优势 & 适合场景

优势

• 采用列式存储, 仅需访问目标列, 可以减少内存和IO访问
• 采用列存可以结合CPU批量执行指令, 提高大批量数据处理速度
• 采用列式存储, 同列同类型, 支持更多的压缩编码技术, 意味着更高压缩比, 更省空间和内存
• parquet还内置了column index , bloom data, 可以根据where条件对数据进行高效过滤

适合OLAP场景, 数据分析型产品、数据湖产品等.

劣势 & 不适合场景

劣势

• 如果需要查找tuple(记录)的所有字段或大多数字段, 由于是按列分开存储的, 所以需要访问更多的page.
• 无法支持物理更新、删除, 如果有这类需求, 需要重整数据
• 不太适合小数据量的高频写入和持久化, 可能导致压缩比下降, 可能导致空间浪费(文件尾部foot信息每次都需要刷新).
• 不适合高并发的小事务查询(因为没有单点精准索引/secondary index)

不适合OLTP业务场景.

原理

行存 VS 列存

比如下图是拥有 A/B/C 3 个字段的简单示意表：

在面向行的存储中，每列的数据依次排成一行，如下所示：

而在面向列的存储中，相同列的数据存储在一起：

显而易见，行存适用于数据整行读取场景，而列存适用于只读取部分列数据（统计分析等）场景。

parquet 数据组织结构和术语

Block (hdfs block)：即指 HDFS Block，Parquet 的设计与 HDFS 完全兼容。Block 是 HDFS 文件存储的基本单位，HDFS 会维护一个 Block 的多个副本。在 Hadoop 1.x 版本中 Block 默认大小 64M，Hadoop 2.x 版本中默认大小为 128M。

File：HDFS 文件，保存了该文件的元数据信息，但可以不包含实际数据（由 Block 保存）。

Row group：按照行将数据划分为多个逻辑分区。一个 Row group（行组）由每个列的一个列块（Column Chunk）组成。

Column chunk：一个列的列块，分布在行组(Row group)当中，同一个row group内的Column chunks在文件中保证是连续存储的(例如group 1: columnA chunk, columnB chunk, columnC chunk, ...; group 2: columnA chunk, columnB chunk, columnC chunk, ...;)。

Page：一个列块(Column chunk)切分成多个 Pages（页面），概念上讲，页面是 Parquet 中最小的基础单元（就压缩和编码方面而言）。一个列块(Column chunk)中可以由多个类型的页面组成(例如字典page、数据page. 未来还能扩展更多的page type)。

Hierarchically, a file consists of one or more row groups. A row group contains exactly one column chunk per column. Column chunks contain one or more pages.

并行化执行的基本单元: 

• MapReduce - File/Row Group（一个任务对应一个文件或一个行组）
• IO - Column chunk（任务中的 IO 以列块为单位进行读取）
• Encoding/Compression - Page（编码格式和压缩一次以一个页面为单位进行）

配置建议: 

行组大小（Row group size）：更大的行组允许更大的列块，这使得可以执行更大的顺序 IO。不过更大的行组需要更大的写缓存。Parquet 建议使用较大的行组（512MB-1GB）。此外由于可能需要读取整个行组，因此最好一个行组能完全适配一个 HDFS Block。因此，HDFS 块大小也需要相应的设置更大。一个较优的读取配置为：行组大小 1GB，HDFS 块大小 1GB，每个 HDFS 文件对应 1 个 HDFS 块。

数据页大小（Data page size）：数据页应视为不可分割的，因此较小的数据页可实现更细粒度的读取（例如单行查找）。但较大的页面可以减少空间的开销（减少 page header 数量）和潜在的较少的解析开销（处理 headers）。Parquet 建议的页面大小为 8KB。

parquet 索引

parquet的范围索引有点类似PG的brin, 支持等值、范围、大于、小于等查询. 实际上就是存储每个page里面列的边界值(例如 pageN:min(column_value),max(column_value) , pageM , ... ), 在筛选数据时, 对于已排序字段, 不需要扫描整个brin的内容, 可以使用二分法在brin中进行快速查找, 找到满足条件的pages的offset在parquet file中进行快速访问. 对于非排序字段就和PG brin索引一样扫描整个索引内容来得到满足条件的pages的offset.

parquet的bloom索引有点类似PG的bloom索引, bloom data也在parquet文件末尾, 但是存放在column index的前面. 通过 bloom filter 可以支持等于、不等于查询. 由于是通过少量bit占位来实现的失真存储, 所以不等于一定为真, 等于则可能为假.

关于bloom,brin更详细的原理可以阅读:

• 《PostgreSQL bloom 索引原理》
• 《PostgreSQL 9.6 黑科技 bloom 算法索引，一个索引支撑任意列组合查询》
• 《重新发现PostgreSQL之美 - 14 bloom 布隆过滤器索引》
• 《PostgreSQL BRIN索引的pages_per_range选项优化与内核代码优化思考》
• 《PostgreSQL 物联网黑科技 - 瘦身几百倍的索引(BRIN index)》
• 《重新发现PostgreSQL之美 - 13 brin 时序索引》

嵌套类型的表达

1、schema 协议

想要深入的了解 Parquet 嵌套类型存储格式首先需要理解它的数据模型。Parquet 采用了一个类似 Google Protobuf 的协议来描述存储数据的 schema。如下是 Parquet 数据 schema 的一个简单示例：

message AddressBook {  
  required string owner;  
  repeated string ownerPhoneNumbers;  
  repeated group contacts {  
    required string name;  
    optional string phoneNumber;  
  }  
}  

schema 的最上层是 message(可以简单理解为字段名称)，里面可以包含一系列field。每个field都拥有 3 个属性：重复性（repetition）、类型（type）以及名称（name）。field类型可以是一个 group 或者原子类型（如 int、boolean、string 等），group 可以用来表示数据的嵌套结构。field的重复性有三种情况：

• required：有且只有一次
• optional：0 或 1 次
• repeated：0 或多次

这个模型非常的简洁。一些复杂的数据类型如：Map、List 和 Set 也可以用重复的field（repeated fields） + groups 来表达，因此也就不用再单独定义这些类型。

采用 repeated field 表达 List 或者 Set 的示例：

采用 repeated group（包含 key 和 value，其中 key 是 required） 来表达 Map 的示例：

2、列式存储格式

试想一下，为了使数据能够按列存储，对于一条记录（Record），首先要将其按列（Column）进行拆分。对于扁平（Flat）结构数据，拆分比较直观，一个字段即对应一列，而嵌套格式数据会复杂些。Dremel/Parquet 中，提出以树状层级的形式组织 schema 中的字段（Field），树的叶子结点对应一个原子类型字段，这样这个模型能同时覆盖扁平结构和嵌套结构数据（扁平结构只是嵌套结构的一种特例）。嵌套字段的完整路径使用简单的点分符号表示，如，contacts. name。

AddressBook 例子以树状结构展示的样式:

列存连续的存储一个字段的值，以便进行高效的编码压缩及快速的读取。Dremel 中行存 vs 列存的图示：

3、Repetition and Definition Levels

嵌套格式数据的Repetition and Definition Levels是最难理解对部分, 我后面会再次解释, 先转载亮亮的文章原文.

对于嵌套格式列存，除了按列拆分进行连续的存储，还需要能够“无损”的保留嵌套格式的结构化信息，以便正确的重建记录。

只有field值不能表达清楚记录的结构。给定一个重复field的两个值，我们不知道此值是在嵌套路径中的什么“级别”被重复的（比如，这些值是来自两个不同的记录(row)，还是相同的记录(row)中两个重复的值）。同样的，给出一个缺失的可选字段，我们不知道整个路径有多少字段被显示定义了。

Dremel 提出了 Repetition Level（重复级别）和 Definition Level（定义级别）两个概念，用以解决这个问题。并实现了记录中任意一个field的恢复都不需要依赖其它field，且可以对任意field子集按原始嵌套格式进行重建。

我后面会用下图这个例子重新梳理讲解

Repetition levels：用以表示在该field路径上哪个节点进行了重复（at what repeated field in the field’s path the value has repeated）。

一个重复field存储的列值，有可能来自不同记录，也可能由同一记录的不同层级节点重复导致。比如图 8 中的 Code field，他在 r1 记录中出现了 3 次，分别是field Name 和 Language 重复导致的，其中 Language 先重复了 2 次，Name field再重复了 1 次。

Repetition Levels 采用数字代表重复节点的层级。根据树形层次结构，根结点为 0、下一层级为 1… 依次类推。根结点的重复暗含了记录的重复，也即 r=0 代表新记录的开始。required 和 optional field不需要 repetition level，只有可重复的field需要。因此，上述 Code field的 repetition levels 范围为 0-2。当我们从上往下扫描 r1 记录，首先遇到 Code 的值是“en-us”，由于它之前没有该field路径相关的field出现，因此 r=0；其次遇到“en”，是 Language 层级重复导致的，r=2；最后遇到“en-gb”，是 Name 层级重复导致的，因此 r=1。所以，Code field的 repetition levels 在 r1 记录中是“0,2,1”。

需要注意的是，r1 记录中的第二个重复 Name，由于其不包含 Code field，为了区分“en-gb”值是来自记录中的第三个 Name 而不是第二个，我们需要在“en”和“en-gb”之间插入一个值“null”。由于它是 Name 级重复的，因此它的 r=1。另外还需要注意一些隐含信息，比如 Code 是 required field类型，因此一旦 Code 出现未定义，则隐含表明其上级 Language 也肯定未定义。

Definition Levels：用以表示该field路径上有多少可选的field实际进行了定义（how many fields in p that could be undefined (because they are optional or repeated) are actually present）。

光有 Repetition Levels 尚无法完全保留嵌套结构信息，考虑上述图 8 中 r1 记录的 Backward field。由于 r1 中未定义 Backward field，因此我们插入一个“null”并设置 r=0。但 Backward 的上级 Links field在 r1 中显式的进行了定义，null 和 r=0 无法再表达出这一层信息。因此需要额外再添加 Definition Levels 定义记录可选field出现的个数，Backward 的路径上出现 1 个可选field Links，因此它的 d=1。

有了 Definition Levels 我们就可以清楚的知道该值出现在field路径的第几层，对未定义field的 null 和field实际的值为 null 也能进行区分。只有 optional 和 repeated field需要 Definition Levels 定义，因为 required field已经隐含了field肯定被定义（这可以减少 Definition Levels 需要描述的数字，并在一定程度上节省后续的存储空间）。另外一些其他的隐含信息：如果 Definition Levels 小于路径中 optional + repeated field的数量，则该field的值肯定为 null；Definition Levels 的值为 0 隐含了 Repeated Levels 也为 0（路径中没有 optional/repeated field或整个路径未定义）。

4、striping and assembly 算法

现在把 Repetition Levels 和 Definition Levels 两个概念一起考虑。还是沿用上述 AddressBook 例子。下表显示了 AddressBook 中每个field的最大重复和定义级别，并解释了为什么它们小于列的深度：

假设这是两条真实的 AddressBook 数据：

AddressBook {  
  owner: "Julien Le Dem",  
  ownerPhoneNumbers: "555 123 4567",  
  ownerPhoneNumbers: "555 666 1337",  
  contacts: {  
    name: "Dmitriy Ryaboy",  
    phoneNumber: "555 987 6543",  
  },  
  contacts: {  
    name: "Chris Aniszczyk"  
  }  
}  
AddressBook {  
  owner: "A. Nonymous"  
}  

我们采用 contacts.phoneNumber 字段(field)来演示一下拆解和重组记录的 striping and assembly 算法。

仅针对 contacts.phoneNumber 字段投影后，数据具有如下结构：

AddressBook {  
  contacts: {  
    phoneNumber: "555 987 6543"  
  }  
  contacts: {  
  }  
}  
AddressBook {  
}  

计算可得该该字段对应的数据如下（R =重复级别，D =定义级别）：

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

• contacts.phoneNumber: “555 987 6543”
• new record: R = 0
• value is defined: D = maximum (2)
• contacts.phoneNumber: null
• repeated contacts: R = 1
• only defined up to contacts: D = 1
• contacts: null
• new record: R = 0
• only defined up to AddressBook: D = 0

使用图表展示（注意其中的 null 值并不会实际存储，原因如上所说只要 Definition Levels 小于其 max 值即隐含该字段值为 null）：

在重组该记录时，我们重复读取该字段的值：

• R=0, D=2, Value = “555 987 6543”:
• R = 0 means a new record. We recreate the nested records from the root until the definition level (here 2)
• D = 2 which is the maximum. The value is defined and is inserted.
• R=1, D=1:
• R = 1 means a new entry in the contacts list at level 1.
• D = 1 means contacts is defined but not phoneNumber, so we just create an empty contacts.
• R=0, D=0:
• R = 0 means a new record. we create the nested records from the root until the definition level
• D = 0 => contacts is actually null, so we only have an empty AddressBook

5、Parquet 文件格式

Parquet 文件格式是自解析的，采用 thrift 格式定义的文件 schema 以及其他元数据信息一起存储在文件的末尾。

文件存储格式示例：

4-byte magic number "PAR1"  
<Column 1 Chunk 1 + Column Metadata>  
<Column 2 Chunk 1 + Column Metadata>  
...  
<Column N Chunk 1 + Column Metadata>  
<Column 1 Chunk 2 + Column Metadata>  
<Column 2 Chunk 2 + Column Metadata>  
...  
<Column N Chunk 2 + Column Metadata>  
...  
<Column 1 Chunk M + Column Metadata>  
<Column 2 Chunk M + Column Metadata>  
...  
<Column N Chunk M + Column Metadata>  
File Metadata  
4-byte length in bytes of file metadata  
4-byte magic number "PAR1"  

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

具体的存储格式展示图：

6、元数据信息

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

7、Parquet 数据类型

在实现层级上，Parquet 只保留了最精简的部分数据类型，以方便存储和读写。在其上有逻辑类型（Logical Types）以供扩展，比如：逻辑类型 strings 就映射为带有 UTF8 标识的二进制 byte arrays 进行存储。

Types：

• BOOLEAN: 1 bit boolean
• INT32: 32 bit signed ints
• INT64: 64 bit signed ints
• INT96: 96 bit signed ints
• FLOAT: IEEE 32-bit floating point values
• DOUBLE: IEEE 64-bit floating point values
• BYTE_ARRAY: arbitrarily long byte arrays.

逻辑类型是在以上基础类型之上封装的类型, 更多说明请参考：LogicalTypes.md。

8、Encoding

数据编码的实现大部分和原理部分所阐述的一致，这里不再重复说明，更多细节可参考：Encodings.md。

9、Column chunks 存储

Column chunks 由一个个 Pages 组成，Reader 在读取的时候可以根据 page header 信息跳过不感兴趣的页面。page header 中还存储着页面数据编码和压缩的信息。

10、错误情况处理

如果文件元数据损坏，则整个文件将丢失。如果列元数据损坏，则该列块将丢失（但其他行组中该列的列块还可以使用）。如果 page header 损坏，则该列块中的剩余页面都将丢失。如果页面中的数据损坏，则该页面将丢失。较小的文件行组配置，可以更有效地抵抗损坏。

可恢复性: 每次写入row group数据后, 读取前一个row group后面存储的meta信息, 与当前row group meta增量合并为一个新的meta(包含所有row group的信息), 写入当前row group文件末尾. 结合fsync文件持久化, 可以保证数据可靠性. 万一当前写入的meta损坏了, 可以通过找到之前row group的meta, 从而回复之前的所有row group的数据.

细说 Repetition and Definition Levels

给出Document列的schema:

message Document {  
  required int64 DocID;  
  optional group Links {  
    repeated int64 Backward;  
    repeated int64 Forward; }  
  repeated group Name {  
    repeated group Language {  
      requited string Code;  
      optional string Country; }  
    optional string Url; }}  

Row1:

DocID: 10  
Links  
  Forward: 20  
  Forward: 40  
  Forward: 60  
Name  
  Language   
    Code: 'en-us'  
    Country: 'us'  
  Language  
    Code: 'en'    
  Url: 'http://A'  
Name  
  Url: 'http://B'  
Name  
  Language   
    Code: 'en-gb'  
    Country: 'gb'  

Row2:

DocID: 20  
Links  
  Backward: 10  
  Backward: 30  
  Forward: 80  
Name  
  Url: 'http://C'  

由于Document列是树状结构, 得到所有field的路径:

DocID  
Name.Url  
Links.Forward  
Links.Backward  
Name.Language.Code  
Name.Language.Country  

Repetition levels：

术语解释: （at what repeated field in the field’s path the value has repeated）.

计算方法:

• 把每个repeated field想象成1个bit位, 在该field路径中出现过的repeated field都设置为1.
• 如何计算Repetition levels:
• 在当前路径中哪个repeated节点发生了重复.
• 当前value的路径与上一个value的路径“bitAnd”计算, 得到sum(1). 即:
• 新Row第一次出现的值repetition levels始终为0. 因为新的Row第一次出现的值没有上一个可比较的value, 所以相交始终得到0. (只要repeated=0, 说明这是新Row)

为什么要填NULL?

• 如上Row1和Row2的数据, 从上至下扫描数据时, 如果“端节点field”值缺失, 但是在“从顶节点到端节点field”的完整路径(也就是下面2张excel表截图中每个粗框内的第1行第1列指出的路径)中的上层field(或者上上层, 上上...上层 field)有值, 则需要对缺失节点(field)填充NULL.

下图中标黄的为repeated field, 与计算Repetition levels相关

Definition levels: 

计算方法:

• 路径中有几个optional或repeated field?(不含被迫填充NULL的field)

下标黄的为repeated及optional field, 与计算Definition levels相关

Repetition level 和 Definition levels 计算例子如下表格.

DEMO

demo可以参考duckdb中parquet的使用

• 《PG被DuckDB碾压,该反省哪些方面? DuckDB v0.10.3 在Macmini 2023款上的tpch性能表现如何? PostgreSQL使用duckdb_fdw 的tpch加速性能表现如何?》
• 《DuckDB 采用外部 parquet 格式存储 - tpch 测试 - in_memory VS in_parquet》
• 《DuckDB 数据库的数据能不能超出内存限制? 以及推荐的使用方法 - parquet》
• 《DuckDB 读写 Parquet 文件 - 同时支持远程s3, oss, http等parquet文件读写》
• 《DuckDB parquet 分区表 / Delta Lake(数据湖) 应用》
• 《DuckDB DataLake 场景使用举例 - aliyun OSS对象存储parquet》
• 《德说-第140期, duckdb+容器+parquet+对象存储, 实现SaaS场景, 低代码拖拉拽多维度实时分析 降本提效》

扩展问题

扩展阅读

参考

• Wiki: https://en.wikipedia.org/wiki/Apache_Parquet
• 文档: https://parquet.apache.org/docs
• 代码: https://github.com/apache/parquet-format
• 代码: https://github.com/apache/parquet-format/blob/master/src/main/thrift/parquet.thrift
• blog: https://arrow.apache.org/blog/2022/10/05/arrow-parquet-encoding-part-1
• blog: https://arrow.apache.org/blog/2022/10/08/arrow-parquet-encoding-part-2
• blog: https://arrow.apache.org/blog/2022/10/17/arrow-parquet-encoding-part-3
• blog: 陈亮亮 一文讲透大数据列存标准格式 - Parquet
• blog: 处理海量数据：列式存储综述（存储篇）
• 论文: Dremel: Interactive Analysis of WebScale Datasets
• 论文导读: Dremel made simple with Parquet
• 论文导读翻译: 经典论文翻译导读之《Dremel: Interactive Analysis of WebScale Datasets》

休息片刻

参考文档点击阅读原文获得

感谢关注我的github (https://github.com/digoal/blog) 及视频号: