1 前言

paper的原文：Mainlining Databases： Supporting Fast Transactional Workloads on Universal Columnar Data File Formats

這篇paper是CMU database group實現的self-driving database的系列paper的其中一篇，主要分享的是如何基於一個通用的列存格式來實現一個in-memory的HTAP系統。noisepage的前身是peloton，與monetdb（荷蘭的CWI開發，open source），HyPer（德國慕尼黑TUM大學開發，已經被Tableau收購）齊名的列式資料庫。

HTAP從工業界目前的實現來看，除了HANA比較另類，基本都是一個行存用來服務TP，一個列存用來服務AP，更細分有2種策略，內部實現行轉列，典型的代表是TiDB，使用者自己做ETL來實現行列轉換，例如Greenplum，TBase。noisepage的實現算是一種學術界的探索，在列存的引擎上同時實現AP和TP。

因為作者在這篇paper中，基於arrow的in-memory的列存做的實現，所以在介紹TP能力實現之前，首先介紹一下arrow，arrow是為了AP的分析效能而生的一個全記憶體的列儲存結構，它下面可以實現對AP或者大資料的各種儲存格式，例如kudu，parquet。

arrow的儲存可以適配打平的表結構，或者層次結構（典型的如樹形結構），為了提升分析效能，對於下圖的2個列的資料表，它在arrow中的儲存格式如右圖所示：

資料按列儲存，並按照8位元組對齊。例如上述的ID，metadata buffer直接指向儲存id值得column buffer。

變長資料透過儲存他們的offset陣列來做跳轉，長度需要計算得到，為當前行的offset與下一行的offset的差值。例如上圖name列，包含一個offsets陣列，和一個values的指標，offsets指向的陣列是name列所在行在column buffer中的offset，第1行的offset為0，第2，3行的offset都是3。

使用一個額外的bitmap buffer來標識其中的null值。

2 系統概覽

noisepage透過multi-versioned delta storage來實現事務引擎，其中事務版本資訊與實際資料是分開儲存，整體架構如下圖：

tuple的delta儲存在本地事務的buffer中（不是arrow中），即上圖的transaction context中的資料，buffer分成2種類似redo和undo，與mysql中的概念類似，redo是實際要修改後期望的值，用來回放，undo是寫入（修改）前的值，當事務還沒完成的時候用來提供給其他併發的時候提供讀服務，在事務失敗的時候用來回滾。

資料儲存在data blocks中，data blocks即上述的arrow結構，並且這個table有一個額外的column用來儲存該行的version chain指標，這一列對外部訪問是不可見的，只是用來做可見性判斷。

對於資料的讀寫，noisepage抽象除了一層data table layer，透過data table api對外提供資料儲存引擎的讀寫服務，對於讀操作，data table layer透過讀version chain並找到正確的版本資料返回，對於寫操作，data table layer在修改arrow中的資料之前，會先把資料複製出來到undo，並構建好對應的version chain。

以上圖例如舉例：transaction 2插入tuple （id=12， val=‘‘foo’’），首先redo裡面會儲存插入的tuple，由於之前沒有資料，所以undo裡面的valid為false，arrow的data blocks裡面對應的version chain pointer指向undo；transaction 1修改id = 13，它會首先把這行修改前的值id = 12寫入undo，然後修改arrow的data block中的值為id = 13，並把這條undo加入到version chain，這個時候的version chain是：data block（id = 13） -> transaction 1‘ undo（id = 12） -> transaction 2’ undo（ valid = false），從上圖可以看到事務資訊是ts和日誌儲存在一塊。

為了處理資料大量寫入的情況，undo buffer是固定大小的記憶體，不夠的時候會動態申請，並且使用linked list來組織這些undo buffer。

2。1 OCC

noisepage這裡使用的是optimistic concurrency control協議，即先寫，提交的時候再檢查是否衝突，衝突則迴歸，與之對應的是悲觀事務，寫之前先加鎖，修改完之後再釋放鎖，其他事務等鎖避免衝突回滾。OCC對於併發衝突嚴重的場景不友好，併發衝突會導致效能急劇下降，傳統的TP系統都是使用悲觀事務。

每個事務都有一個timestamp（後面簡稱為ts） pair（start，commit），commit的時間戳和start時間戳一樣，只是commit的符號位取反用來標識該事務還沒有提交。每次更新的時候，儲存的是commit ts，讀操作的時候，會獲取當前的最新的ts（記為read ts），遍歷version chain的時候，直到碰到一個ts比read ts還小，對比ts的時候，使用無符號對比，因為未提交的ts的符號位為1，所以未提交的ts都比read ts要大，所以會跳過，直到碰到一個ts小於read ts，那麼該ts一定是已經committed，從而得到正確的版本。還是以上面的例子，例如使用ts=8去讀，tansaction 1的undo的ts是-7，無符號對比的時候，比ts = 8要大，apply transaction 1的undo，並跳過到下一個版本，transaction 2的undo的ts是6，比8小，無需apply undo，最終得到正確的值id = 12。

當事務commit的時候，noisepage使用一個臨界區得到一個commit ts來更新delta記錄裡面的commit ts，並把這個delta記錄加入到log manage的佇列中。在這個臨界區中，不允許新的讀，但是已經開始的事務可以繼續執行。對於abort，noisepage使用undo log來替換在data block中的值，但是他不能從version chain中unlink出來，因為可能會出現髒讀。例如一個活動事務在它abort的時候還沒有把undo的記錄更新回data block就複製了原來data block的資料作為一個新的版本，讀的時候會順著version chain把已經unlink的undo（這個undo）認為可見，相當於髒讀，讀到了未提交的資料。這個case的時序如下：

t1：txn1 更新data block（id = 2）， txn1 undo （id = 1），version chain（->txn1 undo）

t2：txn2 更新data block（id = 3）， txn2 undo（id = 2），version chain（->txn2 undo ->txn1 undo）

t3：txn1 abort，把txn 1 的undo從version chain中unlink

t4： txn2讀到txn1修改的（id = 2）的記錄。

t5：txn1 abort， apply txn1 undo，data block（id = 1）

2。2 abort的處理

abort的傳統的做法是把undo的記錄寫回到data block中，並把version pointer重置回去，但是如果在讀然後更新，例如典型的update id =1 where id > 10類似的sql，在讀完後，再更新中間，有事務修改了資料並abort掉了，這個時候沒法透過 簡單判斷version pointer是否一樣來判斷資料是否被修改過，即所謂的ABA問題，abort的時候，會把version pointer重置回去，但是data block中的值不一定修改回去了。

為了規避這個問題，作者的做法是不是透過把原來的version和值重置回去，而是把undo上的commit ts的符號位取反，即認為這個undo已經apply，這樣做的問題是讀的時候，需要多讀一次這個undo上的記錄，髒資料的回收在GC那一節會講到。

PS：這部分的內容看了很久沒思路，與 @旬飛 討論後豁然開朗，非常感謝。

2。3 blocks的資料組織

tuple資料和事務meta資訊分開儲存帶來一個挑戰，為了實現unique tuple，但是unique可能由多列組成，每列是分開儲存的，沒有儲存在一塊，邏輯上透過hash table來實現unique tuple，這個hash table可能成為系統的瓶頸，因為每次都需要2倍的記憶體訪問，先訪問hash table，得到行號，再讀tuple值。為了解決這個問題，作者把每個block限制為1M，並使用一種“physiological scheme”來組織資料。

資料在每個block被組織成PAX（行列混存）格式，一個tuple的所有列的資料都在這個block，每個block有一個layout物件，由下面3個部分組成：

block中slot的個數

attribute （每行的列值）大小的陣列

每列的offset。

每列和他的bitmap按照8位元組對齊，系統在建立block的時候，會把這個layout計算出來。

每個tuple（行）透過一個TupleSlot來表示，TupleSlot由下面資料組成：

tuple所在block的記憶體地址，起始地址

attribute在block中的邏輯offset

為了把上述2種值用一個64位來表示，低20位用來表示offset，高42位用來儲存block的物理地址。

2。4 GC的實現

GC的作用主要是用來刪除version chain並釋放對應的記憶體，對於被刪除的tuple會在資料轉成arrow的過程中處理，因為version chain相關的資訊都儲存在事務對應的buffer中，所以GC只需要掃描事務對應的buffer（上文提到的undo，redo），不需要去掃arrow格式中的資料。

開始掃描的時候，GC會首先檢查事務引擎的得到最老的活動事務的start ts，比這個ts小的並且已經提交了的是可以安全清理的，GC會對每個事務的version chain做檢測，並釋放對應的version chain上的資料，直接從version chain上unlink物件並釋放是不安全的，因為這個時候可能還有其它的事務正在讀，為了處理這種情況，GC會從事務引擎獲取一個自己的ts，標記為unlink ts，在這個時間之後的事務都不能訪問這個unlink的記錄，當正在執行的事務的start ts比unlink ts要大的時候，這個記錄就可以被刪除。（即保證未來的事務不會繼續訪問，已經訪問的事務能夠繼續做完再清理）

2。5 logging和recovery

持久化的實現是透過WAL和checkpoints，每個事務維護一個redo buffer，提交的時候，會增加一個commit record到redo buffer，並把它放到flush 佇列，日誌管理器會非同步把redo buffer寫入磁碟並持久化，redo buffer也是由多個buffer segment組成，系統會在commit之前把redo 記錄寫入磁碟。如果事務還未提交就crash，而commit記錄沒有被寫入磁碟，在recovery的過程中會忽略commit record。

當commit record新增到flush佇列之後，系統就會認為這個事務被提交了，所有對這個事務的寫操作集合的操作，都是一種“推測”，直到commit record被寫入磁碟。系統會為commit record寫入磁碟後呼叫一個callback，用來通知這個事務被持久化了，直到這個回撥被呼叫，系統才向client傳送 事務執行的結果。透過這種方式，即使有其他的事務因為上述的“推測”，即當前事務的comit record還沒有被持久化，就開始透過讀寫這個事務修改的資料，從而做進一步的修改，也不會生效。callback的函式地址被編碼到commit record裡面，當log manger寫commit record的時候，會把它加入回撥佇列，在fsync（這個函式才真正保證commit record被持久化到儲存上）之後呼叫。系統要求對一個只讀的事務也需要非持久化的commit record，用來保證上述所說的回撥。

一般的資料庫都是需要等這條日誌被持久化之後 才認為事務提交，這裡只要commit record加入到flush佇列之後，就認為事務已經被“commit”，但是在commit record真正持久化之後，才向用戶傳送事務結果。而這個過程中，可能又有其他的事務基於之前被認為已經“commit”的記錄，做了修改，顯然這個時候，如果系統奔潰可能有2個時間點。

第一個事務的commit record還沒有被持久化，recovery的時候，第一個和第二個事務的所有的修改都不可見，能保證系統的一致性。

第一個事務的commit record已經被持久化，但是第二個事務的修改commit record未被持久化。顯然第一個事務的修改生效，第二個事務的修改不生效。也是能保證系統的一致性。

3 BLOCK TRANSFORMATION

arrow格式實現事務一個問題就是寫放大，作者使用了一個靈活的arrow格式來實現高效的寫入，當資料變冷（不再頻繁做修改）的時候，透過一個輕量級的轉換把一個block放入到arrow格式中。這個轉換不是這篇paper的核心，所以細節不再複述。

4 總結

這篇paper的核心是怎麼基於arrow的列存格式，來實現一個TP的事務引擎，但是從他對事務協議OCC的選擇，並不是面向典型的TP：高併發，且衝突嚴重的場景，作者還有其它的幾篇paper，特別是執行引擎的最佳化，“Relaxed Operator Fusion for In-Memory Databases： Making Compilation， Vectorization， and Prefetching Work Together At Last”，典型的面向分析場景。綜合來講適合主要面向分析，但是具備完整事務能力的場景，這個定位與我們組當前的產品

AnalyticDB PostgreSQL

是吻合的，後續值得重點關注。