本文將介紹若干個典型的列式存儲數(shù)據(jù)庫系統(tǒng)。作為完整的 OLAP 或 HTAP 數(shù)據(jù)庫系統(tǒng)，他們大多使用了自主設(shè)計的存儲方式，運行在多臺機器節(jié)點上，使用網(wǎng)絡(luò)進(jìn)行通訊協(xié)作。

C-Store (2005) / Vertica

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

[[234040]]

關(guān)于 C-Store 特有的 projection 數(shù)據(jù)模型。這里做一下簡單的回顧：每個 projection 可以包含一個或多個列，完整的表視圖需要通過若干 projection JOIN 得到。Projection 水平拆分成若干 segments。

C-Store 的設(shè)計考慮到企業(yè)級應(yīng)用的使用模式，在優(yōu)化 AP 查詢的同時兼顧了大多數(shù) DBMS 具有的 TP 查詢功能。在 ACID 事務(wù)方面同樣提供了完整的支持，支持快照（snapshot）讀事務(wù)和一般的 2PC 讀寫事務(wù)。

通常而言，互聯(lián)網(wǎng)應(yīng)用對 DBMS 有較高的并發(fā)寫入需求，對一致性讀、分析型查詢的需求不那么強烈。而企業(yè)級應(yīng)用（例如 CRM 系統(tǒng)）的并發(fā)寫入需求不大，但需要對一致性讀、分析型查詢等。

系統(tǒng)設(shè)計

C-Store 將其物理存儲也就是每個 projection 分成兩層，分別是為寫優(yōu)化的 Writeable Store (WS) 和為讀優(yōu)化的 Read-optimized Store (RS)。RS 即是基線數(shù)據(jù)，WS 上暫存了對 RS 數(shù)據(jù)的變更，二者在讀取時需要 merge 得到***的數(shù)據(jù)。在上一篇文章的 Apache ORC 格式種，我們也看到了類似的做法（基線數(shù)據(jù)疊加增量數(shù)據(jù)）。

RS 是一個為讀優(yōu)化的列式存儲。RS 中采用之前提到的 projection 數(shù)據(jù)模型，對不同的列采用了不同的編碼方式，根據(jù)它是否是 projection 的排序列、以及該列的取值個數(shù)，來決定采取何種編碼方式。

WS 用于暫存高性能的寫入操作，例如 INSERT、UPDATE 等。為了簡化系統(tǒng)的設(shè)計，WS 邏輯上仍然按照 projection 的列式模型存儲，但是物理上使用 B 樹以滿足快速的寫入要求。WS 基于 BerkeleyDB 構(gòu)建。

對于某一列中的某個值 v，會有兩個映射關(guān)系存在：一是 (storage_key -> v)，在 RS 中 storage_key 就是 segment 中的行號，但在 WS 中顯式的記錄下

來；二是 (sort_key -> storage_key)，用于滿足主鍵查詢的需求。

值得一提的是，WS 是一個 MVCC 的存儲——它的每個數(shù)據(jù)都保存了對應(yīng)的寫入事務(wù)編號，同一行可能有多個版本同時存在。而 RS 是沒有 MVCC 的，你可以將它看作過去某個時間點的快照。

Tuple Mover 周期性地將 WS 中的數(shù)據(jù)移動到 RS 中。與大多數(shù) MVCC 系統(tǒng)一樣，C-Store 中的更新是通過一個刪除加一個插入實現(xiàn)的，Tuple Mover 的主要工作是根據(jù) WS 的數(shù)據(jù)更新 RS：刪掉被刪除的行、添加新的行。

事務(wù)支持

C-Store 認(rèn)為大多數(shù)事務(wù)是只讀事務(wù)，因此采用了 Snapshot Isolation。C-Store 維護(hù)兩個全局的時間戳：低水位（Low Water Mark, LWM）和高水位（High Water Mark, HWM），允許用戶查詢介于二者之間的任意時間戳的 Snapshot。時間戳來自中心化的 Time Authority (TA)。

LWM 對應(yīng) RS 即基線數(shù)據(jù)的版本。Tuple Mover 會保證任何高于 LWM 的修改都不會被移動到 RS 中，因為一旦移動到 RS 也就失去了多版本。

HWM 由中心的 TA 維護(hù)，時間被分成固定長度的 epoch。當(dāng)各個節(jié)點確認(rèn) epoch e 中開始的寫入事務(wù)完成時，就會發(fā)送一個 Complete(e) 的消息給 TA，當(dāng) TA 收集到所有節(jié)點的 Complete(e) 將 HWM 置為 e。換句話說，HWM 以前的事務(wù)一定是已經(jīng)完成提交的。

對于讀寫事務(wù)，C-Store 采用了傳統(tǒng)的 2PC。

MonetDB (2012) / VectorWise

MonetDB 是一個面向 OLAP 的內(nèi)存數(shù)據(jù)。區(qū)別于大多數(shù) DBMS 使用的 Valcano 執(zhí)行模式，MonetDB 使用一種獨特的 full materialization 的列式（向量）執(zhí)行模型，也因此設(shè)計了對應(yīng)的一系列算子以及查詢優(yōu)化器。

BAT Algebra

MonetDB 獨有的列式計算是通過 BAT（Binary Association Table）的運算組成的，BAT 之間通過算子產(chǎn)生新的 BAT，最終生成查詢結(jié)果。每個 BAT 可以簡單地理解為一列帶有編號的數(shù)據(jù) <oid, value>，有些 BAT 來自用戶的邏輯表，其他則是運算的結(jié)果。每個算子被設(shè)計地很緊湊、高效，能充分利用 CPU 流水線的計算能力，這和 CPU 設(shè)計的 RISC 思想頗為相似，所以被稱為“數(shù)據(jù)庫查詢的 RISC 方案”。

如上圖，對于用戶一條 SELECT 查詢，MonetDB 先將其分解為多次 BAT 的運算，執(zhí)行計劃中的每一步的輸入和輸出都是 BAT。圖中藍(lán)框中為輸入的 BAT，其他則是執(zhí)行產(chǎn)生的運算結(jié)果。

MonetDB 的設(shè)計決定了它的計算過程十分耗費內(nèi)存。MonetDB 利用操作系統(tǒng)的 Memory Mapped File 進(jìn)行內(nèi)存管理，不使用的頁面可以被換出內(nèi)存，為執(zhí)行查詢騰出空間。但顯然這并不是一個徹底的解決方案。

VectorWise 使用類似的向量化執(zhí)行模型，但它嘗試在 full materialization 和 Valcano 模型中間尋求一個平衡——它將整個列劃分成較小的 block，對 block 進(jìn)行上述的 column algebra 計算。

Apache Kudu (2015)

Kudu 是 Cloudera 研發(fā)的處理實時數(shù)據(jù)的 OLAP 數(shù)據(jù)庫。上文提到的 Parquet / ORC 是開源界常用的處理靜態(tài)數(shù)據(jù)的方式，為什么說是靜態(tài)數(shù)據(jù)呢？因為這些緊湊的格式對數(shù)據(jù)修改很不友好，且隨機讀寫性能極差，通常只能用于后臺 OLAP。

所以我們看到，很多數(shù)據(jù)系統(tǒng)都采用動態(tài)、靜態(tài)兩套數(shù)據(jù)，例如：把在線業(yè)務(wù)數(shù)據(jù)放在 HBase 中，定期通過 ETL 程序產(chǎn)生Parquet 格式文件放到 HDFS 上，再對其進(jìn)行統(tǒng)計、歸檔等。這種定期導(dǎo)入的方式不可避免地會帶來小時級的延遲，而且，眾所周知維護(hù) ETL 代碼是一件費時費力的事情。

Kudu 試圖在 OLAP 與 OLTP 之間尋求一個平衡點——在保持同一份數(shù)據(jù)的情況下，既能提供在線業(yè)務(wù)實時寫入的能力，又能支持高效的 OLAP 查詢。

Kudu 采用我們熟悉的半關(guān)系型模型，允許用戶定義 schema，但是目前并不支持二級索引。

事務(wù)方面，Kudu 默認(rèn)使用 Snapshot Isolation 一致性模型。此外，如果用戶需要一個更強的一致性保證（例如 read own's writes），Kudu 也允許用戶指定特定的時間戳，讀取這個時間戳的 snapshot。這項功能被集成在 Kudu 的 API 層面，用戶可以方便地獲得因果（causality）一致性保證。

系統(tǒng)設(shè)計

Kudu 采用了類似 HBase 的 master-slave 架構(gòu)：中心節(jié)點被稱作 Kudu Master，數(shù)據(jù)節(jié)點被稱作 Tablet Server。一個表的數(shù)據(jù)被分割成多個 tablets，由它們對應(yīng)的 Tablet Server 來提供數(shù)據(jù)讀寫服務(wù)。

與 HBase 相比，中心節(jié)點 Kudu Master 除了存放了 Tablet 的分布信息，還身兼了如下角色：

• Catalog 管理：同步各個庫、表的 schema 等元信息、負(fù)責(zé)協(xié)調(diào)完成建表等 DDL 操作
• 集群協(xié)調(diào)者：各個 Tablet Server 向其匯報自己的狀態(tài)、replica 變更等

Kudu 底層數(shù)據(jù)文件并沒有存儲在 HDFS 這樣的分布式文件系統(tǒng)上，而是基于 Raft 算法實現(xiàn)了一套副本同步機制，保障數(shù)據(jù)不丟失及高可用性。其中 Raft 算法用于同步數(shù)據(jù)修改操作的 log，這點和大多數(shù) shared-nothing 架構(gòu)分布式數(shù)據(jù)庫并無二致。對 Raft 算法有興趣的同學(xué)可以參考原論文。

作為列式 OLAP 數(shù)據(jù)庫，Kudu 的磁盤存儲是常見的列式方案，很多地方直接復(fù)用了 Parquet 的代碼。我們知道，緊湊的列式存儲難以實現(xiàn)高效的更新操作。Kudu 為了提供實時寫入功能，采用了類似 C-Store 中的方案——在不可變的基線數(shù)據(jù)上，疊加后續(xù)的更新數(shù)據(jù)。

具體來說，Tablet 由 RowSet 組成，而 RowSet 既可以是內(nèi)存中的 MemRowSet，也可以是存儲在磁盤上的 DiskRowSet。一個 RowSet 包含兩部分?jǐn)?shù)據(jù)：基礎(chǔ)數(shù)據(jù)通常以 DiskRowSet 形式保存在磁盤上；而變更數(shù)據(jù)先以 MemRowSet 的形式暫存在內(nèi)存中，后續(xù)再異步地刷寫到磁盤上。和 C-Store 類似，內(nèi)存中的數(shù)據(jù)使用 B 樹存儲。

與 C-Store 不同的是，Delta 數(shù)據(jù)并不會立即和磁盤上的基線數(shù)據(jù)進(jìn)行合并，而是由后臺的 compaction 線程異步完成。值得注意的是，為了保證 compaction 操作不影響過去的 snapshot read，被覆蓋的舊數(shù)據(jù)也會以 UNDO 記錄的形式保存在另外的文件中。

PowerDrill (2012)

PowerDrill 是 Google 研發(fā)用于快速處理 ad-hoc 查詢的 OLAP 數(shù)據(jù)庫，為前端的 Web 交互式分析軟件提供支持。PowerDrill 的數(shù)據(jù)放在內(nèi)存中，為了盡可能節(jié)約空間，PowerDrill 引入一種全新的分區(qū)的存儲格式，在節(jié)省內(nèi)存占用的同時提供了類似索引的功能，能過濾掉無關(guān)的分區(qū)、避免全表掃描。

同是 Google 家的產(chǎn)品，和 Dremel 相比，PowerDrill 有以下幾點差異：

• 定位不同：Dremel 用于查詢“大量的大數(shù)據(jù)集”（數(shù)據(jù)集的規(guī)模都大，數(shù)據(jù)集很多），PowerDrill 用于查詢“少量的大數(shù)據(jù)集”（數(shù)據(jù)集的規(guī)模大，但數(shù)據(jù)集不多）
• Dremel 用全表掃描（full scan）處理查詢，而 PowerDrill 對數(shù)據(jù)做了分區(qū)，并能根據(jù)查詢只掃描用到的分區(qū)。
• Dremel 使用類似 Protobuf 的嵌套數(shù)據(jù)模型；PowerDrill 使用關(guān)系模型
• Dremel 的數(shù)據(jù)直接放在分布式文件系統(tǒng)上，而 PowerDrill 需要一個 load 過程將數(shù)據(jù)載入內(nèi)存

數(shù)據(jù)分區(qū)

Ad-hoc 查詢常常包含 GROUP BY 子句，在這些 group key 上進(jìn)行分區(qū)，能很好的過濾掉不需要的數(shù)據(jù)。PowerDrill 需要 DBA 根據(jù)自己對數(shù)據(jù)的理解，選出用于用于分區(qū)的一組屬性 Key1 Key2 Key3 ...（優(yōu)先級依次遞減）。分區(qū)是一個遞歸的過程：一開始把整個數(shù)據(jù)集視為一個分區(qū)（Chunk），如果 Key1 能將數(shù)據(jù)分開就用 Key1，否則用 Key2、Key3—……直到分區(qū)大小小于一個閾值。

以下是一個分區(qū)的例子，***次使用 Age 分區(qū)、第二次使用 Salary 分區(qū)。

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

PowerDrill 的數(shù)據(jù)組織以列為單位。對于每個列有一個全局字典表，列的每個分區(qū)有一個分區(qū)字典表：

• 全局字典表（global dictionary）存儲列中所有 distinct 的字符串，按字典順序排序。字典結(jié)構(gòu)是雙向的，既能將 string 映射到 global-id，也能從 global-id 查 string。
• 分區(qū)字典表（chunk dictionary）存儲一個分區(qū)中 chunk-id 到 global-id 的雙向映射。相應(yīng)地，數(shù)據(jù)列（elements）存儲 chunk-id 而不是 global-id。

如果要將 chunk 中的一個 element 也就是 chunk-id 還原成數(shù)據(jù)，***步需要查分區(qū)字典表，得到 global-id；第二步查全局字典表，得到原本的字符串?dāng)?shù)據(jù)。以上圖舉例而言：

1. Chunk 0 存儲的 chunk-id 數(shù)據(jù) [3, 2, 0, ...]
2. 根據(jù)分區(qū)字典表，查出 global-id：[5, 4, 1, ...]
3. 根據(jù)全局字典表，查出 search string: ['ebay', 'cheap flights', 'amazon', ...]

這樣的兩層映射保證 chunk-id 盡可能的小，所以可以用更緊湊的編碼，比如用 8bit、16bit 整數(shù)存儲。這不僅能節(jié)省空間，也能加快掃描速度。

此外，相同的數(shù)據(jù)只會在全局字典表中存一份。而且全局字典表中的字符串?dāng)?shù)據(jù)已經(jīng)被排序，相比不排序，排序后用 Snappy 等算法的壓縮比更高。

分區(qū)索引

上述的數(shù)據(jù)結(jié)構(gòu)還有一個額外的好處：它能快速算出某個分區(qū)是否包含有用的數(shù)據(jù)，幫助執(zhí)行器跳過無關(guān)的分區(qū)。以下面的 SQL 為例（數(shù)據(jù)參考上一張圖 Figure XXXX）：

步驟如下：

1. 在 search_string 列的全局字典表中查找 "[la redoute", "voyages sncf"]，得到 global-id [9, 11]
2. 在各個分區(qū)中查找 global-id [9, 11]： Chunk 0，Chunk 1 中都沒有找到，所以可以直接跳過；而 Chunk 2 中出現(xiàn)了 [11]，對應(yīng) chunk-id 為 [4]
3. 在 Chunk 2 中的 elements 掃描查出 chunk-id = 4 的元素數(shù)量一共有 3 次，作為 COUNT(*) 的結(jié)果返回。

總結(jié)

本文介紹了幾個知名的列式存儲系統(tǒng)。與上一篇文章不同，本文的系統(tǒng)大多重新設(shè)計了存儲層。與此同時，系統(tǒng)的復(fù)雜性也大大提升。

在構(gòu)建自己的數(shù)據(jù)系統(tǒng)時，除了存儲方式本身，以下幾個地方是著重需要考慮清楚的地方，上述的幾個系統(tǒng)也給我們提供了很好的參考：

• 系統(tǒng)需要處理的查詢是怎樣的模式？C-Store 主要服務(wù)于企業(yè)級 HTAP 場景，Kudu 在提供 OLAP 查詢能力的同時保持了一定的實時寫入能力，PowerDrill 著重處理 ad-hoc 的分析型查詢。
• 系統(tǒng)如何保證數(shù)據(jù)的持久性和高可用性？C-Store 在 projection 上保留了一定的冗余，Kudu 用 Raft 協(xié)議保持各個副本的數(shù)據(jù)一致性及可用性，PowerDrill 則直接把數(shù)據(jù)放在分布式文件系統(tǒng)上，因為不需要對數(shù)據(jù)作修改。
• 系統(tǒng)提供怎樣的數(shù)據(jù)一致性保證？對于只讀的系統(tǒng)來說，這不是個問題。但是一旦支持寫入，數(shù)據(jù)的一致性、事務(wù)隔離性都需要精心的考慮和權(quán)衡。Kudu 和 C-Store 的 Snapshot Read 實現(xiàn)可作為參考。