Apache Arrow官方文档-内存结构

发布时间：2020-06-03 01:13:55 作者：Lynn_Yuan
来源：网络阅读：1679

定义/术语

由于不同的项目使用不同的词语描述各种概念，所以这里有一个小小的术语表来帮助消除歧义。

数组：已知长度具有相同类型的值序列。
槽或数组槽：一些特定数据类型的数组中的单个逻辑值
连续的内存区域：给定长度的顺序虚拟地址空间。任何字节都可以通过小于区域长度的单个指针偏移量来取到。
连续的内存缓冲区：存储Array的多值组件的连续内存区域。有时称为“缓冲区”。
基本类型：占用固定大小的内存槽的数据类型，以位宽或字节宽度指定占用内存大小。
嵌套或参数类型：完整结构依赖于一个或多个其他子对象类型的数据类型。当且仅当子类型相等时，两个完全指定的嵌套类型相等。例如，如果U和V是不同的相对（简单）类型，List<U>与List<V> 也不同。
相对类型或简单类型（不合格）：特定的基本类型或完全指定的嵌套类型。当我们说槽时，我们是指相对类型值，不一定是任意物理存储区域。
逻辑类型：使用某些相对（物理）类型实现的数据类型。例如，存储在16个字节中的十进制值可以存储在一个大小为16槽的字节数组中。类似地，字符串可以存储为 List<1-byte>。
父和子数组：表示嵌套类型结构中物理值数组之间关系的名称。例如，List<T>类型：父类型的数组有一个T型数组作为它的子元素（参见下面的列表）。
叶子节点或叶子：一个原始值数组，可能是也可能不是具有嵌套类型的某些数组的子数组。
要求，目标和非目标

基本要求
一种物理内存布局，可在处理平面和嵌套列式数据的各种系统之间进行零反序列化的数据交换，包括Spark，Drill，Impala，Kudu，Ibis，Spark，ODBC协议和利用开源组件的专有系统。
所有数组槽都可以在不间断的时间内访问，复杂性在嵌套级别上呈线性增长
能够表示完全物化和解码/解压缩的Parquet 数据
所有连续的内存缓冲区以64字节边界对齐，并填充到64字节的倍数。
任何相对类型都可以有空槽
数组一旦创建就不可变。实现可以提供API来突变数组，但应用突变将需要构建新的数组数据结构。
数组可重定位（例如，用于RPC /瞬态存储），无需调整指针。另一种方法是连续的内存区域可以迁移到不同的地址空间（例如通过memcpy类型的操作），而不改变它们的内容。
目标（对于本文档）
描述相对类型，足够的明确的描述实现（物理值类型和一组初始嵌套类型）
每个相对类型的内存布局和随机访问模式
空值表示
非目标（对于本文档）
枚举或指定可以实现为基本（固定宽度）值类型的逻辑类型。例如：有符号和无符号整数，浮点数，布尔值，精确小数，日期和时间类型，CHAR（K），VARCHAR（K）等。
指定标准化元数据或RPC或临时文件存储的数据布局。
定义选择或屏蔽向量(vector)构造
实现具体细节
用户或开发人员C/C++/Java API的详细信息。
任何由表命名的数组组成的“表”结构，每一个都有自己的类型，或任何构成数组的其他结构。
任何内存管理或引用计数子系统
枚举或指定编码或压缩支持的类型
字节顺序（Endianness）

默认情况下，Arrow格式是低位编址的（将低序字节存储在起始地址）。模式元数据有一个指明RecordBatches的字节顺序的字段。通常这是生成RecordBatch的系统的字节顺序。主要用例是在具有相同字节码的系统之间交换RecordBatches。首先，当尝试读取与底层系统不匹配的字节顺序的模式时，将会返回错误。参考实现集中在地位编址，并为此提供测试。最终我们可以通过字节交换来提供自动转换。

对齐和填充

如上所述，所有缓冲区都旨在以64字节边界为准对齐内存，并且填充到64字节倍数的长度。对齐要求遵循优化内存访问的最佳做法：
数值数组中的元素将保证通过对齐的访问来读取。
在一些架构上，对齐可以帮助限制部分使用的缓存行。
64字节对齐由英特尔性能向导为超过64个字节的数据结构所推荐的（这将是Arrow格式数组的共同情况）。
要求填充64个字节的倍数允许在循环中一致地使用SIMD指令，无需额外的条件检查。这样就允许更简单和更有效的代码。
选择特定的填充长度是因为它与2016年4月可用的最大的已知SIMD指令寄存器匹配（Intel AVX-512）。保证填充也可以允许某些编译器直接生成更优化的代码（例如可以安全地使用英特尔 -qopt-assume-safe-padding）。
除非另有说明，填充字节不需要具有特定值。
数组长度

任何数组具有已知且固定长度，存储为32位有符号整数，因此最多可以存储(2^31 - 1)个元素。我们选择一个有符号的int32有一下2个原因：
增强与Java和客户端语言的兼容性，可能对无符号整数具有不同的支持质量。
为了鼓励开发人员组成较小的数组（每个数组在其叶节点中都包含连续的内存），以创建可能超过(2^31- 1)个元素的更大数组结构，而不是分配非常大的连续内存块。
空值计数

空值槽的数量是物理数组的属性，并被认为是数据结构的一部分。空值计数存储为32位有符号整数，因为它可能与数组长度一样大。

空值位图

任何相对类型都可以有空值槽，不管是原始类型还是嵌套类型。
具有空值的数组必须具有连续的内存缓冲区，称为空（或有效）位图，其长度为64字节的倍数（如上所述），并且足够大，以至于每个数组槽至少有1位。
任何数组槽是否有效（非空）是在该位图的各个位中编码的。索引（设置位）j值为1表示该值不为空，而0（位未设置）表示该值为空。位图被初始化为在分配时间全部未设置（这包括填充）。
is_valid[j] -> bitmap[j / 8] & (1 << (j % 8))
我们使用最低有效位（LSB）编号（也称为位编址bit-endianness）。这意味着在一组8个位中，我们从右到左读：
```
values = [0, 1, null, 2, null, 3]
```
```
bitmap
j mod 8   7  6  5  4  3  2  1  0
           0  0  1  0  1  0  1  1
```
具有0空值计数的数组可以选择不分配空值位图。实现为了方便可能会选择始终分配一个空值位图，但是在内存被共享时应该注意。
嵌套类型数组具有自己的空值位图和空值计数，而不管其子数组的空值和空位。

原始(基本)类型值数组

基本类型值数组表示固定长度的数组，每个值都具有通常用字节测量的相同的物理槽宽度，尽管规范还提供了位打包类型（例如以位编码的布尔值）。
在内部，数组包含一个连续的内存缓冲区，其总大小等于槽宽乘以数组长度。对于打包类型，大小将舍入到最接近的字节。
关联的空值位图被连续分配（如上所述），但不需要在内存中与值缓冲器相邻。

示例布局：Int32数组

例如int32的原始数组：
```
[1，2，null，4，8]
```

会像：

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

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

* Value Buffer:

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

示例布局：非空int32数组

[1，2，3，4，8]有两种可能的布局：

* Length: 5, Null count: 0
* Null 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
* Null 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 |

列表类型

列表是一种嵌套类型，其中每个数组槽都包含一个可变大小的值序列，它们都具有相同的相对类型（异质性可以通过联合实现，稍后描述）。
列表类型被指定为List<T>，这里的T是任何相对类型（原始或嵌套）。
列表数组由以下组合表示：

值数组，T类型的子数组，T也可以是嵌套类型。
一个包含长度等于顶级数组长度加1的32位有符号整数的偏移缓冲区。请注意，这将数组的大小限制为(2^31 -1)。
偏移数组对值数组中的起始位置进行编码，并且使用与偏移数组中的下一个元素的第一个差异来计算每个槽中的值的长度。例如。槽j的位置和长度计算为：
```
slot_position = offsets[j]
slot_length = offsets[j + 1] - offsets[j]  // (for 0 <= j < length)
```
偏移数组中的第一个值为0，最后一个元素是值数组的长度。

示例布局：List<Char>数组

我们来看一个例子，List<Char>类型：其中Char是一个1字节的逻辑类型。
对于具有相应值的长度为4的数组：
```
[['j'，'o'，'e']，null，['m'，'a'，'r'，'k']，[]]
```
将具有以下表示：

* Length: 4, Null count: 1
* Null 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 (char array):
  * Length: 7,  Null count: 0
  * Null bitmap buffer: Not required

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

示例布局： List<List<byte>>

[[[1,2]，[3，4]]，[[5，6，7]，null，[8]]，[[9，10]]]

将被表示如下：

* Length 3
* Nulls count: 0
* Null bitmap buffer: Not required
* Offsets buffer (int32)

  | Bytes 0-3  | Bytes 4-7  | Bytes 8-11 | Bytes 12-15 | Bytes 16-63 |
  |------------|------------|------------|-------------|-------------|
  | 0          |  2         |  5         |  6          | unspecified |

* Values array (`List<byte>`)
  * Length: 6, Null count: 1
  * Null bitmap buffer:

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

  * Offsets buffer (int32)

    | Bytes 0-27           | Bytes 28-63 |
    |----------------------|-------------|
    | 0, 2, 4, 7, 7, 8, 10 | unspecified |

  * Values array (bytes):
    * Length: 10, Null count: 0
    * Null bitmap buffer: Not required

      | Bytes 0-9                     | Bytes 10-63 |
      |-------------------------------|-------------|
      | 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 | unspecified |

结构体类型

一个struct是一个嵌套类型，它被一个有序序列的相对类型（可以都是不同的）参数化，相对类型称为它的字段。
通常，这些字段具有名称，但名称及其类型是元数据类型的一部分，而不是物理内存布局。
一个struct数组没有为它的值分配任何额外的物理存储。如果结构体数组有一个或多个空值，则它必须具有分配的空值位图。
在物理上，一个struct类型中每个字段都有一个子数组。
例如，struct（这里显示为字符串的字段名称用于说明）

Struct <
  name: String (= List<char>),
  age: Int32
>

有两个子数组，一个列表数组（如上所示）和一个具有Int32逻辑类型的4字节的基本类型数组。

示例布局Struct<List<char>, Int32>：

[{'joe'，1}，{null，2}，null，{'mark'，4}]的布局将是：

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

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

* Children arrays:
  * field-0 array (`List<char>`):
    * Length: 4, Null count: 2
    * Null bitmap buffer:

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

    * Offsets buffer:

      | Bytes 0-19     |
      |----------------|
      | 0, 3, 3, 3, 7  |

     * Values array:
        * Length: 7, Null count: 0
        * Null bitmap buffer: Not required

        * Value buffer:

          | Bytes 0-6      |
          |----------------|
          | joemark        |

  * field-1 array (int32 array):
    * Length: 4, Null count: 1
    * Null bitmap buffer:

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

    * Value Buffer:

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

虽然结构体没有为每个语义槽（即每个与C语言样结构体相似的标量）提供物理存储，但是可以通过空值位图将整个结构化槽设置为空。任何子字段数组可以根据各自的独立空值位图拥有空值。这意味着对于特定的结构体槽，结构体数组的空值位图可能表示一个空槽，当其一个或多个子数组在其相应的槽中具有非空值时。读取结构体数组时，父空值位图是权威的。这在上面的示例中说明，子数组具有空值结构体的有效实体，但是由父数组的空值位图“隐藏”。但是，独立处理时，子数组的对应值将不为空。

密集联合(共用体)类型

密集的联合在语义上类似于一个结构体，并且包含相对类型的有序序列。当一个结构体包含多个数组时，一个联合语义上是一个单个数组，其中每个槽可以有一个不同的类型。
联合类型可以被命名，但是像结构体一样，这将是元数据的问题，并且不会影响物理内存布局。
我们定义了针对不同用例优化的两种不同的联合类型。首先，密集联合，表示每个值为5字节开销的混合型数组。其物理布局如下：
每个相对类型一个子数组

类型缓冲区：8位有符号整数的缓冲区，从每个类型对应的0列举。具有多达127种可能类型的联合可以被模拟为多个联合中的一个联合。
偏移缓冲区：一个带符号int32值的缓冲区，指明给定槽中类型相应子数组的相对偏移量。每个子值数组的相应偏移必须按顺序/增加。
重要的是，密集的联合在普遍的结合体中，结合体在无重叠的字段的用例场景下（Union<s1: Struct1, s2: Struct2, s3: Struct3, ...>）允许最小开销。、

示例布局：密集联合

逻辑联合的示例布局： Union<f: float, i: int32>具有以下值：[{f = 1.2}，null，{f = 3.4}，{i = 5}]

* Length: 4, Null count: 1
* Null bitmap buffer:
  |Byte 0 (validity bitmap) | Bytes 1-63            |
  |-------------------------|-----------------------|
  |00001101                 | 0 (padding)           |

* Types buffer:

  |Byte 0   | Byte 1      | Byte 2   | Byte 3   | Bytes 4-63  |
  |---------|-------------|----------|----------|-------------|
  | 0       | unspecified | 0        | 1        | unspecified |

//存的是Union中的索引 f索引为0， i索引为1

* Offset buffer:

  |Byte 0-3 | Byte 4-7    | Byte 8-11 | Byte 12-15 | Bytes 16-63 |
  |---------|-------------|-----------|------------|-------------|
  | 0       | unspecified | 1         | 0          | unspecified |

* Children arrays:
  * Field-0 array (f: float):
    * Length: 2, nulls: 0
    * Null bitmap buffer: Not required

    * Value Buffer:

      | Bytes 0-7 | Bytes 8-63  |
      |-----------|-------------|
      | 1.2, 3.4  | unspecified |

  * Field-1 array (i: int32):
    * Length: 1, nulls: 0
    * Null bitmap buffer: Not required

    * Value Buffer:

      | Bytes 0-3 | Bytes 4-63  |
      |-----------|-------------|
      | 5         | unspecified |

稀疏联合类型

稀疏联合与密集联合具有相同的结构，省略了偏移数组。在这种情况下，子数组的长度与union的长度相等。
虽然与密集联合相比，稀疏联合可能使用明显更多的空间，但在某些确定的用例中可能拥有一些优点：

在一些用例中，稀疏联合更适合向量化表达式求值。
通过仅定义types数组，等长数组可以解释为联合。
示例布局： SparseUnion<u0: Int32, u1: Float, u2: List<Char>>

对于联合数组：
[{u0 = 5}，{u1 = 1.2}，{u2 ='joe'}，{u1 = 3.4}，{u0 = 4}，{u2 ='mark'}]
将具有以下布局：


* Length: 6, Null count: 0
* Null bitmap buffer: Not required

* Types buffer:

 | Byte 0     | Byte 1      | Byte 2      | Byte 3      | Byte 4      | Byte 5       | Bytes  6-63           |
 |------------|-------------|-------------|-------------|-------------|--------------|-----------------------|
 | 0          | 1           | 2           | 1           | 0           | 2            | unspecified (padding) |

* Children arrays:

  * u0 (Int32):
    * Length: 6, Null count: 4
    * Null bitmap buffer:

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

    * Value buffer:

      |Bytes 0-3   | Bytes 4-7   | Bytes 8-11  | Bytes 12-15 | Bytes 16-19 | Bytes 20-23  | Bytes 24-63           |
      |------------|-------------|-------------|-------------|-------------|--------------|-----------------------|
      | 5          | unspecified | unspecified | unspecified | 4           |  unspecified | unspecified (padding) |

  * u1 (float):
    * Length: 6, Null count: 4
    * Null bitmap buffer:

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

    * Value buffer:

      |Bytes 0-3    | Bytes 4-7   | Bytes 8-11  | Bytes 12-15 | Bytes 16-19 | Bytes 20-23  | Bytes 24-63           |
      |-------------|-------------|-------------|-------------|-------------|--------------|-----------------------|
      | unspecified |  1.2        | unspecified | 3.4         | unspecified |  unspecified | unspecified (padding) |

  * u2 (`List<char>`)
    * Length: 6, Null count: 4
    * Null bitmap buffer:

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

    * Offsets buffer (int32)

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

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

        | Bytes 0-7  | Bytes 8-63            |
        |------------|-----------------------|
        | joemark    | unspecified (padding) |

请注意，稀疏联合中的嵌套类型必须在内部一致（例如，见图中的列表），即任何子数组上任何索引j的随机访问都不会导致错误。换句话说，嵌套类型的数组如果被重新解释为非嵌套数组，则必须是有效的。
与结构类似，特定的子数组可能具有非空槽，即使父联合数组的空值位图表示槽为空。此外，即使类型数组指示槽在索引处包含不同类型，子数组也可能具有非空槽。

字典编码

当字段被字典编码时，这些值由表示字典中值的索引的Int32数组表示。字典被收录为DictionaryBatch，它的id由字段表中的元数据（Message.fbs）中定义的字典属性引用。字典具有与字段类型相同的布局。字典中的每个实体都可以通过其DictionaryBatch中的索引来访问。当Schema引用Dictionary id时，它必须在任何RecordBatch之前为此id发送DictionaryBatch。
例如，您可以获得以下数据：

type: List<String>

[
 ['a', 'b'],
 ['a', 'b'],
 ['a', 'b'],
 ['c', 'd', 'e'],
 ['c', 'd', 'e'],
 ['c', 'd', 'e'],
 ['c', 'd', 'e'],
 ['a', 'b']
]

在字典编码的形式中，这可能显示为：

data List<String> (dictionary-encoded, dictionary id i)
indices: [0, 0, 0, 1, 1, 1, 0]
//['a','b']为字典值，索引为0；['c', 'd', 'e']为字典值，索引为2

dictionary i

type: List<String>

[
 ['a', 'b'],
 ['c', 'd', 'e'],
]

Apache Arrow官方文档-内存结构

定义/术语

要求，目标和非目标

基本要求

目标（对于本文档）

非目标（对于本文档）

字节顺序（Endianness）

对齐和填充

数组长度

空值计数

空值位图

原始(基本)类型值数组

示例布局：Int32数组