劉 軍 冷芳玲 李宇軒

（1.東北大學信息化建設與網(wǎng)絡安全辦公室 沈陽 110819）（2.東北大學計算機科學與工程學院 沈陽 110819）

1 引言

具有強大算力的圖形處理器GPU近些年的發(fā)展十分迅猛，GPU從其自身的架構出發(fā)，不斷進行迭代更新以達到提升性能的目的。在GPU架構不斷演進的過程中，NVIDIA公司所發(fā)布的每一代GPU新架構都會添加新特性，例如高傳輸效率的零拷貝技術等。這些特性使得運行在GPU上的程序更加易用，內(nèi)部協(xié)同處理更加高效。在GPU推出伊始，編寫GPU程序需要紋理編碼等專業(yè)圖形處理領域的專業(yè)知識，因此編碼難度較高。但如今隨著Nvidia公司推出CUDA［1］通用并行計算架構，圖形卡上的編程難度逐漸降低，相關技術逐漸成熟，GPU被廣泛應用于人工智能、深度學習、高性能計算、大數(shù)據(jù)處理等通用計算領域。近年來，在基于異構體系平臺的數(shù)據(jù)庫存儲與管理方向的研究越來越受各界關注，已有不少成果應用于實際生產(chǎn)環(huán)境當中，例如Pgstorm憑借GPU強大的算力協(xié)同PostgreSQL數(shù)據(jù)庫加速任務的執(zhí)行，可以獲得性能上的巨大提升。目前，GPU編程技術在數(shù)據(jù)庫領域的應用還在不斷探索階段，切合GPU特性研究并實現(xiàn)的內(nèi)存索引所取得的科研成果數(shù)量遠遠不及傳統(tǒng)磁盤索引或基于CPU的主存索引，因此研究基于GPU的索引結構對加速數(shù)據(jù)查詢是十分必要的。充分考慮CPU的硬件特點，并結合GPU強大的并行能力共同執(zhí)行查詢?nèi)蝿?，以達到高效處理任務，降低查詢延遲的目的。本文提出并實現(xiàn)的加速數(shù)據(jù)庫查詢的系統(tǒng)核心就是一種基于CPU與GPU協(xié)同處理的B+-Tree索引。

2 相關工作

索引是加速數(shù)據(jù)庫查詢的重要策略。針對索引的優(yōu)化是加速數(shù)據(jù)查詢速度最好的方式之一。構建基于GPU的樹形索引是目前異構環(huán)境下加速數(shù)據(jù)庫操作的主流方法之一。Rao等實現(xiàn)了基于局部性原理和緩存特性設計的樹形索引結構CSS-Tree［2］和CSB+-Tree［3］。Fang［4］等將圖形顯卡的計算能力同索引結構結合在一起，實現(xiàn)了基于GPU的CSS-Tree。T-Tree［5］是一種在節(jié)點內(nèi)包含多個鍵的平衡二叉樹結構，用于將索引信息和數(shù)據(jù)記錄都駐留在主存中。Liu［6］等在GPU平臺上利用N個線程并行化構建N個節(jié)點的方式來迅速構建起T-Tree索引結構。R-Tree［7］作為廣泛被使用的空間索引技術，應用GPU來深入挖掘出其在大規(guī)模的空間數(shù)據(jù)下的查詢處理潛力。You［8］等所提出的R-Tree使用基于GPU的并行查詢處理技術，實現(xiàn)了較八核CPU并行實現(xiàn)方案的十倍提速。

Daga等［9］介紹了一種利用異構計算平臺APU加速B+-Tree搜索的技術。Fix［10］等提出了一種在GPU中以線程塊為單位編織查詢?nèi)蝿盏乃惴?。針對將?shù)據(jù)庫應用移植到GPU上的問題，Kaczmarski［11］等基于數(shù)據(jù)庫中的B+-Tree索引結構和數(shù)據(jù)頁的管理策略提出了一種用二維數(shù)組來表示B+-Tree的索引結構。Kaczmarski［12］等相繼又提出了可以高效創(chuàng)建GPU上的B+-Tree索引算法。Huang［13］等介紹了一種在GPU上的批處理構建和插入算法CUBPT。隨著并發(fā)查詢量和數(shù)據(jù)規(guī)模的增加，Yan［14］等提出了一種面向查詢吞吐量的新型B+-Tree索引Harmonia，可以激發(fā)GPU上低延遲的高速緩存的性能。Ashkiani［15］等提供了一種與B-Tree具有相同操作特性的動態(tài)GPU日志結構合并樹LSM，在GPU平臺上通過減少或消除線程訪問節(jié)點時的競爭實現(xiàn)了一種可變鍵值存儲［16］的B-Tree。綜合現(xiàn)有索引研究成果的優(yōu)缺點，更好地聯(lián)合使用CPU和GPU的內(nèi)存資源與并行計算能力，構建面向查找密集型場景的B+-Tree索引，是本文所實現(xiàn)的基于GPU加速的數(shù)據(jù)庫查詢系統(tǒng)的研究重點。

3 面向GPU的HPGB+-Tree索引

由于CPU與GPU硬件構造不同導致存在較大的差異性，基于CPU的B+-Tree索引結構和查詢方式并不適用于GPU。例如，孩子節(jié)點的尋址采用二分法確定目標鍵的定位方式等在GPU上均表現(xiàn)不佳。因此對B+-Tree索引結構重構使其適應GPU的硬件特性是當前研究的重點之一。隨著索引大小的增長，CPU的性能受到內(nèi)存帶寬的限制［17］，而GPU的內(nèi)存架構足夠高效，所以其內(nèi)存帶寬足夠高。但是GPU中可用的內(nèi)存空間與CPU可用的主機內(nèi)存相比十分有限。因此在數(shù)據(jù)量較大的情況下，B+-Tree索引在GPU上的擴展能力會受到限制，所以如何結合CPU與GPU的內(nèi)存特性構建基于GPU的B+-Tree索引結構是值得研究的問題。

本文所提出的HPGB+-Tree索引結構是基于傳統(tǒng)的B+-Tree索引結構進行重構和設計的。B+-Tree索引最早被提出用于磁盤索引［18］，核心結構是平衡多路排序樹。B+-Tree只在葉子節(jié)點中存儲實際數(shù)據(jù)，內(nèi)部節(jié)點就有足夠的空間去容納更多的鍵值。B+-Tree不同于二叉樹，每個節(jié)點對應的盤塊所容納的鍵值數(shù)量遠超二叉樹，所以B+-Tree的高度就會遠低于二叉樹，因此B+-Tree的搜索操作只需要很少的磁盤I/O次數(shù)就可以定位到含有目標鍵的葉頁。無論是內(nèi)部節(jié)點還是葉子節(jié)點都通過二分搜索查找目標鍵值。在B+-Tree的索引結構中，含有m棵子樹的節(jié)點最多含有m個候選鍵。在葉子節(jié)點中存儲的候選鍵是有序的，并且葉子節(jié)點間通過指針鏈接。因此，B+-Tree很好地支持了高效的范圍查詢。B+-Tree另外一個特性是在執(zhí)行不同的查詢?nèi)蝿諘r，B+-Tree總會遍歷相同長度的路徑，這就使查詢?nèi)蝿盏呢撦d較為均衡，查詢效率較為穩(wěn)定。目前B+-Tree索引已被廣泛應用在數(shù)據(jù)庫當中，如關系型數(shù)據(jù)庫MySQL等。如圖1所示，是一棵傳統(tǒng)的B+-Tree示意圖。

圖1 傳統(tǒng)B+-Tree

HPGB+-Tree的索引結構是由傳統(tǒng)B+-Tree轉換而來，存在于主機端的傳統(tǒng)B+-Tree有三種重要的用途：1）用于計算HPGB+-Tree索引相關的元數(shù)據(jù)信息，如新索引在內(nèi)存中所需空間大小等。2）作為原始材料構建HPGB+-Tree索引結構并初始化索引數(shù)據(jù)。3）HPGB+-Tree索引是面向查詢密集型的索引結構，因此數(shù)據(jù)插入采取從主機端的B+-Tree以批量、異步的方式進行，再同步至GPU。

在對HPGB+-Tree索引樹的節(jié)點Knode進行設計時，選擇用結構體數(shù)組的方式組織關鍵字和分支信息，而不是用數(shù)組結構體。這是因為并行計算架構CUDA在操作細粒度數(shù)組如結構體數(shù)組（SoA），即結構體中的元素是數(shù)組時是很友好的。但是在操作粗粒度數(shù)組如數(shù)組結構體（AoS），即數(shù)組中的元素是結構體時，在性能測試中表現(xiàn)為訪存利用率較低。

結構體在內(nèi)存中是一片連續(xù)的內(nèi)存空間，應用SoA的方式可以帶來內(nèi)存讀寫性能的巨大提升。對全局內(nèi)存帶寬的充分利用，是提高內(nèi)核函數(shù)效率和減少帶寬浪費的重要手段。在樹的搜索過程中，每次會從內(nèi)存里讀取一個節(jié)點進行判斷。由此可知，采用SoA的方式構建樹的節(jié)點，可以更好地利用內(nèi)存資源，同時更方便實現(xiàn)對齊與合并訪問內(nèi)存，將節(jié)點所在的內(nèi)存塊加載進緩存中，優(yōu)化訪存速度。

索引樹的每個節(jié)點都是由結構體數(shù)組Knode表示，如圖2所示。每個Knode包含三部分：候選鍵數(shù)組、子位置數(shù)組以及節(jié)點相關元信息。

圖2 HPGB+-Tree索引節(jié)點結構

在候選鍵數(shù)組Keys中，連續(xù)存放著節(jié)點內(nèi)待比較的關鍵字，用于在查找目標鍵時確定一條準確的路徑。在子位置數(shù)組Indices中，存儲的是當前節(jié)點的所有孩子節(jié)點的地址。每一個元素相當于傳統(tǒng)B+-Tree內(nèi)部節(jié)點的指針域中存放的其孩子節(jié)點的指針。節(jié)點相關元信息包括用于標識節(jié)點是否為葉子節(jié)點的標記符isLeaf，用于標識構建進度的標記Location，以及用于標識當前節(jié)點中候選鍵個數(shù)的標記numsOfkey。這種節(jié)點設計的好處在于不僅可以高效率的訪存，還能夠迅速定位搜索路徑上孩子節(jié)點的位置加速查詢?nèi)蝿盏膱?zhí)行。

為使GPU的并行計算能力物盡其用，同時考慮到GPU上的內(nèi)存容量有限，而CPU上并沒有這方面的瓶頸。因此本文聯(lián)合使用主機內(nèi)存與設備內(nèi)存，將索引結構分散在兩硬件平臺之中。具體來講，HPGB+-Tree索引整體分為兩部分，一部分存在于主機內(nèi)存中，包括索引樹Knodes以及實際數(shù)據(jù)Records。另一部分存在于GPU的設備內(nèi)存中，這部分是位于主存內(nèi)索引樹Knodes的拷貝鏡像，這是由于Records中的元素存儲的是實際數(shù)據(jù)，所占空間較索引樹Knodes要大得多，不僅占用顯存珍貴的內(nèi)存資源，而且向顯存的數(shù)據(jù)傳輸也十分耗時。在第一部分中，Knodes的類型是以AoS方式組織而成的數(shù)組結構體，Knodes將遍歷傳統(tǒng)B+-Tree節(jié)點轉換而來的結構體Knode作為數(shù)組元素。Records是將每條實際數(shù)據(jù)Record作為數(shù)組元素，將數(shù)據(jù)記錄按順序存儲在內(nèi)存當中，支持以O（1）的時間復雜度Records中獲取到記錄。值得一提的是，Record依據(jù)使用場景的不同，既可以是一個具體的值或一條數(shù)據(jù)記錄的主鍵，也可以是一條具有多個數(shù)值字段的記錄。

在第二部分中，存在于GPU上的索引樹是主存里Knodes的一個拷貝，也是憑借GPU高性能并行計算的優(yōu)勢來執(zhí)行查詢?nèi)蝿盏闹饕僮鲗ο?，具體的拷貝過程是將Knodes從主機內(nèi)存?zhèn)鬏數(shù)皆O備內(nèi)存中開辟的緩沖區(qū)內(nèi)。HPGB+-Tree索引會長久地駐留在設備內(nèi)存中，被多個查詢?nèi)蝿展蚕?。另外，在加載或構建多個HPGB+-Tree索引時，多個緩沖區(qū)會在邏輯上組成索引池，而具體的信息維護工作由CPU負責。如圖3所示，是在異構環(huán)境下HPGB+-Tree索引結構的示意圖。在主存中的HPGB+-Tree索引構建算法偽代碼如表1所示。

圖3 HPGB+-Tree索引結構

表1 主機到設備數(shù)據(jù)傳輸測試實驗結果

HPGB+-Tree索引構建算法如下所示。

TRANSFORM_HPGB（root）

1）function TRANSFORM_HPGB（root）

2）Krecords←mallocCpuLeaves（）

3）Knodes←mallocCpuNodes（）

4）queue←enqueue（root）

5）while queue！=null do

6）curNode←dequeue（）

7）initKey（curNode）

8）if node！=leaf then

9） init_indice（curNode）

10） while index

11） next←curNode［index］

12） initIndice（next）

13） queue←enqueue（next）

14） end while

15）end if

16）if curNode==leaf then

17） while index

18） initRecord（curNode）

19） end while

20）end if

21）end while

22）end function

4 實驗分析與性能測試

為了驗證HPGB+-Tree索引為數(shù)據(jù)庫查詢系統(tǒng)帶來的查詢性能的提升，本節(jié)將對基于混合架構的索引算法HPGB+-Tree進行實驗測試。為驗證索引在混合架構下相比于單一架構的優(yōu)勢，本文選擇Aviram［19］提出的基于CPU的高查詢性能的無鎖B+-Tree索 引，F(xiàn)ix等 提 出 的GPU B+-Tree索 引Braided B+-Tree和前期研究成果即其優(yōu)化版本Optimized Braided B+-Tree來進行索引性能的對比實驗。本節(jié)將從實驗環(huán)境，實驗數(shù)據(jù)，實驗方式以及實驗結果與分析來組織內(nèi)容。主要對HPGB+-Tree索引算法進行三個方面的實驗測試：1）數(shù)據(jù)傳輸實驗測試。2）HPGB+-Tree索引的相關參數(shù)實驗測試。3）基于最佳參數(shù)配置的HPGB+-Tree索引等值查詢與范圍查詢的性能表現(xiàn)實驗測試。

4.1 實驗環(huán)境

硬件配置：顯卡GPU為NVIDIA 1660Ti，處理器為CPUIntel i7 9700，內(nèi)存16GB，磁盤512GB SSD；軟件配置：操作系統(tǒng)為Ubuntu 18.04，CUDA運行環(huán)境為CUDA 9.0，開發(fā)IDE為Vscode，CUDA代碼編譯器為NVCC，C編譯器為gcc 4.8，C++編譯器為g++4.8，構建工具為Make。

4.2 實驗數(shù)據(jù)和方式

本文進行的實驗采用的數(shù)據(jù)是隨機生成的數(shù)據(jù)記錄，記錄形式為一張在關系型數(shù)據(jù)庫中具有多個字段的行記錄組成的一張二維表。生成的數(shù)據(jù)記錄中的每個字段均為四字節(jié)的整型數(shù)值，該二維表內(nèi)數(shù)據(jù)記錄的行數(shù)范圍為十萬量級到千萬量級。

本文選擇任務的執(zhí)行時間作為評價指標來衡量本系統(tǒng)內(nèi)部實現(xiàn)的HPGB+-Tree索引核心算法的性能。

在CUDA架構中，主機端的內(nèi)存分為可分頁內(nèi)存與鎖頁內(nèi)存，如表1和表2所示，是由長度為4字節(jié)的整型組成不同規(guī)模數(shù)據(jù)量，使用兩種不同類型內(nèi)存進行主存與設備內(nèi)存之間的數(shù)據(jù)傳輸測試。

表2 設備到主機數(shù)據(jù)傳輸測試實驗結果

本部分測試不同的HPGB+-Tree索引階數(shù)對執(zhí)行查詢?nèi)蝿账俣鹊挠绊?，確定最大化查詢執(zhí)行效率的最佳索引階數(shù)。分別在不同數(shù)據(jù)規(guī)模下構建32階、128階和512階的HPGB+-Tree索引，然后在系統(tǒng)默認配置五個CUDA流的條件下，批量執(zhí)行十萬個等值查詢?nèi)蝿?。實驗結果如圖4所示。在索引階數(shù)為32時，執(zhí)行時間消耗最小，達到執(zhí)行查詢?nèi)蝿盏淖罴研阅堋?/p>

圖4 不同索引階數(shù)的查詢效率

本文所提出的HPGB+-Tree索引繼承了B+-Tree索引的優(yōu)勢，葉子節(jié)點存儲的數(shù)據(jù)記錄是有序的，并且連續(xù)存儲在一塊內(nèi)存區(qū)域中。因此，HPGB+-Tree索引既支持等值查詢，又支持范圍查詢。本文選用傳統(tǒng)B+-Tree、基于GPU的Braided B+-Tree和Braided B+-Tree的優(yōu)化版本Optimized Braided B+-Tree作為實驗對比對象，進行等值查詢與范圍查詢的實驗測試。

等值查詢的實驗是在索引階數(shù)為32和等值查詢?nèi)蝿找?guī)模為一萬的實驗條件下，對在216~224不同規(guī)模的數(shù)據(jù)下構建的四種索引，進行等值查詢的對比實驗。實驗結果如圖5所示。

圖5 不同數(shù)據(jù)規(guī)模下的等值查詢

由于傳統(tǒng)坐標系無法清晰表現(xiàn)出幾種索引的性能差距，因此繪制為同x雙y坐標系的柱狀圖。其中傳統(tǒng)B+-Tree與Braided B+-Tree索引執(zhí)行等值查詢?nèi)蝿諘r間消耗較多，所以使用左側跨度較大的坐標系，而Optimized Braided B+-Tree與HPGB+-Tree索引執(zhí)行等值查詢?nèi)蝿諘r間消耗較少，因此使用右側跨度較小的坐標系。其中隨著索引數(shù)據(jù)規(guī)模的增大，CPU的執(zhí)行時間消耗也逐漸變大，并且執(zhí)行效率遠遠低于借助高性能硬件平臺GPU的其他索引結構。Braided B+-Tree每次執(zhí)行任務都要將索引文件重新傳遞到設備內(nèi)存的臨時緩沖區(qū)中，因此隨數(shù)據(jù)規(guī)模增大，索引文件所占內(nèi)存也增大，由此造成的數(shù)據(jù)傳輸時延會導致執(zhí)行效率與內(nèi)核占用率不斷降低。在執(zhí)行等值查詢?nèi)蝿諘r，本文提出的HPGB+-Tree索引算法比Optimized Braided B+-Tree執(zhí)行效率高近三倍。

范圍查詢實驗是在216~224的數(shù)據(jù)規(guī)模下分別構建階數(shù)為32的四種索引，并進行一萬次隨機選取區(qū)間范圍為一百的范圍查詢測試，實驗結果如圖6所示。

圖6 不同數(shù)據(jù)規(guī)模下的范圍查詢

為了更好表現(xiàn)出幾種索引進行范圍查詢的實驗效果，坐標系構造方式與圖3中等值查詢實驗所繪制的同x雙y坐標系構造相同。其中x軸代表各個不同的數(shù)據(jù)規(guī)模，左側跨度較大的y軸用于標記傳統(tǒng)B+-Tree與Braided B+-Tree索引處理范圍查詢?nèi)蝿盏膱?zhí)行時間，右側跨度較小的y軸用于標記Optimized Braided B+-Tree與HPGB+-Tree索 引 處理范圍查詢?nèi)蝿盏膱?zhí)行時間。

范圍查詢的執(zhí)行邏輯與等值查詢?nèi)蝿疹愃疲欠秶樵內(nèi)蝿招枰獟呙韬Y選出符合條件的左右邊界內(nèi)所有的目標值，導致CPU執(zhí)行任務的消耗時間更加長，查詢效率更加低。Braided B+-Tree索引在執(zhí)行范圍查詢?nèi)蝿諘r仍需要重新傳輸索引結構與數(shù)據(jù)。在數(shù)據(jù)量較小時，由于PCIe傳輸?shù)母邘拰ζ湓斐傻挠绊懖淮?。但隨數(shù)據(jù)量級的增大，其影響越來越明顯，表現(xiàn)為任務的執(zhí)行時間逐漸接近CPU。Optimized Braided B+-Tree索引在執(zhí)行范圍查詢?nèi)蝿諘r避免傳輸索引結構和數(shù)據(jù)的代價，同時優(yōu)化了內(nèi)核程序，使其可以較為高效地獲取符合條件的目標鍵范圍。因此執(zhí)行時間較短，查詢效率較高。

本文提出的基于HPGB+-Tree索引范圍查詢算法在數(shù)據(jù)傳輸、任務分配和內(nèi)核程序等方面都進行了優(yōu)化，相比于Optimized Braided B+-Tree索引，其執(zhí)行效率提升近三倍。

5 結語

目前GPU應用于在數(shù)據(jù)庫領域的研究還處于不斷探索的階段，而索引作為加速數(shù)據(jù)庫檢索數(shù)據(jù)的重要技術手段，現(xiàn)有的研究大多數(shù)為磁盤索引或主存索引且已非常成熟，因此對利用新硬件平臺GPU突破索引性能瓶頸的研究具有重要的意義。

本文提出了一種CPU與GPU協(xié)同構建和處理的HPGB+-Tree索引算法，該算法實現(xiàn)索引結構的并行化設計，使其更加切合GPU的硬件特性。同時將實際數(shù)據(jù)記錄存儲于容量較大的主存中，索引樹的節(jié)點拷貝到帶寬較高的顯存中，解決了CPU內(nèi)存帶寬瓶頸和GPU內(nèi)存容量受限的問題。在未來的工作中，我們將會研究如何將以HPGB+-Tree索引技術為核心，開發(fā)MySQL的擴展模塊。