揭秘TDSQL-A分布式執(zhí)行框架：解放OLAP關(guān)聯(lián)分析查詢性能瓶頸

在“國產(chǎn)數(shù)據(jù)庫硬核技術(shù)沙龍-TDSQL-A技術(shù)揭秘”系列分享中，5位騰訊云技術(shù)大咖分別從整體技術(shù)架構(gòu)、列式存儲(chǔ)及相關(guān)執(zhí)行優(yōu)化、集群數(shù)據(jù)交互總線、分布式執(zhí)行框架設(shè)計(jì)及優(yōu)化策略、以及向量化執(zhí)行引擎等多方面對(duì)TDSQL-A進(jìn)行了深入解讀。

本期帶來了系列分享中騰訊云數(shù)據(jù)庫高級(jí)工程師張倩老師主題為“TDSQL-A分布式執(zhí)行框架設(shè)計(jì)及優(yōu)化策略”的分享的文字版。沒有聽直播的小伙伴，可要認(rèn)真做筆記啦！

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

一、執(zhí)行框架總體設(shè)計(jì)

1.1 TDSQL-A架構(gòu)

首先介紹TDSQL-A的總體架構(gòu)，包括上層的協(xié)調(diào)節(jié)點(diǎn)CN、GTM事務(wù)管理器、中間的數(shù)據(jù)交互總線FN、以及下方的數(shù)據(jù)節(jié)點(diǎn)DN。主要介紹的是協(xié)調(diào)節(jié)點(diǎn)CN和數(shù)據(jù)節(jié)點(diǎn)DN的相關(guān)內(nèi)容，包括用戶的查詢怎么在CN和DN上執(zhí)行、最后如何返回結(jié)果給用戶等問題。

TDSQL-A采用MPP架構(gòu)，其特性是share-nothing，數(shù)據(jù)分散在多個(gè)DN上，按照不同的分布鍵分布，并且不同的表可以自定義不同的分布鍵。如果CN收到了一條查詢，它會(huì)將這個(gè)任務(wù)分散到多個(gè)DN上并行執(zhí)行，從而提高執(zhí)行效率，最后CN獲得DN并行執(zhí)行的最后結(jié)果，匯總之后再返回給客戶端。

1.2 原分布式執(zhí)行框架

這里先說明一下我們的原分布式執(zhí)行框架一個(gè)最主要的問題。下圖是一個(gè)簡單的Join查詢，如果Join查詢正好是在這個(gè)表的分布鍵上進(jìn)行Join，則不涉及數(shù)據(jù)的重分布，可以直接在每個(gè)DN節(jié)點(diǎn)上進(jìn)行Join，DN的結(jié)果匯總起來就是最終的查詢結(jié)果，這是最理想的情況。

但客戶的查詢往往比較復(fù)雜多樣，Join經(jīng)常會(huì)涉及不同節(jié)點(diǎn)之間的數(shù)據(jù)交換，Join的兩個(gè)表的Join鍵不一定是一個(gè)表的分布鍵，這種情況下就會(huì)涉及到數(shù)據(jù)的重分布。在TDSQL-A中，數(shù)據(jù)重分布是由Remote Subplan算子來執(zhí)行。在執(zhí)行的時(shí)候，Remote Subplan算子會(huì)并行地創(chuàng)建對(duì)應(yīng)下層的執(zhí)行進(jìn)程和對(duì)應(yīng)的DN連接，每個(gè)DN都會(huì)創(chuàng)建對(duì)應(yīng)其他DN的各個(gè)鏈接，這就會(huì)導(dǎo)致鏈接數(shù)和進(jìn)程數(shù)急劇膨脹，給服務(wù)器造成很大的壓力。

1.3 TDSQL-A分布式執(zhí)行框架

針對(duì)原分布式架構(gòu)的缺點(diǎn)，我們設(shè)計(jì)了一套全新的分布式執(zhí)行框架。在這種執(zhí)行框架下，查詢執(zhí)行前CN會(huì)對(duì)查詢計(jì)劃進(jìn)行分片，并創(chuàng)建DN上的各個(gè)執(zhí)行進(jìn)程，每個(gè)DN的進(jìn)程間不需要再建立冗余的進(jìn)程及連接。這可以減少不必要的進(jìn)程和連接，減輕服務(wù)器的負(fù)擔(dān)，并且能夠做到比較好的線性擴(kuò)展性。數(shù)據(jù)交互則是通過中間的router——FN節(jié)點(diǎn)來進(jìn)行數(shù)據(jù)交換，這是當(dāng)前TDSQL-A的分布式執(zhí)行框架。

二、查詢計(jì)劃分片策略

2.1 查詢計(jì)劃分片過程

之所以要對(duì)查詢計(jì)劃進(jìn)行分片，主要是因?yàn)橐粋€(gè)分布式的查詢計(jì)劃，在絕大多數(shù)情況下，必然會(huì)包含數(shù)據(jù)的重分布。在我們的執(zhí)行框架中，根據(jù)數(shù)據(jù)重分布進(jìn)行查詢計(jì)劃的劃分。

首先包括數(shù)據(jù)重分布的代價(jià)在內(nèi)，優(yōu)化器會(huì)生成一個(gè)代價(jià)估算最優(yōu)的執(zhí)行計(jì)劃。在這個(gè)執(zhí)行計(jì)劃上，我們會(huì)做計(jì)劃樹的劃分分片——把每一個(gè)數(shù)據(jù)重分布的節(jié)點(diǎn)下面的子數(shù)作為一個(gè)計(jì)劃的分片，再通過FID來對(duì)每一個(gè)計(jì)劃分片進(jìn)行管理。

以下圖為例，假設(shè)有一個(gè)兩層的Hash Join，每一層涉及到一些對(duì)應(yīng)的數(shù)據(jù)重分布，就會(huì)有一個(gè)四分片的查詢的產(chǎn)生。

2.2 Agg算子執(zhí)行計(jì)劃

在分布式數(shù)據(jù)庫里面，對(duì)其他的算子，也會(huì)生成一個(gè)分布式的執(zhí)行計(jì)劃，比如OLAP場景里面經(jīng)常使用的執(zhí)行聚合計(jì)算的Agg算子。在聚合計(jì)算中，比如group id正好是表的分布鍵的情況下，可以生成單獨(dú)的分片，就像下圖中FID 1這樣的分片。每個(gè)Agg操作都是在DN本地執(zhí)行，最后匯總到CN上得到一個(gè)最終結(jié)果。但是在有些情況下，比如聚合鍵不是分布鍵的情況下，就會(huì)在最下層的節(jié)點(diǎn)上做部分的聚合操作，在上層的節(jié)點(diǎn)經(jīng)過數(shù)據(jù)重分布之后再做最后的聚合操作，得到最終結(jié)果。這就是一個(gè)分布式的Agg算子的執(zhí)行計(jì)劃。

2.3 Sort算子&Limit算子執(zhí)行計(jì)劃

Sort算子還有Limit算子也是同樣的邏輯。

對(duì)于Sort算子，我們會(huì)在DN本地先做一次排序，經(jīng)過數(shù)據(jù)重分布后，在上層節(jié)點(diǎn)再進(jìn)行歸并，最后得到最終的排序結(jié)果。

對(duì)于Limit算子，我們會(huì)把它進(jìn)行下推。比如說下面這個(gè)例子中，這條搜索語句是查詢前100名的test order，這樣的話我們會(huì)把Limit算子進(jìn)行下推，每個(gè)DN只返回Limit 100條數(shù)據(jù)給上層節(jié)點(diǎn)，上層節(jié)點(diǎn)在收到結(jié)果之后再進(jìn)行合并排序，最后取Limit 100的結(jié)果作為最終結(jié)果返回給上層。

三、異步執(zhí)行流程控制

3.1 異步執(zhí)行具體流程

在生成查詢計(jì)劃的分片后，CN會(huì)下發(fā)每個(gè)分片對(duì)應(yīng)的執(zhí)行計(jì)劃片段，分別發(fā)送給各個(gè)DN，然后每個(gè)分片在每個(gè)執(zhí)行節(jié)點(diǎn)上會(huì)創(chuàng)建一個(gè)進(jìn)程，執(zhí)行對(duì)應(yīng)的執(zhí)行計(jì)劃。不同層級(jí)的進(jìn)程異步啟動(dòng)執(zhí)行，通過FN進(jìn)行數(shù)據(jù)交互。

下圖中可以看到，這里有兩個(gè)查詢，分別是簡單的Join查詢，以及數(shù)據(jù)重分布的Join查詢。如果是傳統(tǒng)的數(shù)據(jù)庫執(zhí)行流程，就會(huì)先啟動(dòng)下層節(jié)點(diǎn)，再啟動(dòng)上層節(jié)點(diǎn)。但在我們設(shè)計(jì)的這種執(zhí)行框架下，F(xiàn)ID 1和FID 2是同步啟動(dòng)的，它們之間通過FN來進(jìn)行數(shù)據(jù)交互。

如果在有兩個(gè)數(shù)據(jù)節(jié)點(diǎn)的情況下，Join查詢怎么啟動(dòng)執(zhí)行進(jìn)程呢？因?yàn)橛袃蓚€(gè)分片，還有兩個(gè)數(shù)據(jù)節(jié)點(diǎn)，所以在執(zhí)行的過程中，有四個(gè)進(jìn)程在同時(shí)執(zhí)行。

最下面的這兩個(gè)分片，都屬于FID 2，但分別在DN 1和DN 2上執(zhí)行，執(zhí)行對(duì)應(yīng)的計(jì)劃分片。對(duì)其中一個(gè)表進(jìn)行掃描，再通過FN節(jié)點(diǎn)進(jìn)行數(shù)據(jù)交換。上面的這兩個(gè)分片都屬于FID 1，分別在DN 1和DN 2上執(zhí)行，它們分別獲取自己所需要的數(shù)據(jù)，同時(shí)執(zhí)行自己的執(zhí)行計(jì)劃分片。最終，兩個(gè)FID 1的執(zhí)行進(jìn)程會(huì)把最終結(jié)果發(fā)送給CN。這四個(gè)進(jìn)程是同步執(zhí)行的，在數(shù)據(jù)交換的時(shí)候通過FN來進(jìn)行。

3.2 自適應(yīng)流程控制

TDSQL-A執(zhí)行框架最大的難點(diǎn)就在于進(jìn)程間如何進(jìn)行協(xié)調(diào)和控制。針對(duì)這個(gè)問題，我們設(shè)計(jì)了一個(gè)具有自適應(yīng)特點(diǎn)的異步執(zhí)行的流程控制機(jī)制。它主要有以下三個(gè)方面的特點(diǎn)：

·靈活控制執(zhí)行進(jìn)度。根據(jù)實(shí)際執(zhí)行情況，DN動(dòng)態(tài)地控制各個(gè)進(jìn)程之間的執(zhí)行進(jìn)度。

·根據(jù)前端設(shè)置按需執(zhí)行，優(yōu)化資源利用，快速響應(yīng)異常。比如前端發(fā)送Cancel請求時(shí)，能夠及時(shí)響應(yīng)處理。如果任何執(zhí)行進(jìn)程發(fā)生異常，也能夠快速響應(yīng)處理。

·保證分布式事務(wù)一致性。涉及修改操作的分片會(huì)開啟事務(wù)，并且同步執(zhí)行這個(gè)事務(wù)的提交或者回滾等操作。

下面我將分別從這三個(gè)方面來介紹一下這個(gè)異步執(zhí)行流程控制機(jī)制。

在各個(gè)進(jìn)程同步執(zhí)行的情況下，如果有的進(jìn)程出現(xiàn)執(zhí)行阻塞的情況，該怎樣互相協(xié)調(diào)呢？

以下圖為例，假設(shè)上層節(jié)點(diǎn)中的FID 1的這兩個(gè)執(zhí)行進(jìn)程執(zhí)行比較慢，而下層FID 2的這兩個(gè)進(jìn)程執(zhí)行進(jìn)度比較快的時(shí)候，下層FID 2的兩個(gè)進(jìn)程會(huì)源源不斷地向上層發(fā)送它們的執(zhí)行結(jié)果。如果不加控制的話，不僅會(huì)浪費(fèi)下層FID 2的執(zhí)行資源，而且會(huì)造成網(wǎng)絡(luò)的阻塞。

針對(duì)這種情況，我們設(shè)計(jì)了進(jìn)程間可以互相協(xié)調(diào)執(zhí)行進(jìn)度的控制機(jī)制，主要通過數(shù)據(jù)流控制來實(shí)現(xiàn)。如果上層節(jié)點(diǎn)的執(zhí)行進(jìn)度慢于預(yù)期的時(shí)候，下層節(jié)點(diǎn)會(huì)進(jìn)行等待，等到上層節(jié)點(diǎn)能夠繼續(xù)執(zhí)行時(shí)，下層節(jié)點(diǎn)才會(huì)繼續(xù)做自己計(jì)劃分片的執(zhí)行，把數(shù)據(jù)發(fā)送給上層節(jié)點(diǎn)。這樣可以在執(zhí)行節(jié)點(diǎn)上達(dá)到資源分配和使用較優(yōu)的效果，空出來的網(wǎng)絡(luò)資源和CPU/IO資源就可以讓渡給其他查詢來執(zhí)行。

我們的控制機(jī)制中除了數(shù)據(jù)流之外，還有控制流。由CN來監(jiān)聽并統(tǒng)一處理控制流消息。DN節(jié)點(diǎn)的執(zhí)行進(jìn)程，又叫Dprocess，在執(zhí)行的過程中會(huì)隨時(shí)響應(yīng)控制消息。以下圖為例，如果用戶執(zhí)行一個(gè)比較長的進(jìn)程或者誤執(zhí)行了一個(gè)Query，在執(zhí)行幾分鐘后，不想再執(zhí)行了，就會(huì)給CN發(fā)送一個(gè)Cancel信號(hào)取消查詢，這時(shí)CN會(huì)把這個(gè)信號(hào)通過鏈接發(fā)送給每個(gè)執(zhí)行進(jìn)程，DN上的執(zhí)行進(jìn)程收到信號(hào)后就會(huì)終止執(zhí)行，及時(shí)把資源讓渡出來給其他的查詢使用。這是Cancel消息的處理過程。

除了Cancel消息外，我們還處理Error信息。在執(zhí)行進(jìn)程同步執(zhí)行的過程中，每個(gè)執(zhí)行進(jìn)程之間通過FN來進(jìn)行數(shù)據(jù)交換。如果其中一個(gè)進(jìn)程發(fā)生Error，比如在處理的過程中資源不足，或者在處理過程中遇到數(shù)據(jù)錯(cuò)誤或其他錯(cuò)誤等，這時(shí)它會(huì)報(bào)Error信號(hào)，通過鏈接將這個(gè)信號(hào)上報(bào)給CN。CN在收到執(zhí)行進(jìn)程Error消息后，會(huì)進(jìn)行消息處理，然后下發(fā)給其他的執(zhí)行進(jìn)程，讓它們終止執(zhí)行。也就是說，如果任何一個(gè)并行執(zhí)行的進(jìn)程發(fā)生了錯(cuò)誤，我們也能夠及時(shí)取消、結(jié)束這個(gè)查詢。

3.3 執(zhí)行流程示例

下圖是一個(gè)總體執(zhí)行流程的示例。左側(cè)是一個(gè)帶有數(shù)據(jù)重分布的Join查詢，它的整體執(zhí)行流程可以用右邊的這個(gè)圖來表示。四個(gè)執(zhí)行進(jìn)程之間會(huì)有數(shù)據(jù)交換，是通過FN來交換數(shù)據(jù)流，最終結(jié)果也是通過FN數(shù)據(jù)流返還給CN，CN上還有一個(gè)后臺(tái)線程，通過控制流控制各個(gè)執(zhí)行進(jìn)程之間的執(zhí)行，這就是整體的執(zhí)行構(gòu)架。

除了查詢語句外，我們還會(huì)遇到DML語句。DML語句即Insert、Update、Delete語句，它們需要進(jìn)行分布式執(zhí)行事務(wù)的提交或者回滾操作。在執(zhí)行過程中，我們主要是把修改操作集中在一個(gè)分片內(nèi)，然后在執(zhí)行修改操作的這個(gè)分片內(nèi)進(jìn)行事務(wù)的開啟、提交和回滾等操作。這個(gè)事務(wù)的命令同樣也是通過控制線程來進(jìn)行發(fā)送，其他線程也同樣是通過Cancel或者上報(bào)Error來處理控制消息。

這里舉一個(gè)最典型的例子。執(zhí)行Insert into語句時(shí)，如果后面跟的是Select From，也就是在其他的表中經(jīng)過查詢操作獲得一個(gè)結(jié)果集，把這個(gè)結(jié)果集插入到一個(gè)表中，此時(shí)我們在其他分片上執(zhí)行只讀操作，只在第一個(gè)包含Insert的分片上執(zhí)行修改操作，這個(gè)修改操作就涉及事務(wù)的提交和回滾。

3.4 中止處理流程

這里重點(diǎn)介紹中止處理流程，它和Cancel流程不一樣。中止處理流程是CN在獲取了部分的查詢結(jié)果集后中止執(zhí)行。典型的應(yīng)用場景是把查詢結(jié)果做分頁展示。在很多前端的應(yīng)用中，查詢結(jié)果就是用分頁展示的形式展現(xiàn)在客戶端頁面上的。

比如一個(gè)查詢，第一頁可能有1000條查詢結(jié)果，下一頁則是下1000條查詢結(jié)果。CN在查詢執(zhí)行的時(shí)候，只要執(zhí)行獲取到1000條結(jié)果，就可以返回給前端，讓前端做展示或者處理。因?yàn)榍岸顺绦蛱幚聿樵兘Y(jié)果也需要時(shí)間，在這時(shí)，后端就可以繼續(xù)執(zhí)行獲取下1000條查詢結(jié)果，這樣就能實(shí)現(xiàn)前端和后端并行執(zhí)行，取得執(zhí)行效率整體最優(yōu)化。

在這種執(zhí)行流程下，CN會(huì)先獲取前1000條結(jié)果——該數(shù)值用戶可以自由設(shè)置，在獲取到指定結(jié)果集之后CN先返回給前端，前端處理完之后，如果需要再獲取，CN就會(huì)繼續(xù)返回下一批結(jié)果。

如果前端查詢?nèi)∠?，比如用戶可能?頁或者6頁之后不想再看，或者是前端應(yīng)用處理到第幾批數(shù)據(jù)之后不再處理直接返回，在這樣的情況下，查詢其實(shí)不需要再繼續(xù)執(zhí)行，這時(shí)CN會(huì)下發(fā)一個(gè)End query信號(hào)，然后在并行執(zhí)行流程上也會(huì)及時(shí)響應(yīng)這個(gè)信號(hào)來結(jié)束查詢。下圖就是簡單的展示。

左下角是分頁場景下的執(zhí)行性能對(duì)比。最左邊的這個(gè)柱子顯示的是，如果這個(gè)查詢在正常執(zhí)行情況下，在返回第一條結(jié)果的時(shí)候所需要的時(shí)間，第二個(gè)柱子是如果設(shè)置了fetch size是1000條時(shí)，它所需要執(zhí)行的時(shí)間。如果沒有設(shè)置fetch size，在傳統(tǒng)的執(zhí)行方式下，這個(gè)查詢的執(zhí)行時(shí)間是非常長的，但如果我們先設(shè)置返回1000條結(jié)果，這個(gè)查詢時(shí)間可以大幅縮小。同時(shí)在繼續(xù)執(zhí)行的時(shí)候，后續(xù)的每一批的查詢結(jié)果的執(zhí)行時(shí)間幾乎可以忽略不計(jì)。因?yàn)榍岸嗽诮邮懿樵儠r(shí)，我們后端也在同時(shí)處理繼續(xù)獲取查詢結(jié)果。

四、子查詢執(zhí)行優(yōu)化

在OLAP場景下一些比較典型的包含有子查詢的執(zhí)行優(yōu)化。OLAP子查詢基本上可以分為兩類：一類是非相關(guān)的子查詢，一類是相關(guān)的子查詢。

4.1 非相關(guān)子查詢執(zhí)行

非相關(guān)的子查詢，指的是子查詢的結(jié)果集是一個(gè)固定的值，跟外層的查詢沒有關(guān)聯(lián)。對(duì)非相關(guān)子查詢，我們設(shè)計(jì)了“異步執(zhí)行、一次執(zhí)行”的機(jī)制。子查詢對(duì)我們的執(zhí)行框架來說，是另外的一個(gè)分片，它跟父查詢可以并行執(zhí)行。當(dāng)父查詢需要子查詢的結(jié)果時(shí)，子查詢已經(jīng)執(zhí)行完畢了，父查詢可以直接獲取結(jié)果繼續(xù)執(zhí)行。

下圖中，F(xiàn)ID 3分片就是代表子查詢的執(zhí)行分片。Hash Join在執(zhí)行過程中，每個(gè)分片都是并行執(zhí)行的，在FID 2做掃描的時(shí)候，如果它不需要子查詢的結(jié)果，就可以不用等待FID 3的執(zhí)行結(jié)果。當(dāng)它需要子查詢的執(zhí)行結(jié)果時(shí)，因?yàn)镕ID 3和FID 2是并行執(zhí)行，就可以直接獲取到這個(gè)結(jié)果并使用。這是非相關(guān)子查詢的執(zhí)行。

4.2 相關(guān)子查詢執(zhí)行

更為復(fù)雜的是相關(guān)子查詢的執(zhí)行。在執(zhí)行過程中，相關(guān)子查詢的執(zhí)行結(jié)果是跟父查詢的傳遞條件是有關(guān)系的。

以下圖為例，在order 1和order 2的pid是相等的情況下，查詢會(huì)從order 2這個(gè)表中取出最大的tax值。這個(gè)tax的值再和外層的order 1的tax值做等值比較，最后獲取等值比較成立的那個(gè)結(jié)果，作為最終的查詢結(jié)果。

相關(guān)子查詢的執(zhí)行，一般情況是由父分片傳遞參數(shù)到子分片上，子分片會(huì)設(shè)置這個(gè)參數(shù)值，然后返回查詢結(jié)果。比如FID 2先做一個(gè)scan的操作，它在要獲取子查詢的值時(shí)，會(huì)先把order 1的pid先通過fragment之間的連接傳遞給FID 3，F(xiàn)ID 3在取得并設(shè)置了order 1的pid值后，執(zhí)行它本身的執(zhí)行計(jì)劃，最后獲取的結(jié)果再傳遞給FID 2，然后FID 2獲取結(jié)果后再繼續(xù)進(jìn)行計(jì)算，可以看到這是一個(gè)非并行的執(zhí)行。之所以這樣，主要是因?yàn)樽硬樵僃ID 3的每一條執(zhí)行結(jié)果其實(shí)是和FID 2下發(fā)的參數(shù)值是有關(guān)的。因此它們倆不能并行執(zhí)行，這樣的子查詢執(zhí)行效率就比較低。

針對(duì)這種情況，我們做了相關(guān)子查詢的優(yōu)化，會(huì)在計(jì)劃生成階段由優(yōu)化器自動(dòng)改寫查詢計(jì)劃。在很多應(yīng)用中，查詢語句可能是由前端應(yīng)用自動(dòng)生成的，并且數(shù)量很大，如果都用人工來進(jìn)行優(yōu)化改寫，工作量會(huì)非常大。在這種情況下，我們在優(yōu)化器中實(shí)現(xiàn)了一套基于代數(shù)變換規(guī)則的自動(dòng)改寫，會(huì)把相關(guān)子查詢，根據(jù)一定的規(guī)則改寫成等價(jià)的Join查詢，之后再進(jìn)行其他優(yōu)化，生成最后的查詢計(jì)劃。

經(jīng)過優(yōu)化后，相關(guān)子查詢的性能提升非常明顯。下面這個(gè)圖就是在子查詢改寫之后，它的優(yōu)化性能對(duì)比?？梢钥吹剑绻凑赵瓉淼膱?zhí)行方式，每個(gè)子查詢每一次設(shè)置參數(shù)之后都需要執(zhí)行一次，整個(gè)查詢的執(zhí)行時(shí)間非常長。如果改寫成等價(jià)的Join查詢之后，它的執(zhí)行效率非常高。