活动回顾|Apache Doris 向量化技术实现与后续规划
引言
Doris 向量化設計與實現
01????什么是向量化
向量化是指計算從一次對一個值進行運算轉換為一次對一組值進行運算的過程, 從不同的角度來分析,我將拆分成兩個方面來探討或思考這個問題。 從CPU的角度 現代 CPU 支持將單個指令應用于多個數據(SIMD)的向量運算。例如,具有 128 位寄存器的 CP U可以保存 4 個 32 位數并進行一次計算,比一次執行一條指令快 4 倍。
比如我們在內存當中有 4 個 32 位的 int ,進行計算時傳統的 CPU 沒有 SIMD,或者說沒有向量化支持的 CPU 要進行四次從內存中 Load 數據,再進行 4 次乘法計算,然后把結果寫回到內存當中同樣要進行 4 次。假如我們能夠支持 SIMD ,我們可以一次載入多個連續的內存數據,這樣我們就只有一次數據的 Load ,一次的計算,然后得到 4 個結果寫到 4 個寄存器里面,然后這 4 個寄存器再寫回到內存當中,就完成了一次向量化的指令計算操作。這樣的操作能夠比傳統的CPU快 4 倍。 隨著 CPU 的發展,現在大家常用的都是 128 位的 SSE 的指令,后面又多了 256 位的 AVX 指令,以及英特爾現在最新的 AVX512 的指令。隨著寄存器的位數不斷變長,我們一次向量化運算的一組值可以變得越來越多,它的效率會越來越高。但這不一定是線性的關系,不一定隨著寄存機的位數呈線性的性能增長,但是能夠保證一次對一組值的操作是更多更快的。 這是在CPU角度,我們去看向量化這個問題。
從數據庫的角度
從數據庫角度也是計算從一次對一個值進行運算轉換為一次對一組值進行運算的過程。-
數據庫執行引擎:
1. 將 Next Tuple ,變成 Next Batch 。
2. 內存中 Batch 的數據不是以行的形式存在,而是以列的形式存在,算子都是在列上進行運算。
在數據庫執行引擎的角度與 CPU 的角度也是類似,傳統的數據庫執行引擎都是一行一行處理數據的。我們可以看下面這個圖。
所以內存當中的數據不再以行的形式來存在,而是以列的形式存在,所有的計算都通過列的方式進行連續的計算。我們可以看右邊這張圖,比如我們有一個數據掃描的操作,原本按照左邊這張圖,一行做一個判斷對一組值要判斷 4 次,現在對一個列進行數據的判斷。所以在數據庫的角度同樣也是對一個值的運算轉化成對一組值的運算。
02????Doris?如何實現向量化
接下來介紹 Apache Doris 如何實現向量化,這也是我們目前正在做的工作。實現向量化核心工作主要分為這三塊:-
列式存儲: 在 Doris 的執行引擎中引入基于列存的存儲格式。在執行引擎當中, Doris 現在存儲層的數據是以列存儲的,但是在執行引擎當中我們還是基于行的方式來做運算的。我們前面看到那張圖是基于 Tuple 運算的,每次只能運算一個值,所以我們要把它替換為一個列式存儲的執行引擎,這樣我們才能夠實現向量化。
-
向量化函數計算框架 : 基于列式存儲重新設計一套向量化/列式計算引擎。在列式存儲的基礎上,我們要實現一套向量化的函數計算框架。基于現有的新的列式存儲格式,重新設計一套向量化列式存儲的計算引擎。
-
向量化算子 : 基于前兩者,重新組織SQL算子。基于列式存儲和向量化的函數計算框架,我們要實現所有的向量化算子,這一塊工程量其實是比較大的。
1.列式存儲
改變了計算引擎對數據的組織方式,由行存的 Tuple 與 RowBatch 變為了 Column 與 Block原先 Doris 在執行引擎當中的數據內存結構是左邊的 RowBatch 結構,數據通過一個一個 Tuple 進行組織的,每一個 Tuple 是個連續的內存。我們可以看到左邊 RowBatch 的結構分為三個列,但它每一個行是一個連續的內存結構,在組織內部處理當中也是一行一行處理的。 右邊是我們新的結構 Block ,我們可以看到它的數據是按列來進行組織的,每一個列是一個連續的內存結構。 2.向量化的函數計算框架 這里我簡單舉一個例子
select a,abs(b) from test;
但是我們可以看下邊列存的執行邏輯,相對行存的執行邏輯更簡潔。首先在整個 ?Block 的執行過程中只有一次類型判斷,我們可以看到假如 RawBatch 或者 ?Block 有 1024 行,原行存執行結構對于類型的判斷要走 1024 次,但對于列存來說只要一次就可以了,減少了大量類型判斷。另外,從代碼上可能不容易看出來其實每一次處理時列存是連續的,我們對連續的一段內存做處理, Cache 親和度更高。 03????向量化計算優點 相對于舊的行存計算框架,列式的函數計算框架有以下優勢:
-
Cache 更親和,列式計算由于數據是按列組織的,所以更容易命中 Cache 。 比如剛才的例子中,運算 abs(b)?時沒有相關的列是不會參與到計算過程當中來的。列式計算由于數據在列上連續,所以更容易命中我們需要計算的 Cache ,從 Cache 中讀取數據和內存中讀取數據,性能有 10 倍至 100 倍的差距。
-
減少虛函數的調用,減少分支跳轉,降低 CPU 分支預測判斷失敗概率。 從兩段代碼能明顯看到減少很多類型的判斷,在向量化框架當中大量運用模板的方式做零成本的抽象減少虛函數調用。關于虛函數調用會有什么開銷、引起什么問題,我們在后面會再詳細討論。
- 函數計算的 SIMD ,包含編譯器自動 SIMD 與手動 Coding 的 SIMD指令集。 這一部分對應一開始單獨提到的「從CPU角度去看向量化」,原先一次只能算一個值,現在向量化計算框架中一次可以計算多個值,這樣就會有數倍的性能提升。
這邊我列了下面這個表格。
2.虛函數調用的開銷。 虛函數帶來的開銷主要是下面兩點: 2.1 ?虛函數的動態調用是無法進行函數內聯的,這會大大減少編譯器可能進行的優化空間。 虛函數實際調用時需要查表,編譯器無法知道當時動態狀態下需要調用什么樣的函數 ,所以沒有辦法進行內聯。我們知道函數內聯真正意義就是給編譯器更多的優化空間,這與數據庫當中的優化器是類似的,給更多的信息才能做更好的優化。編譯器的角度也是同樣的道理,但因為虛函數沒有辦法進行函數內聯,所以編譯器獲取的信息就會大大減少,這樣編譯器代碼優化空間就會減少。 2.2 ?虛函數查表帶來額外的分支跳轉的開銷,分支預測失敗會導致CPU流水線重新執行。
分支跳轉在 CPU 當中是有一定開銷的。下面這張圖是 Pipeline 的執行流程,分為 Fetch , Decode , Executed , Write-back,這四個 Stage 。現在的 CPU 還要比這個復雜很多。
一旦 CPU 進入一個跳轉流程當中,原則上來講 Pipeline 是要暫停下來的,因為跳轉指令是依賴前一個指令執行結果,完成后我們才能確定要執行什么指令。但是現在 CPU 進行分支預測不會讓流水線空轉。分支預測一旦成功的話,已經順著流水線執行下去的指令能夠得到很好的收益,但一旦分支預測失敗會導致 CPU 流水線重新執行,這也會帶來極大的性能開銷 。 對于分支預測,給大家舉個小例子,大家可以實際去用代碼去實踐一下。 假如我有個 vector 存儲的指針對象有虛函數調用,我們是把不同的對象交替地放在這個
vector 當中,還是把這個 vector 基于對象類型做一次排序之后調用,哪個執行效率更高,大家可以實際寫代碼去驗證一下。有意思的是他們實現的匯編都是一模一樣,但是后者更快,這就是分支預測失敗帶來的一個影響。
3.函數執行如何 SIMD 3.1 Auto?vectorized 自動向量化,也就是編譯器自動去分析 for 循環是否能夠向量化。GCC 開啟的 -O3 優化便會開啟自動向量化。 自動向量化 tips : (1)足夠簡單的 for 循環。
(2)足夠簡單的代碼,避免:函數調用,分支跳動。
(3)規避數據依賴,即避免下一個計算結果依賴上一個循環的計算結果。
(4)連續的內存和對齊的內存。SIMD 指令本身對于內存要求是比較多的。首先前面我們講到了 CPU 是連續載入多個數據的,數據在不連續的內存上沒有辦法一次做連續的載入。第二是內存對齊會影響向量化指令的執行效率。GCC 的文檔上給了一個比較完整的 case ,講到如何寫代碼編譯器能夠做自動的向量化,大家有興趣的話可以參考 GCC 的文檔 CASE:
https://gcc.gnu.org/projects/tree-ssa/vectorization.html
如何確認代碼編譯器的自動向量化生效了呢? (1)編譯器的 Hint 提示。 -fopt-info-vec-all:打印所有編譯器進行向量化的信息,如果循環代碼被向量化了,會打印如下信息 main.cpp:5: note: LOOP VECTORIZED. -fopt-info-vec-missed:沒有被向量化的原因 -fdump-tree-vect-all:進一步分析沒有被向量化的原因 大家可以把 Hint ?提示打開,打開后就能在編譯的過程中看到編譯器的提示,如果循環代碼被向量化了,編譯器會打印對應的信息。LOOP VECTORIZED 告訴你這個循環被向量化。如果是沒有被向量化的話可以打印 ?vec-missed 的 Hint ,它會告訴你為什么函數沒有被向量化,但通常只會提供一個簡單的原因。如果要更深入分析的話,可以用最下面我給大家的 Hint 進一步分析為什么沒有被向量化。大家可以實際寫代碼去實踐一下。 (2)直接通過 perf/objdump 查看生成的匯編代碼。 在一個大型程序上一個一個看 for 循環的話比較困難,我們可以把編譯出來的產出通過 perf 或 objdump 直接查看生成的匯編代碼,就可以看到有沒有向量化了。我這邊截了一張圖:
Doris?向量化的當前情況
01????SQL 算子
在 0.15 版本我們發布了一個單表的向量化執行引擎,能夠滿足大寬表的向量化查詢需求,實現向量化的 SQL 算子包括 Sort,Agg,Scan,Union。當前 Doris 的數據存儲是基于列式存儲,在數據進來之后的一些計算過程是基于行存來進行的,在 ScanNode 上轉成列式存儲,基于列式存儲實現了這4種向量化的算子執行向量化的計算。02????如何開啟向量化
1.設置環境變量?set enable_vectorized_engine = true;(必須) 我們可以看到這張圖,設置后的執行計劃會帶一個v,這其實跟匯編指令生成 ?SIMD 指令集是相似的,代表開啟向量化。
2.設置環境變量set batch_size = 4096; (推薦)
我們在實際的測試當中測試下來,?推薦設置 batch_size 為 4096 ,或者說在向量化當中應該講? Block 實測下來設置為 4096 行性能是最好的。當然這里僅作推薦,不調整的話性能也還是不錯的。
03????向量化的單表性能
這是 0.15 版本我們在單表上做的一些測試,與原來行存做了一個對比。 Q1:select count(*) FROM lineorder_flat; Q2:select min(lo_revenue) as min_revenue from lineorder_flat group by c_nation; Q3:select count(distinct lo_commitdate), count(distinct lo_discount) from lineorder_flat;可以看到性能提升的效果還是比較可觀的。這是在 0.15 版本我們實測的向量化的性能,后續的版本性能會更激動人心,值得大家期待!
Doris?向量化的未來規劃
接下來是向量化的未來規劃,包括功能的完善與發布,以及關于后續版本的想法,這部分我想也是大家最關心的。01????SQL 算子
Join 算子是 Doris 最為核心的算子,絕大多數場景使用 Doris 其實也是看中 Doris 本身在 MPP 場景下的多表? Join 能力,所以 Join 開發也是我們向量化開發當中的重中之重。
可以告訴大家我們已經實現了 Join 的向量化,只是還沒有做系統的調優。這是我們基于 SSB測試集的 Join 向量化性能情況,這是第一版大家可以簡單看一下,在 SSB 測試集當中 Join 性能基本有 30% 至 40% 甚至 1 倍的提升。 剩下一些 SQL 算子,除了 Join 之外大家可能還會用到的:交集,差集, cross Join,ODBC/MySQL Scan Node,窗口函數(WIP),ES Scan Node(WIP)?,這些算子其實都是當前 Doris 行存支持的SQL算子,除了部分算子還在開發中,基本都已經全部 Ready,現在還在做一些穩定性和性能調優工作。
02? ? 存儲層向量化
前面講到目前 Doris 的數據是基于列存儲在磁盤上。但我們讀下來之后要對這個數據做聚合,這個過程是通過行存來表示的。這部分因為歷史原因存在了很多冗余低效的代碼,目前我們在實際的向量化開發中發現已經嚴重影響了整個向量化代碼的執行邏輯與性能。主要是如下幾個問題: 1.計算表達式受限制。 很多計算表達式因為內存結構不同、接口不同沒有辦法作用于存儲層,導致表達式沒有辦法下推,以及無法做向量化的計算。 2.額外的轉換的性能開銷比較嚴重, 嚴重影響到導入和查詢性能。我們實際做了一個 POC 的測試,在 DupKey 表上通過完整的向量化改造性能還能有10倍級別的提升。 3.代碼可維護性降低。 因為結構不同,所以目前Doris 在執行引擎實現的聚合算子沒有辦法作用于存儲引擎。同樣的聚合代碼要在存儲層和查詢層,也就是存儲引擎和查詢引擎分別實現,代碼可維護性就很差。另外在查詢層進行性能優化沒有辦法作用在存儲層下,性能優化需要考慮兩部分,所以也帶來了一些問題。我們目前在做的一個很重要的工作就是把 Doris存儲層通過行存做去重聚合的邏輯進行向量化。
03? ? 導入向量化
?前 Doris 進行數據導入時存在 Tuple 轉 RowCursor ,數據行式聚合等一系列有冗余開銷的工作。而我們后續希望通過導入向量化的開發實現:
- 減少額外內存格式的轉換開銷,提高 CPU 的利用率
- 復用計算層的算子,減少冗余低效的代碼,簡潔 Doris 現有的代碼結構
- 利用 SIMD 加快導入過程當中的聚合計算,進一步提升 Doris 導入性能
目前向量化版本實現了一個簡單的導入框架。Block 計算完成之后是以列組織的,通過向量化的計算引擎做格式的轉化,但最終在發送數據時,由于接收端還沒有做向量化改造,所以我們現在還是基于 RowBatch 的數據格式進行數據發送。下一步我們要規劃的工作就是把通過 Tuple 轉 Rowcursor 進行運算這部分全部剔除掉,轉換成向量化的格式或者說列存的格式進行運算。
04? ??SQL函數
1.函數豐富度支持 前面講到了目前 Doris 已有的函數是比較豐富的,但是因為向量化是基于列存實現的,函數接口包括調用的方式都有所不同,所以我們不單單要實現 SQL 算子,還要實現浩如煙海的 SQL 函數。目前我們已經實現了向量化支持的函數大概有 200 多個,其他還在不斷的開發過程當中,需要盡快補齊原先行存支持但是向量化還沒有支持的函數。這部分工作也歡迎大家參與進來。2.函數的 SIMD 化
我們保證在列存上能夠利用前面提到的幾個優勢使分支跳轉變少,Cache 親和度更高。但目前很多實現向量化的函數沒有考慮 SIMD 化。尤其對于熱點的核心函數,我們后續規劃盡量通過各種可能的方式進行 SIMD 化,包括我們前面提到手寫 SIMD 。我自己在開發過程當中手寫了一些 SIMD 的函數。目前在 Apache 的 Master 庫也能看到我自己手寫的一些在字符串實現的SIMD 的函數。3.向量化的 UDF 的框架設計和實現。
UDF 也是大家經常用到一個功能,向量化上需要重新設計一個 UDF 框架,這也是我們后續要做的。
05? ??代碼重構
1.基礎類型的重構 。目前 Doris 向量化上所有的數據類型都能夠支持,但是有這幾個問題:-
Data / Datatime:更小的內存占用,對 SIMD 更友好的內存布局。 Doris 現在的 Data 和 DataTime 類型復用了行存,毫秒的數據其實在現在的 Doris 當中沒有在用了。 現在 Data 和 DataTime 占用 16 字節,而毫秒就占了 8 字節,這八字節完全沒有用到,額外占用了很大的內存。 這部分內存占用在原來函數當中還不明顯,但在向量化當中8個字節的占用就會帶來很大的內存開銷,對 SIMD 不友好。 另外目前 Data / DataTime 內存布局還有待優化,在做 SIMD 時會有各種各樣的問題。 所以我們準備重構 Data / DataTime,實現在向量化版本有更小的內存占用,對 SIMD 更友好的內存布局。
-
Decimal:根據精度切換內存占用,解決 Doris 中當前精度浪費的問題。 當前的Doris在精度上沒有根據實際用戶設置的精度切換內存占用,統一占用 16 字節的內存,造成很大一部分開銷。 我們準備對 Decimal 的這一問題進行重構。
- HLL:減少 HLL 類型無效的序列化的開銷。 目 前我們已經把 Bitmap 重構完成,用了一個新的結構表示 Bitmap ,減少了大量的序列化開銷,整體性能表現也很不錯。 減少 HLL 在計算時無效的序列化開銷就是下個階段我們要做的事情。
寫在最后
01? ? 感謝 Clickhouse 社區 Doris 在進行向量化代碼開發時,在列存模型和函數框架上引用了部分 Clickhouse 19.16.2.2 版本的代碼,我們在引用代碼的 License 上注明了相應的工作,同時與 Clickhouse 社區進行了對應的溝通。十分感謝 Clickhouse 在 Doris 向量化代碼開發上給予的幫助。
02?? ?版本發布 如果順利的話 1 月底或 2 月初我們就會帶來下一版的向量化執行引擎了,前面所提到的很多后續規劃內容將在下一版本中落地。希望大家屆時多多試用捧場~
—— End ——
歡迎關注:
Apache Doris(incubating)官方公眾號
社區人物志|魏祚:道阻且長,行則將至,做有溫度的開源項目
從NoSQL到Lakehouse,Apache Doris的13年技術演進之路
相關鏈接:
Apache Doris官方網站:
http://doris.incubator.apache.org
Apache?Doris?Githu b:
https://github.com/apache/incubator-doris
Apache Doris 開發者郵件組:
dev@doris.apache.org
本文分享自微信公眾號 - ApacheDoris(gh_80d448709a68)。
如有侵權,請聯系 support@oschina.cn 刪除。
本文參與“ OSC源創計劃 ”,歡迎正在閱讀的你也加入,一起分享。
總結
以上是生活随笔為你收集整理的活动回顾|Apache Doris 向量化技术实现与后续规划的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 王阳明《没有秘密的你》开播 超A男神化身
- 下一篇: 【8583】ISO8583各域段的说明