C-Store: A Column-oriented DBMS

VLDB 2005 Mike Stonebraker, etc.

https://dl.acm.org/doi/10.5555/1083592.1083658

行存（row store）RDBMS 作为当时的主流，通常将同一行记录的所有属性存储在磁盘的连续空间，以获得卓越的写性能，这种方式也被称为 write-optimized，适用于 OLTP 场景。而数据仓库、CRM 等需要 ad-hoc 查询大量数据的系统应该具有 read-optimized 的特性，此类系统往往通过列存（colunm store）架构来获得更有效的性能（如 Sybase IQ, Addamark, KDB）。

列存架构中，查询操作只需按需读取所需要的列，避免将无关数据读取到内存。CPU 的性能增速要远高于磁盘的带宽增速，在 read-optimized 系统，用 CPU cycles 换取磁盘带宽是一件值得的事情，列存通过 1) code 2) densepack 两种方式达到以 CPU cycles 换取磁盘带宽的目的。

C-Store 是作者提出的一个新的列存数据库，具有如下革新特性：

  1. A hybrid architecture with a WS component optimized for frequent insert and update and an RS component optimized for query performance
  2. Redundant storage of elements of a table in several overlapping projections in different orders, so that a query can be solved using the most advantageous projection
  3. Heavily compressed columns using one of several coding schemes
  4. A column-oriented optimizer and executor, with different primitives than in a row-oriented system
  5. High availability and improved performance through K-safety using a sufficient number of overlapping projections
  6. The use of snapshot isolation to avoid 2PC and locking for queries

混合架构

人们对实时数仓数据可见性的延迟要求越来越高（toward 0），C-Store 的 Writeable Store 模块支撑频繁地插入和更新，Read-optimized Store 模块提供高性能查询，Tuple Mover 则负责将数据从 WS merge 到 RS，这是结构非常类似 LSM。

数据模型

C-Store 支持标准关系数据库的逻辑数据模型 —— 数据库由表构成，每个表含多个数据列，表的属性可以作为 primary key 或其它表的 foreign key。但 C-Store 的物理存储模型不同于这种逻辑模型，是以 projection 进行存储的。

  • 一个 projection 存储了一个逻辑表的一个或多个列属性，它还可以存储其它表的一个或多个属性以表示外键
  • 一个 projection 和它的锚表（anchor table）具有的行数相同
  • 一个 projection 具有一个 sort key，由该 projection 的一个或多个列构成。同一个 projection 中的 K 个属性各自存储于一个数据结构中，且都按照 sort key 进行排序
  • 每个 projection 都被水平切分（Horizontally partitioned）为一个或多个 segment，切分的依据为 sort key，这样每个 segment 都对应一段 key range
  • 由于每个 projection 的 sort key 不一致，因此需要 join indexes 来维持不同 projection 的对应关系

Storage key

  • 在 RS 上，storage key 是记录在 segement 上的序数，不存储且按需计算获得
  • 在 WS 上执行引擎给每一次插入赋予一个唯一的 storage key, 大于 RS 上 storage key 的最大值
  • WS 和 RS 按照相同的规则进行水平切分，因此 RS segement 和 WS segent 是 1:1 对应的，因此 (sid, storage_key) 只能存在 RS 或 WS 中的一个
  • 由于 WS 在尺寸上相对较小，因此使用 B-tree 直接存储 projection 的每一列，按 storage key 排序，另外（sort key， storage key）以 sort key 作为 key 保存为 B-tree。这样就根据 sort key 快速定位到 storage key，然后再根据 storage key 找到对应的列值
  • WS 构建在 BerkeleyDB 的 B-tree 结构上

Join Indices

If T1 and T2 are two projections that cover a table T, a join index from the M segments in T1 to the N segments in T2 is logically a collection of M tables, one per segment, S, of T1 consisting of rows of the form:

(s: SID in T2, k: Storage Key in Segment s)

Join Index 按照 T1 的切分方式进行切分，且跟 T1 的 segement 保存在一起。

Join Index 在更新的时候非常难以维护，因此会把每个 column 存储在多个 projection 上，但这对 DBA 设计表结构提出了更高的要求，文中提到他们正在写一个自动化表结构设计工具。

Coding Schema

projection 中的每一列都紧凑地存储在一个结构体中，基于该列是否是 sort key 以及该列不同数据的多少，文中给出了四种编码方式：

  1. Self-order, few distinct values
  2. Foreign-order, few distinct values
  3. Self-order, many distinct values
  4. Foreign-order, many distinct values

Column-oriented optimizer and executor

这块不懂，后面有机会再补充

High availability

由于不同的列存在与多个 projection，C-Store 基于此可以实现 K-safe 的系统。

Snapshot Isolation

Snapshot isolation works by allowing read-only transactions to access the database as of some time in the recent past, before which we can guarantee that there are no uncommitted transactions.

对于只读事务，可以根据时间戳来判断记录的可见性，因此可以不用加锁

对于 Read-write 事务，C-Store 遵循严格的 two-phase locking，并使用了 NO-Force, STEAL 策略。

事务相关的内容感觉跟 Mysql 有些相像，但有些内容还没搞明白，这块后面有机会再研究一下。