ApsaraDB RDS：X-Engine引擎

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

X-Engine的誕生是為了應對阿里內部業務的挑戰，早在2010年，阿里內部就大規模部署了MySQL資料庫，但是業務量的逐年爆炸式增長，資料庫面臨著極大的挑戰：

• 極高的並發交易處理能力（尤其是雙十一的流量突髮式暴增）。

• 超大規模的資料存放區。

這兩個問題雖然可以通過擴充資料庫節點的分布式方案解決，但是堆機器不是一個高效的手段，我們更想用技術的手段將資料庫性價比提升，實現以少量資源換取效能大幅提高的目的。

傳統資料庫結構描述的效能已經被仔細的研究過，資料庫領域的泰鬥，圖靈獎得主Michael Stonebreaker就此寫過一篇論文 《OLTP Through the Looking Glass, and What We Found There》，指出傳統關係型資料庫，僅有不到10%的時間是在做真正有效資料處理工作，剩下的時間都浪費在其它工作上，例如加鎖等待、緩衝管理、日誌同步等。

造成這種現象的原因是近年來我們所依賴的硬體體系發生了巨大的變化，例如多核（眾核）CPU、新的處理器架構（Cache/NUMA）、各種異構計算裝置（GPU/FPGA）等，而架構在這些硬體之上的資料庫軟體卻沒有太大的改變，例如使用B-Tree索引的固定大小的資料頁（Page）、使用ARIES演算法的交易處理與資料恢複機制、基於獨立鎖管理器的並發控制等，這些都是為了慢速磁碟而設計，很難發揮出現有硬體體系應有的效能。

基於以上原因，阿里開發了適合當前硬體體系的儲存引擎，即X-Engine。

X-Engine架構

全新架構的X-Engine儲存引擎不僅可以無縫對接相容MySQL（得益於MySQL Pluginable Storage Engine特性），同時X-Engine使用階層式存放區架構。

因為目標是面向大規模的海量資料存放區，提供高並發交易處理能力和降低儲存成本，在大部分巨量資料量情境下，資料被訪問的機會是不均等的，訪問頻繁的熱資料實際上佔比很少，X-Engine根據資料訪問頻度的不同將資料劃分為多個層次，針對每個層次資料的訪問特點，設計對應的儲存結構，寫入合適的存放裝置。

X-Engine使用了LSM-Tree作為階層式存放區的架構基礎，並進行了重新設計：

• 熱資料層和資料更新使用記憶體儲存，通過記憶體資料庫技術（Lock-Free index structure/append only）提高交易處理的效能。

• 流水線交易處理機制，把交易處理的幾個階段並行起來，極大提升了吞吐。

• 訪問頻度低的資料逐漸淘汰或是合并到持久化的儲存層次中，並結合多層次的存放裝置（NVM/SSD/HDD）進行儲存。

• 對效能影響比較大的Compaction過程做了大量最佳化：

  • 拆分資料存放區粒度，利用資料更新熱點較為集中的特徵，儘可能的在合并過程中複用資料。

  • 精細化控制LSM的形狀，減少I/O和計算代價，有效緩解了合并過程中的空間增大。

• 同時使用更細粒度的存取控制和緩衝機制，最佳化讀的效能。

技術特點

• 利用FPGA硬體加速Compaction過程，使得系統上限進一步提升。這個技術屬首次將硬體加速技術應用到線上交易處理資料庫儲存引擎中，相關論文 《FPGA-Accelerated Compactions for LSM-based Key Value Store》已經被2020年的FAST'20國際會議接收。

• 通過資料複用技術減少資料合併代價，同時減少緩衝被淘汰帶來的效能抖動。

• 使用多交易處理隊列和流水線處理技術，減少線程環境切換代價，並計算每個階段任務量配比，使整個流水線充分流轉，極大提升交易處理效能。相對於其他類似架構的儲存引擎（例如RocksDB），X-Engine的交易處理效能有10倍以上提升。

• X-Engine使用的Copy-on-write技術，避免原地更新資料頁，從而對唯讀資料頁面進行編碼壓縮，相對於傳統儲存引擎（例如InnoDB），使用X-Engine可以將儲存空間降低至10%~50%。

• Bloom Filter快速判定資料是否存在，Surf Filter判斷範圍資料是否存在，Row Cache緩衝熱點行，加速讀取效能。

LSM基本邏輯

LSM的本質是所有寫入操作直接以追加的方式寫入記憶體。每次寫到一定程度，即凍結為一層（Level），並寫入持久化儲存。所有寫入的行，都以主鍵（Key）排序後存放，無論是在記憶體中，還是持久化儲存中。在記憶體中即為一個排序的記憶體資料結構（Skiplist、B-Tree等），在持久化儲存也作為一個唯讀全排序持久化儲存結構。

普通的儲存系統若要支援交易處理，需要加入一個時間維度，為每個事務構造出一個不受並發乾擾的獨立視域。例如儲存引擎會對每個事務定序並賦予一個全域單調遞增的事務版本號碼（SN），每個事務中的記錄會儲存這個SN以判斷獨立事務之間的可見度，從而實現事務的隔離機制。

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

這種結構對於寫入是非常友好的，只要追加到最新的記憶體表中即完成，為實現故障恢複，只需記錄Redo Log，因為新資料不會覆蓋舊版本，追加記錄會形成天然的多版本結構。

但是如此累積，凍結的持久化層次越來越多，會對查詢產生不利的影響。例如對同一個key，不同事務提交產生的多版本記錄會散落在各個層次中；不同的key也會散落在不同層次中。讀操作需要尋找各個層併合並才能得到最終結果。

因此LSM引入了Compaction操作解決這個問題，Compaction操作有2種作用：

• 控制LSM層次形狀

  一般的LSM形狀都是層次越低，資料量越大（倍數關係），目的是為了提升讀效能。

  通常儲存系統的資料訪問都有局部性，大量的訪問都集中在少部分資料上，這也是緩衝系統能有效工作的基本前提。在LSM儲存結構中，如果把訪問頻率高的資料儘可能放在較高的層次上，存放在快速存放裝置中（例如NVM、DRAM），而把訪問頻率低的資料放在較低層次中，存放在廉價慢速存放裝置中。這就是X-Engine的冷熱分層概念。

  

• 合并資料

  Compaction操作不斷的把相鄰層次的資料合併，並寫入更低層次。合并的過程實際上是把要合并的相鄰兩層或多層的資料讀出來，按key排序，相同的key如果有多個版本，只保留新的版本（比當前正在執行的活躍事務中最小版本號碼新），丟掉舊版本資料，然後寫入新的層，這個操作非常耗費資源。

  合并資料除了考慮冷熱分層以外，還需要考慮其他維度，例如資料的更新頻率，大量的多版本資料在查詢的時候會浪費更多的I/O和CPU，因此需要優先進行合并以減少記錄的版本數量。X-Engine綜合考慮了各種策略形成自己的Compaction調度機制。

高度最佳化的LSM

X-Engine的memory tables使用了無鎖跳錶（Locked-free SkipList），並發讀寫的效能較高。在持久化層如何?高效，就需要討論每層的細微結構。

• 資料群組織

  X-Engine的每層都劃分成固定大小的Extent，存放每個層次中的資料的一個連續片段（Key Range）。為了快速定位Extent，為每層Extents建立了一套索引（Meta Index），所有這些索引，加上所有的memory tables（active/immutable）一起組成了一個中繼資料樹（Metadata Tree），root節點為Metadata Snapshot，這個樹結構類似於B-Tree。

  

  X-Engine中除了當前的正在寫入的active memory tables以外，其他結構都是唯讀，不會被修改。給定某個時間點，例如LSN=1000，上圖中的Metadata Snapshot 1引用到的結構即包含了LSN=1000時的所有的資料的快照，因此這個結構被稱為Snapshot。

  即便是Metadata結構本身，也是一旦產生就不會被修改。所有的讀請求都是以Snapshot為入口，這是X-Engine實現Snapshot層級隔離的基礎。前文提到，隨著資料寫入，累積資料越多，會執行Compaction操作、凍結memory tables等，這些操作都是用Copy-on-write實現，即每次都將修改產生的結果寫入新的Extent，然後產生新的Meta Index結構，最終產生新的Metadata Snapshot。

  例如執行一次Compaction操作會產生新的Metadata Snapshot，如下圖所示。

  

  可以看到Metadata Snapshot 2相對於Metadata Snapshot 1並沒有太多的變化，僅僅修改了發生變更的一些葉子節點和索引節點。

  說明

  這個技術頗有些類似 B-trees, shadowing, and clones，如果您閱讀那篇論文，會對理解這個過程有所協助。

• 交易處理

  得益於LSM的輕量化寫機制，寫入操作固然是其明顯的優勢，但是交易處理不只是把更新的資料寫入系統那麼簡單，還要保證ACID（原子性、一致性、隔離性、持久性），涉及到一整套複雜的流程。X-Engine將整個交易處理過程分為兩個階段：

  1. 讀寫階段

     校正事務的衝突（寫寫衝突、讀寫衝突），判斷事務是否可以執行、復原重試或者等鎖。如果事務衝突校正通過，則把修改的所有資料寫入Transaction Buffer。

  2. 提交階段

     寫WAL、寫記憶體表，以及提交並返回使用者結果，這裡面既有I/O操作（寫日誌、返回訊息），也有CPU操作（拷貝日誌、寫記憶體表）。

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

  X-Engine為了進一步提升交易處理的吞吐，使用流水線技術，把提交階段分為4個獨立的更精細的階段：

  1. 拷貝日誌到緩衝區（Log Buffer）

  2. 日誌落盤（Log Flush）

  3. 寫記憶體表（Write memory table）

  4. 提交返回（Commit）

  事務到了提交階段，可以自由選擇執行流水線中任意一個階段，只要流水線任務的大小劃分得當，就能充分並行起來，流水線處於接近滿載狀態。另外這裡利用的是交易處理的線程，而非後台線程，每個線程在執行時，選擇流水線中的一個階段執行任務，或者空閑後處理其他請求，沒有等待，也無需切換，充分利用了每個線程的能力。

  

• 讀操作

  LSM處理多版本資料的方式是新版本資料記錄會追加在老版本資料後面，從物理上看，一條記錄的不同版本可能存放在不同的層，在查詢的時候需要找到合適的版本（根據交易隔離等級定義的可見度規則），一般查詢都是尋找最新的資料，總是由最高的層次往低層次尋找。

  對於單條記錄的尋找而言，一旦找到便可以終止，如果記錄在比較高的層次，例如memory tables，很快便可以返回；如果記錄已經落入了很低的層次，那就得逐層尋找，也許Bloom Filter可以跳過某些層次加快這個旅程，但畢竟還是有很多的I/O操作。X-Engine針對單記錄查詢引入了Row Cache，在所有持久化的層次的資料之上做了一個緩衝，在memory tables中沒有命中的單行查詢，在Row Cache之中也會被捕獲。Row Cache需要保證緩衝了所有持久化層次中最新版本的記錄，而這個記錄是可能發生變化的，例如每次flush將唯讀memory tables寫入持久化層次時，就需要恰當的更新Row Cache中的緩衝記錄，這個操作比較微妙，需要精心的設計。

  對於範圍掃描而言，因為沒法確定一個範圍的key在哪個層次中有資料，只能掃描所有的層次做合并之後才能返回最終的結果。X-Engine採用了一系列的手段，例如SuRF（SIGMOD'18 best paper）提供range scan filter減少掃描層數、非同步I/O與預取。

  

  讀操作中最核心的是緩衝設計，Row Cache負責單行查詢，Block Cache負責Row Cache的漏網之魚，也用來進行範圍掃描。由於LSM的Compaction操作會一次更新大量的Data Block，導致Block Cache中大量資料短時間內失效，導致效能的急劇抖動，因此X-Engine做了很多的最佳化：

  • 減少Compaction的粒度。

  • 減少Compaction過程中改動的資料。

  • Compaction過程中針對已有的快取資料做定點更新。

• Compaction

  Compaction操作是比較重要的，需要把相鄰層次交叉的Key Range資料讀取合并，然後寫到新的位置。這是為前面簡單的寫入操作付出的代價。X-Engine為最佳化這個操作重新設計了儲存結構。

  

  如前文所述，X-Engine將每一層的資料劃分為固定大小的Extent，一個Extent相當於一個小而完整的排序字串表（SSTable），儲存了一個層次中的一個連續片段，連續片段又進一步劃分為一個個連續的更小的片段Data Block，相當於傳統資料庫中的Page，只不過Data Block是唯讀而且不定長的。

  

  回看並對比Metadata Snapshot 1和Metadata Snapshot 2，可以發現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

請參見X-Engine引擎使用須知。

後續發展

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

X-Engine作為儲存引擎，核心的價值還在於性價比，持續提升效能降低成本，是一個長期的根本目標，X-Engine還在Compaction調度、緩衝管理與最佳化、資料壓縮、交易處理等方向上進行深層次的探索。

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