?譯者 | 李睿

審校 | 孫淑娟

提高分析性能非常重要。大家都明白這一點(diǎn)，但要確保用戶在不增加額外工作量的情況下獲得所需的速度，最好的方法是什么?  

作為數(shù)據(jù)工程師，通常面臨著這個挑戰(zhàn)。為了找到解決方案，一個研究團(tuán)隊啟動了開放項目StarRocks，這是一個分析引擎，可以滿足快速增長的分析性能需求，同時也易于使用和維護(hù)。  

隨著開放項目和技術(shù)社區(qū)在過去幾年的發(fā)展，人們已經(jīng)了解到很多關(guān)于分析性能的有效方法和無效方法。如今分享一些關(guān)于構(gòu)建高性能分析引擎的關(guān)鍵技術(shù)之一的見解：向量化。  

為什么向量化可以提高數(shù)據(jù)庫性能  

在深入研究StarRocks如何實現(xiàn)向量化之前，有一點(diǎn)很重要：當(dāng)談?wù)撓蛄炕瘯r，談?wù)摰氖鞘褂矛F(xiàn)代CPU架構(gòu)的數(shù)據(jù)庫的向量化。有了這些了解，就可以開始回答這個問題：為什么向量化可以提高數(shù)據(jù)庫性能?  

要回答這個問題，首先要回答以下幾個問題:  

（1）如何衡量CPU性能?  

（2）影響CPU性能的因素有哪些?  

第一個問題的答案可以用這個公式表示：

CPU時間=(指令數(shù))*CPI*(時鐘周期時間)  

• 指令數(shù)=CPU生成的指令數(shù)  
• CPI(每條指令的周期)=執(zhí)行一條指令所需的CPU周期  
• 時鐘周期時間=CPU時鐘周期所用的時間  

這個公式提供了一些術(shù)語，可以用來討論影響性能的杠桿。由于對時鐘周期時間無能為力，所以需要關(guān)注指令號和CPI來提高軟件性能。  

此外，還知道的另一個重要信息是，CPU指令的執(zhí)行可以分為五個步驟：

（1）提取

（2）解碼  

（3）執(zhí)行  

（4）內(nèi)存訪問  

（5）寫回結(jié)果(寫入寄存器)  

步驟1和步驟2由CPU前端執(zhí)行，步驟3到步驟5由CPU后端處理。Intel公司發(fā)布了自頂向下微架構(gòu)分析方法，如下圖所示。  

自頂向下微架構(gòu)分析方法(Intel)

下面是上述方法的簡化版本。  

正如人們所看到的，導(dǎo)致CPU性能問題的主要因素是退役、錯誤猜測、前端綁定和后端綁定。  

這些問題背后的主要驅(qū)動因素分別是缺乏SIMD指令優(yōu)化、分支預(yù)測錯誤、指令緩存失誤和數(shù)據(jù)緩存失誤。  

因此，如果將上述原因映射到前面介紹的CPU性能公式，可以得到以下結(jié)論:  

那么，設(shè)計什么來提高這四個方面的CPU性能呢?  

沒錯，是向量化。  

現(xiàn)在已經(jīng)確定了向量化可以提高數(shù)據(jù)庫性能。下面將講解向量化是如何做到這一點(diǎn)。

向量化的基本原理  

如果已經(jīng)很好地理解了向量化，那么可以跳過這一節(jié)，然后轉(zhuǎn)到關(guān)于數(shù)據(jù)庫向量化的一節(jié)，但是如果不熟悉向量化的基礎(chǔ)知識，或者可能需要復(fù)習(xí)一下，那么將簡要概述應(yīng)該知道的內(nèi)容。  

在這里將向量化的討論局限于SIMD。SIMD向量化不同于接下來將要討論的一般數(shù)據(jù)庫向量化。  

SIMD的介紹  

SIMD的意思是“單指令、多數(shù)據(jù)”。顧名思義，使用SIMD架構(gòu)，一條指令可以同時操作多個數(shù)據(jù)點(diǎn)。在SISD(單指令、單數(shù)據(jù))架構(gòu)中，其中一條指令只能在單個數(shù)據(jù)點(diǎn)上操作，但情況并非如此。  

如上所述，在SISD架構(gòu)中，操作是標(biāo)量的，這意味著只處理一組數(shù)據(jù)。因此，4個添加操作將涉及8個加載操作(每個變量一個)、4個添加操作和4個存儲操作。如果使用128位SIMD，只需要兩個加載，一個添加，一個存儲。在理論上，與SISD相比，性能提高了4倍?？紤]到現(xiàn)代CPU已經(jīng)有512位寄存器，可以預(yù)期高達(dá)16倍的性能增益。  

如何向量化一個程序?  

以上了解了SIMD向量化如何極大地提高程序的性能。那么，如何開始在自己的工作中使用它呢?  

調(diào)用SIMD的不同方法  

正如英特爾公司的這張圖片所示，SIMD有六種調(diào)用方式。從上到下，每個方法都需要程序員更多的專業(yè)知識，并需要更多的編碼工作。  

方法1.編譯器自動向量化  

程序員不需要對他們的代碼做任何更改。編譯器將自動將標(biāo)量代碼轉(zhuǎn)換為向量代碼。只有一些簡單的情況可以自動轉(zhuǎn)換為向量代碼。  

方法2.給編譯器的提示  

在這個方法中，向編譯器提供了一些提示。通過提供額外的信息，編譯器可以生成更多的SIMD代碼。  

方法3.并行編程API  

在OpenMP或Intel TBB等并行編程API的幫助下，開發(fā)人員可以添加Pragma來生成向量代碼。  

方法4.使用SIMD類庫  

這些庫包裝了啟用SIMD指令的類。  

方法5.使用SIMD intrinsic  

intrinsic是一組程序集編碼的函數(shù)，允許使用c++函數(shù)調(diào)用和變量來代替程序集指令。  

方法6.直接編寫程序集代碼  

1和方法2。對于不能自動轉(zhuǎn)換為向量代碼的性能關(guān)鍵操作，將使用SIMD intrinsic。  

驗證程序?qū)嶋H生成了SIMD代碼  

這里有一個重要的問題，當(dāng)一個程序有一個復(fù)雜的代碼結(jié)構(gòu)，那么如何確保代碼執(zhí)行是向量化的?  

有兩種方法可以檢查和確認(rèn)代碼已經(jīng)向量化。

方法1.向編譯器添加選項  

有了這些選項，編譯器將生成關(guān)于代碼是否向量化的輸出，如果沒有，原因是什么。例如，可以在GCC編譯器中添加--fopt-info-vec-all, -fopt-info-vec-optimized, -fopt-info-vec-missed, 和 -fopt-info-vec-note選項，如下圖所示：

方法2.檢查執(zhí)行的程序集代碼  

可以使用https://gcc.godbolt.org/這樣的網(wǎng)站或Perf和Vtun這樣的工具來檢查程序集代碼。如果匯編代碼中的寄存器是xmm、ymm、zmm等，或者指令以v開頭，那么就知道該代碼已經(jīng)向量化了。  

既然已經(jīng)掌握了向量化的基礎(chǔ)知識，現(xiàn)在是時候討論向量化數(shù)據(jù)庫提高性能的能力了。  

數(shù)據(jù)庫的向量化  

雖然StarRocks項目已經(jīng)發(fā)展成為一個成熟、穩(wěn)定、行業(yè)領(lǐng)先的MPP數(shù)據(jù)庫(甚至還從CelerData推出了企業(yè)級版本)，但該社區(qū)必須克服許多挑戰(zhàn)才能實現(xiàn)這一目標(biāo)。數(shù)據(jù)庫向量化是最大的突破之一，也是最大的挑戰(zhàn)之一。  

數(shù)據(jù)庫向量化的挑戰(zhàn)  

根據(jù)經(jīng)驗，向量化數(shù)據(jù)庫要比簡單地在CPU中啟用SIMD指令復(fù)雜得多。這是一個龐大的系統(tǒng)工程。特別是面臨著六個技術(shù)挑戰(zhàn):  

（1）端到端的柱狀數(shù)據(jù)。數(shù)據(jù)需要跨存儲層、網(wǎng)絡(luò)層和內(nèi)存層以柱狀格式存儲、傳輸和處理，以消除“阻抗失配”。存儲引擎和查詢引擎需要重新設(shè)計以支持列數(shù)據(jù)。  

（2）所有運(yùn)算符、表達(dá)式和函數(shù)都必須實現(xiàn)向量化。這是一項艱巨的任務(wù)，需要幾年才能完成。  

（3）如果可能，操作符和表達(dá)式應(yīng)該調(diào)用SIMD指令。這需要詳細(xì)的逐行優(yōu)化。  

（4）內(nèi)存管理。為了充分利用SIMD CPU的并行處理能力，必須重新考慮內(nèi)存管理。  

（5）新的數(shù)據(jù)結(jié)構(gòu)。所有用于核心操作符的數(shù)據(jù)結(jié)構(gòu)，如連接、聚合、排序等，都需要從頭開始支持向量化。  

（6）系統(tǒng)的優(yōu)化。對StarRocks的目標(biāo)是，與其他市場領(lǐng)先的產(chǎn)品(具有相同的硬件配置)相比，性能提高5倍。為了達(dá)到這個目標(biāo)，必須確保數(shù)據(jù)庫系統(tǒng)中的所有組件都得到了優(yōu)化。  

向量化運(yùn)算符和表達(dá)式  

在向量化StarRocks時，大部分工程工作都花在向量化操作符和表達(dá)式上。這些工作可以總結(jié)為按列批量計算，如下圖所示：

與本文前面討論的Intel公司自頂向下微架構(gòu)分析方法相對應(yīng)，Batch減少了分支錯誤預(yù)測和指令緩存失誤。按列減少了數(shù)據(jù)緩存丟失，并使調(diào)用SIMD優(yōu)化更容易。  

實現(xiàn)批處理計算相對容易。困難的部分是關(guān)鍵操作符(如聯(lián)接、聚合、排序和混洗)的列處理。在進(jìn)行柱狀處理的同時調(diào)用盡可能多的SIMD優(yōu)化是一個更大的挑戰(zhàn)。  

如何用數(shù)據(jù)庫向量化提高數(shù)據(jù)庫性能  

如上所述，向量化數(shù)據(jù)庫是一項系統(tǒng)工程工作。在過去的幾年里，在開發(fā)StarRocks的過程中實施了數(shù)百項優(yōu)化。以下是需要關(guān)注的7個最重要的優(yōu)化領(lǐng)域。  

• 高性能的第三方庫。對于數(shù)據(jù)結(jié)構(gòu)和算法，有許多優(yōu)秀的開源庫。對于StarRocks，使用了許多第三方庫，例如Parallel Hashmap、Fmt、SIMD Json和Hyper Scan。  
• 數(shù)據(jù)結(jié)構(gòu)和算法。高效的數(shù)據(jù)結(jié)構(gòu)和算法可以將CPU周期減少一個數(shù)量級。正因為如此，當(dāng)StarRocks 2.0發(fā)布時，引入了一個低基數(shù)的全局字典。使用這個全局字典，可以將基于字符串的操作轉(zhuǎn)換為基于整數(shù)的操作。  

如下圖所示，通過操作將兩個基于字符串的組轉(zhuǎn)換為一個基于整數(shù)的組。因此，掃描、散列、相等和mumcpy等操作的性能提高了許多倍，整體查詢性能提高了300%以上。  

• 自適應(yīng)優(yōu)化。如果能夠理解查詢的場景，就可以進(jìn)一步優(yōu)化查詢執(zhí)行。然而，通常直到執(zhí)行時才得到查詢場景信息。因此，查詢引擎必須根據(jù)在查詢執(zhí)行過程中獲得的場景信息動態(tài)調(diào)整其策略。這被稱為自適應(yīng)優(yōu)化。  

下面的代碼片段顯示了一個基于選擇率動態(tài)選擇連接運(yùn)行時過濾器的示例：

有三個決策點(diǎn)可以指導(dǎo)上述示例：

（1）如果過濾器不能過濾大部分?jǐn)?shù)據(jù)，那么就不會使用它。  

（2）如果一個過濾器可以過濾幾乎所有的數(shù)據(jù)，那么我們只保留這個過濾器。  

（3）最多保留三個過濾器。  

• SIMD優(yōu)化。如下圖所示，StarRocks在其操作符和表達(dá)式實現(xiàn)中進(jìn)行了大量SIMD優(yōu)化。  

• C++底層優(yōu)化。即使使用相同的數(shù)據(jù)結(jié)構(gòu)和算法，不同C++實現(xiàn)的性能也可能不同。例如，可以使用移動或復(fù)制操作，可以保留向量，或者可以內(nèi)聯(lián)函數(shù)調(diào)用。這些只是必須考慮的一些優(yōu)化。
• 內(nèi)存管理優(yōu)化。批處理大小越大，并發(fā)性越高，分配和釋放內(nèi)存的頻率就越高，內(nèi)存管理對系統(tǒng)性能的影響就越大。  

使用StarRocks，實現(xiàn)了一個列池數(shù)據(jù)結(jié)構(gòu)來重用列的內(nèi)存，并顯著提高了查詢性能。以下的代碼片段顯示了一個HLL(HyperLogLog)聚合函數(shù)內(nèi)存優(yōu)化。通過按塊分配HLL內(nèi)存，并通過重用這些塊，將HLL的聚合性能提高了五倍。  

• CPU緩存優(yōu)化。CPU緩存丟失對性能有巨大的影響?？梢詮腃PU周期的角度來理解這種影響。L1訪問緩存需要3個CPU周期，L2訪問緩存需要9個CPU周期，L3訪問緩存大約需要40個CPU周期，主存訪問緩存大約需要200個CPU周期。

在調(diào)用SIMD優(yōu)化和性能瓶頸從CPU限制轉(zhuǎn)移到內(nèi)存限制之后，CPU緩存缺失成為了一個特別重要的因素。下面的代碼片段展示了如何通過預(yù)取減少CPU丟失。不過在這里指出的是，預(yù)取應(yīng)該是優(yōu)化CPU緩存的最后手段。這是因為很難控制預(yù)取的時間和距離。

回顧與感想  

現(xiàn)在已經(jīng)踏上了StarRocks數(shù)據(jù)庫向量化的旅程，以下回顧一下學(xué)到了什么。  

• 不同系統(tǒng)的基本原理是相似的。當(dāng)開始研究CPU的微架構(gòu)時，意識到CPU的架構(gòu)與數(shù)據(jù)庫架構(gòu)的相似之處。在StarRocks的例子中，前端管理SQL解析和查詢規(guī)劃，后端負(fù)責(zé)SQL執(zhí)行和與存儲層交互。研究的系統(tǒng)和體系結(jié)構(gòu)越多，就會越深入地理解系統(tǒng)級別的相似性。  
• 要建立高性能的數(shù)據(jù)庫，不僅需要設(shè)計良好的架構(gòu)，而且還需要密切關(guān)注工程細(xì)節(jié)。雖然良好的設(shè)計和良好的工程似乎都是很明顯的需要，但在數(shù)據(jù)庫產(chǎn)品中往往缺少其中之一。如果真的相信這兩者，就不會只使用自底向上的方法(從算法和唯一的組件開始)來設(shè)計數(shù)據(jù)庫，而不實現(xiàn)確保所有這些組件都能很好地協(xié)同工作的高級架構(gòu)。也不能選擇Java或Go等編程語言來實現(xiàn)查詢執(zhí)行引擎和存儲引擎，而可以使用C++等更多性能語言。  

• 混合向量化和編譯。向量化和編譯是兩種主要的查詢執(zhí)行風(fēng)格，但它們并不相互排斥。盡管大多數(shù)開源數(shù)據(jù)庫都選擇使用向量化，但可以利用查詢編譯，通過查詢執(zhí)行期間獲得的信息生成更高效的向量代碼。與此同時，查詢編譯也在不斷改進(jìn)。  
• 嘗試采用新的硬件，例如GPUu和FPGA。經(jīng)過大量優(yōu)化后，可能已經(jīng)接近CPU優(yōu)化的收益遞減點(diǎn)?？梢钥紤]其他新的硬件，以進(jìn)一步提高StarRocks的性能。  

隨著數(shù)據(jù)量的增長、數(shù)據(jù)源的擴(kuò)展和用戶期望的提高，數(shù)據(jù)工程師的角色在未來幾年只會變得更加重要。有了StarRocks這樣的項目和數(shù)據(jù)庫向量化這樣的創(chuàng)新，可以滿足遇到的任何性能需求。  

原文標(biāo)題：??How vectorization improves database performance???,作者：James Li，Kaisen Kang?