?譯者 | 李睿

審校 | 孫淑娟

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

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

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

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

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

要回答這個(gè)問(wèn)題，首先要回答以下幾個(gè)問(wèn)題:  

（1）如何衡量CPU性能?  

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

第一個(gè)問(wèn)題的答案可以用這個(gè)公式表示：

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

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

這個(gè)公式提供了一些術(shù)語(yǔ)，可以用來(lái)討論影響性能的杠桿。由于對(duì)時(shí)鐘周期時(shí)間無(wú)能為力，所以需要關(guān)注指令號(hào)和CPI來(lái)提高軟件性能。  

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

（1）提取

（2）解碼  

（3）執(zhí)行  

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

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

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

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

下面是上述方法的簡(jiǎn)化版本。  

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

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

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

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

沒(méi)錯(cuò)，是向量化。  

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

向量化的基本原理  

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

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

SIMD的介紹  

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

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

如何向量化一個(gè)程序?  

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

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

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

方法1.編譯器自動(dòng)向量化  

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

方法2.給編譯器的提示  

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

方法3.并行編程API  

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

方法4.使用SIMD類庫(kù)  

這些庫(kù)包裝了啟用SIMD指令的類。  

方法5.使用SIMD intrinsic  

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

方法6.直接編寫(xiě)程序集代碼  

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

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

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

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

方法1.向編譯器添加選項(xiàng)  

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

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

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

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

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

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

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

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

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

（2）所有運(yùn)算符、表達(dá)式和函數(shù)都必須實(shí)現(xiàn)向量化。這是一項(xiàng)艱巨的任務(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)，如連接、聚合、排序等，都需要從頭開(kāi)始支持向量化。  

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（3）最多保留三個(gè)過(guò)濾器。  

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

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

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

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

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

回顧與感想  

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

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

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

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

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