`Apache Arrow`出现的背景

Apache Arrow出现以前的大数据分析系统基本都有各自不同的内存数据结构，带来一系列的重复工作

从计算引擎上看，算法必须基于项目特有的数据结构、API 与算法之间出现不必要的耦合
从数据获取上看，数据加载时必须反序列化，而每一种数据源都需要单独实现相应的加载器
从生态系统上看，跨项目、跨语言的合作无形之中被阻隔

数据库与数据分析的发展

企业对分析和使用数据的要求越来越复杂，对查询性能的标准也越来越高
内存变得便宜，支持基于内存分析的一套新的性能策略
CPU 和 GPU 的性能有所提高，但也已经发展到可以优化并行处理数据（单指令多数据指令/SIMD/Single Instruction Multiple Data）
针对不同的用例出现了新型数据库，每种都有自己的存储和索引数据的方式，mongo等文档数据库变得流行
新学科出现，包括数据工程和数据科学，都具有数十种新工具来实现特定的分析目标
列式数据表示成为分析工作负载的主流，在速度和效率方面具有显着优势

愿景与目标

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

减少或消除数据在不同系统间序列化、反序列化的成本
跨项目复用算法及IO工具
推动更广义的合作，让数据分析系统的开发者联合起来

项目构成部分

为分析查询引擎 (analytical query engines)、数据帧 (data frames) 设计的内存列存数据格式
用于 IPC/RPC的二进制协议
用于构建数据处理应用的开发平台

项目的基石

基于内存的列存数据格式(Arrow是面向数据分析开发的，所以采用列存)

特点包括

标准化 (standardized)，与语言无关 (language-independent)
同时支持平铺 (flat) 和层级 (hierarchical) 数据结构
硬件感知 (hardware-aware)

Apache Arrow 核心技术

`Arrow` 本身不是存储或执行引擎，旨在作为以下类型系统的共享基础

SQL 执行引擎，例如Drill/Impala
数据分析系统，例如 Pandas/Spark
流和队列系统，例如Kafka/Storm
存储系统，例如 Parquet/Kudu/Cassandra/HBase

`Arrow` 包含许多旨在集成到存储和执行引擎中的连接技术，关键组件包括

定义的数据类型集包括 SQL 和 JSON 类型，例如 int、BigInt、decimal、varchar、map、struct 和 array
DataSet 是数据的列式内存表示，以支持构建在已定义数据类型之上的任意复杂记录结构
常见数据结构 Arrow感知伴随数据结构，包括选择列表、哈希表和队列
在共享内存、TCP/IP 和 RDMA(Remote Direct Memory Access/远程直接数据存取) 中实现的进程间通信
用于以多种语言读写列式数据的数据库，包括 Java、C++、Python、Ruby、Rust、Go 和 JavaScript
用于各种操作的流水线和 SIMD 算法，包括位图选择、散列、过滤、分桶、排序和匹配
列内存压缩包括一系列提高内存效率的技术
内存持久性工具，用于通过非易失性内存、SSD 或 HDD 进行短期持久化

确保处理技术有效地使用 `CPU`，专门设计用于最大化

缓存局部性：内存缓冲区是为现代 CPU 设计的数据的紧凑表示，这些结构是线性定义的，与典型的读取模式相匹配，这意味着相似类型的数据在内存中位于同一位置，这使得缓存预取更有效，最大限度地减少了缓存未命中和主内存访问导致的 CPU 停顿，这些 CPU 高效的数据结构和访问模式扩展到传统的平面关系结构和现代复杂数据结构
流水线：执行模式旨在利用现代处理器的超标量和流水线特性，通过最小化循环内指令数和循环复杂性来实现，这些紧密的循环导致更好的性能和更少的分支预测失败
向量化处理/SIMD 指令：单指令多数据 (SIMD Single Instruction Multiple Data) 指令允许执行算法通过在单个时钟周期内执行多个操作来更有效地运行，Arrow 组织数据以使其非常适合 SIMD 操作

内存效率

Arrow 设计为即使数据不能完全放入内存也能正常工作，核心数据结构包括数据向量和这些向量的集合（也称为记录批次）

记录批次通常为 64KB-1MB，具体取决于工作负载，并且通常限制为 2^16 条记录，不仅提高了缓存的局部性，而且即使在低内存情况下也可以进行内存计算

对于从数百到数千台服务器不等的许多大数据集群，系统必须能够利用集群的聚合内存

Arrow 旨在最大限度地降低在网络上移动数据的成本，利用分散/聚集读取和写入，并具有零序列化/反序列化设计，允许节点之间的低成本数据移动

直接与支持 RDMA 的互连一起工作，为更大的内存工作负载提供单一内存网格

`Arrow`与`Apache Parquet/Apache ORC`的关系

数据存储的两个角度

存储格式：行存 (row-wise/row-based)、列存 (column-wise/column-based/columnar)
主要存储器：面向磁盘 (disk-oriented)、面向内存 (memory-oriented)

Parquet/ORC同样是采用列存，但是都是面向磁盘设计的，Arrow面向内存设计

数据存储格式的设计决定在不同瓶颈下的目的不同

最典型的就是压缩

Parquet/ORC: 对于 disk-oriented 场景，更高的压缩率几乎总是个好主意，利用计算资源换取空间可以利用更多的 CPU 资源，减轻磁盘 IO 的压力，支持高压缩率的压缩算法，如 snappy, gzip, zlib 等压缩技术就十分必要
Arrow: 对于 memory-oriented 场景，压缩只会让 CPU 更加不堪重负，所以更倾向于直接存储原生的二进制数据

尽管磁盘和内存的顺序访问效率都要高于随机访问，但在磁盘中，这个差异在 2-3 个数量级，而在内存中通常在 1 个数量级内。因此要均摊一次随机访问的成本，需要在磁盘中连续读取上千条数据，而在内存中仅需要连续读取十条左右的数据

数据列内存设计

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

更详细的内存布局请参考Apache Arrow文档Arrow Columnar Format

https://arrow.apache.org/docs/format/Columnar.html

https://arrow.apache.org/docs/format/Columnar.html

`Fixed-width data types`/定长数据列格式

比如对于int32数据，有一段数据[1, null, 2, 4, 8]，采用数据列格式定义如下

* Length: 5, Null count: 1
* Validity bitmap buffer:

  |Byte 0 (validity bitmap) | Bytes 1-63            |
  |-------------------------|-----------------------|
  | 00011101                | 0 (padding)           |

* Value Buffer:

  |Bytes 0-3   | Bytes 4-7   | Bytes 8-11  | Bytes 12-15 | Bytes 16-19 | Bytes 20-63 |
  |------------|-------------|-------------|-------------|-------------|-------------|
  | 1          | unspecified | 2           | 4           | 8           | unspecified |

* Length: 5, Null count: 1
* Validity bitmap buffer:

  |Byte 0 (validity bitmap) | Bytes 1-63            |
  |-------------------------|-----------------------|
  | 00011101                | 0 (padding)           |

* Value Buffer:

  |Bytes 0-3   | Bytes 4-7   | Bytes 8-11  | Bytes 12-15 | Bytes 16-19 | Bytes 20-63 |
  |------------|-------------|-------------|-------------|-------------|-------------|
  | 1          | unspecified | 2           | 4           | 8           | unspecified |

可以看到共包含四个字段

Length：数组长度
Null count: null值统计
Validity bitmap buffer：有效位bitmap，0表示null，采用64字节，采用 little-endian 存储字节数据，由于只有第二个数据是空，所以按照从右往左定义，定长为8，所以bitmap的值就变为了00011101
Value Buffer
- 由于采用int32类型，所以每个值占据4个字节
- 无论数组中的某个元素是否是 null，在定长数据格式中 Arrow 都会让该元素占据规定长度的空间，在随机访问时需要先利用 nullBitmap 计算出位移，这样需要的内存带宽更小，性能更优，主要体现的是存储空间与随机访问性能的权衡

如果是采用非null int32 array，则内存布局会有两种可能

比如对于int32 array: [1, 2, 3, 4, 8]

仍然带有bitmap

* Length: 5, Null count: 0
* Validity bitmap buffer:

  | Byte 0 (validity bitmap) | Bytes 1-63            |
  |--------------------------|-----------------------|
  | 00011111                 | 0 (padding)           |

* Value Buffer:

  |Bytes 0-3   | Bytes 4-7   | Bytes 8-11  | bytes 12-15 | bytes 16-19 | Bytes 20-63 |
  |------------|-------------|-------------|-------------|-------------|-------------|
  | 1          | 2           | 3           | 4           | 8           | unspecified |

* Length: 5, Null count: 0
* Validity bitmap buffer:

  | Byte 0 (validity bitmap) | Bytes 1-63            |
  |--------------------------|-----------------------|
  | 00011111                 | 0 (padding)           |

* Value Buffer:

  |Bytes 0-3   | Bytes 4-7   | Bytes 8-11  | bytes 12-15 | bytes 16-19 | Bytes 20-63 |
  |------------|-------------|-------------|-------------|-------------|-------------|
  | 1          | 2           | 3           | 4           | 8           | unspecified |

bitmap被省略优化

* Length 5, Null count: 0
* Validity bitmap buffer: Not required
* Value Buffer:

  |Bytes 0-3   | Bytes 4-7   | Bytes 8-11  | bytes 12-15 | bytes 16-19 | Bytes 20-63 |
  |------------|-------------|-------------|-------------|-------------|-------------|
  | 1          | 2           | 3           | 4           | 8           | unspecified |

* Length 5, Null count: 0
* Validity bitmap buffer: Not required
* Value Buffer:

  |Bytes 0-3   | Bytes 4-7   | Bytes 8-11  | bytes 12-15 | bytes 16-19 | Bytes 20-63 |
  |------------|-------------|-------------|-------------|-------------|-------------|
  | 1          | 2           | 3           | 4           | 8           | unspecified |

`Variable-size Binary Layout`/变长数据内存布局

在该类型下，每个元素都会占据0到多个字节，所以就需要多一个offset buffer区域来存储偏移信息

比如对于数据['joe', null, null, 'mark']，内存布局表示为如下

* Length: 4, Null count: 2
* Validity bitmap buffer:

  | Byte 0 (validity bitmap) | Bytes 1-63            |
  |--------------------------|-----------------------|
  | 00001001                 | 0 (padding)           |

* Offsets buffer:

  | Bytes 0-19     | Bytes 20-63           |
  |----------------|-----------------------|
  | 0, 3, 3, 3, 7  | unspecified           |

 * Value buffer:

  | Bytes 0-6      | Bytes 7-63           |
  |----------------|----------------------|
  | joemark        | unspecified          |

* Length: 4, Null count: 2
* Validity bitmap buffer:

  | Byte 0 (validity bitmap) | Bytes 1-63            |
  |--------------------------|-----------------------|
  | 00001001                 | 0 (padding)           |

* Offsets buffer:

  | Bytes 0-19     | Bytes 20-63           |
  |----------------|-----------------------|
  | 0, 3, 3, 3, 7  | unspecified           |

 * Value buffer:

  | Bytes 0-6      | Bytes 7-63           |
  |----------------|----------------------|
  | joemark        | unspecified          |

字段解释

Length: 数据长度为4
Null count: null统计数是2
Validity bitmap buffer: 采用little-endian 存储字节数据，数组中间两个是null，所以该值是00001001，从右往左看
Offsets buffer：由于每个字符都占据一个字节的长度，null不会增加偏移，值从0开始，所以遇到joe，会+3,遇到null会+0,遇到mark会+4,最后值变成[0, 3, 3, 3, 7]
Value buffer：不给null分配内存，把所有占用内存的值合并，变为joemark

`Variable-size List Layout`/可变长度列表布局

列表是一种嵌套类型，其语义类似于可变大小的类型，它由两个缓冲区、一个validity bitmap和一个 offsets buffer以及一个子数组定义。偏移量与可变大小类型的偏移量相同，并且 32 位和 64 位有符号整数偏移量都是支持的偏移量选项。这些偏移量不是引用额外的数据缓冲区，而是引用子数组

比如对于数据List<List<Int8>>: [[12, -7, 25], null, [0, -127, 127, 50], []]

表示的内存布局如下

* Length: 4, Null count: 1
* Validity bitmap buffer:

  | Byte 0 (validity bitmap) | Bytes 1-63            |
  |--------------------------|-----------------------|
  | 00001101                 | 0 (padding)           |

* Offsets buffer (int32)

  | Bytes 0-3  | Bytes 4-7   | Bytes 8-11  | Bytes 12-15 | Bytes 16-19 | Bytes 20-63 |
  |------------|-------------|-------------|-------------|-------------|-------------|
  | 0          | 3           | 3           | 7           | 7           | unspecified |

* Values array (Int8array):
  * Length: 7,  Null count: 0
  * Validity bitmap buffer: Not required
  * Values buffer (int8)

    | Bytes 0-6                    | Bytes 7-63  |
    |------------------------------|-------------|
    | 12, -7, 25, 0, -127, 127, 50 | unspecified |

* Length: 4, Null count: 1
* Validity bitmap buffer:

  | Byte 0 (validity bitmap) | Bytes 1-63            |
  |--------------------------|-----------------------|
  | 00001101                 | 0 (padding)           |

* Offsets buffer (int32)

  | Bytes 0-3  | Bytes 4-7   | Bytes 8-11  | Bytes 12-15 | Bytes 16-19 | Bytes 20-63 |
  |------------|-------------|-------------|-------------|-------------|-------------|
  | 0          | 3           | 3           | 7           | 7           | unspecified |

* Values array (Int8array):
  * Length: 7,  Null count: 0
  * Validity bitmap buffer: Not required
  * Values buffer (int8)

    | Bytes 0-6                    | Bytes 7-63  |
    |------------------------------|-------------|
    | 12, -7, 25, 0, -127, 127, 50 | unspecified |

字段解释

Validity bitmap buffer: 由于第二个参数是null，所以该参数的值是00001101，从右往左看
Offsets buffer: 每个List<Int8>中的Int8占据一个偏移值，null和[]不增加偏移量，偏移量从0开始计算
Values array: 把二维数组展平，排除了null值到影响，所以值展平开就变为[12, -7, 25, 0, -127, 127, 50]

参考阅读

Arrow Columnar Format

Apache Arrow-知乎

Databend 内幕大揭秘第二弹 - Data Source

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

循环优化之向量化并行（vectorization）

Apache Arrow出现的背景 ​

愿景与目标 ​

项目构成部分 ​

项目的基石 ​

Apache Arrow 核心技术 ​

Arrow 本身不是存储或执行引擎，旨在作为以下类型系统的共享基础 ​

Arrow 包含许多旨在集成到存储和执行引擎中的连接技术，关键组件包括 ​

确保处理技术有效地使用 CPU，专门设计用于最大化 ​

内存效率 ​

Arrow与Apache Parquet/Apache ORC的关系 ​

数据列内存设计 ​

Fixed-width data types/定长数据列格式 ​

Variable-size Binary Layout/变长数据内存布局 ​

Variable-size List Layout/可变长度列表布局 ​

参考阅读 ​