導讀：本文介紹了MatrixOne向HSTAP迭代的過程中的思考與總結。矩陣起源是一家數據庫創業公司，致力于建設開放的開源技術社區，打造服務企業數字化的超融合異構云原生數據庫產品MatrixOne，幫助用戶降本增效，無需操心一切基礎技術挑戰而只專注于業務本身。MatrixOne作為從零開始研發的數據庫，目標是實現One Size fits Most的超融合HTAP數據庫，目前已經積累了50多萬行代碼，預計2022年下半年發布完整的HTAP引擎供試用。

今天的介紹會圍繞下面三點展開：

HTAP的技術路線

MatrixOne的存儲架構

MatrixOne的HTAP存儲引擎

01HTAP的技術路線

1. HTAP問題與挑戰

HTAP指將OLTP和OLAP數據庫進行融合，但融合的方式多種多樣，同時面臨多種問題。數據插入和更新對于OLTP實時可見，而對OLAP存在挑戰；OLTP對數據事務可以支持不同隔離級別，OLAP大多沒有事務支持。OLTP索引的設計也非常直接，可以設計各種次級索引如HashIndex、BitMapIndex、B-Tree、B+Tree，滿足范圍類的、數據量不大的range query的查詢加速過濾場景。由于OLAP更看重掃描數據的性能、任何索引OLAP上都會產生更大的隨機 IO 以及更大的構建開銷，導致在OLAP上實現的索引意義不大，它對索引的需求也不明確，在OLAP上更多的索引實現是Zonemap這類簡單索引。OLTP對完整性約束的要求非常嚴格，需要支持如組件去重、唯一鍵等功能，但OLAP支持的完整性約束的并不多。

2. HTAP分類

OLTP和OLAP滿足的是不同場景下的需求，如何將TP和AP進行融合？什么叫做融合？業界的看法多種多樣。

首先看學術界對HTAP融合的看法。

下圖引用自：

Retrofitting High Availability Mechanism to Tame Hybrid Transaction/Analytical Processing, OSDI 2021.

圖中將可以HTAP融合分為兩個維度：橫軸是數據新鮮度，縱軸是TP transaction性能下降的維度。數據越新鮮，對transaction的影響越大、性能越差，各家廠商的trade off選擇不同。

圖中劃分了三大區域，最左上角的HyPer是慕尼黑工大實驗室的閉源產品，它是一個純內存的HTAP數據庫，MemSQL也是純內存數據庫。HyPer和MemSQL選擇數據插入即可見，且需要滿足事務，這個設計使數據庫事務的并發能力受限。

圖中中間部分是SQLServer的融合型引擎，數據可見度在百毫秒到幾十毫秒左右，性能損耗相對可控。

圖中右下部分是各種數據庫的組合，可以看到TiDB和Google的F1 Lightning等，這些數據庫通過某種方式將數據進行從行到列的轉化、分離，數據可見度在秒級甚至更久。但這類系統的存儲計算分離，對系統沒有損耗。

3. HTAP路線

我們認為，HTAP路線分為兩大類：第一類是將現有的OLTP和OLAP進行封裝，第二類是從底層存儲到計算一步一步地整合成一體化的數據庫。可以認為封裝型路線將會使用多套數據庫系統，融合性路線只使用一套數據庫系統。

路線1

圖中是路線1的實現，能滿足多數需求，本質是中臺組件，通過ETL任務實現流式Join將TP和AP連接起來。ETL任務可以利用大數據生態組件，選擇很多，這里列舉的CDC工具Debezium、消息隊列Kafka、流式計算引擎Flink是比較常見的選擇，但無論如何都會需要這三樣組件結合才能達到將TP內數據整合到AP中的目的。

這個實現方案存在的問題是實時性不好、使用復雜、負載隔離容易、組件多、成本高。我們需要在整個系統前面實現SQL Proxy，將SQL請求區按AP和TP劃分后發到不同存儲引擎進行處理；如果不實現SQL Proxy，則需要中臺的業務開發人員從業務邏輯入手對請求進行分類和拆解。

路線2

路線2的實現上相比路線1具有更好的完整性。通過“MQ”將TP的日志復制到獨立的AP引擎中，從存儲上看TP和AP是兩套獨立的存儲系統。廣義 MQ 指的是數據可以通過MQ同步，也可以通過其他創新的方式同步，比如大家都比較熟悉的TiDB HTAP就是這類實現，TiDB通過Raft Learner實現數據同步，比一般的MQ效果好很多。

路線2的實現完整性、實時性、數據一致性都比路線1更好，且用戶只需要面對一個數據庫。但是，由于這個實現需要把TP的Binlog/Redo log通過廣義MQ傳到OLAP存儲引擎中進行回放，這里需要TP側和AP側的Table一一對應關系成立。

企業內部的數據探索需求常常需要通過大寬表的形式滿足，即需要將幾十、上百張TP表連成一張大寬表進行數據探索，數據在TP和AP間直接復制和同步，缺少了流式處理的能力，使數據庫能覆蓋的場景有限。這里的流式處理（Stream）指的是需要完整的Stream SQL能力，可以對數據進行Join處理，將數據鏈接成一張寬表，不只是將數據從一處傳送到另一處。

路線3、4、5并沒有直接解決實時地把TP內數據Join成寬表的問題，嘗試了從另一個角度解決問題，著眼于數據新鮮度這一指標，對存儲引擎進行創新。

路線3

當前很多新數據庫都是分布式數據庫，分布式數據庫都是高可用的。絕大多數提供高可用的方案都是采用復制狀態機。從復制狀態機的角度來說，我們沒有必要把三個副本全部都交給一種引擎。我們可以拆出一個副本來，比如三副本中的兩副本可以交給TP，就是行存；另一個副本我們會交給AP，也就是列存。

這個路線相比和路線2類似。路線2中可選擇learner參與日志的同步。路線3可以讓狀態及可以投票的角色（voter）參與到整個系統的共識中。這個方案目前主要停留在學術界，暫時沒有產品化的實現。

方案3存在的問題是，如果列存本身沒有創新，會影響整個集群的共識，最終影響整個集群的寫入性能。

路線4

路線4將AP和TP進一步整合，在引擎內同時存在行列兩種存儲，行列間進行自動轉化。查詢引擎方面進一步優化，查詢優化器自動選擇存儲引擎。存儲引擎充分融合，共享數據庫其他基礎設施。

SQL Server是一個具有代表性的路線4實現方案。行存中存儲全量數據，列存是行存的索引，使用Bw-tree在內存中存放行存數據。這里認為列存是行存的索引。

SQL Server列存采用Delta(Tail Index)+Main方式，從Delta到Main時分配RowID。Main按照Row Group組織Append Only列存。列存更新時也需要回寫行存的RowID，列存回寫時會跟行存事務產生競爭，GC時也會競爭。

Oracle也是路線4的一種實現。Oracle采用堆表保存全量數據，行存和列存分別是堆表的索引緩存(內存)。堆表更新數據，先更新Transaction Journal，定期或觸發將Transaction Journal寫入列存。更新不會影響Layout，阿里云PolarDB也是類似的實現思路。

路線5

在系統中，使用一份數據同時滿足TP和AP。

SingleStore是開頭論文截圖中的MemSQL提供的云原生托數據托管服務，數據存儲兩份，delta數據以行的格式存儲在內存中，將列存數據持久化到文件中，列存數據文件可以被存儲到云原生存儲內。delta的行存到列存轉換是在數據庫內部完成的，整體來說是一份數據存儲。

HANA也是路線5的一種實現。HANA使用列存同時服務TP和AP，采用Delta+Main結構，Delta面向寫優化，Main面向讀優化，L1-delta行存，L2-delta appendonly列存。

行存數據落盤時會發生compaction行為，通過合并不斷增加寫放大對讀進行優化。

4. 如何定義HTAP“有多好”

五種實現路線各有優劣。路線1作為中臺模式的方案，相對于其他集中實現方案的運維成本是最高的。由于路線1的跨數據組件交互的特點，一致性也難以保障，經常出現一致性問題。路線2到5都可以提供事務一致性的保障，但路線2在強一致讀時候會對AP的性能有一定影響，放棄強一致性會獲得更高的AP性能。

實效性方面，路線3、4、5由于融合更加緊密，數據的實時性更好；路線2可以實現秒級的準實時同步數據，由于路線1的同步任務是定時任務同步，最快只能實現分鐘級的數據實時同步。

路線1和路線2的隔離型更好，可以原生地實現存儲和計算隔離。路線3的存儲分離，理論上可以做到計算隔離；路線4的存儲是隔離的，但計算不能隔離；路線5存儲和計算都不分離。

路線1由于使用多套系統、多分存儲，使用成本高。路線2使用兩套系統、兩份存儲，分別做高可用多副本，成本比路線1略低；路線3使用一套系統，兩份存儲，共用一套多副本，存儲的冗余性更好；路線4使用兩份存儲，用一套多副本，存儲開銷比路線3更大；路線5開銷最小，作為一個完整的數據引擎，使用一個引擎、一份存儲、一套高可用方案，滿足AP和TP兩種負載。

80%-90%用戶使用路線1即可滿足探索式分析、交互式分析的使用場景。路線2-5對實時分析這類對數據實時性要求非常高對場景更加合適。

02MatrixOne的存儲架構

MatrixOne預計年終發布完整HTAP引擎試用，屆時大家可以看到這方面更加詳細的介紹。

1. MatrixOne 存儲架構

圖中是MatrixOne的存儲架構，中間是MatrixCube，是單獨開源的。MatrixCube是一個復制狀態機，其中有些存儲調度的邏輯，可以用Raft機制管理不同存儲引擎，當前我們使用開源的Pebble做行存存放Catalog信息，使用矩陣起源自研的AOE（Append Only Columnar Store）引擎做列存。目前我們在使用AOE引擎驗證列存和復制狀態機結合的可行性，接下來AOE存儲引擎將進化到TAE，支持事務處理。

2. MatrixOne AOE

圖中是AOE的Layout，在 AOE 的列存中從數據庫到Table之間的單元叫做 Segment。Segment與其他數據庫中的Group概念類似，內部有Block類似行存B+Tree內的Page，也類似于RocksDB、LSM Tree的Block。Block 在 AOE 中的Segment內部。

一個Segment形成后，Segment內部是全排序的，但是在因為數據會增量、實時地寫入，Block在Segment還沒有形成時在Block內部排序，但在Block間無法排序。因此，如果有Block之間的排序查詢，性能會受到一些影響。

下圖中展示了Block和Segment的設計，Segment是由多個Block組成的。Block中存放著一列數據，Segment中的數據區域會把所有列的數據以列的格式分別存放，然后以Block的單元把數據進行包裝。

此外Segment的索引區域存放著一些和AP相關的索引，如Sparse Index 或Zone map 等，此外還有一些元數據。

下圖中是AOE 與 Raft 交互的場景。我們在做 MatrixOne 最初版本時希望探索列存與Raft機制進行交互。我們已知基于Raft的存儲有TiDB、CockroachDB，但是這些都是基于KV的數據庫，而我們是把列存與Raft結合。

通常情況下存儲引擎和Raft結合起來后會產生4份數據冗余，其中包括 Raft log 兩份寫入和數據（Apply到狀態機后）的兩次寫入，其中存儲的冗余和開銷較大。我們希望減少數據冗余，將4份數據減少到2份，Raft log一份、存儲引擎（狀態機）一份，這就需要存儲引擎提供采用外部Log store作為WAL的能力。

除了Raft Log的Last Log Index, Commit Log Index, Applied Log Index外，我們又增加了Checkpoint Log Index。它的作用是什么？MatrixOne的數據在內存中有Mem Table，Mem Table內存寫滿后落盤形成Block，這個時候需要記錄水位信息，方便在整個系統崩潰被恢復時，能夠根據 Raft Log 做回放、恢復數據。

除此之外，由于列存的Schema不能像KV那樣通過給Key增加Prefix編碼來共享同一個namespac，因此它跟Raft結合時，會帶來更多的復雜度，比如多個Table（對應多個物理的Storage文件）能否夠共享一個Raft group？如果一個Table只能對應一個Raft Group，在創建很多Table的情況下是否會受到影響（正如Apache Kudu所面臨的同類問題）？

這些問題帶來了更多的水位信息的維護，因此單純將列存和Raft像NewSQL那樣結合，在狀態維護上要復雜很多。當前的AOE出于展示目的，采用了Table和Raft Group一一對應的方式，但實際上，在AOE內部的狀態管理上，已經做到了跟Raft Group分離，在TAE交付后，它不會跟Raft有任何耦合。

03MatrixOne的HTAP存儲引擎

下圖是MatrixOne關于HTAP的愿景。前面介紹的幾種HTAP路線中，并沒有完美的解決方案，我們的目標是實現One Size for Most的超融合HTAP數據庫，這里邊對應的是兩個實現路徑：

第一條，我們認為前述的路線一仍然有著巨大的用戶慣性，因此我們希望用數據庫內置的流計算引擎，把內部的各種表實時Join成一張寬表，同時做到該過程端到端的自動化，避免路線一由中間件組合帶來的巨大冗余和維護開銷。當然，一個額外的收益是，用戶還可以針對某類特定查詢做優化，實現增量物化視圖能力，這兩者在技術上是一起完成的。

第二條，MatrixOne AOE進一步迭代，演化為可支持事務的分析性引擎——TAE（Transactional Analytical Engine），作為MatrixOne內部唯一的存儲引擎（盡管MatrixCube具備管理多種存儲引擎的能力）。從存儲引擎實現的角度來說，這里有個選擇的問題：TAE到底是為AP優化的TP，還是為TP優化的AP？我們希望是AP和TP兼顧，通過一個存儲引擎的實現服務兩個目標，事實上這并不難理解：一個列存結構，如果我們讓所有列成為一個Column Family，那么數據的存儲布局跟PostgreSQL里的堆表結構，并沒有本質區別，而這可以服務TP型負載，如果讓每個列都是獨立的Column Family，那它就應該跟普通的OLAP沒有區別。本質上，我們是希望通過存儲引擎底層的靈活設計，實現對多種負載的支持，讓用戶在創建表的時候可以靈活指定。

一個靈魂拷問是：是否可以用通常OLTP存儲引擎中的KV來做TAE？已知這些KV很多是LSM Tree結構，且OLAP引擎很多也是LSM Tree結構，如Clickhouse。

那么，我們能否利用RocksDB實現TAE？這會有兩方面的問題：

① TiDB和CockroachDB可以用一個RocksDB這種類型的存儲存放所有Table，每個Table僅用Key前綴進行區分即可，但列存不能這樣做，因為列存的表Schema不能共享一個namespace，同時管理復雜，它的水位管理和元數據管理都更加復雜，因此不能簡單地把RocksDB拿來做列存。

② OLAP大都采用LSM Tree結構，但很少用Key Value Store。如果直接用Key Value直接做列存，這在Scan的時候會導致序列化開銷非常大，性能降低幾個數量級。如果用Column Family模擬列存，每個Column Family放列存，會導致Key存放開銷大。

因此，TAE可以是LSM Tree結構，它對外仍暴露KV接口，但內涵并不是普通KV Store。

《Fast Scans on Key-Value Stores, VLDB 2017》這篇論文中對存儲引擎設計和架構進行了很好的總結。

數據的更新有多種方式，傳統的B-Tree就是替換更新，數據直接會寫到Page中；日志結構更新，如LSM-Tree通過日志的Compaction更新數據；delta main方式存放寫優先數據結構，main存放讀優先數據，delta可以用行存或內存存放數據，main使用列存存放數據。幾種方式各有優劣，替換更新會讓scan查詢性能更好，但并發受限；日志方式的更新讓點查和寫入可以承受更高并發，但Compaction帶來的GC開銷更大；delta main方式的優缺點則是前面兩種方案的折中。

列存對scan性能友好，但點查性能受限；行存讓點查性能更好，但scan性能受限。版本方面，事務型數據庫必然有MVCC結構，MVCC的數據版本有兩種方式存放，一種是clustered方式存放，另一種是chained。clustered版本信息和原始數據放在一起，讀性能更好，但GC開銷大。chained把版本信息作為鏈表獨立存儲。更新非常頻繁且沒有compaction時會對scan不友好。在compaction時把chain 的版本信息，壓縮到原始的存儲內。

對比下圖的兩個設計構型：如果在行存引擎中，把數據在Page或Block中按列擺放，是否能夠實現TAE？本質上這是為TP優化的引擎，而我們希望保持對AP友好。如果行存中數據按列擺放，每次IO時要訪問一個Page，Page內無效的信息也需要進行訪問，導致IO性能受影響。而典型的列存一次IO只訪問一個列的Block，列存中的AP查詢也可以消除隨機IO。我們最終選擇了列存方案，因為我們希望在配置為AP時，它能達到跟普通OLAP一樣的性能。

TAE構型上選擇了和AOE類似的結構。再看下圖的2個構型：下圖中，堆表+次級索引的模式下，文件也可以按照列擺放。堆文件不排序，需要單獨的索引存放去重信息，會引入額外開銷，在內存中用ART Tree方式存放主鍵信息。

根據在AOE上的SSB性能測試經驗，主鍵是否排序這一點會對IO性能有不小的影響，因此我們希望引入帶排序的構型來提升壓測結果。但全排序會導致不斷地進行compaction，有寫放大問題。我們在平衡各類開銷后選擇在Segment內部排序，避免了寫放大問題，但在Segment之間會存在重疊。由于Segment內部已經進行了排序，接下來在內部建立主鍵索引時可以不用ART Tree轉而用簡單的索引結構即可完成索引。

數據更新和版本管理的構型對比：下圖左邊的堆表結構通過索引訪問到堆文件，更新數據時需要刪除原記錄，同時在文件后面新增，這會導致堆文件體積不斷膨脹。PostgreSQL中Vacuum機制就是針對文件膨脹問題的垃圾回收。下圖中右邊的結構以Segment組織數據，可以做到列數據單獨存放，每個列的更新對應一個delta block，其中對應的是數據版本鏈的信息，版本鏈會在Compaction過程中存進數據Block中。

以上是MatrixOne的HTAP設計思路，在HTAP版本正式發布后，關于存儲數據結構方面的設計會有進一步的詳細介紹。

MatrixOne的RoadMap如圖，我們在2021年發布了一個版本，其中使用了列存和Raft結合的分布式AOE結構，配合我們自己設計的MPP計算引擎。今年年中我們會發布單機版本的HTAP，同時實現行存的分布式事務；第三季度MatrixOne會開源完整的、支持分布式事務的TAE存儲；年終時會發布MatrixOne的流引擎。

MatrixOne的AOE引擎支持多表復雜Join，分組聚合性能表現優秀。0.2.0 Release (2022/01)，是業界最快的SQL分析引擎。

性能表現(On SSB Test): 在未疊加過濾、分區等存儲優化手段，同等只PK計算引擎的能力維度下，MO性能表現已優于 ClickHouse/StarRocks。