如何基于LSM-tree架構實作一寫多讀

一  前言

PolarDB是阿裡巴巴自研的新一代雲原生關系型資料庫，在存儲計算分離架構下，利用了軟硬體結合的優勢，為使用者提供具備極緻彈性、海量存儲、高性能、低成本的資料庫服務。X-Engine是阿裡巴巴自研的新一代存儲引擎，作為AliSQL的核心引擎之一已廣泛用于阿裡巴巴集團核心業務，包括交易曆史庫，釘釘曆史庫，圖檔空間等。X-Engine基于LSM-tree架構，其核心特征是資料以追加寫方式寫入，高壓縮低成本，适用于寫多讀少，有低成本訴求的業務場景。傳統MySQL基于binlog複制的主備架構有它的局限性，包括存儲空間有限，備份恢複慢，主備複制延遲等問題，為了解決使用者對于雲上RDS(X-Engine)大容量存儲，以及彈性伸縮的訴求，PolarDB推出了曆史庫(基于X-Engine引擎的一寫多讀)産品，支援實體複制，提供一寫多讀的能力，目前已經在阿裡雲官網售賣。本文主要闡述如何基于LSM-tree結構的存儲引擎實作資料庫的一寫多讀能力。

二  LSM-tree資料庫引擎

LSM-Tree全稱是Log Structured Merge Tree，是一種分層，有序，面向磁盤設計的資料結構，其核心思想是利用磁盤批量的順序寫要比随機寫性能高的特點，将所有更新操作都轉化為追加寫方式，提升寫入吞吐。LSM-tree類的存儲引擎最早源于Google三駕馬車之一的BigTable的存儲引擎以及它的開源實作LevelDB。LSM-tree存儲引擎有幾個特點，首先增量資料像日志一樣，通過追加方式寫入，順序落盤；其次，資料按照key來進行有序組織，這樣在記憶體和磁盤中會形成一顆顆小的“有序樹”；最後，各個“有序樹”可以進行歸并，将記憶體中的增量資料遷移到磁盤上，磁盤上的多個“有序樹”可以進行歸并，優化樹的形狀，整個LSM-tree是一個有序的索引組織結構。

在雲原生資料庫時代，一寫多讀技術已被廣泛應用于生産環境中，主要雲産商都有其标杆産品，典型代表包括亞馬遜的Aurora，阿裡雲的PolarDB以及微軟雲的Socrates。它的核心思想是計算存儲分離，将有狀态的資料和日志下推到分布式存儲，計算節點無狀态，多個計算節點共享一份資料，資料庫可以低成本快速擴充讀性能。Aurora是這個領域的開山鼻祖，實作了業内第一個一寫多讀的資料庫，計算節點Scale up，存儲節點Scale out，并将日志子產品下推到存儲層，計算節點之間，計算與存儲節點之間傳輸redo日志，計算節點基于Quorum協定寫多副本保證可靠性，存儲層提供多版本頁服務。PolarDB與Aurora類似，也采用了存儲計算分離架構，與Aurora相比，PolarDB它自己的特色，存儲基座是一個通用的分布式檔案系統，大量采用OS-bypass和zero-copy技術，存儲的多副本一緻性由ParallelRaft協定保證。PolarDB計算節點與存儲節點同時傳輸資料頁和redo日志，計算節點與計算節點之間隻傳遞位點資訊。與Aurora的“日志即資料庫”理念一樣，Socrates的節點之間隻傳輸redo日志，也實作了多版本頁服務，它的特點是将資料庫存儲層的持久性與可用性分開，抽象出一套日志服務。整個資料庫分為3層，一層計算服務，一層page server服務和一層日志服務，這樣設計的好處是可以分層進行優化，提供更靈活和細粒度的控制。

雖然Aurora，PolarDB和Socrates在設計上各有特點，但它們都共同踐行了存儲計算分離思想，資料庫層面提供一寫多讀的能力。深入到存儲引擎這一層來說，這幾個産品都是基于B+tree的存儲引擎，如果基于LSM-tree存儲引擎來做呢？LSM-tree有它自己的特點，追加順序寫，資料分層存儲，磁盤上資料塊隻讀更有利于壓縮。X-Engine引擎雲上産品RDS(X-Engine)已經充分發揮了LSM-tree高壓縮低成本特點，同樣的資料量，存儲空間隻占到RDS(InnoDB)的1/3甚至更少，RDS(X-Engine)傳統的主備架構，依然面臨着主備複制延遲大，備份恢複慢等問題。基于LSM-tree引擎實作一寫多讀，不僅計算資源和存儲資源解耦，多個節點共享一份資料還能進一步壓縮存儲成本。

基于LSM-tree引擎實作一寫多讀面臨着與B+tree引擎不一樣的技術挑戰，首先是存儲引擎日志不一樣，LSM-tree引擎是雙日志流，需要解決雙日志流的實體複制問題；其次是資料組織方式不一樣，LSM-tree引擎采用分層存儲，追加寫入新資料，需要解決多個計算節點一緻性實體快照以及Compation問題。最後，作為資料庫引擎，還需要解決一寫多讀模式下DDL的實體複制問題。同時，為了産品化，充分發揮B+tree引擎和LSM-tree引擎的各自優勢，還面臨着新的挑戰，即如何在一個資料庫産品中同時實作兩個存儲引擎(InnoDB,X-Engine)的一寫多讀。

三  LSM-tree引擎一寫多讀的關鍵技術

1  PolarDB整體架構

PolarDB支援X-Engine引擎後，X-Engine引擎與InnoDB引擎仍然獨立存在。兩個引擎各自接收寫入請求，資料和日志均存儲在底層的分布式存儲上，其中idb檔案表示的是InnoDB的資料檔案，sst檔案表示的是X-Engine的資料檔案。這裡最主要的點在于InnoDB與XEngine共享一份redo日志，X-Engine寫入時，将wal日志嵌入到InnoDB的redo中，Replica節點和Standby節點在解析redo日志後，分發給InnoDB引擎和XEngine引擎分别回放進行同步。

PolarDB(X-Engine)架構圖

X-Engine引擎架構

X-Engine引擎采用LSM-tree結構，資料以追加寫的方式寫入記憶體，并周期性物化到磁盤上，記憶體中資料以memtable形式存在，包括一個活躍的active memtable和多個靜态的immutable。磁盤上資料分層存儲，總共包括3層，L0，L1和L2，每一層資料按塊有序組織。X-Engine最小空間配置設定機關是一個extent，預設是2M，每個extent包含若幹個block，預設是16k。資料記錄緊湊存儲在block中，由于追加寫特點，磁盤上的資料塊都是隻讀的，是以X-Engine引擎可以預設對block進行壓縮，另外block中的記錄還會進行字首編碼，綜合這些使得X-Engine的存儲空間相對于InnoDB引擎隻有1/3，部分場景(比如圖檔空間)甚至能壓縮到1/7。有利就有弊，追加寫帶來了寫入優勢，對于曆史版本資料需要通過Compaction任務來進行回收。有關X-Engine的核心技術可以參考發表在Sigmod19的論文，《X-Engine: An Optimized Storage Engine for Large-scale E-commerce Transaction Processing》

X-Engine整體架構

2  實體複制架構

實體複制的核心是通過引擎自身的日志來完成複制，避免寫額外的日志帶來的成本和性能損失。MySQL原生的複制架構是通過binlog日志進行複制，寫事務需要同時寫引擎日志和binlog日志，這帶來的問題是一方面單個事務在關鍵寫路徑上需要寫兩份日志，寫性能受制于二階段送出和binlog的串行寫入，另一方面binlog複制是邏輯複制，複制延遲問題也使得複制架構的高可用，以及隻讀庫的讀服務能力大打折扣，尤其是在做DDL操作時，這個延遲會進一步放大。

在InnoDB中有redo和undo兩種日志，undo日志可以了解為一種特殊的“data”，是以實際上InnoDB的所有操作都能通過redo日志來保證持久性。是以，在進行複制時，隻需要在主從節點複制redo日志即可。X-Engine引擎包含兩種日志，一種是wal日志(WriteAheadLog)，用于記錄前台的事務的操作；另一種是Slog(StorageLog)，用于記錄LSM-tree形狀變化的操作，主要指Compaction/Flush等。wal日志保證了前台事務的原子性和持久性，Slog則保證了X-Engine内部LSM-tree形狀變化的原子性和持久性，這兩個日志缺一不可，都需要複制同步。

共享存儲下的實體複制

Primary-Replica實體複制架構

LSM-tree引擎一寫多讀的能力是對PolarDB進行功能增強，展現在架構層面就是充分利用已有的複制鍊路，包括Primary->Replica傳遞日志資訊鍊路和Replica->Primary傳遞協同控制資訊鍊路。InnoDB事務由若幹個mtr(Mini-Transaction)組成，寫入redo日志的最小機關是mtr。我們在Innodb的redo日志新增一種日志類型用于表示X-Engine日志，将X-Engine的事務内容作為一個mtr事務寫入到redo日志中，這樣Innodb的redo和X-Engine的wal日志能共享一條複制鍊路。由于Primary和Replica共享一份日志和資料，Dump_thread隻需要傳遞位點資訊，由Replica根據位點資訊去讀redo日志。Replica解析日志，根據日志類型來分發日志給不同的回放引擎，這種架構使得所有複制架構與之前的複制保持一緻，隻需要新增解析、分發X-Engine日志邏輯，新增X-Engine的回放引擎，充分與InnoDB引擎解耦。

由于LSM-tree追加寫特點，記憶體memtable中資料會周期性的Flush到磁盤，為了保證Primary和Replica讀到一緻性實體視圖，Primary和Replica需要同步SwitchMemtable，需要新增一條SwitchMemtable控制日志來協調。redo日志持久化後，Primary通過日志方式将位點資訊主動推送給Replica，以便Replica及時回放最新的日志，減少同步延遲。對于Slog日志，既可以采用類似于redo的日志方式來主動“push”方式來同步位點，也可以采用Replica主動“pull”的方式來同步。SLog是背景日志，相對于前台事務回放實時性要求不高，不必要将redo位點和SLog位點都放在一條複制鍊路增加複雜性，是以采用了Replica的“pull”的方式來同步SLog。

災備叢集間的實體複制

Primary-Standby實體複制架構

與共享叢集複制不同，災備叢集有獨立一份存儲，Primary—>Standby需要傳遞完整的redo日志。Stanby與Replica差別在于日志來源不同，Replica從共享存儲上擷取日志，Standy從複制鍊路擷取日志，其它解析和回放路徑是一樣的。是否将Slog日志作為redo日志一部分傳遞給Standby是一個問題，Slog日志由Flush/Compaction動作産生，記錄的是LSM-tree形狀的實體變化。如果也通過redo日志鍊路同步給Standby，會帶來一些複雜性，一方面是X-Engine内部寫日志的方式需要改動，需要新增新增檔案操作相關的實體日志來確定主從實體結構一緻，故障恢複的邏輯也需要适配；另一方面，Slog作為背景任務的記錄檔，意味着複制鍊路上的所有角色都需要同構；如果放棄同構，那麼Standy節點可能會觸發Flush/Compaction任務寫日志，這與實體複制中，隻允許Primary寫日志是相違背的。實際上，Slog同步寫入到redo log中不是必須的，因為Slog是背景日志，這個動作不及時回放并不影響資料視圖的正确性，是以，複制鍊路上隻包含redo日志(X-Engine wal日志和InnoDB redo日志)，Standby自己控制Flush/Compaction産生Slog日志，這樣Standby也不必與Primary節點實體同構，整個架構與現有體系相比對，同時也更加靈活。

3  并行實體複制加速

X-Engine的事務包括兩個階段，第一個階段是讀寫階段，這個階段事務操作資料會緩存在事務上下文中，第二階段是送出階段，将操作資料寫入到redo日志持久化，随後寫到memtable中供讀操作通路。對于Standby/Replica節點而言，回放過程與Primary節點類似，從redo中解析到事務日志，然後将事務回放到memtable中。事務之間不存在沖突，通過Sequence版本号來确定可見性。并行回放的粒度是事務，需要處理的一個關鍵問題就是可見性問題。事務串行回放時，Sequence版本号都是連續遞增的，事務可見性不存在問題。在并行回放場景下，我們仍然需要保序，通過引入“滑動視窗”機制，隻有連續一段沒有空洞的Sequence才能推進全局的Sequence版本号，這個全局Sequence用于讀操作擷取快照。

并行複制架構

一寫多讀架構下，為了保證同一資料庫執行個體的Primary、Replica、Standby三個角色的記憶體鏡像完全一緻，新增了一種SwitchMemtableLog，該Log Record在RW的switch_memtable過程中産生，是以RO、Standby不再主動觸發switch_memtable操作，而是通過從RW上同步SwitchMemtableLog進行switch_memtable。SwitchMemtable操作是一個全局的屏障點，以防止目前可寫memtable在插入過程中switch進而導緻資料錯亂。另外，對于2PC事務，并發控制也需要做适配。一個2PC事務除了資料本身的日志，還包括BeginPrepare、EndPrepare、Commit、Rollback四類日志，寫入過程中保證BeginPrepare和EndPrepare寫入到一個WriteBatch中并順序落盤，是以可以保證同一個事務的Prepare日志都會被解析到一個ReplayTask中。在并行回放過程中，由于無法保證Commit或Rollback日志一定後于Prepare日志被回放，是以如果Commit、Rollback日志先于Prepare日志被回放，那麼在全局的recovered_transaction_map中插入一個key對xid的空事務，對應的事務狀态為Commit或Rollback；随後Prepare日志完成回放時，如果發現recovered_transaction_map中已經存在對應的事務，那麼可以根據事務的狀态來決定直接送出事務還是丢棄事務。

對于B+Tree的實體複制，LSM-tree的實體複制并不是真正的“實體”複制。因為B+Tree傳遞的redo的内容是資料頁面的修改，而LSM-tree傳遞的redo内容是KeyValue值。這帶來的結果是，B+tree實體複制可以基于資料頁粒度做并發回放，而LSM-tree的實體複制是基于事務粒度的并發回放。B+tree并發回放有它自身的複雜性，比如需要解決系統頁回放與普通資料頁回放先後順序問題，并且還需要解決同一個mtr中多個資料頁并發回放可能導緻的實體視圖不一緻問題。LSM-tree需要解決多個節點在同樣位置SwitchMemtable，以及2PC事務回放等問題。

4  MVCC(多版本并發控制)

實體複制技術解決了資料同步的問題，為存儲計算分離打下了基礎。為了實作彈性，動态升降配，增删隻讀節點的能力，需要隻讀節點具備一緻性讀的能力，另外RW節點和RO節點共享一份資料，曆史版本回收也是必需要考慮的問題。

一緻性讀

X-Engine提供快照讀的能力，通過多版本機制來實作讀寫不互斥效果。從上述的X-Engine架構圖可以看到，X-Engine的資料實際上包括了記憶體和磁盤兩部分，不同于InnoDB引擎記憶體中page是磁盤上page的緩存，X-Engine中記憶體資料與磁盤資料完全異構，一份“快照”需要對應的是記憶體+磁盤資料。X-Engine采用追加寫方式，新資料進來會産生新的memtable，背景任務做flush/compaction任務也會産生新的extent。那麼如何擷取一緻性視圖呢？X-Engine内部實際上是通過MetaSnapshot+Snapshot來管理，首先每個MetaSnapshot對應一組memtable和L0，L1, L2的extents，這樣在實體上确定了資料範圍，然後通過Snapshot來處理行級版本的可見性，這裡的Snapshot實際上就是一個事務送出序列号Sequence。不同于InnoDB事務編号采用開始序，需要通過活躍事務視圖來判斷記錄的可見性；X-Engine事務采用送出序，每條記錄有一個唯一遞增序列号Sequence，判斷行級版本的可見性隻需要比較Sequence即可。在一寫多讀的模式下，Replica節點與Primary節點共享一份磁盤資料，而磁盤資料是有記憶體中資料定期dump出來的，是以需要保證Primary和Replica節點有相同的切memtable位點，進而保證資料視圖的一緻性。

一寫多讀下的Compaction

在一寫多讀場景下，Replica可以通過類似于Primary的快照機制來實作快照讀，需要處理的問題是曆史版本回收問題。曆史版本的回收，依賴于Compaction任務來完成，這裡的回收包括兩部分，一部分MetaSnapshot的回收，主要确認哪些memtable和extents可以被實體回收掉，另一部分是行級多版本回收，這裡主要是确認哪些曆史版本行可以被回收掉。對于MetaSnapshot的回收，Primary會收集所有Replica節點上的最小不再使用的MetaSnapshot版本号，X-Engine引擎的每個索引都是一個LSM-tree，是以彙報MetaSnaphot版本号是索引粒度的。Primary收集完MetaSnapshot版本号，計算最小可以回收的MetaSnapshot進行資源回收操作，回收操作以Slog日志的方式同步給Replica節點。Replica節點在回放日志進行資源回收時，需要将記憶體和磁盤資源分開，記憶體資源在各個節點是獨立的，磁盤資源是共享的，是以Replica節點的記憶體資源可以獨立釋放，而磁盤資源則統一由Primary節點來釋放。對于行級多版本的回收，同樣需要由Primary節點收集所有Replica節點最小序列号Sequence，由Primary節點通過Compaction任務來消除。這塊彙報鍊路複用PolarDB的ACK鍊路，隻是新增了X-Engine的彙報資訊。

5  DDL的實體複制如何實作

實體複制相對于邏輯複制一個關鍵優勢在于DDL，對于DDL而言，邏輯複制可以簡單了解為複制SQL語句，DDL在從庫上會重新再執行一遍。邏輯複制對于比較重的DDL操作，比如Alter table影響非常大，一個Alter變更操作在主庫執行需要半小時，那麼複制到從庫也需要再執行半小時，那麼主從延遲最大可能就會是1個小時，這個延遲對隻讀庫提供讀服務産生嚴重影響。

Server層複制

DDL操作同時涉及到Server層和引擎層，包括字典，緩存以及資料。最基礎的DDL操作，比如

Create/Drop操作，在一寫多讀架構下，要考慮資料與資料字典，資料與字典緩存一緻性等問題。一寫多讀的基礎是實體複制，實體複制日志隻在引擎層流動，不涉及到Server層，是以需要新增日志來解決DDL操作導緻的不一緻問題。我們新增了meta資訊變更的日志，并作為redo日志的一部分同步給從節點，這個meta資訊變更日志主要包括兩部分内容，一個是字典同步，主要是同步MDL鎖，確定Primary/Replica節點字典一緻；另一個是字典緩存同步，Replica上的記憶體是獨立的，Server層緩存的字典資訊也需要更新，是以要新增日志來處理，比如Drop Table/Drop db/Upate function/Upate precedure等操作。另外，還需要同步失效Replica的QueryCache，避免使用錯誤的查詢緩存。

引擎層複制

X-Engine引擎與InnoDB引擎一樣是索引組織表，在X-Engine内部，每個索引都是一個LSM-tree結構，内部稱為Subtable，所有寫入都是在Subtable中進行，Subtable的生命周期與DDL操作緊密相關。使用者發起建表動作會産生Subtable，這個是實體LSM-tree結構的載體，然後才能有後續的DML操作；同樣的，使用者發起删表動作後，所有這個Subtable的DML操作都應該執行完畢。Create/Drop Table操作涉及到索引結構的産生和消亡，會同時産生redo控制日志和SLog日志，在回放時，需要解決redo控制日志和SLog日志回放的時序問題。這裡我們将對應Subtable的redo日志的LSN位點持久化到SLog中，作為一個同步位點，Replica回放時，兩個回放鍊路做協調即可，redo日志記錄的是前台操作，Slog記錄的是背景操作，是以兩個鍊路做協同時，需要盡量避免redo複制鍊路等待Slog複制鍊路。比如，對于Create操作，回放Slog時，需要等待對應的redo日志的LSN位點回放完畢才推進；對于DROP操作，回放SLog也需要協同等待，避免回放前台事務找不到Subtable。

OnlineDDL複制技術

對于Alter Table操作，X-Engine實作了一套OnlineDDL機制，詳細實作原理可以參考核心月報。在一寫多讀架構下，X-Engine引擎在處理這類Alter操作時采用了實體複制，實際上對于Replica而言，由于是同一份資料，并不需要重新生成實體extent，隻需要同步元資訊即可。對于Standby節點，需要通過實體extent複制來重新建構索引。DDL複制時，實際上包含了基線和增量部分。DDL複制充分利用了X-Engine的分層存儲以及LSM-tree結構追加寫特點，在擷取快照後，利用快照直接建構L2作為基線資料，這部分資料以extent塊複制形式，通過redo通道傳遞給Standby，而增量資料則與普通的DML事務一樣，是以整個操作都是通過實體複制進行，大大提高了複制效率。這裡需要限制的僅僅是在Alter操作過程中，禁止做到L2的compaction即可。整個OnlineDDL過程與InnoDB的OnlineDDL流程類似，也是包括3個階段，prepare階段，build階段和commit階段，其中prepare階段需要擷取快照，commit階段中繼資料生效，需要通過MDL鎖來確定字典一緻。與基于B+tree的OnlineDDL複制相比，基線部分，B+tree索引複制的是實體頁，而LSM-tree複制的是實體extent；增量部分B+tree索引是通過記增量日志，回放增量日志到資料頁寫redo日志進行同步，LSM-tree則是通過DML前台操作寫redo的方式同步。

OnlineDDL複制

6  雙引擎技術

Checkpoint位點推進

通過wal-in-redo技術，我們将X-Engine的wal日志嵌入到了InnoDB的redo中，首先要處理的一個問題就是redo日志的回收問題。日志回收首先涉及到一個位點問題，融合進redo日志後，X-Engine内部将RecoveryPoint定義為<lsn, Sequence>，lsn表示redo日志的位點，Sequence為對應的X-Engine的事務的版本号。Redo日志回收與Checkpoint(檢查點)強相關，確定Checkpoint位點及時推進是需要考慮的問題，否則redo日志的堆積一方面影響磁盤空間，另一方面也影響恢複速度。這裡有一個基本的原則是，Checkpoint=min(innodb-ckpt-lsn, xengine-ckpt-lsn)，xengine-ckpt-lsn就是來源于X-Engine的RecoveryPoint，確定任何引擎有記憶體資料沒有落盤時，對應的redo日志不能被清理。為了避免X-Engine的checkpoint推進影響整體位點推進，内部會確定xengine-ckpt-lsn與全局的redo-lsn保持一定的閥值，超過閥值則會強制将memtable落盤，推進檢查點。

資料字典與DDL

X-Engine作為一個資料庫引擎有自己獨立的字典，InnoDB也有自己的字典，兩份字典在一個系統裡面肯定會存在問題。為了解決問題，這裡有兩種思路，一是X-Engine仍然保留自己的資料字典，在做DDL時，通過2PC事務來保證一緻性，這帶來的問題是需要有協調者。一般情況下，MySQL的協調者是binlog日志，在binlog關閉時是tclog日志。顯然，從功能和性能角度，我們都不會強依賴binlog日志。我們采用了另外一種思路，X-Engine不再用自身引擎存儲中繼資料，所有中繼資料均通過InnoDB引擎持久化，X-Engine中繼資料實際上是InnoDB字典的一份緩存，那麼在做DDL變更時，中繼資料部分實際上隻涉及InnoDB引擎，通過事務能保證DDL的原子性。

通過中繼資料歸一化我們解決了中繼資料的原子性問題，但X-Engine資料和InnoDB中繼資料如何保證一緻也是個問題。比如一個DDL操作，alter table xxx engine = xengine，這個DDL是将innodb表轉為xengine表，由于表結構變更是Innodb字典修改，資料是在修改X-Engine，是一個跨引擎事務，跨引擎事務需要通過協調者保證一緻性。為了避免引入binlog作為協調者依賴，tclog作為協調者沒有經過大規模生産環境驗證，我們選擇了另外一種處理方式，具體來說，在涉及跨引擎事務時，優先送出X-Engine事務，然後再送出InnoDB事務。對于DDL來說，就是“先資料，後中繼資料”，中繼資料送出了，才真正表示這個DDL完成。如果中途失敗，則結合“延遲删除”的機制，來保證垃圾資料能被最終清理掉，通過一個背景任務來周期性的對比X-Engine資料與InnoDB的字典，以InnoDB字典為準，結合X-Engine記憶體元資訊，确認這部分資料是否有用。

CrashRecovery

X-Engine與InnoDB引擎一樣是MySQL的一個插件，X-Enigne作為一個可選的插件，啟動順序在Innodb之後。每個引擎在恢複階段都需要通過redo日志來将資料庫恢複到當機前狀态。在雙引擎形态下，所有redo都在InnoDB中，那意味着無論是InnoDB引擎還是X-Engine引擎在讀取日志恢複時，都需要掃描整個redo日志，相當于整個恢複階段掃描了兩遍redo，這可能使得整個當機恢複過程非常長，降低了系統的可用性。為了解決這個問題，我們将X-Engine的恢複階段細分，并且調整引擎的啟動順序，在InnoDB啟動前，先完成X-Engine的初始化以及Slog等恢複過程，處于恢複redo的狀态。在InnoDB啟動時，根據類型将日志分發X-Engine引擎，整個流程與正常同步redo日志的過程一緻。當redo日志分發完畢，相當于InnoDB引擎和X-Engine引擎自身的當機恢複過程已經完成，然後走正常XA-Recovery和Post-Recovery階段即可，這個流程與之前保持一緻。

HA

PolarDB支援雙引擎後，整個升降級流程中都會嵌套有X-Engine引擎的邏輯，比如在Standby更新為RW前，需要確定X-Engine的回放流水線完成，并将未決的事務儲存起來，以便後續通過XA_Recovery繼續推進。RW降級為Standby的時候需要等待X-Engine寫流水線回放，同時如果還殘留有未決事務，需要在切換過程中将這部分未決事務周遊出來存入Recovered_transactions_集合供後續并發回放使用。

四  LSM-tree VS B+tree

上節我們較長的描述了基于LSM-tree架構的存儲引擎，實作一寫多讀所需要的關鍵技術，并結合PolarDB雙引擎介紹了一些工程實作。現在我們跳出來看看基于B+tree和基于LSM-tree兩種資料組織結構在實作技術上的對比。首先要回到一個基本點，B+tree是原地更新，而LSM-tree是追加寫，這帶來的差別就是B+tree的資料視圖在記憶體和外存一個緩存映射關系，而LSM-tree是一個疊加的關系。因而需要面對的技術問題也不同，B+tree需要刷髒，需要有double-write(在PolarFS支援16k原子寫後，消除了這個限制)；LSM-tree需要Compaction來回收曆史版本。在一寫多讀的模式下面臨的問題也不一樣，比如，B+tree引擎複制是單redo日志流，LSM-tree引擎是雙日志流；B+tree在處理并行回放時，可以做到更細粒度的頁級并發，但是需要處理SMO(SplitMergeOperation)問題，避免讀節點讀到“過去頁”或是“未來頁”。而LSM-tree是事務級别的并發，為了保證RW和RO節點“記憶體+磁盤”的一緻性視圖，需要RW和RO在相同的位點做Switch Memtable。下表以InnoDB引擎和X-Engine引擎為例，列出了一些關鍵的差別點。

五  LSM-tree引擎業内發展狀況

目前業内LSM-tree類型引擎比較熱的是Rocksdb，它的主要應用場景是作為一個KeyValue引擎使用。Facebook将Rocksdb引擎引入到了他們的MySQL8.0分支，類似于X-Engine之于AliSQL，主要服務于他們的使用者資料庫UDB業務，存儲使用者資料和消息資料，采用的仍然是基于binlog的主備複制結構，目前沒有看到有做存儲計算分離，以及一寫多讀的事情。另外，github上有一個rocksdb-cloud項目，将rocksdb作為底座，架在AWS等雲服務上提供NoSQL接口服務，相當于做了存儲計算分離，但并不支援實體複制和一寫多讀。在資料庫領域，阿裡巴巴的Oceanbase和谷歌的Spanner的底層存儲引擎都是基于LSM-tree結構，這顯示了LSM-tree作為資料庫引擎的可行性，這兩個資料庫都是基于Share-Nothing的架構。基于Share-Storage的資料庫，到目前為止還沒有成熟的産品，PolarDB(X-Engine)是業内第一個基于LSM-tree結構的實作的一寫多讀方案，對于後來者有很好的借鑒意義，LSM-tree這種結構天然将記憶體和磁盤存儲分離，我們充分利用了磁盤存儲隻讀的特點，通過壓縮将其成本優勢發揮出來，結合一寫多讀的能力，将成本優勢發揮到極緻。

六  性能測試

基于X-Engine引擎實作一寫多讀能力後，我們采用基準測試工具sysbench對性能做了摸底，主要對比了RDS(X-Engine)，PolarDB(X-Engine)以及PolarDB(InnoDB)的性能。

1  測試環境

測試的client和資料庫server均從阿裡雲官網購買。client采用ecs，規格是ecs.c7.8xlarge(32core,64G)，測試sysbench版本是sysbench-1.0.20，測試的資料庫server包括RDS(X-Engine)，PolarDB(X-Engine)，PolarDB(InnoDB)均采用8core32G規格，配置檔案采用線上預設的配置。測試場景覆寫了全記憶體态和IO-bound的幾種典型的workload。測試表數目是250張表，全記憶體态單表行數為25000行，IO-bound的表行數為300萬行。

2  測試結果

RDS VS PolarDB

上面左圖是小表全記憶體場景，右圖是大表io-bound場景。PolarDB(X-Engine)相比RDS(X-Engine)主要是寫入路徑發生了變化，最核心的差別是RDS主備架構依賴binlog做複制，而PolarDB形态隻需要redo日志即可。PolarDB形态的寫相關workload的性能相比RDS形态，無論在全記憶體态，還是IO-bound場景，都有很大的性能提升。

B+tree VS LSM-tree

上面左圖是小表全記憶體場景，上面右圖是大表io-bound場景。PolarDB形态下，X-Engine引擎相對于InnoDB引擎還有差距，這個差距主要來源于range查詢，另外更新場景導緻的多版本，也會導緻更新時需要做range查詢，這些因素導緻了讀寫相關的workload，InnoDB引擎比X-Engine表現更優秀。同時我們可以看到，在IO-bound場景，X-Engine引擎寫入更有優勢。

七  未來展望

PolarDB(X-Engine)解決方案很好解決了使用者的歸檔存儲問題，但目前來看還不夠徹底。第一，技術上雖然PolarDB支援了雙引擎，但我們還沒有充分将兩個引擎結合起來。一個可行的思路是線上歸檔一體化，使用者的線上資料采用預設的引擎InnoDB，通過設定一定的規則，PolarDB内部自動将部分曆史資料進行歸檔并轉換為X-Engine引擎存儲，整個過程對使用者透明。第二，目前的存儲都落在PolarDB的高性能存儲PolarStore上，為了進一步降低成本，X-Engine引擎可以将部分冷資料存儲在OSS上，這個對于分層存儲是非常友好和自然的。實際上，基于LSM-tree的存儲引擎有很強的可塑性，我們目前的工作隻是充分發揮了存儲優勢，未來還可以對記憶體中資料結構進行進一步探索，比如做記憶體資料庫等都是可以探索的方向。