FPGA：X-DB異構計算實現(xiàn)百萬級TPS的技巧 - 全文

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

背景介紹

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

混合存儲引擎的異步調度邏輯設計。由于一次FPGA compaction的鏈路請求在ms級別，使用傳統(tǒng)的同步調度方式會阻塞大量的compaction線程并且?guī)砗芏嗑€程切換的代價。通過異步調度，我們減少了線程切換的代價，提高了系統(tǒng)在工程方面的可用性。

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

問題背景

X-Engine的Compaction

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

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

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

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

FPGA加速數(shù)據(jù)庫

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

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

系統(tǒng)設計

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

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

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

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

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

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

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

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

輸入數(shù)據(jù)通過DMA傳輸?shù)紽PGA的DDR上；

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

CPU檢查Finished Queue中compaction任務的結果狀態(tài)，如果compaction失敗，該任務會被CPU再次執(zhí)行；

compaction的結果flush到存儲。

詳細設計

FPGA-based Compaction

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

Decoder. 在X-Engine中，KV是經(jīng)過前序壓縮編碼后存儲在data block中的，Decoder模塊的主要作用是為了解碼鍵值對。每一個CU內(nèi)部放置了4個Decoder，CU最多支持4路的compaction，多余4路的compaction任務需要CPU進行拆分，根據(jù)評估，大部分的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個信號來指示當前的狀態(tài)：FLAG_EMPTY, FLAG_HALF_FULL, FLAG_FULL，當FLAG_HALF_FULL為低位時，Decoder模塊會持續(xù)解碼KV pair，否則Decoder會暫停解碼直到流水線的下游消耗掉已經(jīng)解碼的KV pair。

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

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

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

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

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

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

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

在所有的KV長度下，F(xiàn)PGA compaction的吞吐都要優(yōu)于CPU單線程的處理能力，這印證了compaction offload的可行性；

隨著key長度的增長，F(xiàn)PGA compaction的吞吐降低，這是由于需要比較的字節(jié)長度增加，增加了比較的代價；

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

異步調度邏輯設計

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

容錯機制的設計

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

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

FPGA本身的錯誤（比特位翻轉），為了解決這個錯誤，我們?yōu)槊恳粋€CU配置了一個附加CU，兩個CU的計算結果進行按位比對，不一致則說明發(fā)生了比特位翻轉錯誤；

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

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

實驗結果

實驗環(huán)境

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

內(nèi)存：128GB

FPGA 板卡：Xilinx VU9P

memtable: 40 GB

block cache 40GB

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

X-Engine-CPU：compaction操作由CPU執(zhí)行

X-Engine-FPGA：compaction offload到FPGA執(zhí)行

DbBench

結果分析：

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

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

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

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

由于compaction的調度仍然由CPU執(zhí)行，這也就解釋了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%，隨著讀寫比的上升，F(xiàn)PGA Compaction的加速效果逐漸降低，這是因為讀寫比越高，寫入壓力越小，SSTable堆積的速度越慢，因此執(zhí)行compaction的線程數(shù)減少，因此對于寫密集的workload，X-Engine-FPGA的性能提升越明顯；

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

TPC-C （100 warehouses）

ConnectionsX-Engine-CPU?X-Engine-FPGA

128

214279

240105

256

203268

230401

512

197001

219618

1024

189697

208532

結果分析：

通過FPGA加速，隨著連接數(shù)從128增加到1024，X-Engine-FPGA可以得到10%~15%的性能提升。當連接數(shù)增加時，兩個系統(tǒng)的吞吐都逐漸降低，原因在于隨著連接數(shù)增多，熱點行的鎖競爭增加；

TPC-C的讀寫比是1.8：1，從實驗過程來看，在TPC-C benchmark下，80%以上的CPU都消耗在SQL解析和熱點行的鎖競爭上，實際的寫入壓力不會太大，通過實驗觀測，對于X-Engine-CPU系統(tǒng)，執(zhí)行compaction操作的線程數(shù)不超過3個 （總共64核心），因此，F(xiàn)PGA的加速效果不如前幾個實現(xiàn)明顯。

SysBench

在這個實驗中我們包含了對于InnoDB的測試（buffer size = 80G）

結果分析：

X-Engine-FPGA提高了40%以上的吞吐性能，由于SQL解析消耗了大量的CPU資源，DBMS的吞吐要小于KV接口；

X-Engine-CPU在低水位達到了平衡，原因在于compaction的速度小于寫入速度，導致SST文件堆積，compaction持續(xù)被調度；

X-Engine-CPU的性能兩倍于InnoDB，證明了基于LSM-tree的存儲引擎在寫密集場景下的優(yōu)勢；

和TPC-C benchmark相比，Sysbench更類似阿里的實際交易場景，對于交易系統(tǒng)而言，查詢的類型大部分是插入和簡單的點查詢，很少涉及范圍查詢，熱點行沖突的減少使得SQL層消耗的資源減少。在實驗過程中，我們觀測到對于X-Engine-CPU而言，超過15個線程都在執(zhí)行compaction，因此FPGA加速帶來的性能提升更加明顯。

總結

在本文中，我們提出的帶有FPGA加速的X-Engine存儲引擎，對于KV接口有著50%的性能提升，對于SQL接口獲得了40%的性能提升。隨著讀寫比的降低，F(xiàn)PGA加速的效果越明顯，這也說明了FPGA compaction加速適用于寫密集的workload，這和LSM-tree的設計初衷是一致的，另外，我們通過設計容錯機制來規(guī)避FPGA本身的缺陷，最終形成了一個適用于阿里實際業(yè)務的高可用的CPU-FPGA混合存儲引擎。