https://web.stanford.edu/class/cs345d-01/rl/cstore.pdf https://zhuanlan.zhihu.com/p/386369591 https://fuzhe1989.github.io/2020/08/13/c-store-a-column-oriented-dbms/
论文介绍一种针对读优化的关系型数据库，它有以下特点：
大多数 OLTP 数据库采用行存储，这有着良好的写入性能。而对于读多写少的系统，比如数据仓库，使用列存储的性能会更好，这可以避免在查询时读入无关的字段。
传统的关系型数据库会将字段按照原本的格式存储并进行对齐，这对 cpu 读取友好。然而随着技术发展， cpu 性能提升比磁盘带宽快得多。因此我们可以对原本的设计进行权衡，对磁盘带宽友好的设计可能更加有利可图。
这里提出了两种方式：
因此尽量能够让 query executor 支持处理这种压缩过的数据。
关系型数据库会存储索引结构。以主索引为例，它会尽量让表中的行按照某一个字段的顺序进行存储。这种索引结构对于写操作友好，对读操作不友好。因此我们可以考虑其他对读友好的存储结构，如 bitmap indexes、cross table indexes、materialized views。
C-Store 使用列存储的方式，其中每个列都会按照某种方式排序，具有同种排序方式的列集合，我们称之为 projection。同个列可能按照不同种排序方式而存在于不同列集合中，为了防止重复列造成的空间开销，我们需要进行一些优化（The existence of multiple sort-orders opens opportunities for optimization）
分布式架构对于计算密集型和数据密集型的应用十分友好。架构中有多个节点，每个节点都有各自的磁盘和内存。在这种架构中，我们最好对数据进行水平分区，这也有利于并行查询。以往我们使用日志来实现数据的容错，但是对于数据量比较大的情况，通过日志来恢复数据的开销很大。随着磁盘的价格下降，采用维护多个数据副本的方式也变得越来越有吸引力。
维护的多个数据副本不一定要完全一致，C-Store 就采用不同的排序方式来存储冗余对象，这除了高可用性，还带来了更高的查询效率。 C-Store 还支持 Ｋ 台机器故障仍然保持可用（即 K-safe）。
即使是读多写少的情景，我们也需要提供事务和更新的功能。
一般而言，读友好与写友好难两全。然而 C-Store 提出了解决这个困境的方式，C-Store 组合了一个写友好的小组件（WS）和一个读友好的大组件（RS）。WS 组件只能通过 Tuple Mover 将数据批量写入RS 组件。
┌─────────────────────┐
│ Writeable Store(WS) │
└─────────┬───────────┘
│ Tuple Mover
┌─────────▼───────────┐
│ Readable Store(RS) │
└─────────────────────┘
在这个系统中，查询操作必须访问两个组件的数据；插入操作只发送给 WS 组件；删除操作会在 RS 组件中做标记，之后由 Tuple Mover 进行删除；更新操作实现为插入和删除。
为了让数据更快地从 WS 组件写入 RS 组件，C-Store 还使用了一种 LSM 树的变体方式加以优化。
为了支持事务，C-Store 不是盲目地加锁。进行读操作时，系统会选择一个小于最近提交的时间戳 T 来建立快照并返回结果。这要求 C-Store 需要为每次写操作都带上时间戳，而且读操作需要忽略时间戳大于 T 的数据。
由于 RS 和 WS 都是采用列存储的方式，因此也要设计对应的优化器与执行器。
C-Store 创新点如下：
C-Store 支持标准的关系模型，主键外键等等，与基于行的数据库在使用上一致。行存储的数据库直接按照逻辑模型来实现物理模型，而列存储不然，只实现 projections。具体来说，projections 包含一个表的一个或多个字段的数据，如果字段与其他表存在对应关系，如外键，则也可以包含其他表的字段。
举个例子，现在有两个表 EMP(name, age, salary, dept) 和 DEPT(dname, floor)，
┌─────┬─────┬─────────┬──────┐
│Name │ Age │ Dept │Salary│
├─────┼─────┼─────────┼──────┤
│Bob │ 25 │ Math │10K │
│Bill │ 27 │ EECS │50K │
│Jill │ 24 │ Biology │80K │
└─────┴─────┴─────────┴──────┘
Table 1: Sample EMP data
一种可能的 projection 方式如下：
Example 1: Possible projections for EMP and DEPT
EMP1 (name, age)
EMP2 (dept, age, DEPT.floor)
EMP3 (name, salary)
DEPT1(dname, floor)
在每个 projection 中，如果有 k 列，那么会有 k 个存储单列的数据结构。它们按照其中的一列或多列的 sort key 来排序。我们用竖线将列与 sort key 分隔开，如下：
Example 2: Projections in Example 1 with sort orders
EMP1(name, age| age)
EMP2(dept, age, DEPT.floor| DEPT.floor)
EMP3(name, salary| salary)
DEPT1(dname, floor| floor)
最后，每个投影被水平地划分为 1 个或多个段，这些段有一个段标识符 Sid，其中 Sid > 0。C-Store 只支持对投影的排序键进行基于值的分区。因此，给定投影的每个片段都与该投影的排序键的一个键范围相关联。此外，所有键范围的集合将对键空间进行分区。
每个 projections 会被水平分片为多个段，用段标识符 Sid 进行区分。C-Store 只支持基于 sort key 来进行分片。
数据库中每个表的每一列都至少要存储在一个 projection 中，才能响应所有的 SQL 请求。同时，C-Store 还必须能够从 projections 中重建完整的表。 C-Store 依靠 storage keys 和 join indices 来支持这些操作：
每个段中每一列的数据都会有一个序号 storage key（SK），同个段的数据中，如果 storage key 相等，则说明它们在逻辑中是同一行的。
storage key 在 RS 中从 1 开始递增的，RS 不会直接存储 key 值，而是根据数据在列的位置来计算。在 WS 中则会存储 storage key，其值比 RS 的 storage key 都大。
假设 T1、T2 是同个逻辑表的两个 projections，那么从 T1 映射到 T2 的 join index 中，会按 T1 中的数据顺序，记录每条数据在 T2 的位置，格式为(s: SID in T2, k: Storage Key in Segment s)
由于 T1、T2 是同个逻辑表的两个 projections，所以 join index 表示的映射关系是一对一的。映射具有有传递性，多个 join index 构成了数据的映射路径。
为了能够从示例 2 的 projections 中重建出 EMP 表，我们至少需要两个 join index。加入我们使用 age 作为顺序，那么我们需要 将 EMP2 和 EMP3 映射到 EMP1 的 join index。图 2 展示 EMP3 到 EMP1 的映射关系。
EMP1
┌─────┬─────┐
│Name │ Age │
├─────┼─────┤
│Jill │ 24 │ ◄────────────────┐
│Bob │ 25 │
│Bill │ 27 │ Join Index
└─────┴─────┘ ┌────┬────┐
│Sid │Key │
├────┼────┤
│1 │2 │
EMP3 │1 │3 │
┌─────┬──────┐ │1 │1 │
│Name │Salary│ └────┴────┘
├─────┼──────┤ ▲
│Bob │10K │──────────────────┘
│Bill │50K │
│Jill │80K │
└─────┴──────┘
Figure 2: A join index from EMP3 to EMP1.
我们将每个列都存储在多个 projections 中，以减少 join index 的数量。这是因为 join index 的存储和维护成本非常高，对 projections 的修改都需要更新指向它或指向它的每个 join index。
数据库中 projection 的每个段以及对应的 join index 都要存储在多个节点中，用以实现 K-safe。
RS 是对读做优化的列存储。projection 的每一列都按其 sort key 的顺序存储。在RS 中 storage key 是数据在段里的序号，根据需要计算出来。
RS 中的列有四种压缩的编码方案
Type 1 有序且大部分值相同 这种列用 (v, f, n) 来表示，v 是存储在列中的值，f 是列中 v 第一次出现的位置，n 是 v 在列中出现的次数。为了支持查询, c-store 对这个结构支持了 B 树索引，加快了对这个内容的查找。
Since there are no online updates to RS, we can densepack the index leaving no empty space. Further, with large disk blocks (e.g., 64-128K), the height of this index can be kept small (e.g., 2 or less).
Type 2 无序且大部分值相同（顺序由同个 projection 的其他列的值确定） 这种列用 (v, b) 来表示，v 是存储在列中的值，b 是 v 在列中的位图。
Since each bitmap is sparse, it is run length encoded to save space.
为了快速找到列中的第 i 个值，这里用 B 树加以优化，将列中的位置映射到列中的值。这个 B 树称为 offset indexes。
Type 3 有序且大部分值不同 将列中的每个值表示为与前一个值的差。比如 1,4,7,7,8,12 会被表示层 1,3,3,0,1,4。。
Type 4 无序且大部分值不同 不编码
join index 由 (sid, storage_key) 构成，这两个字段可以作为普通的列来存储
为了避免把优化器搞得太复杂，这里 WS 也用了 projection 和列存的模式，和 RS 有相同的 projections 和 join indexes。
每条记录的 storage key 会存储在 WS 中，每次插入数据都会给出唯一的 storage key。The execution engine must ensure that this SK is recorded in each projection larger than the number of records in the largest segment in the database.
为了简单和可扩展性，WS 采用与 RS 相同的方式进行水平分片。因此，RS 段和 WS 段之间存在一对一的映射关系。(sid, storage key) 能标识这两者中的一条记录。
因为 WS 比 RS 小得多，所以不必压缩 WS 的数据。 WS 中的每一列都表示为（v, sk）, v 是数据的值，sk 是其对应的 storage key，并为每列的 sk 建了 b 树索引。
此外，每个 projections 的 sort key 会被表示为（s, sk）, s 是 sort key 的值，sk 是 s 第一个（？）的 storage key。同样，也为（s, sk）集合的 s 建了 b 树索引。因此当我们要使用 sort key 来查找数据时，通过这个 b 树找到目标的 storage key，再由前面的 b 树找到 projection 中目标的其他字段。
projections 会被分片成很多段，有的在 WS，有的在 RS。因此 join index 的 (sid, storage_key) 指向的记录可能在 WS 也可能在 RS。
c-store 会使用 storage allocator 来将每列每段分配到网格系统中的各个节点。storage allocator 会将同个 projection 同个段的所有列都分到同个节点。join indexes 也会和 sender 段位于同个节点。有着相同键范围的 WS、RS 段也会在同个节点。 Our analysis shows that a raw device offers little benefit relative to today’s file systems. Hence, big columns (megabytes) are stored in individual files in the underlying operating system.
An insert is represented as a collection of new objects in WS, one per column per projection, plus the sort key data structure. All inserts corresponding to a single logical record have the same storage key. The storage key is allocated at the site where the update is received. To prevent C-Store nodes from needing to synchronize with each other to assign storage keys, each node maintains a locally unique counter to which it appends its local site id to generate a globally unique storage key. Keys in the WS will be consistent with RS storage keys because we set the initial value of this counter to be one larger than the largest key in RS.
We are building WS on top of BerkeleyDB, we use the B-tree structures in that package to support our data structures. Hence, every insert to a projection results in a collection of physical inserts on different disk pages, one per column per projection. To avoid poor performance, we plan to utilize a very large main memory buffer pool, made affordable by the plummeting cost per byte of primary storage. As such, we expect “hot” WS data structures to be largely main memory resident.
由于 c-store 面向读多写少的场景，因此如果采用普通的锁来处理竞争问题，会由于大量的锁争用而浪费性能。c-store 使用快照隔离来处理只读事务。
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. For this reason, when using snapshot isolation, we do not need to set any locks. We call the most recent time in the past at which snapshot isolation can run the high water mark (HWM) and introduce a low-overhead mechanism for keeping track of its value in our multi-site environment. If we let read-only transactions set their effective time arbitrarily, then we would have to support general time travel, an onerously expensive task. Hence, there is also a low water mark (LWM) which is the earliest effective time at which a read-only transaction can run. Update transactions continue to set read and write locks and obey strict two-phase locking, as described in Section 6.2.
The key problem in snapshot isolation is determining which of the records in WS and RS should be visible to a read-only transaction running at effective time ET. To provide snapshot isolation, we cannot perform updates in place. Instead, an update is turned into an insert and a delete. Hence, a record is visible if it was inserted before ET and deleted after ET. To make this determination without requiring a large space budget, we use coarse granularity “epochs,” to be described in Section 6.1.1, as the unit for timestamps. Hence, we maintain an insertion vector (IV) for each projection segment in WS, which contains for each record the epoch in which the record was inserted. We program the tuple mover (described in Section 7) to ensure that no records in RS were inserted after the LWM. Hence, RS need not maintain an insertion vector. In addition, we maintain a deleted record vector (DRV) for each projection, which has one entry per projection record, containing a 0 if the tuple has not been deleted; otherwise, the entry contains the epoch in which the tuple was deleted. Since the DRV is very sparse (mostly zeros), it can be compactly coded using the type 2 algorithm described earlier. We store the DRV in the WS, since it must be updatable. The runtime system can now consult IV and DRV to make the visibility calculation for each query on a record-by-record basis.