X-Engine 研究綜述

研究背景

X-Engine 是一種基于 Log-structured Merge Tree (LSM-tree) 的存儲引擎，較基于 B-tree 一族的其它存儲引擎而言年輕很多，是以在實踐中遇到問題也更多，對研究的需求也更大。LSM-tree 是 1996 年由美國計算機科學家 Patrick O'Neil 等人提出的一種資料結構，和 B-tree 相比，它擁有更快的寫入性能和階層化的存儲結構，能夠同時利用好 DRAM 記憶體的高性能和持久化存儲的高容量。尤其是 LSM-tree 的分層存儲結構，可以天然地利用資料局部性将熱資料和冷資料差別開，友善壓縮算法有的放矢，有機會在降低整體成本的情況下，實作同樣優秀的性能。但是，與幾乎所有的計算機資料結構和系統設計一樣，有得必有失。LSM-tree 難以避免的在讀性能、I/O 寫放大和空間效率上面對挑戰。

寫路徑上的羅生門

首先，LSM-tree 使用了能夠支援快速寫入的 copy-on-write （CoW）方式來存儲新增資料。顧名思義，假如我要使用 CoW 來更新一條記錄，我不需要定位存儲引擎中該條記錄的位址并将它讀取出來，隻需要直接将我要更新的内容（例如，key = 100, value = value +100）寫入記憶體和日志（直接寫磁盤）即可。這樣整個寫入操作就像記日記一樣，我隻需要在日記本的最後一個空白頁上新增内容即可，至于這個日記本已經寫了多少頁，或者以前的某頁裡面寫了什麼，我都不需要管。是以，LSM-tree 的寫入操作代價很低，而且與資料庫已存資料無關，無論這個資料庫已經存了多少資料了，運作了多少天，寫一條記錄永遠是這麼快。同理，如果我需要删除一條記錄，我隻需要新插入一條反記錄即可。

那麼問題來了，讀記錄的時候我難免要去檢查一下這條記錄的原始資料在哪裡，是什麼，它有沒有更新，在哪裡，是什麼，然後把所有這樣的碎片合并在一起，我才知道這條記錄到底是什麼（例如，key == 100， value = 0 + 100）。這個過程顯然是比較費時的，不如我直接根據索引讀一份資料來得快。而且，絕大部分的資料庫是需要服務大量查詢的，幫使用者查資料才是資料庫的主要工作，使用者存資料就是為了有朝一日要讀取它。LSM-tree 涉嫌揀了芝麻，丢了西瓜。

問題還不至于此，因為在資料庫中所有的資料最終都要落盤來實作持久化存儲，那麼我在記憶體中新寫入的記錄就需要時不時地刷入到磁盤裡。刷盤時，反正都要做 I/O 寫，我們可以把新資料與舊資料直接合并到位，這樣就把碎片控制住了，同時保持了磁盤上資料的有序，友善讀取。可是，當盤上資料越來越多時，這樣的合并會越來越昂貴，在不能按位元組尋址的存儲器件上，我們必須讀入所有需要參與合并的頁，完成合并，并将這些頁寫回。随着資料增多，我們要讀的頁也會越來越多，整體代價也就越來越大。我們稱這個問題為『寫放大』。除了對性能的影響外，寫放大也會給 SSD 盤本身的 endurance 帶來壓力，如果寫放大過高，會提高雲廠商的服務成本。

為了解決寫放大問題，LSM-tree 在磁盤上已經進化出了一種分層存儲結構。新資料先寫在『零層』，零層我們給他一個非常小的容量，隻存剛剛刷下來的資料。因為資料局部性的緣故，零層的資料有很大機率會被通路到，那麼通過限制容量，無論怎麼通路，點讀也好，掃描也罷，它總共就這麼大點地方，不會慢到哪裡去。當零層容量飽和時，我們将它的内容與『壹層』中的資料合并。壹層比零層更大，比如大10倍。那麼理論上，這次合并，最多需要讀取和寫回壹層中十分之一左右的資料，不會更大了。寫放大，也就被我們限制住了。當『壹層』也滿了的時候，我們使用同樣的方法繼續往下刷，刷出『貳層』、『叁層』等等等等，以此類推。每一層的容量，比上一層大10倍，整個存儲中每層的大小呈指數級增長。有了階層化的存儲，配合合并操作，寫放大就這樣被控制住了。對于資料庫系統中的很多問題，我們往往不太可能把它徹底解決掉，而是将其控制在一定的可接受的界限内即可。

分層控制住了寫放大，但是新的問題又來了，合并算法本身是一種資料密集型算法，它需要讀取多路資料，然後進行相對簡單的合并計算，再将合并結果寫回去，整個過程其實本質上讀寫很多，對存儲帶寬的消耗非常大，也會給 CPU 流水線帶來很多的 I/O 等待、記憶體等待等氣泡，進而降低 CPU 流水線的執行效率，拖慢整個系統。單次跑一下還好，如果頻繁跑，會對系統性能有很大影響。而且它即不處理查詢，也不處理新增資料，完全是個看起來不必要的背景操作。這種合并操作，我們叫他『Compaction』。在 LSM-tree 引擎中，compaction 不僅肩負着層與層之間合并資料的任務，還肩負着為了删除操作将反記錄與真實記錄合并進而實作删除的任務等等，是一種多功能的重要操作，但它的成本真得不低。

到此為止，LSM-tree 在寫路徑上的各個部分都已經悉數登場了，而這片江湖上的恩恩怨怨才剛剛開始。為了服務好寫越來越多的 workload，LSM-tree 為了加速寫可謂是不遺餘力，基本上所有的設計都向寫路徑的性能做了傾斜，讓寫入看上去十分美好，實際上也開了一閃羅生門，門後慘象環生。具體怎麼慘，下文詳述。

讀路徑上帶着鐐铐的舞蹈

LSM-tree 上的讀路徑，從出生就帶着鐐铐。因為 CoW 的使用，讀一條記錄實際上需要把這條記錄所有的增量碎片都找到。因為橫跨記憶體和磁盤兩種媒體和有階層化的存儲，這些碎片可能藏在各種犄角旮旯裡面。更慘的是，如果是讀一個範圍内的記錄，俗稱 range scan，因為 LSM-tree 的每一層的 key range 是交疊的，那麼一個 range 内的資料就很有可能會落在所有的層次上，為了把他們都找到，我們就需要每層都去讀，這個工作量也不小。

為了解決這個問題，目前的 LSM-tree 引擎把各種經典技術都用上了：索引、cache。但是為了提高索引和 cache 的效率，讓他們一直發揮比較好的作用，難度不小。以 cache 為例，X-Engine 中使用了兩種經典的 cache，一種是 row cache，緩存記錄級别的熱資料，一種是 block cache，緩存資料塊級别的熱資料。Row cache 可以加速點查詢，block cache 可以加速 range scan，一切看上去都是很完美的芭蕾舞。然而，當 compaction 被大王叫來巡山的時候，危險就發生了。因為 compaction 會重新組織資料塊裡面的内容，幹掉一些老的 block，生成一些新的 block，傳統的 cache 替換政策對老的 block 做的通路統計會失效，而新的 block 它不認識，沒統計資訊。此外，compaction 還會移動資料。這兩點加起來，隻要 compaction 巡了一次山，cache 裡面緩存中的記錄就有很大可能出現大面積失效，導緻原本可以命中 cache 查詢，不得不去通路磁盤，造成嚴重的延遲尖刺。

熱資料的麻煩還不僅僅來源于 cache，因為熱資料經常會被大量更新，而 X-Engine 為了實作一個 OLTP 資料庫的 ACID 特性，使用了 MVCC 的并發控制方法，會為一條熱資料上存上非常多的版本，這樣的設計實際上造成了一條邏輯記錄可能會有特别多的實體分身。這個現實無論是對承接新寫入資料的 memtable（經常被實作為跳躍連結清單），還是索引，還是 compaction，都是一個很煩人的刺頭，硬生生地通過放大資料的體量來造成各種各樣的問題。

除了上述由于 LSM-tree 或者資料庫的機制帶來的問題意外，這些涉及到的資料結構本身的設計和實作也有很大的挑戰，比如 cache 的分桶政策、鎖的管理、跳躍連結清單和索引的查詢效率、資料結構針對多核處理器的并行優化等等等等，都是有很大發力空間的坑。除了讀路徑的問題，LSM-tree 上還有删除效率的問題、空間效率的問題等等，此處不再詳述，詳見相關論文。

學術成果與産學研互動

X-Engine 團隊為了解決上述問題做出了很多優化，申請了大量專利，其中的很多技術也作為學術成果在資料庫和存儲領域的頂會内完成了發表。

2019年，我們在 ACM SIGMOD 的 industrial track 中發表了一篇介紹 X-Engine 來龍去脈的論文《X-Engine: An Optimized Storage Engine for Large-scale E-commerce Transaction Processing》。在這篇文章中，我們介紹了 X-Engine 這種面向寫入優化的存儲引擎為什麼在工業界人氣飙升，為什麼阿裡巴巴的電商場景需要這樣的引擎，主要原因就是每次電商促銷所帶來的富含新增資料的高流量。面對這樣的挑戰，我們首先将問題拆解為了具體的資料庫技術問題，如處理高流量所需的并行寫入流水線、資料量海嘯快速占滿記憶體對資料刷盤帶來的壓力、促銷導緻的資料熱點範圍頻繁變化帶來的加速讀的挑戰等等。為了解決這些實際的技術問題，我們介紹了 X-Engine 做了怎麼樣的技術選型，采取了哪些優化，以及每項優化所帶來的實際效果。這篇論文是中國大陸公司首次在 SIGMOD 上發表資料庫核心上的工作。詳情請見論文（在 ACM DL 中可免費下載下傳）。

Alibaba runs the largest e-commerce platform in the world serving more than 600 million customers, with a GMV (gross merchandise value) exceeding USD 768 billion in FY2018. Online e-commerce transactions have three notable characteristics: (1) drastic increase of transactions per second with the kickoff of major sales and promotion events, (2) a large number of hot records that can easily overwhelm system buffers, and (3) quick shift of the "temperature'' (hot v.s. warm v.s. cold) of different records due to the availability of promotions on different categories over different short time periods. For example, Alibaba's OLTP database clusters experienced a 122 times increase of transactions on the start of the Singles' Day Global Shopping Festival in 2018, processing up to 491,000 sales transactions per second which translate to more than 70 million database transactions per second. To address these challenges, we introduce X-Engine, a write-optimized storage engine of POLARDB built at Alibaba, which utilizes a tiered storage architecture with the LSM-tree (log-structured merge tree) to leverage hardware acceleration such as FPGA-accelerated compactions, and a suite of optimizations including asynchronous writes in transactions, multi-staged pipelines and incremental cache replacement during compactions. Evaluation results show that X-Engine has outperformed other storage engines under such transactional workloads.

論文摘要

2020年，與 AIS 軟硬體結合開發團隊合作，我們在存儲領域的頂會 USENIX FAST 2020 上發表了我們利用 FPGA 異構計算技術來加速 X-Engine 中很多問題的罪魁禍首—— compaction 的工作《FPGA-Accelerated Compactions for LSM-based Key-Value Store》。在這項工作中，我們首先系統研究了 compaction 對 LSM-tree 存儲引擎在 CPU、記憶體、磁盤等資源的消耗上有什麼特征，分析了 compaction 的算法，發現 compaction 算法在合并較短的記錄的時候竟然是受限于 CPU 的。其原因一方面是因為 compaction 對計算的需求，另一方面也是因為這些年來磁盤帶寬有了顯著的增長。是以，我們提出将 compaction 算法 offload 到 FPGA 加速卡上，并在 FPGA 上設計和實作了一套高效的流水線，和 CPU host 實作了快速的互動，也實作了 compaction 算法的加速。這項工作所做的探索讓我們看到了計算型存儲技術的紅利。近年來，随着 SSD 的不斷發展和處理器的微小型化，市場上出現了類似 SmartSSD 這樣的計算型儲存設備，其核心優勢是把較小的 ARM CPU 處理器或者 FPGA 晶片直接嵌入 SSD 内部，讓部分計算任務不需要離開 SSD 就能完成，省去了 I/O 和 CPU 的開銷。因為 SSD 内部的訪存帶寬比外部的 I/O 快幾十倍，計算型存儲特别适合處理類似 compaction、scan 等相對而言更加訪存密集的操作。今年阿裡雲資料庫團隊在 FAST 上收獲了大豐收，投稿的 3 篇論文全部被錄用，而 FAST 是個比較小而專的會議，今年一共也僅有 23 篇論文。

Log-Structured Merge Tree (LSM-tree) key-value (KV) stores have been widely deployed in the industry due to its high write efficiency and low costs as a tiered storage. To maintain such advantages, LSM-tree relies on a background compaction operation to merge data records or collect garbages for housekeeping purposes. In this work, we identify that slow compactions jeopardize the system performance due to unchecked oversized levels in the LSM-tree, and resource contentions for the CPU and the I/O. We further find that the rising I/O capabilities of the latest disk storage have pushed compactions to be bounded by CPUs when merging short KVs. This causes both query/transaction processing and background compactions to compete for the bottlenecked CPU resources extensively in an LSM-tree KV store.

In this paper, we propose to offload compactions to FPGAs aiming at accelerating compactions and reducing the CPU bottleneck for storing short KVs. Evaluations have shown that the proposed FPGA-offloading approach accelerates compactions by 2 to 5 times, improves the system throughput by up to 23%, and increases the energy efficiency (number of transactions per watt) by up to 31.7%, compared with the fine-tuned CPU-only baseline. Without loss of generality, we implement our proposal in X-Engine, a latest LSM-tree storage engine.

除了上述已經發表的成果，我們還探索了使用機器學習技術來預測 compaction 前後的資料通路趨勢，以解決傳統 cache 替換政策被幹擾的問題；我們也探索了在 X-Engine 内部應用細粒度、自适應的排程算法，來改善 compaction 的執行時機，進而提高系統性能的穩定性；我們也優化了記憶體配置設定政策、cache 結構和通路方式等等底層細節，旨在從根本上顯著提高 X-Engine 的性能。目前，這些工作還在進一步的研發中。

X-Engine 自 2019 年進入資料庫界國際頂級學術圈以來，通過向學術界介紹阿裡巴巴的應用場景以及技術挑戰，尤其是 X-Engine 引擎本身所面對的技術挑戰，已經吸引了很多專家學者的目光。我們所抛出的 LSM-tree 删除性能差的問題，已經吸引了來自波士頓大學和哈佛大學的研究者提出了新的優化技術，相應學術成果将發表在最近的學術會議中。在國内，X-Engine 團隊與阿裡自家的達摩院資料庫存儲與實驗室、浙江大學 AZFT 實驗室孫建玲教授、中科院計算所陳世敏教授等學者和研究人員長期合作，共同研究 LSM-tree 相關的技術問題，并且不斷産出優質的學術成果。通過學術合作，目前已經發表了 FAST 一篇，VLDB 一篇。除此以外，我們追求将學術研究探索出來的新技術真正落地在 X-Engine 系統核心中，為提高 X-Engine 産品力貢獻力量。

未來研究方向

未來，X-Engine 團隊會針對生産實踐中遇到的各項技術難題展開公關，也會緊跟新的技術趨勢，探索新型硬體（如 NVM，FPGA 等）在 X-Engine 上的應用。首先，分布式是資料庫産品的潮流。在未來，使用者不需要再操心分庫分表或者擴充性上的麻煩，而是買一份分布式資料庫，把所有任務都交給它後就高枕無憂了。X-Engine 團隊目前正緻力于下一代分布式資料庫 PolarDB-X 的研發，旨在為使用者提供一款高性能、低成本、伸縮性好的分布式資料庫産品，将阿裡多年來積累的資料庫技術紅利分享給阿裡雲上的客戶們。在這個方向上，我們會着力于私有協定、分布式事務處理、分布式負載均衡、故障恢複等重要技術問題。其次，我們認為，X-Engine 的記憶體部分可以看成一個記憶體資料庫，應該與處理器、DRAM 記憶體等硬體深度融合，突破性能瓶頸。具體的研究方向包括 cache-conscious 的高性能記憶體索引、利用 SIMID 技術（Single Instruction Multiple Data）來加速記憶體資料結構通路、降低記憶體鎖開銷等。最後，對于時下的熱點人工智能，我們也不會放過。目前，我們已經探索了機器學習技術在 cache 替換上的應用，未來我們會探索智能調參、智能 compaction 排程、智能索引等 AI for DB 技術。我們希望利用人工智能技術，将複雜的資料庫運維轉換為十分傻瓜的簡單操作，降低使用者使用和維護資料庫的難度，同時改善資料庫的性能。

作為一款重量級的資料庫基礎軟體，X-Engine 雖然看上去隻是負責資料增、删、改、查這樣平淡無奇的操作，但正是因為這些操作足夠基礎，X-Engine 才會被內建與 MySQL 核心和分布式資料庫 PolarDB-X 中，我們的每一項優化也擁有了更大的影響力，直接決定着所有上層應用的安全、穩定和性能。歡迎有志于從事國産自研存儲引擎研發的同學加入我們。