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

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

[[227279]]

一、什么是列式存儲

傳統 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 就采用了關系模型。

Column Families in BigTable

二、起源：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 中的數據編碼方式，具有一定的代表性。

根據：數據本身是否按順序排列（Self-Order）以及數據有多少不同的取值（Distinct Values），我們分成以下 4 種情況討論：

• 有序且Distinct值不多。使用一系列的三元組（v,f,n）對列數據編碼，表示數值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 等分布式文件系統已經成為存放大規模數據集的主流方式。分布式文件系統相比單機上的磁盤，具備多副本高可用、容量大、成本低等諸多優勢，但也帶來了一些單機架構所沒有的問題：

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

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

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

五、列式存儲系統案例

1、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 可以包含一個或多個列，甚至可以包含來自其他邏輯表的列（構成索引）。當然，每個列至少會存在于一個 Projection 上。

下圖的例子中，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 個列會出現在多個 Projections 中，但是它們的順序也就是 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。

2、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 文件雖然支持事務，但主要是對批量寫入的事務比較友好，不適合頻繁且細小地寫入事務的原因。

3、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 的記錄：

• ***個是 en-us，出現在***個 Name 的***個 Lanuage 的***個 Code 里面。在此之前，這三個元素是沒有重復過的，都是***次出現。所以其 R=0
• 第二個是 en，出現在下一個 Language 里面。也就是說 Language 是重復的元素。Name.Language.Code 中Language 排第二個，所以其 R=2
• 第三個是 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 列：

• us 非 NULL 值填上 Country 字段的 Level 即 D=3
• NULL 在 R1 內部，表示當前 Name 之內、后續所有 Language 都不含有 Country 字段，所以D為2。
• NULL 在 R1 內部，表示當前 Document 之內、后續所有 Name 都不含有 Country 字段，所以D為1。
• gb 非 NULL 值填上 Country 字段的 Level 即 D=3
• NULL 在 R2 內部，表示后續所有 Document 都不含有 Country 字段，所以D為0。

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

狀態機實現可以說是 Dremel 論文的***貢獻。但是受限于篇幅，有興趣的同學請參考文末的“文章參考”。

六、總結

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

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

參考文章：

Distinguishing Two Major Types of Column-Stores - Daniel Abadi

Columnar Storage - Amazon Redshift

Weaving Relations for Cache Performance - A Ailamaki, DJ DeWitt, MD Hill, M Skounakis

C-Store and Google BigTable - Greg Linden

The Design and Implementation of Modern Column-Oriented Database Systems - D Abadi, P Boncz, S Harizopoulos…

C-store: a column-oriented DBMS - M Stonebraker, DJ Abadi, A Batkin, X Chen…

Apache ORC Docs

Dremel: Interactive Analysis of Web-Scale Datasets - S Melnik, A Gubarev, JJ Long, G Romer…