吳婧雅 盧文巖 鄢貴海 李曉維
1 （處理器芯片全國重點實驗室（中國科學院計算技術研究所）北京 100190）
2 （中國科學院大學 北京 100049）
索引是數據庫中用來加速數據查詢的一種常用數據結構.其中，B+樹憑借其獨特優勢成為關系型數據庫中最常用的索引結構.相較于其他索引結構，B+樹具有3 個優勢：
1）數據存儲結構規則.利用關鍵字數據結構以平衡樹維護，能夠提升數據查詢效率.且樹的所有內部節點只存儲索引關鍵字（即鍵值），索引信息更密集，降低查詢I/O 開銷.
2）查詢開銷穩定.關鍵字指向的實際數據只在葉子節點中存儲.由此，查詢時需要逐層遍歷各層內部節點直到葉子節點結束，查詢開銷穩定.
3）提升范圍查詢性能.葉子節點以有序鏈表相連，支持范圍查詢依序訪問葉子節點，避免對樹的多次遍歷，使范圍查詢更高效.
然而，B+樹索引的高度有序性使得大數據場景下索引查詢效率降低、索引維序開銷增加，成為限制數據庫性能提升的瓶頸.總結大數據場景下B+樹性能提升面臨的3 個挑戰：
1）訪存性能低.關鍵字查詢通過逐層定位節點實現.由于節點內關鍵字比較結果的不確定性導致對下一層子節點的訪問是隨機的.這種隨機內存訪問使內存帶寬利用異常低效.
2）并行性差.由于查詢需要逐層遍歷節點才能完成，中間結果的不確定性導致逐層遍歷難以實現并行，索引帶來的優勢被削弱.
3）樹的維序難度大.索引維序（索引刪除、插入和修改，其中1 次修改可以看作是1 次刪除和1 次插入的組合）過程會影響樹中間各層節點鍵值的存儲狀態.索引維序導致葉子節點內數據增加或減少，并改變葉子節點內關鍵字順序；
取決于節點內存儲空間容量的限制，也有可能導致中間節點結構的改變.這種不確定的節點狀態改變，使葉子節點內關鍵字維序和中間節點更新復雜且效率低.
由此，如何平衡B+樹的查詢和維序性能，以及在大數據場景下進一步提升索引的查詢和維序效率，成為索引優化的關鍵.
隨著通用計算平臺性能提升放緩[1]，許多研究提出利用GPU 和FPGA 等異構計算平臺加速B+樹的查詢和維護操作[2-4].為充分發揮GPU 異構系統的算力，多數研究從提升索引查詢性能和緩解內存帶寬瓶頸等角度提出解決方法.在SIMD 架構的平臺中，文獻[5-7]提出了提升多條查詢語句并行效率的策略以提升GPU 對B+樹的查詢效率.文獻[8-9]則優化了索引節點的存儲結構，以緩解GPU 的內存帶寬瓶頸.這些研究將重點放在提升索引查詢的性能.利用FPGA 這一類可重構計算架構，文獻[10-11]利用FPGA 分別設計了支持索引的查詢和更新操作的專用計算引擎，并評估了利用FPGA 加速不同體量索引對系統整體性能的影響.但是文獻[10-11]方法欠缺對索引查詢和更新的協同優化，沒有提出B+樹索引系統的均衡優化方案.
為均衡提升大數據場景下數據庫索引的查詢和維護性能，本文系統研究了B+樹索引的查詢和維序的操作特性，提出針對索引訪存和計算的協同優化加速器架構HyperTree，在大數據場景中，兼顧索引的查詢和維序性能的提升.本文的主要貢獻點：
1）提出一種同構的流式計算多引擎架構，既能夠提升單計算引擎的效率，又支持多索引查詢、更新和維序任務的并行；
2）提出一種規則的B+樹節點存儲格式，同時設計專用的內存管理系統以支持低開銷的并行訪存，進一步提升內存帶寬利用效率；
3）提出一種高效靈活的計算控制系統，支持多指令并行和多數據并行，在提升計算引擎性能的同時，不會引入額外開銷；
4）提出一種多子樹結構，將復雜的B+樹拆分為幾棵小的子樹，避免葉子節點的更新沖突，以提升索引的維序效率.
實驗結果表明，相比于CPU，B+樹索引加速系統HyperTree 能夠提升系統查詢性能6.84 倍；
范圍查詢性能提升14.53 倍，且相比單值查詢性能損失很小，平均為單值查詢性能的75.58%；
引入子樹存儲管理系統后，索引維序性能提升超過29.14 倍.
典型的B+樹結構如圖1 所示.內部節點稱為索引節點，按照升序排列存儲關鍵字；
葉子節點既存儲關鍵字又記錄關鍵字指向的數據信息.
Fig.1 Keyword search in B+tree圖1 B+樹的關鍵字查詢
B+樹查詢操作從根節點開始，自頂向下逐層比較內部節點的索引關鍵字范圍，直到找到包含查詢內容的葉子節點.以圖1 所示的等值查詢目標關鍵字11 為例.從根節點開始，將11 與關鍵字2 和10 比較，定位下一層節點應指向根節點最右側子節點.再重復上述范圍比較，定位下一層應指向當前節點最左側子節點.此節點為B+樹的葉子節點，在葉子節點中定位關鍵字11 指向的原數據庫表，結束本次查詢.范圍查詢可以通過等值查詢定位的葉子節點間的指針依次比較關鍵字得到查詢結果.
B+樹查詢性能取決于樹的高度（逐層查找）、節點大小（逐個數據比較）及關鍵字匹配速度.例如：高度為l的B+樹所需查詢時間為l次節點讀取的I/O 延時和mi×l次計算引擎的關鍵字比較處理時間（mi為各節點關鍵字比較的次數）.由此，索引節點的I/O 開銷和關鍵字比較成為限制索引查詢性能的瓶頸.
B+樹的維序過程由數據庫表的插入、刪除和更新操作引起.以索引插入為例，首先通過查詢定位關鍵字待插入的葉子節點位置，然后插入關鍵字.插入前需要判斷插入新關鍵字后葉子節點是否超過規定長度.若沒有超過則結束本次索引插入，否則將該葉子節點平均分裂為2 個新葉子節點，并用新分裂的節點信息更新其父節點.更新時，將新分裂的右側葉子節點的第1 個索引關鍵字插入父節點原關鍵字，并更新葉子節點間指針.葉子節點更新結束后，依層向上重復節點更新過程，直到不需要拆分父節點或找到根節點，結束索引插入.刪除與插入過程類似，區別在于刪除可能導致節點合并，索引更新由刪除和插入組成.以圖2 所示插入關鍵字4 為示例.首先定位關鍵字4 應寫入的葉子節點位置.此時插入新關鍵字后的葉子節點超過規定長度，將該葉子節點分裂為2 個新節點，依大小順序在父節點插入索引值4，同時更新父節點指針.更新后父節點長度未超過規定長度，結束更新過程.
Fig.2 Keyword insertion in B+tree圖2 B+樹的關鍵字插入
數據表的更新，需要首先對葉子節點定位，再修改關鍵字.由于節點存儲空間的限制還有可能向上分裂或合并中間節點.不確定的多層節點操作會引入隨機I/O 讀寫，使得數據表維序的開銷相對于查詢來說大大增加.
在大數據時代，內存數據庫的出現一定程度上解決了傳統硬盤數據庫的讀寫延遲問題[2].然而通用計算卻不足以提供有效算力支持以充分利用內存讀寫帶寬資源[1].研究人員轉而利用異構計算平臺，實現全卸載或半卸載的內存數據庫加速方案提升數據庫的計算效率[2-4].
為提升B+樹的查詢效率，大量研究基于GPU 異構計算平臺設計高效的并行架構[2]，主要優化方向為加速索引查詢[5-6,8]及索引結構優化[7,9,12].GPU 加速索引操作的核心思想是改進查詢的計算模式以充分適配GPU 的SIMD 架構.文獻[5]基于AMD 的CPU+GPU異構系統，提出了粗細粒度2 種并行策略以加速B+樹的查詢.細粒度并行策略將節點的二分查找替換為K-ary 查找，從而使計算引擎執行相同模式的查詢操作；
粗粒度并行策略利用同構的計算引擎同時執行多條查詢.訪存優化主要是調整B+樹內部節點為規則的數據結構，從而充分利用GPU 的高訪存帶寬.文獻[7]設計了一種將索引關鍵字和子節點指針分布存儲的改進樹形結構，以充分利用GPU 的內存帶寬；
并利用SIMD 計算方法設計基于排序的并行查詢方法，進一步緩解查詢時的內存帶寬瓶頸.文獻[12]優化節點內部存儲結構，解決訪存瓶頸，進一步提升查詢并行計算效率.
充分發揮GPU 的并行性能極強地依賴于計算規則且訪存對齊[2].然而索引操作天然具有計算并行難度大、訪存隨機性等問題，導致利用GPU 加速索引操作的性能提升效果有限，從而有一些文獻提出利用可重構硬件加速器設計更加靈活高效的方案.文獻[10]利用FPGA 設計了加速B+樹索引查詢的專用體系結構.利用片上BRAM 存儲部分內部節點地址以達到快速訪問內部節點的目的，同時設計專用并行查詢計算單元，能夠支持節點內關鍵字的快速定位；
而葉子節點和一些低層內部節點的查詢及全部索引維序依靠CPU 實現.文獻[11]補充了文獻[10]的研究工作，設計并行的節點更新計算單元，同時在CPU 端增加1 個調度單元部分卸載索引更新至FPGA，即FPGA 僅處理索引更新的部分操作，一定程度上提升了FPGA 加速B+樹索引的效果.文獻[10-11]利用FPGA 作為通用計算CPU 的補充：CPU 負責數據和指令的卸載，將根節點和部分上層內部節點卸載到FPGA 上加速查詢和更新.但這種方法是半卸載的方案，CPU 仍然需要負責主要的計算，FPGA 僅完成部分協同工作；
且該方法的實現對FPGA 的計算資源和存儲空間利用效率很低，指令并行性差，B+樹索引的性能提升有限.此外，文獻[10-11]將優化的CBS+樹結構作為數據庫的索引格式，雖然降低數據傳輸開銷及FPGA 端地址計算復雜度，但給系統引入了額外的索引格式轉換開銷.
近年來，隨著FPGA 板卡內存空間和帶寬性能的不斷提升，利用FPGA 加速內存數據庫性能提升顯著[2,4].鑒于FPGA 結構更加靈活、資源可配置等特性，本文基于FPGA 異構計算平臺，設計并實現了全卸載B+樹索引加速系統HyperTree——將索引的存儲，B+樹構建，索引查詢，索引插入、刪除和修改全部寫到FPGA 執行.在本文所提出的 CPU-FPGA 構成的異構計算系統中，CPU 只負責查詢計劃的生成和優化以及加速器的啟動運行和管理.
基于第1 節對B+樹典型操作的描述，本節將對B+樹各操作性能瓶頸進行深入分析.
3.1 數據隨機訪存造成存儲帶寬利用率低下
B+樹查詢時內存帶寬利用非常低效：一是由于節點的隨機訪存；
二是由于樹的訪存管理復雜.在B+樹索引查詢時，下層節點的訪存地址由當前層節點內部關鍵字的比較結果決定.結果的不確定性導致每層節點的訪存是隨機的，且中間節點在內存中依靠指針相連，每個節點的數據結構不完全相同，節點的物理地址也是隨機的，進一步增加訪存隨機性.B+樹的存儲管理需要對內存空間動態維護.當執行索引插入和刪除操作時，可能需要動態申請或釋放內存空間.為維護節點的樹形結構，需要動態修改對應的內存空間狀態，該過程的存儲訪存也是隨機的.此外，數據量的增加導致實際應用中B+樹標準格式規定的節點存儲空間無法完整保存1 個數據表內的全部索引信息.從而維護1 個數據表索引需要管理多棵B+樹，進一步加劇了內存空間管理的困難.這種數據訪存隨機性導致的問題無論是CPU 還是GPU 都無法直接解決，也是導致GPU 的高訪存帶寬無法被直接有效利用的根本原因.
為驗證隨機內存訪問帶寬的性能，通過實驗在實際數據庫中測試DDR4-3200 內存訪存特性（其標稱內存帶寬為204.8 Gbps）.隨著讀寫地址空間范圍的增加，實際讀寫帶寬有一定提升，但只有訪存達到突發讀寫長度時，理論最大帶寬才能被充分利用.如圖3 的實驗結果顯示，單字讀寫、隨機讀寫帶寬實際只能將近標稱性能的60%，甚至更低.
Fig.3 Practical efficient read/write bandwidth of DDR4圖3 DDR4 的實際有效讀寫帶寬
3.2 查詢并行度低下影響查詢性能
單節點的查詢和比較難以并行，是大數據量下查詢性能下降的關鍵原因.在B+樹設計中，為優化中間節點訪存帶寬，可以通過盡可能擴大中間節點容量（節點內數據連續存儲）的方法實現.然而，中間節點數據量的增加加劇了節點內關鍵字查找的難度.有研究表明，利用GPU 加速索引操作，即使是改進的算法，例如順序查找、二分查找、并行查找，單條查詢的性能提升仍然十分有限[6].
多查詢語句并行是進一步提升系統性能的關鍵.但現有的CPU-GPU 異構系統由于無法在隨機訪存時充分利用內存帶寬，且查詢時計算結果隨機性強，從而難以提升并行度[5-6,12].對于樹的訪存來說，有限的內存帶寬無法滿足多處理引擎對數據讀寫速度的需求；
且每次訪存的地址空間范圍有限，進一步降低讀寫效率.對于計算來說，處理引擎的比較和查找能力決定了單條查詢語句的效率，而處理引擎的數目決定了查詢的并行度上限.當單引擎的計算性能受限時，并行帶來的性能提升十分有限.
3.3 更新維序復雜大大降低插入性能
索引提升了數據查詢的效率，但樹形結構的高度有序性使索引維序操作復雜.修改數據庫表記錄，包括記錄的增加、刪除或更新，需要同時修改索引.索引的維序對修改數據庫表記錄造成額外開銷.以索引的插入為例，受限于節點容量的限制，關鍵字插入可能引起節點分裂.節點內數據量一旦超過容量閾值，節點的分裂可能自葉子節點出現，并向上逐級影響父節點直到根節點.但這一過程是否出現取決于節點內原有關鍵字的容量和分裂后的節點關鍵字，難以提前預判計算和預取數據，導致索引插入的執行效率很低.這種計算的不確定性對GPU 的SIMD架構極不友好.
索引的維序會阻塞對同一棵樹的其他操作，影響指令并行性能.在本條維序操作結束前，節點內數據容量的差異和樹形結構的數據依賴性導致無法預測其結構變化.索引維序過程對正在執行的樹具有獨占性，即阻塞對同一棵樹的其他操作，從而當索引維序請求發生時，無法實現多指令并行，進一步降低B+樹索引維序的性能.
第3 節的分析表明：訪存效率低和計算并行難是造成B+樹查詢性能差的主要原因；
維序的復雜操作以及維序操作的數據依賴使得加速索引維序更加困難.本節將從訪存效率提升、單節點計算效率提升、計算并行優化及解除維序的數據依賴4 個方面，提出提升B+樹查詢和維序性能的設計思想.
訪存優化的關鍵是利用主存 DRAM 突發讀寫帶寬高的特性來提升帶寬利用率.DRAM 存儲器的特點是連續地址讀寫性能高效，即可以利用突發讀寫機制實現對B+樹各節點的讀寫.在B+樹中，節點內在關鍵字比較時被反復訪問，這也意味著B+樹中間節點數據量越大，數據讀寫效率越高.因此，中間節點的數據量大小、存儲格式以及讀寫方式是本文優化的重點.
然而單節點的數據量增加意味著在查找過程中需要進行更多次數據比較才能找到指向下一級滿足條件的節點指針，對計算引擎的查詢性能提出了更高的要求，從而提升單節點計算效率成為提高計算性能的首要保證.為進一步提升查詢性能，語句級并行是提升系統性能的另一個重點.由此提出設計一種高性能的同構流式計算處理引擎架構以提升單查詢語句的執行效率，并進一步提升多查詢語句的并行度.
大節點引入使得索引維序的過程更加復雜.一方面，定位待修改的關鍵字位置的查詢過程延遲變長；
另一方面，節點內數據量增加導致更高的數據修改開銷.上述2 步驟的延遲和開銷進一步加劇了索引維序導致的數據依賴，阻塞其他對同一棵樹的索引操作.因此，提出解除語句間數據依賴以提升索引維序性能的方法，其核心思想是將單棵B+樹拆分成多棵子樹，能夠支持對單棵 B+樹操作轉為對不同子樹的操作.由于子樹間彼此獨立，從而實現多插入更新操作并行.具體地，我們采取了5 個關鍵優化.
4.1 節點訪存優化
為了提升節點數據的訪存效率，首先要確定樹節點的存儲格式.樹節點存儲格式設計需要解決2 個核心問題：1）單節點的訪存效率，節點大小要符合DDR控制器的特性；
2）存儲可擴展性設計滿足不同大小樹的存儲需求.
設計節點大小的原則以DDR 控制器所支持突發（burst）長度為基準，規定單個節點的大小為突發長度的整數倍.比如Xilinx FPGA 板卡突發傳輸為512 B，可以設計節點大小為512 B 或1024 B 或其他1 次突發讀寫大小的整數倍空間.但一般來說，為降低單節點存儲可能造成的存儲空間浪費，單節點的設計不宜過大.同時規定每次內存讀寫都以1 個節點大小為單位，從而保證在對索引存儲節點的每次數據讀寫都充分利用內存帶寬.
為簡化B+樹的存儲管理，規定以內存塊的方式維護單棵B+樹，一個完整的索引可以由單棵樹或者多棵樹構成，樹的組織結構在內存塊中完成.每個內存塊（即1 棵樹）包含多個節點，每個節點存儲多個索引關鍵字.多樹的可擴展性設計的關鍵是進行樹的動態維護.規定內存空間的動態申請和回收也按照塊進行，即創建新B+樹時，按塊申請內存空間構建索引；
刪除B+樹，也相應地按塊釋放內存空間.以內存塊為最小訪存管理對象，使得內存管理更加簡潔高效.
4.2 高效的訪存管理
確定了樹的存儲結構，接下來要解決的是如何實現處理引擎對樹和節點的數據訪問，即如何快速實現樹和節點從邏輯編號到物理存儲的映射，以及如何高效地將內存數據加載到處理單元.訪存管理需要解決2 個關鍵問題：1）邏輯樹和節點到物理存儲的映射，包括物理空間的申請和釋放；
2）為多處理引擎提供有效的計算數據.
規則的節點設計能夠簡化B+樹節點的地址空間管理.定義一棵B+樹在內存中存儲的數據格式為樹表，每棵樹表對應特定的內存塊.樹表的最小數據組織單位為行，行大小一致，每行表示1 個節點.計算引擎直接對節點內的索引關鍵字進行操作，其訪存過程首先確定樹表的內存空間，然后定位節點的內存地址.由于索引的查詢和維序操作均在1 個或多個節點內完成，為充分利用內存讀寫帶寬，每次I/O 讀寫均以1 個節點為單位.然而，由于索引維序時節點的動態修改對每個節點的地址管理仍然很復雜，需要解決新節點物理地址的申請或原節點物理空間的釋放.
執行查詢操作時，內存訪問均以B+樹根節點開始，并依層次順序訪問內部節點，直到葉子節點結束.為降低節點內存訪問的控制成本，提出構建專用的樹表存儲管理單元（tree-table memory manage unit, TMMU）實現快速從B+樹邏輯地址到樹表節點內存物理地址的映射，以降低內存空間維護的復雜度，并提升計算訪存的效率.TMMU 記錄 B+樹和內部節點的相關狀態信息，保證在樹或節點創建或刪除時，能夠動態維護樹和節點的有效性.
4.3 流式計算架構
利用流式計算的原則設計專用處理引擎從而提升節點內關鍵字查詢的性能.相比于其他批量計算，流式計算有2 個主要的優勢：1）無狀態執行，控制簡單，數據驅動有利于多任務并行；
2）全流水執行，效率高，部分數據到達即可進行處理.圖4 示例了流式計算與批量計算的區別.與傳統的批量計算不同，流式計算每次只對規定窗口大小的數據進行計算，而無需等待全部數據輸入到計算節點.圖4 示例表明，流式計算的控制簡單，計算僅以數據流為驅動，沒有復雜的控制邏輯結構.
Fig.4 Difference between streaming computing and batch computing圖4 流式計算與批量計算的區別
4.4 多查詢語句并行
規則的節點存儲結構和高效的數據管理單元為多語句并行執行提供了快速有效的原始計算數據，解決了帶寬與計算性能不匹配的問題.數據管理單元配合內存控制單元，能夠提供連續不間斷的數據訪存通路，為多計算引擎提供計算所需的數據.
實現多查詢語句并發的另一個關鍵條件是指令間的調度和控制，即查詢指令如何映射到多處理單元.為最大化多語句并行度，并簡化控制邏輯，提出同構的流式計算引擎陣列設計.同構計算引擎，即所有處理單元架構一樣，每個處理單元可以支持包括查詢、刪除、插入和更新在內的全部索引操作.同時，由于各處理單元采用流式計算實現，進一步降低其控制邏輯的復雜度.基于上述設計，多查詢指令的并發管理變得異常簡單高效，當有新的計算指令時，可以快速分配到任一空閑處理引擎執行，而不需要對各處理單元分類別管理.同構的處理引擎設計也會避免計算任務和處理單元類型不匹配而導致資源浪費.相比于如圖5 所示的異構設計，采用同構設計處理單元存在一定的冗余而使得硬件資源開銷增加，我們也在降低開銷上做了很多精細設計，詳細見第5 節.
Fig.5 Difference between homogeneous and heterogeneous computing units圖5 同構計算單元與異構計算單元的區別
4.5 提升索引維序性能的子樹結構設計
為緩解索引維序的獨占性而導致的性能損失，提出解耦合的子樹結構設計，以解決由于索引維序導致的多語句并行阻塞現象.子樹是將1 棵完整的B+樹按照一定的方式拆分為幾棵小的子樹，且規定每一棵子樹的構建嚴格遵循B+樹索引的結構要求.為支持子樹查詢和維序的并行，內存管理模塊也需要進行相應的修改：查詢和維序操作的起始訪問從內存空間的入口地址（即大樹的根節點）變為子樹的根節點對應的內存地址.具體地，創建新樹時仍然申請1 個新的內存塊；
但是在構建樹的過程中，按照某種規則選擇內存塊的某些地址作為子樹的根節點地址，并將樹構建的過程平均至每一棵子樹，直到完成1 棵樹的創建.相應地，查詢操作的起始地址將變為子樹入口地址（即子樹根節點），而不再是原始的大樹入口地址（根節點）.這樣設計的優勢在于，由于子樹間沒有數據依賴，對同一棵大樹但不同子樹的多條插入和更新操作可以并行執行，即實現將對1 棵大樹的串行操作轉化為對多棵子樹的并行操作.
子樹的劃分粒度是子樹設計中需要考量的重要設計參數.劃分子樹時，劃分粒度越細，索引更新可以在更多棵子樹中并行，數據并行度增加，從而提升計算并行效率.但劃分越細粒度，子樹根節點的入口地址維護會越復雜，且劃分越細將丟失越多索引結構信息，對樹的索引結構利用效率降低；
反之，子樹劃分粒度越粗，子樹棵樹越少，數據依賴越多，計算并行提升有限.但粗粒度的劃分方式能夠更好地利用索引結構信息，且子樹控制邏輯簡單，能夠緩解硬件資源開銷.
按照第4 節中提出的優化策略，本節主要介紹基于FPGA 實現的B+樹索引加速系統HyperTree 的具體實現和系統運行流程.HyperTree 統包含3 個主要的子系統，如圖6 所示：存儲管理子系統、索引計算子系統和指令控制子系統.其中，存儲管理子系統包含TMMU 和內存控制單元.在得到激活控制信號后，TMMU 負責將指令中的邏輯編號轉換為內存物理地址.內存控制單元將TMMU 輸出的物理地址中的內存數據傳遞到計算引擎，或按照計算引擎給出的結果寫回相應的內存空間.指令控制子系統負責解析索引操作指令，提取操作碼和操作數，并根據操作碼和操作數依次激活指令執行單元并打開內存數據通道，負責指令并行控制.索引計算子系統由多個同構的計算引擎構成，負責并行執行索引的查詢、插入、刪除和更新指令.其中，存儲管理子系統和指令控制子系統是實現多語句并行的直接控制邏輯單元，索引計算子系統是執行計算并行的核心功能部件.接下來分別對各部分關鍵模塊的實現進行介紹.
Fig.6 System overall architecture圖6 系統整體結構
5.1 節點存儲格式設計
根據第4 節中節點的設計原則，在微結構實現時以512 B 為單位定義節點大小.以128 MB 內存塊大小為單元設計樹表，則樹表共包含218行（即節點），在存儲塊內的標號為0～218-1.樹的大小可以通過改變單位節點大小或樹表容量相應調整.給定固定容量的B+樹，如果1 棵樹滿，可以通過動態申請存儲塊，創建1 棵新樹以實現數據庫表的完整索引結構.該過程利用軟件指令顯式維護.B+樹的節點格式規則定義如圖7 所示.B+樹包含3 種不同的節點類型：內部節點、葉子節點和等值節點.其中，內部節點只存儲關鍵字，葉子節點和等值節點存儲關鍵字和衛星數據（衛星數據指向數據表中的一條數據記錄）.兩者的區別在于，葉子節點指向不同關鍵字對應的記錄，而等值節點指向相同關鍵字對應的記錄.等值節點由葉子節點維護，葉子節點內的等值索引指針若為0，則原始表位置信息有效，直接指向原始數據庫表中的記錄；
否則，等值索引指向等值節點.為簡化索引關鍵字的尋址過程，設計8B 對齊的節點存儲格式.3類節點的格式組織基本相同，都是由節點頭部和節點數據2 部分組成.節點頭部主要標識節點類型及記錄指針；
數據部分主要存儲索引關鍵字和指向子節點或表邏輯地址的指針.
Fig.7 Data structure definition of tree-table圖7 樹表的數據結構定義
規則的節點設計及以節點為單位的訪存規則有效地提升了系統的內存帶寬和內存空間的利用率.以突發讀寫長度為單位設計節點容量，使計算引擎在處理節點內數據時，能夠充分利用突發讀寫的高帶寬，提升內存讀寫效率.節點指針以邏輯地址的形式存儲，所占內存空間更小，且標識節點特征的部分僅占節點頭部的1/4，提升了節點對索引關鍵字及指針的存儲效率，確保最大程度利用內存空間.此外，規則的節點格式設計簡化了計算引擎對數據解析的過程.在處理單節點內部信息時，進一步提升計算性能.
5.2 存儲管理單元
為充分利用內存帶寬，降低樹表地址維護開銷，提出專用樹表存儲管理單元TMMU，其主要實現2部分功能：一是實現邏輯地址到物理地址的快速映射；
二是高效地將數據傳遞到計算引擎.
快速的地址映射能夠簡化軟件對內存地址的管理，并提升節點存儲空間的存儲效率.在實際應用中，軟件不直接管理B+樹的節點地址，從而維護索引物理地址被轉換為硬件開銷.通常計算指令的操作數所攜帶的信息是B+樹的標識tree_ID；
根據樹表的設計原則，所得到的節點指針也只存儲其邏輯地址（以Num表示）.TMMU 的主要任務之一就是實現B+樹的標識tree_ID及樹內節點邏輯地址與B+樹根節點入口地址及節點物理地址的映射，并維護樹表基本信息和節點的有效性.TMMU 的地址映射由圖8 所示.
Fig.8 Address mapping in TMMU圖8 TMMU 的地址映射
TMMU 中維護地址映射，為充分利用緩存讀寫帶寬，映射表的1 行與緩存單次最大讀寫位寬相同.表中的一行記錄樹的標識編號tree_ID、根節點入口地址（記為Addr）、樹深度、節點個數等信息.根節點映射表中以有效位1 表示該條記錄有效，否則該位置可以被改寫.當指令輸入tree_ID，TMMU 通過樹表映射表確定樹表的根節點入口及相應信息；
再依據節點的邏輯地址，根據式（1）中給出的映射關系計算其物理地址，其中單位尋址空間的單位為B.節點邏輯地址到物理地址的映射計算簡單，硬件計算資源開銷很小.
TMMU 可以實現對樹表的動態維護.新建或刪除B+樹時，TMMU 根據對內存空間動態申請或釋放的結果，在樹表映射表中根據有效位信息增加或刪除相應的tree_ID與樹表信息的記錄.指令拆分或合并節點時，TMMU 負責修改樹表中樹的深度和節點個數信息.為簡化樹表管理，規定增加節點時邏輯地址相應加1，刪除節點時不修改原有節點的邏輯地址，下次增加節點仍然在現有邏輯地址的基礎上遞增.這樣的實現方式雖然造成節點刪除時存儲空間的浪費（這種空間損失代價很小，每一個節點僅占樹表結構的1/218），但能夠極大地簡化樹表管理的控制邏輯.
TMMU 的另一個主要功能是充分利用內存讀寫帶寬，實現高效的內存讀寫.隨著指令控制單元依次解析指令隊列中的指令內容，TMMU 接收到節點邏輯地址后立即計算物理地址，內存管理單元打開內存通道，將對應內存空間內的數據傳遞到指定的計算單元.TMMU 對數據的處理是連續的，即只要接收到指令流的邏輯地址，則執行物理地址的計算并打開數據通道，對內存塊內的數據進行緩存.該設計相當于實現了計算引擎的數據預取，消除計算時數據讀寫所引入的I/O 訪問延遲.TMMU 通過緩存機制實現內存的連續訪問并形成數據通道.每個計算引擎獨占1 個數據通道，TMMU 以輪詢的方式依次打開并完成數據傳輸，能夠充分利用內存的高讀寫帶寬.
5.3 流式計算引擎設計
對于單計算節點，提出設計流式計算架構以支持高效的索引計算.流式處理引擎不需要復雜的控制電路，計算以數據流為驅動，即只要在輸入端有數據則計算會持續進行，不需要復雜的狀態控制機制.流式計算引擎能夠最大程度提升單節點的計算性能.單個計算引擎的內部結構如圖9 所示.計算引擎內有1 個地址緩存單元和1 個節點緩存單元，分別用于暫存TMMU 傳遞到計算引擎的節點地址和節點內容.讀數據緩存FIFO 按照8B 對齊的原則讀取數據緩存單元內的節點數據，以指針和關鍵字組的順序依次寫入.只要讀數據緩存FIFO 不為空，則比較器執行待比較關鍵字與節點內關鍵字的比較.讀寫控制單元由指令操作碼決定其打開或關閉.如果操作碼指示了關鍵字的插入或刪除，讀寫控制單元打開，節點地址緩存當前節點的地址，寫數據緩存FIFO 依次讀取節點內的數據內容.當定位到待比較關鍵字的位置，寫數據緩存FIFO 根據指令控制插入或刪除待比較關鍵字并更新指針內容.節點內關鍵字全部寫入寫緩存FIFO 后，讀寫控制打開內存通道，根據地址緩存中的地址更新節點內容.由于索引維序的前序依賴是關鍵字查詢，在同構計算引擎設計中，硬件資源的冗余開銷只有讀寫控制單元和寫數據緩存2 部分.相較于異構計算引擎的復雜狀態控制來說，這部分硬件資源冗余幾乎可以忽略.
計算引擎的執行過程以流水線方式進行，工作流程按照查詢和維序過程分為2 大類.查詢時，讀寫控制無效，僅有讀數據緩存、比較和結果寫回3 個階段.當比較器得到待查詢關鍵字期望位置時，輸出關鍵字所在位置的指針信息.期望位置是指，葉子節點內關鍵字相等，或內部節點中關鍵字大于前一個關鍵字且小于后一個關鍵字.此時，如果葉子節點沒有相等關鍵字，則輸出不存在該數據.輸出的指針信息為葉子節點的衛星數據或等值節點邏輯地址，以及內部節點的葉子節點的邏輯地址.插入或刪除時，讀寫控制有效，包括讀數據緩存、比較、寫數據緩存和結果寫回4 個階段.指令打開讀寫控制單元，寫數據緩存將讀數據緩存內數據和待比較關鍵字根據比較結果的期望順序依次讀入.期望順序是指大于前一個關鍵字且小于后一個關鍵字，或存在與原有關鍵字相等的等值節點則輸出指向等值節點的邏輯地址.
為簡化節點的地址管理，降低節點動態維護的開銷，對節點的合并和拆分進行規定：當且僅當節點內數據為空才執行節點的刪除，當且僅當節點內數據量超過512 B 時才執行節點的創建.節點刪除需要刪除上層父節點中的指針和索引關鍵字.節點的插入對當前層節點進行修改，寫數據緩存將前一半指針和關鍵字組寫入當前節點，將后一半指針和關鍵字組寫入新的節點地址空間，并在上層父節點中插入關鍵字和指針信息.這2 種操作需要同時更新TMMU 中樹表的深度、節點數等信息.
5.4 指令控制子系統
指令控制子系統主要包括指令解析模塊、計算控制單元和內存控制單元，其結構如圖10 所示.其中，指令解析單元分離指令中的操作數和操作碼，解析索引計算類型及節點和樹表邏輯地址.計算控制單元查詢處理引擎的執行狀態，啟動可執行的計算.內存控制單元將邏輯地址寫入TMMU 完成地址映射，判定編號為tree_ID樹的執行情況，并打開可訪問的編號為tree_ID樹的內存地址，完成處理引擎對數據的緩存.
Fig.10 Instruction control system圖10 指令控制系統
為提升系統性能，設計多個同構計算引擎以實現指令集并行.計算引擎的并行由指令控制單元和內存控制單元共同管理，其結構如圖11 所示.計算控制單元為每個處理引擎維護一個寄存器，寄存器中包含處理引擎是否空閑標志位Dest_ID、處理引擎正在執行的操作類別及處理引擎在處理的tree_ID信息.計算控制單元獲取指令隊列中的首條指令，查詢處理引擎寄存器信息，找到空閑的處理引擎，并判斷當前指令及所有正在執行狀態的處理引擎中是否存在對該指令tree_ID的更新操作.有則阻塞指令并發；
否則發送指令操作碼到該空閑的計算引擎，并修改寄存器相關信息.最大指令并行數與計算引擎數目相同.當計算引擎狀態寄存器Dest_ID空間被賦值，說明計算引擎已經完成對本條指令的執行，此時可以修改寄存器標識為當前計算引擎為空閑，并清除執行信息.
Fig.11 Design of homogenous fully functional multiprocessing engines圖11 同構的全功能多處理引擎設計
5.5 指令設計
為配合系統的執行，設計支持的索引操作的指令如表1 所示.指令集包含2 類指令：基本指令和附加指令.其中基本指令是直接規定索引和樹操作的指令，包括樹的操作和關鍵字操作2 類；
附加指令用于部分基本指令的重定義和操作控制，包括范圍查詢和關鍵字更新2 類附加指令.
Table 1 Design of Instruction Set表1 指令集設計
5.6 B+樹子樹系統
由于索引維序操作與其他操作之間存在強數據依賴，設計一種子樹結構以解除這種數據依賴，其結構如圖12 所示.子樹結構使得對1 棵大樹的一次性訪問可以拆分為多棵子樹的多路訪問.也就是說，操作指令將不再以原始大樹的根節點作為源操作數，而是以子樹所在連續空間的起始地址作為訪存的入口地址，只要讀寫不同子樹空間，則對同棵大樹操作的多條指令可以并行.
Fig.12 Sub-tree structure and TMMU management圖12 子樹結構和TMMU 管理
為降低對子樹入口地址管理的復雜度，并提升子樹劃分方式的靈活性，將1 棵大樹的內存地址空間（即樹表）等分為幾段連續子空間，以每部分子空間的起始地址作為子樹的入口地址.子樹入口地址為
其中i表示在大樹中的第i棵子樹（i從0 開始計數），子樹空間subtree_space的單位為MB.
對齊的子樹空間設計降低了內存地址管理的復雜性，也降低了地址映射計算資源的開銷.子樹的大小可以由地址空間范圍劃分方法靈活決定，即子樹空間劃分粒度可以根據實際應用需求設定，這種設計方式實現了靈活性與高效性的權衡.從而，在不同數據量和并發查詢請求需求下，有效提升B+樹的并行讀寫效率，避免引入復雜的子樹空間管理開銷.子樹劃分對查詢操作性能和資源的影響在第6 節中具體評估.
為維護子樹的狀態，在TMMU 的根節點映射表中加入與邏輯地址對應的子樹的層數及內部節點數的記錄.在插入新的索引關鍵字時，為均衡子樹的訪問頻率，在TMMU 中加入一個專用的輪詢仲裁器管理子樹空間的訪存順序：按照子樹的內存空間順序依次檢查子樹空間的訪問狀態，在可訪問時申請對子樹的訪問，否則對下一棵子樹進行檢查.
顯然，子樹的引入改變了B+樹索引構建的方式.為配合子樹結構，提出支持查詢和維序的優化設計，其優化進程如圖13 所示.在B+樹索引構建及新關鍵字插入時，計算引擎按照B+樹創建指令的要求從內存中申請開辟一段連續的空間用于存放樹表，即邏輯結構上的1 棵完整B+樹.隨后，將此段空間平均分配為n段連續子空間，并在TMMU 中分別記錄這幾棵子樹的信息.在當前樹表中，每插入1 個新的關鍵字，則以輪詢的方式依次分配1 段子空間入口地址，依照關鍵字插入的順序依次在子樹中插入索引關鍵字.按照這樣的規則，子樹仍然保持B+樹的特征，但子樹構成的大樹不維持邏輯索引結構.引入子樹結構能夠提升數據維護時樹的并行讀寫效率.根據TMMU 的設計原則，對樹的管理也不會由于引入子樹空間而過于復雜.
Fig.13 Sub-tree structure and query optimization圖13 子樹結構和查詢優化
子樹系統改變了索引指令的尋址方式，影響了指令的執行過程.關鍵字插入可以按輪詢的方式選擇子樹.但是，查詢和刪除需要定位關鍵字所在的葉子節點，不能以輪詢的方式選擇子樹，而大樹沒有邏輯上的索引結構，需要引入一種快速定位到包含關鍵字的子樹的機制.為準確定位查詢和刪除操作中關鍵字所在的子樹，在子樹空間選擇前加入1 級布隆過濾器[13].布隆過濾器是一種快速判斷某元素是否在集合中的功能部件.利用布隆過濾器提前過濾1 次關鍵字的位置，就可以快速定位關鍵字所在的子樹空間.將該子樹的入口地址發送到空閑的計算引擎，子樹內執行查找和刪除與大樹完全相同.子樹系統使得索引查詢引入了1 級布隆過濾器的計算開銷，計算只需要幾個周期，對性能的影響幾乎可以忽略.
5.7 系統工作流程：多索引查詢指令
基于5.1～5.6 節所述的系統實現，我們以多條索引查詢指令為例，介紹系統運行的過程，如圖14 所示.當用戶發出多指令請求時，指令按照順序依次進入指令隊列.①指令處理：指令處理單元將按照隊列順序依次處理隊列中的各條指令.②指令解析：指令處理單元將得到的指令逐條解析，得到操作數和操作碼.③激活TMMU：操作數中對B+樹的訪存地址傳遞到TMMU.TMMU 查詢子樹的訪存狀態，進行邏輯地址與物理地址的映射，得到子樹的入口物理地址.④打開數據通道：按照子樹的內存地址輪詢結果，內存管理單元打開可用的內存數據通道，使得節點內容能夠到達相應的計算節點.⑤激活指令控制單元：操作碼和操作數中的關鍵字被傳遞到指令執行單元，指令執行單元管理計算引擎.⑥計算引擎：指令控制單元依次查詢計算引擎狀態，激活空閑計算單元，修改相關寄存器內容.若沒有空閑計算引擎則等待，直到找到空閑計算引擎.其中①②隨指令流的控制連續不斷地執行；
③④和⑤⑥為異步控制.⑦執行計算：計算引擎按照操作數和操作碼的指令，啟動查詢或節點修改的執行流程.⑧結果寫回：查詢時，僅輸出查詢關鍵字指向的衛星數據的地址.更新時，則按照寫數據緩存內容和地址緩存中的地址修改相應節點內容.如果葉子節點需要刪除，無需寫回數據，只修改父節點及 TMMU 中的相關信息.如果節點需要拆分，則將數據均等分為2 部分，分別寫入2 個節點，并修改父節點和TMMU 相關信息.
Fig.14 Index query of B+tree accelerating system圖14 B+樹加速系統的索引查詢
6.1 實驗搭建
實驗的硬件平臺利用PCIe 接口搭建CPU 服務器與FPGA 板卡互聯的異構計算系統.CPU 型號為Intel Xeon Gold 5218（@2.30GHz）配備22 MB 的L3 緩存和64 GB 的內存（DDR4-2667）.FPGA 板卡選用Xilinx Alveo 的U200，U50，U280 數據中心加速卡.CPU與FPGA 的互聯接口為PCIe3.0 ×16 總線.實驗分別測試3 種不同資源配置（即異構系統選擇不同FPGA板卡）下本方案的性能.FPGA 加速板卡具體資源配置情況如表2 所示.
3 個板卡的主要區別在于其硬件邏輯資源和內存帶寬限制不同.U200 邏輯資源充足但內存帶寬受限，其上僅配備了DDR4 作為存儲資源，可提供76.8 GBps存儲帶寬；
U50 是一種輕量級的板卡，其硬件邏輯資源是三者之中最少的，但它使用了第二代高帶寬內存（high bandwidth memory，HBM）資源HBM2，內存帶寬能夠達到316 GBps；
U280 則是三者之中性能最高的，其硬件邏輯資源最多，且內存使用DDR4 和HBM2，既保證了存儲空間大且帶寬高達460 GBps.
為評估數據庫索引的查詢和維序性能，實驗的數據和程序選擇數據庫基準測試程序TPC-C 中提供的標準數據庫表生成數據和聯機事務處理（on-line transaction processing, OLTP）程序，以充分測試數據庫表記錄的查詢、刪除、插入和更新的實際性能[14].TPC- C 數據集用9 個相關的數據表記錄了某類倉庫在不同地區的存貨量、存儲的不同商品庫存以及地區消費者信息和貨物訂單等信息.在這9 個數據表中，選擇最大數據表order_line 作為本實驗測試用數據.測試數據表的查詢、插入、刪除和更新性能，對應TPC-C 基準測試中訂單信息查詢、提交客戶新交易申請、交易結束刪除訂單信息，以及訂單修改申請.實驗運行所選擇的關系型數據庫為典型的MySQL數據庫.在本實驗測試中，測試用的數據庫表數據仍然存在CPU 主機上，僅在 FPGA 板上內存預先存儲需要構建索引的部分表信息.此時認為HyperTree 可以屏蔽與CPU 進行數據傳輸的開銷；
HyperTree 可以單獨完成指令要求的索引操作，即從索引構建并存儲B+樹索引數據，到完成相應的事務處理的全過程.實驗的比較基準選擇CPU 并行執行TPC-C 數據庫索引查詢和維序的性能.進一步評估實驗結果，選擇目前具有最優效果的基于 GPU 實現的 B+樹索引加速系統結果[5,7]以及基于FPGA 實現的B+樹加速器結果[10-11]進行對比和分析.
在6.2 和6.3 節中，以Alveo U200 板卡作為B+樹索引加速系統HyperTree 的硬件實現原型.此配置方法能夠均衡考慮片上硬件計算資源和帶寬資源的限制，設計32 個并行的計算節點和32 路數據通道實現對資源的充分利用（具體細節評估見6.4 節），配置信息見表3.在這樣的系統配置環境下，能夠充分利用FPGA 板卡的內存帶寬資源，且不會引入冗余的計算引擎，引入不必要的硬件開銷.
Table 3 Hardware Configuration of B+tree Index Accelerator Using Alveo U200 FPGA Board表3 基于Alveo U200 FPGA 板卡的B+樹索引加速器硬件配置
6.2 索引查詢性能
本節主要評價多查詢語句的并行性能.以6.1 節中介紹的實驗環境和實驗數據為基礎，實現B+樹索引加速系統HyperTree.實驗評估指標有2 個：一是以每秒執行查詢指令數目條數QPS（query per second）作為衡量系統性能的指標，其中實驗結果QPS 實際值的數量級為百萬條每秒；
二是以指令平均響應時間衡量每條指令的執行時間，用于驗證OLTP 是否滿足應用系統的實時需求.
評估數據庫表的數據量對系統性能的影響.為充分釋放處理引擎的并行度，指定實驗中測試的并發指令數目為 32.在實驗中按照樹表格式的設計規則，將數據庫表大小的不同直接換算為B+樹索引中節點數目的不同，從而可以以節點數目的差別描述不同容量的B+樹.由于比較基準測試中節點格式不同，節點可存儲的關鍵字數量存在差別.后序實驗為公平對比，每組實驗均基于具有相同節點數目的 B+樹完成.事實上，基于CPU 和文獻[10]中的方法所生成的B+樹要比HyperTree 基于規則節點格式生成的B+樹更小.由此，為公平地評估不同 B+樹索引加速系統的性能隨數據量的變化，實驗結果的對比保持B+樹的節點數目的數量級一致，且在樹結構的限制下盡可能保證數量相近.實驗評估時，以B+樹索引加速系統HyperTree 生成的 B+樹的容量作為數據量數量級的基準，圖15“數據量”指HyperTree 生成的樹.此外，由于樹存儲格式的設計具有明顯區別，后續的實驗結果對比也僅考慮節點數目相同或維持同一數量級，而不直接以樹的大小作為實驗性能對比的指標.
Fig.15 Normalized throughput of B+tree accelerator圖15 B+樹加速器的歸一化吞吐量
圖15 顯示了系統在B+樹的數據量變化下指令查詢的歸一化性能（以CPU 單值查詢為單位1）.當在小數據量測試環境下時系統的吞吐量大約是CPU的11.14 倍；
當在大數據量的情況時，系統的查詢性能提升大約為CPU 的6.84 倍.小數據量時獲得顯著性能提升的原因主要是：緊湊的節點存儲使得進行B+樹查詢時層間跳數更少，且節點規則格式設計使系統對內存帶寬利用更加高效.大數據量時，B+樹索引系統HyperTree 在進行關鍵字查詢時需要更多層內部節點來構建索引，從而增加了內部節點層間的跳數，使得查詢平均延遲增加.實驗結果表明，B+樹索引加速系統相比CPU 能夠獲得顯著的性能提升.這一結果遠超于文獻[10]中利用FPGA 實現的B+樹索引查詢方案所獲得的結果，相較于CPU 性能僅平均提升1.31～2.24 倍.
在多指令并發查詢的實驗中，以TPC-C 數據集提供的order_line 表為模板，按照規定的數據格式隨機生成數據表，每個表包含 6.5～26.2 萬行記錄.這樣，利用其中待查詢的關鍵字段構建 B+樹索引可以保證單棵樹內的節點全部有效，從而節點的數量級維持在 105，大約要求樹表有效節點存儲空間的容量為10～128 MB.實驗設計單值查詢和范圍查詢2 類查詢指令，單次并發指令數目從10 條開始以10 倍量級遞增至100 萬條.圖16 顯示了系統在不同指令并發狀態下歸一化后的系統性能（以CPU 單值查詢為單位1）.當并發指令數目為10 時，計算引擎沒有被占滿，此時系統的性能明顯低于其他多指令并發，但仍是CPU 性能的3.21 倍.隨著并發指令數的增加，由于查詢關鍵字在節點內的位置具有不確定性，系統性能具有一定波動性，但與32 條指令并發的最優性能大體一致.與CPU 在范圍查詢時性能顯著下降有所不同，B+樹索引加速系統HyperTree 的32 長度的范圍查詢的性能大約是其單值查詢的75.58%，性能損失不明顯，能夠達到 CPU 性能的 14.53 倍.這是由于B+樹索引加速系統的規則大節點設計以及高效的并發讀寫機制，在范圍查詢時進行葉子節點讀寫過程中能夠以較小的節點跳樹實現大范圍的查詢.實驗結果表明，B+樹索引加速系統能夠在多指令并發的情況下維持高效的系統查詢性能.
Fig.16 Normalized throughput of parallel data query instructions圖16 歸一化的并行數據查詢指令吞吐量
子樹的引入對索引查詢無顯著影響.一方面，子樹的引入只要求增加1 層布隆過濾器計算，FPGA 實現該計算過程只需要幾個周期；
另一方面，即使增加到32 棵子樹，樹表容量的數量級仍然維持在105.因此，子樹的引入對索引查詢性能的影響很小，幾乎可以忽略不計，所以這一部分實驗不再評估子樹的引入對索引查詢性能的影響.
將該結果與GPU 優化的B+樹進行對比.參考文獻[5,7]中利用GPU 優化B+樹存儲結構的多語句并行查詢結果：GPU 實現的樹的容量為128 MB（只存儲關鍵字，不存儲衛星數據）時，相較于CPU 實現的標準B+樹，單值查詢性能提升20.41 倍，范圍查詢性能提升23.91 倍.然而，由于GPU 優化的樹結構中只保留存儲關鍵字的中間節點，這一方案也只能定位關鍵字在哪一個葉子節點，并沒有最終找到數據庫中的衛星數據，因而與本實驗實現的環境難以直接進行對比.一旦加入對衛星數據的尋址過程，會極大地損失GPU 的查詢性能.同時，范圍查詢的性能提升要比單值查詢更顯著的原因是，CPU 實現范圍查詢時存在一定性能損失，其單值查詢（比較基準）性能比范圍查詢具有2.36 倍的增益.如果以CPU 單值查詢的性能為基準，GPU 實現的B+樹加速系統的范圍查詢性能提升大約為11.22 倍，僅為單值查詢性能提升結果的50%左右.而本文所提出的B+樹索引加速系統HyperTree 能夠有效支持范圍查詢，性能損失大約80%.
6.3 索引維序性能
本節主要評價系統的索引維序性能.在B+樹索引加速系統中，除了設計多數據通道和并行計算引擎以加速索引查詢外，還針對索引維序時由于數據沖突所導致的索引維序性能瓶頸提出子樹的設計思想.以6.1 節中介紹的實驗環境和6.2 節中B+樹索引占滿樹表空間的環境為基礎，搭建B+樹索引加速系統實驗環境.通過增加子樹的棵數，評估子樹系統設計對索引維序性能帶來的提升.實驗以索引插入指令為例，子樹棵數從1 棵開始（即1 棵大樹，不實現子樹系統），以2 的冪次增長，直到32 棵為止.實驗結果以單棵樹的插入性能（QPS）為歸一化的單位1.如圖17所示，實驗結果表明隨著子樹棵數的增加，索引插入的并行性能取得顯著提升：當子樹棵數增加到32 時，系統性能提升約29.14 倍；
且由于資源占用而導致的計算阻塞延遲也顯著降低.相比文獻[11]基于FPGA實現的B+樹索引查詢系統對索引更新操作會引入大約70%性能下降這一結論，HyperTree 能夠有效解決這一問題.另一方面，比較基準文獻[11]所提出的 CPUFPGA 優化架構并沒有實現顯著的索引維序性能提升，而僅通過優化調度 CPU 和 FPGA 的計算執行，使一些不適合利用 FPGA 加速的維序計算由性能更高的CPU 取代，由此并沒有充分利用FPGA 計算性能.
Fig.17 Parallelism of sub-tree圖17 子樹并行性
將該結果與GPU 優化的B+樹進行對比.參考文獻[5,7]中利用GPU 實現的一種優化的B+樹存儲結構的關鍵字插入結果：實驗執行GPU 實現的B+樹容量為128 MB（只存儲關鍵字，不存儲衛星數據）時，其更新性能大約僅為CPU 實現的標準B+樹的72%.這也進一步說明B+樹的維序操作是索引性能損失的關鍵因素.而HyperTree 的子樹解耦合的數據存儲方法能夠解決由于索引維序對數據的獨占性而導致的計算并行困難的問題，從而有效提升索引維序的性能，均衡提升 B+樹查詢和維序性能.
6.4 計算架構的可擴展性
本節評估B+樹索引加速系統的可擴展性.計算架構的可擴展性可以衡量一種計算架構設計在增加計算節點時，硬件資源需求的增加情況以及實際性能的提升倍率.利用不同硬件平臺實現B+樹索引加速系統，可以衡量該計算架構設計是否能夠充分利用板卡資源，以較小的邊際硬件資源成本獲得系統性能提升.在本節實驗中，選用Xilinx Alveo U200，U50，U280 這3 個不同資源配置的FPGA 板卡來實現B+樹索引加速器系統HyperTree.這3 個板卡中限制系統性能的因素不同：U200 的帶寬資源受限，U50 的硬件邏輯單元受限，U280 則沒有資源受限（在本實驗的實現架構設計情況下）.
評價計算架構的可擴展性，可以通過增加系統中的計算引擎數目，評估系統硬件資源的使用情況及系統帶寬性能.在實驗中，設計系統的計算引擎數目從4 開始，以2 的冪次依次增長，直到256 個截止（受硬件邏輯資源限制，U50 僅支持128 個計算引擎）.本測試實驗所實現的子樹棵數與處理引擎數目相同，指令并發數目與處理引擎數目也相同.假設一種理想的實驗環境，即滿足處理引擎能夠無空閑地執行索引計算.所獲得的QPS 值為理想條件下的結果，即沒有數據沖突且處理引擎全部并發.實驗結果能夠綜合評估處理引擎、數據存儲和子樹系統的性能提升，結果如表4 所示.
Table 4 The Scalability of B+tree Accelerator表4 B+樹加速器的可擴展性
U200 板卡的內存帶寬標稱性能為76.8 GBps，為最大化利用內存帶寬資源，當計算引擎數目為32 時，內存帶寬資源可以達到41.8 GBps，基本實現了帶寬的最優利用效率，相對于CPU 歸一化的QPS 可以達到174.78.計算引擎再翻倍后，受物理內存帶寬的限制，系統整體性能不會進一步增長，反而造成計算引擎的冗余，即由于缺少計算所需數據而出現計算引擎空閑，造成硬件邏輯資源的浪費.U50 板卡由于使用HBM 資源能夠提供316 GBps 的理論內存帶寬.為充分利用這一高內存帶寬資源，實驗結果表明，配置128 個計算引擎能使系統資源的利用性能達到最優.此時，限制計算性能的因素是U50 片上的其他硬件計算資源的數目無法支持更多計算引擎.而U280 板卡是三者之中帶寬性能和硬件邏輯資源都最豐富的，其標稱內存帶寬可以達到460 GBps.在片上實現 256個計算引擎，系統帶寬性能可以提升至302.3 GBps，相對于CPU 歸一化的QPS 可以達到1 258.12.實驗結果表明，B+樹索引加速系統具有很好的可移植性，能夠充分利用板卡資源，擴展設計時只需引入很小的硬件資源開銷即可實現索引查詢和更新性能的線性提升.
為解決大數據環境下，數據庫查詢和更新的性能，本文提出一種支持B+樹索引加速的系統，從訪存和計算2 方面協同加速數據庫索引操作.為提升內存讀寫帶寬的利用效率，設計規則的樹表存儲結構和高效的節點存儲格式，規定讀寫控制以單節點為單位，使讀寫帶寬可以達到68.8 GBps.為提升系統執行性能，設計同構的多計算引擎，支持語句級并行.相比CPU，B+樹索引加速系統能夠實現14.53 倍的查詢性能提升.同時，為緩解索引插入和刪除操作的數據依賴，設計一種子樹存儲結構，支持多子樹插入及更新的并行，降低索引刪除的數據依賴，進一步提升索引的維序性能.相較于單棵大樹，子樹系統能夠提升索引插入性能29.14 倍.
作者貢獻聲明：吳婧雅負責整理相關文獻，提出問題解決方法，完成實驗驗證及撰寫論文；
盧文巖提出設計實驗方案并實現優化方案；
鄢貴海和李曉維提供實驗環境支持，指導論文撰寫及修改論文.
“涉藍”新引擎商周刊(2017年22期)2017-11-09無形的引擎河南電力(2015年5期)2015-06-08基于Cocos2d引擎的PuzzleGame開發皖西學院學報(2015年5期)2015-02-28智能垃圾箱環球時報(2009-11-25)2009-11-25