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就此寫過一篇論文，分析指出傳統關系通用型資料庫，僅僅有不到百分之十左右的時間是在做真正有效的處理資料工作。剩下百分之九十多的時間都浪費在其它工作上,比如一些加鎖等待，緩沖管理，日志同步等。
造成這種現象的原因是近些年來，我們所依賴的硬體體系發生了巨大的變化：多核(衆核)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的架構和優化技術已經被總結成論文，發表在了資料庫業界最頂尖的會議SIGMOD'19，尚屬中國大陸公司首次在國際頂會上發表OLTP資料庫核心相關的技術成果。
技術特點
X-Engine基于LSM-Tree架構設計，主要是為了利用其天然分層的結構，同時為了避免LSM固有的一些劣勢，對整個存儲架構做了根本性的調整和優化，比如 :
- 使用多事務處理隊列和流水線處理技術，減少線程上下文切換代價，并計算每個階段任務量配比，使整個流水線充分流轉，極大提升事務處理性能，相對于其他類似架構的存儲引擎比如RocksDB，X-Engine的事務處理性能有10倍以上提升。
- X-Engine使用的copy-on-write技術，避免原地更新資料頁，進而對隻讀資料頁面進行編碼壓縮，相對于傳統存儲引擎(比如InnoDB)資料壓縮2倍以上。
- 資料複用技術減少資料合并代價，并且因為資料複用減少緩存淘汰帶來的性能抖動。進一步利用FPGA硬體加速compaction過程，使得系統上限進一步提升。這個技術也屬首次将硬體加速技術應用到線上事務處理資料庫存儲引擎中，我們也将其總結為論文已經被今年的頂級會議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沒有做過多優化，原因在事務處理的邏輯比較複雜，寫入記憶體表還沒有成為其瓶頸。
持久化層如何組織更顯高效，這就需要讨論每層的細微結構。
資料組織
簡單來說，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"，如果你讀過那篇論文，會對了解這個過程有所幫助。
事務處理
得益于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)。我們的事務送出線程到了處理階段，都可以自由選擇執行流水線中任意一個階段，這樣每個階段都可以并行起來，隻要流水線任務的大小劃分得當，就能充分并行起來，流水線處于接近滿載狀态。
另外，利用的是事務處理的線程，而非背景線程，每個線程在執行的時候，要麼選擇了流水線中的一個階段幹活，要麼逛了一圈發現無事可做，幹脆回去接收更多的請求，這裡沒有等待，也無需切換，充分的調動了每個線程的能力。
讀操作
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同樣做了很多的處理：
- 減少Compaction的粒度。
- 減少compaction過程中改動的資料(見稍後章節)
- 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分布式版本的核心，提供企業級資料庫服務。
相關閱讀
1，阿裡雲RDS vs 自建MySQL，這篇評測終結你的選擇困難症!
https://developer.aliyun.com/article/7421892，内附大神PPT | 最大化資源管理技術紅利， 阿裡雲重磅釋出RDS MySQL專屬主機組服務！
https://developer.aliyun.com/article/7422363，同樣是365天，但RDS for MySQL的這一年也太高産了...
https://developer.aliyun.com/article/742127