本文約9500字，建議閱讀20+分鐘
本文主要闡述如何基于LSM-tree結構的存儲引擎實現(xiàn)數(shù)據(jù)庫的一寫多讀能力。

一? 前言

PolarDB是阿里巴巴自研的新一代云原生關系型數(shù)據(jù)庫，在存儲計算分離架構下，利用了軟硬件結合的優(yōu)勢，為用戶提供具備極致彈性、海量存儲、高性能、低成本的數(shù)據(jù)庫服務。X-Engine是阿里巴巴自研的新一代存儲引擎，作為AliSQL的核心引擎之一已廣泛用于阿里巴巴集團核心業(yè)務，包括交易歷史庫，釘釘歷史庫，圖片空間等。X-Engine基于LSM-tree架構，其核心特征是數(shù)據(jù)以追加寫方式寫入，高壓縮低成本，適用于寫多讀少，有低成本訴求的業(yè)務場景。傳統(tǒng)MySQL基于binlog復制的主備架構有它的局限性，包括存儲空間有限，備份恢復慢，主備復制延遲等問題，為了解決用戶對于云上RDS(X-Engine)大容量存儲，以及彈性伸縮的訴求，PolarDB推出了歷史庫(基于X-Engine引擎的一寫多讀)產(chǎn)品，支持物理復制，提供一寫多讀的能力，目前已經(jīng)在阿里云官網(wǎng)售賣。

二? LSM-tree數(shù)據(jù)庫引擎

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

在云原生數(shù)據(jù)庫時代，一寫多讀技術已被廣泛應用于生產(chǎn)環(huán)境中，主要云產(chǎn)商都有其標桿產(chǎn)品，典型代表包括亞馬遜的Aurora，阿里云的PolarDB以及微軟云的Socrates。它的核心思想是計算存儲分離，將有狀態(tài)的數(shù)據(jù)和日志下推到分布式存儲，計算節(jié)點無狀態(tài)，多個計算節(jié)點共享一份數(shù)據(jù)，數(shù)據(jù)庫可以低成本快速擴展讀性能。Aurora是這個領域的開山鼻祖，實現(xiàn)了業(yè)內第一個一寫多讀的數(shù)據(jù)庫，計算節(jié)點Scale up，存儲節(jié)點Scale out，并將日志模塊下推到存儲層，計算節(jié)點之間，計算與存儲節(jié)點之間傳輸redo日志，計算節(jié)點基于Quorum協(xié)議寫多副本保證可靠性，存儲層提供多版本頁服務。PolarDB與Aurora類似，也采用了存儲計算分離架構，與Aurora相比，PolarDB它自己的特色，存儲基座是一個通用的分布式文件系統(tǒng)，大量采用OS-bypass和zero-copy技術，存儲的多副本一致性由ParallelRaft協(xié)議保證。PolarDB計算節(jié)點與存儲節(jié)點同時傳輸數(shù)據(jù)頁和redo日志，計算節(jié)點與計算節(jié)點之間只傳遞位點信息。與Aurora的“日志即數(shù)據(jù)庫”理念一樣，Socrates的節(jié)點之間只傳輸redo日志，也實現(xiàn)了多版本頁服務，它的特點是將數(shù)據(jù)庫存儲層的持久性與可用性分開，抽象出一套日志服務。整個數(shù)據(jù)庫分為3層，一層計算服務，一層page server服務和一層日志服務，這樣設計的好處是可以分層進行優(yōu)化，提供更靈活和細粒度的控制。

雖然Aurora，PolarDB和Socrates在設計上各有特點，但它們都共同踐行了存儲計算分離思想，數(shù)據(jù)庫層面提供一寫多讀的能力。深入到存儲引擎這一層來說，這幾個產(chǎn)品都是基于B+tree的存儲引擎，如果基于LSM-tree存儲引擎來做呢？LSM-tree有它自己的特點，追加順序寫，數(shù)據(jù)分層存儲，磁盤上數(shù)據(jù)塊只讀更有利于壓縮。X-Engine引擎云上產(chǎn)品RDS(X-Engine)已經(jīng)充分發(fā)揮了LSM-tree高壓縮低成本特點，同樣的數(shù)據(jù)量，存儲空間只占到RDS(InnoDB)的1/3甚至更少，RDS(X-Engine)傳統(tǒng)的主備架構，依然面臨著主備復制延遲大，備份恢復慢等問題?；贚SM-tree引擎實現(xiàn)一寫多讀，不僅計算資源和存儲資源解耦，多個節(jié)點共享一份數(shù)據(jù)還能進一步壓縮存儲成本。

基于LSM-tree引擎實現(xiàn)一寫多讀面臨著與B+tree引擎不一樣的技術挑戰(zhàn)，首先是存儲引擎日志不一樣，LSM-tree引擎是雙日志流，需要解決雙日志流的物理復制問題；其次是數(shù)據(jù)組織方式不一樣，LSM-tree引擎采用分層存儲，追加寫入新數(shù)據(jù)，需要解決多個計算節(jié)點一致性物理快照以及Compation問題。最后，作為數(shù)據(jù)庫引擎，還需要解決一寫多讀模式下DDL的物理復制問題。同時，為了產(chǎn)品化，充分發(fā)揮B+tree引擎和LSM-tree引擎的各自優(yōu)勢，還面臨著新的挑戰(zhàn)，即如何在一個數(shù)據(jù)庫產(chǎn)品中同時實現(xiàn)兩個存儲引擎(InnoDB,X-Engine)的一寫多讀。

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

1? PolarDB整體架構

PolarDB支持X-Engine引擎后，X-Engine引擎與InnoDB引擎仍然獨立存在。兩個引擎各自接收寫入請求，數(shù)據(jù)和日志均存儲在底層的分布式存儲上，其中idb文件表示的是InnoDB的數(shù)據(jù)文件，sst文件表示的是X-Engine的數(shù)據(jù)文件。這里最主要的點在于InnoDB與XEngine共享一份redo日志，X-Engine寫入時，將wal日志嵌入到InnoDB的redo中，Replica節(jié)點和Standby節(jié)點在解析redo日志后，分發(fā)給InnoDB引擎和XEngine引擎分別回放進行同步。

PolarDB(X-Engine)架構圖

X-Engine引擎架構

X-Engine引擎采用LSM-tree結構，數(shù)據(jù)以追加寫的方式寫入內存，并周期性物化到磁盤上，內存中數(shù)據(jù)以memtable形式存在，包括一個活躍的active memtable和多個靜態(tài)的immutable。磁盤上數(shù)據(jù)分層存儲，總共包括3層，L0，L1和L2，每一層數(shù)據(jù)按塊有序組織。X-Engine最小空間分配單位是一個extent，默認是2M，每個extent包含若干個block，默認是16k。數(shù)據(jù)記錄緊湊存儲在block中，由于追加寫特點，磁盤上的數(shù)據(jù)塊都是只讀的，因此X-Engine引擎可以默認對block進行壓縮，另外block中的記錄還會進行前綴編碼，綜合這些使得X-Engine的存儲空間相對于InnoDB引擎只有1/3，部分場景(比如圖片空間)甚至能壓縮到1/7。有利就有弊，追加寫帶來了寫入優(yōu)勢，對于歷史版本數(shù)據(jù)需要通過Compaction任務來進行回收。有關X-Engine的核心技術可以參考發(fā)表在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日志來保證持久性。因此，在進行復制時，只需要在主從節(jié)點復制redo日志即可。X-Engine引擎包含兩種日志，一種是wal日志(WriteAheadLog)，用于記錄前臺的事務的操作；另一種是Slog(StorageLog)，用于記錄LSM-tree形狀變化的操作，主要指Compaction/Flush等。wal日志保證了前臺事務的原子性和持久性，Slog則保證了X-Engine內部LSM-tree形狀變化的原子性和持久性，這兩個日志缺一不可，都需要復制同步。

共享存儲下的物理復制

Primary-Replica物理復制架構

LSM-tree引擎一寫多讀的能力是對PolarDB進行功能增強，體現(xiàn)在架構層面就是充分利用已有的復制鏈路，包括Primary->Replica傳遞日志信息鏈路和Replica->Primary傳遞協(xié)同控制信息鏈路。InnoDB事務由若干個mtr(Mini-Transaction)組成，寫入redo日志的最小單位是mtr。我們在Innodb的redo日志新增一種日志類型用于表示X-Engine日志，將X-Engine的事務內容作為一個mtr事務寫入到redo日志中，這樣Innodb的redo和X-Engine的wal日志能共享一條復制鏈路。由于Primary和Replica共享一份日志和數(shù)據(jù)，Dump_thread只需要傳遞位點信息，由Replica根據(jù)位點信息去讀redo日志。Replica解析日志，根據(jù)日志類型來分發(fā)日志給不同的回放引擎，這種架構使得所有復制框架與之前的復制保持一致，只需要新增解析、分發(fā)X-Engine日志邏輯，新增X-Engine的回放引擎，充分與InnoDB引擎解耦。

由于LSM-tree追加寫特點，內存memtable中數(shù)據(jù)會周期性的Flush到磁盤，為了保證Primary和Replica讀到一致性物理視圖，Primary和Replica需要同步SwitchMemtable，需要新增一條SwitchMemtable控制日志來協(xié)調。redo日志持久化后，Primary通過日志方式將位點信息主動推送給Replica，以便Replica及時回放最新的日志，減少同步延遲。對于Slog日志，既可以采用類似于redo的日志方式來主動“push”方式來同步位點，也可以采用Replica主動“pull”的方式來同步。SLog是后臺日志，相對于前臺事務回放實時性要求不高，不必要將redo位點和SLog位點都放在一條復制鏈路增加復雜性，所以采用了Replica的“pull”的方式來同步SLog。

災備集群間的物理復制

Primary-Standby物理復制架構

與共享集群復制不同，災備集群有獨立一份存儲，Primary—>Standby需要傳遞完整的redo日志。Stanby與Replica區(qū)別在于日志來源不同，Replica從共享存儲上獲取日志，Standy從復制鏈路獲取日志，其它解析和回放路徑是一樣的。是否將Slog日志作為redo日志一部分傳遞給Standby是一個問題，Slog日志由Flush/Compaction動作產(chǎn)生，記錄的是LSM-tree形狀的物理變化。如果也通過redo日志鏈路同步給Standby，會帶來一些復雜性，一方面是X-Engine內部寫日志的方式需要改動，需要新增新增文件操作相關的物理日志來確保主從物理結構一致，故障恢復的邏輯也需要適配；另一方面，Slog作為后臺任務的操作日志，意味著復制鏈路上的所有角色都需要同構；如果放棄同構，那么Standy節(jié)點可能會觸發(fā)Flush/Compaction任務寫日志，這與物理復制中，只允許Primary寫日志是相違背的。實際上，Slog同步寫入到redo log中不是必須的，因為Slog是后臺日志，這個動作不及時回放并不影響數(shù)據(jù)視圖的正確性，因此，復制鏈路上只包含redo日志(X-Engine wal日志和InnoDB redo日志)，Standby自己控制Flush/Compaction產(chǎn)生Slog日志，這樣Standby也不必與Primary節(jié)點物理同構，整個架構與現(xiàn)有體系相匹配，同時也更加靈活。

3? 并行物理復制加速

X-Engine的事務包括兩個階段，第一個階段是讀寫階段，這個階段事務操作數(shù)據(jù)會緩存在事務上下文中，第二階段是提交階段，將操作數(shù)據(jù)寫入到redo日志持久化，隨后寫到memtable中供讀操作訪問。對于Standby/Replica節(jié)點而言，回放過程與Primary節(jié)點類似，從redo中解析到事務日志，然后將事務回放到memtable中。事務之間不存在沖突，通過Sequence版本號來確定可見性。并行回放的粒度是事務，需要處理的一個關鍵問題就是可見性問題。事務串行回放時，Sequence版本號都是連續(xù)遞增的，事務可見性不存在問題。在并行回放場景下，我們仍然需要保序，通過引入“滑動窗口”機制，只有連續(xù)一段沒有空洞的Sequence才能推進全局的Sequence版本號，這個全局Sequence用于讀操作獲取快照。

并行復制框架

一寫多讀架構下，為了保證同一數(shù)據(jù)庫實例的Primary、Replica、Standby三個角色的內存鏡像完全一致，新增了一種SwitchMemtableLog，該Log Record在RW的switch_memtable過程中產(chǎn)生，因此RO、Standby不再主動觸發(fā)switch_memtable操作，而是通過從RW上同步SwitchMemtableLog進行switch_memtable。SwitchMemtable操作是一個全局的屏障點，以防止當前可寫memtable在插入過程中switch從而導致數(shù)據(jù)錯亂。另外，對于2PC事務，并發(fā)控制也需要做適配。一個2PC事務除了數(shù)據(jù)本身的日志，還包括BeginPrepare、EndPrepare、Commit、Rollback四類日志，寫入過程中保證BeginPrepare和EndPrepare寫入到一個WriteBatch中并順序落盤，因此可以保證同一個事務的Prepare日志都會被解析到一個ReplayTask中。在并行回放過程中，由于無法保證Commit或Rollback日志一定后于Prepare日志被回放，因此如果Commit、Rollback日志先于Prepare日志被回放，那么在全局的recovered_transaction_map中插入一個key對xid的空事務，對應的事務狀態(tài)為Commit或Rollback；隨后Prepare日志完成回放時，如果發(fā)現(xiàn)recovered_transaction_map中已經(jīng)存在對應的事務，那么可以根據(jù)事務的狀態(tài)來決定直接提交事務還是丟棄事務。

對于B+Tree的物理復制，LSM-tree的物理復制并不是真正的“物理”復制。因為B+Tree傳遞的redo的內容是數(shù)據(jù)頁面的修改，而LSM-tree傳遞的redo內容是KeyValue值。這帶來的結果是，B+tree物理復制可以基于數(shù)據(jù)頁粒度做并發(fā)回放，而LSM-tree的物理復制是基于事務粒度的并發(fā)回放。B+tree并發(fā)回放有它自身的復雜性，比如需要解決系統(tǒng)頁回放與普通數(shù)據(jù)頁回放先后順序問題，并且還需要解決同一個mtr中多個數(shù)據(jù)頁并發(fā)回放可能導致的物理視圖不一致問題。LSM-tree需要解決多個節(jié)點在同樣位置SwitchMemtable，以及2PC事務回放等問題。

4? MVCC(多版本并發(fā)控制)

物理復制技術解決了數(shù)據(jù)同步的問題，為存儲計算分離打下了基礎。為了實現(xiàn)彈性，動態(tài)升降配，增刪只讀節(jié)點的能力，需要只讀節(jié)點具備一致性讀的能力，另外RW節(jié)點和RO節(jié)點共享一份數(shù)據(jù)，歷史版本回收也是必需要考慮的問題。

一致性讀

X-Engine提供快照讀的能力，通過多版本機制來實現(xiàn)讀寫不互斥效果。從上述的X-Engine架構圖可以看到，X-Engine的數(shù)據(jù)實際上包括了內存和磁盤兩部分，不同于InnoDB引擎內存中page是磁盤上page的緩存，X-Engine中內存數(shù)據(jù)與磁盤數(shù)據(jù)完全異構，一份“快照”需要對應的是內存+磁盤數(shù)據(jù)。X-Engine采用追加寫方式，新數(shù)據(jù)進來會產(chǎn)生新的memtable，后臺任務做flush/compaction任務也會產(chǎn)生新的extent。那么如何獲取一致性視圖呢？X-Engine內部實際上是通過MetaSnapshot+Snapshot來管理，首先每個MetaSnapshot對應一組memtable和L0，L1, L2的extents，這樣在物理上確定了數(shù)據(jù)范圍，然后通過Snapshot來處理行級版本的可見性，這里的Snapshot實際上就是一個事務提交序列號Sequence。不同于InnoDB事務編號采用開始序，需要通過活躍事務視圖來判斷記錄的可見性；X-Engine事務采用提交序，每條記錄有一個唯一遞增序列號Sequence，判斷行級版本的可見性只需要比較Sequence即可。在一寫多讀的模式下，Replica節(jié)點與Primary節(jié)點共享一份磁盤數(shù)據(jù)，而磁盤數(shù)據(jù)是有內存中數(shù)據(jù)定期dump出來的，因此需要保證Primary和Replica節(jié)點有相同的切memtable位點，從而保證數(shù)據(jù)視圖的一致性。

一寫多讀下的Compaction

在一寫多讀場景下，Replica可以通過類似于Primary的快照機制來實現(xiàn)快照讀，需要處理的問題是歷史版本回收問題。歷史版本的回收，依賴于Compaction任務來完成，這里的回收包括兩部分，一部分MetaSnapshot的回收，主要確認哪些memtable和extents可以被物理回收掉，另一部分是行級多版本回收，這里主要是確認哪些歷史版本行可以被回收掉。對于MetaSnapshot的回收，Primary會收集所有Replica節(jié)點上的最小不再使用的MetaSnapshot版本號，X-Engine引擎的每個索引都是一個LSM-tree，因此匯報MetaSnaphot版本號是索引粒度的。Primary收集完MetaSnapshot版本號，計算最小可以回收的MetaSnapshot進行資源回收操作，回收操作以Slog日志的方式同步給Replica節(jié)點。Replica節(jié)點在回放日志進行資源回收時，需要將內存和磁盤資源分開，內存資源在各個節(jié)點是獨立的，磁盤資源是共享的，因此Replica節(jié)點的內存資源可以獨立釋放，而磁盤資源則統(tǒng)一由Primary節(jié)點來釋放。對于行級多版本的回收，同樣需要由Primary節(jié)點收集所有Replica節(jié)點最小序列號Sequence，由Primary節(jié)點通過Compaction任務來消除。這塊匯報鏈路復用PolarDB的ACK鏈路，只是新增了X-Engine的匯報信息。

5? DDL的物理復制如何實現(xiàn)

物理復制相對于邏輯復制一個關鍵優(yōu)勢在于DDL，對于DDL而言，邏輯復制可以簡單理解為復制SQL語句，DDL在從庫上會重新再執(zhí)行一遍。邏輯復制對于比較重的DDL操作，比如Alter table影響非常大，一個Alter變更操作在主庫執(zhí)行需要半小時，那么復制到從庫也需要再執(zhí)行半小時，那么主從延遲最大可能就會是1個小時，這個延遲對只讀庫提供讀服務產(chǎn)生嚴重影響。

Server層復制

DDL操作同時涉及到Server層和引擎層，包括字典，緩存以及數(shù)據(jù)。最基礎的DDL操作，比如Create/Drop操作，在一寫多讀架構下，要考慮數(shù)據(jù)與數(shù)據(jù)字典，數(shù)據(jù)與字典緩存一致性等問題。一寫多讀的基礎是物理復制，物理復制日志只在引擎層流動，不涉及到Server層，因此需要新增日志來解決DDL操作導致的不一致問題。我們新增了meta信息變更的日志，并作為redo日志的一部分同步給從節(jié)點，這個meta信息變更日志主要包括兩部分內容，一個是字典同步，主要是同步MDL鎖，確保Primary/Replica節(jié)點字典一致；另一個是字典緩存同步，Replica上的內存是獨立的，Server層緩存的字典信息也需要更新，因此要新增日志來處理，比如Drop Table/Drop db/Upate function/Upate precedure等操作。另外，還需要同步失效Replica的QueryCache，避免使用錯誤的查詢緩存。

引擎層復制

X-Engine引擎與InnoDB引擎一樣是索引組織表，在X-Engine內部，每個索引都是一個LSM-tree結構，內部稱為Subtable，所有寫入都是在Subtable中進行，Subtable的生命周期與DDL操作緊密相關。用戶發(fā)起建表動作會產(chǎn)生Subtable，這個是物理LSM-tree結構的載體，然后才能有后續(xù)的DML操作；同樣的，用戶發(fā)起刪表動作后，所有這個Subtable的DML操作都應該執(zhí)行完畢。Create/Drop Table操作涉及到索引結構的產(chǎn)生和消亡，會同時產(chǎn)生redo控制日志和SLog日志，在回放時，需要解決redo控制日志和SLog日志回放的時序問題。這里我們將對應Subtable的redo日志的LSN位點持久化到SLog中，作為一個同步位點，Replica回放時，兩個回放鏈路做協(xié)調即可，redo日志記錄的是前臺操作，Slog記錄的是后臺操作，因此兩個鏈路做協(xié)同時，需要盡量避免redo復制鏈路等待Slog復制鏈路。比如，對于Create操作，回放Slog時，需要等待對應的redo日志的LSN位點回放完畢才推進；對于DROP操作，回放SLog也需要協(xié)同等待，避免回放前臺事務找不到Subtable。

OnlineDDL復制技術

對于Alter Table操作，X-Engine實現(xiàn)了一套OnlineDDL機制，詳細實現(xiàn)原理可以參考內核月報。在一寫多讀架構下，X-Engine引擎在處理這類Alter操作時采用了物理復制，實際上對于Replica而言，由于是同一份數(shù)據(jù)，并不需要重新生成物理extent，只需要同步元信息即可。對于Standby節(jié)點，需要通過物理extent復制來重新構建索引。DDL復制時，實際上包含了基線和增量部分。DDL復制充分利用了X-Engine的分層存儲以及LSM-tree結構追加寫特點，在獲取快照后，利用快照直接構建L2作為基線數(shù)據(jù)，這部分數(shù)據(jù)以extent塊復制形式，通過redo通道傳遞給Standby，而增量數(shù)據(jù)則與普通的DML事務一樣，所以整個操作都是通過物理復制進行，大大提高了復制效率。這里需要限制的僅僅是在Alter操作過程中，禁止做到L2的compaction即可。整個OnlineDDL過程與InnoDB的OnlineDDL流程類似，也是包括3個階段，prepare階段，build階段和commit階段，其中prepare階段需要獲取快照，commit階段元數(shù)據(jù)生效，需要通過MDL鎖來確保字典一致。與基于B+tree的OnlineDDL復制相比，基線部分，B+tree索引復制的是物理頁，而LSM-tree復制的是物理extent；增量部分B+tree索引是通過記增量日志，回放增量日志到數(shù)據(jù)頁寫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，確保任何引擎有內存數(shù)據(jù)沒有落盤時，對應的redo日志不能被清理。為了避免X-Engine的checkpoint推進影響整體位點推進，內部會確保xengine-ckpt-lsn與全局的redo-lsn保持一定的閥值，超過閥值則會強制將memtable落盤，推進檢查點。

數(shù)據(jù)字典與DDL

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

通過元數(shù)據(jù)歸一化我們解決了元數(shù)據(jù)的原子性問題，但X-Engine數(shù)據(jù)和InnoDB元數(shù)據(jù)如何保證一致也是個問題。比如一個DDL操作，alter table xxx engine = xengine，這個DDL是將innodb表轉為xengine表，由于表結構變更是Innodb字典修改，數(shù)據(jù)是在修改X-Engine，是一個跨引擎事務，跨引擎事務需要通過協(xié)調者保證一致性。為了避免引入binlog作為協(xié)調者依賴，tclog作為協(xié)調者沒有經(jīng)過大規(guī)模生產(chǎn)環(huán)境驗證，我們選擇了另外一種處理方式，具體來說，在涉及跨引擎事務時，優(yōu)先提交X-Engine事務，然后再提交InnoDB事務。對于DDL來說，就是“先數(shù)據(jù)，后元數(shù)據(jù)”，元數(shù)據(jù)提交了，才真正表示這個DDL完成。如果中途失敗，則結合“延遲刪除”的機制，來保證垃圾數(shù)據(jù)能被最終清理掉，通過一個后臺任務來周期性的對比X-Engine數(shù)據(jù)與InnoDB的字典，以InnoDB字典為準，結合X-Engine內存元信息，確認這部分數(shù)據(jù)是否有用。

CrashRecovery

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

HA

PolarDB支持雙引擎后，整個升降級流程中都會嵌套有X-Engine引擎的邏輯，比如在Standby升級為RW前，需要確保X-Engine的回放流水線完成，并將未決的事務保存起來，以便后續(xù)通過XA_Recovery繼續(xù)推進。RW降級為Standby的時候需要等待X-Engine寫流水線回放，同時如果還殘留有未決事務，需要在切換過程中將這部分未決事務遍歷出來存入Recovered_transactions_集合供后續(xù)并發(fā)回放使用。

四? LSM-tree VS B+tree

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

五? LSM-tree引擎業(yè)內發(fā)展狀況

目前業(yè)內LSM-tree類型引擎比較熱的是Rocksdb，它的主要應用場景是作為一個KeyValue引擎使用。Facebook將Rocksdb引擎引入到了他們的MySQL8.0分支，類似于X-Engine之于AliSQL，主要服務于他們的用戶數(shù)據(jù)庫UDB業(yè)務，存儲用戶數(shù)據(jù)和消息數(shù)據(jù)，采用的仍然是基于binlog的主備復制結構，目前沒有看到有做存儲計算分離，以及一寫多讀的事情。另外，github上有一個rocksdb-cloud項目，將rocksdb作為底座，架在AWS等云服務上提供NoSQL接口服務，相當于做了存儲計算分離，但并不支持物理復制和一寫多讀。在數(shù)據(jù)庫領域，阿里巴巴的Oceanbase和谷歌的Spanner的底層存儲引擎都是基于LSM-tree結構，這顯示了LSM-tree作為數(shù)據(jù)庫引擎的可行性，這兩個數(shù)據(jù)庫都是基于Share-Nothing的架構?；赟hare-Storage的數(shù)據(jù)庫，到目前為止還沒有成熟的產(chǎn)品，PolarDB(X-Engine)是業(yè)內第一個基于LSM-tree結構的實現(xiàn)的一寫多讀方案，對于后來者有很好的借鑒意義，LSM-tree這種結構天然將內存和磁盤存儲分離，我們充分利用了磁盤存儲只讀的特點，通過壓縮將其成本優(yōu)勢發(fā)揮出來，結合一寫多讀的能力，將成本優(yōu)勢發(fā)揮到極致。

六? 性能測試

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

1? 測試環(huán)境

測試的client和數(shù)據(jù)庫server均從阿里云官網(wǎng)購買。client采用ecs，規(guī)格是ecs.c7.8xlarge(32core,64G)，測試sysbench版本是sysbench-1.0.20，測試的數(shù)據(jù)庫server包括RDS(X-Engine)，PolarDB(X-Engine)，PolarDB(InnoDB)均采用8core32G規(guī)格，配置文件采用線上默認的配置。測試場景覆蓋了全內存態(tài)和IO-bound的幾種典型的workload。測試表數(shù)目是250張表，全內存態(tài)單表行數(shù)為25000行，IO-bound的表行數(shù)為300萬行。

2? 測試結果

RDS VS PolarDB

上面左圖是小表全內存場景，右圖是大表io-bound場景。PolarDB(X-Engine)相比RDS(X-Engine)主要是寫入路徑發(fā)生了變化，最核心的區(qū)別是RDS主備架構依賴binlog做復制，而PolarDB形態(tài)只需要redo日志即可。PolarDB形態(tài)的寫相關workload的性能相比RDS形態(tài)，無論在全內存態(tài)，還是IO-bound場景，都有很大的性能提升。

B+tree VS LSM-tree

上圖是小表全內存場景，下圖是大表io-bound場景。PolarDB形態(tài)下，X-Engine引擎相對于InnoDB引擎還有差距，這個差距主要來源于range查詢，另外更新場景導致的多版本，也會導致更新時需要做range查詢，這些因素導致了讀寫相關的workload，InnoDB引擎比X-Engine表現(xiàn)更優(yōu)秀。同時我們可以看到，在IO-bound場景，X-Engine引擎寫入更有優(yōu)勢。

七? 未來展望

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

編輯：于騰凱

校對：林亦霖

如何基于LSM-tree架構實現(xiàn)一寫多讀