云原生数据仓库TPC-H第一背后的Laser引擎大揭秘
簡介： 作者| 魏闖先阿里云數(shù)據(jù)庫資深技術(shù)專家
一、ADB PG 和Laser 計算引擎的介紹
（一）ADB PG 架構(gòu)
ADB PG 是一款云原生數(shù)據(jù)倉庫，在保證事務(wù)ACID 能力的前提下，主要解決云上海
量數(shù)據(jù)的實時分析問題。它的架構(gòu)與傳統(tǒng)的MPP 數(shù)據(jù)倉庫非常類似，主要分成兩層，第一層是master 節(jié)點；第二層是work 節(jié)點。
?
master 節(jié)點主要承擔(dān)實時寫入和事務(wù)的處理，執(zhí)行計劃的生成。與其他的傳統(tǒng)的
MPP 數(shù)據(jù)倉庫不同的是ADB PG 的master 節(jié)點支持線性擴展，可以通過多個master
提升整體的事務(wù)能力、實時寫入吞吐能力。
?
work 節(jié)點主要承擔(dān)兩個功能，第一個功能是執(zhí)行，第二個功能是存儲。執(zhí)行引擎采用
的是向量化執(zhí)行引擎，通過向量列式Batch 處理，codegen 技術(shù)，以及Fusion Scan 加速列式計算效率，在一些分析場景性能相對于普通的火山模型有了3~5 倍的提升。
?
同時它的存儲節(jié)點不僅支持傳統(tǒng)的行表和列表，也可以通過外表方式支持一些開源的表
結(jié)構(gòu)，例如Parquet、ORC 等開源數(shù)據(jù)結(jié)構(gòu)。ADB PG 可以直接分析保存在類似于像
OSS/HDFS 等分布式存儲上的數(shù)據(jù)，減少數(shù)據(jù)的導(dǎo)入，可以大幅的降低用戶的使用門檻和存儲成本。
（二）為什么做Laser 計算引擎
為什么不采用PG 原生的計算引擎？
第一，PG 是一個傳統(tǒng)的事務(wù)型數(shù)據(jù)庫，它主要的優(yōu)化大多來自于TP 的事務(wù)優(yōu)化，并沒有針對海量數(shù)據(jù)的分析計算做定制化的優(yōu)化。
?
第二，PG 計算引擎采用解釋執(zhí)行的邏輯，復(fù)雜表達(dá)式采用函數(shù)執(zhí)行樹的遞歸的調(diào)用解
釋執(zhí)行。如圖中的例子所示，每個表達(dá)式都被翻譯成一個函數(shù)并組成一個執(zhí)行樹。每一條的數(shù)據(jù)都通過以上的函數(shù)遞歸調(diào)用去完成最終的計算。它帶來的問題就是在海量千萬以上的數(shù)據(jù)計算場景，虛函數(shù)調(diào)用大幅影響計算的性能。
?
第三， PG 默認(rèn)只支持行存存儲引擎，并不支持列存，所以它的整個計算執(zhí)行過程是逐行處理數(shù)據(jù)，并沒有對列存做定制化的優(yōu)化。
?
第四， PG 代碼具有非常好的擴展性、兼容性，但是在性能上考慮不多。例如說在計算過程中會涉及到內(nèi)存的多次拷貝，序列化的開銷比較高。
?
最后，PG 采用的是單分區(qū)單進(jìn)程執(zhí)行模式，無法充分發(fā)揮現(xiàn)代多核CPU 的優(yōu)勢。
?
?
（三）主流OLAP 業(yè)界方案
在開始ADB PG 計算引擎的選型過程，我們重點調(diào)研了當(dāng)前主流的OLAP 業(yè)界主流
方案。
主要分成兩大類，第一類：向量化執(zhí)行；第二類：編譯執(zhí)行。
第一：向量化執(zhí)行的基本做法，非常類似于火山模型，主要差別來自于它采用的是批量計算，每一批里優(yōu)先列式計算。
這種模式優(yōu)勢在于可以充分發(fā)揮CPU 的流水線執(zhí)行和內(nèi)存的順序訪問，減少cache
的miss。缺點是第一實現(xiàn)邏輯比較復(fù)雜。第二，它需要批量的數(shù)據(jù)，并不適合每次計算數(shù)量較小的OLTP 場景。第三,它需要緩存批量數(shù)據(jù)，緩存本身帶來一定的內(nèi)存開銷。
?
第二：編譯執(zhí)行基本做法是使用Codegen 技術(shù)，將所有的算子編譯成函數(shù)，通過PUSH 的模型自下而上通過數(shù)據(jù)上推完成計算。
?
優(yōu)點一：由于每次計算的都是一行數(shù)據(jù)，執(zhí)行過程可以將這一行數(shù)據(jù)保存在寄存器里面，寄存器計算代替內(nèi)存計算。優(yōu)點二，它通過Codegen 技術(shù)把復(fù)雜的算子編譯成一個函數(shù)，所以它非常適合計算復(fù)雜性非常高的計算加速。
?
缺點在于，PUSH 模型控制邏輯比較復(fù)雜，同時由于采用單條計算，無法做到內(nèi)存的順序訪問，所以它整體的Cache miss 率比較高。典型的代表產(chǎn)品有Spark 和 Peloton。
?
ADB PG 綜合考慮這兩類方案的優(yōu)缺點，最終使用了向量化的方案，主要考慮到ADB PG 原生PG 火山模型與向量化模型架構(gòu)上較為接近，改造成向量計算引擎的邏輯順暢，改造成本較編譯執(zhí)行小。
（四）業(yè)界主流計算引擎對比
我們對業(yè)界主流開源計算引擎做了對比，包括ClickHouse、PG11、Spark、ADBPG。在執(zhí)行模型上，ClickHouse 和ADB PG、PG11 都采用的向量執(zhí)行，Spark 采用
的是編譯執(zhí)行。
?
在內(nèi)存模型上，ClickHouse 采用的是列存、PG11 采用行存、Spark 采用行存、ADB PG 采用行列混存。行列混存主要應(yīng)用在類似于join、AGG 的場景，我們可以將多列g(shù)roup by、hashtable 數(shù)據(jù)拼成一列數(shù)據(jù)，可以充分發(fā)揮順序訪問的效率。
?
在即時編譯上，ClickHouse 采用表達(dá)式級LLVM、PG11 采用表達(dá)式級LLVM，Spark 采用Stage Java 技術(shù),ADB PG 采用算子級LLVM 技術(shù)。算子級LLVM 技術(shù)可以提升算子的計算性能。
?
在硬件加速上，ClickHouse 和PG11 都不支持硬件加速，Spark 支持FPGA 加速，ADB PG 采用IR 技術(shù)，可以通過將IR 翻譯成對應(yīng)的機器執(zhí)行代碼,從而支持GPU 加速。
?
二、laser 計算引擎的核心技術(shù)
Laser 計算引擎的核心技術(shù)主要包括5 大塊:
1. 向量計算引擎
2. 行列式內(nèi)存模型
3. JIT 加速
4. SIMD 指令加速
5. FUSION SCAN
第一,向量計算引擎，傳統(tǒng)火山模型中算子之間數(shù)據(jù)逐條交互，向量化計算引擎之間的交互的是BATCH 數(shù)據(jù)，然后在每個算子內(nèi)部，采用的列式多條數(shù)據(jù)并行計算，這種邏輯可以充分的發(fā)揮CPU 流水線的作用。
?
在內(nèi)存模型上，我們采用的是行列混存內(nèi)存模型。在算子之間數(shù)據(jù)傳遞的是一個mini batch，mini batch 內(nèi)部采用的行列混存的結(jié)構(gòu)。由于每列數(shù)據(jù)在內(nèi)存里都是連續(xù)擺放的，所以每次計算一列都是內(nèi)存的順序訪問的過程。
?
第三，針對復(fù)雜計算，采用JIT 技術(shù)加速。可以利用LLVM CodeGen 技術(shù)將復(fù)雜計算過程轉(zhuǎn)換成IR 代碼，然后再通過IR 代碼翻譯成機器碼。它的好處是可以避免類型判斷，減少虛函數(shù)的調(diào)用，從而提升計算性能。
?
第四，針對一些簡單場景（如：聚合場景、固定場景），利用現(xiàn)代CPU 的SIMD 指令，實現(xiàn)單條指令多條數(shù)據(jù)的并行執(zhí)行，大幅提升這些簡單場景的效率。
?
第五，針對列存場景，可以通過FUSION SCAN 去減少無用列讀取，避免無用內(nèi)存的中間拷貝，從而提升列表的計算性能。
?
?
（一）向量計算引擎
下圖是一個典型的火山模型下SUM 算子的計算過程。對于火山模型，如果總共有n條數(shù)據(jù)，就會調(diào)用n 次的函數(shù)調(diào)用。右邊是向量化執(zhí)行過程，sum 函數(shù)接收輸入?yún)?shù)是一個數(shù)組，而不是兩個變量。整個執(zhí)行過程，數(shù)據(jù)按2048 條分批處理，每2048 條數(shù)據(jù)調(diào)用一次sum 函數(shù)。
?
從這個例子中明顯可以看出：
第一，Sum 函數(shù)調(diào)用從原來的n 次變成n÷2048，減少了多次。
第二，在函數(shù)內(nèi)部處理中，由于計算的數(shù)據(jù)是一個batch，就可以充分發(fā)揮SIMD 指令加速效果，實現(xiàn)單條指令多條語句的并行計算。
第三，可以針對一些算子，如AGG 和JOIN，可以將AGG 和JOIN 算子函數(shù)合并一個函數(shù)，可以進(jìn)一步的減少虛函數(shù)調(diào)用，提升系統(tǒng)性能。
?
由于計算過程中全部采用數(shù)組計算，可以將計算過程中的數(shù)組使用內(nèi)存池化技術(shù)管理。通過MemoryPool 可以實現(xiàn)定長數(shù)據(jù)的內(nèi)存的復(fù)用，避免頻繁內(nèi)存分配和釋放，減少整個內(nèi)存的碎片。在實際的TPC-H 的測試中，使用向量化引擎后，Q1 提升了120%，Q18提升了190%。
（二）SIMD指令加速
針對簡單的加速，可以利用現(xiàn)代CPU 的SSE、AVX 指令，一條指令可以實現(xiàn)512bit 數(shù)據(jù)計算。
?
我們對TPCH 測試中的Lineitem 表做性能的對比測試，在使用SIMD 以后，整體的性能從原來的1 秒多降低到了200 多毫秒，有了4 倍左右的提升。
（三）Just-in-Time 編譯優(yōu)化
ADB PG 不僅支持表達(dá)式級的CodeGen，也支持算子級的CodeGen。每個plan的node 對應(yīng)一個CodeGen 單元和一個Executor，CodeGen 單元根據(jù)plan node 生成code(IR)，Executor 根據(jù)硬件平臺選擇不同的后端，將IR 生成對應(yīng)的執(zhí)行文件，并申請資源執(zhí)行，最終的結(jié)果通過master 返回給客戶端。
?
如圖所示，對于這樣一個簡單的表達(dá)式，where a>10 and b<5，如果采用解釋執(zhí)行，總共包括三次函數(shù)調(diào)用，1、a>10；2、b<5；3、and 函數(shù)。
?
如果使用LLVM GIT 編譯優(yōu)化，上面的三個函數(shù)就編譯成三條LLVM 指令，避免了三次函數(shù)調(diào)用的開銷。
?
在TPCH 測試場景中，使用JIT 加速后整體的性能提升了20%~30%，并且在測試中發(fā)現(xiàn),表達(dá)式越復(fù)雜，性能提升越明顯。
?
（四）Fusion Scan 優(yōu)化
Fusion Scan 主要優(yōu)化是減少無用列的讀取，并且盡量的減少無用數(shù)據(jù)的讀取和內(nèi)存的拷貝。
?
舉個例子，如果要查詢滿足a 大于3 和b 小于6 的a，c*d 的值，傳統(tǒng)做法是對數(shù)據(jù)庫中的每條數(shù)據(jù)數(shù)據(jù)，做a 大于3 和b 小于6 的條件過濾并且計算對應(yīng)列的值。
?
Fusion Scan 的做法分成兩階段：
第一階段是對過濾列做計算。把a 列和b 列的所有數(shù)據(jù)讀出來，對每條數(shù)據(jù)進(jìn)行判斷。如圖所示，滿足條件的只有第一行第三行，我們把第一行第三行號保存在一個bitset中，同時把第一行和第三行的a 列值也保存在mini batch 中；
?
第二階段是計算project 列，由于滿足這個條件只有第一行和第三行，我們只需要把c 列和d 列的第一行和第三行的值讀取出來。同時為了避免中間結(jié)果的數(shù)據(jù)拷貝，我們直接去將c 列和d 列的值結(jié)果相乘，把結(jié)果保存在mini batch 的第二列中。
?
在計算過程中，我們提前將表達(dá)式編譯成IR 代碼，可以避免了多次表達(dá)式函數(shù)的遞歸調(diào)用。
?
以上過程的主要優(yōu)化點在于：
第一、避免無用列表D、E、F、G 列讀取；
第二、實現(xiàn)了按需讀取，只有滿足條件的c 列和d 列的里面內(nèi)容才進(jìn)行計算和IO，不需要讀那些不滿足條件的數(shù)據(jù)。同時在c 和d 計算過程中，直接進(jìn)行c 和d 的讀取，無需內(nèi)存中間結(jié)果的拷貝。
?
在實際執(zhí)行過程中，Fusion Scan 結(jié)合列存塊block 索引做進(jìn)一步的優(yōu)化。block
索引中包含了數(shù)據(jù)塊的min 和max，我們可以將min 和max 值和where 條件做交集，
只有這個交集非空的話，才會去真正讀取block 的值，否則可以直接跳過這個block。
?
通過Fusion Scan 的技術(shù)，在列存的場景Scan 算子整體的性能有3 倍以上的提升。
?
?
（五）算子實現(xiàn)-HashJoin
HashJoin 的向量化執(zhí)行引擎，算法采用Hybrid Hash Join，HashTable 采用開放鏈表數(shù)據(jù)結(jié)構(gòu)。
?
HashJoin 的實現(xiàn)過程，主要包括：
1. 把左表probe 列的值取出來計算它的Hash 值。
2. Hashcode 的值去模entry 個數(shù)，獲取對應(yīng)的行號。
3. 對應(yīng)行號里的所有的entry 對象，比較它的哈希值，如果哈希值相同，再去比較join key。
4. 如果join key 相同，則代表probe 成功，拼接左右表的對應(yīng)列并生成最終的結(jié)果。
?
如何將這樣的執(zhí)行過程用向量化實現(xiàn)?
?
1. 從左表里面讀取批量數(shù)據(jù)。
2. 使用CodeGen 技術(shù)批量計算hash code 值。
3. 根據(jù)hashcode 值，批量查找hash table，得到可能的結(jié)果集。
4. 批量比較左右表的join 列值，如果匹配的話，則拼接左右表的對應(yīng)列并生成最終的結(jié)果。
?
與原來行式的火山模型比起來，向量化執(zhí)行主要差一點在于：
1. 按列計算；
2. 批量計算。
?
（六）插件集成
計算引擎如何與ADB PG 代碼融合？
?
ADB PG 同時支持PG 計算引擎和Laser 向量化計算引擎。優(yōu)化器會自動根據(jù)SQL 的pattern 和掃描的數(shù)據(jù)量來決定是否使用Laser。如果掃描數(shù)據(jù)量太少，則使用原生的計算引擎。如果數(shù)據(jù)量足夠多，并且這些SQL pattern 比較適合使用向量化執(zhí)行引擎的，就使用laser 計算引擎。
?
Laser 引擎的所有代碼采用插件模式，代碼獨立。好處在于代碼可以和原生代碼之間完全是松耦合關(guān)系，不會影響PG 的原生代碼，同時可以復(fù)用里面的一些函數(shù)和數(shù)據(jù)結(jié)構(gòu)。插件模式還帶來一個好處，就是可以實現(xiàn)熱升級。因為采用動態(tài)庫方式，能夠在不重啟PGdameon 進(jìn)程的情況下，替換插件，完成升級LASER 引擎。
?
唯一需要修改的是三個stub 函數(shù)—ExecutorStart、ExecutorRun、ExecutorEnd。
?
（七）TPC-H 結(jié)果
2020 年5 月20 號，我們完成了TPC-H 30TB 場景測試，拿到了世界第一的成績。相比于第二名微軟SQL Server 2019，整體性能提升了290%，且成本只有SQL
Server 的1/4。
?
通過性能指標(biāo)統(tǒng)計，Laser 計算引擎對性能提升起了至關(guān)重要的價值，相對于PG 計算引擎，性能提升了兩倍之多。細(xì)分計算引擎的各種優(yōu)化，其中大半的性能提升都是來自于向量化提升。其次是是JIT 加速，主要來源于表達(dá)式的計算。第三來自于是Fusion Scan，針對列存場景下，我們通過Fusion Scan，減少了內(nèi)存的拷貝，減少了無用的讀取。最后還有小部分來自于SIMD 指令的提升。
三、計算引擎的未來展望
整體的未來轉(zhuǎn)化（以未來一年為計劃）：
第一：2020 年12 月，支持窗口函數(shù)，完成全算子的向量化改造。
第二：2020 年3 月，完成網(wǎng)絡(luò)motion 重構(gòu)。
第三：2020 年6 月，完成算子并行執(zhí)行優(yōu)化，可以充分利用多核能力。
第四：2020 年9 月，完成優(yōu)化器適配。優(yōu)化器不僅適配計劃數(shù)據(jù)書，同時能夠根據(jù)計算引擎來做動態(tài)識別，能夠感知到數(shù)據(jù)的動態(tài)變化，再去動態(tài)去調(diào)整執(zhí)行計劃。
原文鏈接
本文為阿里云原創(chuàng)內(nèi)容，未經(jīng)允許不得轉(zhuǎn)載。
總結(jié)
以上是生活随笔為你收集整理的云原生数据仓库TPC-H第一背后的Laser引擎大揭秘的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Java编程技巧之样板代码
- 下一篇： 独家深度 | 一文看懂 ClickHou