這就是TDSQL的向量化執(zhí)行引擎？有效降低函數(shù)調(diào)用開(kāi)銷，提升CPU利用率

在“國(guó)產(chǎn)數(shù)據(jù)庫(kù)硬核技術(shù)沙龍-TDSQL-A技術(shù)揭秘”系列分享中，5位騰訊云技術(shù)大咖分別從整體技術(shù)架構(gòu)、列式存儲(chǔ)及相關(guān)執(zhí)行優(yōu)化、集群數(shù)據(jù)交互總線、Fragment執(zhí)行框架/查詢分片策略/子查詢框架以及向量化執(zhí)行引擎等多方面對(duì)TDSQL-A進(jìn)行了深入解讀。沒(méi)有觀看直播的小伙伴，可要認(rèn)真做筆記啦！今天帶來(lái)本系列分享中最后一篇騰訊云數(shù)據(jù)庫(kù)高級(jí)工程師胡翔老師主題為“TDSQL-A向量化執(zhí)行引擎技術(shù)揭秘”的分享的文字版。

作為領(lǐng)先的分析型數(shù)據(jù)庫(kù)，TDSQL-A是騰訊首款分布式分析型數(shù)據(jù)庫(kù)，采用全并行無(wú)共享架構(gòu)，具有自研列式存儲(chǔ)引擎，支持行列混合存儲(chǔ)，適應(yīng)于海量OLAP關(guān)聯(lián)分析查詢場(chǎng)景。它能夠支持2000臺(tái)物理服務(wù)器以上的集群規(guī)模，存儲(chǔ)容量能達(dá)到單數(shù)據(jù)庫(kù)實(shí)例百P級(jí)。

一、TDSQL-A向量化執(zhí)行引擎

1.1 背景

要優(yōu)化數(shù)據(jù)庫(kù)的查詢執(zhí)行效率，就要充分地利用CPU、緩存等資源。但在現(xiàn)實(shí)中，硬件發(fā)展帶來(lái)的能力提升并沒(méi)有在實(shí)際應(yīng)用中得到體現(xiàn)。右圖統(tǒng)計(jì)了不同的數(shù)據(jù)庫(kù)操作的CPU利用率，可以看到像seq scan、index scan這些基本的數(shù)據(jù)庫(kù)操作，實(shí)際上并沒(méi)有有效地利用好CPU，利用率還是很低。根本原因在于沒(méi)有按照最高效使用CPU的方式來(lái)設(shè)計(jì)和實(shí)現(xiàn)實(shí)際的應(yīng)用系統(tǒng)。所以我們必須了解當(dāng)代CPU的主要特征。

當(dāng)前CPU主要具有以下五個(gè)特征：

·流水線。可以允許一個(gè)指令周期內(nèi)執(zhí)行多個(gè)命令，具有多個(gè)核心的CPU還支持超標(biāo)量流水線，允許并發(fā)執(zhí)行多個(gè)流水線，進(jìn)一步提高CPU的計(jì)算能力。

·亂序執(zhí)行?？梢栽试S不具有依賴關(guān)系的指令并發(fā)執(zhí)行，避免因?yàn)榈却硞€(gè)指令而阻塞運(yùn)行。

·分支預(yù)測(cè)。CPU會(huì)對(duì)分支進(jìn)行預(yù)測(cè)并根據(jù)預(yù)測(cè)選取下一步執(zhí)行的路徑，提前加載指令和數(shù)據(jù)，但如果分支預(yù)測(cè)失敗，也會(huì)導(dǎo)致流水線中斷。

·分層存儲(chǔ)。CPU周圍設(shè)置了寄存器、L1/L2/L3緩存、內(nèi)存和磁盤等多級(jí)存儲(chǔ)，數(shù)據(jù)越靠近CPU，計(jì)算速度越快，反之，如果頻繁地從內(nèi)存或者磁盤讀取數(shù)據(jù)，會(huì)導(dǎo)致CPU把較多的時(shí)間浪費(fèi)到IO上，計(jì)算效率減低。

·SIMD等新硬件能力。SIMD即單指令多數(shù)據(jù)流，一次操作完成多組操作數(shù)的計(jì)算，可以進(jìn)一步提高計(jì)算效率。像SIMD等新硬件提供了更強(qiáng)的執(zhí)行能力。

我們針對(duì)CPU的這些特征，提出了幾個(gè)數(shù)據(jù)庫(kù)查詢性能的優(yōu)化方向：

首先，可以通過(guò)向量化批量計(jì)算提高CPU流水線和亂序執(zhí)行的執(zhí)行效率；其次，編寫CPU計(jì)算友好的程序，比如通過(guò)減少上下依賴、減少分支、預(yù)取數(shù)據(jù)到緩存等方式，讓CPU集中于計(jì)算任務(wù)；最后，還可以通過(guò)SIMD來(lái)對(duì)計(jì)算密集型的簡(jiǎn)單程序進(jìn)行改造，加速計(jì)算效率。

1.2 向量化計(jì)算

顧名思義，向量化計(jì)算就是按照向量的方式計(jì)算，也就是一次計(jì)算多對(duì)操作數(shù)。

按照實(shí)現(xiàn)方式的不同，向量化主要分為以下三種類型：

·自動(dòng)向量化。編譯器可以識(shí)別出循環(huán)內(nèi)哪些操作可以寫成向量化執(zhí)行的方式，但要求必須是簡(jiǎn)單的循環(huán)，不能包含條件、跳轉(zhuǎn)等語(yǔ)句，不能包含前后依賴關(guān)系，硬件也必須要支持SIMD指令。

·添加編譯器提示。通過(guò)使用一些關(guān)鍵字或者預(yù)編譯指令，強(qiáng)制進(jìn)行向量化。

·顯式向量化。通過(guò)CPU提供的SIMD指令集來(lái)手工編寫向量化執(zhí)行的代碼。

三種方式中，第一種是最為簡(jiǎn)單也是應(yīng)用最廣泛的方式，只需要遵循一定的代碼編寫規(guī)則即可，不會(huì)影響原來(lái)代碼的邏輯性和可讀性，性能加速效果也不錯(cuò)。而另外兩種方式對(duì)編程人員的要求很高，需要結(jié)合編譯器和硬件能力來(lái)做深度優(yōu)化。

1.3 列存儲(chǔ)

這里再次介紹一下列存儲(chǔ)，因?yàn)榱写鎯?chǔ)跟向量化密切相關(guān)，向量化計(jì)算就是基于列存儲(chǔ)來(lái)構(gòu)建。

我們先來(lái)了解下數(shù)據(jù)庫(kù)存儲(chǔ)。數(shù)據(jù)庫(kù)存儲(chǔ)主要分為兩類：行存儲(chǔ)和列存儲(chǔ)。

行存儲(chǔ)中，每一行的元組的每一列實(shí)際上是連續(xù)存儲(chǔ)的，這樣的優(yōu)點(diǎn)是易于添加或者修改一個(gè)元組，但在讀取數(shù)據(jù)時(shí)可能會(huì)額外讀到不需要的列，比較適合于包含大量高并發(fā)增刪改查事務(wù)的OLTP場(chǎng)景。

列存儲(chǔ)中，每一列是單獨(dú)存儲(chǔ)的，這樣就可以只讀取需要的列，但缺點(diǎn)是元組的寫入需要操作多個(gè)文件，比較適合于包含大數(shù)據(jù)量讀取和復(fù)雜計(jì)算的OLAP場(chǎng)景。

采用列存儲(chǔ)的好處有很多。除了上面提到的數(shù)據(jù)裁剪能力之外，列存儲(chǔ)還可以通過(guò)壓縮算法帶來(lái)更高的壓縮比，也可以通過(guò)字典里列排序或者稀疏索引加速數(shù)據(jù)的查找效率。另外，這種列式的存儲(chǔ)組織形式還為上層計(jì)算的性能優(yōu)化提供了很大的便利，特別是在向量化查詢和延遲物化等方面。

1.4 向量化查詢執(zhí)行引擎

這部分主要介紹的是，如何結(jié)合前面提到的向量化和列存儲(chǔ)技術(shù)，來(lái)對(duì)查詢執(zhí)行引擎進(jìn)行向量化加速計(jì)算。

傳統(tǒng)查詢執(zhí)行引擎采用火山模型，按照一次處理一個(gè)元組的方式，邏輯非常簡(jiǎn)單，便于開(kāi)發(fā)實(shí)現(xiàn)，但是效率比較低，主要原因有以下三點(diǎn)：

首先，CPU把大部分時(shí)間都花在遍歷查詢操作樹(shù)上，而不是在真正處理數(shù)據(jù)。一次處理一個(gè)Tuple的處理速度可能非?？?，但是處理完之后就需要調(diào)用下層算子獲取下一個(gè)tuple，這就導(dǎo)致函數(shù)調(diào)用的次數(shù)比較多，這樣就進(jìn)而會(huì)浪費(fèi)掉CPU的很多時(shí)間。其次，數(shù)據(jù)和指令的緩存命中率低。頻繁的函數(shù)調(diào)用導(dǎo)致寄存器需要保存更多的信息，而且實(shí)現(xiàn)時(shí)可能會(huì)為了通用性的考慮，對(duì)接口進(jìn)行封裝，這就會(huì)導(dǎo)致復(fù)雜度的提升，執(zhí)行越復(fù)雜就會(huì)導(dǎo)致緩存利用率越低。最后，這種傳統(tǒng)的方式無(wú)法利用新硬件提供的SIMD能力進(jìn)行進(jìn)一步優(yōu)化。

與之相比，向量化查詢執(zhí)行引擎仍然采用火山模型，但是按照一次處理一組元組的方式，實(shí)現(xiàn)批量讀取和批量處理，大大減少了函數(shù)調(diào)用開(kāi)銷，CPU可以把更多的時(shí)間集中到實(shí)際的計(jì)算上，效率會(huì)更高。

按照向量化計(jì)算的方式，對(duì)一組數(shù)據(jù)做簡(jiǎn)單的循環(huán)計(jì)算，同時(shí)數(shù)據(jù)按照列組織形式表示成列向量，每個(gè)列向量對(duì)應(yīng)的一整塊連續(xù)數(shù)據(jù)，進(jìn)而可以批量讀入緩存以及進(jìn)行批量處理，這就可以大大提高指令、數(shù)據(jù)的緩存命中率，進(jìn)而提高CPU的執(zhí)行效率。

以上圖中的例子為例。這是一個(gè)帶where子句的聚合運(yùn)算語(yǔ)句，左邊是行存儲(chǔ)非向量化查詢執(zhí)行過(guò)程，右邊是列存儲(chǔ)向量化查詢執(zhí)行過(guò)程?；诹写鎯?chǔ)，我們只需要獲取id和agg列的數(shù)據(jù)。基于向量化查詢執(zhí)行引擎，每層算子獲取的都是表示成列向量的一組元組，并對(duì)每個(gè)列向量進(jìn)行批量計(jì)算。

1.5 向量化執(zhí)行實(shí)例

下面通過(guò)一個(gè)聚合計(jì)算的例子來(lái)進(jìn)一步介紹向量化執(zhí)行的具體步驟。

這個(gè)例子使用兩個(gè)列進(jìn)行分組，并對(duì)每個(gè)組內(nèi)進(jìn)行count(*)計(jì)算。整個(gè)流程包含兩個(gè)步驟：一是構(gòu)建hash table并在每個(gè)hash entry上計(jì)算聚合結(jié)果；二是遍歷hash table，計(jì)算最終的聚合結(jié)果。

向量化改造之后，一些具體步驟可以通過(guò)簡(jiǎn)單的循環(huán)來(lái)進(jìn)行批量處理。

首先，根據(jù)輸入的向量在分組列上批量計(jì)算Hash值；其次，根據(jù)上一步計(jì)算的Hash值批量獲取Hash bucket值；然后，批量處理輸入向量?jī)?nèi)的每個(gè)元組，在Hash table內(nèi)查找匹配的Hash entry或者創(chuàng)建新的Hash entry，如果發(fā)生哈希沖突，按照Open addressing的處理方式，繼續(xù)對(duì)下一個(gè)位置進(jìn)行匹配處理；接著根據(jù)上一步獲取的對(duì)應(yīng)每個(gè)輸入向量的Hash entry，批量計(jì)算Agg結(jié)果并更新到對(duì)應(yīng)的Hash entry上（count++）；最后，掃描Hash table的每一個(gè)Hash entry，計(jì)算最終的Agg結(jié)果（count計(jì)算不需要此步驟），將結(jié)果組織成向量形式返回給上層算子。

1.6 向量化執(zhí)行效果

接下來(lái)看一下向量化執(zhí)行的效果。下面給出了一些測(cè)試用例，主要包含多種不同類型的Agg和Join場(chǎng)景，涵蓋了定長(zhǎng)和變長(zhǎng)列。

藍(lán)色是行存，橙色是原列存，灰色是列存向量化。測(cè)試了1G/10G/100G的結(jié)果，可以看出列存向量化的執(zhí)行時(shí)間最短。數(shù)據(jù)量越大，原列存和列存向量化效果越明顯。最好的情況下，列存向量化運(yùn)行時(shí)間是原列存的1/2，列存向量化運(yùn)行時(shí)間是行存的1/8。

1.7 下一步計(jì)劃

最后介紹關(guān)于向量化的下一步計(jì)劃，主要有以下四方面：

·Just-in-Time編譯優(yōu)化。對(duì)函數(shù)調(diào)用進(jìn)行展開(kāi)，減少函數(shù)調(diào)用，比較適合于復(fù)雜的表達(dá)式或者算子計(jì)算。

·SIMD指令加速。適合于簡(jiǎn)單的線性計(jì)算，可以利用現(xiàn)代CPU的SSE、AVX指令讓一條指令實(shí)現(xiàn)512bit數(shù)據(jù)計(jì)算。

·Hash Agg/Hash Join等算法進(jìn)一步向量化優(yōu)化。

·列存掃描等存儲(chǔ)相關(guān)部分進(jìn)一步優(yōu)化。

二、TDSQL-A與CK的對(duì)比

2.1 CK介紹

CK是目前社區(qū)里面比較熱門的，應(yīng)用場(chǎng)景也比較廣泛。

首先，在架構(gòu)上，集群內(nèi)劃分為多個(gè)分片，通過(guò)分片的線性擴(kuò)展能力，支持海量數(shù)據(jù)的分布式存儲(chǔ)計(jì)算，每個(gè)分片內(nèi)包含一定數(shù)量的節(jié)點(diǎn)Node，即進(jìn)程，Node之間互為副本，通過(guò)ZooKeeper進(jìn)行數(shù)據(jù)同步。

其次，CK的數(shù)據(jù)模型主要使用MergeTree表引擎——一種LSM Tree的實(shí)現(xiàn)，同時(shí)支持分布式表，寫入時(shí)進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)，讀取時(shí)進(jìn)行數(shù)據(jù)收集。

再者，在存儲(chǔ)上，CK采用了列存、分區(qū)、數(shù)據(jù)排序和分塊、主鍵索引等方式。最后，在計(jì)算上，CK采用向量化執(zhí)行方式，利用SIMD指令加速。

2.2 存儲(chǔ)引擎

在存儲(chǔ)引擎上來(lái)看，TDSQL-A和CK各有自己鮮明的特點(diǎn)。

TDSQL-A采用的是典型的列存設(shè)計(jì)，功能完備，包括完整的事務(wù)能力，同時(shí)還設(shè)計(jì)一些特殊的優(yōu)化來(lái)加速數(shù)據(jù)讀寫操作。

2.3 SQL引擎

在SQL引擎上，TDSQL-A繼承了PG原生的SQL能力，SQL完備且兼容性好，支持多表關(guān)聯(lián)、存儲(chǔ)過(guò)程等復(fù)雜查詢，另外TDSQL-A在分布式架構(gòu)上對(duì)優(yōu)化器和執(zhí)行器具有很多優(yōu)化。我們也在分布式架構(gòu)上做了一些并發(fā)器和執(zhí)行器的優(yōu)化，左圖實(shí)際上就是分布式的一個(gè)重要例子。

CK也具有出色的向量化執(zhí)行引擎，特別是在AGG計(jì)算中，針對(duì)不同數(shù)據(jù)類型設(shè)計(jì)不同的數(shù)據(jù)結(jié)構(gòu)和算法，將CPU和內(nèi)存能力發(fā)揮到極致。右圖中列了一下針對(duì)于Hash AGG計(jì)算設(shè)計(jì)的不同數(shù)據(jù)結(jié)構(gòu)。

2.4 對(duì)比

整體來(lái)看，TDSQL-A相比于CK，在SQL能力、事務(wù)能力、優(yōu)化器能力、分布式管控能力以及高可用能力上具有優(yōu)勢(shì)，而CK則在計(jì)算引擎執(zhí)行效率上表現(xiàn)突出。

TDSQL-A受惠于PG社區(qū)的長(zhǎng)期積累，同時(shí)經(jīng)過(guò)我們團(tuán)隊(duì)長(zhǎng)時(shí)間的功能增強(qiáng)、性能優(yōu)化以及在多個(gè)應(yīng)用領(lǐng)域的實(shí)踐，已經(jīng)具備了全面和強(qiáng)大的能力，可以提供企業(yè)級(jí)一站式解決方案，可以把事務(wù)、高可用以及部分業(yè)務(wù)邏輯放到數(shù)據(jù)庫(kù)中來(lái)處理，大大降低業(yè)務(wù)的復(fù)雜程度。我們也將繼續(xù)與PG社區(qū)、CK社區(qū)等優(yōu)秀開(kāi)源社區(qū)保持緊密聯(lián)系，吸收改進(jìn)新的發(fā)展技術(shù)和研究成果，不斷地提高TDSQL-A的能力并開(kāi)放給我們的用戶。