列式存储系列（二）: Vertica

本文是列式存储系列的第二篇。在上一篇，我们介绍了C-Store，一个列式存储数据库。在本篇，我们讲述 C-Store 的继任者——Vertica。C-Store 是一个概念原型，在这个概念原型提出并发表后，Stonebraker 着手建立了一家公司研发商用的列式分析型数据库，公司名字就叫 Vertica。2011 年 Vertica 被惠普公司收购。2012 年，Vertica 公布了它的论文：《The Vertica Analytic Database: C-Store 7 Years Later》。Vertica 没有使用 C-Store 的任何代码，仅仅是借鉴了 C-Store 的某些设计思想。同时，对于 C-Store 一些设计不合理的地方，Vertica 提出了改进措施。在这篇文章里，Vertica 详细介绍了那些与 C-Store 不同的设计及其背后的设计考量。

Projection

C-Store 的核心概念是 Projections，即一张表的若干列子集构成一个 projection，多个 projection 的并集构成整张表。每个 projection 有自己的 sort-order。Projection 的概念类似于物化视图。但是物化视图要更为复杂，它往往还包含聚合、索引、join 等内容，而 projection 仅仅包含数据。Vertica 继承了 C-Store 的这个概念。

上图是 projection 的一个示例。对于一张原始表，它被拆分成了两个 projection。第一个 project 包含原表的全部五个字段，并按照 date 排序。第二个 projection 包含两个字段，并按照 cust 排序。在 Vertica 中，数据被分段（segment）存储到不同的节点。每个 projection 有不同的分段依据。在第一个 projection 中，分段依据为 hash(sale_id)，第二个 projection 中，分段依据为 hash(cust)，即图中浅色的字段。

在 C-Store 的介绍文章中我们有提到，projection 的设计的核心难点在于，如何根据几个 partial projection 还原出原表，因为不同的 projection 中数据的排序都是不一样的。C-Store 采用了一种 Join-Index 的做法（具体原理请参考上一篇文章）。Vertica 没有采用 Join-Index，而是要求所有的表都必须要有一个 super projection，即包含所有列的 projection。之所以不采用 Join-Index 是因为维护 Join-Index 的负担过重，已经远远超出了 projection 设计带来的好处。不过这里笔者有点疑惑，根据 Join-Index，我们能够根据 partial projections 还原出原 row（或者原 row 的一部分），但是 Vertica 没有 Join-Index，要根据 partial projection 获得原 row（或者原 row 的一部分）是不可能的，我们只能从 super projection 去读。例如，假设原表有 200 个列，super projection 包含全部的列。projection 1 包含列 3，4，5，并且按照列 3 排序，projection 2 包含列 5，6，7，并且按照列 5 排序。如果要查询列 3，4，5，6，7，我们不能从 projection 1 join projection 2 得到结果，只能读 super projection。这样看来，Vertica 实际上牺牲了 C-Store projection 的灵活性。可惜的是 Vertica 论文并没有交代这些细节。

除此之外，Vertica 还保留了 C-Store 中设计的 prejoin projection，即一个 projection 可以包含多张表（如一张事实表和多个维表）的列，只要它们之间存在外键关系即可。

Partitioning 和 Segmentation

同其他数据库类似，Vertica 支持分区（Partitioning）。Vertica 的分区在物理上的表现是在一个节点内部，对存储划分不同的 logical region，这样就能达到并行处理不同分区的能力。除了分区，Vertica 还支持分段（Segmentation）。在上一小节有提到，对于一个 projection，会按照其中一个字段 hash 为一个个独立的 segments，然后将 segments 分发到不同的 nodes 存储。与分区不同的是，分段是在节点间扩展的，而分区是在节点内。

Vertica 的 projection 可以有副本（replica）。副本也按照 segment 存储。副本设计的优点是一方面增加了系统的可用性，另一方面也能够在一定程度上提高并发性。

对于分区和分段，我们也能够从其他的分布式系统中看到一些类似的设计。对于 Hive 这种 Hadoop based 的 NoSQL 系统，由于存储本身为分布式存储，因此上层大体上是不太管怎么存的，但是上层必须要根据 HDFS 上 block 的存储做本地性优化。这个有点类似于 Vertica 的分段，均是大文件跨节点存储。在开源搜索系统 Elasticsearch 中，一个索引被划分为 Shard，并跨节点存储，也是和这里的分段类似的。ES 的 Shard 也有 replica。可见，在分布式环境下对存储做分区和分段，是一种通常的做法。

ROS 和 WOS

Vertica 实现了 ROS（Read Optimized Store）和 WOS（Write Optimized Store），其作用和 C-Store 中的 RS 和 WS 类似。ROS 负责管理存储在磁盘上的数据，而 WOS 则运行在内存中，用于应对频繁的 Insert/Delete/Update 等操作。当 WOS 中的数据到达一定量之后，会运行 Tuple Mover 将 WOS 中的数据移动至 ROS。

C-Store 的 RS 主要负责存储 segments 数据和相应的 Join-Index，而在 Vertica 中没有 Join-Index，因此这部分数据就不用存了。但是 ROS 还存了另外一类数据：Position-Index。Position-Index 不是存储每一条数据的 position，而是有点类似于 Parquet 文件中的 meta。它记录了磁盘上每个数据块的起始位置、数据的最大值最小值等信息。这些信息可以用来在运行时过滤数据。

ROS 有个概念叫做 ROS container。一个 container 是一个小的“容器”，容纳一部分数据。这样做的好处是可以在一定程度上提高数据处理的并发性（节点内并发）。图 3 展示了一个 projection 在一个 node 内的存储状况。

在这个例子中，首先数据在节点内是分区的，分区列为 MONTH/YEAR，分为 3/2012、4/2012、5/2012、6/2012 四个区。然后数据根据 hash(cid) 分段，分为三个段：Segment 1，2，3. 每个段的数据占用一定数量的 container 用于存储数据，在这里有 14 个 container。对于每个 column，Vertica 存储两个文件：数据文件和 Position-Index，这样总共有 28 个数据文件和 28 个 Position-Index 文件。

Execution Engine

Vertica 设计了一套并行化的、管道式的执行引擎。这一部分的介绍比较枯燥乏味，并且和其他的 pipline 式的 SQL 执行引擎大同小异（如 impala、presto 等）。这里介绍一下 Vertica 论文中特意提到的执行引擎的优化点。

1. Sideways Information Passing(SIP)。名字非常高大上，但是原理比较简单，就是利用一些“不是非常直观的信息”生成 predicate。所谓“不是非常直观的信息”就是从 plan 中 infer 出来的信息。比如对于 HashJoin，如果表被 hash 的表较小，那么可以提前 collect 相应的值，分发到大表端进行过滤数据。这个特性 Hive 也有，叫做 “Runtime Filter”。另外，EMR-Spark 也实现了这个特性，有兴趣的同学可以测试体验一下。Vertica 的 SIP 除了 Hash Join 还用到了 Merge Join 上，但是论文没有具体讲。
2. 算法的运行时调整。比如 HashJoin 发现 Hash table 在内存中无法放下，它会转为 Merge Join。
3. Prepass 算子。它本质上是多线程的预先执行一些操作，然后这些操作的结果可以被下游的 operator 利用生成最终结果。Vertica 给了个例子，如图 4 所示。对于 GroupBy，Vertica optimizer 会生成几个 stage 来执行。其中第一个 stage 会生成一个 L1 缓存同等大小的 HashTable（从这点上看，Vertica 确实做到了硬件级别的优化），用来预先聚合数据（图 4 中倒数第二个算子），并把这些数据发送到下游。当一批数据聚合好后 clear 掉 HashTable，再聚合下一批。最终的 GroupBy 是在正数第三个算子实现的。从这个原理上看，我觉着与其叫做 Prepass，不如叫算子下推更为合适一些。

1. JIT（Just-in-time Compilation）。在很多计算中，计算都是类型相关的。为了避免类型判断带来的开销以及虚调用，很多计算引擎利用了 JIT 技术来提升性能，Vertica 也不例外（这几乎成了现在 SQL 执行引擎的标配了）。不过 JIT 是一个非常考验技术的技术，JIT 做的好并不容易。

其他

讲了数据模型、存储和计算引擎，Vertica 的核心就介绍完了。Vertica 的论文还介绍了 Tuple Mover、事务管理、容灾等细节，这里就不介绍了，有兴趣的读者可以参阅论文。

总结

本文就 Vertica 的数据模型、存储、执行引擎以及这几个方面与 C-Store 的区别进行了简单的介绍。总的来说，Vertica 是一个纯正的列式存储数据库，为此，Vertica 设计实现了 projection 这一数据模型，并围绕该模型设计实现了一套大数据分析管理引擎。在 NoSQL 风起云涌的时代，Vertica 能够凭借自身良好的设计，在广大 NoSQL 方案包围圈里争得一席之地，且没有开源优势，充分说明了它的实力。

参考文献

[1] Andrew Lamb et.al. The Vertica Analytic Database: C-Store 7 Years Later. In VLDB, pages 1790-1801, 2012.