7月QCon广州站2022,关注Web 3.0、数据架构选型、数字化转型等热门话题,点击了解 了解详情
写点什么

Apache Arrow:一种适合异构大数据系统的内存列存数据格式标准

  • 2020 年 12 月 12 日
  • 本文字数:4395 字

    阅读完需:约 14 分钟

Apache Arrow:一种适合异构大数据系统的内存列存数据格式标准

本文介绍一种内存列存数据格式:Apache Arrow,它有一个非常大的愿景:提供内存数据分析 (in-memory analytics) 的开发平台,让数据在异构大数据系统间移动、处理地更快。同时,比较特别的是这个项目的启动形式与其他项目也不相同,Arrow 项目的草台班子由 5 个 Apache Members、6 个 PMC Chairs 和一些其它项目的 PMC 及 committer 构成,他们直接找到 ASF 董事会,征得同意后直接以顶级 Apache 项目身份启动。


本文从以下几个方面来介绍 Arrow 项目:


  • Arrow 项目的来源

  • Arrow 如何表示定长、变长和嵌套数据

  • 内存列存数据格式与磁盘列存数据格式的设计取舍


注:Arrow 即可以指内存列存数据格式,也可以指 Apache Arrow 项目整体,因此下文中将用 「Arrow」 表示格式本身,「Arrow 项目」表示整体项目。

Arrow 项目简介


现存的大数据分析系统基本都基于各自不同的内存数据结构,这就会带来一系列的重复工作:从计算引擎上看,算法必须基于项目特有的数据结构、API 与算法之间出现不必要的耦合;从数据获取上看,数据加载时必须反序列化,而每一种数据源都需要单独实现相应的加载器;从生态系统上看,跨项目、跨语言的合作无形之中被阻隔。能否减少或消除数据在不同系统间序列化、反序列化的成本?能否跨项目复用算法及 IO 工具?能否推动更广义的合作,让数据分析系统的开发者联合起来?在这样的使命驱动下,Arrow 就诞生了。


与其它项目不同,Arrow 项目的草台班子由 5 个 Apache Members、6 个 PMC Chairs 和一些其它项目的 PMC 及 committer 构成,他们直接找到 ASF 董事会,征得同意后直接以顶级 Apache 项目身份启动。想了解项目的详细历史可以阅读项目 Chair,Jacques Nadeau 写的这篇博客。另外,这张 google sheet 记录着项目的取名过程,取名为 Arrow 的原因是:”math symbol for vector. and arrows are fast. also alphabetically will show up on top.” 可以说考虑得相当全面 😂。


Arrow 项目的愿景是提供内存数据分析 (in-memory analytics) 的开发平台,让数据在异构大数据系统间移动、处理地更快:

项目主要由 3 部分构成:


  • 为分析查询引擎 (analytical query engines)、数据帧 (data frames) 设计的内存列存数据格式

  • 用于 IPC/RPC 的二进制协议

  • 用于构建数据处理应用的开发平台


整个项目的基石是基于内存的列存数据格式,现在将它的特点罗列如下:


  • 标准化 (standardized),与语言无关 (language-independent)

  • 同时支持平铺 (flat) 和层级 (hierarchical) 数据结构

  • 硬件感知 (hardware-aware)

基于内存的列存格式


详细、准确的格式定义请阅读官方文档,本节内容参考了官方文档及 Daniel Abadi 的这篇博客


在实践中,工程师通常会将系统中的数据通过多个二维数据表建模,每张数据表的一行表示一个实体 (entity),一列表示同一属性。然而,在硬件中存储器通常是一维的,即计算机程序只能线性地、沿同一方向地从内存或硬盘中读取数据,因此存储二维数据表就有两种典型方案:行存列存。通常前者适用于 OLTP 场景,后者适用于 OLAP 场景,Arrow 是面向数据分析开发的,因此采用后者。



任何一张数据表都可能由不类型的数据列构成。以某张用户表为例,表中可能包含如年龄 (integer)、姓名 (varchar)、出生日期 (date) 等属性。Arrow 将数据表中所有可能的列数据分成两类,定长和变长,并基于定长和变长数据类型构建出更复杂的嵌套数据类型。

Fixed-width data types


定长的数据列格式如下所示:


1
2
3
4
5
6
type FixedColumn struct {
  data       []byte
  length     int
  nullCount  int
  nullBitmap []byte // bit 0 is null, 1 is not null
}


除了数据数组 (data) 外,还包含:


  • 数组长度 (length)

  • null 元素的个数 (nullCount)

  • null 位图 (nullBitmap)


以 Int32 数组:[1, null, 2, 4, 8] 为例,它的结构如下:


1
2
3
4
5
6
7
8
9
length: 5, nullCount: 1
nullBitmap:
|Byte 0 (null bitmap) | Bytes 1-63            |
|---------------------|-----------------------|
| 00011101            | 0 (padding)           |
data:
|Bytes 0-3   | Bytes 4-7   | Bytes 8-11  | Bytes 12-15 | Bytes 16-19 | Bytes 20-63 |
|------------|-------------|-------------|-------------|-------------|-------------|
| 1          | unspecified | 2           | 4           | 8           | unspecified |


这里有一个值得关注的设计决定,无论数组中的某个元素 (cell) 是否是 null,在定长数据格式中 Arrow 都会让该元素占据规定长度的空间;另一种备选方案就是不给 null 元素分配任何空间。前者可以利用指针代数支持 O(1) 的随机访问,后者在随机访问时需要先利用 nullBitmap 计算出位移。如果是顺序访问,后者需要的内存带宽更小,性能更优,因此这里主要体现的是存储空间与随机访问性能的权衡,Arrow 选择倾向是后者。


从 nullBitmap 的结构可以看出,Arrow 采用 little-endian 存储字节数据。

Variable-width data types


变长的数据列格式如下所示:


1
2
3
4
5
6
7
type VarColumn struct {
  data       []byte
  offsets    []int64
  length     int
  nullCount  int
  nullBitmap []byte // bit 0 is null, 1 is not null
}


可以看出,比定长列仅多存一个偏移量数组 (offsets)。offsets 的第一个元素固定为 0,最后一个元素为数据的长度,即与 length 相等,那么关于第 i 个变长元素:


1
2
pos  := column.offsets[i]                       // 位置
size := column.offsets[i+1] - column.offsets[i] // 大小


另一种备选方案是在 data 中利用特殊的字符分隔不同元素,在个别查询场景下,后者能取得更优的性能。如扫描字符串列中包含某两个连续字母的所有列:利用 Arrow 的格式需要频繁地访问 offsets 来遍历 data,但利用特殊分隔符的解决方案直接遍历一次 data 即可。而在其它场景下,如查询某字符串列中值和 “hello world” 相等的字符串,这时利用 offsets 能过滤掉所有长度不为 11 的列,因此利用 Arrow 的格式能获取更优的性能。

Nested Data


数据处理过程中,一些复杂数据类型如 JSON、struct、union 都很受开发者欢迎,我们可以将这些数据类型归类为嵌套数据类型。Arrow 处理嵌套数据类型的方式很优雅,并未引入定长和变长数据列之外的概念,而是直接利用二者来构建。假设以一所大学的班级 (Class) 信息数据列为例,该列中有以下两条数据:


1
2
3
4
5
6
7
8
9
10
11
// 1
Name:       Introduction to Database Systems
Instructor: Daniel Abadi
Students:   Alice, Bob, Charlie
Year:       2019

// 2
Name:       Advanced Topics in Database Systems
Instructor: Daniel Abadi
Students:   Andrew, Beatrice
Year:       2020


我们可以将改嵌套数据结构分成 4 列:Name、Instructor、Students 以及 Year,其中 Name 和 Instructor 是变长字符串列,Year 是定长整数列,Students 是字符串数组列 (二维数组),它们的存储结构分别如下所示:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
Name Column:
data:      Introduction to Database SystemsAdvanced Topics in Database Systems
offsets:   0, 32, 67
length:    2
nullCount: 0
nullBitmap: 
| Byte 0   | Bytes 1-63 |
|----------|------------|
| 00000011 | 0 (padding)|


Instructor Column:
data:      Daniel AbadiDaniel Abadi
offsets:   0, 12, 24
length:    2
nullCount: 0
nullBitmap:
| Byte 0   | Bytes 1-63 |
|----------|------------|
| 00000011 | 0 (padding)|


Students Column
data:                        AliceBobCharlieAndrewBeatrice
students offsets:            0, 5, 8, 15, 21, 29
students length:             5
students nullCount:          0
students nullBitmap:
| Byte 0   | Bytes 1-63 |
|----------|------------|
| 00011111 | 0 (padding)|
nested student list offsets:   0, 3, 5
nested student list length:    2
nested student list nullCount: 0
nested student list nullBitmap:
| Byte 0   | Bytes 1-63 |
|----------|------------|
| 00000011 | 0 (padding)|

Year Column
data:       2019|2019
length:     2
nullCount:  0
nullBitmap:
| Byte 0   | Bytes 1-63 |
|----------|------------|
| 00000011 | 0 (padding)|


这里的 Students 列本身就是嵌套数据结构,而外层的 Class 表包含了 Students 列,可以看出这种巧思能支持无限嵌套,是很值得称赞的设计。

Buffer alignment and padding


Arrow 列存格式的所有实现都需要考虑数据内存地址的对齐 (alignment) 以及填充 (padding),通常推荐将地址按 8 或 64 字节对齐,若不足 8 或 64 字节的整数倍则按需补全。这主要是为了利用现代 CPU 的 SIMD 指令,将计算向量化。

Memory-oriented columnar format


计算机发展的几十年来,绝大多数数据引擎都采用行存格式,主要原因在于早期的数据应用负载模式基本都逃不出单个实体的增删改查。面对此类负载,如果采用列存格式存储数据,读取一个实体数据就需要在存储器上来回跳跃,找到该实体的不同属性,本质上是在执行随机访问。但随着时间的推移,数据的增多,负载变得更加复杂,数据分析的负载模式逐渐显露,即每次访问一组实体的少数几个属性,然后聚合出分析结果,这时候列存格式的地位便逐渐提高。


在 Hadoop 生态中,Apache Parquet 和 Apache ORC 已经成为最流行的两种文件存储格式,它们核心价值也是围绕着列存数据格式建立,那么我们为什么还需要 Arrow?这里我们可以从两个角度来看待数据存储:


  • 存储格式:行存 (row-wise/row-based)、列存 (column-wise/column-based/columnar)

  • 主要存储器:面向磁盘 (disk-oriented)、面向内存 (memory-oriented)


尽管三者都采用列存格式,但 Parquet 和 ORC 是面向磁盘设计,而 Arrow 是面向内存设计。为了理解面向磁盘设计与面向内存设计的区别,我们来看 Daniel Abadi 做的一个实验

Daniel Abadi 的实验


在一台 Amazon EC2 的 t2.medium 实例上,创建一张包含 60,000,000 行数据的表,每行包含 6 个属性,每个属性值都是 int32 类型的数据,因此每行需要 24 字节空间,整张表占用约 1.5GB 空间。我们将这张表分别用行存格式和列存格式保存一份,然后执行一个简单的查询:在第一列中查找与特定值相等的数据,即:


1
SELECT a FROM t WHERE t.a = 477638700;


不论是行存还是列存版本,CPU 的工作都是获取整数与目标整数进行比较。但在行存版本中执行该查询需要扫描每行,即全部 1.5GB 数据,而在列存版本中执行该查询只需扫描第一列,即 0.25GB 数据,因此后者的执行效率理论上应该是前者的 6 倍。然而,实际的结果如下所示:



列存版本与行存版本的性能竟然相差无几!原因在于实验执行时关闭了所有 CPU 优化 (vectorization/SIMD processing),使得该查询的瓶颈出现在 CPU 处理上。我们来一起分析一下其中的原因:根据经验,从内存扫描数据到 CPU 中的吞吐能达到 30GB/s,现代 CPU 的处理频率能达到 3GHz,即每秒 30 亿 CPU 指令,因此即便处理器可以在一个 CPU 周期执行 32 位整数比较,它的吞吐最多为 12 GB/s,远远小于内存输送数据的吞吐。因此不论是行存还是列存,从内存中输送 0.25GB 还是 1.5GB 数据到 CPU 中,都不会对结果有大的影响。


如果打开 CPU 优化选项,情况就大不相同。对于列存数据,只要这些整数在内存中连续存放,编译器可以将简单的操作向量化,如 32 位整数的比较。通常,向量化后处理器在单条指令中能够同时将 4 个 32 位整数与指定值比较。优化后再执行相同的查询,实验的结果如下图所示:



可以看到与预期相符的 4 倍差异。不过值得注意的是,此时 CPU 仍然是瓶颈。如果内存带宽是瓶颈的话,我们将能够看到列存版本与行存版本的性能差异达到 6 倍。


从以上实验可以看出,针对少量属性的顺序扫描查询的工作负载,列存格式要优于行存格式,这与数据是在磁盘上还是内存中无关,但它们优于行存格式的理由不同。如果以磁盘为主要存储,CPU 的处理速度要远远高于数据从磁盘移动到 CPU 的速度,列存格式的优势在于能通过更适合的压缩算法减少磁盘 IO;如果以内存为主要存储,数据移动速度的影响将变得微不足道,此时列存格式的优势在于它能够更好地利用向量化处理。


这个实验告诉我们:数据存储格式的设计决定在不同瓶颈下的目的不同。最典型的就是压缩,对于 disk-oriented 场景,更高的压缩率几乎总是个好主意,利用计算资源换取空间可以利用更多的 CPU 资源,减轻磁盘 IO 的压力;对于 memory-oriented 场景,压缩只会让 CPU 更加不堪重负。

Apache Parquet/ORC vs. Apache Arrow


现在要对比 Parquet/ORC 与 Arrow 就变得容易一些。因为 Parquet 和 ORC 是为磁盘而设计,支持高压缩率的压缩算法,如 snappy、gzip、zlib 等压缩技术就十分必要。而 Arrow 为内存而设计,对压缩算法几乎没有要求,更倾向于直接存储原生的二进制数据。面向磁盘与面向内存的另一个不同点在于:尽管磁盘和内存的顺序访问效率都要高于随机访问,但在磁盘中,这个差异在 2-3 个数量级,而在内存中通常在 1 个数量级内。因此要均摊一次随机访问的成本,需要在磁盘中连续读取上千条数据,而在内存中仅需要连续读取十条左右的数据。这种差异意味着 内存场景下的 batch 大小 (如 Arrow 的 64KB) 要小于磁盘场景下的 batch 大小。

参考



2020 年 12 月 12 日 10:004301

评论

发布
暂无评论
发现更多内容

信息安全等级保护是什么意思?开展信息安全等级保护工作有啥意义?

行云管家

云计算 网络安全 等级保护 信息安全等级保护

官方线索 | 阿里云1024程序员创造营

穿过生命散发芬芳

1024我在现场

第 24 章 -《Linux 一学就会》- shell中色彩处理和awk使用技巧

学神来啦

Linux linux运维 linux云计算 linux一学就会

Flux架构思想在度咔App中的实践

百度Geek说

百度 架构 后端 短视频 Flux

IOS技术分享| ARCall视频通话重构

anyRTC开发者

ios 音视频 语音通话 视频通话 视频呼叫

英特尔On技术创新峰会公布开发者重点投入计划,全面赋能开发者

科技新消息

安全漏洞的复现与总结

网络安全学海

网络安全 信息安全 渗透测试 WEB安全 漏洞挖掘

实时大数据Flink知识结构(超全整理,附知识脑图)

大象灵感

大数据 flink spark 实时数仓 流处理

【IT运维小知识】安全组是什么意思?

行云管家

网络安全 安全 数据安全 安全组 IT运维

短短 146 天就成为 Apache APISIX Committer,我是怎么做到的?

Apache APISIX 中国社区

成长笔记 API网关 社区 Apache APISIX

网易云音乐音视频算法的 Serverless 探索之路

阿里巴巴中间件

云计算 阿里云 Serverless 云原生 中间件

[2021年新鲜出炉]K8s工程师资料合辑,书籍推荐,面试题,精选文章,开源项目,PPT,视频,大厂资料

奔着腾讯去

golang Docker Kubernetes 容器 云原生

给JSONObject添加自定义遍历方法

FunTester

单元测试 Fastjson JSON库 spock FunTester

网络生病了怎么办?看华为云网络测量如何“悬丝诊脉”

华为云开发者联盟

华为云 云网络 网络故障 网络测量 SDN架构

企业级开发工具,J2PaaS低代码平台核心能力解析!

J2PaaS低代码平台

软件开发 低代码 低代码开发 低代码平台

堪称神级的Spring Boot手册,从基础入门到实战进阶

Java 程序员 Spring Boot

三轮融资笔笔过亿,来画如何实现弯道超车?

ToB行业头条

Linux指令日志分析(一)

正向成长

日志分析

以开发之名 | 美好出行体验,“管家”一站实现

最新动态

这一篇 K8S(Kubernetes)我觉得可以了解一下!!!

牧小农

Docker 容器 kubenetes

如何赋能APaaS平台应用管理员

明道云

英特尔全面升级开发者专区(Developer Zone),携手开发者共塑科技未来

科技新消息

2021年10月国产数据库流行度排行解读 浅谈基础软件发展之道

墨天轮

数据库 华为 opengauss Gauss DB 国产数据库

阿里二面:为什么要分库分表?

Java MySQL 数据库 架构 面试

Redis核心原理与实践--Redis启动过程源码分析

binecy

redis 源码阅读

iOS 崩溃日志在线符号化实践

百度Geek说

直面Z级计算挑战,英特尔携手生态合作伙伴加速开发者工具和软件部署

科技新消息

业内首款云原生技术中台产品云原生 Stack 来了!

阿里巴巴云原生

阿里云 云原生 技术中台

医药研发企业数据中台的选择

鲸品堂

产业互联网

阿里最新春招面经,腾讯/美团/字节1万道Java中高级面试题

收到请回复

Java 程序员 面试 职场 后端

华为云网络覆盖全球2500+站点,打造高品质、低成本接入体验

华为云开发者联盟

RTC 华为云 媒体服务 LiveVideoStack

Apache Arrow:一种适合异构大数据系统的内存列存数据格式标准_大数据_伴鱼技术团队_InfoQ精选文章