C-Store：一个列存数据库

今天介绍《C-Store: A Column-oriented DBMS》，这篇文章是VLDB 2005的，作者 Mike Stonebraker，2015年图灵奖获得者。这篇文章很硬，是一个内容很丰富的系统论文，今天只介绍其中几个部分。

正文 1954 字，预计阅读时间 5 分钟。

C-Store官网：http://db.csail.mit.edu/projects/cstore/

背景知识

行式存储是当时数据库的主流，由于适用 OLTP 场景，于是叫做 write-optimized，而针对 OLAP 场景的系统叫做 read-optimized，如数据仓库。

CPU的增速比磁盘带宽快很多，于是可以牺牲一定的 CPU 来换取磁盘带宽。

有两种方式干这个事：（1）编码（2）densepack，紧凑存储，我理解就是压缩。

当时关系数据库不能很好的支持 OLAP 查询密集场景。于是作者提出了一个新的列存数据库 C-Store，这篇文章里包含很多内容，是个大杂烩，其中有几个新的特点：（1）write-optimized 和 read-optimized 混合架构 （2）存储模型，冗余的数据按不同顺序存储，来支持快速检索。（3）高效的压缩，直接处理压缩的数据（4）列式查询优化器（5）数据恢复（6）快照隔离避免 2PC

本文介绍其中的（1）（2）（5）

（1）混合架构

优化写入和优化查询是比较互斥的，比如直接按写入顺序存储数据，就像日志追加一样，但是这种方式对查询不友好，因为查询可能在另一种顺序下比较快。

一个模型适用两个场景是很难的，因此本文的架构是搞两个模块。一个模块负责处理快速写入，就是上边的 WS，一个模块负责提供高效的查询，就是下边的 RS，这样就需要一些连接器，就是 Tuple Mover，将 WS 中的数据同步到 RS 中。

作者的预期是 WS 相比 RS 而言是很小的一部分，可以全部放在内存中，其实这个架构就类似 LSM 了。

为了实现简便，C-Store 用同一套列存引擎来管理 WS 和 RS，只不过在 WS 中多存一些索引信息用来快速定位数据。

（2）存储模型

projection：

每一个表可以绑定多个 projection，这是什么概念呢？每个 projection 是这张表的某些列的组合，是实际存储在磁盘上的，每个 projection 可以按不同顺序存储，一张表的每个列必须出现在至少一个 projection 中。一个表绑定的 projection 也可能包括其他表中的列（相当于重新划分表了）。

比如一张用户表（姓名，年龄，工资），可以绑定两个 projection，P1（姓名，年龄） order by 年龄，P2（姓名，工资），order by工资。

这样，按年龄查找姓名和按工资查找姓名这两种查询就可以分别分配到 P1 和 P2 里，每个都很快。

由于把各个列分散开了，就需要重组一行数据。这里涉及三个概念

SID：Segment id，每个 projection 水平分成多个 segment 分区，SID 就是分区号。

SK：Storage keys，每个分区中，给每行数据分配的一个自增的主键，用来将不同的 projection 对齐，其实就是行号、下标。

下图就是一个示例：

join index：为了重建一行完整的数据，需要将这些按不同顺序的记录映射到同一个顺序上，也就是 join index 的作用。比如将 projection2 映射到 projection1 上，这是个一对一映射。

这个 join index 可以是一条路径，比如还有一个 projection3 到 projection2 的映射，有传递性。这样，就能根据 join index 重组数据了。

在对数据的遍历过程中，将传统的按点返回的 Iterator 接口改成了批量返回的 iterator ，每个批次 64KB，避免了方法的过多调用。

数据恢复

当节点挂掉但是数据没丢时，可以直接重启机器，把其他机器的执行队列中的操作拿过来执行。

当一个节点的 RS 和 WS 都丢了，就需要从其他节点的 projections 和 join indexes 重建这个节点的数据。

当仅仅 WS 丢了，可以快速从 RS 恢复出来，这个涉及快照隔离，不详细说了。

局限

projection 是如何生成的没有具体说明，没有讲如何做负载均衡。

join index 的维护比较麻烦，尤其是加入update，在恢复数据时候也需要 join index，没有做错误恢复的性能。

在完成这篇论时系统还没开发完，功能不全，还是个单机系统。

总结

C-Store 应该是第一个将各种列存技术在实际系统中实现出来的，并且对查询进行了优化，通过数据冗余和按需排序优化了查询性能。在 BigTable 的论文里轻怼了一下 C-Store，C-Store 更像一个关系型数据库，而 BigTable 的 API 比较底层，支持高吞吐率。C-Store 只对读做了优化，而 BigTable 即对读优化又对写优化。