內存數據庫解析與主流產品對比（三）

作者：實驗室小陳/大數據開放實驗室

在上一篇文章《內存數據庫解析與主流產品對比（二）》中，我們從數據組織和索引的角度介紹了內存數據庫的特點和幾款產品的技術實現。本文將繼續解析內存數據庫，從並發控制、持久化和查詢處理的角度介紹幾款技術，帶來更多維度、更細緻的內存數據庫技術討論。

— 數據庫管理系統中的並發控制—

1. 內存數據庫並發控制的兩種策略

a. 多版本的並發控制

內存數據庫中的並發控制主要採用兩類策略：1. 多版本的並發控制；2. 分Partition處理。並發控制機制可以分為樂觀和悲觀兩種類型。悲觀並發控制則認為進程競爭資源總是存在的，因此訪問時先加鎖，訪問完再釋放；樂觀並發控制認為大多數情況不需要競爭資源，只在最後提交前檢查是否存在衝突，有衝突就回滾，沒有就提交。

樂觀並發控制大多數不採用基於鎖的技術實現，並且通常是多版本的。多版本意味着每次更新都會產生新的版本，讀操作根據可見範圍選取合適的老版本，讀操作不阻塞寫操作，所以並發程度比較高。其缺點是會產生額外開銷，例如更新要創建新版本，而且隨着版本越來越多，還需要額外開銷收回老版本。內存數據庫多採用樂觀的多版本並發控制機制，相比於基於鎖的悲觀並發控制其優勢是開銷較小，而且支持並發程度較高的場景；缺點是在有大量寫競爭的場景下，事務間衝突概率比較高時，大量事務會失敗和回滾。

b. 分Partition處理

內存數據庫並發控制的另外一類策略是把數據庫分成多個Partition，每個Partition採用串行方式處理事務。優勢是單Partition業務的執行沒有用於並發控制的額外開銷，缺點是存在跨Partition事務時系統的吞吐率會直線下降。因此，如果不能保證所有業務都是單Partition進行，將導致性能不可預測。

2. 多版本並發控制之 Hekaton

Hekaton採用樂觀的多版本並發控制。Transaction開始時，系統為事務分配讀時間戳，並將Transaction標記為active，然後開始執行事務，在操作過程中系統記錄被讀取/掃描/寫入的數據。隨後，在Pre-commit階段，先獲取一個結束的時間戳，然後驗證讀和掃描數據的版本是否仍然有效。如果驗證通過，就寫一個新版本到日誌，執行Commit，然後把所有的新版本設置為可見。Commit之後，Post-Processing記錄版本時間戳，之後Transaction才真正結束。
image.png

a. Hekaton 的事務驗證

i) Read Stability：

Hekaton系統能夠保證數據的讀穩定性（Read Stability），比如交易開始時讀到的每條記錄版本，在Commit時仍然可見，從而實現Read Stability。

ii) Phantom Avoidances：

Phantom指一個事務在開始和結束時執行相同的條件查詢，兩次結果不一樣。出現幻影的原因是該事務執行過程中，其他事務對相同數據集進行了增加/刪除/更新操作。應該如何避免幻影現象呢？可通過重複掃描，檢查所讀取的數據是否有新版本，保證記錄在事務開始時的版本和在結束時一致。

Hekaton並發控制的好處在於，不需要對Read-Only事務做驗證，因為多版本能夠保證事務開始時的記錄版本在結束時依然存在。對於執行更新的事務，是否做驗證由事務的隔離級別決定。例如如果快照隔離級別，就不需要做任何驗證；如果要做可重複讀，就要做Read Stability；如果是串行化隔離級別，既要保證Read Stability，又要保證Phantom Avoidance。

b. Hekaton的回收策略

Hekaton中的回收任務並不由獨立的線程處理，而是每個事務自己回收。如下圖所示，Transaction ID為250的事務結束時間戳為150且狀態為terminated，此時會有一個Write Set獲取所有老版本，並判斷當前所有active的Transaction的開始時間戳是否大於ID為250的事務結束時間，即150。如果都大於150，說明不可能再基於時間戳早於150的舊版本進行修改，因而由事務回收舊版本，這部分工作是每個線程在處理Transaction時的額外工作。
image.png

3. 多版本並發控制之Hyper

Hyper的並發控制和Hekaton的區別主要有以下三點：1. 直接在記錄位置進行更新，通過undo buffer來保存對數據的修改，數據和所有修改被鏈接在一起；2. 驗證是根據最近的更新與讀的記錄進行比較來實現（後續會涉及到）；3. 串行化處理commit，對提交的事務進行排序，並依次處理。
image.png
在事務驗證方面，Hyper的驗證需要在日誌中記錄Read Predictates，包括查詢或Range Scan，而且要記錄插入、刪除和更新的記錄。在Hyper模式中，插入/刪除/更新通過對應的Undo Buffer獲悉被修改過的記錄，所以記錄改動對於Hyper而言是容易的。

對於每個Transaction，只需要比較該事務從開始到Commit之間，是否存在其他Transaction對滿足搜索條件的數據集進行過增/刪/改，從而判斷是否存在幻影現象，如果存在，就直接終止事務。

4. 多版本並發控制之HANA和HStore/VoltDB

HANA並行控制方式比較簡單，採用悲觀的多版本控制，由行級鎖保護數據結構，每行由時間戳決定每個版本的可見範圍。每個Transaction在更新或刪除時都需要申請寫鎖，而且要做死鎖檢測。

HStore/VoltDB是一個Partition系統，鎖的粒度很粗，每個Partition對應一把鎖，因此Transaction在某節點上執行時，需要拿到該節點所有資源。一旦一個事務可能涉及到兩個Partition，就需要把兩個Partition的鎖都拿到。所以Partition系統的優點是單Partition處理速度非常快，缺點是多Partition效率很低。同時，系統對於負載的偏斜非常敏感，如果有熱點數據，那麼熱點數據就構成系統瓶頸。

5. 多版本並發控制之負載預知

假設一個工作負載中，事務需要讀和寫的數據集可以提前獲得，就可以在執行前確定所有事務的執行順序。Calvin就是基於這樣的假設設計的VLL (Very Lightweight Locking）超輕量級鎖數據庫原型系統。通用場景的工作負載是無法提前知道讀寫集合的，但在存儲過程業務的應用中，可以提前確定讀寫集合，對於這些場景就可以考慮類似Calvin的系統。

— 數據庫管理系統中的持久化技術—

對於內存數據庫而言，和基於磁盤的數據庫相同也需要日誌和Checkpoint。Checkpoint的目的是恢復可以從最近的檢查點開始，而不需要回放所有數據。因為Checkpoint涉及寫入磁盤的操作，所以影響性能，因此要盡量加快相關的處理。

一個不同是內存數據庫的日誌和Checkpoint可以不包含索引，在恢復時通過基礎數據重新構造索引。內存數據庫中的索引在恢復時重新構造，構造完成後也放在內存中而不用落盤，內存索引數據丟失了再重構即可。另外一個不同是內存數據庫Checkpoint的數據量更大。面向磁盤的數據庫在Checkpoint時，只需要把內存中所有Dirty Page寫到磁盤上即可，但是內存數據庫Checkpoint要把所有數據全部寫到磁盤，數據量無論多大都要全量寫一遍，所以內存數據庫Checkpoint時寫入磁盤的數據遠大於基於磁盤的數據庫。

Hekaton Checkpoint

對於持久化的性能優化，第一要保證寫日誌時的高吞吐量和低延遲，第二要考慮恢復時如何快速重構整個數據庫。Hekaton的記錄和索引存放在內存，所有操作寫日誌到磁盤。日誌只記錄數據的更新，而不記錄索引的更新。進行Checkpoint時，Hekaton會從日誌中恢復，並根據主鍵範圍並行處理。如下圖，分三個主鍵範圍：100199、200299、300~399，綠色代表數據，紅色代表刪除的記錄（單獨保存被刪除的文件）。在恢復時，Hekaton用並行算法在內存中重構索引和數據，過程中根據刪除記錄過濾數據文件，去除被刪除的數據，然後從Checkpoint點開始，根據日誌回放數據。
image.png

其他系統的Checkpoints

1.採用Logic Logging的系統如H-Store/VoltDB，即不記錄具體的數據改動，而是記錄執行過的操作、指令。它的優勢是記錄的日誌信息比較少。寫日誌時，HStore/VoltDB採用COW(Copy-on-Write)模式，即正常狀態是單版本，但在寫日誌時會另外「複製」一個版本，待寫完再合併版本。

2.另一種是定期把Snapshot寫入磁盤（不包括索引），比如Hyper就是基於操作系統Folk功能來提供Snapshot。

— 數據庫管理系統中的查詢處理—

傳統的查詢處理採用火山模型，查詢樹上的每個節點是一個通用的Operator，優勢在於Operator可以任意組合。但Operator拿到的記錄只是一個位元組數組，還需要調用另一個方法來解析屬性以及屬性類型。如果這種設計放到內存數據庫中，屬性以及類型的解析都是在Runtime而非編譯時進行的，會對性能產生影響。

另外對於get-next，如果有百萬個數據就要調用百萬次，同時get-next通常實現是一個虛函數，通過指針調用，相比直接通過內存地址調用，這些都會影響性能。此外，這樣的函數代碼在內存中的分佈是非連續的，要不斷跳轉。綜上，傳統DBMS的查詢處理方式在內存數據庫當中並不適用，尤其體現在在底層執行時。
image.png
內存數據庫通常採用編譯執行的方式，首先對查詢進行解析，然後優化解析後的語句，並生成執行計劃，然後根據模板對執行計划進行編譯產生可執行的機器代碼，隨後把機器代碼加載到數據庫引擎，執行時直接調用。
image.png
下圖是對不同查詢方式的耗時分析，可以看出編譯執行方式中Resource Stall的佔比很少。
image.png
另外一張圖解釋了目前的CPU架構實現，L2 Cache和主存之間存在Hardware Pre-fetcher。L2 Cache分為指令Cache和Data Cache，指令Cache會由Branch Prediction實現分支預測，Data Cache會由基於Sequential Pattern的Pre-fetcher實現預測。因此，數據庫系統的設計需要考慮該架構下如何充分發揮Pre-fetcher功能，讓Cache可以不斷為 CPU計算單元提供指令和數據，避免出現Cache Stall。
image.png

Hekaton編譯查詢處理

Hekaton的編譯採用T-SQL存儲過程，編譯的中間形式叫做MAT Generator，生成最終的C代碼在編譯器中執行。它產生的庫和通用Operator的區別在於：通用Operator需要在運行時解釋數據類型；而Hekaton編譯方式是把表的定義和查詢編譯在一起，每個庫只能處理對應的表而不能通用，自然就能拿到數據類型，這樣的實現能獲得3~4倍的性能提升。
image.png

HyPer和MemSQL編譯查詢處理

HyPer的編譯方式是把查詢樹按照Pipeline的分割點每段編譯。而MemSQL採用LLVM做編譯，把MPI語言編譯成代碼。
image.png
下圖是一個對MemSQL性能的測試。沒有採用編譯執行時，MemSQL兩次執行相同查詢的時間都是0.05秒；如果採用編譯執行，第一次耗時0.08秒，但是再執行時耗時僅0.02秒。
image.png
image.png

— 其他內存數據庫系統—

除了之前提到的幾種內存數據庫外，還有其他一些著名的內存DBMS出現。

i) SolidDB：

誕生於1992年的混合型數據庫系統，同時具備基於磁盤和內存的優化引擎，使用VTRIE（Variable-length Trie）樹索引和悲觀鎖機制進行並發控制，通過Snapshot Checkpoints恢復。

ii) Oracle Times Ten：

早期是惠普實驗室名為Smallbase的研究項目，在2005年被Oracle收購，現在多作為大型數據庫系統的前端內存加速引擎。Oracle Times Ten支持靈活部署，具有獨立的DBMS引擎和基於RDBMS的事務緩存；在BI工作時支持Memory Repository，通過Locking進行並發控制；使用行級Latching處理寫衝突，採用Write-Ahead Logging和Checkpoint機制提高持久性。

iii) Altibase：

於1999年在韓國成立，在電信、金融和製造業應用廣泛。Altibase在Page上存儲記錄，以Page為粒度進行Checkpoint且兼容傳統DBMS引擎；支持多版本並發控制，使用預寫日誌記錄和檢查點實現持久性和恢復能力，通過Latching-Free對Page的數據進行Checkpoint。

iv) P*Time:

21世紀起源於韓國，2005年出售給SAP，現在是SAP HANA的一部分。P*Time具備極佳的性能處理，對日誌記錄使用差分編碼（XOR），採用混合存儲布局，支持大於內存（Larger-than-Memory）的數據庫管理系統。

— 本文小結—

每一個數據庫系統都是針對特定的硬件環境設計，基於磁盤的數據庫系統面臨CPU單核、內存小、磁盤慢的場景設計。而內存數據庫以內存為主存，不需要再重複讀寫磁盤，磁盤I/O不再是性能瓶頸，而要解決其他瓶頸，比如：1. Locking/Latching的開銷；2. Cache-Line Miss，即如果數據結構定義的不夠好或在內存中組織的不好，無法匹配CPU的層級緩存，會導致計算性能變差；3. Pointer Chasing，即需要另一個指針解釋，或者查另外的表才能查到記錄地址，也是主要的性能開銷。此外，還有Predicate Evaluation計算、數據遷移/存儲時的大量拷貝、分佈式系統應用與數據庫系統的網絡通信等開銷。

在本專欄中，我們介紹了傳統基於磁盤的DBMS和內存數據庫的特點，並從數據組織、索引、並發控制、語句處理編譯、持久化幾個方面對內存數據庫與基於磁盤數據庫的相同和差異性進行了介紹：

1. 數據組織：

內存數據庫中，把記錄分成定長和變長管理，不需要數據連續存儲，用指針替代了Page ID + Offset的間接訪問；

2. 索引優化：

考慮面向內存中的Cach Line優化、快速的內存訪問等Latch-Free技術，以及索引的更新不記錄日誌等；

3. 並發控制：

可以採用悲觀和樂觀的並發控制方式，但是與傳統基於磁盤數據庫的區別是，內存數據庫鎖信息和數據綁定，而不用單獨的Lock Table管理；

4. 查詢處理：

內存數據庫場景下的順序訪問和隨機訪問性能差別不大。可以通過編譯執行提高查詢性能；

5. 持久化：

仍然通過WAL（Write-Ahead Logging）做Logging，並採用輕量級的日誌，日誌記錄的內容盡量少，目的是降低日誌寫入磁盤延遲。

內存數據庫從1970s開始出現經歷了理論成熟、投入生產、市場驗證等發展環節。隨着當前互聯網秒殺、移動支付、短視頻平台等高並發、大流量、低時延的平台出現，對於數據庫性能提出了巨大需求和挑戰。同時，內存本身在容量、單位價格友好度上不斷提升，以及近期非容失性存儲（NVM）的發展，促進了內存數據庫的發展，這些因素使得內存數據庫在未來有着廣闊的市場和落地機會。

註：本文相關內容參照以下資料：

  1. Pavlo, Andrew & Curino, Carlo & Zdonik, Stan. (2012). Skew-aware automatic database partitioning in shared-nothing, parallel OLTP systems. Proceedings of the ACM SIGMOD International Conference on Management of Data. DOI: 10.1145/2213836.2213844.

  2. Kemper, Alfons & Neumann, Thomas. (2011). HyPer: A hybrid OLTP&OLAP main memory database system based on virtual memory snapshots. Proceedings – International Conference on Data Engineering. 195-206. DOI: 10.1109/ICDE.2011.5767867.

  3. Faerber, Frans & Kemper, Alfons & Larson, Per-Åke & Levandoski, Justin & Neumann, Tjomas & Pavlo, Andrew. (2017). Main Memory Database Systems. Foundations and Trends in Databases. 8. 1-130. DOI: 10.1561/1900000058.

  4. Sikka, Vishal & Färber, Franz & Lehner, Wolfgang & Cha, Sang & Peh, Thomas & Bornhövd, Christof. (2012). Efficient Transaction Processing in SAP HANA Database –The End of a Column Store Myth. DOI: 10.1145/2213836.2213946.

  5. Diaconu, Cristian & Freedman, Craig & Ismert, Erik & Larson, Per-Åke & Mittal, Pravin & Stonecipher, Ryan & Verma, Nitin & Zwilling, Mike. (2013). Hekaton: SQL server’s memory-optimized OLTP engine. 1243-1254. DOI: 10.1145/2463676.2463710.

Tags:

VirMach 便宜 VPS

QNews

QNews