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

C-Store (2005) / Vertica

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

[[234040]]

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

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

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

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

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

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

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

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

來(lái)；二是 (sort_key -> storage_key)，用于滿(mǎn)足主鍵查詢(xún)的需求。

值得一提的是，WS 是一個(gè) MVCC 的存儲(chǔ)——它的每個(gè)數(shù)據(jù)都保存了對(duì)應(yīng)的寫(xiě)入事務(wù)編號(hào)，同一行可能有多個(gè)版本同時(shí)存在。而 RS 是沒(méi)有 MVCC 的，你可以將它看作過(guò)去某個(gè)時(shí)間點(diǎn)的快照。

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

事務(wù)支持

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

LWM 對(duì)應(yīng) RS 即基線數(shù)據(jù)的版本。Tuple Mover 會(huì)保證任何高于 LWM 的修改都不會(huì)被移動(dòng)到 RS 中，因?yàn)橐坏┮苿?dòng)到 RS 也就失去了多版本。

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

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

MonetDB (2012) / VectorWise

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

BAT Algebra

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

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

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

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

Apache Kudu (2015)

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

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

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

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

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

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

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

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

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

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

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

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

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

PowerDrill (2012)

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

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

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

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

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

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

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

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

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

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

1. Chunk 0 存儲(chǔ)的 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ù)存儲(chǔ)。這不僅能節(jié)省空間，也能加快掃描速度。

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

分區(qū)索引

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

步驟如下：

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

總結(jié)

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

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

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