ApacheArrow官方文檔-內存結構-創新互聯

定義/術語

由于不同的項目使用不同的詞語描述各種概念，所以這里有一個小小的術語表來幫助消除歧義。

成都創新互聯專業為企業提供昌江網站建設、昌江做網站、昌江網站設計、昌江網站制作等企業網站建設、網頁設計與制作、昌江企業網站模板建站服務，十載昌江做網站經驗，不只是建網站，更提供有價值的思路和整體網絡服務。

數組：已知長度具有相同類型的值序列。
槽或數組槽：一些特定數據類型的數組中的單個邏輯值
連續的內存區域：給定長度的順序虛擬地址空間。任何字節都可以通過小于區域長度的單個指針偏移量來取到。
連續的內存緩沖區：存儲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'],
]

另外有需要云服務器可以了解下創新互聯scvps.cn，海內外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業上云的綜合解決方案，具有“安全穩定、簡單易用、服務可用性高、性價比高”等特點與優勢，專為企業上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。

標題名稱：ApacheArrow官方文檔-內存結構-創新互聯
文章來源：http://vcdvsql.cn/article44/deodhe.html

成都網站建設公司_創新互聯，為您提供微信公眾號、移動網站建設、全網營銷推廣、網站內鏈、企業建站、微信小程序

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源：創新互聯

猜你還喜歡下面的內容

bl双性强迫侵犯h_国产在线观看人成激情视频_蜜芽188_被诱拐的少孩全彩啪啪漫画

ApacheArrow官方文檔-內存結構-創新互聯

定義/術語

要求，目標和非目標

基本要求

目標（對于本文檔）

非目標（對于本文檔）

字節順序（Endianness）

對齊和填充

數組長度

空值計數

空值位圖

原始(基本)類型值數組

示例布局：Int32數組