引言

以我的机器为例来做一个简单的计算：

1. 执行cat /proc/cpuinfo |grep MHz|uniq可以看到目前机器中CPU频率，得到值 2494.140MHZ～=2494140000HZ，即每秒可以执行25亿个脉冲信号，换句话说每一个脉冲信号仅仅用时0.4ns（时钟周期），假设每个脉冲信号为一次CPU计算指令（当然实际不能简单对应，实际的CPU性能还是应该看IPC（Instructions Per Cycle））
2. 执行getconf LONG_BIT获取CPU的位数，执行lshw -C cpu|grep width获取数据总线宽度，没什么问题的话这里就是64，即CPU每秒可以计算2494.140MHZ*64bit~=18GB/s
3. 接下来计算内存带宽[21]，公式为：内存带宽（GB/s）= 内存总线宽度（bits）/ 8 × 内存频率（MHz）× Number of data transfers per clock = 2） 执行dmidecode -t memory，内存总线宽度为64 bits；内存频率为2933 MT/s～=1466MHZ；类型为: DDR4；所以得出结论内存带宽=21GB/S=1466*000000*8*2/1024/1024/1024
4. 网卡带宽：执行ip a检查网卡数量；执行ethtool eth0|grep Speed检查网卡带宽，得到10000Mb/s，假设每个TCP包全部装满MTU，即数据包1538字节，包头84字节，实际payload带宽为1.1GB/s
5. 磁盘带宽：hdparm -t，数据保密。

基于此结果可以推测在纯内存计算中，瓶颈其实在CPU计算中，数据从内存传输到CPU到数据是大于CPU可计算的值的，此时最重要的事情是加速计算（节省计算）。

不同介质导致的瓶颈使得数据存储格式的决策有很大的优化空间，主内存列存储和磁盘列存储之间存在根本差异。CPU列存储倾向于加速计算效率，节省CPU使用量；而磁盘列存储更注重压缩决策，对于存储在磁盘上的数据和网络传输的数据，从磁盘带宽/网络带宽是瓶颈，此时压缩大概率是一个很好的决定，因为原本CPU的资源就是充足的，数据总大小减小会使得整体效率更高。当然高额的压缩率也会利好于存储成本。

回到文章题目。我们简单了解下Arrow，Parquet，ORC代表三种高效的数据存储格式，后两种用于磁盘存储/网络传输，而Arrow用于内存计算。

Arrow

Arrow的定位在官网首页写的明明白白：

1. 作为内存列存格式标准，旨在直接和高效地用于计算目的
2. 提供多语言适配的工具集，作为开发平台
3. 建立Arrow生态系统

arrow优势可以在[7]中找到相关描述：

• Data adjacency for sequential access (scans)
• O(1) (constant-time) random access
• SIMD and vectorization-friendly
• Relocatable without “pointer swizzling”, allowing for true zero-copy access in shared memory
• For simple streaming and file-based serialization, we define a “encapsulated” message format for interprocess communication. Such messages can be “deserialized” into in-memory Arrow array objects by examining only the message metadata without any need to copy or move any of the actual data.

其中最吸引我的地方在于可以从网络包中直接零拷贝的拿到原始数据并构建内存数据结构[22]，这归功于Arrow定义的网络传输格式，这在带宽与CPU处理速度差别不大时可以大幅度提升内存处理效率。

Arrow也使用到了FlatBuffers作为传输格式中元信息的存储方式[24、25]。

在数据格式方面Arrow依旧和Parquet一样支持多类型嵌套数据结构，并定义了一系列基础数据格式的内存排列方式[7]。

官网中有一些常见问题的官方回复[14]。

Parquet

Nested Encoding

层次化编码是可嵌套的列式存储的基石，Parquet实际采用了Dremel[13]中描述的算法作为核心数据存储的方法，在这个问题上我们聚焦于扁平化和编解码。

对于一个多类型复杂嵌套结构来说想要扁平化。有两个问题要解决

Repetition Levels

首先要解决的问题给定的多个值判断他们到底属于哪些Record，比如在存储Name.Language.Code的过程中，如果只是存储en-us，en和en-gb，根本无法判断这个值属于哪个Name.Language。为了区分这些出现的情况，需要每个值附加一个Repetition Levels，标识了在此值字段路径中的哪个重复字段上重复出现。这个东西初次看还挺难理解的，我理解的要点是把整个列式嵌套结构看成一颗树，根节点为虚拟节点，根节点下一级别为实际的单个嵌套结构，此时可以发现Repetition Levels其实就是就是和第一个值的最近公共祖先。

注意永远可以看作虚拟节点的层级代表0，Name，Link都是1，Language为2。

此时看起来就清晰很多，我们以Name.Language.Country作为例子，首先第一个Name.Language中第一个有值，第二个为null，值分别为0和2。第二个Name没有值，所以Repetition Levels其实就是自己，即为1，当然因为此时在Name数组，所以就算有值，其实也是1；到了r2中，当Name.Language.Country不存在的时候自然就是0了。

论文中原始描述如下：

Consider field Code in Figure 2. It occurs three times in r1. Occurrences ‘en-us’ and ‘en’ are inside the first Name, while ’en-gb’ is in the third Name. To disambiguate these occurrences, we attach a repetition level to each value. It tells us at what repeated field in the field’s path the value has repeated. The field path Name.Language.Code contains two repeated fields, Name and Language. Hence, the repetition level of Code ranges between 0 and 2; level 0 denotes the start of a new record. Now suppose we are scanning record r1 top down. When we encounter ‘en-us’, we have not seen any repeated fields, i.e., the repetition level is 0. When we see ‘en’, field Language has repeated, so the repetition level is 2. Finally, when we encounter ‘en-gb’, Name has repeated most recently (Language occurred only once after Name), so the repetition level is 1. Thus, the repetition levels of Code values in r1 are 0, 2, 1.

Notice that the second Name in r1 does not contain any Code values. To determine that ‘en-gb’ occurs in the third Name and not in the second, we add a NULL value between ‘en’ and ‘en-gb’ (see Figure 3). Code is a required field in Language, so the fact that it is missing implies that Language is not defined. In general though, determining the level up to which nested records exist requires extra information.

Definition Levels

其次是判断某个field值属于哪一个层级，尤其是对NULL的判断，我使用Name.Language.Country作为例子，因为存在较高层次的值直接为NULL，需要判断到底哪个层级为null，比如Name.Language.Country其实在第一个和第二个Name中都没有值，但是第一个只是不存在Country，但是第二个是不存在Language，那NULL的层级就是不一样的。

论文中使用Links.Backward作为例子，因为第一个Links中不存在Backward，但是又是第一个出现的值，所以存在r=0，d=1。

论文中原始描述如下：

Each value of a field with path p, esp. every NULL, has a definition level specifying how many fields in p that could be undefined (because they are optional or repeated) are actually present in the record. To illustrate, observe that r1 has no Backward links. However, field Links is defined (at level 1). To preserve this information, we add a NULL value with definition level 1 to the Links.Backward column.
Similarly, the missing occurrence of Name.Language.Country in r2 carries a definition level 1, while its missing occurrences in r1 have definition levels 2 (inside Name.Language) and 1 (inside Name), respectively.

列化

本质上是如何把一个嵌套结构抽象成多个column，且高效计算Repetition and Definition Levels。DissectRecord会从decoder中分析Repetition and Definition Levels，然后写入对应FieldWriter，这是一个 tree of field writers，其结构与原始schema层次结构相同。

压缩

前文已经提到，Parquet旨在实现最大的空间效率，以减少磁盘存储空间和网络传输效率，所以可以预想Parquet一定会使用各种激进的压缩策略。目前支持的压缩算法有如下[15]：

1. UNCOMPRESSED
2. SNAPPY
3. GZIP
4. LZO
5. BROTLI
6. LZ4
7. ZSTD
8. LZ4_RAW

但是也正因为与Arrow的应用场景不同，这使得网络传输中还是存在序列化/反序列化成本。

ORC

关于ORC和Parquet的使用业界似乎有一致的共识，即ORC在查询，压缩，兼容性方面在大多数情况下优于Parquet，而且支持ACID与Update/Delete操作，甚至于在ORC的官网也有这样的文字：

但是感觉看了ORC的Optimized Row Columnar和Parquet的Dremel格式后，感觉差异更多的集中在对于不同系统的负载类型和工程实现上，这部分对我一个新人来说没法想明白。具体资料可以参考[16、17、18、19、20]

参考：

1. Apache Arrow：一种适合异构大数据系统的内存列存数据格式标准
2. Apache Arrow 内存数据
3. Apache Arrow vs. Parquet and ORC: Do we really need a third Apache project for columnar data representation?
4. An analysis of the strengths and weaknesses of Apache Arrow
5. Dremio blog: The Origin & History of Apache Arrow
6. Arrow数据格式-Arrow究竟是个啥
7. Arrow Columnar Format
8. 再来聊一聊 Parquet 列式存储格式
9. Apache Parquet列式存储格式介绍
10. Parquet文件是怎么被写入的-Row Groups，Pages，需要的内存，以及flush操作
11. The striping and assembly algorithms from the Dremel paper
12. Apache Parquet设计解读
13. Dremel: Interactive Analysis of Web-Scale Datasets
14. Arrow Frequently Asked Questions
15. Parquet compression definitions
16. Using Presto in our Big Data Platform on AWS
17. Even faster: Data at the speed of Presto ORC
18. LanguageManual ORC
19. Hive - ORC 文件存储格式详细解析
20. orc格式和parquet格式对比
21. https://en.wikipedia.org/wiki/Memory_bandwidth
22. Arrow Flight RPC
23. 深入浅出FlatBuffers原理
24. 深入浅出 FlatBuffers 之 Schema