列式存储系列（一）C-Store

序

本文是列式存储系列的第一篇。在这个系列中，我们将介绍几个典型的列式存储系统。这些列式系统的出现都有各自的时代背景。在介绍这些系统的同时，我们也尽量介绍一下它们的背景，以便大家有一个更宏观的认识，理解这个系统为什么会出现，它要解决的问题，以及它如何影响后来类似系统的发展。

列式存储不是一个新概念，它最早可以追溯到上个世纪 70 年代。在上个世纪六七十年代，数据库学者们的主题是如何定义一个数据模型，以便更好的存储、管理和使用数据。被提出的数据模型多种多样，其核心就是构造什么样的逻辑关系，设计什么样的存储结构和计算方法，满足人们存储、管理和使用数据的需求。在这种背景下，1970 年就诞生了我们后来熟知的关系型数据模型[1]。关系型数据模型是一种逻辑模型，只关心数据的组织方式，不关心底层的存储，也就是说，它只是定义了一个数据该如何被组织、被表现的接口，至于底层，它是不关心的。由于一个关系被组织成一张表，所以天然的想法就是按照多维数组的方式存储数据，这种存储模型称为 n-array 存储模型（也叫 NSM）。传统的 n-array 模型按照数据写入的方式，将数据一行一行的存储下来，形成一个行优先的表。这种存储模型对数据的插入、删除、更新友好，是 OLTP 工作负载的理想选择。1985 年，Copeland 和 Khoshafian 提出了一种称为 “Decomposition Storage Model” DSM 存储模型[2]，在这种模型中，数据以属性（也就是列）的方式进行存储，每一行数据有一个代理主键，每个列存代理主键和该列的值。当用户查询时，系统从最底层的存储层取出相应的列，并通过一定的算法还原出用户想要的 row，并返回给用户。DSM 的数据模型大概是下面这个样子

DSM 模型的特点是数据按列存储，每列数据定长，易于压缩。由于数据是排序的，因此可以按照列偏移量进行读取。另外，读取时可以只读取涉及到的列，而不涉及的列则不参与计算。这些特点使得 DSM 对分析任务友好。引起了业界的关注，启发并产生了一些基于列式存储的商用分析系统，如 SyBase IQ[7]。不过在 90 年代，数据量还不是很大，所以更多的数据仓库的设计都是基于关系型数据库的，数据库提供商想用一套方案覆盖所有场景，称之为“One Size Fits All”[3]。这种“One Size Fits All”的尝试在 2000 年后变得不再适应时代，因为互联网的爆发使得数据量激增，用户分析数据的时间花费变得非常漫长。在这种背景下，业界不得不探索新的解决方案。现实需要直接结果就是推动了整个分析型时长的繁荣。也就是大约 2005 年以后，我们看到了各种针对大数据量的分析型引擎雨后春笋般出现了（Google 的 Bigtable[6] 论文发表于 2006 年）。

下图是 column store 的一个发展历史[8]。（columns store 是基于列式的数据库系统，和目前流行的 NoSql 概念上还不太一样，注意图中 “Re-birth” 一词的含义）

C-Store 概述

今天要介绍的第一个列式存储系统为 C-Store。C-Store 不像其他大数据系统那样出名，但在分析型数据库历史中的地位还是非常高的。C-Store 的提出者是 Michael Stonebraker，是数据库领域四位图领奖获得者之一，也是著名的商用分析系统 Vertica、开源数据库 Postgresql 的发明者。Vertica 正式基于 C-Store 的原型开发的，由此也可见 C-Store 的地位。

在 C-Store 的论文中，作者明确了写优化与读优化两种系统的工作场景，并把前者行优先的存储方式称为 row-store，而列的方式称为 column-store（不知道 column store 一词是否由此而来）。作者指出了row-store 类型的系统在进行分析任务时运行低效的问题，并给出了 C-Store 如何解决这些问题的。同时，针对 column-store 不擅长的数据更新，作者也给出了自己的解决方案。这些 argue point 简要列在下面：

• 需要额外精力处理内存对齐。CPU 运算速率以摩尔定律增长，而相应的主存存取速率却增长有限。一次性的主存访问大约需要几百个 CPU 周期。在这种情况下，数据库实现者需要仔细考虑内存对齐，以避免数据跨越边界，造成处理一次数据需要两次访问内存的情况。C-Store 不存在这个情况，因为列的长度都是固定的，一次可以处理 N 条数据，使得 N 条数据恰好填满一个数据块。
• 一般的数据块使用 B-tree 进行索引。索引键一般是主键。对于其他列，往往通过创建二次索引来进行快速检索。二次索引在进行点查时需要读取完数据才知道该条数据符不符合要求。因此为了增加查询性能，数据库系统需要引入对读友好的其他存储结构，比如 bit-map 索引，交叉表索引以及物化视图等等。C-Store 的处理方式有些不同。它将一个表的一个到多个列组成一个 projection，多个 projections 的并集为该表，且每个列可能属于多个 projections。Projection 可以按照某个列进行排序，这样一个列可能有多个排序方式。在查询时选择合适的 projection 就能达到一个比较好的效果。
• C-Store 的 projection 带来了额外的好处。在集群环境下，存储成本很低，数据往往存在多份拷贝。但是没有必要为所有数据进行一模一样的拷贝备份。C-Store 将列分开存储，涉及查询频繁的列可以存放多份拷贝，并且存放在不同的 projection 里，使用不同的 sort order。这样 C-Store 在高性能和 HA 两方面取得了很好的平衡
• 插入删除更新。虽然数据仓库更多的使用方式是批量的导入，很少的更新，但是更新也是有必要的。而且，发展趋势则是使数据流式地进入系统，甚至在线更新数据仓库中的数据。针对这样的需求，C-Store 设计了一个两层的架构，上层是一个面向写的 Writeable Store(WS)，下层有一个面向读的 Read-Optimized Store(RS)，中间运行一个 Tuple Mover 不断地将数据从 WS 移至 RS：

在支持事务方面，C-Store 使用基于快照的事务方案，用于避免额外的锁开销。

数据模型

C-Store 的核心是 projection。一个 projection 就是一个或多个列的“部分表”，多个 projections 可以合成一张表，同时，一个表的一个列也可以出现在多个 projection 当中。一个 projection 中也可以包含其他表的列，前提是该 projection 所属（原文称 anchor，即锚表）表含有该其他表列的外键。一个 projection 有一个 sort key，用于确定该 projection 数据的排列方式。下面是一张逻辑表，以及几个可能的 projections：

其中 projection 括号中竖线后边的键为 sort key。另外，一个 projection 可以被按列拆分成多个分区，称为 segments，存放在不同的节点上。

有了 projections，一个核心问题是如何通过 projections 构建原表（这是所有列式系统共同的问题）。C-Store 的工具有两个：

• Storage Keys(SK): C-Store 为每个 segment 中的每个列赋予一个 SK，SK 对应原逻辑表中对应列的位置。
• Join Indices: Join Indices 用于关联不同 projections，下图是一个例子：

可以看到，EMP1 和 EMP3 通过一个 Join Indices 相联系，从而构造出 (Name, Salary, Age) 这个 tuple。值得注意的是，这个 join indices 是单向的。为了构造出整张表，C-Store 需要在多个 projections 的 join indices 中找到一条能够构造出整张表的path（在上面的例子中，至少需要两个合理的 join indices，比如从 EMP3 到 EMP1 再到 EMP2，才能构造出原表）。C-Store 的这套 join indices 也有不足，即维护成本很高。所以作者建议一个列最好保存在多个 projections 中，也就是说，尽量避免一个 projection 仅包含一个列这样琐碎，以减少 join indices 的数量。如果 projection 包含的列很多，存储成本会相应加大，但是性能会提升，反之存储成本下降，性能也下降，这是一个权衡的因素。

WS 和 RS

RS 的主要功能是保存 projections 以及相应的 join indices。为了和 RS 保持一致，减轻 Tuple Mover 的额外开销，WS 中也保存了同样的 projections 和 join indices，只不过，WS 中经过了优化，以适应大量的写：首先 WS 中的 projections 并没有被压缩，其次，WS 中使用 B-tree 而不是直接排序来保证存储的顺序。WS 中的列按照 (v, sk) 的方式进行存储，其中 v 是属性的值，sk 是该列的 storage key，并且按照 B-tree 索引。对于 sort key，(v, sk) 就简化为 (s, sk)，其中 s 就是 sort key。在进行基于 sort key 的查询时，首先根据 (s, sk) 找到 sk，然后再根据 sk 和 (v, sk) 获得其他列的值。

WS 和 RS 通过 Tuple Mover 相联系。Tuple Mover 使用一个类似于 LSM 的结构将 WS 中的数据持久化，并发往 RS 进行存储。

事务

C-Store 提供快照隔离的机制包保证事务。具体地说，当记录被插入时，其获得一个时间戳，如果查询某一个快照 S，那么时间戳大于 S 对于时间戳的那些记录将会被忽略。同时，update 操作也不是原地更新，而是被分成了 delete 和 insert 两个动作，delete 的 record 会被记录一个删除标记。这一点和 Hive ACID-2.0 是一样的（但是 C-Store 是 05 年的系统）。与 HIVE ACID-2.0 有点不一样的是，HIVE 使用了WriteId 来跟踪事务的顺序，WriteId 由中心化的 Metastore 产生。WriteId 跟 TransactionId 之间有些关联，当一个 Transaction 完成后，相应的 WriteId 就被持久化到 Metasotre，之后的读就可以读该 WriteId 及之前的记录了。C-Store 则使用类似的概念，称为“水位（Water Mark）”，水位有高水位和低水位，只有那些位于两者之间的记录才能被读取。C-Store 的水位用“时间戳”来标识，但这个时间戳不是真正的时间戳，而叫做 epoch。C-Store 引入了一个中心化的 Time Authority TA 节点，它在启动时将 epoch 设置为 0，此后周期性的将 epoch 加 1，并发送给其他节点。epoch 是时间的最小粒度。epoch 的工作原理如下图所示，当某个 epoch 结束开始一个新的 epoch 时，TA 发送 end of epoch 给各个节点。各个节点等待在此次 epoch 内的事务（包括之前未完成的事务）完成后发送 Epoch complete 到 TA。等 TA 收集到所有节点的 Epoch complete 事件后，TA 将水位更新。

对于事务的并发控制，C-Store 采用严格的两阶段封锁协议。在事务的提交方面，它使用省略了 PREPARE 阶段的两阶段提交协议来实现。

性能

C-Store 论文里给了它与传统数据库以及和其他 Columns based 的数据库的性能对比，第一个表格为数据体积，第二个表格为 TPC-H 中 7 个query 的性能

C-Store 论文里特别提到了它对于数据无解压处理的能力，并称这是其性能优异的一个很重要的因素。

总结

本文介绍了 C-Store 系统，它提出了一种混合架构，上层提供了面向写的 Write store，下层是面向读的 Read store。其核心设计点为 projections，一种基于列的存储结构。C-Store 面向列的设计使得其对于分析有着优秀的性能表现。此外，C-Store 还提供了基于快照隔离的事务功能。

参考文献

[1] E. F. CODD. A Relational Model of Data for Large Shared Data Banks
[2] George P. Copeland, Setrag N. Khoshafian. A decomposition storage model
[3] Michael Stonebraker, Ugur Cetintemel. "One Size Fits All": An Idea Whose Time Has Come and Gone
[4] Clark D. French. One Size Fits All Database Architectures Do Not Work for DSS
[5] Mike Stonebraker, et,al. C-store: a column-oriented DBMS. In VLDB, pages 553–564, 2005.
[6] Fay Chang, Jeffrey Dean, et,al. Bigtable: A Distributed Storage System for Structured Data
[7] http://www.sybase.com/products/databaseservers/sybaseiq
[8] Column_Store_Tutorial_VLDB09()

声明

限于本人水平，文中内容仅供参考。更加详情请阅读原论文。同时欢迎读者批评指正，共同探讨。