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

總的來說，列式存儲的優(yōu)勢一方面體現(xiàn)在存儲上能節(jié)約空間、減少 IO，另一方面依靠列式數(shù)據(jù)結(jié)構(gòu)做了計算上的優(yōu)化。本文將著重介紹列式存儲的數(shù)據(jù)組織方式，包括數(shù)據(jù)的布局、編碼、壓縮等。

一、什么是列式存儲

傳統(tǒng) OLTP 數(shù)據(jù)庫通常采用行式存儲。以下圖為例，所有的列依次排列構(gòu)成一行，以行為單位存儲，再配合以 B+ 樹或 SS-Table 作為索引，就能快速通過主鍵找到相應(yīng)的行數(shù)據(jù)：

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

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

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

顯然，列式存儲對于 OLTP 不友好，一行數(shù)據(jù)的寫入需要同時修改多個列。但對 OLAP 場景有著很大的優(yōu)勢：

當查詢語句只涉及部分列時，只需要掃描相關(guān)的列

每一列的數(shù)據(jù)都是相同類型的，彼此間相關(guān)性更大，對列數(shù)據(jù)壓縮的效率較高

小貼士：

BigTable（HBase）是列式存儲嗎？

很多文章將 BigTable 歸為列式存儲。但嚴格地說，BigTable 并非列式存儲，雖然論文中提到借鑒了 C-Store 等列式存儲的某些設(shè)計，但 BigTable 本身按 Key-Value Pair 存儲數(shù)據(jù)，和列式存儲并無關(guān)系。

有一點迷惑的是 BigTable 的列簇（Column Family）概念，列簇可以被指定給某個 Locality Group，決定了該列簇數(shù)據(jù)的物理位置，從而可以讓同一主鍵的各個列簇分別存放在最優(yōu)的物理節(jié)點上。由于 Column Family 內(nèi)的數(shù)據(jù)通常具有相似性，對它做壓縮要比對整個表壓縮效果更好。

另外，值得強調(diào)的一點是：列式數(shù)據(jù)庫可以是關(guān)系型、也可以是 NoSQL，這和是否是列式并無關(guān)系。本文中討論的 C-Store 就采用了關(guān)系模型。

Column Families in BigTable

二、起源：DSM 分頁模式

我們知道，由于機械磁盤受限于磁頭尋址過程，讀寫通常都以一塊（Block）為單位，故在操作系統(tǒng)中被抽象為塊設(shè)備，與流設(shè)備相對。這能幫助上層應(yīng)用更好地管理儲存空間、增加讀寫效率等。

這一特性直接影響了數(shù)據(jù)庫儲存格式的設(shè)計：數(shù)據(jù)庫的 Page 對應(yīng)一個或幾個物理扇區(qū)，讓數(shù)據(jù)庫的 Page 和扇區(qū)對齊，提升讀寫效率。

那如何將數(shù)據(jù)存放到頁上呢？

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

NSM 的缺點在于：如果每次查詢只涉及很小的一部分列，那多余的列依然要占用掉寶貴的內(nèi)存以及 CPU Cache，從而導(dǎo)致更多的 IO。為了避免這一問題，很多分析型數(shù)據(jù)庫采用 DSM（Decomposition Storage Model），即按列分頁：將 Relation 按列拆分成多個 Sub-relation。類似的，頁的尾部存放了一個索引：

順便一提，2001 年 Ailamaki 等人提出 PAX （Partition Attributes Cross） 格式，嘗試將 DSM 的一些優(yōu)點引入 NSM，將兩者的優(yōu)點相結(jié)合。

具體來說，NSM 能更快速地取出一行記錄，這是因為一行的數(shù)據(jù)相鄰，保存在同一頁；DSM 能更好地利用 CPU Cache 以及使用更緊湊的壓縮。PAX 的做法是將一個頁劃分成多個 Minipage，Minipage 內(nèi)按列存儲，而一頁中的各個 Minipage 能組合成完整的若干 Relation。

如今，隨著分布式文件系統(tǒng)的普及和磁盤性能的提高，很多先進的 DBMS 已經(jīng)拋棄了按頁存儲的模式。但是其中的某些思想，例如數(shù)據(jù)分區(qū)、分區(qū)內(nèi)索引、行列混合等，仍然處處可見于這些現(xiàn)代的系統(tǒng)中。

分布式儲存系統(tǒng)雖然不再有頁的概念，但是仍然會將文件切割成分塊進行儲存，但分塊的粒度要遠遠大于一般扇區(qū)的大?。ㄈ?HDFS 的 Block Size 一般是128MB）。更大的讀寫粒度是為了適應(yīng)網(wǎng)絡(luò) IO 更低的帶寬以獲得更大的吞吐量，但另一方面也犧牲了細粒度隨機讀寫。

三、列數(shù)據(jù)的編碼與壓縮

無論對于磁盤還是內(nèi)存數(shù)據(jù)庫，IO 相對于 CPU 通常都是系統(tǒng)的性能瓶頸，合理的壓縮手段不僅能節(jié)省空間，也能減少 IO 、提高讀取性能。列式存儲在數(shù)據(jù)編碼和壓縮上具有天然的優(yōu)勢。

以下介紹的是 C-Store 中的數(shù)據(jù)編碼方式，具有一定的代表性。

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

有序且Distinct值不多。使用一系列的三元組（v，f，n）對列數(shù)據(jù)編碼，表示數(shù)值v從第f行出現(xiàn)，一共有n個（即f到f+n？1行）。例如：數(shù)值4出現(xiàn)在12-18行，則編碼為 （4，12，7）。

無序且Distinct值不多。對于每個取值v構(gòu)造一個二進制串b，表示v所在位置的Bitmap。例如：如果一列的數(shù)據(jù)是0，0，1，1，2，1，0，2，1，則編碼為（0，110000100）、（1，001101001）和（2，000010010）。由于Bitmap是稀疏的，可以對其再進行行程編碼。

有序且Distinct值多。對于這種情況，把每個數(shù)值表示為前一個數(shù)值加上一個變化量（Delta），當然第一個數(shù)值除外。例如，對于一列數(shù)據(jù)1，4，7，7，8，12，可以表示為序列1，3，3，0，1，4。顯然編碼后的數(shù)據(jù)更容易被Dense Pack，且壓縮比更高。

無序且Distinct值多。對于這種情況沒有很好的編碼方式。

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

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

四、列式存儲與分布式文件系統(tǒng)

在現(xiàn)代的大數(shù)據(jù)架構(gòu)中，GFS、HDFS 等分布式文件系統(tǒng)已經(jīng)成為存放大規(guī)模數(shù)據(jù)集的主流方式。分布式文件系統(tǒng)相比單機上的磁盤，具備多副本高可用、容量大、成本低等諸多優(yōu)勢，但也帶來了一些單機架構(gòu)所沒有的問題：

讀寫均要經(jīng)過網(wǎng)絡(luò)，吞吐量可以追平甚至超過硬盤，但是延遲卻要比硬盤大得多，且受網(wǎng)絡(luò)環(huán)境影響很大；

可以進行大吞吐量的順序讀寫，但隨機訪問性能很差，大多不支持隨機寫入。為了抵消網(wǎng)絡(luò)的 Overhead，通常寫入都以幾十MB為單位。

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

要想將分布式文件系統(tǒng)的性能發(fā)揮到極致，無非有幾種方法：按塊（分片）讀取數(shù)據(jù)、流式讀取、追加寫入等。我們在后面會看到一些開源界流行的列式存儲模型，將這些優(yōu)化方法體現(xiàn)在存儲格式的設(shè)計中。

五、列式存儲系統(tǒng)案例

1、C-Store （2005） / Vertica

大多數(shù) DBMS 都是為了寫優(yōu)化，而 C-Store 是第一個為了讀優(yōu)化的 OLTP 數(shù)據(jù)庫系統(tǒng)，雖然從今天的視角看它應(yīng)當算作 HTAP 。在 Ad-Hoc 的分析型查詢、ORM 的在線查詢等場景中，大多數(shù)操作都是查詢而非寫入，在這些場景中列式存儲能取得更好的性能。像主流的 DBMS 一樣，C-Store 支持標準的關(guān)系型模型。

就像本文開頭即提到——列式存儲不是新鮮事。C-Store 的主要貢獻有以下幾點：

通過精心設(shè)計的 Projection 同時實現(xiàn)列數(shù)據(jù)的多副本和多種索引方式；

用讀寫分層的方式兼顧了（少量）寫入的性能；

此外，C-Store 可能是第一個現(xiàn)代的列式存儲數(shù)據(jù)庫實現(xiàn)，其設(shè)計啟發(fā)了無數(shù)后來的商業(yè)或開源數(shù)據(jù)庫，就比如 Vertica。

數(shù)據(jù)模型

C-Store 是關(guān)系型數(shù)據(jù)庫，它的邏輯表和其他數(shù)據(jù)庫中的并沒有什么不同。但是在 C-Store 內(nèi)部，邏輯表被縱向拆分成 Projections，每個 Projection 可以包含一個或多個列，甚至可以包含來自其他邏輯表的列（構(gòu)成索引）。當然，每個列至少會存在于一個 Projection 上。

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

Projection 內(nèi)是以列式存儲的：里面的每個列分別用一個數(shù)據(jù)結(jié)構(gòu)存放。為了避免列太長引起問題，也支持每個 Projection 以 Sort key 的值做橫向切分。

查詢時 C-Store 會先選擇一組能覆蓋結(jié)果中所有列的 Projections 集合作為 Covering set，然后進行 Join 計算重構(gòu)出原來的行。為了能高效地進行 Projections 的 Join（即按照另一個 Key 重新排序），引入 Join Index 作為輔助，其中存儲了 Proj1 到 Proj2 的下標映射關(guān)系。

Projection 是有冗余性的，常常 1 個列會出現(xiàn)在多個 Projections 中，但是它們的順序也就是 Sort key 并不相同，因此 C-Store 在查詢時可以選用最優(yōu)的一組 Projections，使得查詢執(zhí)行的代價最小。

巧妙的是，C-Store 的 Projection 冗余性還用來實現(xiàn) K-safe 高可用（容忍最多 K 臺機器故障），當部分節(jié)點宕機時，只要 C-Store 還能找到某個 Covering set 就能執(zhí)行查詢，雖然不一定是最優(yōu)的 Covering set 組合。

從另一個角度看，C-Store 的 Projection 可以看作是一種物化（Materialized）的查詢結(jié)果，即查詢結(jié)果在查詢執(zhí)行前已經(jīng)被預(yù)先計算好。并且由于每個列至少出現(xiàn)在一個 Projection 當中，沒有必要再保存原來的邏輯表。

為任意查詢預(yù)先計算好結(jié)果顯然不現(xiàn)實，但是如果物化某些經(jīng)常用到的中間視圖，就能在預(yù)計算代價和查詢代價之間獲得一個平衡。C-Store 物化的正是以某個 Sort key 排好序（甚至 JOIN 了其他表）的一組列數(shù)據(jù)，同時預(yù)計算的還有 Join Index。

2、Apache ORC

Apache ORC 最初是為支持 Hive 上的 OLAP 查詢開發(fā)的一種文件格式，如今在 Hadoop 生態(tài)系統(tǒng)中有廣泛的應(yīng)用。ORC 支持各種格式的字段，包括常見的 Int、String 等，也包括 Struct、List、Map 等組合字段，字段的 meta 信息就放在 ORC 文件的尾部（這被稱為自描述的）。

數(shù)據(jù)結(jié)構(gòu)及索引

為分區(qū)構(gòu)造索引是一種常見的優(yōu)化方案，ORC 的數(shù)據(jù)結(jié)構(gòu)分成以下 3 個層級，在每個層級上都有索引信息來加速查詢：

File Level：即一個 ORC 文件，F(xiàn)ooter 中保存了數(shù)據(jù)的 meta 信息，還有文件數(shù)據(jù)的索引信息，例如各列數(shù)據(jù)的最大最小值（范圍）、NULL 值分布、布隆過濾器等，這些信息可用來快速確定該文件是否包含要查詢的數(shù)據(jù)。每個 ORC 文件中包含多個 Stripe。

Stripe Level：對應(yīng)原表的一個范圍分區(qū)，里面包含該分區(qū)內(nèi)各列的值。每個 Stripe 也有自己的一個索引放在 Footer 里，和 File-Level 索引類似。

Row-Group Level ：一列中的每 10000 行數(shù)據(jù)構(gòu)成一個 Row-Group，每個 Row-Group 擁有自己的 Row-Level 索引，信息同上。

ORC 里的 Stripe 就像傳統(tǒng)數(shù)據(jù)庫的頁，它是 ORC 文件批量讀寫的基本單位。這是由于分布式儲存系統(tǒng)的讀寫延遲較大，一次 IO 操作只有批量讀取一定量的數(shù)據(jù)才劃算。這和按頁讀寫磁盤的思路也有共通之處。

像其他很多儲存格式一樣，ORC 選擇將統(tǒng)計數(shù)據(jù)和 Metadata 放在 File 和 Stripe 的尾部而不是頭部。

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

ACID 支持

Apache ORC 提供有限的 ACID 事務(wù)支持。受限于分布式文件系統(tǒng)的特點，文件不能隨機寫，那如何把修改保存下來呢？

類似于 LSM-Tree 中的 MVCC 那樣，Writer 并不是直接修改數(shù)據(jù)，而是為每個事務(wù)生成一個 Delta 文件，文件中的修改被疊加在原始數(shù)據(jù)之上。當 Delta 文件越來越多時，通過 Minor Compaction 把連續(xù)多個 Delta 文件合成一個；當 Delta 變得很大時，再執(zhí)行 Major Compaction 將Delta 和原始數(shù)據(jù)合并。

這種保持基線數(shù)據(jù)不變、分層疊加 Delta 數(shù)據(jù)的優(yōu)化方式在列式存儲系統(tǒng)中十分常見，是一種通用的解決思路。

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

3、Dremel （2010） / Apache Parquet

Dremel 是 Google 研發(fā)的用于大規(guī)模只讀數(shù)據(jù)的查詢系統(tǒng)，用于進行快速的 Ad-Hoc 查詢，彌補 MapReduce 交互式查詢能力的不足。為了避免對數(shù)據(jù)的二次拷貝，Dremel 的數(shù)據(jù)就放在原處，通常是 GFS 這樣的分布式文件系統(tǒng)，為此需要設(shè)計一種通用的文件格式。

Dremel 的系統(tǒng)設(shè)計和大多 OLAP 的列式數(shù)據(jù)庫相比，并無太多創(chuàng)新點，但是其精巧的存儲格式卻變得流行起來，Apache Parquet 就是它的開源復(fù)刻版。要注意的是，Parquet 和 ORC 一樣都是一種存儲格式，而非完整的系統(tǒng)。

嵌套數(shù)據(jù)模型

Google 內(nèi)部大量使用 Protobuf 作為跨平臺、跨語言的數(shù)據(jù)序列化格式，相比 JSON 要更緊湊并具有更強的表達能力。Protobuf 不僅允許用戶定義必須（Required）和可選（Optinal）字段，還允許用戶定義 Repeated 字段，意味著該字段可以出現(xiàn) 0～N 次，類似變長數(shù)組。

Dremel 格式的設(shè)計目的就是按列來存儲 Protobuf 的數(shù)據(jù)。由于 Repeated 字段的存在，這要比按列存儲關(guān)系型的數(shù)據(jù)困難一些。一般的思路可能是用終止符表示每個 Repeat 結(jié)束，但是考慮到數(shù)據(jù)可能很稀疏，Dremel 引入了一種更為緊湊的格式。

作為例子，下圖左半邊展示了數(shù)據(jù)的 Schema 和 2 個 Document 的實例，右半邊是序列化之后的各個列：

序列化之后的列多出了 R、D 兩列，分別代表 Repetition Level 和 Definition Level，通過這兩個值就能確保唯一地反序列化出原本的數(shù)據(jù)。

Repetition Level 表示當前值在哪一個級別上重復(fù)。對于非 Repeated 字段只要填上 Trivial 值 0 即可；否則，只要這個字段可能出現(xiàn)重復(fù)（無論本身是 Repeated 還是外層結(jié)構(gòu)是 Repeated），應(yīng)當為 R 填上當前值在哪一層上 Repeat。

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

第一個是 en-us，出現(xiàn)在第一個 Name 的第一個 Lanuage 的第一個 Code 里面。在此之前，這三個元素是沒有重復(fù)過的，都是第一次出現(xiàn)。所以其 R=0

第二個是 en，出現(xiàn)在下一個 Language 里面。也就是說 Language 是重復(fù)的元素。Name.Language.Code 中Language 排第二個，所以其 R=2

第三個是 en-gb，出現(xiàn)在下一個 Name 中，Name 是重復(fù)元素，排第一個，所以其 R=1

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

Definition Level 是為了說明 NULL 被定義在哪一層，也就宣告那一層的 Repeat 到此為止。對于非 NULL 字段只要填上 Trivial 值，即數(shù)據(jù)本身所在的 Level 即可。

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

us 非 NULL 值填上 Country 字段的 Level 即 D=3

NULL 在 R1 內(nèi)部，表示當前 Name 之內(nèi)、后續(xù)所有 Language 都不含有 Country 字段，所以D為2。

NULL 在 R1 內(nèi)部，表示當前 Document 之內(nèi)、后續(xù)所有 Name 都不含有 Country 字段，所以D為1。

gb 非 NULL 值填上 Country 字段的 Level 即 D=3

NULL 在 R2 內(nèi)部，表示后續(xù)所有 Document 都不含有 Country 字段，所以D為0。

可以證明，結(jié)合 R、D 兩個數(shù)值一定能唯一構(gòu)建出原始數(shù)據(jù)。為了高效編解碼，Dremel 在執(zhí)行時首先構(gòu)建出狀態(tài)機，之后利用狀態(tài)機處理列數(shù)據(jù)。不僅如此，狀態(tài)機還會結(jié)合查詢需求和數(shù)據(jù)的 Structure 直接跳過無關(guān)的數(shù)據(jù)。

狀態(tài)機實現(xiàn)可以說是 Dremel 論文的最大貢獻。但是受限于篇幅，有興趣的同學(xué)請參考文末的“文章參考”。

六、總結(jié)

本文介紹了列式存儲的存儲結(jié)構(gòu)設(shè)計。拋開種種繁復(fù)的細節(jié)，我們看到，以下這些思想或設(shè)計是具有共性的：

跳過無關(guān)的數(shù)據(jù)。從行存到列存，就是消除了無關(guān)列的掃描；ORC 中通過三層索引信息，能快速跳過無關(guān)的數(shù)據(jù)分片。

編碼既是壓縮，也是索引。Dremel 中用精巧的嵌套編碼避免了大量 NULL 的出現(xiàn)；C-Store 對 Distinct 值的編碼同時也是對 Distinct 值的索引；PowerDrill 則將字典編碼用到了極致。

假設(shè)數(shù)據(jù)不可變。無論 C-Store、Dremel 還是 ORC，它們的編碼和壓縮方式都完全不考慮數(shù)據(jù)更新。如果一定要有更新，暫時寫到別處、讀時合并即可。

數(shù)據(jù)分片。處理大規(guī)模數(shù)據(jù)，既要縱向切分也要橫向切分，不必多說。