FPGA：X-DB異構(gòu)計算實(shí)現(xiàn)百萬級TPS的技巧

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

背景介紹

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

問題背景

X-Engine的Compaction

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

當(dāng)memtable寫滿后，會轉(zhuǎn)化為 immutable memtable，然后轉(zhuǎn)化為SSTable flush到L0層。每一個SSTable包含多個data block和一個用來索引data block的index block。當(dāng)L0層文件個數(shù)超過了限制，就會觸發(fā)和L1層有重疊key range的SSTable的合并，這個過程就叫做compaction。類似的，當(dāng)一層的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ù)庫的架構(gòu)分為兩種，"bump-in-the-wire" 設(shè)計和混合設(shè)計架構(gòu)。前期由于FPGA板卡的內(nèi)存資源不夠，前一種架構(gòu)方式比較流行，F(xiàn)PGA被放置在存儲和host的數(shù)據(jù)路徑上，充當(dāng)一個filter，這樣設(shè)計的好處是數(shù)據(jù)的零拷貝，但是要求加速的操作是流式處理的一部分，設(shè)計方式不夠靈活；

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

系統(tǒng)設(shè)計

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

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

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

當(dāng)memtable的大小達(dá)到閾值時會被轉(zhuǎn)化為immutable memtable；

immutable memtable轉(zhuǎn)化為SSTable并且被flush到持久化存儲上。

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

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

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

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

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

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

compaction的結(jié)果flush到存儲。

詳細(xì)設(shè)計

FPGA-based Compaction

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

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

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

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

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

Encoder. Encoder模塊負(fù)責(zé)將Encoding KV Ring Buffer中的KV pair編碼到data block中，如果data block的大小超過閾值，會將當(dāng)前的data block flush到DDR中。

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

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

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

從實(shí)驗(yàn)中我們可以得到以下三個結(jié)論：

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

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

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

異步調(diào)度邏輯設(shè)計

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

容錯機(jī)制的設(shè)計

對于FPGA compaction而言，有以下三種原因可能會導(dǎo)致compaction 任務(wù)出錯

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

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

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

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

實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)環(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

結(jié)果分析：

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

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

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

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

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

YCSB

結(jié)果分析：

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

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

在write-only場景下，X-Engine-FPGA的吞吐提高了40%，隨著讀寫比的上升，F(xiàn)PGA Compaction的加速效果逐漸降低，這是因?yàn)樽x寫比越高，寫入壓力越小，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

結(jié)果分析：