處理海量數據：列式存儲綜述（存儲篇）

來自專欄 茄子的數據平台小菜

列式存儲（Column-oriented Storage）並不是一項新技術，最早可以追溯到 1983 年的論文 Cantor。然而，受限於早期的硬體條件和使用場景，主流的事務型資料庫（OLTP）大多採用行式存儲，直到近幾年分析型資料庫（OLAP）的興起，列式存儲這一概念又變得流行。

總的來說，列式存儲的優勢一方面體現在存儲上能節約空間、減少 IO，另一方面依靠列式數據結構做了計算上的優化。本文中著重介紹列式存儲的數據組織方式，包括數據的布局、編碼、壓縮等。在下一篇文章中將介紹計算層以及 DBMS 整體架構設計。

什麼是列式存儲

傳統 OLTP 資料庫通常採用行式存儲。以下圖為例，所有的列依次排列構成一行，以行為單位存儲，再配合以 B+ 樹或 SS-Table 作為索引，就能快速通過主鍵找到相應的行數據。

行式存儲對於 OLTP 場景是很自然的：大多數操作都以實體（entity）為單位，即大多為增刪改查一整行記錄，顯然把一行數據存在物理上相鄰的位置是個很好的選擇。

然而，對於 OLAP 場景，一個典型的查詢需要遍歷整個表，進行分組、排序、聚合等操作，這樣一來按行存儲的優勢就不復存在了。更糟糕的是，分析型 SQL 常常不會用到所有的列，而僅僅對其中某些感興趣的列做運算，那一行中那些無關的列也不得不參與掃描。

列式存儲就是為這樣的需求設計的。如下圖所示，同一列的數據被一個接一個緊挨著存放在一起，表的每列構成一個長數組。

顯然，列式存儲對於 OLTP 不友好，一行數據的寫入需要同時修改多個列。但對 OLAP 場景有著很大的優勢：

• 當查詢語句只涉及部分列時，只需要掃描相關的列
• 每一列的數據都是相同類型的，彼此間相關性更大，對列數據壓縮的效率較高

BigTable（HBase）是列式存儲嗎？

很多文章將 BigTable 歸為列式存儲。但嚴格地說，BigTable 並非列式存儲，雖然論文中提到借鑒了 C-Store 等列式存儲的某些設計，但 BigTable 本身按 Key-Value Pair 存儲數據，和列式存儲並無關係。

有一點迷惑的是 BigTable 的列簇（column family）概念，列簇可以被指定給某個 locality group，決定了該列簇數據的物理位置，從而可以讓同一主鍵的各個列簇分別存放在最優的物理節點上。由於 column family 內的數據通常具有相似性，對它做壓縮要比對整個表壓縮效果更好。

另外，值得強調的一點是：列式資料庫可以是關係型、也可以是 NoSQL，這和是否是列式並無關係。本文中討論的 C-Store 就採用了關係模型。

起源：DSM 分頁模式

我們知道，由於機械磁碟受限於磁頭定址過程，讀寫通常都以一塊（block）為單位，故在操作系統中被抽象為塊設備，與流設備相對。這能幫助上層應用是更好地管理儲存空間、增加讀寫效率等。這一特性直接影響了資料庫儲存格式的設計：資料庫的 Page 對應一個或幾個物理扇區，讓資料庫的 Page 和扇區對齊，提升讀寫效率。

那如何將數據存放到頁上呢？

大多數服務於在線查詢的 DBMS 採用 NSM (N-ary Storage Model) 即按行存儲的方式，將完整的行（即關係 relation）從 Header 開始依次存放。頁的最後有一個索引，存放了頁內各行的起始偏移量。由於每行長度不一定是固定的，索引可以幫助我們快速找到需要的行，而無需逐個掃描。

NSM 的缺點在於，如果每次查詢只涉及很小的一部分列，那多餘的列依然要佔用掉寶貴的內存以及 CPU Cache，從而導致更多的 IO；為了避免這一問題，很多分析型資料庫採用 DSM (Decomposition Storage Model) 即按列分頁：將 relation 按列拆分成多個 sub-relation。類似的，頁的尾部存放了一個索引。

順便一提，2001 年 Ailamaki 等人提出 PAX (Partition Attributes Cross) 格式，嘗試將 DSM 的一些優點引入 NSM，將兩者的優點相結合。具體來說，NSM 能更快速的取出一行記錄，這是因為一行的數據相鄰保存在同一頁；DSM 能更好的利用 CPU Cache 以及使用更緊湊的壓縮。PAX 的做法是將一個頁劃分成多個 minipage，minipage 內按列存儲，而一頁中的各個 minipage 能組合成完整的若干 relation。

如今，隨著分散式文件系統的普及和磁碟性能的提高，很多先進的 DBMS 已經拋棄了按頁存儲的模式，但是其中的某些思想，例如數據分區、分區內索引、行列混合等，仍然處處可見於這些現代的系統中。

分散式儲存系統雖然不再有頁的概念，但是仍然會將文件切割成分塊進行儲存，但分塊的粒度要遠遠大於一般扇區的大小（如 HDFS 的 Block Size 一般是 128MB）。更大的讀寫粒度是為了適應網路 IO 更低的帶寬以獲得更大的吞吐量，但另一方面也犧牲了細粒度隨機讀寫。

列數據的編碼與壓縮

無論對於磁碟還是內存資料庫，IO 相對於 CPU 通常都是系統的性能瓶頸，合理的壓縮手段不僅能節省空間，也能減少 IO 提高讀取性能。列式存儲在數據編碼和壓縮上具有天然的優勢。

以下介紹的是 C-Store 中的數據編碼方式，具有一定的代表性。根據 1) 數據本身是否按順序排列（self-order） 2) 數據有多少不同的取值（distinct values），分成以下 4 種情況討論：

• 有序且 distinct 值不多。使用一系列的三元組 對列數據編碼，表示數值 v 從第 f 行出現，一共有 n 個（即 f 到 f+n?1 行）。例如：數值 4 出現在 12-18 行，則編碼為 (4,12,7)。
• 無序且 distinct 值不多。對於每個取值 v 構造一個二進位串 b，表示 v 所在位置的 bitmap。例如：如果一列的數據是 0,0,1,1,2,1,0,2,1，則編碼為 (0, 110000100)、(1, 001101001) 和 (2,000010010)。由於 bitmap 是稀疏的，可以對其再進行行程編碼。
• 有序且 distinct 值多。對於這種情況，把每個數值表示為前一個數值加上一個變化量（delta），當然第一個數值除外。例如，對於一列數據 1,4,7,7,8,12，可以表示為序列 1,3,3,0,1,4。顯然編碼後的數據更容易被 dense pack，且壓縮比更高。
• 無序且 distinct 值多。對於這種情況沒有很好的編碼方式。

編碼之後，還可以對數據進行壓縮。由於一列的數據本身具有相似性，即使不做特殊編碼，也能取得相對較好的壓縮效果。通常採用 Snappy 等支持流式處理、吞吐量高的壓縮演算法。

最後，編碼和壓縮不僅是節約空間的手段，更多時候也是組織數據的手段。在 PowerDrill、Dremel 等系統中，我們會看到很多編碼本身也兼具了索引的功能，例如在掃描中跳過不需要的分區，甚至完全改表查詢執行的方式。

列式存儲與分散式文件系統

在現代的大數據架構中，GFS、HDFS 等分散式文件系統已經成為存放大規模數據集的主流方式。分散式文件系統相比單機上的磁碟，具備多副本高可用、容量大、成本低等諸多優勢，但也帶來了一些單機架構所沒有的問題：

1. 讀寫均要經過網路，吞吐量可以追平甚至超過硬碟，但是延遲要比硬碟大得多，且受網路環境影響很大。
2. 可以進行大吞吐量的順序讀寫，但隨機訪問性能很差，大多不支持隨機寫入。為了抵消網路的 overhead，通常寫入都以幾十 MB 為單位。

上述缺點對於重度依賴隨機讀寫的 OLTP 場景來說是致命的。所以我們看到，很多定位於 OLAP 的列式存儲選擇放棄 OLTP 能力，從而能構建在分散式文件系統之上。

要想將分散式文件系統的性能發揮到極致，無非有幾種方法：按塊（分片）讀取數據、流式讀取、追加寫入等。我們在後面會看到一些開源界流行的列式存儲模型，將這些優化方法體現在存儲格式的設計中。

列式存儲系統案例

C-Store (2005) / Vertica

大多數 DBMS 都是為寫優化，而 C-Store 是第一個為讀優化的 OLTP 資料庫系統，雖然從今天的視角看它應當算作 HTAP 。在 ad-hoc 的分析型查詢、ORM 的在線查詢等場景中，大多數操作都是查詢而非寫入，在這些場景中列式存儲能取得更好的性能。像主流的 DBMS 一樣，C-Store 支持標準的關係型模型。

就像本文開頭即提到——列式存儲不是新鮮事。C-Store 的主要貢獻有以下幾點：通過精心設計的 projection 同時實現列數據的多副本和多種索引方式；用讀寫分層的方式兼顧了（少量）寫入的性能。此外，C-Store 可能是第一個現代的列式存儲資料庫實現，其的設計啟發了無數後來的商業或開源資料庫，就比如 Vertica。

數據模型

C-Store 是關係型資料庫，它的邏輯表和其他資料庫中的並沒有什麼不同。但是在 C-Store 內部，邏輯表被縱向拆分成 projections，每個 projection 可以包含一個或多個列，甚至可以包含來自其他邏輯表的列（構成索引）。當然，每個列至少會存在於一個 projections 上。

下圖的例子中，EMP 表被存儲為 3 個 projections，DEPT 被存儲為 1 個 projection。每個 projection 按照各自的 sort key 排序，在圖中用下劃線表示 sort key。

Projection 內是以列式存儲的：裡面的每個列分別用一個數據結構存放。為了避免列太長引起問題，也支持每個 projection 以 sort key 的值做橫向切分。

查詢時 C-Store 會先選擇一組能覆蓋結果中所有列的 projections 集合作為 covering set，然後進行 join 計算重構出原來的行。為了能高效地進行 projections 的 join（即按照另一個 key 重新排序），引入 join index 作為輔助，其中存儲了 proj1 到 proj2 的下標映射關係。

Projection 是有冗餘性的，常常 1 個列會出現在多個 projection 中，但是它們的順序也就是 sort key 並不相同，因此 C-Store 在查詢時可以選用最優的一組 projections，使得查詢執行的代價最小。

巧妙的是，C-Store 的 projection 冗餘性還用來實現 K-safe 高可用（容忍最多 K 台機器故障），當部分節點當機時，只要 C-Store 還能找到某個 covering set 就能執行查詢，雖然不一定是最優的 covering set 組合。

從另一個角度看，C-Store 的 Projection 可以看作是一種物化（materialized）的查詢結果，即查詢結果在查詢執行前已經被預先計算好；並且由於每個列至少出現在一個 Projection 當中，沒有必要再保存原來的邏輯表。

為任意查詢預先計算好結果顯然不現實，但是如果物化某些經常用到的中間視圖，就能在預計算代價和查詢代價之間獲得一個平衡。C-Store 物化的正是以某個 sort key 排好序（甚至 JOIN 了其他表）的一組列數據，同時預計算的還有 join index。

C-Store 對寫入的處理將在下一篇文章中呈現。

Apache ORC

Apache ORC 最初是為支持 Hive 上的 OLAP 查詢開發的一種文件格式，如今在 Hadoop 生態系統中有廣泛的應用。ORC 支持各種格式的欄位，包括常見的 int、string 等，也包括 struct、list、map 等組合欄位；欄位的 meta 信息就放在 ORC 文件的尾部（這被稱為自描述的）。

數據結構及索引

為分區構造索引是一種常見的優化方案，ORC 的數據結構分成以下 3 個層級，在每個層級上都有索引信息來加速查詢。

• File Level：即一個 ORC 文件，Footer 中保存了數據的 meta 信息，還有文件數據的索引信息，例如各列數據的最大最小值（範圍）、NULL 值分布、布隆過濾器等，這些信息可用來快速確定該文件是否包含要查詢的數據。每個 ORC 文件中包含多個 Stripe。
• Stripe Level 對應原表的一個範圍分區，裡面包含該分區內各列的值。每個 Stripe 也有自己的一個索引放在 footer 里，和 file-level 索引類似。
• Row-Group Level ：一列中的每 10000 行數據構成一個 row-group，每個 row-group 擁有自己的 row-level 索引，信息同上。

ORC 里的 Stripe 就像傳統資料庫的頁，它是 ORC 文件批量讀寫的基本單位。這是由於分散式儲存系統的讀寫延遲較大，一次 IO 操作只有批量讀取一定量的數據才划算。這和按頁讀寫磁碟的思路也有共通之處。

像其他很多儲存格式一樣，ORC 和都選擇將統計數據和 Metadata 放在 File 和 Stripe 的尾部而不是頭部。

但 ORC 在 Stripe 的讀寫上還有一點優化，那就是把分區粒度小於 Stripe 的結構（如 Column 和 Row-Group）的索引統一抽取出來放到 Stripe 的頭部。這是因為在批處理計算中一般是把整個 Stripe 讀入批量處理的，將這些索引抽取出來可以減少在批處理場景下需要的 IO（批處理讀取可以跳過這一部分）。

ACID 支持

Apache ORC 提供有限的 ACID 事務支持。受限於分散式文件系統的特點，文件不能隨機寫，那如何把修改保存下來呢？

類似於 LSM-Tree 中的 MVCC 那樣，writer 並不是直接修改數據，而是為每個事務生成一個 delta 文件，文件中的修改被疊加在原始數據之上。當 delta 文件越來越多時，通過 minor compaction 把連續多個 delta 文件合成一個；當 delta 變得很大時，再執行 major compaction 將 delta 和原始數據合併。

這種保持基線數據不變、分層疊加 delta 數據的優化方式在列式存儲系統中十分常見，是一種通用的解決思路。

別忘了 ORC 的 delta 文件也是寫入到分散式儲存中的，因此每個 Delta 文件的內容不宜過短。這也解釋了 ORC 文件雖然支持事務，但是主要是對批量寫入的事務比較友好，不適合頻繁且細小的寫入事務的原因。

Dremel (2010) / Apache Parquet

Dremel 是 Google 研發的用於大規模只讀數據的查詢系統，用於進行快速的 ad-hoc 查詢，彌補 MapReduce 互動式查詢能力的不足。為了避免對數據的二次拷貝，Dremel 的數據就放在原處，通常是 GFS 這樣的分散式文件系統，為此需要設計一種通用的文件格式。

Dremel 的系統設計和大多 OLAP 的列式資料庫並無太多創新點，但是其精巧的存儲格式卻變得流行起來，Apache Parquet 就是它的開源復刻版。注意 Parquet 和 ORC 一樣都是一種存儲格式，而非完整的系統。

嵌套數據模型

Google 內部大量使用 Protobuf 作為跨平台、跨語言的數據序列化格式，相比 JSON 要更緊湊並具有更強的表達能力。Protobuf 不僅允許用戶定義必須（required）和可選（optinal）欄位，還允許用戶定義 repeated 欄位，意味著該欄位可以出現 0～N 次，類似變長數組。

Dremel 格式的設計目的就是按列來存儲 Protobuf 的數據。由於 repeated 欄位的存在，這要比按列存儲關係型的數據困難一些。一般的思路可能是用終止符表示每個 repeat 結束，但是考慮到數據可能很稀疏，Dremel 引入了一種更為緊湊的格式。

作為例子，下圖左半邊展示了數據的 schema 和 2 個 Document 的實例，右半邊是序列化之後的各個列。序列化之後的列多出了 R、D 兩列，分別代表 Repetition Level 和 Definition Level，通過這兩個值就能確保唯一地反序列化出原本的數據。

Repetition Level 表示當前值在哪一個級別上重複。對於非 repeated 欄位只要填上 trivial 值 0 即可；否則，只要這個欄位可能出現重複（無論本身是 repeated 還是外層結構是 repeated），應當為 R 填上當前值在哪一層上 repeat。

舉個例子說明：對於 Name.Language.Code 我們一共有三條非 NULL 的記錄。

1. 第一個是 en-us，出現在第一個 Name 的第一個 Lanuage 的第一個 Code 裡面。在此之前，這三個元素是沒有重複過的，都是第一次出現。所以其 R=0
2. 第二個是 en，出現在下一個 Language 裡面。也就是說 Language 是重複的元素。Name.Language.Code 中Language 排第二個，所以其 R=2
3. 第三個是 en-gb，出現在下一個 Name 中，Name 是重複元素，排第一個，所以其 R=1

注意到 en-gb 是屬於第3個 Name 的而非第2個Name，為了表達這個事實，我們在 en 和 en-gb中間放了一個 R=1 的 NULL。

Definition Level 是為了說明 NULL 被定義在哪一層，也就宣告那一層的 repeat 到此為止。對於非 NULL 欄位只要填上 trivial 值，即數據本身所在的 level 即可。

同樣舉個例子，對於 Name.Language.Country 列

1. us 非 NULL 值填上 Country 欄位的 level 即 D=3
2. NULL 在 R1 內部，表示當前 Name 之內、後續所有 Language 都不含有 Country 欄位。所以D為2。
3. NULL 在 R1 內部，表示當前 Document 之內、後續所有 Name 都不含有 Country 欄位。所以D為1。
4. gb 非 NULL 值填上 Country 欄位的 level 即 D=3
5. NULL 在 R2 內部，表示後續所有 Document 都不含有 Country 欄位。所以D為0。

可以證明，結合 R、D 兩個數值一定能唯一構建出原始數據。為了高效編解碼，Dremel 在執行時首先構建出狀態機，之後利用狀態機處理列數據。不僅如此，狀態機還會結合查詢需求和數據的 structure 直接跳過無關的數據。

狀態機實現可以說是 Dremel 論文的最大貢獻。但是受限於篇幅，有興趣的同學請參考原論文。

總結

本文介紹了列式存儲的存儲結構設計。拋開種種繁複的細節，我們看到，以下這些思想或設計是具有共性的。

1. 跳過無關的數據。從行存到列存，就是消除了無關列的掃描；ORC 中通過三層索引信息，能快速跳過無關的數據分片。
2. 編碼既是壓縮，也是索引。Dremel 中用精巧的嵌套編碼避免了大量 NULL 的出現；C-Store 對 distinct 值的編碼同時也是對 distinct 值的索引；PowerDrill 則將字典編碼用到了極致（見下一篇文章）。
3. 假設數據不可變。無論 C-Store、Dremel 還是 ORC，它們的編碼和壓縮方式都完全不考慮數據更新。如果一定要有更新，暫時寫到別處、讀時合併即可。
4. 數據分片。處理大規模數據，既要縱向切分也要橫向切分，不必多說。

下一篇文章中，將會結合 C-Store、MonetDB、Apache Kudu、PowerDrill 等現代列式資料庫系統，側重描述列式 DBMS 的整體架構設計以及獨特的查詢執行過程。敬請期待！

References

1. Distinguishing Two Major Types of Column-Stores - Daniel Abadi
2. Columnar Storage - Amazon Redshift
3. Weaving Relations for Cache Performance - A Ailamaki, DJ DeWitt, MD Hill, M Skounakis
4. C-Store and Google BigTable - Greg Linden
5. The Design and Implementation of Modern Column-Oriented Database Systems - D Abadi, P Boncz, S Harizopoulos…
6. C-store: a column-oriented DBMS - M Stonebraker, DJ Abadi, A Batkin, X Chen…
7. Apache ORC Docs
8. Dremel: Interactive Analysis of Web-Scale Datasets - S Melnik, A Gubarev, JJ Long, G Romer…

最後，特別感謝 @張茄子 同學為本文提出的各種建議和見解！

本文章採用 CC BY-NC-SA 3.0 許可協議。轉載請註明出處！

原文鏈接： https://ericfu.me/columnar-storage-overview-storage/

推薦閱讀：