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

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

HTAP的技術(shù)路線

MatrixOne的存儲架構(gòu)

MatrixOne的HTAP存儲引擎

01HTAP的技術(shù)路線

1. HTAP問題與挑戰(zhàn)

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

2. HTAP分類

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

首先看學術(shù)界對HTAP融合的看法。

下圖引用自：

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

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

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

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

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

3. HTAP路線

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

路線1

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

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

路線2

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

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

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

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

路線3

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

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

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

路線4

路線4將AP和TP進一步整合，在引擎內(nèi)同時存在行列兩種存儲，行列間進行自動轉(zhuǎn)化。查詢引擎方面進一步優(yōu)化，查詢優(yōu)化器自動選擇存儲引擎。存儲引擎充分融合，共享數(shù)據(jù)庫其他基礎(chǔ)設(shè)施。

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

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

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

路線5

在系統(tǒng)中，使用一份數(shù)據(jù)同時滿足TP和AP。

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

HANA也是路線5的一種實現(xiàn)。HANA使用列存同時服務(wù)TP和AP，采用Delta+Main結(jié)構(gòu)，Delta面向?qū)憙?yōu)化，Main面向讀優(yōu)化，L1-delta行存，L2-delta appendonly列存。

行存數(shù)據(jù)落盤時會發(fā)生compaction行為，通過合并不斷增加寫放大對讀進行優(yōu)化。

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

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

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

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

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

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

02MatrixOne的存儲架構(gòu)

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

1. MatrixOne 存儲架構(gòu)

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

2. MatrixOne AOE

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

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

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

此外Segment的索引區(qū)域存放著一些和AP相關(guān)的索引，如Sparse Index 或Zone map 等，此外還有一些元數(shù)據(jù)。

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

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

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

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

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

03MatrixOne的HTAP存儲引擎

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

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

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

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

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

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

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

因此，TAE可以是LSM Tree結(jié)構(gòu)，它對外仍暴露KV接口，但內(nèi)涵并不是普通KV Store。

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

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

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

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

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

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

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

以上是MatrixOne的HTAP設(shè)計思路，在HTAP版本正式發(fā)布后，關(guān)于存儲數(shù)據(jù)結(jié)構(gòu)方面的設(shè)計會有進一步的詳細介紹。

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

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

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