當資料庫遇見FPGA：X-DB異構計算如何實現百萬級TPS？

05-01

前言

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的操作計算足夠密集，數據傳輸的代價是可以接受的。混合架構的設計允許更為靈活的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 板卡：Xilinix 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）

結果分析：

通過FPGA加速，隨著連接數從128增加到1024，X-Engine-FPGA可以得到10%~15%的性能提升。當連接數增加時，兩個系統的吞吐都逐漸降低，原因在於隨著連接數增多，熱點行的鎖競爭增加；
TPC-C的讀寫比是1.8：1，從實驗過程來看，在TPC-C benchmark下，80%以上的CPU都消耗在SQL解析和熱點行的鎖競爭上，實際的寫入壓力不會太大，通過實驗觀測，對於X-Engine-CPU系統，執行compaction操作的線程數不超過3個（總共64核心），因此，FPGA的加速效果不如前幾個實現明顯。

SysBench

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

結果分析：

X-Engine-FPGA提高了40%以上的吞吐性能，由於SQL解析消耗了大量的CPU資源，DBMS的吞吐要小於KV介面；
X-Engine-CPU在低水位達到了平衡，原因在於compaction的速度小於寫入速度，導致SST文件堆積，compaction持續被調度；
X-Engine-CPU的性能兩倍於InnoDB，證明了基於LSM-tree的存儲引擎在寫密集場景下的優勢；
和TPC-C benchmark相比，Sysbench更類似阿里的實際交易場景，對於交易系統而言，查詢的類型大部分是插入和簡單的點查詢，很少涉及範圍查詢，熱點行衝突的減少使得SQL層消耗的資源減少。在實驗過程中，我們觀測到對於X-Engine-CPU而言，超過15個線程都在執行compaction，因此FPGA加速帶來的性能提升更加明顯。

總結

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

寫在最後

此項目是X-DB引入異構計算設備，以加速資料庫核心功能的第一個落地項目。從使用經驗來看，FPGA能完全解決X-Engine的Compaction帶來的計算需求。同時我們也在進一步研究將更多合適的計算任務調度到FPGA上運行，如壓縮，生成BloomFilter，SQL JOIN運算元等。目前壓縮功能開發基本完畢，將會和Compaction做成一套IP，同步完成數據合併和壓縮操作。

X-DB FPGA-Compaction硬體加速，是資料庫事業部資料庫內核團隊，伺服器研發事業部定製計算團隊，浙江大學三方合作完成的一個研發項目。同時此項目的落地也有賴Xilinx公司技術團隊的大力支持，在此一併表示感謝。

X-DB將在今年上線阿里雲進行公測，大家可以體驗到FPGA加速給X-DB帶來的極致性能，也期待大家的寶貴建議。

原文鏈接

原文發布時間為：2018-04-5

本文作者：北樓

本文來自雲棲社區合作夥伴「阿里技術」

更多技術乾貨敬請關注云棲社區知乎機構號：阿里云云棲社區 - 知乎