不對稱內存計算平臺OLAP查詢處理技術研究

張延松,張宇,周恒,王珊

(1.中國人民大學DEKE實驗室,北京100872; 2.中國人民大學信息學院,北京100872; 3.中國人民大學中國調查與數(shù)據(jù)中心,北京100872; 4.國家衛(wèi)星氣象中心,北京100081)

不對稱內存計算平臺OLAP查詢處理技術研究

張延松1-3,張宇4,周恒1,2,王珊1,2

(1.中國人民大學DEKE實驗室,北京100872; 2.中國人民大學信息學院,北京100872; 3.中國人民大學中國調查與數(shù)據(jù)中心,北京100872; 4.國家衛(wèi)星氣象中心,北京100081)

給出了一種面向當前和未來不對稱內存計算平臺的OLAP查詢處理技術.不對稱內存計算平臺是指配置有不同計算類型的處理器、不同存儲訪問設備的計算機,因此需要對OLAP查詢處理模型按不同的計算特點進行優(yōu)化存儲配置和實現(xiàn)算法設計,從而使OLAP查詢處理的不同階段更好地適應相應的存儲與計算設備的硬件特點,提高硬件設備的利用率,更好地發(fā)揮硬件的性能.提出了3階段OLAP計算模型,將傳統(tǒng)基于迭代處理模型的OLAP查詢處理過程分解為計算密集型和數(shù)據(jù)密集型負載,分別由功能完備的通用處理器和并行計算能力強大的協(xié)處理器分而治之地完成,并最小化不同存儲與計算設備之間的數(shù)據(jù)傳輸代價.實驗結果表明基于負載劃分的3階段OLAP計算模型能夠較好地適應CPU-Phi不對稱計算平臺,實現(xiàn)通過計算型硬件加速計算密集型負載,從而加速整個OLAP查詢處理性能的目標.

內存計算;不對稱計算平臺;內存聯(lián)機分析處理

0 引言

硬件技術的發(fā)展推動數(shù)據(jù)庫技術的升級.計算機硬件技術發(fā)展的一個重要反映是晶體管制造工藝水平的持續(xù)提高,晶體管制造工藝主要體現(xiàn)在CPU/GPU和內存技術的進步. CPU制造工藝從1971年的10 μm提升到2015年的14 nm,未來還將推出7 nm工藝.隨著CPU和GPU制造工藝的迅速提高,在單位面積的芯片上能夠集成更多的晶體管.晶體管集成技術的提升在處理器和內存架構設計上產(chǎn)生了巨大的影響.如圖1(a)-(f)所示,處理器在晶體管的集成技術的不同技術路線產(chǎn)生了不同類型的處理器.多核CPU采用了L1-L2-L3多級緩存結構,大量晶體管用于構建控制電路與LLC(Last Level Cache),僅有5%左右用于計算單元ALU,主要通過高性能緩存加速數(shù)據(jù)訪問性能,圖1(a)中間部分面積較大的晶體管單元為LLC.當前多核CPU已達到22個處理核心,55 MB LLC.協(xié)處理器(coprocessor,如圖1(b)和1(c))Cache較小,核心數(shù)量眾多但功能相對簡單,大約40%的晶體管用于構建計算單元,主要通過更多的并發(fā)線程來掩蓋內存訪問延遲.例如NVIDIA K80雙GK210核心采用28 nm工藝,集成的晶體管數(shù)量超過71億個,每個GK210核心有2880個流處理器.代號Knights Landing的新一代Xeon Phi處理器采用14 nm工藝制造,擁有72億個晶體管,集成了72個x86核心,搭配16 GB MCDRAM緩存.

通用處理核心的復雜數(shù)據(jù)處理能力與大規(guī)模計算核心強大的并行計算能力相結合產(chǎn)生了融核設計思想.圖1(d)顯示了AMD融核架構的APU結構,將多核處理器與GPU處理器集成到一個芯片上,使處理器同時具有兩種不同的計算特性.圖1(e)為下一代Intel Phi處理器Knight Landing的主處理器架構,由眾核處理器直接構建主處理器,從而提供一個兼容x86架構的高性能計算平臺.下一代Xeon處理器將使用Xeon+FPGA的異構計算模式[1](見圖1(f)),將FPGA集成到Xeon處理器內部,提供定制的計算能力和更低的計算功耗.

存儲技術同樣隨著晶體管集成技術的發(fā)展而不斷進步.圖1(h)為IBM的eXFlash DIMM內存[2],提供了基于內存插槽的非易失性大容量存儲,為內存計算提供了大容量持久存儲介質.圖1(i)顯示了3D內存的基本結構,通過芯片堆疊技術顯著提升內存的容量和帶寬性能,新一代采用3D芯片堆疊技術的內存架構相較于DDR3內存速度有10倍的提升.圖1(j)顯示了Intel的3D XPointDIMM結構[3],通過獨特的3D集成技術提供非易失、大容量、高性能存儲,Q可用作SSD,也可用作新型非易失內存.

圖1 不同類型的處理器與存儲技術Fig.1Different types of processors and memory technologies

硬件技術的飛速發(fā)展提供了多樣化的存儲與計算平臺,也構建了一個不對稱的內存計算平臺,即內存計算面對的不僅是對稱的多核處理器和DRAM,而且包含了多核處理器、協(xié)處理器、融核處理器和DRAM內存、非易失內存、Flash閃存等性能特征存在顯著不同的異構存儲與計算平臺.硬件技術的發(fā)展與變化為內存數(shù)據(jù)庫技術帶來的直接挑戰(zhàn)是如何將負載的特點與計算設備的特點相匹配,如何將不同訪問類型的數(shù)據(jù)在不同訪問特點的異構存儲設備上進行分布,從而實現(xiàn)負載本地計算的最大化,更好地發(fā)揮新型存儲和計算設備的性能.

本文探討了基于當前和未來不對稱內存計算平臺硬件特征的內存OLAP查詢處理技術,通過負載劃分將傳統(tǒng)的迭代處理模型分解為具有較強數(shù)據(jù)局部性的3階段計算模型,使不同階段的計算特征與負載特征、數(shù)據(jù)分布特征以及存儲和計算硬件特征相匹配,更好地適應不對稱內存計算平臺的特性,提高內存OLAP查詢處理的性能與效率.本文第1節(jié)介紹了研究背景及相關工作,第2節(jié)給出了基于負載特征劃分的3階段內存計算模型,第3節(jié)通過實驗驗證3階段內存計算模型的性能特征,最后在第4節(jié)概括本文的工作.

1 研究背景和相關工作

1.1 研究背景

隨著硬件技術的發(fā)展,內存計算平臺呈現(xiàn)多樣化的趨勢.從處理器技術發(fā)展趨勢來看,通用的多核處理器結構復雜、成本高昂、能耗顯著、核心集成數(shù)量較少,基于對稱同構多核處理器的計算平臺在大規(guī)模實時分析處理領域將逐漸被異構非對稱的計算型處理器所取代.

圖2顯示了當前和未來內存計算平臺可能的技術選擇.位于主板的主處理器(host processor)能夠直接訪問內存,需要處理器能夠獨立運行系統(tǒng).除傳統(tǒng)的通用多核CPU之外, AMD融核APU處理器在CPU中集成了具有較強并行計算能力的GPU,實現(xiàn)CPU與GPU對相同地址空間數(shù)據(jù)的直接訪問與處理.Intel Phi下一代的Knights Landing采用Silvermont核心替代原來的P54C核心,可以作為主處理器使用,從而提供更加強大的內存計算能力. FPGA在一些數(shù)據(jù)密集型負載中得到廣泛的應用,如Netezza使用FPGA作為數(shù)據(jù)庫加速卡進行前端數(shù)據(jù)流的簡單、數(shù)據(jù)密集型處理.Intel未來的Xeon處理器中將集成FPGA,面向應用定制處理器,提高處理器面向負載特征的性能.通過PCI-E通道連接的獨立協(xié)處理器,如Intel Xeon Phi、NVIDIA GPGPU、FPGA等具有強大的并行處理能力,通常具有較大的本地高帶寬內存,但需要通過帶寬相對較低的PCI-E通道訪問大容量內存,現(xiàn)階段主要的技術挑戰(zhàn)是協(xié)處理器強大的并行計算能力和PCI-E傳輸瓶頸之間的矛盾,未來的設備互聯(lián)技術,如PCI-E 4.0、NVLink、Omni Path等技術能夠大幅度提高協(xié)處理器與CPU內存或協(xié)處理器之間的數(shù)據(jù)傳輸性能,從而使協(xié)處理器強大的并行計算能力得到更好的發(fā)揮.

圖2 不對稱處理器與存儲技術Fig.2Asymmetric processor and storage technologies

從內存層面來看,主存在現(xiàn)代3D內存技術的支持下將獲得更大的容量、更高的帶寬以及非易失性,是內存計算的重要高性能存儲設備.協(xié)處理器內存通常為8-24 GB,一般作為協(xié)處理器的本地緩存使用,也可以作為計算密集型負載的駐留存儲和計算存儲.PCI-E Flash閃存卡是一種大容量存儲設備,當前能夠提供高達6.4TB的設備存儲容量,可以作為內存計算的二級內存使用,從而提高內存計算的性價比.FPGA良好的集成性使其可以集成到大容量PCI-E Flash閃存卡中,從而實現(xiàn)將一部分數(shù)據(jù)處理工作下推到最底層的數(shù)據(jù)存儲層.

硬件技術的日新月異為內存數(shù)據(jù)庫技術提出很多技術挑戰(zhàn).內存數(shù)據(jù)庫的算法設計以傳統(tǒng)的基于通用多核處理器多級cache硬件架構為基礎,但新興的計算型處理器通常采用大量處理核心、更高向量處理能力、較小cache的硬件架構,因此內存數(shù)據(jù)庫在算法設計上需要從cache-conscious算法設計升級為architecture-conscious算法設計,使內存數(shù)據(jù)庫的關鍵算法設計能夠更好地適應未來不同的處理器特點.同時,需要在內存數(shù)據(jù)庫查詢處理模型的設計上改變以同構內存訪問和計算為假設的思想,需要根據(jù)不對稱的計算與存儲資源特點對查詢處理任務進行分解,將負載的特征、數(shù)據(jù)的特征與存儲和計算資源的特征相匹配,達到優(yōu)化資源配置,減少不同負載處理的耦合度,提高不對稱內存計算性能和效率.

1.2 相關工作分析

雖然內存數(shù)據(jù)庫已經(jīng)成為當前數(shù)據(jù)庫的主流技術,但對內存數(shù)據(jù)庫核心算法的研究仍在繼續(xù),尤其以內存連接算法研究為代表.從近年來的研究技術路線來看,一個熱點討論問題是在現(xiàn)代處理器硬件架構下,cache-oblivious還是cache-conscious能夠獲得更高的性能. cache-oblivious性能占優(yōu)意味著連接算法采用簡單的設計并且對不同硬件平臺具有自動適應能力,cache-conscious性能占優(yōu)則意味著連接算法必須挖掘硬件特性以獲得更高的性能,算法復雜度相對較高.文獻［4］通過實驗對比了cache-oblivious的無分區(qū)哈希連接算法與cache-conscious的radix分區(qū)哈希連接算法的性能,指出無分區(qū)哈希連接算法的主要代價集中在哈希探測產(chǎn)生的內存訪問代價,可以通過現(xiàn)代處理器支持的并發(fā)多線程和自動預取機制提高性能；radix分區(qū)哈希連接算法的主要代價集中在radix分區(qū)過程,時間和空間代價均較高,但哈希探測性能較高.文獻［5］進一步優(yōu)化了［4］的算法設計,通過SIMD等硬件技術進一步優(yōu)化算法性能,從而使radix分區(qū)哈希連接算法優(yōu)于無分區(qū)哈希連接算法,證明了基于硬件特性的優(yōu)化技術仍然能夠帶來更高的性能.文獻［6］通過SIMD技術對排序歸并算法和哈希算法進行優(yōu)化,radix分區(qū)哈希連接算法的綜合性能最優(yōu),證明了radix分區(qū)哈希連接算法的優(yōu)勢.

內存數(shù)據(jù)庫的算法研究同樣延伸到眾核協(xié)處理器平臺.在文獻［7］中,radix連接的radix分區(qū)操作在CPU端執(zhí)行,分區(qū)后的數(shù)據(jù)傳輸?shù)紾PU端,通過nested loop或二分查找算法完成分區(qū)數(shù)據(jù)上的連接操作.GPU相對CPU擁有大量的核心與硬件級并發(fā)線程,內存訪問的優(yōu)化不同于CPU通過cache緩存減少內存訪問延遲,而是通過大量并發(fā)內存訪問線程掩蓋內存訪問延遲,因此更加適合cache-oblivious的無分區(qū)哈希連接算法[8,9].文獻［10］進一步探索了基于融核APU上的查詢優(yōu)化技術,通過協(xié)同CPU與GPU核心的任務調度和優(yōu)化不同內核之間的數(shù)據(jù)共享訪問提高查詢處理性能.相對于GPU需要用CUDA或OpenCL對算法重寫,Xeon Phi由于其與x86兼容的指令系統(tǒng)而更容易從CPU平臺遷移到Xeon Phi協(xié)處理器平臺.文獻［11］將文獻［5］提供的開源哈希算法優(yōu)化為Xeon Phi版本并進行測試,實驗結果表明Xeon Phi的眾多核心和更多的線程能夠有效地降低內存訪問延遲,cache-oblivious的無分區(qū)哈希連接算法較CPU平臺有較大的性能提升,甚至優(yōu)于radix分區(qū)哈希連接算法的性能.最新的研究[12]對算法再次進行全面的SIMD優(yōu)化設計,挖掘了Xeon Phi 512位向量處理能力,進一步優(yōu)化了算法在Xeon Phi端的性能,并使radix分區(qū)哈希連接算法再次優(yōu)于無分區(qū)哈希連接算法.值得注意的是,Xeon Phi與CPU具有類似的L1-L2 cache結構,因此經(jīng)過充分優(yōu)化后具有與CPU類似的性能特征.但radix分區(qū)哈希連接算法需要雙倍的內存空間來支持對兩個連接表的radix分區(qū)操作,降低了Xeon Phi協(xié)處理器有限內存的利用率.內存哈希連接算法的研究同樣擴展到FPGA平臺[13],FPGA相對于CPU支持更深的流水線和數(shù)以千計的并發(fā)內存訪問線程,不借助cache機制而達到較高的內存訪問性能,在相似內存帶寬性能的CPU和FPGA平臺上基于文獻［5］的兩種內存哈希算法較CPU平臺有成倍的性能提升.除通用的內存哈希連接算法之外,文獻［14］研究了OLAP中基于主-外鍵參照完整性約束關系和代理鍵機制[15]的外鍵連接優(yōu)化技術,通過對OLAP模式的分析提出了代理鍵地址映射機制,并基于數(shù)組存儲模型設計了以維代理向量參照地址訪問為基礎的數(shù)組地址參照訪問AIR算法,并通過Benchmark測試驗證了其較好的性能.AIR算法是一種依賴簡單數(shù)組存儲和數(shù)組地址訪問操作的外鍵連接算法,算法效率高并且易于向協(xié)處理器平臺遷移.

哈希連接是內存數(shù)據(jù)庫最重要的算法,也是內存OLAP性能決定性的操作符.連接操作性能優(yōu)化技術研究的一個顯著趨勢是借助先進硬件的性能獲得提升,需要使算法設計與硬件特點相匹配.在未來的處理器技術中,Intel Xeon Phi KNL可以將整個板上內存用作16 GB的L3 cache,提高了cache-oblivious算法優(yōu)化的應用范圍,而NVIDIA GPGPU、FPGA等處理器則更加注重大規(guī)模并發(fā)線程的內存訪問性能,因此,在內存連接算法的研究上不能完全依賴cache-oblivious或者cache-conscious設計,而要使算法具有對不同類型硬件平臺的適應性,提高內存利用率,優(yōu)化內存隨機訪問性能.

2 不對稱內存計算平臺OLAP查詢優(yōu)化技術

處理器和存儲技術的分化產(chǎn)生了不對稱的內存計算平臺,查詢處理的整個過程被物理地分配給不同硬件性能特點的存儲設備和處理器,因此,如何減少數(shù)據(jù)在不同處理器和存儲設備之間的傳輸代價、使查詢負載適合不同的處理器計算特性對于提高不對稱內存計算平臺的性能和效率具有重要的意義.

2.1 內存OLAP不對稱存儲模型

OLAP模型是一種多維數(shù)據(jù)模型,由數(shù)量眾多但數(shù)據(jù)量極小的維表和巨大的事實表構成,維表由主鍵和代表維層次等屬性的描述性字段構成,事實表由維表外鍵和代表數(shù)量關系的度量屬性組成.

圖3 SSB不同類型數(shù)據(jù)量和查詢時間占比Fig.3Proportions of Different Datasets and Processing Time of Star Schema Benchmark

以SSB數(shù)據(jù)集為例(SF=100,事實表包含600 000 000記錄),如圖3所示,四個維表數(shù)據(jù)量占比為0.86%,事實表外鍵數(shù)據(jù)量占比為19.34%,事實表度量列數(shù)據(jù)量占比為79.80%；在［14］中基于AIR算法的維表處理、外鍵連接和聚集計算三個階段執(zhí)行時間占比分別為7.11%、86.43%和6.46%.20%的外鍵列上的計算代價超過OLAP查詢總代價的80%,而這部分外鍵連接操作適合通過新興的計算型處理器進行加速,較小的外鍵通常能夠實現(xiàn)協(xié)處理器內存駐留存儲,從而最小化內存與協(xié)處理器之間的PCI-E數(shù)據(jù)傳輸代價.以SSB數(shù)據(jù)集為例,在SF=100的數(shù)據(jù)集中四個外鍵列大小為9.6 GB,小于主流Xeon Phi與GPGPU的16 GB和24 GB內存,也就是說一個協(xié)處理器可以支持SF=100的OLAP外鍵存儲和其上的連接加速任務.

在內存OLAP應用中,維表數(shù)據(jù)量和其上的選擇、投影、分組等操作執(zhí)行時間較短,維表可采用內存存儲或閃存存儲.事實表外鍵相對于度量列較小,但其上的外鍵連接操作占OLAP查詢時間的比重最高,屬于計算密集型負載,需要將其駐留存儲于最接近計算單元的存儲設備中,如協(xié)處理器內存或主存.事實表度量列數(shù)據(jù)量最大,但其上的聚集計算執(zhí)行時間較短,屬于數(shù)據(jù)密集型負責,可以將其存于閃存等低成本、大容量存儲設備中以提高內存OLAP查詢處理的性價比.

2.2 內存OLAP三階段計算模型

我們以數(shù)據(jù)為中心,將OLAP查詢處理分解為三個獨立的計算階段.第一階段是維表處理階段,將OLAP查詢中維表上的選擇、投影、分組操作應用在維表上,生成分組投影向量,并對分組投影向量采用輕量字典表壓縮,將投影出的分組成員存儲在數(shù)組字典表中,數(shù)組下標作為壓編碼更新到分組投影向量中.第二階段是事實表外鍵列計算階段,事實表外鍵與維表投影向量執(zhí)行外鍵連接操作,與分組投影向量連接的結果存儲在度量向量中,記錄每個事實表記錄是否滿足連接條件及相應的多維形式的分組編碼.第三階段通過度量向量在事實表度量列上執(zhí)行分組聚集計算,度量向量起到位圖索引的作用,按位置訪問OLAP查詢相關的度量屬性列,并根據(jù)度量向量中存儲的多維分組編碼進行聚集計算.三個計算階段之間輸入與輸出的是較小的維表分組投影向量和事實表度量向量,在數(shù)據(jù)按存儲和計算設備劃分時能夠最小化不同計算任務之間的數(shù)據(jù)傳輸代價.

在維表處理階段,我們使用基于代理鍵的外鍵連接技術.在數(shù)據(jù)倉庫中具有主-外鍵參照完整性約束關系的被參照表中使用代理鍵[15]作為主鍵,然后更新外鍵為代理外鍵.OLAP查詢在維表上的操作生成代理向量,即以代理鍵為偏移地址的向量,外鍵連接操作轉化為向代理向量的地址映射訪問,即文獻［14］所述的AIR算法.我們進一步放松了文獻［14］中基于數(shù)組存儲的強約束條件,通過邏輯代理鍵保持被參照表主鍵邏輯地址映射特性,解決了數(shù)據(jù)庫異位更新機制(out-of-place update)導致的代理鍵與物理偏移地址不對應問題.圖4顯示了邏輯代理鍵映射機制的實例,其中surrogate key列為邏輯代理鍵列,數(shù)據(jù)庫只需要維護代理鍵唯一、連續(xù)分配,并不需要保持物理存儲順序.查詢結果輸出為代理向量,即以邏輯代理鍵為下標的向量,投影操作的結果映射到邏輯代理鍵值對應的向量單元中,由代理向量與外鍵列完成基于代理鍵地址映射的外鍵連接操作.

圖4 邏輯代理鍵映射Fig.4Logical surrogate key mapping

OLAP查詢在維表上按WHERE子句投影出GROUP BY子句對應的分組屬性作為代理向量,代理向量中的空值代表對應邏輯代理鍵記錄不滿足WHERE謂詞條件,非空值作為當前維上輸出的分組屬性分量.代理向量通過字典表數(shù)據(jù)壓縮將OLAP查詢投影出的分組向量進一步壓縮,通過數(shù)組字典表存儲代理向量中的分組值,以分組字典數(shù)組下標作為代理向量壓縮編碼.在SSB和TPC-H大部分OLAP查詢中分組為低勢集,維表上的代理向量通常可以壓縮為int 8類型(表示28-1個分組).由于維表較小且涉及復雜的數(shù)據(jù)類型、函數(shù)及表達式處理,維表處理階段由CPU負載,并輸出經(jīng)過字典表壓縮后的分組投影向量.

在事實表外鍵列計算階段,基于代理鍵地址引用訪問的AIR算法將哈希連接算法簡化為外鍵向代理向量的地址映射訪問,從而消除了復雜的哈希表設計,提高了AIR算法的代碼執(zhí)行效率,并且易于向GPU、Xeon Phi、FPGA等復雜數(shù)據(jù)管理能力弱、并行計算能力強大的協(xié)處理器進行部署.圖5描述了在不對稱內存計算平臺上的外鍵連接實現(xiàn)策略.當協(xié)處理器為主處理器或者與CPU訪問相同的內存地址空間時,由并行計算能力更加強大的協(xié)處理器(如APU中的GPU單元、Xeon Phi KNL主處理器、FPGA、Xeon+FPGA中的FPGA單元等)執(zhí)行事實表外鍵連接操作,并生成度量向量.度量向量由各維代理向量分組壓縮編碼構造的多維數(shù)組地址編碼構成,通過多維地址編碼進一步壓縮多分組屬性存儲空間.

圖5 基于代理鍵參照訪問的外鍵連接實現(xiàn)Fig.5Surrogate key referencing oriented foreign key join implementation

當協(xié)處理器為PCI-E加速卡時,如NVIDIA GPGPU、Xeon Phi、FPGA加速卡等,我們將PCI-E加速卡的本地內存作為外鍵列存儲器,加速OLAP的外鍵連接操作.對于給定的OLAP數(shù)據(jù)集,PCI-E加速卡加速全部外鍵連接操作所需要的內存大小為,其中wi表示n個外鍵寬度及度量向量寬度,R表示外鍵列行數(shù).當數(shù)據(jù)集較大時,可以根據(jù)需求配置多個加速卡實現(xiàn)計算密集型外鍵連接操作的內存計算.較小的維代理向量在OLAP查詢執(zhí)行時由CPU通過PCI-E通道傳輸?shù)郊铀倏▋却鎴?zhí)行外鍵連接操作,生成度量向量通過PCI-E通道傳輸回CPU內存,完成后續(xù)的聚集計算,或者由協(xié)處理器基于度量向量通過PCI-E卡間的通道訪問PCI-E Flash閃存卡完成聚集計算任務.

在聚集計算階段,度量向量中存儲的多維數(shù)組壓縮編碼可以作為分組鍵值執(zhí)行哈希分組聚集計算；當多維分組壓縮編碼較小時,即多個分組壓縮編碼所構建的多維數(shù)組較小(通常低于LLC slice,即2.5 MB,支持655 360個int類型分組聚集結果)時,可以使用多維數(shù)組進行聚集計算,度量向量中存儲的多維數(shù)組壓縮編碼直接映射為多維數(shù)組下標.

當在PCI-E大容量Flash閃存卡上集成了FPGA時,可以進一步將聚集計算階段下推到Flash閃存卡的FPGA單元中.度量向量傳輸?shù)紽lash閃存卡,由嵌入式FPGA根據(jù)度量向量按位置訪問度量列并執(zhí)行基于多維數(shù)組的分組聚集計算,減少度量列在PCI-E通道的傳輸代價.在聚集計算算法設計中只使用向量和多維數(shù)組,算法易于在FPGA中實現(xiàn).

2.3 不對稱內存計算平臺OLAP查詢處理基本策略

通過前面的算法設計,我們實現(xiàn)了OLAP模式中具有典型的復雜數(shù)據(jù)管理特征的維表、具有計算密集型處理特征的事實表外鍵列、具有數(shù)據(jù)密集型訪問特征的事實表度量列在不同存儲層次上的分布以及與數(shù)據(jù)相關的計算負載在不同處理單元上的分布,將負載的特征與處理單元的特征相結合,計算密集型的外鍵連接操作由并行計算能力強大的協(xié)處理器完成,從而實現(xiàn)通過硬件加速卡加速OLAP關鍵操作性能的目標.

本文提出的3階段計算模型的意義是將OLAP查詢中數(shù)據(jù)量占比20%但計算量占比80%的計算密集型外鍵連接負載獨立出來,并通過代理鍵索引機制簡化外鍵連接算法,使其更易于部署在協(xié)處理器上進行加速.三個計算階段之間通過簡單的向量數(shù)據(jù)結構進行驅動, Q減少了數(shù)據(jù)傳輸量,也簡化了后續(xù)計算的復雜度.基于度量向量的聚集計算將位圖索引訪問和多維數(shù)組聚集計算結合起來,簡化算法設計,使之更加易于部署在嵌入式FPGA等芯片中而集成到Flash卡中,實現(xiàn)存儲設備上的計算.

簡化每個階段的數(shù)據(jù)結構與算法設計,將查詢處理過程解耦合為向量驅動的獨立計算過程等優(yōu)化技術可以根據(jù)不對稱內存計算平臺的資源靈活分配不同的負載任務,提高存儲和計算資源的利用率,更好地利用硬件加速器提升關鍵計算性能,優(yōu)化OLAP查詢性能.

3 實驗分析

不對稱內存計算平臺查詢優(yōu)化技術的核心是通過眾核協(xié)處理器的高并行處理性能加速OLAP查詢中最為關鍵的外鍵連接操作的性能,從而起到通過硬件協(xié)同處理加速OLAP整體性能的效果.我們在文獻［16］已驗證基于GPU的3階段OLAP計算模型的性能,其性能的決定因素為事實表外鍵連接性能.

為驗證眾核協(xié)處理器對外鍵連接操作的加速效率,我們在一臺DELL PowerEdge R730服務器上進行外鍵連接算法測試,服務器配置有2塊Intel Xeon E5-2650 v3@2.30 GHz 10核CPU,共20個核心,40個線程,512 GB DDR3內存.操作系統(tǒng)為CentOS,Linux版本為2.6.32-431.el6.x86 64,gcc版本為4.4.7.服務器配置了一塊Intel Xeon Phi 5110P@1.053 GHz協(xié)處理器,其中集成了60個核心,每核心支持4線程,共計240線程,Phi 5110P協(xié)處理配置有8 GB內存,協(xié)處理器內置操作系統(tǒng)的Linux版本為2.6.38.8+mpss3.3,gcc版本為4.7.0.服務器還配置了一塊NVIDIA K80 GPU加速卡,K80擁有4992 cuda核心和24 GB GDDR5顯存,顯存帶寬達到480 GB/s.

我們在文獻［5］提供的開源NPO、PRO算法的基礎上增加了AIR算法.在數(shù)據(jù)生成器中屏蔽了對R表的shuffler過程,使R表使用代理鍵作為主鍵,S表需要進行shuffler過程,使之符合主-外鍵約束的一般場景.AIR算法實現(xiàn)中模擬了R表上的謂詞操作,在NPO算法的BUILD過程對R表進行過濾,生成R表代理向量,然后S表根據(jù)主鍵映射到R表代理向量,完成連接操作.AIR算法生成的R表代理向量可以使用不同的數(shù)據(jù)類型,如int 8、int 16或int 32,根據(jù)對SSB、TPC-H等查詢中維表分組投影的分析,我們主要使用int 8作為過濾器數(shù)據(jù)類型,模擬維過濾位圖及分組向量存儲.在實驗中R表和S表采用int 32數(shù)據(jù)類型key和payload,key的值域(232-1)能夠滿足數(shù)據(jù)倉庫維表主鍵的取值范圍,考慮到內存數(shù)據(jù)庫普遍采用數(shù)據(jù)壓縮技術,我們在實驗中并未使用int 64數(shù)據(jù)類型.我們在測試中對比2塊Xeon CPU與1塊Xeon Phi協(xié)處理器的性能,CPU端算法測試設置為40線程,Xeon Phi端算法測試設置為240線程.

3.1 測試數(shù)據(jù)集

我們首先對比了文獻［5］使用的Workload A和B,其數(shù)據(jù)集對應的連接表R和S的設置如表1所示.我們將Workload A和B中的key與payload數(shù)據(jù)寬度統(tǒng)一設置為4字節(jié),能夠滿足OLAP應用中主鍵的值域和基于壓縮技術的數(shù)據(jù)存儲需求.

表1 參考負載測試集Tab.1Referenced workloads dataset

為更好地分析不同的外鍵連接算法在內存OLAP中的性能,我們模擬典型OLAP Benchmark中的外鍵連接操作,選用的數(shù)據(jù)集為SSB、TPC-H和TPC-DS中相應的外鍵連接操作,包括維表與事實表之間的外鍵連接操作以及具有主-外鍵參照完整性約束關系的事實表之間的外鍵連接操作,數(shù)據(jù)集大小設置為SF=100,對應TPC-H網(wǎng)站官方測試的最小數(shù)據(jù)集.各數(shù)據(jù)集中連接表的記錄行數(shù)如表2所示.

表2 基準測試數(shù)據(jù)集Tab.2Datasets for benchmark testing

3.2 外鍵連接性能測試結果分析

由于Intel Xeon E5-2650 v3與Intel Xeon Phi 5110P的主頻不同,因此我們以納秒每記錄(ns/tuple)作為性能指標.

圖6顯示了AIR、NPO和PRO外鍵連接算法在CPU和Xeon Phi端的執(zhí)行性能,其中無分區(qū)哈希連接算法NPO的主要代價是共享哈希表內存訪問,Xeon Phi的并發(fā)多線程內存訪問機制能夠提高內存訪問性能,因此NPO的性能在Xeon Phi端較高；PRO算法依賴于cache大小進行優(yōu)化,CPU具有更高的每核心cache大小,而Xeon Phi上有更高的并發(fā)處理線程,總體來看,其性能在CPU端和Xeon Phi端差距不大；AIR算法中的代理向量較小,CPU較大的cache能夠較好地加速其性能,當R表較小時,CPU較大的cache使AIR算法在CPU端的性能優(yōu)于Xeon Phi端,當R表較大時,CPU的cache緩存優(yōu)化和Xeon Phi的多線程優(yōu)化具有類似的性能.需要注意的是,我們在實驗中使用2塊Xeon 10核處理器與1塊Xeon Phi 60核協(xié)處理器進行性能對比,單Xeon Phi協(xié)處理器的性能與2塊Xeon 10核處理器持平.

圖6 外鍵連接算法性能對比Fig.6Performance comparison for foreign key join algorithms

圖7顯示了SSB和TPC-H基準中各外鍵連接操作在CPU和Xeon Phi上的性能對比.首先,AIR使用代理向量的內存開銷低于NPO算法中的哈希表,因此能夠支持全部測試,而NPO在TPC-H中較大的連接表時超出Xeon Phi的內存而不能執(zhí)行,PRO算法的raidx分區(qū)操作需要2倍的內存空間,在SSB和TPC-H測試中超出內存容量而不能執(zhí)行測試.從算法內存效率來看,AIR優(yōu)于NPO,NPO優(yōu)于PRO.其次,從算法性能來看,SSB數(shù)據(jù)集中維表較小,更適合CPU較大cache上的優(yōu)化,因此AIR算法與NPO算法在CPU上的性能優(yōu)于Xeon Phi上的性能.TPC-H除supplier表較小外其他表均較大,在大表連接時Xeon Phi的性能優(yōu)于CPU.

圖7 SSB、TPC-H基準外鍵連接算法性能對比Fig.7Performance comparison for foreign key join algorithmsin SSB and TPC-H

TPC-DS相對于SSB和TPC-H有更多的維表,但維表記錄數(shù)量較少且記錄增長緩慢.AIR算法的代理向量通常低于L2 cache,因此Xeon Phi與CPU都有較好的cache訪問性能,Xeon Phi更多的線程使AIR算法的性能優(yōu)于CPU.NPO算法在較少和中等記錄量時CPU的性能優(yōu)于Xeon Phi,在較大記錄量時Xeon Phi的性能優(yōu)于CPU.PRO算法在CPU端的性能略優(yōu)于Xeon Phi端的性能,CPU較大的cache和較高的主頻更加有利于PRO算法性能的提高.

總體來說,AIR算法在較小維表時在Xeon Phi有較好的加速性能,PRO算法在Xeon Phi上也有接近一倍的性能提升(圖7和圖8中1塊Xeon Phi與2塊Xeon多核CPU性能接近).在當前PCI-E形式的Xeon Phi協(xié)處理器中,AIR算法更適合較小維表對應的外鍵連接操作,不僅維表代理向量傳輸代價低,而且能夠獲得較高的性能收益,當維表較大時,AIR算法更適合在CPU平臺上執(zhí)行.NPO算法則適合于較大維表的外鍵連接操作,但維表子集在PCI-E通道傳輸代價也相應較高.PRO算法雖然加速性比較穩(wěn)定,但其2倍的內存空間消耗降低了Xeon Phi協(xié)處理器內存的利用率.未來Xeon Phi KNL主處理器可以直接訪問內存數(shù)據(jù),更加適合較大表的外鍵連接操作加速.

圖8 TPC-DS外鍵連接算法性能對比Fig.8Performance comparison for foreign key join algorithms in TPC-DS

圖9 NVIDIA GPGPU K80外鍵連接算法性能對比Fig.9Performance comparison for foreign key join algorithms on NVIDIA GPGPU K80

我們用CUDA語言實現(xiàn)AIR算法,并在最新的NVIDIA GPGPU K80上執(zhí)行以上各Benchmark的外鍵連接性能測試.K80使用了4992個流處理器,具有極強的并行處理能力.圖9列出了本文所使用的SSB、TPC-H、TPC-DS、Workloads等Benchmark中的外鍵連接操作使用AIR算法(CPU)、AIR算法(Phi)、NPO(Phi)、PRO(Phi)以及AIR算法(GPU)時的查詢執(zhí)行總時間,其中AIR算法(GPU)執(zhí)行時間極短,我們使用了另一個較小的坐標軸標示其外鍵連接執(zhí)行時間.圖9中可以看到,AIR算法在2塊10核Xeon E5-2650 v3CPU上與1塊Xeon Phi 5110P協(xié)處理器上具有較好的外鍵連接執(zhí)行性能,均低于哈希連接算法NPO和PRO在Xeon Phi協(xié)處理器上的執(zhí)行時間.AIR算法在K80 GPU上的執(zhí)行時間幾乎為常量,穩(wěn)定在30-45微秒之間,其眾多的cuda核心、高并發(fā)內存訪問線程和高帶寬內存在AIR算法的代理外鍵內存訪問時有極高的性能.

以上實驗在中高端10核處理器Xeon E5-2650 v3、中端Xeon Phi 5110P協(xié)處理器、高端的NVIDIA GPGPU K80上的實驗結果證明了AIR算法對于cache優(yōu)化(Xeon E5-2650 v3、Xeon Phi 5110P)及并發(fā)內存訪問優(yōu)化(K80)都有較好的性能與適應性,適合在未來不對稱處理器平臺上面向計算密集型處理器的負載優(yōu)化,并通過先進硬件性能的優(yōu)化加速OLAP查詢整體性能.

4 結論

本文給出了一種面向未來不對稱內存計算平臺的OLAP查詢優(yōu)化技術,其主要設計思想體現(xiàn)在3個方面:①通過schema-conscious設計和代理鍵索引機制的優(yōu)化工作提出了基于代理向量參照訪問的外鍵連接技術,消除復雜的內存哈希表結構,簡化連接操作數(shù)據(jù)結構與算法設計,提高外鍵連接操作的代碼執(zhí)行效率,使算法更好地適應cache及并發(fā)多線程內存訪問機制,提高算法對cache-conscious和cache-oblivious設計的適應性;②通過對OLAP查詢處理過程的重組,將SPJGA操作分解為SPG+J+A三個計算階段,分別綁定較小的維表、固定大小的事實表外鍵列及較大的事實表度量列,實現(xiàn)數(shù)據(jù)密集型任務與計算密集型任務在數(shù)據(jù)集上的劃分,有效地分離了不同類型的負載,通過基于向量數(shù)據(jù)結構的優(yōu)化最小化三個計算階段之間的數(shù)據(jù)傳輸代價;③基于不同類型的不對稱計算及存儲架構提出了基于3階段計算模型的分布式存儲與計算策略,將數(shù)據(jù)密集型負載與計算密集型負載在通用處理器與計算型處理器之間優(yōu)化配置,通過新興的眾核協(xié)處理器加速決定OLAP性能的外鍵連接操作,達到提高性能和降低系統(tǒng)改寫代價的目標.

實驗結果表明,基于代理鍵索引機制和代理向量參照訪問的外鍵連接操作的性能較傳統(tǒng)的內存哈希連接算法具有更高的性能和更加簡單的實現(xiàn)技術,能夠更加靈活地適應以cache為中心和以并發(fā)內存訪問為中心的不同類型硬件體系結構,在通用CPU和眾核協(xié)處理器平臺均有較優(yōu)的性能,其簡化的算法設計進一步降低了遷移到未來眾核協(xié)處理器平臺的代價.

［1］SEBASTIAN ANTHONYIntel unveils new Xeon chip with integrated FPGA,touts 20x performance boost [EB/OL].(2014-01-19)[2015-12-25].http://www.extremetech.com/extreme/184828-intel-unveils-new-xeon-chipwith-integrated-fpga-touts-20x-performance-boost.

［2］JIM H.IBM launches flashDIMMs[EB/OL].(2014-01-20)[2015-12-25].http://thessdguy.com/ibm-launchesflash-dimms/.

［3］ANTON S.Intel:First 3D XPoint SSDs will feature up to 6GB/s of bandwidth[EB/OL].(2015-08-28)[2016-03-16].http://www.kitguru.net/components/memory/anton-shilov/intel-first-3d-xpoint-ssds-will-feature-up-to-6gbs-of-bandwidth/.

［4］BLANAS S,LI Y,PATEL J M.Design and evaluation of main memory hash join algorithms for multi-core CPUs [C]//SIGMOD.2011:37-48.

［5］BALKESEN C,TEUBNER J,ALONSO Get al Main-memory hash joins on multi-core cpus:Tuning to the underlying hardware[C]//ICDE.2013:362-373.

［6］ALBUTIU M-C,KEMPER A,NEUMANN T Massively parallel sort-merge joins in main memory multi-core data-base systems[J].VLDB Endowment,2012,5(10):1064-1075.

［7］HE B,YANG K,FANG Ret al.Relational joins on graphics processors[C]//SIGMOD.2008:511-524.

［8］YUAN Y,LEE R,ZHANG XThe yin and yang of processing data warehousing queries on GPU devices[J]. PVLDB,2013,6(10):817-828.

［9］PIRK H,MANEGOLD S,KERSTEN M L.Accelerating foreign-key joins using asymmetric memory channels [C]//ADMS@VLDB.2011:27-35.

［10］HE J,LU M,HE B.Revisiting co-processing for hash joins on the coupled CPU-GPU architecture[J].VLDB Endowment,2013,6(10):889-900.

［11］JHA S,HE B,LU M,et al.Improving main memory hash joins on Intel Xeon Phi processors:an experimental approach[J].Proceedings of TheVldb Endowment,2015,8(6):642-653.

［12］POLYCHRONIOU O,RAGHAVAN A,ROSS K A.Rethinking SIMD vectorization for in-memory databases [C]//SIGMOD Conference.2015:1493-1508.

［13］HALSTEAD R J,ABSALYAMOV I,NAJJAR W A,et al.FPGA-based Multithreading for In-Memory Hash Joins[C]//Conference on Innovative Data Systems Research.2015.

［14］ZHANG Y,ZHOU X,ZHANG Y,et al.Virtual Denormalization via Array Index Reference for Main Memory OLAP[J].IEEE Transactions on Knowledge and Data Engineering,2016,28(4):1061-1074.

［15］ALEKSIC S,CELIKOVIC M,LINK S,et al.Face off:Surrogate vs.natural keys[C]//Advances in Databases and Information Systems-14th East European Conference.2010:543-546.

［16］張宇,張延松,陳紅,等.GPU semi-MOLAP:一種適應GPU的混合OLAP查詢處理模型[J].軟件學報,2016,27(5): 1246-1265.

(責任編輯:李萬會)

Research on OLAP query processing technology for asymmetric in-memory computing platform

ZHANG Yan-song1-3,ZHANG Yu4,ZHOU Xuan1,3,WANG Shan1,2
(1.DEKE Lab,Renmin University of China,Beijing100872,China; 2.School of Information,Renmin University of China,Beijing100872,China; 3.National Survey Research Center at Renmin University of China,
Beijing100872,China; 4.National Satellite Meteorological Center,Beijing100081,China)

This paper proposes an OLAP query processing technology for nowadays and future asymmetric in-memory computing platform.Asymmetric in-memory computing platform means that computer equips with different computing feature processors and different memory access devices so that the OLAP processing model needs to be optimized fordifferent computing features and implementation designs to enable the different processing stages to adapt to the characteristics of corresponding storage and computing hardware for higher hardware utilization and performance.This paper proposes the 3-stage OLAP computing model,which divides the traditional iterative processing model into computing intensive and data intensive workloads to be assigned to general purpose processor with full fledged functions and coprocessor with powerful parallel processing capacity.The data transmission overhead between different storage and computing devices is also minimized. The experimental results show that the 3-stage OLAP computing model based on workload partitioning can be adaptive to CPU-Phi asymmetric computing platform,the acceleration on OLAP query processing can be achieved by accelerating computing intensive workload by computing intensive hardware.

in-memory computing;asymmetric computing platform;in-memory OLAP

TP311

A

10.3969/j.issn.1000-5641.2016.05.011

1000-5641(2016)05-0089-14

2016-05

國家863計劃項目(2015AA015307)；中央高?；究蒲袠I(yè)務費專項資金項目(16XNLQ02)；華為創(chuàng)新研究計劃(HIRP 20140507,HIRP 20140510)

張延松,男,博士,副教授,研究方向為內存數(shù)據(jù)庫.E-mail:zhangys ruc@hotmail.com.

張宇,女,博士,研究方向為OLAP,GPU數(shù)據(jù)庫.E-mail:zyszy511@hotmail.com.