吳婧雅 盧文巖 鄢貴海 李曉維

1 （處理器芯片全國重點實驗室（中國科學院計算技術研究所）北京 100190）

2 （中國科學院大學 北京 100049）

索引是數(shù)據(jù)庫中用來加速數(shù)據(jù)查詢的一種常用數(shù)據(jù)結構.其中，B+樹憑借其獨特優(yōu)勢成為關系型數(shù)據(jù)庫中最常用的索引結構.相較于其他索引結構，B+樹具有3 個優(yōu)勢：

1）數(shù)據(jù)存儲結構規(guī)則.利用關鍵字數(shù)據(jù)結構以平衡樹維護，能夠提升數(shù)據(jù)查詢效率.且樹的所有內部節(jié)點只存儲索引關鍵字（即鍵值），索引信息更密集，降低查詢I/O 開銷.

2）查詢開銷穩(wěn)定.關鍵字指向的實際數(shù)據(jù)只在葉子節(jié)點中存儲.由此，查詢時需要逐層遍歷各層內部節(jié)點直到葉子節(jié)點結束，查詢開銷穩(wěn)定.

3）提升范圍查詢性能.葉子節(jié)點以有序鏈表相連，支持范圍查詢依序訪問葉子節(jié)點，避免對樹的多次遍歷，使范圍查詢更高效.

然而，B+樹索引的高度有序性使得大數(shù)據(jù)場景下索引查詢效率降低、索引維序開銷增加，成為限制數(shù)據(jù)庫性能提升的瓶頸.總結大數(shù)據(jù)場景下B+樹性能提升面臨的3 個挑戰(zhàn)：

1）訪存性能低.關鍵字查詢通過逐層定位節(jié)點實現(xiàn).由于節(jié)點內關鍵字比較結果的不確定性導致對下一層子節(jié)點的訪問是隨機的.這種隨機內存訪問使內存帶寬利用異常低效.

2）并行性差.由于查詢需要逐層遍歷節(jié)點才能完成，中間結果的不確定性導致逐層遍歷難以實現(xiàn)并行，索引帶來的優(yōu)勢被削弱.

3）樹的維序難度大.索引維序（索引刪除、插入和修改，其中1 次修改可以看作是1 次刪除和1 次插入的組合）過程會影響樹中間各層節(jié)點鍵值的存儲狀態(tài).索引維序導致葉子節(jié)點內數(shù)據(jù)增加或減少，并改變葉子節(jié)點內關鍵字順序；取決于節(jié)點內存儲空間容量的限制，也有可能導致中間節(jié)點結構的改變.這種不確定的節(jié)點狀態(tài)改變，使葉子節(jié)點內關鍵字維序和中間節(jié)點更新復雜且效率低.

由此，如何平衡B+樹的查詢和維序性能，以及在大數(shù)據(jù)場景下進一步提升索引的查詢和維序效率，成為索引優(yōu)化的關鍵.

隨著通用計算平臺性能提升放緩[1]，許多研究提出利用GPU 和FPGA 等異構計算平臺加速B+樹的查詢和維護操作[2-4].為充分發(fā)揮GPU 異構系統(tǒng)的算力，多數(shù)研究從提升索引查詢性能和緩解內存帶寬瓶頸等角度提出解決方法.在SIMD 架構的平臺中，文獻[5-7]提出了提升多條查詢語句并行效率的策略以提升GPU 對B+樹的查詢效率.文獻[8-9]則優(yōu)化了索引節(jié)點的存儲結構，以緩解GPU 的內存帶寬瓶頸.這些研究將重點放在提升索引查詢的性能.利用FPGA 這一類可重構計算架構，文獻[10-11]利用FPGA 分別設計了支持索引的查詢和更新操作的專用計算引擎，并評估了利用FPGA 加速不同體量索引對系統(tǒng)整體性能的影響.但是文獻[10-11]方法欠缺對索引查詢和更新的協(xié)同優(yōu)化，沒有提出B+樹索引系統(tǒng)的均衡優(yōu)化方案.

為均衡提升大數(shù)據(jù)場景下數(shù)據(jù)庫索引的查詢和維護性能，本文系統(tǒng)研究了B+樹索引的查詢和維序的操作特性，提出針對索引訪存和計算的協(xié)同優(yōu)化加速器架構HyperTree，在大數(shù)據(jù)場景中，兼顧索引的查詢和維序性能的提升.本文的主要貢獻點：

1）提出一種同構的流式計算多引擎架構，既能夠提升單計算引擎的效率，又支持多索引查詢、更新和維序任務的并行；

2）提出一種規(guī)則的B+樹節(jié)點存儲格式，同時設計專用的內存管理系統(tǒng)以支持低開銷的并行訪存，進一步提升內存帶寬利用效率；

3）提出一種高效靈活的計算控制系統(tǒng)，支持多指令并行和多數(shù)據(jù)并行，在提升計算引擎性能的同時，不會引入額外開銷；

4）提出一種多子樹結構，將復雜的B+樹拆分為幾棵小的子樹，避免葉子節(jié)點的更新沖突，以提升索引的維序效率.

實驗結果表明，相比于CPU，B+樹索引加速系統(tǒng)HyperTree 能夠提升系統(tǒng)查詢性能6.84 倍；范圍查詢性能提升14.53 倍，且相比單值查詢性能損失很小，平均為單值查詢性能的75.58%；引入子樹存儲管理系統(tǒng)后，索引維序性能提升超過29.14 倍.

1 研究背景

典型的B+樹結構如圖1 所示.內部節(jié)點稱為索引節(jié)點，按照升序排列存儲關鍵字；葉子節(jié)點既存儲關鍵字又記錄關鍵字指向的數(shù)據(jù)信息.

Fig.1 Keyword search in B+tree圖1 B+樹的關鍵字查詢

B+樹查詢操作從根節(jié)點開始，自頂向下逐層比較內部節(jié)點的索引關鍵字范圍，直到找到包含查詢內容的葉子節(jié)點.以圖1 所示的等值查詢目標關鍵字11 為例.從根節(jié)點開始，將11 與關鍵字2 和10 比較，定位下一層節(jié)點應指向根節(jié)點最右側子節(jié)點.再重復上述范圍比較，定位下一層應指向當前節(jié)點最左側子節(jié)點.此節(jié)點為B+樹的葉子節(jié)點，在葉子節(jié)點中定位關鍵字11 指向的原數(shù)據(jù)庫表，結束本次查詢.范圍查詢可以通過等值查詢定位的葉子節(jié)點間的指針依次比較關鍵字得到查詢結果.

B+樹查詢性能取決于樹的高度（逐層查找）、節(jié)點大?。ㄖ饌€數(shù)據(jù)比較）及關鍵字匹配速度.例如：高度為l的B+樹所需查詢時間為l次節(jié)點讀取的I/O 延時和mi×l次計算引擎的關鍵字比較處理時間（mi為各節(jié)點關鍵字比較的次數(shù)）.由此，索引節(jié)點的I/O 開銷和關鍵字比較成為限制索引查詢性能的瓶頸.

B+樹的維序過程由數(shù)據(jù)庫表的插入、刪除和更新操作引起.以索引插入為例，首先通過查詢定位關鍵字待插入的葉子節(jié)點位置，然后插入關鍵字.插入前需要判斷插入新關鍵字后葉子節(jié)點是否超過規(guī)定長度.若沒有超過則結束本次索引插入，否則將該葉子節(jié)點平均分裂為2 個新葉子節(jié)點，并用新分裂的節(jié)點信息更新其父節(jié)點.更新時，將新分裂的右側葉子節(jié)點的第1 個索引關鍵字插入父節(jié)點原關鍵字，并更新葉子節(jié)點間指針.葉子節(jié)點更新結束后，依層向上重復節(jié)點更新過程，直到不需要拆分父節(jié)點或找到根節(jié)點，結束索引插入.刪除與插入過程類似，區(qū)別在于刪除可能導致節(jié)點合并，索引更新由刪除和插入組成.以圖2 所示插入關鍵字4 為示例.首先定位關鍵字4 應寫入的葉子節(jié)點位置.此時插入新關鍵字后的葉子節(jié)點超過規(guī)定長度，將該葉子節(jié)點分裂為2 個新節(jié)點，依大小順序在父節(jié)點插入索引值4，同時更新父節(jié)點指針.更新后父節(jié)點長度未超過規(guī)定長度，結束更新過程.

Fig.2 Keyword insertion in B+tree圖2 B+樹的關鍵字插入

數(shù)據(jù)表的更新，需要首先對葉子節(jié)點定位，再修改關鍵字.由于節(jié)點存儲空間的限制還有可能向上分裂或合并中間節(jié)點.不確定的多層節(jié)點操作會引入隨機I/O 讀寫，使得數(shù)據(jù)表維序的開銷相對于查詢來說大大增加.

2 相關工作

在大數(shù)據(jù)時代，內存數(shù)據(jù)庫的出現(xiàn)一定程度上解決了傳統(tǒng)硬盤數(shù)據(jù)庫的讀寫延遲問題[2].然而通用計算卻不足以提供有效算力支持以充分利用內存讀寫帶寬資源[1].研究人員轉而利用異構計算平臺，實現(xiàn)全卸載或半卸載的內存數(shù)據(jù)庫加速方案提升數(shù)據(jù)庫的計算效率[2-4].

為提升B+樹的查詢效率，大量研究基于GPU 異構計算平臺設計高效的并行架構[2]，主要優(yōu)化方向為加速索引查詢[5-6,8]及索引結構優(yōu)化[7,9,12].GPU 加速索引操作的核心思想是改進查詢的計算模式以充分適配GPU 的SIMD 架構.文獻[5]基于AMD 的CPU+GPU異構系統(tǒng)，提出了粗細粒度2 種并行策略以加速B+樹的查詢.細粒度并行策略將節(jié)點的二分查找替換為K-ary 查找，從而使計算引擎執(zhí)行相同模式的查詢操作；粗粒度并行策略利用同構的計算引擎同時執(zhí)行多條查詢.訪存優(yōu)化主要是調整B+樹內部節(jié)點為規(guī)則的數(shù)據(jù)結構，從而充分利用GPU 的高訪存帶寬.文獻[7]設計了一種將索引關鍵字和子節(jié)點指針分布存儲的改進樹形結構，以充分利用GPU 的內存帶寬；并利用SIMD 計算方法設計基于排序的并行查詢方法，進一步緩解查詢時的內存帶寬瓶頸.文獻[12]優(yōu)化節(jié)點內部存儲結構，解決訪存瓶頸，進一步提升查詢并行計算效率.

充分發(fā)揮GPU 的并行性能極強地依賴于計算規(guī)則且訪存對齊[2].然而索引操作天然具有計算并行難度大、訪存隨機性等問題，導致利用GPU 加速索引操作的性能提升效果有限，從而有一些文獻提出利用可重構硬件加速器設計更加靈活高效的方案.文獻[10]利用FPGA 設計了加速B+樹索引查詢的專用體系結構.利用片上BRAM 存儲部分內部節(jié)點地址以達到快速訪問內部節(jié)點的目的，同時設計專用并行查詢計算單元，能夠支持節(jié)點內關鍵字的快速定位；而葉子節(jié)點和一些低層內部節(jié)點的查詢及全部索引維序依靠CPU 實現(xiàn).文獻[11]補充了文獻[10]的研究工作，設計并行的節(jié)點更新計算單元，同時在CPU 端增加1 個調度單元部分卸載索引更新至FPGA，即FPGA 僅處理索引更新的部分操作，一定程度上提升了FPGA 加速B+樹索引的效果.文獻[10-11]利用FPGA 作為通用計算CPU 的補充：CPU 負責數(shù)據(jù)和指令的卸載，將根節(jié)點和部分上層內部節(jié)點卸載到FPGA 上加速查詢和更新.但這種方法是半卸載的方案，CPU 仍然需要負責主要的計算，F(xiàn)PGA 僅完成部分協(xié)同工作；且該方法的實現(xiàn)對FPGA 的計算資源和存儲空間利用效率很低，指令并行性差，B+樹索引的性能提升有限.此外，文獻[10-11]將優(yōu)化的CBS+樹結構作為數(shù)據(jù)庫的索引格式，雖然降低數(shù)據(jù)傳輸開銷及FPGA 端地址計算復雜度，但給系統(tǒng)引入了額外的索引格式轉換開銷.

近年來，隨著FPGA 板卡內存空間和帶寬性能的不斷提升，利用FPGA 加速內存數(shù)據(jù)庫性能提升顯著[2,4].鑒于FPGA 結構更加靈活、資源可配置等特性，本文基于FPGA 異構計算平臺，設計并實現(xiàn)了全卸載B+樹索引加速系統(tǒng)HyperTree——將索引的存儲，B+樹構建，索引查詢，索引插入、刪除和修改全部寫到FPGA 執(zhí)行.在本文所提出的 CPU-FPGA 構成的異構計算系統(tǒng)中，CPU 只負責查詢計劃的生成和優(yōu)化以及加速器的啟動運行和管理.

3 B+樹性能瓶頸分析

基于第1 節(jié)對B+樹典型操作的描述，本節(jié)將對B+樹各操作性能瓶頸進行深入分析.

3.1 數(shù)據(jù)隨機訪存造成存儲帶寬利用率低下

B+樹查詢時內存帶寬利用非常低效：一是由于節(jié)點的隨機訪存；二是由于樹的訪存管理復雜.在B+樹索引查詢時，下層節(jié)點的訪存地址由當前層節(jié)點內部關鍵字的比較結果決定.結果的不確定性導致每層節(jié)點的訪存是隨機的，且中間節(jié)點在內存中依靠指針相連，每個節(jié)點的數(shù)據(jù)結構不完全相同，節(jié)點的物理地址也是隨機的，進一步增加訪存隨機性.B+樹的存儲管理需要對內存空間動態(tài)維護.當執(zhí)行索引插入和刪除操作時，可能需要動態(tài)申請或釋放內存空間.為維護節(jié)點的樹形結構，需要動態(tài)修改對應的內存空間狀態(tài)，該過程的存儲訪存也是隨機的.此外，數(shù)據(jù)量的增加導致實際應用中B+樹標準格式規(guī)定的節(jié)點存儲空間無法完整保存1 個數(shù)據(jù)表內的全部索引信息.從而維護1 個數(shù)據(jù)表索引需要管理多棵B+樹，進一步加劇了內存空間管理的困難.這種數(shù)據(jù)訪存隨機性導致的問題無論是CPU 還是GPU 都無法直接解決，也是導致GPU 的高訪存帶寬無法被直接有效利用的根本原因.

為驗證隨機內存訪問帶寬的性能，通過實驗在實際數(shù)據(jù)庫中測試DDR4-3200 內存訪存特性（其標稱內存帶寬為204.8 Gbps）.隨著讀寫地址空間范圍的增加，實際讀寫帶寬有一定提升，但只有訪存達到突發(fā)讀寫長度時，理論最大帶寬才能被充分利用.如圖3 的實驗結果顯示，單字讀寫、隨機讀寫帶寬實際只能將近標稱性能的60%，甚至更低.

Fig.3 Practical efficient read/write bandwidth of DDR4圖3 DDR4 的實際有效讀寫帶寬

3.2 查詢并行度低下影響查詢性能

單節(jié)點的查詢和比較難以并行，是大數(shù)據(jù)量下查詢性能下降的關鍵原因.在B+樹設計中，為優(yōu)化中間節(jié)點訪存帶寬，可以通過盡可能擴大中間節(jié)點容量（節(jié)點內數(shù)據(jù)連續(xù)存儲）的方法實現(xiàn).然而，中間節(jié)點數(shù)據(jù)量的增加加劇了節(jié)點內關鍵字查找的難度.有研究表明，利用GPU 加速索引操作，即使是改進的算法，例如順序查找、二分查找、并行查找，單條查詢的性能提升仍然十分有限[6].

多查詢語句并行是進一步提升系統(tǒng)性能的關鍵.但現(xiàn)有的CPU-GPU 異構系統(tǒng)由于無法在隨機訪存時充分利用內存帶寬，且查詢時計算結果隨機性強，從而難以提升并行度[5-6,12].對于樹的訪存來說，有限的內存帶寬無法滿足多處理引擎對數(shù)據(jù)讀寫速度的需求；且每次訪存的地址空間范圍有限，進一步降低讀寫效率.對于計算來說，處理引擎的比較和查找能力決定了單條查詢語句的效率，而處理引擎的數(shù)目決定了查詢的并行度上限.當單引擎的計算性能受限時，并行帶來的性能提升十分有限.

3.3 更新維序復雜大大降低插入性能

索引提升了數(shù)據(jù)查詢的效率，但樹形結構的高度有序性使索引維序操作復雜.修改數(shù)據(jù)庫表記錄，包括記錄的增加、刪除或更新，需要同時修改索引.索引的維序對修改數(shù)據(jù)庫表記錄造成額外開銷.以索引的插入為例，受限于節(jié)點容量的限制，關鍵字插入可能引起節(jié)點分裂.節(jié)點內數(shù)據(jù)量一旦超過容量閾值，節(jié)點的分裂可能自葉子節(jié)點出現(xiàn)，并向上逐級影響父節(jié)點直到根節(jié)點.但這一過程是否出現(xiàn)取決于節(jié)點內原有關鍵字的容量和分裂后的節(jié)點關鍵字，難以提前預判計算和預取數(shù)據(jù)，導致索引插入的執(zhí)行效率很低.這種計算的不確定性對GPU 的SIMD架構極不友好.

索引的維序會阻塞對同一棵樹的其他操作，影響指令并行性能.在本條維序操作結束前，節(jié)點內數(shù)據(jù)容量的差異和樹形結構的數(shù)據(jù)依賴性導致無法預測其結構變化.索引維序過程對正在執(zhí)行的樹具有獨占性，即阻塞對同一棵樹的其他操作，從而當索引維序請求發(fā)生時，無法實現(xiàn)多指令并行，進一步降低B+樹索引維序的性能.

4 B+樹索引的優(yōu)化

第3 節(jié)的分析表明：訪存效率低和計算并行難是造成B+樹查詢性能差的主要原因；維序的復雜操作以及維序操作的數(shù)據(jù)依賴使得加速索引維序更加困難.本節(jié)將從訪存效率提升、單節(jié)點計算效率提升、計算并行優(yōu)化及解除維序的數(shù)據(jù)依賴4 個方面，提出提升B+樹查詢和維序性能的設計思想.

訪存優(yōu)化的關鍵是利用主存 DRAM 突發(fā)讀寫帶寬高的特性來提升帶寬利用率.DRAM 存儲器的特點是連續(xù)地址讀寫性能高效，即可以利用突發(fā)讀寫機制實現(xiàn)對B+樹各節(jié)點的讀寫.在B+樹中，節(jié)點內在關鍵字比較時被反復訪問，這也意味著B+樹中間節(jié)點數(shù)據(jù)量越大，數(shù)據(jù)讀寫效率越高.因此，中間節(jié)點的數(shù)據(jù)量大小、存儲格式以及讀寫方式是本文優(yōu)化的重點.

然而單節(jié)點的數(shù)據(jù)量增加意味著在查找過程中需要進行更多次數(shù)據(jù)比較才能找到指向下一級滿足條件的節(jié)點指針，對計算引擎的查詢性能提出了更高的要求，從而提升單節(jié)點計算效率成為提高計算性能的首要保證.為進一步提升查詢性能，語句級并行是提升系統(tǒng)性能的另一個重點.由此提出設計一種高性能的同構流式計算處理引擎架構以提升單查詢語句的執(zhí)行效率，并進一步提升多查詢語句的并行度.

大節(jié)點引入使得索引維序的過程更加復雜.一方面，定位待修改的關鍵字位置的查詢過程延遲變長；另一方面，節(jié)點內數(shù)據(jù)量增加導致更高的數(shù)據(jù)修改開銷.上述2 步驟的延遲和開銷進一步加劇了索引維序導致的數(shù)據(jù)依賴，阻塞其他對同一棵樹的索引操作.因此，提出解除語句間數(shù)據(jù)依賴以提升索引維序性能的方法，其核心思想是將單棵B+樹拆分成多棵子樹，能夠支持對單棵 B+樹操作轉為對不同子樹的操作.由于子樹間彼此獨立，從而實現(xiàn)多插入更新操作并行.具體地，我們采取了5 個關鍵優(yōu)化.

4.1 節(jié)點訪存優(yōu)化

為了提升節(jié)點數(shù)據(jù)的訪存效率，首先要確定樹節(jié)點的存儲格式.樹節(jié)點存儲格式設計需要解決2 個核心問題：1）單節(jié)點的訪存效率，節(jié)點大小要符合DDR控制器的特性；2）存儲可擴展性設計滿足不同大小樹的存儲需求.

設計節(jié)點大小的原則以DDR 控制器所支持突發(fā)（burst）長度為基準，規(guī)定單個節(jié)點的大小為突發(fā)長度的整數(shù)倍.比如Xilinx FPGA 板卡突發(fā)傳輸為512 B，可以設計節(jié)點大小為512 B 或1024 B 或其他1 次突發(fā)讀寫大小的整數(shù)倍空間.但一般來說，為降低單節(jié)點存儲可能造成的存儲空間浪費，單節(jié)點的設計不宜過大.同時規(guī)定每次內存讀寫都以1 個節(jié)點大小為單位，從而保證在對索引存儲節(jié)點的每次數(shù)據(jù)讀寫都充分利用內存帶寬.

為簡化B+樹的存儲管理，規(guī)定以內存塊的方式維護單棵B+樹，一個完整的索引可以由單棵樹或者多棵樹構成，樹的組織結構在內存塊中完成.每個內存塊（即1 棵樹）包含多個節(jié)點，每個節(jié)點存儲多個索引關鍵字.多樹的可擴展性設計的關鍵是進行樹的動態(tài)維護.規(guī)定內存空間的動態(tài)申請和回收也按照塊進行，即創(chuàng)建新B+樹時，按塊申請內存空間構建索引；刪除B+樹，也相應地按塊釋放內存空間.以內存塊為最小訪存管理對象，使得內存管理更加簡潔高效.

4.2 高效的訪存管理

確定了樹的存儲結構，接下來要解決的是如何實現(xiàn)處理引擎對樹和節(jié)點的數(shù)據(jù)訪問，即如何快速實現(xiàn)樹和節(jié)點從邏輯編號到物理存儲的映射，以及如何高效地將內存數(shù)據(jù)加載到處理單元.訪存管理需要解決2 個關鍵問題：1）邏輯樹和節(jié)點到物理存儲的映射，包括物理空間的申請和釋放；2）為多處理引擎提供有效的計算數(shù)據(jù).

規(guī)則的節(jié)點設計能夠簡化B+樹節(jié)點的地址空間管理.定義一棵B+樹在內存中存儲的數(shù)據(jù)格式為樹表，每棵樹表對應特定的內存塊.樹表的最小數(shù)據(jù)組織單位為行，行大小一致，每行表示1 個節(jié)點.計算引擎直接對節(jié)點內的索引關鍵字進行操作，其訪存過程首先確定樹表的內存空間，然后定位節(jié)點的內存地址.由于索引的查詢和維序操作均在1 個或多個節(jié)點內完成，為充分利用內存讀寫帶寬，每次I/O 讀寫均以1 個節(jié)點為單位.然而，由于索引維序時節(jié)點的動態(tài)修改對每個節(jié)點的地址管理仍然很復雜，需要解決新節(jié)點物理地址的申請或原節(jié)點物理空間的釋放.

執(zhí)行查詢操作時，內存訪問均以B+樹根節(jié)點開始，并依層次順序訪問內部節(jié)點，直到葉子節(jié)點結束.為降低節(jié)點內存訪問的控制成本，提出構建專用的樹表存儲管理單元（tree-table memory manage unit, TMMU）實現(xiàn)快速從B+樹邏輯地址到樹表節(jié)點內存物理地址的映射，以降低內存空間維護的復雜度，并提升計算訪存的效率.TMMU 記錄 B+樹和內部節(jié)點的相關狀態(tài)信息，保證在樹或節(jié)點創(chuàng)建或刪除時，能夠動態(tài)維護樹和節(jié)點的有效性.

4.3 流式計算架構

利用流式計算的原則設計專用處理引擎從而提升節(jié)點內關鍵字查詢的性能.相比于其他批量計算，流式計算有2 個主要的優(yōu)勢：1）無狀態(tài)執(zhí)行，控制簡單，數(shù)據(jù)驅動有利于多任務并行；2）全流水執(zhí)行，效率高，部分數(shù)據(jù)到達即可進行處理.圖4 示例了流式計算與批量計算的區(qū)別.與傳統(tǒng)的批量計算不同，流式計算每次只對規(guī)定窗口大小的數(shù)據(jù)進行計算，而無需等待全部數(shù)據(jù)輸入到計算節(jié)點.圖4 示例表明，流式計算的控制簡單，計算僅以數(shù)據(jù)流為驅動，沒有復雜的控制邏輯結構.

Fig.4 Difference between streaming computing and batch computing圖4 流式計算與批量計算的區(qū)別

4.4 多查詢語句并行

規(guī)則的節(jié)點存儲結構和高效的數(shù)據(jù)管理單元為多語句并行執(zhí)行提供了快速有效的原始計算數(shù)據(jù)，解決了帶寬與計算性能不匹配的問題.數(shù)據(jù)管理單元配合內存控制單元，能夠提供連續(xù)不間斷的數(shù)據(jù)訪存通路，為多計算引擎提供計算所需的數(shù)據(jù).

實現(xiàn)多查詢語句并發(fā)的另一個關鍵條件是指令間的調度和控制，即查詢指令如何映射到多處理單元.為最大化多語句并行度，并簡化控制邏輯，提出同構的流式計算引擎陣列設計.同構計算引擎，即所有處理單元架構一樣，每個處理單元可以支持包括查詢、刪除、插入和更新在內的全部索引操作.同時，由于各處理單元采用流式計算實現(xiàn)，進一步降低其控制邏輯的復雜度.基于上述設計，多查詢指令的并發(fā)管理變得異常簡單高效，當有新的計算指令時，可以快速分配到任一空閑處理引擎執(zhí)行，而不需要對各處理單元分類別管理.同構的處理引擎設計也會避免計算任務和處理單元類型不匹配而導致資源浪費.相比于如圖5 所示的異構設計，采用同構設計處理單元存在一定的冗余而使得硬件資源開銷增加，我們也在降低開銷上做了很多精細設計，詳細見第5 節(jié).

Fig.5 Difference between homogeneous and heterogeneous computing units圖5 同構計算單元與異構計算單元的區(qū)別

4.5 提升索引維序性能的子樹結構設計

為緩解索引維序的獨占性而導致的性能損失，提出解耦合的子樹結構設計，以解決由于索引維序導致的多語句并行阻塞現(xiàn)象.子樹是將1 棵完整的B+樹按照一定的方式拆分為幾棵小的子樹，且規(guī)定每一棵子樹的構建嚴格遵循B+樹索引的結構要求.為支持子樹查詢和維序的并行，內存管理模塊也需要進行相應的修改：查詢和維序操作的起始訪問從內存空間的入口地址（即大樹的根節(jié)點）變?yōu)樽訕涞母?jié)點對應的內存地址.具體地，創(chuàng)建新樹時仍然申請1 個新的內存塊；但是在構建樹的過程中，按照某種規(guī)則選擇內存塊的某些地址作為子樹的根節(jié)點地址，并將樹構建的過程平均至每一棵子樹，直到完成1 棵樹的創(chuàng)建.相應地，查詢操作的起始地址將變?yōu)樽訕淙肟诘刂罚醋訕涓?jié)點），而不再是原始的大樹入口地址（根節(jié)點）.這樣設計的優(yōu)勢在于，由于子樹間沒有數(shù)據(jù)依賴，對同一棵大樹但不同子樹的多條插入和更新操作可以并行執(zhí)行，即實現(xiàn)將對1 棵大樹的串行操作轉化為對多棵子樹的并行操作.

子樹的劃分粒度是子樹設計中需要考量的重要設計參數(shù).劃分子樹時，劃分粒度越細，索引更新可以在更多棵子樹中并行，數(shù)據(jù)并行度增加，從而提升計算并行效率.但劃分越細粒度，子樹根節(jié)點的入口地址維護會越復雜，且劃分越細將丟失越多索引結構信息，對樹的索引結構利用效率降低；反之，子樹劃分粒度越粗，子樹棵樹越少，數(shù)據(jù)依賴越多，計算并行提升有限.但粗粒度的劃分方式能夠更好地利用索引結構信息，且子樹控制邏輯簡單，能夠緩解硬件資源開銷.

5 系統(tǒng)實現(xiàn)

按照第4 節(jié)中提出的優(yōu)化策略，本節(jié)主要介紹基于FPGA 實現(xiàn)的B+樹索引加速系統(tǒng)HyperTree 的具體實現(xiàn)和系統(tǒng)運行流程.HyperTree 統(tǒng)包含3 個主要的子系統(tǒng)，如圖6 所示：存儲管理子系統(tǒng)、索引計算子系統(tǒng)和指令控制子系統(tǒng).其中，存儲管理子系統(tǒng)包含TMMU 和內存控制單元.在得到激活控制信號后，TMMU 負責將指令中的邏輯編號轉換為內存物理地址.內存控制單元將TMMU 輸出的物理地址中的內存數(shù)據(jù)傳遞到計算引擎，或按照計算引擎給出的結果寫回相應的內存空間.指令控制子系統(tǒng)負責解析索引操作指令，提取操作碼和操作數(shù)，并根據(jù)操作碼和操作數(shù)依次激活指令執(zhí)行單元并打開內存數(shù)據(jù)通道，負責指令并行控制.索引計算子系統(tǒng)由多個同構的計算引擎構成，負責并行執(zhí)行索引的查詢、插入、刪除和更新指令.其中，存儲管理子系統(tǒng)和指令控制子系統(tǒng)是實現(xiàn)多語句并行的直接控制邏輯單元，索引計算子系統(tǒng)是執(zhí)行計算并行的核心功能部件.接下來分別對各部分關鍵模塊的實現(xiàn)進行介紹.

Fig.6 System overall architecture圖6 系統(tǒng)整體結構

5.1 節(jié)點存儲格式設計

根據(jù)第4 節(jié)中節(jié)點的設計原則，在微結構實現(xiàn)時以512 B 為單位定義節(jié)點大小.以128 MB 內存塊大小為單元設計樹表，則樹表共包含218行（即節(jié)點），在存儲塊內的標號為0～218-1.樹的大小可以通過改變單位節(jié)點大小或樹表容量相應調整.給定固定容量的B+樹，如果1 棵樹滿，可以通過動態(tài)申請存儲塊，創(chuàng)建1 棵新樹以實現(xiàn)數(shù)據(jù)庫表的完整索引結構.該過程利用軟件指令顯式維護.B+樹的節(jié)點格式規(guī)則定義如圖7 所示.B+樹包含3 種不同的節(jié)點類型：內部節(jié)點、葉子節(jié)點和等值節(jié)點.其中，內部節(jié)點只存儲關鍵字，葉子節(jié)點和等值節(jié)點存儲關鍵字和衛(wèi)星數(shù)據(jù)（衛(wèi)星數(shù)據(jù)指向數(shù)據(jù)表中的一條數(shù)據(jù)記錄）.兩者的區(qū)別在于，葉子節(jié)點指向不同關鍵字對應的記錄，而等值節(jié)點指向相同關鍵字對應的記錄.等值節(jié)點由葉子節(jié)點維護，葉子節(jié)點內的等值索引指針若為0，則原始表位置信息有效，直接指向原始數(shù)據(jù)庫表中的記錄；否則，等值索引指向等值節(jié)點.為簡化索引關鍵字的尋址過程，設計8B 對齊的節(jié)點存儲格式.3類節(jié)點的格式組織基本相同，都是由節(jié)點頭部和節(jié)點數(shù)據(jù)2 部分組成.節(jié)點頭部主要標識節(jié)點類型及記錄指針；數(shù)據(jù)部分主要存儲索引關鍵字和指向子節(jié)點或表邏輯地址的指針.

Fig.7 Data structure definition of tree-table圖7 樹表的數(shù)據(jù)結構定義

規(guī)則的節(jié)點設計及以節(jié)點為單位的訪存規(guī)則有效地提升了系統(tǒng)的內存帶寬和內存空間的利用率.以突發(fā)讀寫長度為單位設計節(jié)點容量，使計算引擎在處理節(jié)點內數(shù)據(jù)時，能夠充分利用突發(fā)讀寫的高帶寬，提升內存讀寫效率.節(jié)點指針以邏輯地址的形式存儲，所占內存空間更小，且標識節(jié)點特征的部分僅占節(jié)點頭部的1/4，提升了節(jié)點對索引關鍵字及指針的存儲效率，確保最大程度利用內存空間.此外，規(guī)則的節(jié)點格式設計簡化了計算引擎對數(shù)據(jù)解析的過程.在處理單節(jié)點內部信息時，進一步提升計算性能.

5.2 存儲管理單元

為充分利用內存帶寬，降低樹表地址維護開銷，提出專用樹表存儲管理單元TMMU，其主要實現(xiàn)2部分功能：一是實現(xiàn)邏輯地址到物理地址的快速映射；二是高效地將數(shù)據(jù)傳遞到計算引擎.

快速的地址映射能夠簡化軟件對內存地址的管理，并提升節(jié)點存儲空間的存儲效率.在實際應用中，軟件不直接管理B+樹的節(jié)點地址，從而維護索引物理地址被轉換為硬件開銷.通常計算指令的操作數(shù)所攜帶的信息是B+樹的標識tree_ID；根據(jù)樹表的設計原則，所得到的節(jié)點指針也只存儲其邏輯地址（以Num表示）.TMMU 的主要任務之一就是實現(xiàn)B+樹的標識tree_ID及樹內節(jié)點邏輯地址與B+樹根節(jié)點入口地址及節(jié)點物理地址的映射，并維護樹表基本信息和節(jié)點的有效性.TMMU 的地址映射由圖8 所示.

Fig.8 Address mapping in TMMU圖8 TMMU 的地址映射

TMMU 中維護地址映射，為充分利用緩存讀寫帶寬，映射表的1 行與緩存單次最大讀寫位寬相同.表中的一行記錄樹的標識編號tree_ID、根節(jié)點入口地址（記為Addr）、樹深度、節(jié)點個數(shù)等信息.根節(jié)點映射表中以有效位1 表示該條記錄有效，否則該位置可以被改寫.當指令輸入tree_ID，TMMU 通過樹表映射表確定樹表的根節(jié)點入口及相應信息；再依據(jù)節(jié)點的邏輯地址，根據(jù)式（1）中給出的映射關系計算其物理地址，其中單位尋址空間的單位為B.節(jié)點邏輯地址到物理地址的映射計算簡單，硬件計算資源開銷很小.

TMMU 可以實現(xiàn)對樹表的動態(tài)維護.新建或刪除B+樹時，TMMU 根據(jù)對內存空間動態(tài)申請或釋放的結果，在樹表映射表中根據(jù)有效位信息增加或刪除相應的tree_ID與樹表信息的記錄.指令拆分或合并節(jié)點時，TMMU 負責修改樹表中樹的深度和節(jié)點個數(shù)信息.為簡化樹表管理，規(guī)定增加節(jié)點時邏輯地址相應加1，刪除節(jié)點時不修改原有節(jié)點的邏輯地址，下次增加節(jié)點仍然在現(xiàn)有邏輯地址的基礎上遞增.這樣的實現(xiàn)方式雖然造成節(jié)點刪除時存儲空間的浪費（這種空間損失代價很小，每一個節(jié)點僅占樹表結構的1/218），但能夠極大地簡化樹表管理的控制邏輯.

TMMU 的另一個主要功能是充分利用內存讀寫帶寬，實現(xiàn)高效的內存讀寫.隨著指令控制單元依次解析指令隊列中的指令內容，TMMU 接收到節(jié)點邏輯地址后立即計算物理地址，內存管理單元打開內存通道，將對應內存空間內的數(shù)據(jù)傳遞到指定的計算單元.TMMU 對數(shù)據(jù)的處理是連續(xù)的，即只要接收到指令流的邏輯地址，則執(zhí)行物理地址的計算并打開數(shù)據(jù)通道，對內存塊內的數(shù)據(jù)進行緩存.該設計相當于實現(xiàn)了計算引擎的數(shù)據(jù)預取，消除計算時數(shù)據(jù)讀寫所引入的I/O 訪問延遲.TMMU 通過緩存機制實現(xiàn)內存的連續(xù)訪問并形成數(shù)據(jù)通道.每個計算引擎獨占1 個數(shù)據(jù)通道，TMMU 以輪詢的方式依次打開并完成數(shù)據(jù)傳輸，能夠充分利用內存的高讀寫帶寬.

5.3 流式計算引擎設計

對于單計算節(jié)點，提出設計流式計算架構以支持高效的索引計算.流式處理引擎不需要復雜的控制電路，計算以數(shù)據(jù)流為驅動，即只要在輸入端有數(shù)據(jù)則計算會持續(xù)進行，不需要復雜的狀態(tài)控制機制.流式計算引擎能夠最大程度提升單節(jié)點的計算性能.單個計算引擎的內部結構如圖9 所示.計算引擎內有1 個地址緩存單元和1 個節(jié)點緩存單元，分別用于暫存TMMU 傳遞到計算引擎的節(jié)點地址和節(jié)點內容.讀數(shù)據(jù)緩存FIFO 按照8B 對齊的原則讀取數(shù)據(jù)緩存單元內的節(jié)點數(shù)據(jù)，以指針和關鍵字組的順序依次寫入.只要讀數(shù)據(jù)緩存FIFO 不為空，則比較器執(zhí)行待比較關鍵字與節(jié)點內關鍵字的比較.讀寫控制單元由指令操作碼決定其打開或關閉.如果操作碼指示了關鍵字的插入或刪除，讀寫控制單元打開，節(jié)點地址緩存當前節(jié)點的地址，寫數(shù)據(jù)緩存FIFO 依次讀取節(jié)點內的數(shù)據(jù)內容.當定位到待比較關鍵字的位置，寫數(shù)據(jù)緩存FIFO 根據(jù)指令控制插入或刪除待比較關鍵字并更新指針內容.節(jié)點內關鍵字全部寫入寫緩存FIFO 后，讀寫控制打開內存通道，根據(jù)地址緩存中的地址更新節(jié)點內容.由于索引維序的前序依賴是關鍵字查詢，在同構計算引擎設計中，硬件資源的冗余開銷只有讀寫控制單元和寫數(shù)據(jù)緩存2 部分.相較于異構計算引擎的復雜狀態(tài)控制來說，這部分硬件資源冗余幾乎可以忽略.

計算引擎的執(zhí)行過程以流水線方式進行，工作流程按照查詢和維序過程分為2 大類.查詢時，讀寫控制無效，僅有讀數(shù)據(jù)緩存、比較和結果寫回3 個階段.當比較器得到待查詢關鍵字期望位置時，輸出關鍵字所在位置的指針信息.期望位置是指，葉子節(jié)點內關鍵字相等，或內部節(jié)點中關鍵字大于前一個關鍵字且小于后一個關鍵字.此時，如果葉子節(jié)點沒有相等關鍵字，則輸出不存在該數(shù)據(jù).輸出的指針信息為葉子節(jié)點的衛(wèi)星數(shù)據(jù)或等值節(jié)點邏輯地址，以及內部節(jié)點的葉子節(jié)點的邏輯地址.插入或刪除時，讀寫控制有效，包括讀數(shù)據(jù)緩存、比較、寫數(shù)據(jù)緩存和結果寫回4 個階段.指令打開讀寫控制單元，寫數(shù)據(jù)緩存將讀數(shù)據(jù)緩存內數(shù)據(jù)和待比較關鍵字根據(jù)比較結果的期望順序依次讀入.期望順序是指大于前一個關鍵字且小于后一個關鍵字，或存在與原有關鍵字相等的等值節(jié)點則輸出指向等值節(jié)點的邏輯地址.

為簡化節(jié)點的地址管理，降低節(jié)點動態(tài)維護的開銷，對節(jié)點的合并和拆分進行規(guī)定：當且僅當節(jié)點內數(shù)據(jù)為空才執(zhí)行節(jié)點的刪除，當且僅當節(jié)點內數(shù)據(jù)量超過512 B 時才執(zhí)行節(jié)點的創(chuàng)建.節(jié)點刪除需要刪除上層父節(jié)點中的指針和索引關鍵字.節(jié)點的插入對當前層節(jié)點進行修改，寫數(shù)據(jù)緩存將前一半指針和關鍵字組寫入當前節(jié)點，將后一半指針和關鍵字組寫入新的節(jié)點地址空間，并在上層父節(jié)點中插入關鍵字和指針信息.這2 種操作需要同時更新TMMU 中樹表的深度、節(jié)點數(shù)等信息.

5.4 指令控制子系統(tǒng)

指令控制子系統(tǒng)主要包括指令解析模塊、計算控制單元和內存控制單元，其結構如圖10 所示.其中，指令解析單元分離指令中的操作數(shù)和操作碼，解析索引計算類型及節(jié)點和樹表邏輯地址.計算控制單元查詢處理引擎的執(zhí)行狀態(tài)，啟動可執(zhí)行的計算.內存控制單元將邏輯地址寫入TMMU 完成地址映射，判定編號為tree_ID樹的執(zhí)行情況，并打開可訪問的編號為tree_ID樹的內存地址，完成處理引擎對數(shù)據(jù)的緩存.

Fig.10 Instruction control system圖10 指令控制系統(tǒng)

為提升系統(tǒng)性能，設計多個同構計算引擎以實現(xiàn)指令集并行.計算引擎的并行由指令控制單元和內存控制單元共同管理，其結構如圖11 所示.計算控制單元為每個處理引擎維護一個寄存器，寄存器中包含處理引擎是否空閑標志位Dest_ID、處理引擎正在執(zhí)行的操作類別及處理引擎在處理的tree_ID信息.計算控制單元獲取指令隊列中的首條指令，查詢處理引擎寄存器信息，找到空閑的處理引擎，并判斷當前指令及所有正在執(zhí)行狀態(tài)的處理引擎中是否存在對該指令tree_ID的更新操作.有則阻塞指令并發(fā)；否則發(fā)送指令操作碼到該空閑的計算引擎，并修改寄存器相關信息.最大指令并行數(shù)與計算引擎數(shù)目相同.當計算引擎狀態(tài)寄存器Dest_ID空間被賦值，說明計算引擎已經(jīng)完成對本條指令的執(zhí)行，此時可以修改寄存器標識為當前計算引擎為空閑，并清除執(zhí)行信息.

Fig.11 Design of homogenous fully functional multiprocessing engines圖11 同構的全功能多處理引擎設計

5.5 指令設計

為配合系統(tǒng)的執(zhí)行，設計支持的索引操作的指令如表1 所示.指令集包含2 類指令：基本指令和附加指令.其中基本指令是直接規(guī)定索引和樹操作的指令，包括樹的操作和關鍵字操作2 類；附加指令用于部分基本指令的重定義和操作控制，包括范圍查詢和關鍵字更新2 類附加指令.

Table 1 Design of Instruction Set表1 指令集設計

5.6 B+樹子樹系統(tǒng)

由于索引維序操作與其他操作之間存在強數(shù)據(jù)依賴，設計一種子樹結構以解除這種數(shù)據(jù)依賴，其結構如圖12 所示.子樹結構使得對1 棵大樹的一次性訪問可以拆分為多棵子樹的多路訪問.也就是說，操作指令將不再以原始大樹的根節(jié)點作為源操作數(shù)，而是以子樹所在連續(xù)空間的起始地址作為訪存的入口地址，只要讀寫不同子樹空間，則對同棵大樹操作的多條指令可以并行.

Fig.12 Sub-tree structure and TMMU management圖12 子樹結構和TMMU 管理

為降低對子樹入口地址管理的復雜度，并提升子樹劃分方式的靈活性，將1 棵大樹的內存地址空間（即樹表）等分為幾段連續(xù)子空間，以每部分子空間的起始地址作為子樹的入口地址.子樹入口地址為

其中i表示在大樹中的第i棵子樹（i從0 開始計數(shù)），子樹空間subtree_space的單位為MB.

對齊的子樹空間設計降低了內存地址管理的復雜性，也降低了地址映射計算資源的開銷.子樹的大小可以由地址空間范圍劃分方法靈活決定，即子樹空間劃分粒度可以根據(jù)實際應用需求設定，這種設計方式實現(xiàn)了靈活性與高效性的權衡.從而，在不同數(shù)據(jù)量和并發(fā)查詢請求需求下，有效提升B+樹的并行讀寫效率，避免引入復雜的子樹空間管理開銷.子樹劃分對查詢操作性能和資源的影響在第6 節(jié)中具體評估.

為維護子樹的狀態(tài)，在TMMU 的根節(jié)點映射表中加入與邏輯地址對應的子樹的層數(shù)及內部節(jié)點數(shù)的記錄.在插入新的索引關鍵字時，為均衡子樹的訪問頻率，在TMMU 中加入一個專用的輪詢仲裁器管理子樹空間的訪存順序：按照子樹的內存空間順序依次檢查子樹空間的訪問狀態(tài)，在可訪問時申請對子樹的訪問，否則對下一棵子樹進行檢查.

顯然，子樹的引入改變了B+樹索引構建的方式.為配合子樹結構，提出支持查詢和維序的優(yōu)化設計，其優(yōu)化進程如圖13 所示.在B+樹索引構建及新關鍵字插入時，計算引擎按照B+樹創(chuàng)建指令的要求從內存中申請開辟一段連續(xù)的空間用于存放樹表，即邏輯結構上的1 棵完整B+樹.隨后，將此段空間平均分配為n段連續(xù)子空間，并在TMMU 中分別記錄這幾棵子樹的信息.在當前樹表中，每插入1 個新的關鍵字，則以輪詢的方式依次分配1 段子空間入口地址，依照關鍵字插入的順序依次在子樹中插入索引關鍵字.按照這樣的規(guī)則，子樹仍然保持B+樹的特征，但子樹構成的大樹不維持邏輯索引結構.引入子樹結構能夠提升數(shù)據(jù)維護時樹的并行讀寫效率.根據(jù)TMMU 的設計原則，對樹的管理也不會由于引入子樹空間而過于復雜.

Fig.13 Sub-tree structure and query optimization圖13 子樹結構和查詢優(yōu)化

子樹系統(tǒng)改變了索引指令的尋址方式，影響了指令的執(zhí)行過程.關鍵字插入可以按輪詢的方式選擇子樹.但是，查詢和刪除需要定位關鍵字所在的葉子節(jié)點，不能以輪詢的方式選擇子樹，而大樹沒有邏輯上的索引結構，需要引入一種快速定位到包含關鍵字的子樹的機制.為準確定位查詢和刪除操作中關鍵字所在的子樹，在子樹空間選擇前加入1 級布隆過濾器[13].布隆過濾器是一種快速判斷某元素是否在集合中的功能部件.利用布隆過濾器提前過濾1 次關鍵字的位置，就可以快速定位關鍵字所在的子樹空間.將該子樹的入口地址發(fā)送到空閑的計算引擎，子樹內執(zhí)行查找和刪除與大樹完全相同.子樹系統(tǒng)使得索引查詢引入了1 級布隆過濾器的計算開銷，計算只需要幾個周期，對性能的影響幾乎可以忽略.

5.7 系統(tǒng)工作流程：多索引查詢指令

基于5.1～5.6 節(jié)所述的系統(tǒng)實現(xiàn)，我們以多條索引查詢指令為例，介紹系統(tǒng)運行的過程，如圖14 所示.當用戶發(fā)出多指令請求時，指令按照順序依次進入指令隊列.①指令處理：指令處理單元將按照隊列順序依次處理隊列中的各條指令.②指令解析：指令處理單元將得到的指令逐條解析，得到操作數(shù)和操作碼.③激活TMMU：操作數(shù)中對B+樹的訪存地址傳遞到TMMU.TMMU 查詢子樹的訪存狀態(tài)，進行邏輯地址與物理地址的映射，得到子樹的入口物理地址.④打開數(shù)據(jù)通道：按照子樹的內存地址輪詢結果，內存管理單元打開可用的內存數(shù)據(jù)通道，使得節(jié)點內容能夠到達相應的計算節(jié)點.⑤激活指令控制單元：操作碼和操作數(shù)中的關鍵字被傳遞到指令執(zhí)行單元，指令執(zhí)行單元管理計算引擎.⑥計算引擎：指令控制單元依次查詢計算引擎狀態(tài)，激活空閑計算單元，修改相關寄存器內容.若沒有空閑計算引擎則等待，直到找到空閑計算引擎.其中①②隨指令流的控制連續(xù)不斷地執(zhí)行；③④和⑤⑥為異步控制.⑦執(zhí)行計算：計算引擎按照操作數(shù)和操作碼的指令，啟動查詢或節(jié)點修改的執(zhí)行流程.⑧結果寫回：查詢時，僅輸出查詢關鍵字指向的衛(wèi)星數(shù)據(jù)的地址.更新時，則按照寫數(shù)據(jù)緩存內容和地址緩存中的地址修改相應節(jié)點內容.如果葉子節(jié)點需要刪除，無需寫回數(shù)據(jù)，只修改父節(jié)點及 TMMU 中的相關信息.如果節(jié)點需要拆分，則將數(shù)據(jù)均等分為2 部分，分別寫入2 個節(jié)點，并修改父節(jié)點和TMMU 相關信息.

Fig.14 Index query of B+tree accelerating system圖14 B+樹加速系統(tǒng)的索引查詢

6 實驗和評估

6.1 實驗搭建

實驗的硬件平臺利用PCIe 接口搭建CPU 服務器與FPGA 板卡互聯(lián)的異構計算系統(tǒng).CPU 型號為Intel Xeon Gold 5218（@2.30GHz）配備22 MB 的L3 緩存和64 GB 的內存（DDR4-2667）.FPGA 板卡選用Xilinx Alveo 的U200，U50，U280 數(shù)據(jù)中心加速卡.CPU與FPGA 的互聯(lián)接口為PCIe3.0 ×16 總線.實驗分別測試3 種不同資源配置（即異構系統(tǒng)選擇不同F(xiàn)PGA板卡）下本方案的性能.FPGA 加速板卡具體資源配置情況如表2 所示.

3 個板卡的主要區(qū)別在于其硬件邏輯資源和內存帶寬限制不同.U200 邏輯資源充足但內存帶寬受限，其上僅配備了DDR4 作為存儲資源，可提供76.8 GBps存儲帶寬；U50 是一種輕量級的板卡，其硬件邏輯資源是三者之中最少的，但它使用了第二代高帶寬內存（high bandwidth memory，HBM）資源HBM2，內存帶寬能夠達到316 GBps；U280 則是三者之中性能最高的，其硬件邏輯資源最多，且內存使用DDR4 和HBM2，既保證了存儲空間大且?guī)捀哌_460 GBps.

為評估數(shù)據(jù)庫索引的查詢和維序性能，實驗的數(shù)據(jù)和程序選擇數(shù)據(jù)庫基準測試程序TPC-C 中提供的標準數(shù)據(jù)庫表生成數(shù)據(jù)和聯(lián)機事務處理（on-line transaction processing, OLTP）程序，以充分測試數(shù)據(jù)庫表記錄的查詢、刪除、插入和更新的實際性能[14].TPC- C 數(shù)據(jù)集用9 個相關的數(shù)據(jù)表記錄了某類倉庫在不同地區(qū)的存貨量、存儲的不同商品庫存以及地區(qū)消費者信息和貨物訂單等信息.在這9 個數(shù)據(jù)表中，選擇最大數(shù)據(jù)表order_line 作為本實驗測試用數(shù)據(jù).測試數(shù)據(jù)表的查詢、插入、刪除和更新性能，對應TPC-C 基準測試中訂單信息查詢、提交客戶新交易申請、交易結束刪除訂單信息，以及訂單修改申請.實驗運行所選擇的關系型數(shù)據(jù)庫為典型的MySQL數(shù)據(jù)庫.在本實驗測試中，測試用的數(shù)據(jù)庫表數(shù)據(jù)仍然存在CPU 主機上，僅在 FPGA 板上內存預先存儲需要構建索引的部分表信息.此時認為HyperTree 可以屏蔽與CPU 進行數(shù)據(jù)傳輸?shù)拈_銷；HyperTree 可以單獨完成指令要求的索引操作，即從索引構建并存儲B+樹索引數(shù)據(jù)，到完成相應的事務處理的全過程.實驗的比較基準選擇CPU 并行執(zhí)行TPC-C 數(shù)據(jù)庫索引查詢和維序的性能.進一步評估實驗結果，選擇目前具有最優(yōu)效果的基于 GPU 實現(xiàn)的 B+樹索引加速系統(tǒng)結果[5,7]以及基于FPGA 實現(xiàn)的B+樹加速器結果[10-11]進行對比和分析.

在6.2 和6.3 節(jié)中，以Alveo U200 板卡作為B+樹索引加速系統(tǒng)HyperTree 的硬件實現(xiàn)原型.此配置方法能夠均衡考慮片上硬件計算資源和帶寬資源的限制，設計32 個并行的計算節(jié)點和32 路數(shù)據(jù)通道實現(xiàn)對資源的充分利用（具體細節(jié)評估見6.4 節(jié)），配置信息見表3.在這樣的系統(tǒng)配置環(huán)境下，能夠充分利用FPGA 板卡的內存帶寬資源，且不會引入冗余的計算引擎，引入不必要的硬件開銷.

Table 3 Hardware Configuration of B+tree Index Accelerator Using Alveo U200 FPGA Board表3 基于Alveo U200 FPGA 板卡的B+樹索引加速器硬件配置

6.2 索引查詢性能

本節(jié)主要評價多查詢語句的并行性能.以6.1 節(jié)中介紹的實驗環(huán)境和實驗數(shù)據(jù)為基礎，實現(xiàn)B+樹索引加速系統(tǒng)HyperTree.實驗評估指標有2 個：一是以每秒執(zhí)行查詢指令數(shù)目條數(shù)QPS（query per second）作為衡量系統(tǒng)性能的指標，其中實驗結果QPS 實際值的數(shù)量級為百萬條每秒；二是以指令平均響應時間衡量每條指令的執(zhí)行時間，用于驗證OLTP 是否滿足應用系統(tǒng)的實時需求.

評估數(shù)據(jù)庫表的數(shù)據(jù)量對系統(tǒng)性能的影響.為充分釋放處理引擎的并行度，指定實驗中測試的并發(fā)指令數(shù)目為 32.在實驗中按照樹表格式的設計規(guī)則，將數(shù)據(jù)庫表大小的不同直接換算為B+樹索引中節(jié)點數(shù)目的不同，從而可以以節(jié)點數(shù)目的差別描述不同容量的B+樹.由于比較基準測試中節(jié)點格式不同，節(jié)點可存儲的關鍵字數(shù)量存在差別.后序實驗為公平對比，每組實驗均基于具有相同節(jié)點數(shù)目的 B+樹完成.事實上，基于CPU 和文獻[10]中的方法所生成的B+樹要比HyperTree 基于規(guī)則節(jié)點格式生成的B+樹更小.由此，為公平地評估不同 B+樹索引加速系統(tǒng)的性能隨數(shù)據(jù)量的變化，實驗結果的對比保持B+樹的節(jié)點數(shù)目的數(shù)量級一致，且在樹結構的限制下盡可能保證數(shù)量相近.實驗評估時，以B+樹索引加速系統(tǒng)HyperTree 生成的 B+樹的容量作為數(shù)據(jù)量數(shù)量級的基準，圖15“數(shù)據(jù)量”指HyperTree 生成的樹.此外，由于樹存儲格式的設計具有明顯區(qū)別，后續(xù)的實驗結果對比也僅考慮節(jié)點數(shù)目相同或維持同一數(shù)量級，而不直接以樹的大小作為實驗性能對比的指標.

Fig.15 Normalized throughput of B+tree accelerator圖15 B+樹加速器的歸一化吞吐量

圖15 顯示了系統(tǒng)在B+樹的數(shù)據(jù)量變化下指令查詢的歸一化性能（以CPU 單值查詢?yōu)閱挝?）.當在小數(shù)據(jù)量測試環(huán)境下時系統(tǒng)的吞吐量大約是CPU的11.14 倍；當在大數(shù)據(jù)量的情況時，系統(tǒng)的查詢性能提升大約為CPU 的6.84 倍.小數(shù)據(jù)量時獲得顯著性能提升的原因主要是：緊湊的節(jié)點存儲使得進行B+樹查詢時層間跳數(shù)更少，且節(jié)點規(guī)則格式設計使系統(tǒng)對內存帶寬利用更加高效.大數(shù)據(jù)量時，B+樹索引系統(tǒng)HyperTree 在進行關鍵字查詢時需要更多層內部節(jié)點來構建索引，從而增加了內部節(jié)點層間的跳數(shù)，使得查詢平均延遲增加.實驗結果表明，B+樹索引加速系統(tǒng)相比CPU 能夠獲得顯著的性能提升.這一結果遠超于文獻[10]中利用FPGA 實現(xiàn)的B+樹索引查詢方案所獲得的結果，相較于CPU 性能僅平均提升1.31～2.24 倍.

在多指令并發(fā)查詢的實驗中，以TPC-C 數(shù)據(jù)集提供的order_line 表為模板，按照規(guī)定的數(shù)據(jù)格式隨機生成數(shù)據(jù)表，每個表包含 6.5～26.2 萬行記錄.這樣，利用其中待查詢的關鍵字段構建 B+樹索引可以保證單棵樹內的節(jié)點全部有效，從而節(jié)點的數(shù)量級維持在 105，大約要求樹表有效節(jié)點存儲空間的容量為10～128 MB.實驗設計單值查詢和范圍查詢2 類查詢指令，單次并發(fā)指令數(shù)目從10 條開始以10 倍量級遞增至100 萬條.圖16 顯示了系統(tǒng)在不同指令并發(fā)狀態(tài)下歸一化后的系統(tǒng)性能（以CPU 單值查詢?yōu)閱挝?）.當并發(fā)指令數(shù)目為10 時，計算引擎沒有被占滿，此時系統(tǒng)的性能明顯低于其他多指令并發(fā)，但仍是CPU 性能的3.21 倍.隨著并發(fā)指令數(shù)的增加，由于查詢關鍵字在節(jié)點內的位置具有不確定性，系統(tǒng)性能具有一定波動性，但與32 條指令并發(fā)的最優(yōu)性能大體一致.與CPU 在范圍查詢時性能顯著下降有所不同，B+樹索引加速系統(tǒng)HyperTree 的32 長度的范圍查詢的性能大約是其單值查詢的75.58%，性能損失不明顯，能夠達到 CPU 性能的 14.53 倍.這是由于B+樹索引加速系統(tǒng)的規(guī)則大節(jié)點設計以及高效的并發(fā)讀寫機制，在范圍查詢時進行葉子節(jié)點讀寫過程中能夠以較小的節(jié)點跳樹實現(xiàn)大范圍的查詢.實驗結果表明，B+樹索引加速系統(tǒng)能夠在多指令并發(fā)的情況下維持高效的系統(tǒng)查詢性能.

Fig.16 Normalized throughput of parallel data query instructions圖16 歸一化的并行數(shù)據(jù)查詢指令吞吐量

子樹的引入對索引查詢無顯著影響.一方面，子樹的引入只要求增加1 層布隆過濾器計算，F(xiàn)PGA 實現(xiàn)該計算過程只需要幾個周期；另一方面，即使增加到32 棵子樹，樹表容量的數(shù)量級仍然維持在105.因此，子樹的引入對索引查詢性能的影響很小，幾乎可以忽略不計，所以這一部分實驗不再評估子樹的引入對索引查詢性能的影響.

將該結果與GPU 優(yōu)化的B+樹進行對比.參考文獻[5,7]中利用GPU 優(yōu)化B+樹存儲結構的多語句并行查詢結果：GPU 實現(xiàn)的樹的容量為128 MB（只存儲關鍵字，不存儲衛(wèi)星數(shù)據(jù)）時，相較于CPU 實現(xiàn)的標準B+樹，單值查詢性能提升20.41 倍，范圍查詢性能提升23.91 倍.然而，由于GPU 優(yōu)化的樹結構中只保留存儲關鍵字的中間節(jié)點，這一方案也只能定位關鍵字在哪一個葉子節(jié)點，并沒有最終找到數(shù)據(jù)庫中的衛(wèi)星數(shù)據(jù)，因而與本實驗實現(xiàn)的環(huán)境難以直接進行對比.一旦加入對衛(wèi)星數(shù)據(jù)的尋址過程，會極大地損失GPU 的查詢性能.同時，范圍查詢的性能提升要比單值查詢更顯著的原因是，CPU 實現(xiàn)范圍查詢時存在一定性能損失，其單值查詢（比較基準）性能比范圍查詢具有2.36 倍的增益.如果以CPU 單值查詢的性能為基準，GPU 實現(xiàn)的B+樹加速系統(tǒng)的范圍查詢性能提升大約為11.22 倍，僅為單值查詢性能提升結果的50%左右.而本文所提出的B+樹索引加速系統(tǒng)HyperTree 能夠有效支持范圍查詢，性能損失大約80%.

6.3 索引維序性能

本節(jié)主要評價系統(tǒng)的索引維序性能.在B+樹索引加速系統(tǒng)中，除了設計多數(shù)據(jù)通道和并行計算引擎以加速索引查詢外，還針對索引維序時由于數(shù)據(jù)沖突所導致的索引維序性能瓶頸提出子樹的設計思想.以6.1 節(jié)中介紹的實驗環(huán)境和6.2 節(jié)中B+樹索引占滿樹表空間的環(huán)境為基礎，搭建B+樹索引加速系統(tǒng)實驗環(huán)境.通過增加子樹的棵數(shù)，評估子樹系統(tǒng)設計對索引維序性能帶來的提升.實驗以索引插入指令為例，子樹棵數(shù)從1 棵開始（即1 棵大樹，不實現(xiàn)子樹系統(tǒng)），以2 的冪次增長，直到32 棵為止.實驗結果以單棵樹的插入性能（QPS）為歸一化的單位1.如圖17所示，實驗結果表明隨著子樹棵數(shù)的增加，索引插入的并行性能取得顯著提升：當子樹棵數(shù)增加到32 時，系統(tǒng)性能提升約29.14 倍；且由于資源占用而導致的計算阻塞延遲也顯著降低.相比文獻[11]基于FPGA實現(xiàn)的B+樹索引查詢系統(tǒng)對索引更新操作會引入大約70%性能下降這一結論，HyperTree 能夠有效解決這一問題.另一方面，比較基準文獻[11]所提出的 CPUFPGA 優(yōu)化架構并沒有實現(xiàn)顯著的索引維序性能提升，而僅通過優(yōu)化調度 CPU 和 FPGA 的計算執(zhí)行，使一些不適合利用 FPGA 加速的維序計算由性能更高的CPU 取代，由此并沒有充分利用FPGA 計算性能.

Fig.17 Parallelism of sub-tree圖17 子樹并行性

將該結果與GPU 優(yōu)化的B+樹進行對比.參考文獻[5,7]中利用GPU 實現(xiàn)的一種優(yōu)化的B+樹存儲結構的關鍵字插入結果：實驗執(zhí)行GPU 實現(xiàn)的B+樹容量為128 MB（只存儲關鍵字，不存儲衛(wèi)星數(shù)據(jù)）時，其更新性能大約僅為CPU 實現(xiàn)的標準B+樹的72%.這也進一步說明B+樹的維序操作是索引性能損失的關鍵因素.而HyperTree 的子樹解耦合的數(shù)據(jù)存儲方法能夠解決由于索引維序對數(shù)據(jù)的獨占性而導致的計算并行困難的問題，從而有效提升索引維序的性能，均衡提升 B+樹查詢和維序性能.

6.4 計算架構的可擴展性

本節(jié)評估B+樹索引加速系統(tǒng)的可擴展性.計算架構的可擴展性可以衡量一種計算架構設計在增加計算節(jié)點時，硬件資源需求的增加情況以及實際性能的提升倍率.利用不同硬件平臺實現(xiàn)B+樹索引加速系統(tǒng)，可以衡量該計算架構設計是否能夠充分利用板卡資源，以較小的邊際硬件資源成本獲得系統(tǒng)性能提升.在本節(jié)實驗中，選用Xilinx Alveo U200，U50，U280 這3 個不同資源配置的FPGA 板卡來實現(xiàn)B+樹索引加速器系統(tǒng)HyperTree.這3 個板卡中限制系統(tǒng)性能的因素不同：U200 的帶寬資源受限，U50 的硬件邏輯單元受限，U280 則沒有資源受限（在本實驗的實現(xiàn)架構設計情況下）.

評價計算架構的可擴展性，可以通過增加系統(tǒng)中的計算引擎數(shù)目，評估系統(tǒng)硬件資源的使用情況及系統(tǒng)帶寬性能.在實驗中，設計系統(tǒng)的計算引擎數(shù)目從4 開始，以2 的冪次依次增長，直到256 個截止（受硬件邏輯資源限制，U50 僅支持128 個計算引擎）.本測試實驗所實現(xiàn)的子樹棵數(shù)與處理引擎數(shù)目相同，指令并發(fā)數(shù)目與處理引擎數(shù)目也相同.假設一種理想的實驗環(huán)境，即滿足處理引擎能夠無空閑地執(zhí)行索引計算.所獲得的QPS 值為理想條件下的結果，即沒有數(shù)據(jù)沖突且處理引擎全部并發(fā).實驗結果能夠綜合評估處理引擎、數(shù)據(jù)存儲和子樹系統(tǒng)的性能提升，結果如表4 所示.

Table 4 The Scalability of B+tree Accelerator表4 B+樹加速器的可擴展性

U200 板卡的內存帶寬標稱性能為76.8 GBps，為最大化利用內存帶寬資源，當計算引擎數(shù)目為32 時，內存帶寬資源可以達到41.8 GBps，基本實現(xiàn)了帶寬的最優(yōu)利用效率，相對于CPU 歸一化的QPS 可以達到174.78.計算引擎再翻倍后，受物理內存帶寬的限制，系統(tǒng)整體性能不會進一步增長，反而造成計算引擎的冗余，即由于缺少計算所需數(shù)據(jù)而出現(xiàn)計算引擎空閑，造成硬件邏輯資源的浪費.U50 板卡由于使用HBM 資源能夠提供316 GBps 的理論內存帶寬.為充分利用這一高內存帶寬資源，實驗結果表明，配置128 個計算引擎能使系統(tǒng)資源的利用性能達到最優(yōu).此時，限制計算性能的因素是U50 片上的其他硬件計算資源的數(shù)目無法支持更多計算引擎.而U280 板卡是三者之中帶寬性能和硬件邏輯資源都最豐富的，其標稱內存帶寬可以達到460 GBps.在片上實現(xiàn) 256個計算引擎，系統(tǒng)帶寬性能可以提升至302.3 GBps，相對于CPU 歸一化的QPS 可以達到1 258.12.實驗結果表明，B+樹索引加速系統(tǒng)具有很好的可移植性，能夠充分利用板卡資源，擴展設計時只需引入很小的硬件資源開銷即可實現(xiàn)索引查詢和更新性能的線性提升.

7 結 論

為解決大數(shù)據(jù)環(huán)境下，數(shù)據(jù)庫查詢和更新的性能，本文提出一種支持B+樹索引加速的系統(tǒng)，從訪存和計算2 方面協(xié)同加速數(shù)據(jù)庫索引操作.為提升內存讀寫帶寬的利用效率，設計規(guī)則的樹表存儲結構和高效的節(jié)點存儲格式，規(guī)定讀寫控制以單節(jié)點為單位，使讀寫帶寬可以達到68.8 GBps.為提升系統(tǒng)執(zhí)行性能，設計同構的多計算引擎，支持語句級并行.相比CPU，B+樹索引加速系統(tǒng)能夠實現(xiàn)14.53 倍的查詢性能提升.同時，為緩解索引插入和刪除操作的數(shù)據(jù)依賴，設計一種子樹存儲結構，支持多子樹插入及更新的并行，降低索引刪除的數(shù)據(jù)依賴，進一步提升索引的維序性能.相較于單棵大樹，子樹系統(tǒng)能夠提升索引插入性能29.14 倍.

作者貢獻聲明：吳婧雅負責整理相關文獻，提出問題解決方法，完成實驗驗證及撰寫論文；盧文巖提出設計實驗方案并實現(xiàn)優(yōu)化方案；鄢貴海和李曉維提供實驗環(huán)境支持，指導論文撰寫及修改論文.