1、What is X-Engine
X-Engine是阿裡雲自研OLTP資料庫存儲引擎，已經廣泛應用于包括釘釘、核心交易、阿裡媽媽在内的阿裡巴巴核心業務，在提供高性能的同時大幅降低了存儲開銷。
經過阿裡雙十一等高壓場景的考驗與打磨，RDS MySQL(X-Engine)版即将在阿裡雲上向外部客戶提供服務，将技術紅利帶給雲上使用者。
X-Engine:An Optimized Storage Engine for Large-scale E-Commerce Transaction Processing 介紹了X-Engine的系統架構以及核心設計，發表在SIGMOD'19 Industrial Track。
近日，X-Engine團隊的另一項工作FPGA-Accelerated Compactions for LSM-based Key-Value Store被FAST'20 Research Track接收（USENIX Conference on File and Storage Techniques (FAST)，CCF A類會議，存儲領域頂會，2020年接受率16%），本文會對這項工作進行簡單介紹。
X-Engine采用了LSM-tree架構，同時廣泛針對現代多核，大記憶體，高速存儲的伺服器進行了優化，例如其内部大量采用無鎖設計，具有良好的擴充性。
在開始論文的解讀前，我們先分析下X-Engine所處時代的伺服器硬體發展趨勢，以及LSM-tree架構的存儲引擎對伺服器計算資源及存儲資源的需求特點，兩項結合，讀者能更好的了解為何在資料庫中引入CPU以外的專用計算裝置會是未來的一個趨勢。
2、硬體發展趨勢
近年來，包括處理器和存儲在内的伺服器端硬體的發展非常快。CPU 方面，Intel 的 Xeon CPU 家族在 14nm 制程上完成了第一輪 "Process-Architecture-Optimization" 模型下的疊代，在 10nm 制程上也推出了最新的 Tiger Lake 微架構。
在 CPU 核數的增長已經變得司空見慣的今天，Tiger Lake 不僅擁有比 Skylake 高約 30% 的時鐘頻率，還擁有更大的 L1/L2 cache，更大的 cache line，使用 HBM 技術的 L4 cache 和更快的 I/O。這些突破性的進展都标志着 CPU 處理能力的躍升。放眼未來，Intel 還預計于 2021 年開啟一輪新的疊代，釋出其新的 7nm 制程處理器。
CPU 之外，新型 FPGA、GPU 和各類 AI 處理器層出不窮。2019年，阿裡巴巴釋出了峰值推理性能達到 78563 IPS的含光800處理器。傳統的異構加速器在不斷疊代更新之外，也發展出了日漸成熟的混合架構，如 CPU-FPGA（e.g., Intel Arria），和 FPGA-accelerated NVMe SSD (e.g., BittWare 250)。存儲方面，随着比傳統 NAND 閃存快近千倍的 3D XPoint 技術的發展和應用，無論是 NVM 還是 SSD 的性能都有了長足的進步。
最新的 Intel Optane SSD 的随機讀、寫性能都達到了 550000 IOPS，順序讀寫帶寬更是分别達到了 2500 MB/s 和 2200 MB/s，讀寫延遲 10 µs。下圖則展示過去10年間，每年進入市場的 Intel SSD 的峰值 I/O 性能。我們可以看到，無論是順序I/O，還是随機 I/O 的能力都有了非常快的進步。
在我們的工業實踐中，三年前我們所使用的典型伺服器，還隻能提供2.4GB/S的順序讀帶寬，而到了今年，在我們最新的伺服器上，測試值已經達到了 12GB/S的帶寬。
過去10年間，每年上市的 Intel SSD 的峰值 I/O 性能
新硬體趨勢和底層硬體性能的變化往往會造成上層軟體的性能瓶頸的遷移，尤其是像資料庫存儲引擎這樣的直接接觸存儲硬體的基礎軟體。随着 I/O 性能的不斷提高，很多傳統的瓶頸在 I/O的 資料庫算法逐漸轉變為被計算資源所限制；反之亦然。在這項工作中，我們發現 LSM-tree 存儲引擎的中的 Compaction 操作正是一個正在由 I/O 瓶頸轉變為計算瓶頸的例子。具體細節，請看下文詳細展開。
3、LSM-tree 的 Compaction
在LSM-tree架構中，寫入操作會首先插入到記憶體中，當大小到達門檻值後，會寫到磁盤上，并和磁盤上的資料合并（類似于merge sort），而磁盤上的資料按照層級進行組織，每一層的資料達到門檻值後都會和下一層的資料進行合并（圖（a））。
這樣做的好處主要有兩點：1. 寫入操作（insert/update/delete）統一轉化為追加操作，不會更新原有資料，寫性能要優于innodb等存儲引擎；2. 分層存儲，資料有序排列，每個block都是緊湊的，不存在空洞，便于壓縮，存儲成本優勢明顯。
X-Engine 的資料層次結構與LevelDB, RocksDB這些使用LSM-tree的存儲引擎類似，寫入首先寫入到memtable中，當memtable寫滿後轉化為immutable memtable，之後immutable memtable會刷盤持久化。
X-Engine磁盤上的資料也是按層組織，每一層一般切分成多個固定大小的有序段（X-Engine中的Extent，類似于RocksDB中的SSTable），每一個Extent再切分成多個data block，data block中的資料一般進行字首編碼存儲，每一個Extent會有一個Index block來索引data block（圖（b））。
背景的flush/compaction線程負責将記憶體資料和磁盤上的資料進行合并，每一層的資料量到達門檻值後也會觸發和下層資料的合并，這個操作稱之為 compaction 。
及時的compaction非常重要，LSM-tree在持續高強度寫入壓力下會産生形變（層數累計過多），會給讀操作帶來非常大的麻煩（由于多版本資料的影響，讀操作需要順序掃描各層并合并産生結果）。compaction及時合并多版本資料，删除舊版本資料，維持一個健康的讀取路徑長度，對存儲空間釋放及系統性能意義重大。
下圖展示了不同KV長度的compaction執行時間分解圖，在短KV情況下（value長度小于等于64B），compaction的計算時間占比在50%以上。近年來儲存設備讀寫性能提升非常快，而CPU主頻的提升則非常緩慢，compaction操作中計算時間占比越來越長。另外，X-Engine的資料塊都是壓縮存儲的，考慮到壓縮帶來的額外CPU消耗，計算資源的瓶頸更加明顯。
下圖展示了X-Engine長時間運作的性能以及資源利用情況（key=8B, value=32B），預熱時間1個小時，觀測視窗2個小時，讀寫比為3:1，在32個compaction線程的設定下，系統性能達到了最高水位。
這個随着背景compaction線程數增加性能類似抛物線的變化說明了兩個問題：
1.及時的compaction能讓系統性能得以保持在高水位，否則LSM-tree層數的堆積增長會嚴重損害系統性能（32個線程配置下，X-Engine性能是8個線程配置的2倍左右）。
2.在CPU資源受限的情況下，compaction操作需要和前台的事務處理線程競争計算資源，資源競争對系統性能的損害在超過32個compaction 線程的設定下開始顯現。
- 為了使compaction任務及時的被處理，我們可以設定更多的compaction線程， 但過多的compaction線程争搶計算資源又會對執行前台事務操作的線程帶來負面影響，降低吞吐。前台事務産生新資料的速度和背景compaction線程消納堆積資料的速度達到平衡時，系統達到均衡性能，但此性能一般遠低于資料庫可以達到的峰值性能。
Compaction需要做，但不一定非得CPU來做。一個compaction任務包含了多路資料塊的讀取、解碼、歸并排序、編碼、寫回等階段，對于同一個compaction任務來說，前後階段存在資料依賴，但是對于多個任務來說，并不存在資料依賴，完全可以通過流水線執行來提高吞吐能力。
通過将compaction offload到适合處理流水線任務的FPGA來執行，CPU可以全部服務于複雜的事務處理，進而避免了背景任務對于計算資源的侵占。如此資料庫系統可以一直以峰值性能處理事務。
4、整體架構
我們所使用的FPGA加速卡是通過PCIe接口連接配接到伺服器上，它并不能像伺服器上的CPU一樣友善的通路記憶體和磁盤。另外FPGA計算能力強大，但是單次通路的延時卻更像一個IO裝置。這樣的特點決定了我們不能直接将之前CPU版本的compaction算法直接應用到FPGA上。
為了适配FPGA加速卡，我們首先将CPU版本的流式compaction實作改造成分批次模式。CPU負責将compaction拆分成特定大小的task，每個task可以并行執行，這樣可以充分發揮FPGA加速卡上多CU的并行能力。
在X-Engine中，我們設計了一個任務隊列（Task Queue）來緩存需要執行的compaction任務，通過Driver來下發給FPGA上的計算單元（compaction unit，CU）執行，執行的結果會緩存在結果隊列（Result Queue）中，等待CPU寫回持久化存儲。
- 架構關鍵設計一：Compaction 排程器
度器負責建構compaction任務，然後分發給CU執行，并将compaction的結果寫回到磁盤上，我們設計了三種線程來完成整個鍊路：
Builder thread：将需要被合并的Extent按照range切分，形成compaction task。每一個compaction task結構體維護了必要的元資訊，包括Task Queue指針，輸入資料的起始位址（傳輸到FPGA需要做CRC校驗保證資料正确性），compaction結果的寫回位址，以及後續邏輯的回調函數指針。
此外，每一個task還包含return code，标志此次compaction任務是否執行成功，對于失敗的任務，我們會調用CPU再次執行。通過線上運作的資料顯示，大概隻有0.03%的task會被CPU再次執行（主要是KV長度過長的case）。
Dispatcher thread：由于FPGA上存在多個CU，需要設計相應的分發算法，目前我們采用了簡單的round-robin分發政策，由于每一個下發的compaction task大小接近，實驗表明不同CU的使用率比較均衡。
Driver thread：負責将資料傳輸至FPGA并通知CU開始工作，當CU任務執行完成後會中斷Driver thread将結果傳回記憶體，并将task入隊Result Queue。
- 架構關鍵設計二：Compaction Unit
Compaction Unit （CU）是CPU compaction對應的FPGA實作邏輯。一個FPGA上可以部署多個CU，由Driver進行分發排程。一個CU由Decoder、KV Ring Buffer、KV Transfer and Key Buffer、Merger、Encoder、Controller組成。
Decoder子產品的設計和LSM-tree的compaction policy相關，目前的CU采用4路Decoder設計。X-Engine采用tiering政策，是以可能會存在多路合并的情況，從實際的運作情況來看，2~4路的歸并是比較常見的，而4路歸并的設計比2路歸并的設計更加高效（性能提升3倍，硬體資源消耗增加40%左右）。Decoder子產品将前序編碼的KV對解碼後緩存到KV Ring Buffer中。
KV Ring Buffer 由32個8KB的slot構成，每一個slot中6KB存儲KV資料，另外2KB存儲KV的元資訊（KV長度等）。每一個KV Ring Buffer有三種狀态：FLAG_EMPTY, FLAG_HALF_FULL, FLAG_FULL，來辨別Ring Buffer是處在空、半滿、滿，根據緩存的KV數量我們會決定是否要繼續推進流水線，還是要暫時Decoder以等待下遊消耗。
KV Transfer和Key Buffer主要負責KV的傳輸，由于歸并排序并不需要比較value，是以隻需要緩存Key值即可。
Merger操作負責合并 Key Buffer中的key，下圖中，第二路的key值最小，Controller會通知KV Transfer将對應 KV 從 KV Ring Buffer中傳輸到 KV Output Buffer（和KV Ring Buffer結構類似），并将KV Ring Buffer的讀指針前移得到下一個KV，Controller會通知Merger進行下一輪比較。
Encoder子產品主要負責将Merger輸出的KV進行前序編碼，組織成data block的格式寫入到FPGA的記憶體中。
為了控制各個階段的處理速度，我們引入了Controller子產品，Controller子產品負責維護KV Ring Buffer的讀寫指針，并根據KV Ring Buffer的狀态感覺流水線上下遊處理速度的差距，通過暫停/重新開機相應子產品來維持流水線的高效運轉。
- 架構關鍵設計三：容錯機制
保證資料一緻性是資料庫引擎基本功能，引入異構計算裝置，增加了額外變量，引入新風險。X-Engine在整體架構設計上考慮到了FPGA 計算裝置失效，傳輸鍊路出現bit跳變等風險。容錯方面X-Engine做了如下工作。
1.X-Engine可以探測到伺服器是否部署FPGA加速卡，以及目前FPGA卡是否可用（有刷入compaciton/壓縮解壓 固件，裝置是否存活)等。X-Engine的Compaction/壓縮等邏輯均有CPU版本實作做備份。如果運作過程中FPGA突然失聯，可以平滑的切換回CPU模式，隻是峰值性能稍低，穩定性不會有任何影響。切換回CPU模式之後，X-Engine會定期探測FPGA加速卡的可用性，如有可能就立即切換到FPGA加速模式。
2.Compaction CU的每一個步驟中，均儲存了CRC校驗值，同時compaction任務的輸入輸出在FPGA卡的記憶體和主機記憶體之間傳輸後，均會做校驗。確定傳輸鍊路中不會出現跳變。
3.X-Engine可以相容部分compacton任務的執行失敗。由于逾時，記憶體讀寫錯誤導緻的單個任務失敗，X-Engine會捕獲到執行結果，并将失敗的任務交由CPU重新執行并獲得結果。而且這個設計還給我們帶來另一個好處，由于FPGA卡的compaction固件邏輯實作涉及到晶片上的寄存器配置設定及邏輯布線，如果需要處理key或者value特别長的記錄，會導緻FPGA邏輯的計算效率降低。
是以我們的FPGA實作中，隻支援特定長度KV記錄。遇見超長KV記錄時會直接報錯傳回，并交由CPU處理。這樣可以避免讓FPGA處理一些資料庫中出現的長TEXT/BLOB等字段。這樣就實作了功能（長KV)和性能的兼顧. X-Engine線上上實際運作中，統計到的失敗的task占比在萬分之三左右, 證明我們的思路是可行的。
5、實驗評估
本文的所有實驗均在裝有兩個Intel XeonPlatinum 8163 2.5 GHz 24-core (two-way hyperthreading)的處理器上進行，記憶體為512GB的DDR4-2133，磁盤環境為由10塊SSD構成的RAID 0陣列，Linux版本為4.9.79。FPGA闆卡型号為Xilinx VU9P (200M Hz)，FPGA記憶體大小為16GB，通過 x16 PCIe Gen 3和主機相連。FPGA上共配置了8個CU。
1.CU加速評估
我們設計單測來比較單CU和CPU單核心的compaction吞吐。load四路共計400萬條記錄并觸發compaction，在不同的KV場景下，FPGA compaction加速比在2到5倍之間。
為了能夠定量評估流水線各個子產品的吞吐速度，我們還為CU的處理速度進行了模組化，實際上，無論是對于FPGA Compaction還是CPU compaction，能夠精準控制compaction執行時間都是非常重要的。通過理論模型，我們可以通過預估提供指定compaction吞吐所需要的CU數量。模型計算的結果和單測結果誤差在20%以内。
2.系統性能評估
性能評估工具：DbBench，workload分布采用Zipf-1.0，讀寫比預設設定為3：1，load 32個subtable（對應一棵LSM-Tree），每個subtable包含200000000條資料，記憶體設定為70GB，Key和Value的大小分别設定為8B和32B，該配置是線上的一個常見配置，所有的實驗預熱時間3600秒，評估時間為7200秒。
使用FPGA加速後，X-Engine的性能和32個線程的CPU版本性能提升在25%左右，CPU的使用率降低了10%左右。雖然32個線程以上的CPU compaction吞吐大于FPGA版本的compaction，但是增加了計算資源的競争，雖然資料消解更快（資料量），但是性能也不理想。
6、總結
存儲引擎的發展就是在應用負載不斷變化、硬體環境不斷革新的情況下尋找成本和性能最優平衡的過程。
LSM-tree生态的繁榮正是上述兩點共同作用的結果，一方面，寫操作、點查詢逐漸成為了使用者負載的主要部分（WPI，write and point read-intensive），資料量的爆炸增長，寫操作比例的上升令LSM-tree存儲引擎得以廣泛應用，另一方面，存儲媒體技術的飛速發展，SSD，NVMe等媒體将持久化層的吞吐推上了一個新的高度，存儲引擎的性能瓶頸開始從IO過渡到CPU，也正在催生許多新的挑戰。
運用新硬體來解決存儲系統的瓶頸問題，我們隻是向前邁了一小步，還有很多有意思的問題需要更好的解答：
Compaction越快越好嗎？如何在及時compaction和避免compact熱點資料造成cache miss之間尋找平衡，timing compaction看似顯而易見，實則需要細細考量。
“專用”是把雙刃劍。如何在compaction壓力較小的時候提高FPGA資源的使用率，可以考慮同時支援多個執行個體以及不同IP共享硬體資源，哪種方案更切實可行，還需要更長時間的工業實踐積累來告訴我們答案。
前路漫漫，道阻且長。
緻謝
本工作由阿裡巴巴資料庫産品事業部X-Engine團隊、基礎設施事業部定制計算(AIS)團隊、達摩院資料庫與存儲實驗室以及阿裡巴巴-浙江大學前沿技術聯合研究中心（AZFT）合作完成。在此向參與此項工作的研究人員以及指導論文寫作的老師表示感謝，相信未來還會有更多的合作成果産生。