列式存储系列(二): Vertica

xy_xin 2019-08-27

列式存储 Vertica

列式存储系列(二): 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 的这个概念。

图1. Projection

上图是 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 存储。副本设计的优点是一方面增加了系统的可用性,另一方面也能够在一定程度上提高并发性。

图2. Segments 存储

对于分区和分段,我们也能够从其他的分布式系统中看到一些类似的设计。对于 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 内的存储状况。

图3. ROS container

在这个例子中,首先数据在节点内是分区的,分区列为 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,不如叫算子下推更为合适一些。

图4. Execution Engine

  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.

登录 后评论
下一篇
云攻略小攻
1451人浏览
2019-10-11
相关推荐
《Vertica的这些事》系列文章
1522人浏览
2016-11-03 13:18:00
列式存储系列(一)C-Store
783人浏览
2019-03-21 23:37:08
大数据,大创收!
648人浏览
2017-08-01 10:56:00
NOSQL数据模型和CAP原理
685人浏览
2017-11-16 20:27:00
0
0
0
388