雲原生數倉如何破解大規模叢集的關聯查詢效能問題?

語言: CN / TW / HK

作者 | 宇毅

前言

近年來,資料庫系統服務的資料量呈指數級增長,同時也面臨處理的業務需求愈發複雜、實時性要求越來越高等挑戰。單機資料庫系統已經逐漸不能滿足現代的資料庫服務要求,因此分散式資料庫/資料倉庫得到了越來越廣泛地運用。

在實時分析(OLAP)領域,分散式資料倉庫可以充分發揮系統的分散式特點,將複雜的OLAP任務分解下發到系統中的所有節點進行計算提升分析效能;分散式資料倉庫也可以比較方便地對系統節點進行擴容,應對使用者業務資料量增加的需求。但是分散式資料倉庫使用者無法避免的一個問題是:隨著資料倉庫叢集規模增大,擴容帶來的價效比愈發降低。

造成這種現象的一個原因是,表連線(Join)作為資料庫業務中最廣泛使用的運算元之一,在分散式計算中依賴系統節點間的資料互動;當分散式叢集規模增大時,節點之間的資料互動代價會明顯增加,這種情況下非常考驗分散式系統的網路處理能力,並依賴使用者的資料表設計和SQL編寫能力以緩解資料互動壓力。

針對這個問題,業界不同的分散式資料庫系統提出了不同的Join執行時過濾(Runtime Filter)演算法。AnalyticDB for PostgreSQL(以下簡稱ADB PG)是一款PB級的MPP架構雲原生資料倉庫,同樣也面臨著上述問題的挑戰。本文從ADB PG架構設計的角度出發,探討Runtime Filter在ADB PG中的實現方案,並介紹了基於Bloom Filter的ADB PG Dynamic Join Filter功能技術細節。

ADB PG架構簡介

ADB PG基於開源專案Greenplum構建,在單機PostgreSQL的基礎上進行擴充套件,將多個PG服務同時啟動在單個或多個伺服器上並組成叢集,以分散式的形式提供資料庫服務。ADB PG將每一個PG服務稱為一個Segment,並引入了Slice的概念。Slice用於解決分散式系統中的網路結構,當資料庫涉及到MPP多階段計算時,例如Hash Join左右表的Join Key不滿足相同的Hash分佈,那麼就需要對Join Key通過網路傳輸進行重分佈,ADB PG將網路傳輸的前後階段切分為不同的Slices。以下是一個ADB PG叢集示意圖。

在這種架構下如何解決大規模叢集下表連線Join的效能問題呢?業界解決這個問題的一個方案是引入網路代理節點,同一機器內的Segment將網路資料傳送至本地代理節點,由代理節點與其它機器上的代理節點進行網路收發工作以減少網路擁塞。該方案對ADB PG架構的挑戰較大,且沒有從根本上減少Join的網路Shuffle開銷。因此為了從Join根源上減少Join計算的資料量,ADB PG設計並實現了Join Runtime Filter方案。

Runtime Filter和Bloom Filter

Runtime FIlter的目的是在Join計算前篩選掉一部分資料,需要一個Filter的實現“載體”。在結合ADB PG的架構設計、儲存層和網路層的特點後,我們選擇使用Bloom Filter作為Runtime Filter的實現形式。

Bloom Filter是一種概率資料結構,通常被用於判斷一個元素是否屬於一個集合。Bloom Filter的優點是其空間效率非常高,計算效能通常也高;缺點是存在陽性誤判率false positive,但是不存在false negative,即Bloom Filter判斷一個元素是否屬於集合的結果不是單純的true or false,而是"possible true" or "false"。

上圖是一個標準Bloom Filter的計算思路示意圖,其中的0、1為Bloom Filter用於表示集合資訊的bit array,即每一位用一個bit儲存。上方x,y,z表示向Bloom Filter中插入的三個元素,分別使用3種hash演算法計算hash值後在bit array中置位。而下方為判斷元素w是否屬於集合,由於3個hash值中的某一位沒有在bit array中被置位,可以肯定的是w不屬於集合。

Bloom Filter通常由以下幾個引數描述:

  • m --- Bloom Filter bit array的大小m bits
  • k --- 使用的hash函式個數k
  • p --- 誤判率
  • n --- Bloom Filter插入的元素個數

我們省略推導過程,直接將各個引數的關係給出:

當Bloom Filter足夠大時,可以簡化為:

在設計Bloom Filter時,n和m我們可以根據實際計算場景提前確定,上述公式可以視為自變數為k,應變數為p的函式p(k),此函式通常在k > 0時通常不是單調的(由n:m確定)。因此Bloom Filter在設計時要考慮如何確定hash函式k的個數以獲得最小的誤判率p。根據上式可以計算得到當p為極小值時,對應k的值為:

Bloom Filter的引數設計:

如何將Bloom Filter應用至ADB PG Join過濾優化,我們首先要設計選擇Bloom Filter的引數。對於Bloom Filter插入元素的個數n,可以直接使用執行計劃中獲得的Join右表計劃行數;而為了獲得理想的過濾率,減少誤判率p,ADB PG使用了PG高版本Bloom Filter的思路,設計Bloom FIlter大小Bytes為n的2倍,即總體n:m達到1:16。在這個設計下,可以計算得到最佳的k取值為11,p(k)函式如下圖所示,當k = 11時可以取得最小的p = 0.046%

k = 11意味著對於每一個元素,都需要計算11個hash值以插入到Bloom Filter bit array中,這對於ADB PG是無法接受的,構建Bloom Filter的代價明顯過大。在構建Bloom Filter時,ADB PG會綜合誤判率、hash計算等因素考慮,選擇合適的k值。

在確定構建Bloom Filter的基本原則後,接下來就是工程實現問題。Bloom Filter的工程實現非常簡單高效,通常我們可以直接使用bitset陣列來建立Bloom Filter,通過位操作實現Bloom Filter的插入和查詢。下圖為向一個Bloom Filter bitset陣列中插入元素的計算示意圖。

Dynamic Join Filter in ADB PG

在完成ADB PG Hash Join的Bloom Filter設計後,接來下討論如何將Bloom Filter應用至Join的Runtime Filter中。ADB PG將基於Bloom Filter的Runtime Filter命名為Dynamic Join Filter。

1.Dynamic Join Filter的實現方式

由於ADB PG優化器通常會選擇將右表作為小表,左表作為大表,因此ADB PG將Dynamic Join Filter的設計特點為單向過濾的,即僅用於右表過濾左表,暫不考慮左表過濾右表的形式;同時我們也可以將Dynamic Join Filter靈活應用於Hash Join左錶鏈路不同運算元的過濾中。

由於Hash Join的形式不同,Dynamic Join Filter的實現形式可以總結為Local Join和MPP Join兩種形式,並根據Runtime Filter是否具有下推運算元的能力做進一步區分。

Local Join

Local Join是指左右表的Join Key均滿足相同Hash分佈,無需再Shuffle資料。此時Hash、Hash Join和左表Scan處於同一個Slice內部,即同一個程序中,我們可以直接在程序空間內將Bloom Filter傳遞給左表Scan運算元過濾輸出。

MPP Join

MPP Join是指左右表的Join Key均不滿足相同Hash分佈,需要針對Join Key Shuffle資料。在前文介紹過,ADB PG的Hash Join和Hash運算元一定處於同一個Slice內部,因此基於基本原則只需要考慮左表Shuffle的情況,即左表在Hash Join前存在Motion的場景。

MPP Join存在的另一種情況是,左表Motion下不是簡單的Scan,也沒有關聯資訊將Join Key的Bloom Filter下推至Scan。那麼以減少網路傳輸資料量為最後準則,將Bloom Filter過濾放在Motion前,減少Motion Sender的資料。

2.Bloom Filter網路傳輸

Dynamic Join Filter在各個計算節點上建立了一個Local Bloom Filter,每個計算節點需要收集所有其它節點的Bloom Filter,並在本地組成完整的Bloom Filter後才能開始過濾計算。我們將Bloom Filter的收發分為兩種模式:全量傳輸和位傳輸。在傳送前我們可以判斷兩種模式的資料量大小,並自適應選擇資料量小的模式。

Bloom Filter全量傳輸

Bloom Filter位傳輸

效能測試

接下來我們對ADB PG Dynamic Join Filter的效能表現測試。測試叢集為ADB PG公有云搭建的例項,測試使用TPC-H 1TB測試集(scale = 10000),測試通過開啟\關閉Dynamic Join Filter功能對比執行效能。下圖展示了TPC-H執行效能有差異的Query測試結果:

可以看到Dynamic Join Filter在Q5、Q8、Q9和Q17上均獲得了較大的效能提升,其中Q17的優化效能最佳,執行時間137s優化至8s。而Q10存在略微的效能回退:10s回退至12s,原因在於Q10的Join Key是完全匹配的,Dynamic Join Filter無法做到動態提前過濾,而優化器未能準確估算代價導致計劃仍然使用了Dynamic Join Filter。此外Q20也因為優化器下推規則的的原因沒有選擇Dynamic Join Filter,實際上經過分析Q20與Q17類似,比較適合使用Dynamic Join Filter。為了解決這些問題,ADB PG優化器相關功能仍在開發迭代中。

總結&未來規劃

Dynamic Join Filter根據ADB PG架構設計、儲存層和網路層特點,使用Bloom Filter作為Join Runtime Filter的實現形式,在TPC-H測試中取得了明顯的效能提升成果。未來我們將從以下幾個方面做進一步的開發和優化,提升客戶使用體驗:

完善Dynamic Join Filter功能,支援各種模式的Hash Join,並進一步推廣到Merge Sort Join、NestedLoop Join的優化中;

提升優化器的代價估算模型精度,完善優化器下推規則;

Runtime Filter自適應排程。

歡迎訪問雲原生資料倉庫ADB PG主頁,瞭解更多:http://help.aliyun.com/product/35364.html