觀點 | 阿裡資深技術專家：優秀的資料庫存儲引擎應具備哪些能力？

導讀

本文作者是阿裡巴巴OLTP資料庫團隊資深技術專家——曲山。作為自研高性能、低成本存儲引擎X-Engine的負責人，曲山眼中的優秀關系型資料庫存儲引擎應該具備哪些能力呢？

正文

資料庫核心按層次來分，就是兩層：SQL & Storage。SQL Layer負責将你輸入的SQL statement通過一系列步驟(parse/resolve/rewrite/optimize…)轉換成實體執行計劃，同時負責計劃的執行，執行計劃通常是一顆樹的形式，其中樹的葉子節點(執行器算子)部分往往負責單表的資料操作，這些操作算子就要在storage layer來執行了。

是以，一個資料庫存儲引擎的主要工作，簡單來講就是存取資料，但是前提是保證資料庫的ACID(atomicity/consistency/isolation/durability)語義。存儲引擎對外提供的接口其實比較簡單，主要就是資料寫入/修改/查詢，事務處理(start transaction/commit/rollback…)，修改schema對象/資料字典(可選), 資料統計，還有一些周邊的運維或資料導入導出功能。

僅僅從功能上來說，要實作一個存儲引擎似乎并不困難，如今也有很多Key-Value Store搖身一變就成為了資料庫存儲引擎，無非是加上一套事務處理機制罷了。但是作為資料庫的底盤，一個成熟的存儲引擎必須要考慮效率，如何高效(性能/成本最大化)的實作資料存取則成了在設計上做出種種權衡的主要考量。可以從存儲引擎的幾個主要元件來讨論：

資料組織

資料在記憶體和磁盤中的組織方式很大程度上決定了存取的效率，不同的應用場景選擇也不同，典型的如：

1. 資料按行存儲(NSM)，對事務處理比較友好，因為事務資料總是完整行寫進來， 多用于OLTP場景。
2. 按列存儲(DSM)，把tuples中相同的列值實體上存儲在一起，這樣隻需要讀取需要的列，在大規模資料掃描時減少大量I/O。另外列存做壓縮的效果更好，适合OLAP場景，但是事務處理就不那麼友善，需要做行轉列。是以大部分AP資料庫事務處理效率都不怎麼高，某些甚至隻支援批量導入。
3. 混合存儲(FSM)，行列混合布局，有把資料先按行分組(Segment, SubPage)，組内使用DSM組織，如PAX, RCFile，也有先按列分組(Column Group)，組内指定的列按NSM組織，如Peloton的Tile。此種格式試圖結合NSM和DSM兩者的優點，達到處理混合負載(HTAP)的目的，但是同時也繼承了兩者的缺點。

是以做存儲引擎，一開始就要面臨選擇何種存儲格式的問題。即便標明了大類，每種格式中也有無數的細節需要考慮，每種資料類型的字段如何編碼(Encoding)，行存中null/not null如何存儲，是否需要列索引加快project operation，是否需要對列值進行重排，列存如何進行資料壓縮，等等，都要存儲空間和存取速度中做平衡。

現代資料庫為了應對複雜的應用場景，往往使用不隻一種存儲格式，比如Oracle有In-memory Column Store在記憶體中将行存的頁面轉換為列存方式的page，用來加速複雜查詢。

當資料標明存儲格式以後，還要選擇資料在磁盤和記憶體中的聚集方式。以按行存儲為例，大部分存儲引擎使用固定大小的頁面(page)來存儲連續的若幹行。當然，資料行如何連續排列，有堆表(随機)和索引組織表(按索引序)兩種，現在較為流行的LSM-Like的存儲引擎使用不定大小的頁面(稱為DataBlock)，隻支援按主鍵索引序聚集；這兩種方式主要差別在于前者被設計為可更新的，每個page中會留有空間，後者是隻讀的，資料緊密存儲不帶padding，便于壓縮。兩者的差別實際上是因為事務處理機制有較大的差別導緻的，後面再論。

對于In-Memory Database來說，資料組織的方式會有較大差別，因為不需要在記憶體和持久化存儲中交換資料，記憶體中一般不會使用page形式，而是直接使用索引存儲結構(比如B+Tree)直接索引到記錄(tuples)，無需page這一層間接引用，減少cpu cache miss。

緩存管理

緩存的粒度一般是page，關鍵在于緩存替換算法。目前用的比較廣泛的LRU,LFU,ARC..以及各種變種的算法都有在資料庫中使用。另外還有一個是如何更有效的管理記憶體的問題，這點上，定長的page會比不定長的更有優勢。

當然還要考慮各種query pattern對cache的影響，如果單行查詢較多，選用更細粒度(比如row)的cache會更有效率，但是淘汰的政策會更複雜，很多新的研究開始嘗試引入機器學習的方法來優化cache淘汰算法，以及有效的管理cache.

事務處理

存儲引擎之核心，保證資料庫的ACID。要保證D，大家的做法差不多，都是寫WAL(Write Ahead Log)來做recovery，關鍵是如何高效的實作ACI，也就是所謂的多版本并發控制(MVCC)機制。

MVCC的完整實作比較複雜，暫不詳細闡述，這裡面的關鍵在于如何處理并發執行過程中的資料沖突(data race)，包括寫寫沖突，讀寫沖突；因為資料庫的負載一般是讀多寫少的，要做到高效，隻讀事務不能被讀寫事務阻塞，這就要求我們的寫不能直接去更新目前的資料，而是要有一套維護多版本資料的能力，目前的存儲引擎管理多版本資料的辦法無非兩種：

1. 寫入資料原地更新，被更新的舊版本寫到undo鍊中，寫入代價大，事務處理複雜, 但是回收舊版本資料高效。
2. 寫入資料不直接更新原來的資料，而是追加為新版本，寫入代價小，但是讀，尤其是掃描需要讀取層次較多，更為嚴重的問題是回收舊版本的資料需要做compact，代價很大。

前一種稱為ARIES算法比大多數主流資料庫存儲引擎使用，後一種稱為LSM-Tree的結構也被很多新存儲引擎使用，受到越來越多的關注。

Catalog

與KV store有差別的是，資料庫是有嚴格的schema的，是以多數存儲引擎中的記錄都是有結構的，很多KV store在作為資料庫存儲引擎時，都是在中間做一層轉換，将上層處理的tuples以特定的編碼方式轉換為binary key-value，寫入KVStore，并在讀取到上層後，依靠schema解釋為tuples格式供上層處理。

這種方法當然可以工作，但是諸多優化無法實施：a. 資料疊代必須是整行，即便隻需要其中一列，序列化/反序列化開銷是免不了的。b. project和filter的工作無法下放到存儲層内部進行處理; c. 沒有列資訊，做按列編碼，壓縮也不可能。d. schema change隻能暴力重整資料… 是以要做到真正的高效，越來越多的存儲引擎選擇完全感覺schema，存儲細微結構。

總結

以上所探讨的，還隻是單機資料庫的存儲引擎幾個大的問題，而現代資料庫對存儲引擎提出了更高的要求，可擴充，高可用已經成為标配，現在要考慮的是如何給你的存儲引擎加上分布式的能力，而這又涉及到高可用一緻性保證，自動擴充，分布式事務等一系列更為複雜的問題，這已遠超出本文的範疇，需要另開篇章。

最後介紹下我們正在開發的阿裡自研分布式資料庫X-DB，其中的存儲引擎就使用了我們自研的X-Engine。X-Engine使用了一種對資料進行分層的存儲架構，因為目标是面向大規模的海量資料存儲，提供高并發事務處理能力和盡可能降低成本。

我們根據資料通路頻度(冷熱)的不同将資料劃分為多個層次，針對每個層次資料的通路特點，設計對應的存儲結構，寫入合适的儲存設備。X-Engine使用了LSM-Tree作為分層存儲的架構基礎，并在這之上進行了重新設計。

簡單來講，熱資料層和資料更新使用記憶體存儲，利用了大量記憶體資料庫的技術(Lock-Free index structure/append only)提高事務處理的性能，我們設計了一套事務處理流水線處理機制，把事務處理的幾個階段并行起來，極大提升了吞吐。而通路頻度低的冷(溫)資料逐漸淘汰或是合并到持久化的存儲層次中，結合目前豐富的儲存設備層次體系(NVM/SSD/HDD)進行存儲。

我們對性能影響比較大的compaction過程做了大量優化，主要是拆分資料存儲粒度，利用資料更新熱點較為集中的特征，盡可能的在合并過程中複用資料，精細化控制LSM的形狀，減少I/O和計算代價，并同時極大的減少了合并過程中的空間放大。同時使用更細粒度的通路控制和緩存機制，優化讀的性能。當然優化是無止境的，得益于豐富的應用場景，我們在其中獲得了大量的工程經驗。

X-Engine現在已經不隻一個單機資料庫存儲引擎，結合我們的X-Paxos(分布式強一緻高可用架構), GMS(分布式管理服務), 和X-Trx(分布式事務處理架構)，已經演變為一個分布式資料庫存儲系統。