轉(zhuǎn)載：https://mp.weixin.qq.com/s/I2WqQoGwK7LRrpB4R2pobw

很值得學(xué)習(xí)的一篇文章，不適用于初學(xué)者，適用于中級(jí)或者進(jìn)階高級(jí)的大數(shù)據(jù)工程師

?

OLAP 系統(tǒng)廣泛應(yīng)用于 BI, Reporting, Ad-hoc, ETL 數(shù)倉(cāng)分析等場(chǎng)景，本文主要從體系化的角度來(lái)分析 OLAP 系統(tǒng)的核心技術(shù)點(diǎn)，從業(yè)界已有的 OLAP 中萃取其共性，分為談存儲(chǔ)，談?dòng)?jì)算，談優(yōu)化器，談趨勢(shì)?4 個(gè)章節(jié)。

01

談儲(chǔ)存??

?

?

列存的數(shù)據(jù)組織形式

行存，可以看做 NSM (N-ary Storage Model) 組織形式，一直伴隨著關(guān)系型數(shù)據(jù)庫(kù)，對(duì)于 OLTP 場(chǎng)景友好，例如 innodb[1] 的 B+ 樹聚簇索引，每個(gè) Page 中包含若干排序好的行，可以很好的支持 tuple-at-a-time 式的點(diǎn)查以及更新等；而列存 (Column-oriented Storage)，經(jīng)歷了早期的 DSM (Decomposition Storage Model) [2]，以及后來(lái)提出的 PAX (Partition Attributes Cross) 嘗試混合 NSM 和 DSM，在 C-Store 論文 [3] 后逐漸被人熟知，用于 OLAP，分析型不同于交易場(chǎng)景，存儲(chǔ) IO 往往是瓶頸，而列存可以只讀取需要的列，跳過(guò)無(wú)用數(shù)據(jù)，避免 IO 放大，同質(zhì)數(shù)據(jù)存儲(chǔ)更緊湊，編碼壓縮友好，這些優(yōu)勢(shì)可以減少 IO，進(jìn)而提高性能。

?

?

列存的數(shù)據(jù)組織形式

對(duì)于基本類型，例如數(shù)值、string 等，列存可以使用合適的編碼，減少數(shù)據(jù)體積，在 C-Store 論文中對(duì)于是否排序、NDV (Number of Distince Values) 區(qū)分度，這 4 種排列組合，給出了一些方案，例如數(shù)值類型，無(wú)序且 NDV 小的，轉(zhuǎn)成 bitmap，然后 bit-packing 編碼。其他場(chǎng)景的編碼還有 varint、delta、RLE (Run Length Encoding)、字符串字典編碼 (Dictionary Encoding) 等，這些輕量級(jí)的編碼技術(shù)僅需要多付出一些 CPU，就可以節(jié)省不小的 IO。對(duì)于復(fù)雜類型，嵌套類型的可以使用 Google Dremel 論文 [4] 提出 Striping/Assembly 算法 (開源 Parquet)，使用 Definition Level+Repetition Level做編解碼。一些數(shù)值類型有時(shí)也可以嘗試大一統(tǒng)的用 bitshuffle [14] 做轉(zhuǎn)換，配合壓縮效果也不錯(cuò)，例如 KUDU [7] 和百度 Palo (Doris) 中有應(yīng)用。在編碼基礎(chǔ)上，還可以進(jìn)行傳統(tǒng)的壓縮，例如 lz4、snappy、zstd、zlib 等，一般發(fā)現(xiàn)壓縮率不理想時(shí)可以不啟用。

?

一些其他的選項(xiàng)，包括 HBase，實(shí)際存儲(chǔ)的是純二進(jìn)制，僅支持 Column Family，實(shí)際不是 columnar format，一些序列化框架和 Hadoop 融合比較好的，例如 Avro，也不是列式存儲(chǔ)。

?

?

儲(chǔ)存格式

現(xiàn)代的 OLAP 往往采用行列混存的方案，采用 Data Block + Header/Footer 的文件結(jié)構(gòu)，例如 Parquet、ORC，Data Block 使用 Row Group (Parquet的叫法，ORC叫做Stripe) -> Column Chunk -> Page 三層級(jí)，每一層又有 metadata，Row Group meta包含 row count，解決暴力 count(*)，Column Chunk meta 包含 max、min、sum、count、distinct count、average length 等，還有字典編碼，解決列剪枝，并且提供基礎(chǔ)信息給優(yōu)化器，Page meta 同樣可以包含 max、min 等，跳頁(yè)用于加速計(jì)算。

?

?

存儲(chǔ)索引

在 Parquet、ORC 中，除了列 meta 信息外，不提供其他索引，在其他存儲(chǔ)上，支持了更豐富的索引，索引可以做單獨(dú)的塊 (Index Block)，或者形成獨(dú)立的文件。例如阿里云 ADB [5]，對(duì)于 cardinality 較小的，可以做 bitmap 索引，多個(gè)條件下推使用 and/or。倒排索引也是可選的，需要在空間和性能上有所折中，還可以支持全文檢索。Bloom Filter 可以按照 page 粒度做很多組，加速 "in", "=" 查詢，快速做 page 剪枝。另外，假設(shè)數(shù)據(jù)按照某個(gè)列或者某幾個(gè)列是有序的，這樣可以減少數(shù)據(jù)隨機(jī)性，好處在于相似的數(shù)據(jù)對(duì)編碼壓縮有利，而且可以基于 Row Group、Column Chunk、Page 的 meta 做有效的過(guò)濾剪枝，有序列可以使用 B-Tree、Masstree [6]（例如KUDU [7]），或者借鑒 LevelDB 的思想，在 Index Block 內(nèi)對(duì)有序列做稀疏索引，方便二分查找，Index Block 可以用 LRU Cache 盡量常駐內(nèi)存，這樣有利于按照排序列做點(diǎn)查 (point query) 和順序掃描的范圍查詢 (range query)。另外其他列也可以做稀疏有序索引。有序列如果是唯一，可以看做 OLTP 中主鍵的概念。

?

?

分布式存儲(chǔ)

DAC (Divide And Conquer) 在分布式領(lǐng)域也是屢試不爽，要突破單機(jī)存儲(chǔ)大小和 IO 限制，就需要把一個(gè)文件劃分為若干小分片 (sharding)，以某個(gè)列做 round-robin、constant、random、range、hash 等，分布在不同的文件或者機(jī)器，形成分布式存儲(chǔ)。

?

第一類，存儲(chǔ)計(jì)算一體的架構(gòu)，基于單機(jī)磁盤 (SATA、SSD、NVM)，例如 Greenpulm 基于 PostgreSQL，還有 ClickHouse、百度 Palo (Doris) 等，是 share nothing 架構(gòu)，可實(shí)現(xiàn)多副本，擴(kuò)容需要 reshard 往往比較耗時(shí)。

?

第二類，存儲(chǔ)計(jì)算分離，文件存在分布式存儲(chǔ) (GFS、HDFS) 或者對(duì)象存儲(chǔ) (S3、OSS、GCS)，是 share everthing (share storage) 架構(gòu)，好處在于擴(kuò)展性和可用性的提高，由于存儲(chǔ)網(wǎng)絡(luò)延遲，所以一般都做批量、追加寫，而非隨機(jī)寫，這把雙刃劍也加大了 OLAP 在實(shí)時(shí)更新上難度，所以很多都放棄了實(shí)時(shí)寫和 ACID 能力。存儲(chǔ)計(jì)算分離的架構(gòu)上，例如文件如果存在 HDFS 上，每個(gè)分片是一個(gè) HDFS block（例如 128MB 大小），便于高吞吐大塊 IO 順序讀，一個(gè) Row Group 大小等于 block size，便于上層計(jì)算引擎，例如 Spark SQL 作業(yè)并行計(jì)算。存儲(chǔ)計(jì)算一體架構(gòu)，可以更專心的設(shè)計(jì)文件和分片管理系統(tǒng)，采用 Centralized Master + 多個(gè) Tablet 架構(gòu)，例如 KUDU 以及 OLTP 新興的 Tikv，分片的多副本依賴于一致性協(xié)議 Multi-Paxos 或者支持亂序提交的 Raft 協(xié)議，多個(gè)分片組成 Raft-Group，這樣可以打散一個(gè)表（文件）到多分片多副本的架構(gòu)上，既保證了擴(kuò)展性又保證了高可用。Centralized Master 管理分片存放的位置，元數(shù)據(jù)，便于負(fù)載均衡、分裂合并等。

?

示例：數(shù)據(jù)按 uid range 分片。?

• ?
• ?
• ?
• ?
• ?
• ?
• ?

shard1 shard2+---------------+ +---------------+ |uid| date | |uid| date | +---------------+ +---------------+ | 1 | 2020-11-11| | 3 | 2020-11-13|| 2 | 2020-11-12| | 4 | 2020-11-14|+---------------+ +---------------+

?

示例：數(shù)據(jù)按uid hash分片，f(uid) = uid mod 2。?

• ?
• ?
• ?
• ?
• ?
• ?
• ?

shard1 shard2+---------------+ +---------------+ |uid| date | |uid| date | +---------------+ +---------------+ | 1 | 2020-11-11| | 2 | 2020-11-12|| 3 | 2020-11-13| | 4 | 2020-11-14|+---------------+ +---------------+

?

?

數(shù)據(jù)進(jìn)一步分區(qū)

數(shù)據(jù)分片的基礎(chǔ)上，可以進(jìn)行更細(xì)粒度的分區(qū) (partition)，便于做分區(qū)剪枝 (partition prune)，直接跳過(guò)不需要掃描的文件。分片 (sharding) 策略按照 range，可以優(yōu)化 OLAP 的范圍查詢和快速點(diǎn)查；按照 hash 分區(qū)，可以充分打散，有效解決 hotspot 熱點(diǎn)。將二者結(jié)合，做二級(jí)分區(qū) (two-level)，例如阿里云 ADB、ClickHouse、KUDU，支持 DISTRIBUTED BY HASH 再 PARTITION BY RANGE，而百度 Palo (Doris) 一般先按時(shí)間一級(jí)分區(qū)，更好做冷熱數(shù)據(jù)區(qū)分，二級(jí)分區(qū)分桶采用 hash。

?

示例：數(shù)據(jù)按照二級(jí)分區(qū)，一級(jí)分區(qū)uid hash分片，二級(jí)分區(qū)按date，形成4個(gè)文件。?

• ?
• ?
• ?
• ?
• ?
• ?
• ?
• ?
• ?
• ?
• ?
• ?

shard1 shard2+---------------+ +---------------+ |uid| date | |uid| date | +---------------+ +---------------+ | 1 | 2020-11-11| | 2 | 2020-11-12|+---------------+ +---------------+
+---------------+ +---------------+ |uid| date | |uid| date | +---------------+ +---------------+ | 3 | 2020-11-13| | 3 | 2020-11-14| +---------------+ +---------------+

?

?

實(shí)時(shí)寫入和 ACID

隨著實(shí)時(shí)數(shù)倉(cāng)和 HTAP，HSAP [8] 等概念的興起，對(duì)于傳統(tǒng)數(shù)據(jù)處理的 Lambda 架構(gòu)弊端就凸顯出來(lái)，鏈路長(zhǎng)，數(shù)據(jù)冗余，數(shù)據(jù)一致性不好保證等。融合 OLTP 的能力，第一點(diǎn)就是在之前所述的 immutable table file 上做實(shí)時(shí)增刪改，要保證低延遲，高吞吐，可以借鑒 LSM-Tree 思想，優(yōu)化寫吞吐，將流式的低延遲隨機(jī)寫，最終變成聚批 mini-batch 的 group commit 順序?qū)?#xff0c;依賴 write-ahead log 保證持久性，最終形成 Base + Delta 的文件結(jié)構(gòu)，讀流程包括點(diǎn)查或者掃描，基于 Base 的同時(shí)，還需要 merge Delta 的變化，另外后臺(tái)通過(guò) minor compaction 和 major compaction 不斷的合并 Delta 和 Base，可以不斷優(yōu)化讀性能，在阿里云 ADB，KUDU，Google MESA [9] 里面都采用了類似的方案。在讀寫一致性層面，需要提供 ACID 和事務(wù)隔離特性，比較好保證單行和 mini-batch 的原子性，持久性不言而喻，對(duì)于一致性和事務(wù)隔離，可以采用 MVCC 機(jī)制，每個(gè)寫都帶有 version，很簡(jiǎn)單的實(shí)現(xiàn)帶版本查一致性，快照一致性 (snapshot isolation)。

?

?

02

談?dòng)?jì)算??

?

查詢步驟

SQL 語(yǔ)言是?OLAP 的標(biāo)配，一個(gè)完整的 SQL 查詢步驟包括：

SQL詞法解析，語(yǔ)法解析；

形成抽象語(yǔ)法樹 (AST)；

校驗(yàn)檢查；

AST轉(zhuǎn)成關(guān)系代數(shù)表達(dá)式 (relational algebra)；

根據(jù)關(guān)系代數(shù)表達(dá)式生成執(zhí)行計(jì)劃，先生成邏輯執(zhí)行計(jì)劃 (logical plan)；

經(jīng)過(guò)優(yōu)化器生成最優(yōu)的執(zhí)行計(jì)劃；

根據(jù)執(zhí)行計(jì)劃生成物理執(zhí)行計(jì)劃 (physical plan)；

最終交由執(zhí)行器執(zhí)行并返回結(jié)果。

由 SQL 到 AST 的過(guò)程，類庫(kù)和工具較多，C++可用 Lex/Yacc，Java 可用 JavaCC/ANTLR，也可以自己手寫實(shí)現(xiàn)。由 AST 到關(guān)系代數(shù)表達(dá)式，可以使用 visitor 模式遍歷。下一章節(jié)談優(yōu)化器，本節(jié)聚焦在物理執(zhí)行計(jì)劃后的執(zhí)行階段。

?

?

OLAP 數(shù)據(jù)建模分類

ROLAP 和 MOLAP。Relational OLAP (ROLAP)?對(duì) SQL 支持好，查詢靈活，使用組合模型，雪花或者星型模型組織多張表。ROLAP 計(jì)算的數(shù)據(jù)規(guī)模往往小于離線大數(shù)據(jù)計(jì)算（Hive/Spark），ROLAP產(chǎn)品很多，包括傳統(tǒng)的 Greenpulm、Vertica、Teradata，Sql-on-Hadoop 系的 Presto、Impala、Spark SQL、HAWQ，云計(jì)算廠商的阿里云 ADB、Google BigQuery，AWS RedShift，有學(xué)術(shù)界出品的 MonetDB [10]，還有新興的 ClickHouse。

?

如果把查詢階段分為

• ?
• ?
• ?
• ?

cache /\ |pre-computing -> computing -> post computing

?

上面的提到的存儲(chǔ)技術(shù)更多是為了 ROLAP 在 computing 階段優(yōu)化考慮的，如果把計(jì)算中的熵前置到 pre-computing 階段做預(yù)計(jì)算，也可以大幅優(yōu)化 computing 階段。

?

Multidimensional OLAP (MOLAP)?可以把數(shù)據(jù)預(yù)計(jì)算，有些場(chǎng)景下不一定需要細(xì)粒度的fact，可以嚴(yán)格區(qū)分維度列和指標(biāo)列，使用 Kylin、Druid 等，利用上卷 (roll-up) 做數(shù)據(jù)立方體 (data cube)，這樣可以大大減少 OLAP 場(chǎng)景下聚合查詢的 IO，另外百度 Palo、Google MESA，基于上卷操作做物化視圖，也減少了 IO 消耗，所以他們對(duì)于高并發(fā)查詢支持普遍較好，但是缺點(diǎn)就在于查詢不夠靈活，數(shù)據(jù)有冗余。下文主要針對(duì) ROLAP 談?dòng)?jì)算。

?

?

計(jì)算引擎分類

物理執(zhí)行計(jì)劃往往是一個(gè) DAG，每個(gè)節(jié)點(diǎn)都是一種 operator，最下游的葉子節(jié)點(diǎn)一般都是 TableScan operator，這個(gè) DAG 的分布式執(zhí)行器就是計(jì)算引擎 (Query Engine)，分為兩個(gè)流派。

?

第一類是基于離線計(jì)算引擎，例如 Hive on MR，Spark SQL，阿里云 MaxCompute，支持超大規(guī)模的數(shù)據(jù)，進(jìn)行了容錯(cuò)保證，多個(gè) stage 落盤 (spill to disk)，使用 resource manager 調(diào)度和 queueing，作業(yè)可能持續(xù)非常長(zhǎng)的時(shí)間，占用大量資源，并發(fā)低。

?

第二類是MPP，例如 Greenpulm、Presto、Impala、阿里云 ADB，RedShift 支持大規(guī)模數(shù)據(jù)，不需要 resource manager 耗時(shí)的分配資源和調(diào)度任務(wù)，long-running 的 task manager，只需要輕量級(jí)的調(diào)度，查詢一般不容錯(cuò)，算子并行執(zhí)行，并行度有限制避免 straggler node 影響 TP99，相比基于離線的計(jì)算引擎往往是短任務(wù)，查詢耗時(shí)不會(huì)太長(zhǎng)。

?

Presto、Impala 屬于 Sql-on-Hadoop MPP，利用 Hive metastore，直接讀取 Parquet、ORC 等文件格式，Greenpulm、RedShift 基于 PostgreSQL，阿里云 ADB 采用私有的數(shù)據(jù)存儲(chǔ)技術(shù)，計(jì)算存儲(chǔ)分離的架構(gòu)，存儲(chǔ)表到分布式存儲(chǔ)盤古上。

?

?

MPP 架構(gòu)

通用的 MPP 架構(gòu)組成由 coordinator，worker，metastore，scheduler 組成，各個(gè)產(chǎn)品名稱不同而已。通過(guò) metastore 可以獲取表元信息、分區(qū)/分片位置、輔助 coordinator 做校驗(yàn)等。coordinator 負(fù)責(zé)從 SQL 到物理執(zhí)行計(jì)劃的生成以及執(zhí)行，一個(gè)計(jì)劃往往被切分為多個(gè) plan fragment，plan fragment 之間通過(guò)添加 ExchangeOperator 來(lái)傳遞數(shù)據(jù)（例如 shuffle），邏輯上 plan fragment 等同于 stage，scheduler 管理所有 worker 節(jié)點(diǎn)，coordinator 調(diào)用 scheduler 分發(fā) stage 到不同的 worker 節(jié)點(diǎn)執(zhí)行，就形成了很多 task。一個(gè) task，包含一個(gè)或者多個(gè) operator 算子，最簡(jiǎn)單的算子實(shí)現(xiàn)就是解釋執(zhí)行 (interpreted) 的模式。算子包括 Project、Filter、TableScan、HashJoin、Aggregation 等，葉子節(jié)點(diǎn)一般是 TableScan，拉取存儲(chǔ)中數(shù)據(jù)。MPP 架構(gòu)就是充分利用分布式的特性，讓算子分布式的并行計(jì)算，同時(shí) task 內(nèi)部也可以做并行處理，加速查詢。

?

?

計(jì)算執(zhí)行

數(shù)據(jù)流

DAG 在進(jìn)行數(shù)據(jù)流動(dòng)時(shí)，采用 pipeline 方式，也就是上游 stage 不用等下游 stage 完全執(zhí)行結(jié)束就可以拉取數(shù)據(jù)并執(zhí)行計(jì)算。數(shù)據(jù)不落盤，算子之間通過(guò)內(nèi)存直接拷貝到 socket buffer 發(fā)送，需要保證內(nèi)存足夠大，否則容易 OOM。

?

火山模型 (Volcano-style)

是一種 Row-Based Streaming Iterator Model 算子的實(shí)現(xiàn)，只需要 open、next、close 三個(gè)函數(shù)，就可以實(shí)現(xiàn)數(shù)據(jù)從底向上的“拉”取，驅(qū)動(dòng)計(jì)算進(jìn)行。

?

向量化執(zhí)行 (Vectorized query)

MonetDB 論文提出了火山模型的改進(jìn)方案——向量化執(zhí)行，火山模型 tuple-at-a-time 的實(shí)現(xiàn)，每個(gè)算子執(zhí)行完傳遞一行給上游算子繼續(xù)執(zhí)行，函數(shù)調(diào)用過(guò)多，且大量的虛函數(shù)調(diào)用，條件分支預(yù)測(cè)失敗，直接現(xiàn)象就是 CPU 利用率低 (low IPC)。而現(xiàn)代的 CPU 有多級(jí)流水線可以實(shí)現(xiàn)指令級(jí)并行，超標(biāo)量 (super scalar) 實(shí)現(xiàn)亂序執(zhí)行，對(duì)于 forloop 可以有效優(yōu)化，超線程還能實(shí)現(xiàn)線程級(jí)并行，而 CPU 多級(jí)的 Cache，以及 cache line 的有效利用避免 cache miss，再配合編譯器的優(yōu)化，都會(huì)大大加速計(jì)算過(guò)程。向量化執(zhí)行的思想就是算子之間的輸入輸出是一批（Batch，例如上千行）數(shù)據(jù)，這樣可以讓計(jì)算更多的停留在函數(shù)內(nèi)，而不是頻繁的交互切換，提高了 CPU 的流水線并行度，而且還可以使用 SIMD 指令，例如 AVX 指令集來(lái)實(shí)現(xiàn)數(shù)據(jù)并行處理。實(shí)際實(shí)現(xiàn)中，例如 Impala 各個(gè)算子的 input 雖然是 RowBatch，但除了 TableScan 算子，其他的也是火山模型執(zhí)行式的 row by row 處理，TableScan 讀存儲(chǔ)，列式內(nèi)存布局加速 pushdown 的 filter 執(zhí)行，aggregation 下推后還可以使用 SIMD 指令加速聚合。但是向量化也會(huì)帶來(lái)額外的開銷，就是物化中間結(jié)果 (materlization)，以犧牲物化的開銷換取更高的計(jì)算性能。

?

動(dòng)態(tài)代碼生成 (codegen)

解釋執(zhí)行 (interpreted) 的算子，因?yàn)槊嫦蛲ㄓ没O(shè)計(jì)，大數(shù)據(jù)集下往往效率不高，可以使用 codegen 動(dòng)態(tài)生成算子邏輯，例如 Java 使用 ASM 或者 Janino，C++ 使用 LLVM IR，這樣生成的算子更貼近計(jì)算，減少了冗余和虛函數(shù)調(diào)用，還可以多個(gè)算子糅合成一個(gè)函數(shù)。另外表達(dá)式計(jì)算的 codegen 還可以做的更極致，一些簡(jiǎn)單的計(jì)算可以做成匯編指令，進(jìn)一步加速。

?

關(guān)于向量化或者 codegen，孰優(yōu)孰劣，論文 Everything You Always Wanted to Know About Compiled and Vectorized Queries But Were Afraid to Ask [11] 進(jìn)行了深入的對(duì)比。二者也可以融合，通過(guò) codegen 生成向量化執(zhí)行代碼，另外也不一定做 wholestage codegen，和解釋執(zhí)行也可以一起配合。

?

計(jì)算的耗時(shí)有一部分會(huì)損耗在 IO、CPU 的閑置上。內(nèi)存的布局和管理，行式布局還是列式布局，對(duì)于 CPU Cache 是否友好，內(nèi)存池還是按需分配，都會(huì)影響著系統(tǒng)的吞吐，C++ 可自行維護(hù) Arena 或者使用 jemalloc 等框架，而 Java 的 heap memory 比較低效還影響 GC，因此使用 Unsafe API 操作堆外內(nèi)存。另外 Arrow 的興起，也對(duì)于跨進(jìn)程通信后，不必進(jìn)行數(shù)據(jù)反序列化、內(nèi)存分配再拷貝，就可以讀取列式的數(shù)據(jù)，也進(jìn)一步加速了計(jì)算。

?

?

常見(jiàn)算子實(shí)現(xiàn)

TableScan 算子直讀底層數(shù)據(jù)源，例如 Presto，抽象了很好了 connector，可對(duì)接多種數(shù)據(jù)源（Hadoop，對(duì)象存儲(chǔ)等），一般都支持 projection、filter，因此可以做 filter pushdown 和 projection pushdown 到 TableScan，另外在做 predicate 的時(shí)候可以使用 lazy materialization（延遲物化）的技巧去 short circuit 掉先不需要的列。

?

Join 算子的實(shí)現(xiàn)，如果兩個(gè)表都很小，最簡(jiǎn)單的利用 in-memory hash join、simple nested loop join；一大一小，可以廣播小表 (broadcast)，一般維度表都比較小，如果大表有索引，掃描小表，根據(jù)大表做 index lookup join，否則基于小表做 build table，大表做 probe table，實(shí)現(xiàn) hash join；兩個(gè)大表，如果兩個(gè)表的 join key 的一級(jí)分區(qū)策略相同，則可以很好的對(duì)齊，避免大表 shuffle，直接在大表的 shard 做 local join，如果不能對(duì)齊，則兩個(gè)表按照 join key shuffle 到其他節(jié)點(diǎn)，重分布式后再做 join；另外如果兩個(gè)表的 join key 有序，還可以使用 sort-merge join。

?

?

資源管理與調(diào)度

MPP 架構(gòu)下 coordinator 需要 scheduler 調(diào)度 task 到 worker 節(jié)點(diǎn)，對(duì)于長(zhǎng)計(jì)算任務(wù)或者 ETL 任務(wù)，會(huì)占用很多資源，導(dǎo)致 OLAP 的并發(fā)度受限，其他請(qǐng)求需要排隊(duì)，因此很難服務(wù)對(duì)外在線請(qǐng)求，為了迎合混合負(fù)載，傳統(tǒng) scheduler 簡(jiǎn)單粗暴的調(diào)度和資源管理已經(jīng)無(wú)法滿足要求，因此可以進(jìn)行任務(wù)的 fine grained schedule 避免空閑資源，請(qǐng)求間對(duì)資源的使用盡量的隔離，避免 bad query 吃滿資源，簡(jiǎn)單的策略可以通過(guò) label 化集群，或者用 SQL hint 實(shí)現(xiàn)，區(qū)分長(zhǎng)短計(jì)算任務(wù)，讓更多的短任務(wù)也可以快速得到響應(yīng)。當(dāng) OLAP 系統(tǒng)足夠高性能后，更好的資源管理和調(diào)度，將會(huì)提升 OLAP 為一個(gè)支持高并發(fā)、低延遲的，可對(duì)外提供在線服務(wù)的系統(tǒng)，而不僅僅是一個(gè) in-house 的分析系統(tǒng)。

?

?

03?

談優(yōu)化器??

查詢優(yōu)化器不光是傳統(tǒng)數(shù)據(jù)庫(kù) DB2、Oracle、MySQL 的核心，在 OLAP 里也至關(guān)重要。AST 轉(zhuǎn)為 SQL 形式化表達(dá)語(yǔ)言——關(guān)系代數(shù)表達(dá)式 (relational algebra)，代碼實(shí)現(xiàn)就是一顆關(guān)系運(yùn)算符組成的樹，查詢優(yōu)化主要是圍繞著“等價(jià)交換”的原則做相應(yīng)的轉(zhuǎn)換，優(yōu)化關(guān)系代數(shù)表達(dá)式。關(guān)系代數(shù)的基本運(yùn)算包括投影 (project)、選擇 (select)、并 (union)、差 (set difference)、連接 (join) 等。優(yōu)化器分為 Rule-Based Optimizer (RBO) 和 Cost-Based Optimizer (CBO) 兩類。

?

?

RBO

會(huì)將原有表達(dá)式裁剪掉，遍歷一系列規(guī)則 (Rule)，只要滿足條件就轉(zhuǎn)換，生成最終的執(zhí)行計(jì)劃。一些常見(jiàn)的規(guī)則包括分區(qū)裁剪 (Partition Prune)、列裁剪、謂詞下推 (Predicate Pushdown)、投影下推 (Projection Pushdown)、聚合下推、limit 下推、sort 下推、常量折疊 (Constant Folding)、子查詢內(nèi)聯(lián)轉(zhuǎn) join 等。

?

?

CBO

會(huì)將原有表達(dá)式保留，基于統(tǒng)計(jì)信息 + 代價(jià)模型，嘗試探索生成等價(jià)關(guān)系表達(dá)式，最終取代價(jià)最小的執(zhí)行計(jì)劃。CBO 的實(shí)現(xiàn)有兩種模型，Volcano 模型，Cascades 模型，很流行的 Calcite [12] 使用 Volcano 模型，比如 Flink、Hive 都基于此，Orca 使用 Cascades 模型，在 Greenpulm 中使用。優(yōu)化器需要盡量的高效，高效的生成搜索空間、動(dòng)態(tài)規(guī)劃遍歷搜索空間 (top down、bottom up、depth-first 等)，高效的剪枝策略等都可以加速優(yōu)化過(guò)程。統(tǒng)計(jì)信息包括表數(shù)據(jù)大小，row count。查詢列的 trait metadata (min、max、cardinality等)，sortness、可利用的索引，直方圖 (Histogram) 分布統(tǒng)計(jì)等。Join 是 OLAP 最消耗吞吐的算子之一，也是 ROLAP 對(duì)于分析最強(qiáng)大的地方，可以進(jìn)行多表的關(guān)聯(lián)查詢，常見(jiàn)的優(yōu)化手段包括 join reorder，使用 left-deep tree 還是 bushy tree 執(zhí)行 join，以及如何選擇 join 算法實(shí)現(xiàn)（上節(jié)提到的各種 join 實(shí)現(xiàn)的選擇），結(jié)合高效索引結(jié)構(gòu)實(shí)現(xiàn)的 index join，group by 下推、top-n 下推等。

?

?

04

談趨勢(shì)??

OLAP 領(lǐng)域經(jīng)歷了從 RDBMS 建立起來(lái)的 SQL + OLAP，到 ETL + 專有 OLAP 的數(shù)倉(cāng)階段，目前仍在不斷演進(jìn)，更多的云廠商也加入這個(gè)領(lǐng)域，展示出、也正經(jīng)歷著如下的趨勢(shì)。

?

實(shí)時(shí)分析

傳統(tǒng)的 OLAP 需要做各種 pipeline、ETL 導(dǎo)入數(shù)據(jù)，這樣的架構(gòu)會(huì)存儲(chǔ)多份數(shù)據(jù)，冗余并且一致性不好保證，也引入過(guò)多的技術(shù)棧和復(fù)雜度，也不能滿足實(shí)時(shí)分析，即使 mini-batch 的處理仍然需要最快數(shù)分鐘。業(yè)界的趨勢(shì)在于賦予 OLAP 高吞吐實(shí)時(shí)寫，提供實(shí)時(shí)查詢能力，例如上游數(shù)據(jù)源，經(jīng)過(guò)流計(jì)算系統(tǒng)，老的架構(gòu)基于 lambda，寫歷史數(shù)據(jù)到存儲(chǔ)再清洗，實(shí)時(shí)數(shù)據(jù)入一些 NoSQL，使用方需要做各種數(shù)據(jù)源 merge 操作，流行的方式是流計(jì)算系統(tǒng)直接寫 OLAP，這樣避免了數(shù)據(jù)孤島，保證了鏈路簡(jiǎn)單，阿里云 hologres 團(tuán)隊(duì)提出的 HSAP (Hybrid Serving/Analytical Processing) [8] 正是這種理念。

?

HTAP

事務(wù)處理和分析處理在一個(gè)數(shù)據(jù)庫(kù)中提供，是最理想的狀態(tài)，但是二者的技術(shù)體系往往又很難融合，因此現(xiàn)在很多數(shù)據(jù)庫(kù)廠商都在做這方面的嘗試，保證數(shù)據(jù)一致性是很大的挑戰(zhàn)，一種思路是從 OLTP 到 OLAP，多副本存儲(chǔ)時(shí)，有些副本是專門為 OLAP 定制的，使用專用的 OLAP 引擎提供查詢，另外就是賦予 ACID 和事務(wù)能力到 OLAP 系統(tǒng)中，使得 OLAP 也支持 INSERT/DELETE/UPDATE 操作。

?

云原生

傳統(tǒng)的 OLAP，例如 Exadata 等依賴于高端硬件，很多 on-premise 的解決方案也面臨擴(kuò)展性和成本問(wèn)題，云原生的架構(gòu)通過(guò)虛擬化技術(shù)，可實(shí)現(xiàn)更好的彈性計(jì)算，如果采用存儲(chǔ)計(jì)算分離的架構(gòu)還可以實(shí)現(xiàn)彈性存儲(chǔ)，這些水平擴(kuò)展的機(jī)制可以很好的兼顧高性能、成本和擴(kuò)展性。

?

多模數(shù)據(jù)結(jié)構(gòu)分析

不僅限于結(jié)構(gòu)化數(shù)據(jù)，半結(jié)構(gòu)化、非結(jié)構(gòu)化的數(shù)據(jù)分析也逐漸在 OLAP 中應(yīng)用，包括向量檢索，JSON、ARRAY 檢索等。

?

軟硬一體化

計(jì)算方面，更好利用多核并行，使得查詢滿足 NUMA-aware，親核性 (affinity) 可以進(jìn)一步榨干系統(tǒng)的吞吐，使用 FPGA、GPU 硬件加速，利用這些硬件提供的超高帶寬和深度流水線可以加速一些向量計(jì)算和聚合操作；存儲(chǔ)方面，隨著存儲(chǔ)查詢帶寬增大、延遲降低，可以應(yīng)用更多新存儲(chǔ)，例如 Intel 傲騰 NVM 3D-XPoint SSD [13] 提供 2.6G/s 的順序讀吞吐，高并發(fā)點(diǎn)查延遲可控制在 10 幾個(gè) us；網(wǎng)絡(luò)方面，基于 RDMA 網(wǎng)絡(luò)，DPDK 等技術(shù)可替換傳統(tǒng)的 tcp，做 kernel bypass，降低網(wǎng)絡(luò)延遲。上層的 OLAP 軟件可以基于這些新硬件做更深度的定制，提供更極致的性能。

?

?

?

?

?

參考資料

?

[1] [從MySQL InnoDB物理文件格式深入理解索引](從MySQL InnoDB物理文件格式深入理解索引)

[2] [A DECOMPOSITION STORAGE MODEL](inf.ufpr.br/eduardo/ens)

[3] [C-Store: A Column-oriented DBMS](vldb.org/archives/websi)

[4] [Dremel: Interactive Analysis of Web-Scale Datasets](static.googleusercontent.com)

[5] [AnalyticDB: Real-time OLAP Database System at Alibaba Cloud](vldb.org/pvldb/vol12/p2)

[6] [Cache craftiness for fast multicore key-value storage](pdos.csail.mit.edu/pape)

[7] [Kudu: Storage for Fast Analytics on Fast Data](kudu.apache.org/kudu.pd)

[8] [數(shù)據(jù)倉(cāng)庫(kù)、數(shù)據(jù)湖、流批一體，終于有大神講清楚了](阿里云Hologres：數(shù)據(jù)倉(cāng)庫(kù)、數(shù)據(jù)湖、流批一體，終于有大神講清楚了！)

[9] [Mesa: Geo-Replicated, Near Real-Time, Scalable Data Warehousing](static.googleusercontent.com)

[10] [MonetDB/X100: Hyper-Pipelining Query Execution](w6113.github.io/files/p)

[11] [Everything You Always Wanted to Know About Compiled and Vectorized Queries But Were Afraid to Ask](vldb.org/pvldb/vol11/p2)

[12] [Apache Calcite: A Foundational Framework for Optimized Query Processing Over Heterogeneous Data Sources](arxiv.org/pdf/1802.1023)

[13] [Intel Optane Series](Intel? Optane? DC SSD Series)

[14] [bitshuffle](github.com/kiyo-masui/b)

總結(jié)

以上是生活随笔為你收集整理的每个大数据工程师都应该知道的OLAP 核心知识点的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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