作者：曲山，阿里雲資深技術專家

X-Engine是阿里自研的資料庫存儲引擎，曾一度登上過資料庫業界最頂尖的會議SIGMOD，作為RDS MySQL的存儲引擎，X-Engine到底有何魅力呢？

X-Engine是什麼

X-Engine是阿里自研的資料庫存儲引擎，可以作為MySQL的存儲引擎使用，兼容MySQL的功能，目前已經廣泛應用在阿里集團內部諸多業務系統中。只需要在配置中將默認存儲引擎設置為X-Engine，在後續過程中所有創建的表就可以使用了，當然也可以在創建表時指定存儲引擎，這樣只有指定的表才會使用X-Engine.

那麼問題來了，為什麼要使用X-Engine?

為什麼設計一個新的存儲引擎

X-Engine是阿里內部生長出來的，一開始，也是為應對阿里內部業務帶來的挑戰，早在2010年，阿里內部就大規模部署了MySQL資料庫，但是業務量的逐年爆炸式增長，對資料庫提出了嚴苛的要求，一是極高的並發事務處理能力，尤其是雙十一的流量突髮式暴增；二是數據規模超大，需要占用大量存儲資源。

這兩個問題當然都可以擴展資料庫節點的分布式方案解決，不過堆機器不是一個高效的手段，我們更想用技術的手段來將單機的資料庫性價比提升到極致，達到以少量資源換取性能大幅上升的目的。

傳統資料庫架構下的性能已經被仔細的研究過，資料庫領域的泰斗，圖靈獎得主Michael Stonebreaker就此寫過一篇論文<OLTP Through the Looking Glass, and What We Found There>，分析指出傳統關係通用型資料庫，僅僅有不到百分之十左右的時間是在做真正有效的處理數據工作。剩下百分之九十多的時間都浪費在其它工作上,比如一些加鎖等待，緩衝管理，日誌同步等。

造成這種現象的原因是近些年來，我們所依賴的硬體體系發生了巨大的變化：多核(眾核)CPU，新的處理器架構(Cache/NUMA)，各種異構計算設備(GPU/FPGA)，越來越大，越來越便宜的內存，越來越快的存儲設備(SSD/3D-XPoint/NVRAM)…

而架構在這之上的資料庫軟體棧卻沒有太大的改變，一切都是為了慢速磁碟而設計，使用B-Tree索引的固定大小的數據頁(Page)，使用ARIES算法的事務處理與數據恢復機制，基於獨立鎖管理器的並發控制…

這一切在現有的體系架構上，很難發揮出硬體應有的性能，大量的cpu cycles被浪費在等鎖等無效操作上了，這些問題在小規模體量的數據上還不太明顯，一旦吞吐和數據量上來，就成為瓶頸了。

整體架構

為此我們設計了全新架構的存儲引擎X-Engine，得益於MySQL Pluginable Storage Engine的特性，X-Engine可以無縫對接兼容MySQL特性，我們只需要專注優化存儲結構就好。

X-Engine使用了一種對數據進行分層的存儲架構，(如下圖) 因為目標是面向大規模的海量數據存儲，提供高並發事務處理能力和儘可能降低成本，我們觀察到，大部分大數據量場景下，數據被訪問的機會是不均等的，訪問頻繁的熱數據實際上占比很少。

X-Engine根據數據訪問頻度(冷熱)的不同將數據劃分為多個層次，針對每個層次數據的訪問特點，設計對應的存儲結構，寫入合適的存儲設備。

X-Engine使用了LSM-Tree作為分層存儲的架構基礎，並在這之上進行了重新設計。簡單來講，熱數據層和數據更新使用內存存儲，利用了大量內存資料庫的技術(Lock-Free index structure/append only)提高事務處理的性能。

我們設計了一套事務處理流水線處理機制，把事務處理的幾個階段並行起來，極大提升了吞吐。

而訪問頻度低的冷(溫)數據逐漸淘汰或是合併到持久化的存儲層次中，結合當前豐富的存儲設備層次體系(NVM/SSD/HDD)進行存儲。

我們對性能影響比較大的compaction過程做了大量優化，主要是拆分數據存儲粒度，利用數據更新熱點較為集中的特徵，儘可能的在合併過程中復用數據，精細化控制LSM的形狀，減少I/O和計算代價，並同時極大的減少了合併過程中的空間放大。

同時使用更細粒度的訪問控制和緩存機制，優化讀的性能。

X-Engine的架構和優化技術已經被總結成論文<X-Engine: An Optimized Storage Engine for Large-scale E-Commerce Transaction Processing>，發表在了資料庫業界最頂尖的會議SIGMOD'19，尚屬中國大陸公司首次在國際頂會上發表OLTP資料庫內核相關的技術成果。

技術特點

X-Engine基於LSM-Tree架構設計，主要是為了利用其天然分層的結構，同時為了避免LSM固有的一些劣勢，對整個存儲架構做了根本性的調整和優化，比如 :

• 使用多事務處理隊列和流水線處理技術，減少線程上下文切換代價，並計算每個階段任務量配比，使整個流水線充分流轉，極大提升事務處理性能，相對於其他類似架構的存儲引擎比如RocksDB，X-Engine的事務處理性能有10倍以上提升。
• X-Engine使用的copy-on-write技術，避免原地更新數據頁，從而對只讀數據頁面進行編碼壓縮，相對於傳統存儲引擎(比如InnoDB)數據壓縮2倍以上。
• 數據復用技術減少數據合併代價，並且因為數據復用減少緩存淘汰帶來的性能抖動。進一步利用FPGA硬體加速compaction過程，使得系統上限進一步提升。這個技術也屬首次將硬體加速技術應用到在線事務處理資料庫存儲引擎中，我們也將其總結為論文<FPGA-Accelerated Compactions for LSM-based Key Value Store>已經被今年的頂級會議FAST'20接收.
• Bloom Filter 快速判定數據是否存在, Surf Filter判斷範圍數據是否存在, Row Cache緩存熱點行，加速讀取性能。

以下章節逐一介紹X-Engine的優化架構和實現細節。既然是基於LSM架構設計，首先簡要介紹下LSM架構的一些特點。

背景知識:LSM基本邏輯

一條數據在LSM結構中的旅程，從寫入WAL(Write Ahead Log)開始，然後進入MemTable，這是Ta整個生命周期的第一處落腳點。隨後，flush操作將Ta刻在更穩固的介質上，compaction操作將Ta帶往更深遠的去處，或是在途中丟棄，取決於Ta的繼任者何時到來。

LSM的本質是，所有寫入操作並不做原地更新，而是以追加的方式寫入內存。每次寫到一定程度，即凍結為一層(Level)，寫入持久化存儲。所有寫入的行，都以主鍵(Key)排序好後存放，無論是在內存中，還是持久化存儲中。在內存中即為一個排序的內存數據結構(Skiplist, B-Tree, etc.)，在持久化存儲也作為一個只讀的全排序持久化存儲結構。

普通的存儲系統若要支持事務處理，尤其是ACI，需要加入一個時間維度，藉此為每個事務構造出一個不受並發乾擾的獨立視域。存儲引擎會對每個事務定序並賦予一個全局單調遞增的事務版本號(SN)，每個事務中的記錄會存儲這個SN以判斷獨立事務之間的可見性，從而實現事務的隔離機制。

如果LSM存儲結構持續寫入，不做其他的動作，那麼最終會成為如下結構：

注意這裡每一層的SN範圍標識了事務寫入的先後順序，已經持久化的數據不再會被修改。每一層數據按Key排序，層與層之間的Key range會交疊。

這種結構對於寫入是非常友好的，只要追加到最新的內存表中即完成，為實現crash recovery，只需記錄WAL(Redo Log)，因為新數據不會覆蓋舊版本，追加記錄會形成天然的多版本結構。

可以想見，如此累積凍結的持久化層次越來越多，會對查詢會產生不利的影響，對同一個key不同事務提交產生的多版本記錄會散落在各個層次中，不同的key也會散落在不同層次中，讀操作諸如順序掃描便需要查找各個層併合並產生最終結果。

LSM引入了一個compaction的操作解決這個問題，這個操作不斷的把相鄰層次的數據合併，並寫入這個更低層次。而合併的過程實際上就是把要合併的相鄰兩層(或是多層)數據讀出來，按key排序，相同的key如果有多個版本，只保留新(比當前正在執行的活躍事務中最小版本號新)的版本，丟掉舊版本數據，然後寫入新的層。可以想見這個操作非常耗費資源。

LSM compaction操作，有幾種作用，一是為了丟棄不再被使用的舊版本數據，二是為了控制LSM層次形狀，一般的LSM形狀都是層次越低，數據量越大(倍數關係)，這樣放置的目的主要是為了提升讀性能。

一般來講，任何存儲系統的數據訪問都有局部性，大量的訪問都集中在少部分數據上，這也是緩存系統能有效工作的基本前提。

在LSM存儲結構中，如果我們把訪問頻率高的數據儘可能放在較高的層次上，保持這部分數據量規模，可以存放在快速存儲設備中(比如NVM,DRAM)，而把訪問頻率低的數據放在較低層次中，使用廉價慢速存儲設備存儲。這就是X-Engine的根據冷熱分層概念。

要達到這種效果，核心問題是如何挑選合適的數據合併到更低的層次，這是compaction調度策略首先要解決的問題，根據冷熱分層的邏輯，就是優先合併冷數據(訪問頻率相對低)。

識別冷數據有很多方法，對於不同的業務不盡然相同，對於很多流水型業務(如交易，日誌系統)，新近寫入的數據會有更多的機率被讀到，冷熱按寫入時間順序即可區分，也有很多應用的訪問特徵跟寫入的時間不一定有關係，這個就要根據實際的訪問頻率去識別冷數據或是熱數據。

除了數據熱度以外，挑選合併數據還有其他一些維度，會對讀性能產生影響，比如數據的更新頻率，大量的多版本數據在查詢的時候會浪費更多的I/O和CPU，因此需要優先進行合併以減少記錄的版本數量，X-Engine綜合考慮了各種策略形成自己的compaction調度機制。

X-Engine:高度優化的LSM

上面是LSM宏觀邏輯結構，如果具體來論讀寫操作和compaction如何進行，就需要探討每一層的數據組織方式,每個LSM變種的實現各不相同。

X-Engine的memtable使用了Locked-free SkipList. 求的是簡單，而且並發讀寫的性能都比較高。當然有更高效的數據結構，或者同時使用多種索引技術。這個部分X-Engine沒有做過多優化，原因在事務處理的邏輯比較複雜，寫入內存表還沒有成為其瓶頸。

持久化層如何組織更顯高效，這就需要討論每層的細微結構。

1、數據組織

簡單來說，X-Engine的每層都劃分成固定大小的Extent，存放每個層次中的數據的一個連續片段(Key Range). 為了快速定位Extent，為每層Extents建立了一套索引(Meta Index)，所有這些索引，加上所有的memory tables(active/immutable)一起組成了一個元數據樹(Metadata Tree)，root節點為"Metadata Snapshot", 這個樹結構類似於B-Tree，當然不盡相同。

需要注意的是，X-Engine中除了當前的正在寫入的active memtable以外，其他結構都是只讀的，不會被修改。給定某個時間點, 比如LSN=1000, 上圖中的"Metadata Snapshot1"引用到的結構即包含了(LSN=1000)時刻的所有的數據的快照(這也是為什麼這個結構被稱為Snapshot的原因)。

即便是Metadata結構本身，也是一旦生成就不會修改。所有的讀都是以這個"Snapshot"結構為入口，這個是X-Engine實現SI隔離級別的基礎。之前講過隨著數據寫入，累積數據越多，需要對memtable凍結，flush, 以及層與層的compaction. 這些操作都會修改每層的數據存儲結構。

所有這些操作，都是用copy-on-write來實現，方法就是每次都將修改(switch/flush/compaction)產生的結果寫入新的Extent，然後依次生成新的"Meta Index"結構，乃至新的"Metadata Snapshot"，以一次compaction操作為例：

可以看到"Metadata Snapshot 2"相對於"Metadata Snapshot 1"並沒有太多的變化，僅僅修改了發生變更的一些葉子節點以及索引節點。這個技術頗有些類似"B-trees, Shadowing, and Clones"，如果你讀過那篇論文，會對理解這個過程有所幫助。

2、事務處理

得益於LSM輕量化寫機制，寫入操作固然是其明顯的優勢，但是事務處理遠不只是把更新的數據寫入系統那麼簡單，這裡要保證ACID，涉及到一整套複雜的流程。

X-Engine將整個事務處理過程分為兩個階段：讀寫階段和提交階段。讀寫階段需要校驗事務的寫寫衝突，讀寫衝突，判斷事務是否可以執行或回滾重試，或是等鎖。如果事務衝突校驗通過，則把修改的所有數據寫入"Transaction Buffer", 提交階段包括寫WAL，寫內存表，以及提交並返回給用戶結果的整個過程，這裡面既有I/O操作(寫日誌,返回消息)，也有CPU操作(拷貝日誌,寫內存表)。

為了提高事務處理吞吐，系統內會有大量事務並發執行，單個I/O操作比較昂貴，大部分存儲引擎會傾向於聚集一批事務一起提交，稱為"Group Commit"，能夠合併I/O操作，但是一組事務提交的過程中，還是有大量等待過程的，比如寫入日誌到磁碟過程中，除了等待落盤無所事事。

X-Engine為了進一步提升事務處理的吞吐，採用了一種流水線的技術：把提交階段分為四個獨立的更細的階段：拷貝日誌到緩衝區(Log Buffer), 日誌落盤(Log Flush), 寫內存表(Write memtable), 提交返回(Commit)。我們的事務提交線程到了處理階段，都可以自由選擇執行流水線中任意一個階段，這樣每個階段都可以並行起來，只要流水線任務的大小劃分得當，就能充分並行起來，流水線處於接近滿載狀態。

另外，利用的是事務處理的線程，而非後台線程，每個線程在執行的時候，要麼選擇了流水線中的一個階段幹活，要麼逛了一圈發現無事可做，乾脆回去接收更多的請求，這裡沒有等待，也無需切換，充分的調動了每個線程的能力。

3、讀操作

LSM在處理多版本數據的方式是新版本數據記錄會追加在老版本數據後面，從物理上看，一條記錄不同的版本可能存放在不同的層，在查詢的時候需要找到合適的版本(根據事務的隔離級別定義的可見性規則)，一般查詢都是查找最新的數據，總是由新的層次(最新寫入)往老的層次方向找。

對於單條記錄的查找而言，一旦找到便可終止，如果記錄還在比較靠上的層次，比如memtable，很快便返回；如果記錄不幸已經落入了很低的層次(可能是很隨機的讀)，那就得經歷逐層查找的漫漫旅途，也許bloomfilter可以跳過某些層次加快這個旅程，但畢竟還是有更多的I/O操作。

X-Engine針對單記錄查詢引入了Row Cache，在所有持久化的層次的數據之上做了一個緩存，在memtable中沒有命中的單行查詢，在Row Cache之中也會被捕獲。Row Cache需要保證緩存了所有持久化層次中最新版本的記錄，而這個記錄是可能發生變化的，比如每次flush將只讀的memtable寫入持久化層次時，就需要恰當的更新Row Cache中的緩存記錄，這個操作比較微妙，需要小心的設計。

範圍掃描的操作就沒這麼幸運了。因為沒法確定一個範圍的key在哪個層次中有數據，也許是每層都有，只能掃描所有的層次做合併之後才能返回最終的結果。X-Engine同樣採用了一系列的手段：比如Surf(SIGMOD'18 best paper)提供range scan filter減少掃描層數；還有異步I/O與預取對大範圍掃描也有顯著的提升。

讀操作中最核心的是緩存設計，Row Cache來應付單行查詢，Block Cache負責Row Cache miss的漏網之魚，也用來應付scan；由於LSM的compaction操作會一次大批量更新大量的Data Block，導致Block Cache中大量數據短時間內失效，帶來性能的急劇抖動。X-Engine同樣做了很多的處理：

1.減少Compaction的粒度,。

2. 減少compaction過程中改動的數據(見稍後章節)

3. compaction過程中針對已有的cache數據做定點更新。由此可以基本將cache失效帶來的抖動降到最低的水平。

X-Engine中的緩存比較多樣，memtable也可算做其中一種。以有限的內存，如何恰當的分配給每一種緩存，才能實現價值最大化，是一個還未被妥善解決的問題，X-Engine也在探索當中。

當然，LSM對讀帶來的也並非全是壞處，除了memtable以外的只讀的結構，在讀取路徑上可以做到完全無鎖(memtable也可設計成讀無鎖)。

Compaction

compaction操作是比較重的。需要把相鄰層次交叉的key range數據讀出來，合併，然後寫到新的位置。這是為前面簡單的寫入操作不得不付出的代價。X-Engine為優化這個操作重新設計了存儲結構。

如前所述，X-Engine將每一層的數據劃分為固定大小的"Extent"，一個Extent相當於一個小的完整的SSTable, 存儲了一個層次中的一個連續片段，其中又會被進一步劃分一個個連續的更小的片段"Data Block"，相當於傳統資料庫中的"Page"，只不過是只讀的，而且是不定長的。

回看數據組織一節中"合併操作對元數據的改變", 對比"Metadata Snapshot2"和"Metadata Snapshot1"的區別，可以發現Extent的設計意圖。是的，每次修改對結構的調整並不是全部來過，而是只需要修改少部分有交疊的數據，以及涉及到的"Meta Index"節點。

兩個"Metadata Snapshot"結構實際上共用了大量的數據結構。這個被稱為數據復用技術(Data Reuse)，而Extent大小正是影響數據復用率的關鍵，Extent作為一個完整的被復用的物理結構，需要儘可能的小，這樣與其他Extent數據交叉點會變少，但又不能非常小，否則需要索引過多，管理成本太大。

X-Engine中compaction的數據復用是非常徹底的，假設選取兩個相鄰層次(Level1, Level2)中的交叉的Key Range所涵蓋的Extents進行合併，合併算法會逐行進行掃描，只要發現任意的"物理結構"(包括Data Block和Extent)與其他層中的數據沒有交疊，則可以進行復用。只不過，Extent的復用可以修改Meta Index，而Data Block的復用只能拷貝，即便如此也可以節省大量的CPU.

一個典型的數據復用在compaction中的過程可以參考下圖：

可以看出，對於數據復用的過程是在逐行疊代的過程中完成的，不過這種精細的數據復用帶來另一個副作用，即數據的碎片化，所以在實際操作的過程中也需要根據實際情況進行折中。

數據復用不僅給compaction操作本身帶來了好處，降低操作過程中的I/O與CPU消耗，更對系統的綜合性能產生了一系列的影響。比如compaction過程中數據不用完全重寫，大大減少了寫入空間放大; 更因為大部分數據保持原樣，數據緩存不會因為數據更新而失效，減少合併過程中因緩存失效帶來的讀性能抖動。

實際上，優化compaction的過程只是X-Engine工作的一部分，還有更重要的，就是優化compaction調度的策略，選什麼樣的Extent，定義compaction任務的粒度，執行的優先級，都會對整個系統性能產生影響，可惜並不存在什麼完美的策略，X-Engine積累了一些經驗，定義了很多規則，而探索如何合理的調度策略是未來一個重要方向。

什麼時候你應該選擇使用X-Engine

X-Engine一直以來的目標都是為了成為MySQL生態體系下大數據體量通用存儲引擎，我們還在持續優化存儲結構，壓縮算法，讀寫性能，穩定性，以期達到最好的性價比。

X-Engine仍然有他最擅長的方向，可以作為在線歷史數據一體化的資料庫，在不損失讀寫性能的情況下充分壓縮數據表，根據我們的測試結果，在標準TPC-C測試場景下，X-Engine的tpmC性能與InnoDB基本持平。如果你的應用使用MySQL資料庫，有大量寫入，希望大幅降低存儲成本，並且有一定查詢需求的應用，例如日誌、消息歸檔，訂單流水存儲等等，都非常適合使用X-Engine.

X-Engine不只是一個為研究設計的系統，從一開始就是為了實現用戶價值，在阿里集團內部大規模使用已經有兩年多，並且在最為核心的交易，釘釘消息歷史庫上都全面替代了原有的系統，達到了預期中的良好效果，為交易歷史庫(原來使用HBase)節省33%成本，為釘釘消息歷史庫(原來使用MySQL with InnoDB)節省了60%的成本。

更多信息請參考X-Engine RDS最佳應用實踐。

如何在MySQL RDS中使用X-Engine

X-Engine目前只在RDS MySQL 8.0版本中提供，當前使用RDS MySQL 5.6/5.7的用戶如果想使用X-Engine引擎，請遷移至RDS MySQL 8.0版本，同時配置X-Engine引擎生效，你可以設置默認存儲引擎為X-Engine，也可以在創建表時顯示指定表存儲引擎為X-Engine，與其他存儲引擎混合使用，也可以通過alter table your_table engine = xengine來將已有的錶轉換為X-Engine存儲(注意此操作會鎖表並拷貝數據，視數據存量大小需要時間不等)。

具體的操作，參數配置，以及使用限制，請參見X-Engine使用文檔。

後續方向

作為MySQL的存儲引擎，持續的提升MySQL系統的兼容能力是一個重要目標，後續會根據需求的迫切程度逐步加強原本取消的一些功能，比如外鍵，對一些數據結構，索引類型的支持。

X-Engine作為存儲引擎，核心的價值還在於性價比，持續提升性能降低成本，是一個長期的根本目標，X-Engine還在compaction調度，緩存管理與優化，數據壓縮，事務處理等方向上一直進行深層次的探索。

X-Engine不僅僅局限在一個單機的資料庫存儲引擎，未來還將作為自研分布式資料庫PolarDB分布式版本的核心，提供企業級資料庫服務。