來源 | OSCHINA 社區

作者 | KaiwuDB

導讀

本篇博客主要講解發布于 Microprocessors and Microsystems 的文章《Semi-static Operator Graphs for Accelerated Query Execution on FPGAs》，介紹它所提出的算法與試驗結果，并結合實際情況給出一些思考。

一、背景介紹

在當今的數據化場景越來越豐富的大環境下，涌現出的非結構化數據存儲分析被應用于多數領域。 為了使機器能夠自動分析數據，語義網絡的概念被創建，元數據被用來描述和鏈接任何類型的數據和資源。

面對存儲和處理大規模的數據，除了不斷被優化的數據結構外，硬件也是需要被極大優化的。 海量數據的持續存儲在當今硬件環境下是沒有問題的，但是要實現在一個可以被接受的、被允許的時間范圍內進行處理和分析則變得愈發艱難。

因此，許多數據庫系統逐漸傾向于異構，由專門的計算內核來有效地執行特定的任務。

那么不得不提的，便是高性能計算常用到的 GPU （圖形處理器）。 GPU 最突出的優點是高性能，即高密度運算和高效并行性，非常適合處理計算密集型的任務； 同時，其易于連接到處理器端的屬性也是它可以被廣泛應用的原因。 然而，其缺點也是顯而易見的，就是高功耗。

在 GPU 之外，還存在為特定任務設計的專有硬件加速器，其對于指定的任務擁有較高的性能，但是其使用非常的不靈活，只能處理特定的任務，重新擴展的性能幾乎為零。

最后，則是最近被廣泛使用的 FPGA，它具有動態部分重配置的能力，可以縮小 CPU 的靈活性和專用硬件加速器的性能之間的差距，并且還擁有低功耗、高并發的優勢。

FPGA 卡的核心部分示意圖

如上圖所示，一塊 FPGA 芯片由可配置邏輯模塊（CLB）構成，每個 CLB 都包含特定的結構，如：查找表（LUT）、多路復用器、進位鏈、觸發器等。 除此之外，一塊 FPGA 卡上還有 BRAM（Block RAM），可以將其想象成 CPU 中 cache 的角色，以及 DSP (數字信號處理器）和一些通信接口（PCIe 等）。

這篇文章通過引入半靜態操作符圖，設計了一個 FPGA-CPU 異構的圖數據庫系統，加速了在大規模語義數據集上的查詢性能。

二、相關工作

上圖為一個 FPGA-CPU 混合處理運算的基本架構，客戶端應用程序向混合數據庫服務器發送查詢，該服務器使用基于 FPGA 的硬件加速器透明地確定結果。

文中主要引用的內容為：

Dennl 等人提出了關系型數據庫 MySQL 中 SQL 查詢的實時硬件加速的概念，但他們主要關注限制和聚合操作符，因此無法在 FPGA 上執行完整的查詢。

Becher 等人添加了更復雜的運算符（例如：歸并連接、小數據集上的排序）。 對于一個包含一個 Join 的簡單的查詢，它們的性能與標準的基于 x86 的系統相當，不過能源效率更高一些。

Woods 等人提出了 Ibex，一種用于關系數據庫 MySQL 的智能存儲引擎，可以支持使用 FPGA 卸載復雜的查詢操作符。

Wang 等人使用 OpenCL high level synthesis (HLS) 將數據庫操作符實現為 FPGA 的 Kernel。 但是查詢只用到了范圍檢查和一個 Join，相對簡單。

Heinrich 等人提出了一種混合索引結構，它在 FPGA 上存儲包括根節點在內的高層 B+ 樹，在主機上存儲包括葉子節點在內的低層。

而本文是第一個針對語義 Web 數據庫完全集成的基于 FPGA 的查詢引擎。

在介紹本文的混合數據庫系統之前，先介紹一下本文用到的圖數據庫基礎。 論文的工作是基于一個開源的圖數據庫系統 LUPOSDATE，它支持完整的 SPARQL 1.0 和 SPARQL 1.1 標準查詢語言。 論文通過引入基于 FPGA 的查詢引擎，與 LUPOSDATE 系統結合在一起。

LUPOSDATE 使用 RDF 三元組作為基本數據格式來描述 Web 資源，RDF 三元組表示為 ，其中 s 是 subject (主語)、p 是 predicate (謂詞)、o 是 object (賓語)。

相應的，LUPOSDATE 存儲的 B+ 樹索引結構有六種：SPO、SOP、PSO、POS、OSP、OPS，可以在檢索時方便的得到有序的三元組。 除此之外，LUPOSDATE 還維護一個 ISTree 和一個 SITree，用于 RDF 字符串和整數 id 之間的映射，這有利于 FPGA 模塊的設計，因為 FPGA 無法處理不定長度的字符串。

如下圖所示，對于給定的一個 SPARQL 查詢：

LUPOSDATE 語法分析器會產生相應的變量數組和操作符圖：

三、論文解決的問題

本文實現的混合數據庫系統是一個 LUPOSDATE 的擴展，由 CPU 主機和 FPGA 異構而成，如上圖所示。 主機提供更高層級的功能，如用戶界面、查詢優化、評估指標維護等，而 FPGA 被用作查詢執行時的自適應加速器。 主機和 FPGA 之間的通信是基于外設原件 PCIe 的。

FPGA 區域被劃分為靜態邏輯和許多個小 RP，每個 RP 可以配置任意類型的運算符，每個運算符作為一個可配置模塊是提前生成的。 靜態邏輯包含與實際查詢結構獨立的模塊，包括 PCIe 接口、一個管理模塊和查詢協調器（QC）。

QC 的主要任務是將傳入的三元組交給最上層的 RP 進行相應索引結構的導入，以及檢索和序列化變量數組用以生成最終結果。 此外，每個 RP 之間的互聯也位于靜態邏輯中。 每個實現的查詢操作符都使用了如下圖所示的一個公共模板：

每個操作符至多有兩個前向操作符和一個后向操作符，如果一個操作符只需要一個前向操作符，那么只有左邊的輸入被啟用。 每一個輸入或輸出都有如下參數：一個 data 向量對應輸入輸出的數組，一個 valid 信號表示數據的有效性，一個 finished 參數指定數據的結尾，一個反向 read 信號通知前向操作符數據已經被讀取，并且在新數據到來之前不會進行操作。 最后，數據的寬度也必須作為一個參數傳入，因為 FPGA 無法支持變長的數據類型。

下面介紹一下論文實現的操作符：

RDF3XIndexScan：RDF3XIndexScan 是 QC 和內部操作符之間的聯系。 這個操作符的主要目標是從 QC 中接收三元組，并將它們所需的組件映射到變量數組的某個位置。 它維護三個 one-hot 編碼的向量，每個向量的第 i 位代表第 i 個變量，如果某一個元素是常量，那么就將其所有位置為 1。

Join：Join 操作符是自然連接，本文使用的是 MergeJoin 的方式。 它維護一個 one-hot 編碼的向量，向量的第 i 位代表第 i 個變量，指代要 Join 的變量。

Filter：Filter 操作符是用于執行條件查詢。 復雜的 Filter 表達式將被分解為多個簡單的 VALUE COND VALUE 的 Filter 操作符。 其中，VALUE 可以是一個值、一個變量或一個式子，COND 是比較條件。 但由于 FPGA 無法處理字符串的問題，所以通過將字符串映射為整數 id 之后，系統只能支持相等和不相等的比較。

Projection：Projection 操作符是用于將需要的變量結果從變量數組中投影出來。

Union：Union 操作符就是簡單的將兩個前向操作符得到的結果做一個并集操作。

Limit 和 offset：Limit 操作符會轉發特定數量的結果給變量數組。 而 offset 操作符會跳過特定數量的結果。 它們一般作為操作符圖的最后幾步。

從混合系統結構圖中可以看到，每個 RP 之間并不是直接輸入輸出互聯，而是通過了一個上圖所示的半靜態路由元素（SRE）結構。 論文以一個兩路復用 SRE 為例，當 succ_sel 信號為 0 時，數據流會直接向下路由，為 1 時，會向另一側路由。 SRE 的存在使得可以用更少的 RP 組成一個支持查詢范圍更大的半靜態操作符圖。

四、混合系統工程流程

上圖給出了混合系統的工作流程圖，可以將其分為部署階段和系統運行時。 在部署階段，除了需要導入數據之外，整個靜態邏輯必須部署在 FPGA 上，每個操作符對應的 RM 也需要提前生成并存儲在 RM 庫中。

在系統運行時，主機通過分析輸入的 SPARQL 查詢，將其解析成相應的操作符圖，檢測其是否可以用配置在 FPGA 上，如果有不支持的操作符存在，那么會直接 CPU 端執行查詢，如果所有操作符都支持，那么 ICAP 會選擇對應操作符的 RM 配置在 FPGA 的半靜態操作符圖上。 主機通過 PCIe 向 FPGA 端提供輸入三元組，并接收 FPGA 端發回的結果進行后處理，FPGA 端負責具體的計算任務。

五、實驗結果

本文使用的是 Xilinx 的 Virtex-6 FPGA 卡和 PCIe 2.0 八通道通信接口，在 SP2Bench 三個不同大小的數據集（66M，131M 和 262M 個三元組）上進行了實驗。 下圖是他們采用的 SPARQL 查詢示例：

Query 1 是用到了 Filter 操作符的查詢，Query 2 是用到了 Union 操作符的查詢，Query 3-5 分別是用到了不同數量的 Join 操作符。 他們在 FPGA 端部署的半靜態操作符圖如下：

最后的實驗結果表明，加入了 FPGA 的混合系統比原來的 LUPOSDATE 系統的查詢執行速度更快。 并且隨著數據規模的增大，加速比會更大，說明混合系統更加適合大規模的數據集上的查詢。

六、總結

在這篇文章中，作者在 FPGA 上引入了半靜態運算符圖（SOG）的概念，為語義網數據庫中的查詢執行提供靈活的硬件加速器。 作者沒有為給定的查詢系統運行時生成一個 FPGA 配置，而是以一定程度的靈活性部署了通用查詢結構。

SOG 由多個具有公共接口的 RP 組成。 在為每個 RP 部署系統期間，會生成一組部分位文件的 RM，并將其存儲到存儲庫中。 在系統運行時，作者的混合系統針對給定的 SPARQL 查詢選擇 RM，并通過 ICAP 將其配置為 RP，RP 設置 FPGA 上運算符圖的最終結構。 作為這項工作的主要貢獻，耗時的 RM 生成在系統運行時之前執行，并且信號大大減少了查詢執行期間的重新配置。