TAE是MatrixOne的儲存引擎，取這個名字，是因為它需要同時支撐TP和AP能力。第一個版本的TAE實現，已經隨MatrixOne 0.5版本釋出，這是一個單機儲存引擎。從MatrixOne 0.6版本開始，TAE將進化成為存算分離的雲原生分散式架構。我們將分期跟隨MatrixOne版本地演進，逐步揭示TAE儲存引擎的設計內幕。

本文假定讀者對列存有基本的瞭解，對於列存的資料常見組織，比如block(或者page，最小IO單元)，segment(若干block組成的row group)，zonemap(column block內的最大/最小值)等都有基本的認知，對普通的Key Value儲存引擎實現，比如LSM Tree也有初步瞭解，比如它的Memtable，WAL，SST檔案等概念。下圖的TAE邏輯結構的左半部分，涉及到了列存的一些基本概念，可以供不具備相關背景的同學瞭解。

在介紹TAE設計之前，首先回答一個問題：為什麼採用列存結構來設計一個數據庫的核心儲存引擎？

這是因為MatrixOne期望用一個儲存引擎同時解決TP和AP的問題。至於為什麼這樣做，可以關注矩陣起源的其他文章，簡單地講，就是期望在共享儲存的基礎之上，可以隨意彈性的啟動不同計算節點分別處理TP和AP任務，在最大化伸縮性的同時保證不同負載的相互隔離。在這個前提之下，採用以列存為基礎的結構，可以具備如下優點：

1. 很容易對AP優化
2. 通過引入Column Family的概念可以對負載靈活適配。假如所有列都是一個Column Family，也就是所有的列資料儲存在一起，這就跟資料庫的HEAP檔案非常類似，可以表現出行存類似的行為，典型的OLTP資料庫如PostgreSQL就是基於HEAP來做的儲存引擎。假如每個列都是獨立的Column Family，也就是每一列都獨立存放，那麼就是典型的列存。通過定義Column Family，使用者可以方便地在行存和列存之間切換，這隻需要在DDL表定義中指定即可。

因此，從物理上來說，TAE就是一個列存引擎。下文的行存，則是指普通的Key Value儲存引擎如RocksDB，因為很多典型的分散式資料庫都基於它來構建。TAE是一個類似LSM Tree的結構但卻沒有直接採用RocksDB，是出於一些額外的考慮。

為什麼列存比行存難設計？

眾所周知SQL計算引擎處理TP請求和AP請求有著巨大的不同，前者以點查詢為主，要求高併發能力，後者以Scan請求為主，通常採用MPP引擎，不追求併發而追求並行處理。對應到儲存，行存天然是服務TP請求的，列存天然是服務AP請求的，因為前者可以採用基礎的火山模型，少量讀取若干行即返回結果，後者則必須批處理(所謂的向量化執行)，通常還要配合Pipeline，一次讀取某列的幾千行這樣，因此MPP計算引擎，讀取完記錄，需要極快地對整批資料做集中處理，而不能逐條的讀取，反序列化，解碼，那樣將大大降低系統的吞吐量。

當儲存引擎內部需要支援多張表的時候，對於行存來說，處理非常簡單，只需要給每行增加TableID的字首即可，這並沒有給系統整體增加多少開銷，因為反序列化，解碼只需針對若干記錄即可。這時的多張表，在儲存引擎看來，都是統一的Key Value，表之間並沒有什麼不同。

可是對於列存來說，首先，每張表的列都是獨立存放的，不同的表也包含不同的列，這樣表之間的資料擺放，完全不同。假定它也支援主鍵，那麼同樣給每行增加TableID的字首，本質上是對向量化執行的打斷，因此，TableID這樣的資料，需要存放到元資料。除了TableID之外，列存還需要記錄每個列的資訊(比如block，segment，zonemap，等等)，並且不同的Table之間是完全不同的，而行存就沒有這樣的問題，所有的Table只要通過TableID作字首，就可以，因此列存為什麼比行存難，核心點之一在於元資料複雜度遠高於行存。以樹狀視角來看，常見的列存元資料組織看起來像是這樣：

|-- [0]dentry:[name="/"]
|   |-- [1]dentry:[name="db1"]
|   |    |-- [2]dentry:[name="table1"]
|   |    |    |-- [3]dentry:[name="segment1"]
|   |    |    |     |-- [4]dentry:[name="block1"]
|   |    |    |     |    |-- col1 [5]
|   |    |    |     |    |-- col2 [6]
|   |    |    |     |    |-- idx1 [7]
|   |    |    |     |    |-- idx2 [8]
|   |    |    |     |
|   |    |    |     |-- [9]dentry:[name="block2"]
|   |    |    |     |    |-- col1 [10]
|   |    |    |     |    |-- col2 [11]
|   |    |    |     |    |-- idx1 [12]
|   |    |    |     |    |-- idx2 [13]

除了元資料的複雜之外，還有崩潰恢復機制，這就是WAL(Write Ahead Logging)，列存要考慮的事情，也會更多。對於行存來說，所有的表都共享同樣的Key Value空間，因此就是一個普通的Key Value儲存所需要的WAL，記錄一個LSN(Last Sequence Number)水位即可。但如果列存也這麼做，就會有一些問題：

上面的圖很粗略顯示了一個列存Memtable的樣例，為方便管理，我們認定Memtable的每個Block(Page)只能包含一張表的某列資料。假設在Memtable裡包含多張表同時寫入的資料，由於不同的表寫入速度的不同，因此每張表在Memtable包含資料的多少也必然不同。如果我們在WAL中只記錄一個LSN，這就意味著當發生Checkpoint的時候，我們需要把Memtable每張表的資料都Flush到硬碟，哪怕這張表的資料在Memtable中只有1行。同時，由於列存的schema無法像行存那樣完全融入到單一的Key Value中，因此，即使一行表資料，也會生成對應的檔案，甚至是每列一個檔案，在表的數量眾多的時候，這會產生大量的碎片檔案，導致巨大的讀放大。當然，也可以不考慮這麼複雜的場景，畢竟，很多列存引擎連WAL都還沒有，而即使有WAL的列存引擎，也大都不這樣考慮問題，比如所有表固定到某行數的時候才做Checkpoint，那麼表多的時候，Memtable可能就會佔據大量記憶體，甚至OOM。TAE是MatrixOne資料庫主要甚至是唯一的儲存引擎，它需要承載不僅AP還有TP的業務，因此對於資料庫使用來說，它必須要能夠像普通Key Value儲存引擎那樣任意建立表，因此，最直接的方案，就意味著在WAL中需要為每張表都維護一個LSN，也就是說，在統一的WAL中，每張表都有自己獨立的邏輯日誌空間記錄自己當前寫入的水位。換句話，如果我們把WAL看做是一個訊息佇列，普通行存的WAL就相當於只有一個Topic的訊息佇列，而列存的WAL則相當於有一堆Topic的訊息佇列，而且這些Topic在物理上連續存放，並不像普通訊息佇列那樣各個Topic資料獨立存放。因此，列存的WAL，需要更加精細化的設計，才能讓它使用方便。

下面正式介紹TAE儲存引擎的設計。

資料儲存

TAE以表的形式儲存資料。每個表的資料被組織成一個LSM樹。目前，TAE是一個三層LSM樹，稱為L0、L1和L2。L0很小，可以完全駐留在記憶體中，就是上文提到的Memtable，而L1和L2都駐留在硬碟上。在TAE中，L0由transient block組成，不排序，L1由sorted block組成。傳入的新資料總是被插入最新的transient block中。如果插入導致該塊超過了一個塊的最大行數，該塊將被按主鍵排序，並作為sorted block刷入L1。如果被排序的塊的數量超過了一個segment的最大數量，那麼將使用merge sort方法按主鍵進行排序並寫入L2。column block是TAE的最小IO單元，目前它是按照固定行數來組織的，對於blob列的單獨處理，會在後續版本中改進。

L1和L2存放的都是按主鍵排序的資料。排序的資料之間，主鍵會有範圍重疊。L1和L2的區別在於，L1是保證block內按主鍵排序，而L2則是保證一個segment內按主鍵排序。這裡segment是一個邏輯概念，它在同類實現中也可以等價為row group，row set等。如果一個segment有許多更新（刪除），它可以被compact成一個新的segment，多個segment也可以merge成一個新segment，這些都通過後臺的非同步任務來完成，任務的排程策略，主要是寫放大和讀放大之間的權衡——基於此考慮TAE不推薦提供L4層，也就是說全部segment按照主鍵全排序，儘管從技術上可以這麼做(通過後臺非同步任務反覆merge，比如ClickHouse等列存的行為)。

索引和元資料

跟傳統列存一樣，TAE沒有引入行存的次級索引，只有在block和segment級分別引入了Zonemap(Min/Max資料)資訊，未來也會根據需要增加Bloom Filter資料，為查詢執行的Runtime Filter優化提供支援。作為支撐TP的儲存引擎，TAE提供完整的主鍵約束，包含多列主鍵和全域性自增ID。TAE預設為每個表的主鍵建立一個主鍵索引。主要功能是在插入資料時做去重滿足主鍵約束，以及根據主鍵進行過濾。主鍵去重是資料插入的關鍵路徑。TAE需要在以下三個方面做出權衡：

1. 查詢效能
2. 記憶體使用
3. 跟上述資料佈局的匹配

從索引的粒度來看，TAE可以有兩類，一類是表級索引，另一類是segment級。例如，可以有一個表級的索引，或者每個segment有一個索引。TAE的表資料由多個segment組成，每個segment的資料都經歷了從L1到L3，從無序，通過壓縮/merge到有序的過程，這種情況對錶級索引非常不友好。所以TAE的索引是構建在segment級。有兩種型別的segment。一種是可以追加修改的，另一種是不可修改的。對於後者，segment級索引是一個兩級結構，分別是bloomfilter和zonemap。對於bloomfilter有兩種選擇，一種是基於segment的bloomfilter，另一種是基於block的bloomfilter。當索引可以完全駐留在記憶體中時，基於segment的是一個更好的選擇。一個可追加修改的segment至少由一個可追加的塊加上多個不可追加的塊組成。可追加的block索引是一個常駐記憶體的ART-tree加上zonemap，而不可追加的則是bloomfilter加上zonemap。

Buffer Manager

嚴肅的儲存引擎需要Buffer Manager實現對記憶體的精細化控制。儘管Buffer Manager原理上只是一個LRU Cache，但是沒有資料庫會直接採用作業系統Page Cache來取代Buffer Manager，尤其是TP類資料庫。TAE用Buffer Manager管理記憶體buffer，每個buffer node是固定大小，它們總共被劃分到4個區域：

1. Mutable：固定size的buffer，用來存放L0的transient column block
2. SST：給L1和L2的block使用
3. Index：存放索引資訊
4. Redo log：用來服務事務未提交資料，每個事務的local需要至少一個Buffer

Buffer Manager的每個buffer node有Loaded和Unloaded 兩種狀態，當使用者請求buffer manager對一個buffer node 進行Pin操作時，如果該node處於Loaded狀態，那麼它的引用計數會增加1，如果節點處於Unloaded狀態，它將從硬碟或遠端儲存讀取資料，增加節點引用計數。當記憶體沒有剩餘空間時，將採用LRU策略把一些buffer node換出記憶體以騰出空間。當使用者解除安裝Unpin一個node時，只需呼叫節點控制代碼的Close。如果引用次數為0，則該節點將成為被換出記憶體的候選節點，引用次數大於0的節點永遠不會被換出。

WAL和日誌回放

如前所述，列存引擎的WAL設計會比行存更加複雜。在TAE中，redo log不需要記錄每個寫操作，但必須在事務提交時記錄。TAE通過使用Buffer Manager來減少io的使用，對於那些時間不長，可能因為各種衝突而需要回滾的事務，避免任何IO事件。它也可以支援長的或大的事務。TAE的WAL的Log Entry Header採用如下的格式：

Item	Size(Byte)
GroupId	4
LSN	8
Length	4
Type	1

事務Log Entry包含如下型別：

Type	Datatype	Value	Description
AC	int8	0x10	完整的寫操作的提交事務
PC	int8	0x11	由部分寫操作組成的已提交事務
UC	int8	0x12	未提交的事務的部分寫操作
RB	int8	0x13	事務回滾
CKP	int8	0x40	Checkpoint

大多數事務只有一個Log Entry。只有那些長的或大的事務可能需要記錄多個Log Entry。所以一個事務的日誌可能是1個以上UC型別的日誌條目加上一個PC型別的Log Entry，或者只有一個AC型別的Log Entry。TAE為UC型別的Log Entry分配了一個專用Group。下圖是六個已提交事務的事務日誌。

一個事務Log Entry的Payload包括多個transaction node，正如圖中所示。transaction node包含有多種型別，比如DML的Delete，Append，Update，DDL的Create/Drop Table，Create/Drop Database等。一個node是一個原子命令，它可以理解為一個已提交Log Entry的sub-entry的索引。正如在Buffer Manager部分所提到的，所有活動的事務共享固定大小的記憶體空間，該空間由Buffer Manager管理。當剩餘空間不足時，一些transaction node將被解除安裝(Unload)。如果是第一次解除安裝node，它將作為一個Log Entry儲存在Redo Log中，而當載入時，相應的Log Entry將從Redo Log回放。這個過程舉例說明如下：

圖中\(TN_{1-1} \)表示事務Txn1的第一個transaction node。在一開始，Txn1在Buffer Manager中註冊transaction node \(TN_{1-1} \) ，並寫入資料\(W_{1-1} \) ：

1. Txn2註冊transaction node \(TN_{2-1} \)，並寫入資料\(W_{2-1} \)，將\(W_{1-2} \)加入\(TN_{1-1} \)
2. Txn3註冊transaction node \(TN_{3-1} \)，並寫入資料\(W_{3-1} \)
3. Txn4註冊transaction node \(TN_{4-1} \)，並寫入資料\(W_{4-1} \)，將\(W_{2-2} \)加入\(TN_{2-1} \)
4. Txn5註冊transaction node \(TN_{5-1} \)，並寫入資料\(W_{5-1} \)
5. Txn6註冊transaction node \(TN_{6-1} \)，並寫入資料\(W_{6-1} \)，將\(W_{3-2} \)加入\(TN_{3-1} \)，將\(W_{2-3} \)加入\(TN_{2-1} \)，此時有事務發生提交，將Commit資訊\(C_{5} \)加入\(TN_{5-1} \) ，建立一個Log Entry，將\(C_{4}\) 加入\(TN_{4-1} \)，建立對應的Log Entry
6. 在Buffer Manager中取消註冊\(TN_{4-1} \)和\(TN_{5-1} \)。在將\(W_{3-3} \)寫入\(TN_{3-1} \)之前，記憶體空間不足，\(TN_{2-1} \)被Buffer Manager選為可以evict的候選，它被解除安裝到WAL作為Log Entry存入。將\(W_{3-3} \)寫入\(TN_{3-1} \)，Txn2在Buffer Manager註冊\(TN_{2-2} \)並寫入\(W_{2-4} \)，此時有事務發生提交，寫入Commit資訊\(C_{1} \) 到\(TN_{1-1} \)並建立對應的Log Entry，寫入\(C_{6} \) 到\(TN_{6-1} \)並建立對應的Log Entry。將\(W_{5-2} \)寫入\(TN_{2-2} \)，給\(TN_{2-2} \)增加\(A_{2} \)並建立對應的Log Entry

通常情況下，Checkpoint是一個安全點，在重啟期間，狀態機可以從這個安全點開始應用Log Entry。Checkpoint之前的Log Entry不再需要，將在適當的時候被物理銷燬。一個Checkpoint可以代表它所指示範圍內的資料等價物。例如，\(CKP_{LSN-11}\)(-∞, 10]]等價於從\(Entry_{LSN=1}\)到\(Entry_{LSN=10}\)的Log Entry，該範圍內的日誌已不再需要。重啟時從最後一個Checkpoint \(CKP_{LSN-11}\)(-∞, 10]]開始重放即可。TAE由於列存的原因，需要一個二級結構記錄最後一個Checkpoint資訊，在WAL上用Group來區分。

TAE的實現，將WAL和日誌回放的部分，專門抽象成獨立的程式碼模組logstore，它對底層日誌的存取做了抽象，可以對接從單機到分散式的不同實現，在物理層，logstore所依賴的行為類似訊息佇列語義。從MatrixOne 0.6版本開始，系統架構將演進到雲原生版本，對應的日誌服務將以shared log形式獨立執行，因此屆時TAE的logstore將略做修改，直接訪問外部的shared log服務而不依賴任何本地儲存。

事務

TAE採用MVCC機制保證事務SI快照隔離機制。對於SI來說，每個事務都有一個一致性讀取檢視Read View，它是由事務開始時間決定的，所以在事務內讀取的資料永遠不會反映其他同時進行的事務所做的改變。TAE提供細粒度樂觀併發控制，只有對同一行和同一列的更新才會發生衝突。事務使用的是事務開始時存在的value版本，在讀取資料時不會對其加鎖。當兩個事務試圖更新同一個value時，第二個事務將由於寫-寫衝突而失敗。

在TAE中，一個表包括多個segment，一個segment是多個事務共同產生作用的結果。所以一個segment可以表示為[\(T_{start}, T_{end}\)] （\(T_{start}\)是最早的事務的提交時間，而\(T_{end}\)最新事務的提交時間）。由於segment可以被壓縮成一個新的segment，並且segment可以被合併成一個新的segment，我們需要在segment的表示上增加一個維度來區分版本 ([\(T_{start},T_{end}\)], [\(T_{create},T_{drop}\)])（\(T_{create} \)是segment的建立時間，而\(T_{drop}\)是segment的刪除時間）。\(T_{drop}\) = 0表示該segment沒有被丟棄。Block的表示方法與segment([\(T_{start},T_{end}\)], [\(T_{create},T_{drop}\)])相同。當事務提交的時候，需要根據提交時間來獲得它的Read View：

\((Txn_{commit}\geqslant T_{create}) \bigcap ((T_{drop}= 0) \bigcup (T_{drop}>Txn_{commit}))\)

segment的產生和變化是由後臺非同步任務進行的，因此TAE將這些非同步任務也納入到事務處理框架中，確保資料讀取的一致性，舉例如下：

\(Block1_{L_{0}}\)在 \(t_{1}\)建立 ，它包含來自 \({Txn1,Txn2,Txn3,Txn4} \)的資料。\(Block1_{L_{0}}\)在\(t_{11}\)開始排序，它的Read View是基線加上一個uncommitted update node。排序和持久化一個block可能需要很長的時間。在提交排序的\(Block2_{L_{1}}\)之前，有兩個已提交事務\({Txn5,Txn6}\)和一個未提交事務\({Txn7}\)。當 \({Txn7}\)在\(t_{16}\)提交時，將會失敗，因為\(Block1_{L_{0}}\)已經被終止了。在\((t_{11}, t_{16})\)之間提交的update node \({Txn5,Txn6}\)將被合併為一個新的update node，它將與\(Block2_{L_{1}}\)在 \(t_{16}\)一起提交。

Compaction過程會終止一系列的block或segment，同時原子化地建立一個新的block或segment（或者建立索引）。與正常的事務相比，它通常需要很長的時間，而且我們不希望在涉及的block或segment上阻止更新或刪除事務。這裡我們擴充套件了Read View的內容，將block和segment的元資料納入其中。當提交一個正常的事務時，一旦檢測到寫操作對應的block（或者segment）的元資料被改變（提交），它就會失敗。對於一個Compaction事務，寫操作包括block（或segment）的軟刪除和新增。在事務的執行過程中，每次寫入都會檢測到寫寫之間的衝突。一旦出現衝突，事務將被提前終止。

MVCC

再來看TAE的MVCC版本資訊儲存機制。資料庫的版本儲存機制決定了系統如何儲存這些版本以及每個版本包含哪些資訊。基於資料Tuple的指標欄位來建立一個latch free的連結串列，稱為版本鏈。這個版本鏈允許資料庫定位一個Tuple的所需版本。因此這些版本資料的存放機制是資料庫儲存引擎設計的一個重要考量。一個方案是採用Append Only機制，一個表的所有Tuple版本都儲存在同一個儲存空間。這種方法被用於Postgres，為了更新一個現有的Tuple，資料庫首先為新的版本從表中獲取一個空的slot，然後，它將當前版本的內容複製到新版本。最後，它在新分配的slot中應用對Tuple的修改。Append Only方案的關鍵決定是如何為Tuple的版本鏈排序，由於不可能維持一個lock free的雙向連結串列，因此版本鏈只指向一個方向，或者從Old到New(O2N)，或者從New到Old(N2O)。另外一個類似的方案稱為Time-Travel，它會把版本鏈的資訊單獨存放，而主表維護主版本資料。第三種方案，是在主表中維護Tuple的主版本，在一個單獨的delta儲存中維護一系列delta版本。這種儲存在MySQL和Oracle中被稱為回滾段。為了更新一個現有的Tuple，資料庫從delta儲存中獲取一個連續的空間來建立一個新的delta版本。這個delta版本包含修改過的屬性的原始值，而不是整個Tuple。然後資料庫直接對主表中的主版本進行In Place Update。

這些方案各有不同的特點，影響它們在OLTP工作負載中的表現。對於LSM Tree來說，由於它天然就是Append-only結構，因此跟第一種較接近。只是版本鏈的連結串列未必會體現。例如RocksDB，所有的寫操作都是後期Merge，因此自然也就是Key的多版本（不同的版本可能位於不同的Level）。在更新量並不大的時候，這種結構簡單，很容易達到較好的效能。TAE則目前選擇了第3種方案的變種，如下圖所示。

這主要是出於以下考慮：在更新量巨大的時候，LSM Tree結構的舊版本資料會引起較多的讀放大，而TAE的版本鏈是由Buffer Manager維護，在需要被換出的時候，它會跟主表資料合併，重新生成新的block。因此在語義上，它是In-Place Update，但實現上，則是Copy On Write，這對於雲上儲存是必須的。重新生成的新block，它的讀放大會較少，這對於發生頻繁更新後的AP查詢會更有利，目前在列存中採用類似機制的還有DuckDB。當然，另一方面，語義上的In Place Update也帶來了額外的困難，這在未來的TAE系列文章中會逐步介紹。

從本質上來說，TAE作為一個全新設計和實現的儲存引擎，距離成熟還需要時間，但是它的每個元件，都是完全從零搭建，並不斷快速演進中。後邊的系列文章，我們將逐步就TAE在存算分離體系下的調整逐步展開分享。