AP存储-C-Store
date
slug
tags
summary
type
status
C-Store是一个经典的列存数据库，它对我产生了以下启示：
- 经典列存格式以及编码优化。
- Projection的概念。
- 通过读写分离的思维方式，同时支持事务更新和提供MVCC，以降低对读性能的影响。
Projection
在C-Store中，会以projection的方式存储一个表。一个projection包含若干列（可以是当前表的列，也可以是其他表的列），以及其中某个列的顺序进行排序存储。C-Store要求每个列至少存在一个projection中，以此保证可以通过projection复现一个完整的表。
Projection的组织方式是内部分成多个segment，每个segment由一对read store和write store组成。segment内部以列存格式存储若干列。
对于read store中的列存，C-Store针对数据的不同性质进行相应的编码：
- 排序良好，基数小：通过范围编码（x，start，end）。
- 排序良好，基数大：通过delta的方式编码，例如1,2,3 → 1,1,1。因为delta值通常较小，可以进一步使用densepack将多个int的bit位打包在一起。
- 乱序，基数小：bitmap优化。
在查询时，有时需要组合多个projection，C-Store针对该场景提出了join index的优化。在每个segment中，每行都有一个唯一标识 storage key，通过该标识符，C-Store可以创建某个projection到另外一个projection的映射。如下图是一个EMP3到EMP1的优化。通过该JoinIndex，可以实现来个Segment的快速合并。（这也是为什么要保证write store的storage key必定比read store的原因，因为一个segment包含一对write store和read store，两者中的每个行的storage key都必须唯一）
读写分离
C-Store的另一个亮点是它提出了读写分离的设计。基于这种设计，它实现了MVCC，支持读写并发，平衡了读写性能。（写性能不至于过差）
具体而言，C-Store对于projection中的每个segment都维护了一个read store和write store。read store的优化在上述内容中已经提到，而write store则为了优化写性能而不使用编码。所有的写操作都会先写到write store上，对于读取数据时，需要合并read store和write store的结果。为了保持write store尽可能小，C-Store会由tuple mover定期将数据从write store复制到read store。
同时，C-Store实现了MVCC：对于每次写入，C-Store都会在写入项计入一个时间戳（这个时间戳通过一个中心节点进行全局统一）。之后在读的时候则可以根据时间戳实现MVCC。
Ref
Loading...