X-Engine 是集團數據庫事業部研發的新一代存儲引擎，是新一代分布式數據庫X-DB的根基。為了達到10倍MySQL性能，1/10存儲成本的目標，X-DB從一開始就使用了軟硬件結合的設計思路， 以充分發揮當前軟件和硬件領域最前沿的技術優勢。而引入FPGA加速是我們在定制計算領域做出的第一個嘗試。目前FPGA加速版本的X-DB已經在線上開始小規?；叶?，在今年6.18，雙11大促中，FPGA將助力X-DB， 將在不增加成本的前提下，滿足阿里業務對數據庫更高的性能要求。

背景介紹

作為世界上最大的在線交易網站，阿里巴巴的 OLTP （online transaction processing） 數據庫系統需要滿足高吞吐的業務需求。根據統計，每天 OLTP 數據庫系統的記錄寫入量達到了幾十億，在2017年的雙十一，系統的峰值吞吐達到了千萬級TPS (transactions per second)。阿里巴巴的業務數據庫系統主要有以下幾個特點：

事務高吞吐并且讀操作和寫操作的低延時；

寫操作占比相對較高，傳統的數據庫workload，讀寫比一般在 10:1 以上，而阿里巴巴的交易系統，在雙十一當天讀寫比達到了 3:1；

數據訪問熱點比較集中，一條新寫入的數據，在接下來7天內的訪問次數占整體訪問次數的99%，超過7天之后的被訪問概率極低。

為了滿足阿里的業務對性能和成本近乎苛刻的要求，我們重新設計開發了一個存儲引擎稱為X-Engine。在X-Engine中，我們引入了諸多數據庫領域的前沿技術，包括高效的內存索引結構，寫入異步流水線處理機制，內存數據庫中使用的樂觀并發控制等。

為了達到極致的寫性能水平，并且方便分離冷熱數據以實現分層存儲，X-Engine借鑒了LSM-Tree的設計思想。其在內存中會維護多個 memtable，所有新寫入的數據都會追加到 memtable ，而不是直接替換掉現有的記錄。由于需要存儲的數據量較大，將所有數據存儲在內存中是不可能的。

當內存中的數據達到一定量之后，會flush到持久化存儲中形成 SSTable。為了降低讀操作的延時，X-Engine通過調度 compaction 任務來定期 compact持久化存儲中的 SSTable，merge多個 SSTable 中的鍵值對，對于多版本的鍵值對只保留最新的一個版本（所有當前被事務引用的鍵值對版本也需要保留）。

根據數據訪問的特點，X-Engine會將持久化數據分層，較為活躍的數據停留在較高的數據層，而相對不活躍(訪問較少)的數據將會與底層數據進行合并，并存放在底層數據中，這些底層數據采用高度壓縮的方式存儲，并且會遷移到在容量較大，相對廉價的存儲介質 (比如SATA HDD) 中，達到使用較低成本存儲大量數據的目的。

如此分層存儲帶來一個新的問題：即整個系統必須頻繁的進行compaction，寫入量越大，Compaction的過程越頻繁。而compaction是一個compare & merge的過程，非常消耗CPU和存儲IO，在高吞吐的寫入情形下，大量的compaction操作占用大量系統資源，必然帶來整個系統性能斷崖式下跌，對應用系統產生巨大影響。

而完全重新設計開發的X-Engine有著非常優越的多核擴展性，能達到非常高的性能，僅僅前臺事務處理就幾乎能完全消耗所有的CPU資源，其對資源的使用效率對比InnoDB,如下圖所示：

在如此性能水平下，系統沒有多余的計算資源進行compaction操作，否則將承受性能下跌的代價。

經測試，在 DbBench benchmark 的 write-only 場景下，系統會發生周期性的性能抖動，在 compaction 發生時，系統性能下跌超過40%，當 compaction 結束時，系統性能又恢復到正常水位。如下圖所示：

但是如果 compaction 進行的不及時，多版本數據的累積又會嚴重影響讀操作。

為了解決 compaction 的抖動問題，學術界提出了諸如 VT-tree、bLSM、PE、PCP、dCompaction 等結構。盡管這些算法通過不同方法優化了 compaction 性能，但是 compaction 本身消耗的 CPU 資源是無法避免的。據相關研究統計，在使用SSD存儲設備時，系統中compaction的計算操作占據了60%的計算資源。因此，無論在軟件層面針對 compaction 做了何種優化，對于所有基于 LSM-tree 的存儲引擎而言，compaction造成的性能抖動都會是阿喀琉斯之踵。

幸運的是，專用硬件的出現為解決compaction導致的性能抖動提供了一個新的思路。實際上，使用專用硬件解決傳統數據庫的性能瓶頸已經成為了一個趨勢，目前數據庫中的select、where操作已經offload到FPGA上，而更為復雜的 group by 等操作也進行了相關的研究。但是目前的FPGA加速解決方案存在以下兩點不足：

目前的加速方案基本上都是為SQL層設計，FPGA也通常放置在存儲和host之間作為一個filter。雖然在FPGA加速OLAP系統方面已經有了許多嘗試，但是對于OLTP系統而言，FPGA加速的設計仍然是一個挑戰；

隨著FPGA的芯片尺寸越來越小，FPGA內部的錯誤諸如單粒子翻轉（SEU）正在成為FPGA可靠性的越來越大的威脅，對于單一芯片而言，發生內部錯誤的概率大概是3-5年，對于大規模的可用性系統，容錯機制的設計顯得尤為重要。

為了緩解compaction對X-Engine系統性能的影響，我們引入了異構硬件設備FPGA來代替CPU完成compaction操作，使系統整體性能維持在高水位并避免抖動，是存儲引擎得以服務業務苛刻要求的關鍵。本文的貢獻如下：

FPGA compaction 的高效設計和實現。通過流水化compaction操作，FPGA compaction取得了十倍于CPU單線程的處理性能；

混合存儲引擎的異步調度邏輯設計。由于一次FPGA compaction的鏈路請求在ms級別，使用傳統的同步調度方式會阻塞大量的compaction線程并且帶來很多線程切換的代價。通過異步調度，我們減少了線程切換的代價，提高了系統在工程方面的可用性。

容錯機制的設計。由于輸入數據的限制和FPGA內部錯誤，都會造成某個compaction 任務的回滾，為了保證數據的完整性，所有被FPGA回滾的任務都會由同等的CPU compaction線程再次執行。本文設計的容錯機制達到了阿里實際的業務需求并且同時規避了FPGA內部的不穩定性。

問題背景

X-Engine的Compaction

X-Engine的存儲結構包含了一個或多個內存緩沖區 （memtable）以及多層持久化存儲 L0, L1, ... ，每一層由多個SSTable組成。

當memtable寫滿后，會轉化為 immutable memtable，然后轉化為SSTable flush到L0層。每一個SSTable包含多個data block和一個用來索引data block的index block。當L0層文件個數超過了限制，就會觸發和L1層有重疊key range的SSTable的合并，這個過程就叫做compaction。類似的，當一層的SSTable個數超過了閾值都會觸發和下層數據的合并，通過這種方式，冷數據不斷向下流動，而熱數據則駐留在較高層上。

一個compaction過程merge一個指定范圍的鍵值對，這個范圍可能包含多個data block。一般來說，一個compaction過程會處理兩個相鄰層的data block合并，但是對于L0層和L1層的compaction需要特殊考慮，由于L0層的SSTable是直接從內存中flush下來，因此層間的SSTable的Key可能會有重疊，因此L0層和L1層的compaction可能存在多路data block的合并。

對于讀操作而言，X-Engine需要從所有的memtable中查找，如果沒有找到，則需要在持久化存儲中從高層向底層查找。因此，及時的compaction操作不僅會縮短讀路徑，也會節省存儲空間，但是會搶奪系統的計算資源，造成性能抖動，這是X-Engien亟待解決的困境。

FPGA加速數據庫

從現在的FPGA加速數據庫現狀分析，我們可以將FPGA加速數據庫的架構分為兩種，"bump-in-the-wire" 設計和混合設計架構。前期由于FPGA板卡的內存資源不夠，前一種架構方式比較流行，FPGA被放置在存儲和host的數據路徑上，充當一個filter，這樣設計的好處是數據的零拷貝，但是要求加速的操作是流式處理的一部分，設計方式不夠靈活；

后一種設計方案則將FPGA當做一個協處理器，FPGA通過PCIe和host連接，數據通過DMA的方式進行傳輸，只要offload的操作計算足夠密集，數據傳輸的代價是可以接受的?；旌霞軜嫷脑O計允許更為靈活的offload方式，對于compaction這一復雜操作而言，FPGA和host之間數據的傳輸是必須的，所以在X-Engine中，我們的硬件加速采用了混合設計的架構。

系統設計

在傳統的基于LSM-tree的存儲引擎中，CPU不僅要處理正常的用戶請求，還要負責compaction任務的調度和執行，即對于compaction任務而言，CPU既是生產者，也是消費者，對于CPU-FPGA混合存儲引擎而言，CPU只負責compaction任務的生產和調度，而compaction任務的實際執行，則被offload到專用硬件（FPGA）上。

對于X-Engine，正常用戶請求的處理和其他基于LSM-tree的存儲引擎類似：

用戶提交一個操作指定KV pair（Get/Insert/Update/Delete）的請求，如果是寫操作，一個新的記錄會被append到memtable上；

當memtable的大小達到閾值時會被轉化為immutable memtable；

immutable memtable轉化為SSTable并且被flush到持久化存儲上。

當L0層的SSTable數量達到閾值時，compaction任務會被觸發，compaction的offload分為以下幾個步驟：

從持久化存儲中load需要compaction的SSTable，CPU通過meta信息按照data block的粒度拆分成多個compaction任務，并且為每個compaction任務的計算結果預分配內存空間，每一個構建好的compaction任務都會被壓入到Task Queue隊列中，等待FPGA執行；

CPU讀取FPGA上Compaction Unit的狀態，將Task Queue中的compaction任務分配到可用的Compaction Unit上；

輸入數據通過DMA傳輸到FPGA的DDR上；

Compaction Unit執行Compaction任務，計算完成后，結果通過DMA回傳給host，并且附帶return code指示此次compaction任務的狀態（失敗或者成功），執行完的compaction結果會被壓入到Finished Queue隊列中；

CPU檢查Finished Queue中compaction任務的結果狀態，如果compaction失敗，該任務會被CPU再次執行；

compaction的結果flush到存儲。

詳細設計

FPGA-based Compaction

Compaction Unit (CU) 是FPGA執行compaction任務的基本單元。一個FPGA板卡內可以放置多個CU，單個CU由以下幾個模塊組成：

Decoder. 在X-Engine中，KV是經過前序壓縮編碼后存儲在data block中的，Decoder模塊的主要作用是為了解碼鍵值對。每一個CU內部放置了4個Decoder，CU最多支持4路的compaction，多余4路的compaction任務需要CPU進行拆分，根據評估，大部分的compaction都在4路以下。放置4個Decoder同樣也是性能和硬件資源權衡的結果，和2個Decoder相比，我們增加了50%的硬件資源消耗，獲得了3倍的性能提升。

KV Ring Buffer. Decoder 模塊解碼后的KV pair都會暫存在KV Ring Buffer中。每一個KV Ring Buffer維護一個讀指針（由Controller模塊維護）和一個寫指針（由Decoder模塊維護），KV Ring Buffer 維護3個信號來指示當前的狀態：FLAG_EMPTY, FLAG_HALF_FULL, FLAG_FULL，當FLAG_HALF_FULL為低位時，Decoder模塊會持續解碼KV pair，否則Decoder會暫停解碼直到流水線的下游消耗掉已經解碼的KV pair。

KV Transfer. 該模塊負責將key傳輸到Key Buffer中，因為KV的merge只涉及key值的比較，因此value不需要傳輸，我們通過讀指針來追蹤當前比較的KV pair。 Key Buffer. 該模塊會存儲當前需要比較的每一路的key，當所有需要比較的key都被傳輸到Key Buffer中，Controller會通知Compaction PE進行比較。

Compaction PE. Compaction Processing Engine （compaction PE）負責比較Key Buffer中的key值。比較結果會發送給Controller，Controller會通知KV Transfer將對應的KV pair傳輸到Encoding KV Ring Buffer中，等待Encoder模塊進行編碼。

Encoder. Encoder模塊負責將Encoding KV Ring Buffer中的KV pair編碼到data block中，如果data block的大小超過閾值，會將當前的data block flush到DDR中。

Controller. 在CU中Controller充當了一個協調器的作用，雖然Controller不是compaction pipeline的一部分，單在compaction 流水線設計的每一個步驟都發揮著關鍵的作用。

一個compaction過程包含三個步驟：decode，merge，encode。設計一個合適的compaction 流水線的最大挑戰在于每一個步驟的執行時間差距很大。比如說由于并行化的原因，decode模塊的吞吐遠高于encoder模塊，因此，我們需要暫停某些執行較快的模塊，等待流水線的下游模塊。為了匹配流水線中各個模塊的吞吐差異，我們設計了controller模塊去協調流水線中的不同步驟，這樣設計帶來的一個額外好處是解耦了流水線設計的各個模塊，在工程實現中實現更敏捷的開發和維護。

在將FPGA compaction集成到X-Engine中，我們希望可以得到獨立的CU的吞吐性能，實驗的baseline是CPU單核的compaction線程 （Intel(R) Xeon(R) E5-2682 v4 CPU with 2.5 GHz）

從實驗中我們可以得到以下三個結論：

在所有的KV長度下，FPGA compaction的吞吐都要優于CPU單線程的處理能力，這印證了compaction offload的可行性；

隨著key長度的增長，FPGA compaction的吞吐降低，這是由于需要比較的字節長度增加，增加了比較的代價；

加速比（FPGA throughput / CPU throughput）隨著value長度的增加而增加，這是由于在KV長度較短時，各個模塊之間需要頻繁進行通信和狀態檢查，而這種開銷和普通的流水線操作相比是非常昂貴的。

異步調度邏輯設計

由于FPGA的一次鏈路請求在ms級別，因此使用傳統的同步調度方式會造成較頻繁的線程切換代價，針對FPGA的特點，我們重新設計了異步調度compaction的方式：CPU負責構建compaction task并將其壓入Task Queue隊列，通過維護一個線程池來分配compaction task到指定的CU上，當compaction結束后，compaction任務會被壓入到Finished Queue隊列，CPU會檢查任務執行的狀態，對于執行失敗的任務會調度CPU的compaction線程再次執行。通過異步調度，CPU的線程切換代價大大減少。

容錯機制的設計

對于FPGA compaction而言，有以下三種原因可能會導致compaction 任務出錯

數據在傳輸過程中被損壞，通過在傳輸前和傳輸后分別計算數據的CRC值，然后進行比對，如果兩個CRC值不一致，則表明數據被損壞；

FPGA本身的錯誤（比特位翻轉），為了解決這個錯誤，我們為每一個CU配置了一個附加CU，兩個CU的計算結果進行按位比對，不一致則說明發生了比特位翻轉錯誤；

compaction輸入數據不合法，為了方便FPGA compaction的設計，我們對KV的長度進行了限制，超過限制的compaction任務都會被判定為非法任務。

對于所有出錯的任務，CPU都會進行再次計算，確保數據的正確性。在上述的容錯機制的下，我們解決了少量的超過限制的compaction任務并且規避了FPGA內部錯誤的風險。

實驗結果

實驗環境

CPU：64-core Intel (E5-2682 v4, 2.50 GHz) processor

內存：128GB

FPGA 板卡：Xilinx VU9P

memtable: 40 GB

block cache 40GB

我們比較兩種存儲引擎的性能：

X-Engine-CPU：compaction操作由CPU執行

X-Engine-FPGA：compaction offload到FPGA執行

DbBench

結果分析：

在write-only場景下，X-Engine-FPGA的吞吐提升了40%，從性能曲線我們可以看出，當compaction開始時，X-Engine-CPU系統的性能下跌超過了三分之一；

由于FPGA compaction吞吐更高，更及時，因此讀路徑減少的更快，因此在讀寫混合的場景下X-Engine-FPGA的吞吐提高了50%；

讀寫混合場景的吞吐小于純寫場景，由于讀操作的存在，存儲在持久層的數據也會被訪問，這就帶來了I/O開銷，從而影響了整體的吞吐性能；

兩種性能曲線代表了兩種不同的compaction狀態，在左圖，系統性能發生周期性的抖動，這說明compaction操作在和正常事務處理的線程競爭CPU資源；對于右圖，X-Engine-CPU的性能一直穩定在低水位，表明compaction的速度小于寫入速度，導致SSTable堆積，compaction任務持續在后臺調度；

由于compaction的調度仍然由CPU執行，這也就解釋了X-Engine-FPGA仍然存在抖動，并不是絕對的平滑。

YCSB

結果分析：

在YCSB benchmark上，由于compaction的影響，X-Engine-CPU的性能下降了80%左右，而對于X-Engine-FPGA而言，由于compaction調度邏輯的影響，X-Engine-FPGA的性能只有20%的浮動；

check unique的存在引入了讀操作，隨著壓測時間的增長，讀路徑變長，因此兩個存儲引擎的性能隨著時間下降；

在write-only場景下，X-Engine-FPGA的吞吐提高了40%，隨著讀寫比的上升，FPGA Compaction的加速效果逐漸降低，這是因為讀寫比越高，寫入壓力越小，SSTable堆積的速度越慢，因此執行compaction的線程數減少，因此對于寫密集的workload，X-Engine-FPGA的性能提升越明顯；

隨著讀寫比的上升，吞吐上升，由于寫吞吐小于KV接口，因此cache miss的比例較低，避免了頻繁的I/O操作，而隨著寫比例的上升，執行compaction線程數增加，因此降低了系統的吞吐能力。

TPC-C （100 warehouses）

ConnectionsX-Engine-CPU?X-Engine-FPGA

128

214279

240105

256

203268

230401

512

197001

219618

1024

189697

208532

結果分析：