C-Store：列式数据库

一句话

C-Store 把关系数据库的物理存储从「按行」翻成「按列」，并围绕这一点重做了整套设计：重度压缩且尽量在压缩态上直接计算、把同一份数据按不同排序键存成若干重叠的「投影」（用排好序的冗余副本兼任索引与容错副本）、以及用「写优化小库 + 读优化大库 + 后台搬运工」的混合结构把列存最怕的写入吸收掉。它是分析型（OLAP）数据库换代的起点，后来商业化为 Vertica。

Glossary · 术语表

坐标

作者是 Michael Stonebraker（MIT）、Daniel Abadi、Samuel Madden、Mitch Cherniack（Brandeis）、Elizabeth 与 Patrick O'Neil（UMass Boston）、Stan Zdonik（Brown）等十来人，发表于 VLDB 2005。按列存储本身不是它发明的——1985 年的分解存储模型（DSM）、商用的 Sybase IQ、学术界的 MonetDB 都早有先例；C-Store 的贡献是把列存放进一套完整的、可用的数据库设计里：压缩、排序冗余、混合读写、副本容错、快照读，环环相扣。它下启 Vertica，并与同期的 Dremel（列存 + 多级执行树，见本站那篇）一起成为今日数据仓库的两条源流。

问题与动机

2005 年前后的主流关系数据库（Oracle、DB2、SQL Server 等）血统都来自 1970–80 年代的 OLTP 世界，物理存储是写优化的：一整行连续摆放，插一条记录只要写一处。可市场的重心已经挪向数据仓库——批量灌入、几乎不改、被反复扫描汇总。

在这种负载上，行存有个结构性的浪费：磁盘按块读取，而一个块里塞的是整行。一条「按年汇总销售额」的查询只碰两三个字段，硬盘却被迫把每行的几十个字段全搬进内存；表越宽，浪费越大。当时的补救是狂建索引和物化视图，但那既要额外空间、又拖慢写入，还只照顾得到预先想到的查询。

作者的判断很直接：问题不在于优化得不够，而在于物理布局站错了边。既然读远多于写，就该从零设计一个读优化的存储——哪怕写入变难，也用别的机制补回来。

核心思想 / 方法

一、按列存：只搬要用的那几列

C-Store 把每一列单独连续存放。查询要哪几列就只读哪几列，不相干的字段一个字节都不碰。宽表上的分析查询，I/O 量常常因此降一个数量级。

代价是重建行（tuple reconstruction）：查询往往要把几列拼回同一条记录。C-Store 的办法是靠位置对齐——同一批列里的第 i 个值天然属于第 i 行，于是拼接只是按序号取值，不需要在每个值上存行号。这个「位置即身份」的约定后来成了所有列式引擎的基本功。

二、压缩，而且尽量压着算

一列里全是同类型、同语义、常常还有序的值，重复度远高于一整行，因此压缩率天生比行存高得多。C-Store 按两个维度挑编码：这一列是不是它所在那份数据的排序键（有序 / 无序）× 不同取值多不多：

• 有序 + 取值少：游程编码（RLE），把一段相同值记成三元组 (值, 起始位置, 连续个数)——几千行压成一行。
• 无序 + 取值少：位图编码，每个取值配一串「哪些行是它」的比特位图，位图本身再做游程压缩。
• 有序 + 取值多：按块存与前一个值的差值（delta），递增的日期、编号能压得很扁。
• 无序 + 取值多：没什么结构可利用，基本不编码。

真正关键的一步是：算子尽量直接吃压缩后的表示，不先解压。统计「某门店的交易笔数」碰上 RLE，只要读出那句「连续 5000 行」，答案就是 5000——省掉的不只是磁盘 I/O，还有解压和逐行处理的 CPU。压缩在这里不再是「省空间、费 CPU」的取舍，而是两头都省。

三、投影：同一份数据按几种顺序各存一套

C-Store 存的不是「表」，而是投影（projection）：从某张表出发、挑出一组列（可以顺着外键把别的表的列也拉进来），整体按某个排序键（sort key）排好序。同一列允许出现在多个投影里、各按不同的键排序。只要所有列都至少被某个投影覆盖，任意查询就都能回答。

为什么这么设计？因为一旦按列存 + 重压缩，「多存一份排好序的副本」变得很便宜，而一份排好序的副本同时干三件事：① 当索引用——按该键做范围查询可以直接跳段；② 当压缩加速器用——排序键那一列有序，RLE 压到极致；③ 当容错副本用（见下文 K-safety）。传统数据库里「基表 + 索引 + 物化视图」三样东西，在这里被统一成同一种物件。

每个投影再按排序键的取值范围水平切成段（segment）分布到不同机器；段内每行有一个存储键（storage key），其实就是它在段里的序号，读优化那份根本不落盘、按位置算出来即可。不同投影排序不同，行序自然对不上，于是需要 join index：它为「发送方」投影的每一行记下对应行在「接收方」投影里的 (段号, 存储键)，把两种顺序缝回同一条逻辑记录。

四、WS / RS 混合：把「写」从「读」身上剥离

列式 + 排序 + 重压缩，等于把数据焊成了一整块——想在中间插一行，几乎要重写一段。C-Store 干脆把写和读拆成两个库：

• RS（读优化存储）：大的那份，列式、压缩、按排序键排好，存储键隐式；只适合成批重写。
• WS（写优化存储）：小的那份，逻辑结构与 RS 完全一样（同样的投影、同样的排序键），但不压缩、用 B 树按排序键组织、存储键显式，因而扛得住零散插入。

插入只进 WS；删除是在对应行上打一个标记（记进删除向量），更新 = 删除 + 插入。后台的搬运工（tuple mover）周期性做一次批量归并：把 WS 里够「老」的成块数据合进 RS，顺带重写压缩块、更新 join index。查询则同时读 WS 和 RS 再合并结果，所以刚写的数据不会读丢。「小而快的写区 + 大而齐的读区 + 后台批量合并」这一模式，后来在 LSM 树、ClickHouse 的分区合并、Vertica 的 ROS/WOS 里反复出现。

五、只读查询不加锁：epoch 与快照隔离

数据仓库的查询又长又重，和写入抢锁会互相拖死。C-Store 让只读事务跑在稍早的一个时间点上：系统用粗粒度的 epoch（几秒一格）作时间戳单位，由一个时间戳权威推进「高水位」；只读查询挑一个不晚于高水位的 epoch，靠每行的插入与删除时间判断它在那一刻是否可见——于是读事务全程不加锁、也不阻塞写，代价是看到的数据可能旧几秒。读写事务则走常规的两阶段锁。

六、不靠日志靠副本：K-safety

RS 又大、又是整块重写，给它记预写日志代价高得离谱。C-Store 的取舍是：只给小小的 WS 记日志，整体容错交给副本——保证任意 K 台机器同时故障时剩下的投影仍覆盖所有列（称作 K-safety）。某台机器崩溃重启后，它缺的那段数据不靠重放日志补，而是向其它副本「查」回来，把结果灌回自己的 WS。妙处在于这些副本本来就为查询性能而存在，容错几乎是白捡的。

关键结果

论文给出的是一组初步实验：TPC-H 派生的仓库式模式上、7 条查询，对手是一个流行的商用行存和一个流行的商用列存（均匿名）。在限定各系统可用磁盘空间的那组配置下，同样的数据 C-Store 占 1.987 GB，商用行存占 4.480 GB（约四成），而查询上 C-Store 平均比商用行存快约 164 倍、比商用列存快约 21 倍。作者把收益归因于三处叠加：只读需要的列、投影代替全表扫描、以及更好的压缩。

作者本人对这些数字相当克制：原型只实现了设计的一部分——WS 与搬运工尚未完整跑通，所以测的基本是读优化那一半；他们明说要等这些补齐才谈得上详尽评估。把它当成「方向性证据」而非「产品对比」更恰当。

为什么重要 / 影响

这篇之后，列式存储从小众选项变成分析型数据库的默认前提。C-Store 商业化为 Vertica（2011 年被惠普收购），而它那套组合拳——列式布局、按列选编码的重压缩、压缩态上直接计算、排序冗余副本兼任索引、读写分离加后台合并——几乎被后来每一个分析引擎继承：Redshift、ClickHouse、Snowflake、BigQuery，以及 Parquet / ORC 这类列式文件格式。今天「湖仓」里那些扫几十亿行只用几秒的查询，吃的正是这份红利。

它还坐实了 Stonebraker 的那句主张：「一种尺码穿不下所有人」——OLTP 与 OLAP 该用结构不同的引擎，而不是同一个引擎调参数（同一批人随后做的 H-Store／VoltDB 就是这条主张的另一半）。学术上，它把「压缩与执行如何协同」「什么时候把列拼回行（延迟物化）」推成了一整条研究线。

局限与批评

• 实验是原型对商用产品，不对等：调优、成熟度、功能完整度都不在一个量级，作者自称初步结果。威斯康星的 DeWitt 与 Halverson 后来在同一套框架里重做比较，指出差距远没那么悬殊，且相当一部分收益来自物理设计（窄表 / 垂直分区）而非「列存」这个概念本身。
• 收益来源当时没拆干净：Abadi 等 2008 年那篇「列存与行存到底差在哪」进一步说明，在行存里用垂直分区「模拟」列存往往更慢，真正的收益来自压缩、延迟物化、块式迭代等执行层技巧——这些在 2005 年的版本里还只是雏形。
• 写入路径最弱、落地最少：WS 与搬运工正是论文里实现最不完整的部分，而它恰恰是列存能否进生产的关键。
• 工程上并非照单全收：Vertica 团队七年后的复盘坦承，join index 复杂又昂贵，实际产品里基本没用上，改以「预连接投影」等手段替代。
• 物理设计成了新负担：建哪些投影、按什么排序、冗余几份直接决定性能；论文把这件难事推给一个自动设计工具，选型错了就退化成「又占空间又不快」。
• 不适合 OLTP：改一行要触及多个投影与多处编码，只读查询看到的又是几秒前的快照——这是设计的自觉取舍，不是疏漏。

要点