記憶體資料庫解析與主流產品對比（二）

• 2020 年 11 月 26 日
• AI
• 資料庫系統

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

在上一篇文章《記憶體資料庫解析與主流產品對比（一）》中，我們介紹了基於磁碟的資料庫管理系統相關知識，並簡述了記憶體資料庫的技術發展。本篇文章將從數據組織和索引的角度來介紹記憶體資料庫的特點，並介紹幾款產品實際的技術實現。

— 資料庫管理系統中的數據組織—

定長Block VS 變長Block

記憶體資料庫在記憶體中對數據進行管理時，雖然不再需要通過Slotted Page的形式對數據進行組織，但也不能在記憶體中任意為數據分配地址空間，依然需要把數據組織成塊（Block/Page）的形式。傳統基於磁碟的DBMS採用Slotted Page的形式組織數據是為了讀寫性能的考慮，因為磁碟介面是以Block/Page為讀寫單位。而記憶體資料庫採用塊的方式組織數據是為了便於定址和管理，通常會將數據塊分為定長數據塊（Fixed-Length Data Block）和變長數據塊(Variable-Length Data Block)兩種。

假設一個數據集已經全部被載入進記憶體，為了使用方便，記憶體資料庫在進行數據組織時會把記錄的定長的屬性全部分出來，放到定長數據塊；所有變長的屬性保存在另外的變長數據塊中。例如，通常將數據表中所有小於8個位元組的屬性都放在定長數據塊中，將變長屬性和超過8個位元組的屬性單獨放在變長數據塊中，並在定長數據塊中放一個指向其地址的指針。採用定長數據塊管理數據的好處是定址快，可以通過記錄長度和編號確定記錄在數據塊中存儲的位置；記錄地址指針所需要的空間少，使得索引結構或其他結構中存放這條記錄的記憶體地址最為精簡，並且CPU做Pre-Fetch時預測較准。

在傳統基於磁碟的DBMS中，索引葉子節點保存的記錄地址是Page ID + Offset，Page Table負責將Page ID映射到Buffer的Frame；記憶體資料庫中，索引的葉子節點保存的記錄地址則是直接的記憶體地址。在傳統基於磁碟的DBMS中，訪問Buffer中的Page時需要對Page進行加鎖/解鎖/修改鎖的操作，由於現實系統中鎖（Latch）的類型可能會很多，一個執行緒如果要訪問一個Page，往往要加好幾種類型的Latch。現在記憶體資料庫中沒有了Buffer，因此就省去了Latch的開銷，性能上有很大提升。

數據組織：數據分區、多版本、行/列存儲

在多核或多CPU共享記憶體的系統中，對數據的並發訪問衝突是始終存在的。目前的記憶體資料庫系統可以分為Partition System和Non-Partition System兩種。Partition System是把所有的數據切分成互不相交的多個Partition，每一個Partition被分配給一個核（或分散式系統中的一個節點），所有操作都是串列執行，沒有並發的數據訪問，理想情況下可以獲得最好的性能。但這類系統的缺點也很明顯，例如如何劃分Partition以及跨Partition的事務怎麼處理等。對於Non-Partition System，所有的核以及所有的執行緒都可以訪問所有的數據，因此一定會存在並發訪問衝突，必須採用支援並發訪問的數據結構。目前，通用資料庫更多的是採用Non-Partition System設計，之所以不採用Partition設計的主要原因是：通用場景下很難對數據進行有效分區，Partition資料庫無法使用。

在Non-Partition System中，如果兩個執行緒訪問同一個數據項會發生衝突，這時可以考慮Multi-Version的解決方案。Multi-Version的優勢在於可以提高並發程度，其基本的思想是通過多版本的數據讓所有的讀操作不阻塞寫操作，從而提高整個系統的性能。對於那些讀多寫少的系統，Multi-Version性能會很好，但對於一些Write Heavy的系統，性能並不理想。

數據組織還有一個需要考慮的是Row和Column的組織形式。傳統資料庫系統在磁碟上維護數據時，分為行式存儲和列式存儲。顧名思義，行式存儲是按行存儲數據，列式存儲是按列存儲數據。如果對少量記錄的所有屬性進行操作，行式存儲更加合適，如果只讀大量記錄的部分列數據，則列式存儲性能比較好。比如一條記錄有100個屬性，本次讀操作需要讀取所有記錄的其中一個屬性，如果按行存儲，Block讀進來後還需要再篩選列；如果按列存儲，可以只讀取這列數據所對應的Block，所以性能會比較好，適合去做統計分析。但記憶體資料庫不會有這個問題，所有數據都放在記憶體，無論行存還是列存，訪問的代價是差不多的。所以在記憶體資料庫中，行存/列存是可以做交換或任意選擇的。當然對於TP應用而言，更多的還是用行存，因為可以一次性把所有屬性都讀出來。但即使是列存，性能也並沒有在基於磁碟的資料庫系統中那麼糟糕。比如SAP HANA就是一個行列混合的存儲，前端的事務引擎是行存儲，通過合併整合以後，後端轉為了列存儲。

— 記憶體資料庫系統對比—

接下來從數據組織的角度，簡要介紹一下4個具有代表性的系統：SQL Server的記憶體資料庫引擎Hekaton、慕尼黑工業大學的記憶體資料庫系統HyPer、SAP的HANA、圖靈獎獲得者Michael Stonebraker的H-Store/VoltDB。

Hekaton

Hekaton是一個Non-Partition的系統，所有執行緒都可以訪問任意數據。Hekaton的並發控制不採用基於鎖的協議，而是利用多版本機制實現，每條記錄的每個版本都有開始時間戳和結束時間戳，用於確定該版本的可見範圍。

Hekaton中每一張表最多有8個索引，可以是Hash或者Range索引。同時，所有記錄版本在記憶體中不要求連續存儲，可以是非連續存儲（No-Clustering），通過指針（Pointer Link）將同一記錄的不同版本關聯起來。

上圖所示，圖中有一個包含姓名、城市和金額欄位的表，姓名欄位上有一個Hash索引，城市欄位上有一個B-Tree索引。黑色箭頭代表姓名索引對應的指針，名字John對應的第一條記錄，指向下一個具有相同開頭字母名字的記錄。每條記錄包含有開始和結束時間戳，紅色表示存在一個事務正在更新記錄，事務提交後會替換結束的時間戳。B-Tree索引也是同理，藍色箭頭指針按照城市值串聯。

H-Store/VoltDB

H-Store/VoltDB是Partition System，每個Partition部署在一個節點，每個節點上的任務串列執行。H-Store/VoltDB沒有並發控制，但有簡單的鎖控制。一個Partition對應一把鎖，如果某事務要在一個Partition上執行，需要先拿到這個Partition的鎖，才能開始執行。為了解決跨Partition執行問題，H-Store/VoltDB要求Transaction必須同時拿到所有相關Partition的鎖才能開始執行，相當於同時鎖住所有與事務相關的Partition。

H-Store/VoltDB採用兩層架構：上層是Transaction Coordinator，確定Transaction是否需要跨Partition執行；下層是執行引擎負責數據的存儲、索引和事務執行，採用的是單版本的行存結構。

H-Store/VoltDB中的數據塊分為定長和變長兩類：定長數據塊的每條記錄長度都相同，索引中採用8位元組地址指向每條記錄在定長數據塊中的位置；變長屬性被保存在變長數據塊中，在定長數據塊的記錄中對應一個指針（Non-Inline Data），指向其在變長數據塊中具體的位置。在這種數據組織方式下，可以用一個壓縮過的Block Look-Up Table來對數據記錄進行定址。

HyPer

HyPer是多版本的Non-Partition System，每個Transaction可以訪問任何數據。同時HyPer是針對於HTAP業務建立的TP和AP混合處理系統。HyPer通過Copy on Write機制實現TP和AP混合處理。假設當前系統正在對數據集做事務處理，此時如果出現AP請求，HyPer會通過作業系統的Fork功能對數據集做Snapshot，隨後在快照上面做分析。Copy on Write機制並不會對記憶體中的所有數據進行複製，只有因OLTP業務導致數據發生變化時，快照才會真正拷貝出原數據，而沒有變化的數據則通過虛擬地址引用到相同的物理記憶體地址。

此外，Hyper採用多版本控制，所有更新都是基於原記錄的，每條記錄都會維護一個Undo Buffer存儲增量更新數據，並通過Version Vector指出當前最新版本。因此，可以通過Transaction找到被修改過的記錄，同時可以通過反嚮應用增量數據來找回修改前的版本，當然也可以對數據版本進行定期融合或恢復等操作。

SAP HANA

SAP HANA是一個Non-Partition的混合存儲系統，物理記錄在存儲介質中會經過三個階段：1. 事務處理的記錄存儲在L1-Delta（行存方式）；2. 隨後記錄轉化為列式並存儲在L2-Delta（列式存儲、未排序字典編碼）；3. SAP HANA的主存是列存（高度壓縮並採用排序字典編碼）。每條記錄經歷著從行存到列存的映射合併，相當於一個多版本設計。

— 資料庫管理系統中的索引技術—

記憶體資料庫領域在設計索引時，主要是從面向快取的索引技術（Cache-Awareness）和多核多CPU的並行處理（Multi-Core and Multi-Socket Parallelism）兩方面進行考慮。

由於記憶體資料庫不再有磁碟的I/O限制，因此索引目的轉變為加速CPU和記憶體之間的訪問速度。雖然現在記憶體價格較低，但是記憶體速度的增速與CPU主頻的增速相差依然較多，因此對於記憶體資料庫，索引技術的目的是及時給CPU供數，以盡量快的速度將所需數據放入CPU的Cache中。

對於多核多CPU的並行處理，80年代就開始考慮如果數據結構和數據都放在記憶體中，應該如何合理的構造索引。其中，1986年威斯康星大學的MM-DBMS項目提出了自平衡的二叉搜索樹T-Tree索引，每個二叉節點中存儲取值範圍內的數據記錄，同時有兩個指針指向它的兩個子節點。T-Tree索引結構記憶體開銷較小，因為在80年代記憶體昂貴，所以主要的度量不在於性能是否最優，而是是否佔用最小記憶體空間。T-Tree的缺點是性能問題，需要定期地做負載平衡，並且掃描和指針也會對其性能產生影響。早期商業系統如Times Ten中，採用的便是T-Tree的數據結構。

那麼索引的設計為什麼需要考慮Cache-Awareness呢？1999年有研究發現記憶體訪問中的Cache Stall或者Cache Miss是記憶體系統最主要的性能瓶頸。該研究進行了一項性能測試，通過對A/B/C/D 4個系統評測，測試以下過程的時間佔比：Computation、Memory Stalls、Branch Mispredicitons和Resource Stalls。Computation表示真正用於計算的時間；Memory Stall是等待記憶體訪問的時間；Branch Mispredicitons是指CPU指令分支預測失敗的開銷；Resource Stalls是指等待其他資源的時間開源，如網路、磁碟等。

可以看到Memory Stall在不同的測試場景都會佔據較大比例開銷。因此對於記憶體索引結構來說，發展面向快取的索引的主要目的就是為了減少Memory Stall的開銷。

CSB+-Tree

這裡介紹幾個典型的記憶體索引結構例子。第一個是CSB+-Tree，它在邏輯上仍然是B+-Tree，但是做了一些變化。首先每個Node的大小是一個Cache Line長度的倍數；同時CSB+-Tree將一個節點的所有的子節點組織成Children Group，一個父節點通過一個指針指向它的Children Group，目的是減少數據結構中的指針數量。因為CSB+-Tree的節點與Cache Line長度相匹配，只要依序讀取，就可以達到較好的pre-fetche性能。當樹分裂時，CSB+-Tree會對記憶體中的Group重新分配位置，因為CSB+-Tree節點在記憶體中不需要連續，排好後再創建新的指針鏈接就可以。

PB+-Trees

另一個例子是PB+-Trees（Pre-fetching B+-Tree）。它並不是新的結構，只是在記憶體中實現了B+-Tree，每個節點的大小等於Cache Line的長度倍數。PB+-Trees比較特殊的是在整個系統實現過程中，引入了Pre-fetching，通過加入一些額外資訊幫助系統預取數據。

PB+-Trees傾向於採用扁平的樹來組織數據，論文中給出了它Search和Scan的性能，其中Search性能提高1.5倍，Scan上提高了6倍。處理Search時的性能相比CSB+-Tree，PB+-Trees的Data Cache Stalls佔比更小。

另外一個性能對比是，當沒有採用預取時，讀取一個Node大小等於兩個Cache Line的三級索引需要900個時鐘周期，而加了預取後僅需要480個周期。PB+-Trees還有一個實現是，它會在每個節點加上Jump Pointer Array，用來判斷做掃描時要跳過多少Cache Line以預取下一個值。

Bw-Tree

Bw-Tree是Hekaton系統中使用的索引，基本思想是通過Compare-and-Swap指令級原子操作比較記憶體值，如果新舊值相等就更新，如果不等則不更新。比如原值為20（存儲在磁碟），而記憶體地址對應30，那麼要是把30更新成40就不會成功。這是一個原子操作，可用於在多執行緒編程中實現不被打斷的數據交換操作。

Bw-Tree中存在Mapping Table，每一個節點都在Mapping Table中有一個存儲位置，Mapping Table會存儲節點在記憶體中的地址。對於Bw-Tree來講，從父節點到子節點的指針並不是物理指針，而是邏輯指針，也就是記錄在Mapping Table中的位置並不是真正的記憶體位置。

Bw-Tree採用的設計是節點的更新並不是直接修改節點，而是通過增加Delta Record（增量記錄）來保存修改的內容，然後在Mapping Table中指向Delta Record，如果有新的更新就繼續指向新的Delta Record。在讀取一個節點的內容時，實際上是合併所有的Delta Record。因為對Bw-Tree的更新是通過一個原子操作來實現的，發生競爭時只有一個改動能成功，因此是一種Latch-Free結構，只需要靠Compare-and-Swap就能夠解決競爭問題，不再需要依賴鎖機制。

Adaptive Radix Tree

Hyper的索引樹的設計採用了Adaptive Radix Tree。傳統Radix Tree是一個前綴樹，其優勢是樹的深度不依賴於被索引的值的個數，而是靠Search Key的長度來決定。它的缺點是每一個節點都要維護可能取值的子節點的資訊，導致每個節點的存儲開銷較大。

而在Adaptive Radix Tree中，為每個節點提供了不同類型長度的格式，分別可以保存4/16/48/256等不同個數的子節點。Node4為最小的節點類型，最多可存儲4個子節點指針， Key用來表示節點所存儲的值，指針可以指向葉子節點，也可以指向下一層內部節點。Node16 和Node4 結構上一致，但 Node16 可以存放16個 unsigned char 和16個指針，在存放第17個key時則需要將其擴大為 Node48。Node48結構上和 Node4/16 有所不同，有256個索引槽和48個指針，這256個索引槽對應 unsigned char 的0-255，每個索引槽的值對應指針的位置，分別為 1-48，如果某個位元組不存在的話，那麼它的索引槽的值就是0。當存放第49個key byte 時需要將其擴大為 Node256。Node256結果較為簡單，直接存放256個指針，每個指針對應 unsigned char 的0-255 區間。

比如說在這個例子里，我們要索引一個整數（+218237439），整數的二進位表示形式為32位，隨後將32位bit轉換為4個Byte，這4個byte十進位表示為13、2、9、255，這就是它的Search Key。在索引樹中，第一層為Node 4，13符合這一層的存儲要求，於是就保留在第一層節點上，後面的位數則進入下一層存儲，下一層為Node 48，用來存儲2；接下來的每一位都存儲到下面的每一層。由於本例子中整數為4個位元組表示，故共有4層。可以看到，每個節點的結構是不一樣的，根據位元組位數和順序逐一存儲，數值在這一層目前有多少個不同的值，就選擇什麼類型的節點。如果當前類型的不夠用，可以再增加個數，每個節點可以容納的 key 是動態變化的，這樣既可以節省空間，又可以提高快取局部性。

另外Adaptive Radix還採用了路徑壓縮機制，如果一條路徑的父節點只有一個子節點就會將之壓縮合併。Adaptive Radix之所以採用這樣的索引結構，是因為每個節點的大小都等於一個Cache Line，所有操作可以在一個Cache Line的基礎上實現。

OLFIT on B+-Trees

OLFIT on B+-Trees（Optimistic Latch Free Index Access Protocol）是HANAP*Time採用的索引技術，能夠在多核資料庫上保證CPU的Cache Coherence。在多處理器電腦的體系結構中，多個CPU的Cache會快取同一記憶體的數據。在記憶體資料庫中，存儲的數據會先讀到對應Cache再處理；如果快取數據處理過程中記憶體數據發生變化，那Cache的數據會因與記憶體數據不一致而失效，Cache Coherence就是解決這個不同步的問題。

考慮這樣一個場景：如下圖所示，記憶體中有一個樹形數據結構，由4個CPU處理，每個CPU有自己的Cache。假設CPU-P1先讀了n1、n2、n4，Cache中便有了n1、n2、n4。隨後CPU-P2讀n1、n2和n5時，假設這個數據結構不是Latch-Free，如果在讀的同時且允許修改，就需要一個Latch來在讀的時候上鎖，讀完再釋放。因為記憶體資料庫中Latch和數據放在一起，數據雖然沒有變化，但是Latch的狀態發生了改變，電腦的硬體結構會認為記憶體發生了變化。所以，當多個CPU讀同樣的數據時，只有最後一次讀取狀態是有效的，前序的讀取會被認為失效。這就會出現即使都是進行讀操作，但是因為Latch狀態改變導致CPU的Cache失效。因此OLFIT設計了一套機制，要求寫操作申請Latch，讀操作不需要。OLFIT通過版號維護讀寫事務，每個CPU讀前先把版本號拷貝到本地暫存器，然後等讀完數據後，再判斷此時版本號跟讀前的是否一樣。如果一樣就繼續正常執行，不一樣就說明Cache失效。因此，讀請求不會引起其他CPU的Cache失效。

通過這個例子可以看到，記憶體資料庫考慮的問題和基於磁碟的資料庫是不一樣的，沒有了磁碟I/O的因素，就需要考慮其他方面對性能的限制。

Skiplists

Skiplists是MemSQL的數據處理引擎所用到的技術，它的最底層是一個有序的列表，上層按照一定的概率（P-value）抽取數據，再做一層列表。進行大列表搜索時，從最上層開始一層層遞進，類似於二分查找，粒度可以根據實際情況自定義。之所以這樣設計是因為所有對列表的插入操作，都是可以通過Compare-and-Swap原子操作完成，從而省去了鎖的開銷。

— 本文小結—

本文首先介紹了記憶體資料庫的數據組織，分別從數據劃分，Partition/Non-Partition的系統差異和存儲方式進行介紹，並對比了四款產品的實際實現。隨後，介紹了六種記憶體資料庫系統的索引技術，並通過例子簡述了索引查詢原理。下一篇文章將繼續對記憶體資料庫進行剖析，從並發控制、持久化存儲和編譯查詢的角度，討論記憶體資料庫對於查詢性能和可用性的優化設計。

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

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.