StarRocks 技術內幕：向量化程式設計精髓

 作者：康凱森，StarRocks PMC，負責查詢方向的研發

本文是對我在 StarRocks 線下 MeetUp 演講的整理，主要分為三部分：第一部分簡要介紹向量化的基礎知識，第二部分講解資料庫如何進行向量化，最後是 StarRocks 向量化實踐後的一些粗淺思考。

 

#01

向量化為什麼可以提升資料庫效能？

—

本文所討論的資料庫都是基於 CPU 架構的，資料庫向量化一般指的都是基於 CPU 的向量化，因此資料庫效能優化的本質在於：一個基於 CPU 的程式如何進行效能優化。這引出了兩個關鍵問題：

1. 如何衡量 CPU 效能

2. 哪些因素會影響 CPU 效能

第一個問題的答案可以用以下公式總結：CPU Time = Instruction Number * CPI * Clock Cycle Time

• Instruction Number 表示指令數。當你寫一個 CPU 程式，最終執行時都會變成 CPU 指令，指令條數一般取決於程式複雜度。

• CPI 是 （Cycle Per Instruction）的縮寫，指執行一個指令需要的週期。

• Clock Cycle Time 指一個 CPU 週期需要的時間，是和 CPU 硬體特性強關聯的。

我們在軟體層面可以改變的是前兩項：Instruction Number 和 CPI。那麼問題來了，具體到一個 CPU 程式，到底哪些因素會影響 Instruction Number 和 CPI 呢？

我們知道 CPU 的指令執行分為如下 5 步：

1. 取指令

2. 指令譯碼

3. 執行指令

4. 記憶體訪問

5. 結果寫回暫存器

其中 CPU 的 Frontend 負責前兩部分，Backend 負責後面三部分。基於此，Intel 提出了 《Top-down Microarchitecture Analysis Method》的 CPU 微架構效能分析方法，如下圖所示：

​

 

Top-down Microarchitecture Analysis Method 的具體內容大家可以參考相關的論文，本文不做展開，為了便於大家理解，我們可以將上圖簡化為下圖（不完全準確）：

​

 

即影響一個 CPU 程式的效能瓶頸主要有4大點：Retiring、Bad Speculation、Frontend Bound 和 Backend Bound，4個瓶頸點導致的主要原因（不完全準確）依次是：缺乏 SIMD 指令優化，分支預測錯誤，指令 Cache Miss， 資料 Cache Miss。

再對應到之前的 CPU 時間計算公式，我們就可以得出如下結論：

​

 

而資料庫向量化對以上 4 點都會有提升，後文會有具體解釋，至此，本文從原理上解釋了為什麼向量化可以提升資料庫效能。

 

#02

向量化基礎知識

—

在瞭解資料庫如何向量化之前，我們先理解一些向量化的基礎知識。

注意，在第二個章節裡面，向量化一詞可以理解為和 SIMD 等價，僅指狹義上的 CPU SIMD 向量化，與資料庫領域廣義的向量化含義不同。

 

1、SIMD 簡介

SIMD 是 Single Instruction Multiple Data 的縮寫，指單個指令可以操作多個數據流，與之相對的是傳統的 SISD，單指令單資料流。

​

如上圖所示，對於最簡單的 A + B = C，假如我們要計算 4 組加法，傳統的 SISD 需要執行 8 次 Load 指令 (A 和 B 分別4次)、4 次 Add 指令、4 次 Store 指令。但當我們使用 128 位寬的 SIMD， 我們只需要 2 次 Load 指令、1 次 Add 指令、1 次 Store 指令，這樣理論上就可以獲得 4 倍的效能提升。而目前的向量化暫存器位寬已經發展到 512 位，理論上 Int 的加法操作就可以加速 16 倍。

 

2、如何觸發向量化？

如前文所述，SIMD 指令會帶來巨大的效能提升，資料庫開發人員自然需要理解並掌握如何進行 SIMD 程式設計。

​

如上圖所示，SIMD 觸發向量化一般有 6 種方式，這 6 種方式自頂向下，對工程師的要求越來越高，需要手動編寫的東西越來越多。 

• 第一種是編譯器自動向量化，程式碼不需要做特殊處理和改動，編譯自動將預設的標量程式碼轉換成向量化程式碼。但編譯器預設只能處理比較簡單的程式，具體支援的 Case 大家可以在網上搜索，資料很多；

• 第二種是我們給編譯器一些 Hint，給編譯器更多的資訊和上下文，編譯器也可以生成 SIMD 指令；

• 第三種是使用像 OpenMP 或者 Intel Cilk 這種並行程式設計 API，開發者可以加一些 Pragma 來生成 SIMD 指令；

• 第四種是使用一些 SIMD Intrinsics 的包裝類；

• 第五種是直接使用 SIMD Intrinsics 程式設計；

• 最後一種是直接寫彙編程式碼。

在 StarRocks 專案中，我們向量化的原則是儘可能觸發編譯器的自動向量化，也就是第一種和第二種，對於不能自動向量化但是效能又很關鍵的操作，我們會通過 SIMD Intrinsics 的方式手動向量化。

關於如何觸發編譯器的自動化，如何給編譯器加 Hint 觸發向量化以及如何通過 SIMD Intrinsics 的方式手動向量化大家可以參考我個人部落格《資料庫學習資料》向量化部分的資料，本文不再贅述。

《資料庫學習資料》：https://blog.bcmeng.com/post/database-learning.html

 

3、如何驗證程式生成了向量化程式碼？

當一個專案程式碼比較複雜時，如何確保程式碼觸發向量化是很常見的問題。 我們可以通過兩種方式來檢查：

第一種是給編譯器加一些編譯選項，編譯器會輸出某些程式碼是否觸發向量化，以及沒有向量化的原因。比如 GCC 編譯器，我們可以加入 -fopt-info-vec-all 或者 -fopt-info-vec-optimized，-fopt-info-vec-missed，-fopt-info-vec-note 編譯選項。效果如下圖所示：

​

第二種方法，我們可以直接檢視最終執行的彙編程式碼，比如使用 https://gcc.godbolt.org/ 等網站或者 Perf、Vtune 等工具，如果彙編程式碼裡面的暫存器是 xmm,ymm,zmm 或者指令以 v 開頭，一般就說明程式碼觸發了向量化。

 

#03

資料庫向量化

—

 

1、資料庫向量化的核心

StarRocks 的向量化引擎從寫下第一行程式碼到成為一款成熟、穩定、世界領先的查詢執行器，已經有 2 年多的時間，以我們的經驗來看，資料庫的向量化並不僅僅是觸發 CPU 的 SIMD 向量化，而是一個巨大的、系統化的效能優化工程。

 

2、資料庫向量化的挑戰

資料庫向量化的挑戰主要有以下幾點：

1. 全面的列式佈局：在磁碟，記憶體，網路中全部都是列式佈局，這意味儲存引擎和計算引擎的完全重構

2. 所有運算元、表示式和函式支援向量化：這意味數人年的工作

3. 運算元和表示式計算儘可能使用 SIMD 指令：這意味著大量 Case By Case 的細緻優化

4. 重新設計記憶體管理：因為處理的資料從一行變成了數千行

5. 重新設計資料結構：比如 Join、Aggregate、Sort 等核心運算元的資料結構都需要進行改變

6. 整體效能提升 5 倍以上：所有的運算元和表示式效能都要提升 5 倍以上，意味著全面地、系統地效能優化，所有重要的運算元和表示式效能都不能有短板

 

3、運算元和表示式向量化的關鍵點

資料庫的向量化在工程上主要體現在運算元和表示式的向量化，而運算元和表示式的向量化的關鍵點就一句話：Batch Compute By Column, 如下圖所示：

​

 

對應 Intel 的 Top-down 分析方法，Batch 優化了 分支預測錯誤和指令 Cache Miss，By Column 優化了 資料 Cache Miss，並更容易觸發 SIMD 指令優化。

Batch 這一點其實比較好做到，難點是對一些重要運算元，比如 Join、Aggregate、Sort、Shuffle 等，如何做到按列處理，更難的是在按列處理的同時，如何儘可能觸發 SIMD 指令的優化。每個運算元的按列處理和 SIMD 指令優化我們會在之後的 《StarRocks 查詢原始碼解析》系列文章中詳細解釋。

 

4、資料庫向量化如何進行效能優化

前面提到，資料庫向量化是一個巨大的、系統的效能優化工程，兩年來，我們實現了數百個大大小小的優化點。我將 StarRocks 向量化兩年多的效能優化經驗總結為 7 個方面 （注意，由於向量化執行是單執行緒執行策略，所以下面的效能優化經驗不涉及併發相關）：

1. 高效能第三方庫：在一些區域性或者細節的地方，已經存在大量效能出色的開源庫，這時候，我們可能沒必要從頭實現一些演算法或者資料結構，使用高效能第三方庫可以加速我們整個專案的進度。在 StarRcoks 中，我們使用了 Parallel Hashmap、Fmt、SIMD Json 和 Hyper Scan 等優秀的第三方庫。

2. 資料結構和演算法：高效的資料結構和演算法可以直接在數量級上減少 CPU 指令數。在 StarRocks 2.0 中，我們引入了低基數全域性字典，可以通過全域性字典將字串的相關操作轉變成整形的相關操作。如下圖所示，StarRcoks 將之前基於兩個字串的 Group By 變成了基於一個整形的 Group By，這樣 Scan、Hash 計算、Equal、Memcpy 等操作都會有數倍的效能提升，整個查詢最終會有 3 倍的效能提升。

​

 

3. 自適應優化：很多時候，如果我們擁有更多的上下文或者更多的資訊，我們就可以做出更多針對性的優化，但是這些上下文或者資訊有時只能在查詢執行時才可以獲取，所以我們必須在查詢執行時根據上下文資訊動態調整執行策略，這就是所謂的自適應優化。下圖展示了一個根據選擇率動態選擇 Join Runtime Filter 的例子，有 3 個關鍵點： 

  a. 如果一個 Filter 幾乎不能過濾資料，我們就不選擇；

  b. 如果一個 Filter 幾乎可以把資料過濾完，我們就只保留一個 Filter; 

  c. 最多隻保留 3 個有用的 Filter

​

 

4. SIMD 優化：如下圖所示，StarRcoks 在運算元和表示式中大量使用了 SIMD 指令提升效能。

​

 

5. C++ Low Level 優化：即使是相同的資料結構、相同的演算法，C++ 的不同實現，效能也可能相差好幾倍，比如 Move 變成了 Copy，Vector 是否 Reserve，是否 Inline， 迴圈相關的各種優化，編譯時計算等等。

6. 記憶體管理優化：當 Batch Size 越大、併發越高，記憶體申請和釋放越頻繁，記憶體管理對效能的影響越大。我們實現了一個 Column Pool，用來複用 Column 的記憶體，顯著優化了整體的查詢效能。下圖是一個 HLL 聚合函式記憶體優化的程式碼示意，通過將 HLL 的記憶體分配變成按 Block 分配，並實現複用，將 HLL 的聚合效能直接提升了 5 倍。

​

 

7. CPU Cache 優化：做效能優化的同學都應該對下圖的資料了熟於心，清楚 CPU Cache Miss 對效能的影響是十分巨大的，尤其是我們啟用了 SIMD 優化之後，程式的瓶頸就從 CPU Bound 變成了 Memory Bound。同時我們也應該清楚，隨便程式的不斷優化，程式的效能瓶頸會不斷轉移。

​

 

下面的程式碼展示了我們利用 Prefetch 優化 Cache Miss 的示例，我們需要知道，Prefetch 應該是最後一項優化 CPU Cache 的嘗試手段，因為 Prefetch 的時機和距離比較難把握，需要充分測試。

​

 

#04

StarRocks 向量化工程的粗淺思考

—

其一，很多事物的底層原理是相似的：當我深入瞭解到 CPU 的微架構後，發現 CPU 的微架構和資料庫的整體架構也很類似，比如 CPU 和 StarRocks 都分 Frontend 和 Backend， CPU 的 Frontend 負責指令的取碼和編解碼，Backend 負責指令的執行和資料的互動， StarRocks的 Frontend 負責 SQL 的 Parse 和 Plan， Backend 負責 SQL 的執行和儲存的互動。當你瞭解的系統、架構越多，你的這種感受會越深刻。

其二，打造一個高效能的資料庫，需要的不僅是優秀合理的架構，還需要極致優秀的工程細節。這一點看似十分顯然，其實並不是，如果你認可這一點，當你想打造一個極致效能的資料庫時，你就不會像 ClickHouse 一樣 Bottom-Up 地從細節和演算法層面出發去設計整個系統，也不會選擇 Java 或者 Go 等語言去實現查詢執行層和儲存層。

​

 

其三，向量化和查詢編譯的融合。我們知道，向量化和查詢編譯是查詢執行的兩大類方式，是正交的，並不衝突，只是目前業界大多數開源的資料庫選擇了向量化的做法，其實我們完全可以通過查詢編譯的方式，結合上下文資訊，生成更強大的向量化程式碼。而且，近幾年查詢編譯的本身諸多缺點業界也一直在改進。

其四，嘗試 GPU、FPGA 等新硬體。我們知道，假如一件事情，做到 80 分，需要一個月的時間，那麼從 80 分做到 90 分，可能就需要 1 年的時間，從 90 分做到 99 分，可能就需要 2 年的時間。雖然目前基於 CPU 架構下的效能還沒到極限，但是取得大的突破可能需要比較大的精力，我們或許可以考慮在新的硬體開闢新的賽道和戰場。

其五，挑戰不可能。創業兩年來，我們團隊從零實現了向量化引擎、CBO 優化器、Pipeline 並行引擎……看著一個又一個突破和成績，我最大的一個感受就是我們應該永遠堅信自己，挑戰不可能。最後我向大家推薦一本書 《像火箭科學家一樣思考:將不可能變為可能》，這本書比較完美地詮釋了 StarRocks 團隊的價值觀：在 Think Big、敢想敢幹的同時，如何攻堅克難、快速迭代，將一個又一個巨集大的想法落地。

 

本期 StarRocks 技術內幕到這就結束了，好學的你肯定學會了一些新東西，或者又產生了一些新困惑，不妨掃描下方使用者群二維碼加入 StarRocks 社群一起交流！

 

 

關於 StarRocks 

StarRocks 創立兩年多來，一直專注打造世界頂級的新一代極速全場景 MPP 資料庫，幫助企業建立“極速統一”的資料分析新正規化，助力企業全面數字化經營。

當前已經幫助騰訊、攜程、順豐、Airbnb 、滴滴、京東、眾安保險等超過 110 家大型使用者構建了全新的資料分析能力，生產環境中穩定執行的 StarRocks 伺服器數目達數千臺。 

2021 年 9 月，StarRocks 原始碼開放，在 GitHub 上的星數已超過 3100 個。StarRocks 的全球社群飛速成長，至今已有超百位貢獻者，社群使用者突破 5000 人，吸引幾十家國內外行業頭部企業參與共建。

​