作者 | 伴魚技術(shù)團(tuán)隊(duì) 策劃 | 鈺瑩

本文介紹一種內(nèi)存列存數(shù)據(jù)格式：Apache Arrow，它有一個(gè)非常大的愿景：提供內(nèi)存數(shù)據(jù)分析 (in-memory analytics) 的開發(fā)平臺，讓數(shù)據(jù)在異構(gòu)大數(shù)據(jù)系統(tǒng)間移動(dòng)、處理地更快。同時(shí)，比較特別的是這個(gè)項(xiàng)目的啟動(dòng)形式與其他項(xiàng)目也不相同，Arrow 項(xiàng)目的草臺班子由 5 個(gè) Apache Members、6 個(gè) PMC Chairs 和一些其它項(xiàng)目的 PMC 及 committer 構(gòu)成，他們直接找到 ASF 董事會(huì)，征得同意后直接以頂級 Apache 項(xiàng)目身份啟動(dòng)。

本文從以下幾個(gè)方面來介紹 Arrow 項(xiàng)目：

• Arrow 項(xiàng)目的來源

• Arrow 如何表示定長、變長和嵌套數(shù)據(jù)

• 內(nèi)存列存數(shù)據(jù)格式與磁盤列存數(shù)據(jù)格式的設(shè)計(jì)取舍

注：Arrow 即可以指內(nèi)存列存數(shù)據(jù)格式，也可以指 Apache Arrow 項(xiàng)目整體，因此下文中將用 「Arrow」 表示格式本身，「Arrow 項(xiàng)目」表示整體項(xiàng)目。

Arrow 項(xiàng)目簡介

現(xiàn)存的大數(shù)據(jù)分析系統(tǒng)基本都基于各自不同的內(nèi)存數(shù)據(jù)結(jié)構(gòu)，這就會(huì)帶來一系列的重復(fù)工作：從計(jì)算引擎上看，算法必須基于項(xiàng)目特有的數(shù)據(jù)結(jié)構(gòu)、API 與算法之間出現(xiàn)不必要的耦合；從數(shù)據(jù)獲取上看，數(shù)據(jù)加載時(shí)必須反序列化，而每一種數(shù)據(jù)源都需要單獨(dú)實(shí)現(xiàn)相應(yīng)的加載器；從生態(tài)系統(tǒng)上看，跨項(xiàng)目、跨語言的合作無形之中被阻隔。能否減少或消除數(shù)據(jù)在不同系統(tǒng)間序列化、反序列化的成本？能否跨項(xiàng)目復(fù)用算法及 IO 工具？能否推動(dòng)更廣義的合作，讓數(shù)據(jù)分析系統(tǒng)的開發(fā)者聯(lián)合起來？在這樣的使命驅(qū)動(dòng)下，Arrow 就誕生了。

與其它項(xiàng)目不同，Arrow 項(xiàng)目的草臺班子由 5 個(gè) Apache Members、6 個(gè) PMC Chairs 和一些其它項(xiàng)目的 PMC 及 committer 構(gòu)成，他們直接找到 ASF 董事會(huì)，征得同意后直接以頂級 Apache 項(xiàng)目身份啟動(dòng)。想了解項(xiàng)目的詳細(xì)歷史可以閱讀項(xiàng)目 Chair，Jacques Nadeau 寫的這篇博客。另外，這張 google sheet 記錄著項(xiàng)目的取名過程，取名為 Arrow 的原因是：”math symbol for vector. and arrows are fast. also alphabetically will show up on top.” 可以說考慮得相當(dāng)全面 。

Arrow 項(xiàng)目的愿景是提供內(nèi)存數(shù)據(jù)分析 (in-memory analytics) 的開發(fā)平臺，讓數(shù)據(jù)在異構(gòu)大數(shù)據(jù)系統(tǒng)間移動(dòng)、處理地更快：

項(xiàng)目主要由 3 部分構(gòu)成：

• 為分析查詢引擎 (analytical query engines)、數(shù)據(jù)幀 (data frames) 設(shè)計(jì)的內(nèi)存列存數(shù)據(jù)格式

• 用于 IPC/RPC 的二進(jìn)制協(xié)議

• 用于構(gòu)建數(shù)據(jù)處理應(yīng)用的開發(fā)平臺

整個(gè)項(xiàng)目的基石是基于內(nèi)存的列存數(shù)據(jù)格式，現(xiàn)在將它的特點(diǎn)羅列如下：

• 標(biāo)準(zhǔn)化 (standardized)，與語言無關(guān) (language-independent)

• 同時(shí)支持平鋪 (flat) 和層級 (hierarchical) 數(shù)據(jù)結(jié)構(gòu)

• 硬件感知 (hardware-aware)

基于內(nèi)存的列存格式

詳細(xì)、準(zhǔn)確的格式定義請閱讀官方文檔，本節(jié)內(nèi)容參考了官方文檔及 Daniel Abadi 的這篇博客。

在實(shí)踐中，工程師通常會(huì)將系統(tǒng)中的數(shù)據(jù)通過多個(gè)二維數(shù)據(jù)表建模，每張數(shù)據(jù)表的一行表示一個(gè)實(shí)體 (entity)，一列表示同一屬性。然而，在硬件中存儲器通常是一維的，即計(jì)算機(jī)程序只能線性地、沿同一方向地從內(nèi)存或硬盤中讀取數(shù)據(jù)，因此存儲二維數(shù)據(jù)表就有兩種典型方案：行存和列存。通常前者適用于 OLTP 場景，后者適用于 OLAP 場景，Arrow 是面向數(shù)據(jù)分析開發(fā)的，因此采用后者。

任何一張數(shù)據(jù)表都可能由不類型的數(shù)據(jù)列構(gòu)成。以某張用戶表為例，表中可能包含如年齡 (integer)、姓名 (varchar)、出生日期 (date) 等屬性。Arrow 將數(shù)據(jù)表中所有可能的列數(shù)據(jù)分成兩類，定長和變長，并基于定長和變長數(shù)據(jù)類型構(gòu)建出更復(fù)雜的嵌套數(shù)據(jù)類型。

Fixed-width data types

定長的數(shù)據(jù)列格式如下所示：

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

除了數(shù)據(jù)數(shù)組 (data) 外，還包含：

• 數(shù)組長度 (length)

• null 元素的個(gè)數(shù) (nullCount)

• null 位圖 (nullBitmap)

以 Int32 數(shù)組：[1, null, 2, 4, 8] 為例，它的結(jié)構(gòu)如下：

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 |

這里有一個(gè)值得關(guān)注的設(shè)計(jì)決定，無論數(shù)組中的某個(gè)元素 (cell) 是否是 null，在定長數(shù)據(jù)格式中 Arrow 都會(huì)讓該元素占據(jù)規(guī)定長度的空間；另一種備選方案就是不給 null 元素分配任何空間。前者可以利用指針代數(shù)支持 O(1) 的隨機(jī)訪問，后者在隨機(jī)訪問時(shí)需要先利用 nullBitmap 計(jì)算出位移。如果是順序訪問，后者需要的內(nèi)存帶寬更小，性能更優(yōu)，因此這里主要體現(xiàn)的是存儲空間與隨機(jī)訪問性能的權(quán)衡，Arrow 選擇傾向是后者。

從 nullBitmap 的結(jié)構(gòu)可以看出，Arrow 采用 little-endian 存儲字節(jié)數(shù)據(jù)。

Variable-width data types

變長的數(shù)據(jù)列格式如下所示：

type VarColumn struct {
  data       []byte
  offsets    []int64
  length     int
  nullCount  int
  nullBitmap []byte // bit 0 is null, 1 is not null
}

可以看出，比定長列僅多存一個(gè)偏移量數(shù)組 (offsets)。offsets 的第一個(gè)元素固定為 0，最后一個(gè)元素為數(shù)據(jù)的長度，即與 length 相等，那么關(guān)于第 i 個(gè)變長元素：

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

另一種備選方案是在 data 中利用特殊的字符分隔不同元素，在個(gè)別查詢場景下，后者能取得更優(yōu)的性能。如掃描字符串列中包含某兩個(gè)連續(xù)字母的所有列：利用 Arrow 的格式需要頻繁地訪問 offsets 來遍歷 data，但利用特殊分隔符的解決方案直接遍歷一次 data 即可。而在其它場景下，如查詢某字符串列中值和 “hello world” 相等的字符串，這時(shí)利用 offsets 能過濾掉所有長度不為 11 的列，因此利用 Arrow 的格式能獲取更優(yōu)的性能。

Nested Data

數(shù)據(jù)處理過程中，一些復(fù)雜數(shù)據(jù)類型如 JSON、struct、union 都很受開發(fā)者歡迎，我們可以將這些數(shù)據(jù)類型歸類為嵌套數(shù)據(jù)類型。Arrow 處理嵌套數(shù)據(jù)類型的方式很優(yōu)雅，并未引入定長和變長數(shù)據(jù)列之外的概念，而是直接利用二者來構(gòu)建。假設(shè)以一所大學(xué)的班級 (Class) 信息數(shù)據(jù)列為例，該列中有以下兩條數(shù)據(jù)：

// 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

我們可以將改嵌套數(shù)據(jù)結(jié)構(gòu)分成 4 列：Name、Instructor、Students 以及 Year，其中 Name 和 Instructor 是變長字符串列，Year 是定長整數(shù)列，Students 是字符串?dāng)?shù)組列 (二維數(shù)組)，它們的存儲結(jié)構(gòu)分別如下所示：

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 列本身就是嵌套數(shù)據(jù)結(jié)構(gòu)，而外層的 Class 表包含了 Students 列，可以看出這種巧思能支持無限嵌套，是很值得稱贊的設(shè)計(jì)。

Buffer alignment and padding

Arrow 列存格式的所有實(shí)現(xiàn)都需要考慮數(shù)據(jù)內(nèi)存地址的對齊 (alignment) 以及填充 (padding)，通常推薦將地址按 8 或 64 字節(jié)對齊，若不足 8 或 64 字節(jié)的整數(shù)倍則按需補(bǔ)全。這主要是為了利用現(xiàn)代 CPU 的 SIMD 指令，將計(jì)算向量化。

Memory-oriented columnar format

計(jì)算機(jī)發(fā)展的幾十年來，絕大多數(shù)數(shù)據(jù)引擎都采用行存格式，主要原因在于早期的數(shù)據(jù)應(yīng)用負(fù)載模式基本都逃不出單個(gè)實(shí)體的增刪改查。面對此類負(fù)載，如果采用列存格式存儲數(shù)據(jù)，讀取一個(gè)實(shí)體數(shù)據(jù)就需要在存儲器上來回跳躍，找到該實(shí)體的不同屬性，本質(zhì)上是在執(zhí)行隨機(jī)訪問。但隨著時(shí)間的推移，數(shù)據(jù)的增多，負(fù)載變得更加復(fù)雜，數(shù)據(jù)分析的負(fù)載模式逐漸顯露，即每次訪問一組實(shí)體的少數(shù)幾個(gè)屬性，然后聚合出分析結(jié)果，這時(shí)候列存格式的地位便逐漸提高。

在 Hadoop 生態(tài)中，Apache Parquet 和 Apache ORC 已經(jīng)成為最流行的兩種文件存儲格式，它們核心價(jià)值也是圍繞著列存數(shù)據(jù)格式建立，那么我們?yōu)槭裁催€需要 Arrow？這里我們可以從兩個(gè)角度來看待數(shù)據(jù)存儲：

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

• 主要存儲器：面向磁盤 (disk-oriented)、面向內(nèi)存 (memory-oriented)

盡管三者都采用列存格式，但 Parquet 和 ORC 是面向磁盤設(shè)計(jì)，而 Arrow 是面向內(nèi)存設(shè)計(jì)。為了理解面向磁盤設(shè)計(jì)與面向內(nèi)存設(shè)計(jì)的區(qū)別，我們來看 Daniel Abadi 做的一個(gè)實(shí)驗(yàn)。

Daniel Abadi 的實(shí)驗(yàn)

在一臺 Amazon EC2 的 t2.medium 實(shí)例上，創(chuàng)建一張包含 60,000,000 行數(shù)據(jù)的表，每行包含 6 個(gè)屬性，每個(gè)屬性值都是 int32 類型的數(shù)據(jù)，因此每行需要 24 字節(jié)空間，整張表占用約 1.5GB 空間。我們將這張表分別用行存格式和列存格式保存一份，然后執(zhí)行一個(gè)簡單的查詢：在第一列中查找與特定值相等的數(shù)據(jù)，即：

SELECT a FROM t WHERE t.a = 477638700;

不論是行存還是列存版本，CPU 的工作都是獲取整數(shù)與目標(biāo)整數(shù)進(jìn)行比較。但在行存版本中執(zhí)行該查詢需要掃描每行，即全部 1.5GB 數(shù)據(jù)，而在列存版本中執(zhí)行該查詢只需掃描第一列，即 0.25GB 數(shù)據(jù)，因此后者的執(zhí)行效率理論上應(yīng)該是前者的 6 倍。然而，實(shí)際的結(jié)果如下所示：

列存版本與行存版本的性能竟然相差無幾！原因在于實(shí)驗(yàn)執(zhí)行時(shí)關(guān)閉了所有 CPU 優(yōu)化 (vectorization/SIMD processing)，使得該查詢的瓶頸出現(xiàn)在 CPU 處理上。我們來一起分析一下其中的原因：根據(jù)經(jīng)驗(yàn)，從內(nèi)存掃描數(shù)據(jù)到 CPU 中的吞吐能達(dá)到 30GB/s，現(xiàn)代 CPU 的處理頻率能達(dá)到 3GHz，即每秒 30 億 CPU 指令，因此即便處理器可以在一個(gè) CPU 周期執(zhí)行 32 位整數(shù)比較，它的吞吐最多為 12 GB/s，遠(yuǎn)遠(yuǎn)小于內(nèi)存輸送數(shù)據(jù)的吞吐。因此不論是行存還是列存，從內(nèi)存中輸送 0.25GB 還是 1.5GB 數(shù)據(jù)到 CPU 中，都不會(huì)對結(jié)果有大的影響。

如果打開 CPU 優(yōu)化選項(xiàng)，情況就大不相同。對于列存數(shù)據(jù)，只要這些整數(shù)在內(nèi)存中連續(xù)存放，編譯器可以將簡單的操作向量化，如 32 位整數(shù)的比較。通常，向量化后處理器在單條指令中能夠同時(shí)將 4 個(gè) 32 位整數(shù)與指定值比較。優(yōu)化后再執(zhí)行相同的查詢，實(shí)驗(yàn)的結(jié)果如下圖所示：

可以看到與預(yù)期相符的 4 倍差異。不過值得注意的是，此時(shí) CPU 仍然是瓶頸。如果內(nèi)存帶寬是瓶頸的話，我們將能夠看到列存版本與行存版本的性能差異達(dá)到 6 倍。

從以上實(shí)驗(yàn)可以看出，針對少量屬性的順序掃描查詢的工作負(fù)載，列存格式要優(yōu)于行存格式，這與數(shù)據(jù)是在磁盤上還是內(nèi)存中無關(guān)，但它們優(yōu)于行存格式的理由不同。如果以磁盤為主要存儲，CPU 的處理速度要遠(yuǎn)遠(yuǎn)高于數(shù)據(jù)從磁盤移動(dòng)到 CPU 的速度，列存格式的優(yōu)勢在于能通過更適合的壓縮算法減少磁盤 IO；如果以內(nèi)存為主要存儲，數(shù)據(jù)移動(dòng)速度的影響將變得微不足道，此時(shí)列存格式的優(yōu)勢在于它能夠更好地利用向量化處理。

這個(gè)實(shí)驗(yàn)告訴我們：數(shù)據(jù)存儲格式的設(shè)計(jì)決定在不同瓶頸下的目的不同。最典型的就是壓縮，對于 disk-oriented 場景，更高的壓縮率幾乎總是個(gè)好主意，利用計(jì)算資源換取空間可以利用更多的 CPU 資源，減輕磁盤 IO 的壓力；對于 memory-oriented 場景，壓縮只會(huì)讓 CPU 更加不堪重負(fù)。

Apache Parquet/ORC vs. Apache Arrow

現(xiàn)在要對比 Parquet/ORC 與 Arrow 就變得容易一些。因?yàn)?Parquet 和 ORC 是為磁盤而設(shè)計(jì)，支持高壓縮率的壓縮算法，如 snappy、gzip、zlib 等壓縮技術(shù)就十分必要。而 Arrow 為內(nèi)存而設(shè)計(jì)，對壓縮算法幾乎沒有要求，更傾向于直接存儲原生的二進(jìn)制數(shù)據(jù)。面向磁盤與面向內(nèi)存的另一個(gè)不同點(diǎn)在于：盡管磁盤和內(nèi)存的順序訪問效率都要高于隨機(jī)訪問，但在磁盤中，這個(gè)差異在 2-3 個(gè)數(shù)量級，而在內(nèi)存中通常在 1 個(gè)數(shù)量級內(nèi)。因此要均攤一次隨機(jī)訪問的成本，需要在磁盤中連續(xù)讀取上千條數(shù)據(jù)，而在內(nèi)存中僅需要連續(xù)讀取十條左右的數(shù)據(jù)。這種差異意味著 內(nèi)存場景下的 batch 大小 (如 Arrow 的 64KB) 要小于磁盤場景下的 batch 大小。

參考:

DBMS Musings: Apache Arrow vs. Parquet and ORC: Do we really need a third Apache project for columnar data representation?

DBMS Musings: An analysis of the strengths and weaknesses of Apache Arrow

Dremio blog: The Origin & History of Apache Arrow

ACM: Apache Arrow and the Future of Data Frames, slides

Apache Arrow: official docs, committers

---

你也「在看」嗎？?

總結(jié)

以上是生活随笔為你收集整理的byte数组穿换成pcm格式_Apache Arrow：一种适合异构大数据系统的内存列存数据格式标准...的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。