如何基於LSM-tree架構實現一寫多讀
- 2021 年 12 月 29 日
- 筆記
- MySQL, mysql polardb 雲原生 分佈式 數據庫 一寫多讀 高壓縮 低成本, 分佈式
一 前言
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表示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的存儲引擎有很強的可塑性，我們目前的工作只是充分發揮了存儲優勢，未來還可以對內存中數據結構進行進一步探索，比如做內存數據庫等都是可以探索的方向。
