為什么設(shè)計一個新的存儲引擎

X-Engine的誕生是為了應(yīng)對阿里內(nèi)部業(yè)務(wù)的挑戰(zhàn)，早在2010年，阿里內(nèi)部就大規(guī)模部署了MySQL數(shù)據(jù)庫，但是業(yè)務(wù)量的逐年爆炸式增長，數(shù)據(jù)庫面臨著極大的挑戰(zhàn)：

• 極高的并發(fā)事務(wù)處理能力（尤其是雙十一的流量突發(fā)式暴增）。

• 超大規(guī)模的數(shù)據(jù)存儲。

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

傳統(tǒng)數(shù)據(jù)庫架構(gòu)的性能已經(jīng)被仔細的研究過，數(shù)據(jù)庫領(lǐng)域的泰斗，圖靈獎得主Michael Stonebreaker就此寫過一篇論文 《OLTP Through the Looking Glass, and What We Found There》，指出傳統(tǒng)關(guān)系型數(shù)據(jù)庫，僅有不到10%的時間是在做真正有效的數(shù)據(jù)處理工作，剩下的時間都浪費在其它工作上，例如加鎖等待、緩沖管理、日志同步等。

造成這種現(xiàn)象的原因是近年來我們所依賴的硬件體系發(fā)生了巨大的變化，例如多核（眾核）CPU、新的處理器架構(gòu)（Cache/NUMA）、各種異構(gòu)計算設(shè)備（GPU/FPGA）等，而架構(gòu)在這些硬件之上的數(shù)據(jù)庫軟件卻沒有太大的改變，例如使用B-Tree索引的固定大小的數(shù)據(jù)頁（Page）、使用ARIES算法的事務(wù)處理與數(shù)據(jù)恢復(fù)機制、基于獨立鎖管理器的并發(fā)控制等，這些都是為了慢速磁盤而設(shè)計，很難發(fā)揮出現(xiàn)有硬件體系應(yīng)有的性能。

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

X-Engine架構(gòu)

全新架構(gòu)的X-Engine存儲引擎不僅可以無縫對接兼容MySQL（得益于MySQL Pluginable Storage Engine特性），同時X-Engine使用分層存儲架構(gòu)。

因為目標是面向大規(guī)模的海量數(shù)據(jù)存儲，提供高并發(fā)事務(wù)處理能力和降低存儲成本，在大部分大數(shù)據(jù)量場景下，數(shù)據(jù)被訪問的機會是不均等的，訪問頻繁的熱數(shù)據(jù)實際上占比很少，X-Engine根據(jù)數(shù)據(jù)訪問頻度的不同將數(shù)據(jù)劃分為多個層次，針對每個層次數(shù)據(jù)的訪問特點，設(shè)計對應(yīng)的存儲結(jié)構(gòu)，寫入合適的存儲設(shè)備。

X-Engine使用了LSM-Tree作為分層存儲的架構(gòu)基礎(chǔ)，并進行了重新設(shè)計：

• 熱數(shù)據(jù)層和數(shù)據(jù)更新使用內(nèi)存存儲，通過內(nèi)存數(shù)據(jù)庫技術(shù)（Lock-Free index structure/append only）提高事務(wù)處理的性能。

• 流水線事務(wù)處理機制，把事務(wù)處理的幾個階段并行起來，極大提升了吞吐。

• 訪問頻度低的數(shù)據(jù)逐漸淘汰或是合并到持久化的存儲層次中，并結(jié)合多層次的存儲設(shè)備（NVM/SSD/HDD）進行存儲。

• 對性能影響比較大的Compaction過程做了大量優(yōu)化：

  • 拆分數(shù)據(jù)存儲粒度，利用數(shù)據(jù)更新熱點較為集中的特征，盡可能的在合并過程中復(fù)用數(shù)據(jù)。

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

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

技術(shù)特點

• 利用FPGA硬件加速Compaction過程，使得系統(tǒng)上限進一步提升。這個技術(shù)屬首次將硬件加速技術(shù)應(yīng)用到在線事務(wù)處理數(shù)據(jù)庫存儲引擎中，相關(guān)論文 《FPGA-Accelerated Compactions for LSM-based Key Value Store》已經(jīng)被2020年的國際會議接收。

• 通過數(shù)據(jù)復(fù)用技術(shù)減少數(shù)據(jù)合并代價，同時減少緩存淘汰帶來的性能抖動。

• 使用多事務(wù)處理隊列和流水線處理技術(shù)，減少線程上下文切換代價，并計算每個階段任務(wù)量配比，使整個流水線充分流轉(zhuǎn)，極大提升事務(wù)處理性能。相對于其他類似架構(gòu)的存儲引擎（例如RocksDB），X-Engine的事務(wù)處理性能有10倍以上提升。

• X-Engine使用的Copy-on-write技術(shù)，避免原地更新數(shù)據(jù)頁，從而對只讀數(shù)據(jù)頁面進行編碼壓縮，相對于傳統(tǒng)存儲引擎（例如InnoDB），使用X-Engine可以將存儲空間降低至10%~50%。

• Bloom Filter快速判定數(shù)據(jù)是否存在，Surf Filter判斷范圍數(shù)據(jù)是否存在，Row Cache緩存熱點行，加速讀取性能。

LSM基本邏輯

LSM的本質(zhì)是所有寫入操作直接以追加的方式寫入內(nèi)存。每次寫到一定程度，即凍結(jié)為一層（Level），并寫入持久化存儲。所有寫入的行，都以主鍵（Key）排序好后存放，無論是在內(nèi)存中，還是持久化存儲中。在內(nèi)存中即為一個排序的內(nèi)存數(shù)據(jù)結(jié)構(gòu)（Skiplist、B-Tree等），在持久化存儲也作為一個只讀的全排序持久化存儲結(jié)構(gòu)。

普通的存儲系統(tǒng)若要支持事務(wù)處理，需要加入一個時間維度，為每個事務(wù)構(gòu)造出一個不受并發(fā)干擾的獨立視域。例如存儲引擎會對每個事務(wù)定序并賦予一個全局單調(diào)遞增的事務(wù)版本號（SN），每個事務(wù)中的記錄會存儲這個SN以判斷獨立事務(wù)之間的可見性，從而實現(xiàn)事務(wù)的隔離機制。

如果LSM存儲結(jié)構(gòu)持續(xù)寫入，不做其他的動作，那么最終會成為如下結(jié)構(gòu)。

這種結(jié)構(gòu)對于寫入是非常友好的，只要追加到最新的內(nèi)存表中即完成，為實現(xiàn)故障恢復(fù)，只需記錄Redo Log，因為新數(shù)據(jù)不會覆蓋舊版本，追加記錄會形成天然的多版本結(jié)構(gòu)。

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

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

• 控制LSM層次形狀

  一般的LSM形狀都是層次越低，數(shù)據(jù)量越大（倍數(shù)關(guān)系），目的是為了提升讀性能。

  通常存儲系統(tǒng)的數(shù)據(jù)訪問都有局部性，大量的訪問都集中在少部分數(shù)據(jù)上，這也是緩存系統(tǒng)能有效工作的基本前提。在LSM存儲結(jié)構(gòu)中，如果把訪問頻率高的數(shù)據(jù)盡可能放在較高的層次上，存放在快速存儲設(shè)備中（例如NVM、DRAM），而把訪問頻率低的數(shù)據(jù)放在較低層次中，存放在廉價慢速存儲設(shè)備中。這就是X-Engine的冷熱分層概念。

  

• 合并數(shù)據(jù)

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

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

高度優(yōu)化的LSM

X-Engine的memory tables使用了無鎖跳表（Locked-free SkipList），并發(fā)讀寫的性能較高。在持久化層如何實現(xiàn)高效，就需要討論每層的細微結(jié)構(gòu)。

• 數(shù)據(jù)組織

  X-Engine的每層都劃分成固定大小的Extent，存放每個層次中的數(shù)據(jù)的一個連續(xù)片段（Key Range）。為了快速定位Extent，為每層Extents建立了一套索引（Meta Index），所有這些索引，加上所有的memory tables（active/immutable）一起組成了一個元數(shù)據(jù)樹（Metadata Tree），root節(jié)點為Metadata Snapshot，這個樹結(jié)構(gòu)類似于B-Tree。

  

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

  即便是Metadata結(jié)構(gòu)本身，也是一旦生成就不會被修改。所有的讀請求都是以Snapshot為入口，這是X-Engine實現(xiàn)Snapshot級別隔離的基礎(chǔ)。前文說過隨著數(shù)據(jù)寫入，累積數(shù)據(jù)越多，會執(zhí)行Compaction操作、凍結(jié)memory tables等，這些操作都是用Copy-on-write實現(xiàn)，即每次都將修改產(chǎn)生的結(jié)果寫入新的Extent，然后生成新的Meta Index結(jié)構(gòu)，最終生成新的Metadata Snapshot。

  例如執(zhí)行一次Compaction操作會生成新的Metadata Snapshot，如下圖所示。

  

  可以看到Metadata Snapshot 2相對于Metadata Snapshot 1并沒有太多的變化，僅僅修改了發(fā)生變更的一些葉子節(jié)點和索引節(jié)點。

  說明

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

• 事務(wù)處理

  得益于LSM的輕量化寫機制，寫入操作固然是其明顯的優(yōu)勢，但是事務(wù)處理不只是把更新的數(shù)據(jù)寫入系統(tǒng)那么簡單，還要保證ACID（原子性、一致性、隔離性、持久性），涉及到一整套復(fù)雜的流程。X-Engine將整個事務(wù)處理過程分為兩個階段：

  1. 讀寫階段

     校驗事務(wù)的沖突（寫寫沖突、讀寫沖突），判斷事務(wù)是否可以執(zhí)行、回滾重試或者等鎖。如果事務(wù)沖突校驗通過，則把修改的所有數(shù)據(jù)寫入Transaction Buffer。

  2. 提交階段

     寫WAL、寫內(nèi)存表，以及提交并返回用戶結(jié)果，這里面既有I/O操作（寫日志、返回消息），也有CPU操作（拷貝日志、寫內(nèi)存表）。

  為了提高事務(wù)處理吞吐，系統(tǒng)內(nèi)會有大量事務(wù)并發(fā)執(zhí)行，單個I/O操作比較昂貴，大部分存儲引擎會傾向于聚集一批事務(wù)一起提交，稱為Group Commit，能夠合并I/O操作。但是一組事務(wù)提交的過程中，還是有大量等待過程的，例如寫入日志到磁盤過程中，除了等待落盤無所事事。

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

  1. 拷貝日志到緩沖區(qū)（Log Buffer）

  2. 日志落盤（Log Flush）

  3. 寫內(nèi)存表（Write memory table）

  4. 提交返回（Commit）

  事務(wù)到了提交階段，可以自由選擇執(zhí)行流水線中任意一個階段，只要流水線任務(wù)的大小劃分得當，就能充分并行起來，流水線處于接近滿載狀態(tài)。另外這里利用的是事務(wù)處理的線程，而非后臺線程，每個線程在執(zhí)行的時候，選擇流水線中的一個階段執(zhí)行任務(wù)，或者空閑后處理其他請求，沒有等待，也無需切換，充分利用了每個線程的能力。

  

• 讀操作

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

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

  對于范圍掃描而言，因為沒法確定一個范圍的key在哪個層次中有數(shù)據(jù)，只能掃描所有的層次做合并之后才能返回最終的結(jié)果。X-Engine采用了一系列的手段，例如SuRF（SIGMOD'18 best paper）提供range scan filter減少掃描層數(shù)、異步I/O與預(yù)取。

  

  讀操作中最核心的是緩存設(shè)計，Row Cache負責(zé)單行查詢，Block Cache負責(zé)Row Cache的漏網(wǎng)之魚，也用來進行范圍掃描。由于LSM的Compaction操作會一次更新大量的Data Block，導(dǎo)致Block Cache中大量數(shù)據(jù)短時間內(nèi)失效，導(dǎo)致性能的急劇抖動，因此X-Engine做了很多的優(yōu)化：

  • 減少Compaction的粒度。

  • 減少Compaction過程中改動的數(shù)據(jù)。

  • Compaction過程中針對已有的緩存數(shù)據(jù)做定點更新。

• Compaction

  Compaction操作是比較重要的，需要把相鄰層次交叉的Key Range數(shù)據(jù)讀取合并，然后寫到新的位置。這是為前面簡單的寫入操作付出的代價。X-Engine為優(yōu)化這個操作重新設(shè)計了存儲結(jié)構(gòu)。

  

  如前文所述，X-Engine將每一層的數(shù)據(jù)劃分為固定大小的Extent，一個Extent相當于一個小而完整的排序字符串表（SSTable），存儲了一個層次中的一個連續(xù)片段，連續(xù)片段又進一步劃分為一個個連續(xù)的更小的片段Data Block，相當于傳統(tǒng)數(shù)據(jù)庫中的Page，只不過Data Block是只讀而且不定長的。

  

  回看并對比Metadata Snapshot 1和Metadata Snapshot 2，可以發(fā)現(xiàn)Extent的設(shè)計意圖。每次修改只需要修改少部分有交疊的數(shù)據(jù)，以及涉及到的Meta Index節(jié)點。兩個Metadata Snapshot結(jié)構(gòu)實際上共用了大量的數(shù)據(jù)結(jié)構(gòu)，這被稱為數(shù)據(jù)復(fù)用技術(shù)（Data Reuse），而Extent大小正是影響數(shù)據(jù)復(fù)用率的關(guān)鍵，Extent作為一個完整的被復(fù)用的物理結(jié)構(gòu)，需要盡可能的小，這樣與其他Extent數(shù)據(jù)交叉點會變少，但又不能非常小，否則需要索引過多，管理成本太大。

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

  一個典型的數(shù)據(jù)復(fù)用在Compaction中的過程可以參見下圖。

  

  可以看出數(shù)據(jù)復(fù)用的過程是在逐行迭代的過程中完成的，不過這種精細的數(shù)據(jù)復(fù)用帶來另一個副作用，即數(shù)據(jù)的碎片化，所以在實際操作的過程中也需要根據(jù)實際情況進行分析。

  數(shù)據(jù)復(fù)用不僅給Compaction操作本身帶來好處，降低操作過程中的I/O與CPU消耗，更對系統(tǒng)的綜合性能產(chǎn)生一系列的影響。例如Compaction過程中數(shù)據(jù)不用完全重寫，大大降低了寫入時空間的增大；大部分數(shù)據(jù)保持原樣，數(shù)據(jù)緩存不會因為數(shù)據(jù)更新而失效，減少合并過程中因緩存失效帶來的讀性能抖動。

  實際上，優(yōu)化Compaction的過程只是X-Engine工作的一部分，更重要的是優(yōu)化Compaction調(diào)度的策略，選什么樣的Extent、定義compaction任務(wù)的粒度、執(zhí)行的優(yōu)先級等，都會對整個系統(tǒng)性能產(chǎn)生影響，可惜并不存在什么完美的策略，X-Engine積累了一些經(jīng)驗，定義了很多規(guī)則，而探索更合理的調(diào)度策略是未來一個重要方向。

適用場景

請參見X-Engine最佳實踐。

如何使用X-Engine

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

后續(xù)發(fā)展

作為MySQL的存儲引擎，持續(xù)地提升MySQL系統(tǒng)的兼容能力是一個重要目標，后續(xù)會根據(jù)需求的迫切程度逐步加強原本取消的一些功能，例如外鍵，以及對一些數(shù)據(jù)結(jié)構(gòu)、索引類型的支持。

X-Engine作為存儲引擎，核心的價值還在于性價比，持續(xù)提升性能降低成本，是一個長期的根本目標，X-Engine還在Compaction調(diào)度、緩存管理與優(yōu)化、數(shù)據(jù)壓縮、事務(wù)處理等方向上進行深層次的探索。