C store底层存储设计
1 like1,140 views
C-Store底层存储设计原理描述，主要参考Mike Stonebraker的论文：C-Store: A Column-oriented DBMS。
More Related Content
What's hot (6)
Viewers also liked (11)
Similar to C store底层存储设计 (20)
C store底层存储设计
- 2. C-Store设计思想 ? 在只读的数据仓库应用中，支持更新事务也是 很有必要的！ ? 在实时的数据仓库应用中，将新灌入数据的可 见性延迟压得越低越好！ ? 但基于读优化的数据结构，很难再提供高效的 更新性能！ ? C-Store将两个针对读和写分别优化的存储模块 集成到一起来解决读写两难的困境！
- 4. C-Store数据模型(cont.) EMP3(name, salary | salary) EMP2(dept, age, DEPT.floor | DEPT.floor) Name Age Dept Age DEPT.floor Jill 24 Math 25 8 Bob 25 Biology 24 10 Bill 27 EECS 27 19 Salary Bob EMP1(name, age | age) Name 10K Bill 50K Jill 80K DEPT1(name, floor | floor) Floor Math 8 Biology 10 EECS EMP Name 19 DEPT Name Age Dept Salary Name Floor Bob 25 Math 10K Biology 10 Bill 27 EECS 50K Math 8 Jill 24 Biology 80K EECS 19
- 5. C-Store数据模型(cont.) ? 投影以列存的方式存储，即投影中有几个属性 列，就有几个存储列的数据结构。 ? 投影通过基于排序属性值的水平分区切割成段 （Segment），每个段都会有一个标识。 ? 段中的每个属性列的值都会关联一个存储主键。 EMP1(name, age | age) SK Name SK Age 1 Jill 1 24 Name Age 2 Bob 2 25 Jill 24 1 Bill 1 27 Bob 25 Bill 27 SID = 1 SID = 2 段中具有相同存储主键的属性列构成一条逻 辑上的记录！
- 6. C-Store存储设计 ? 读写分离，最新的更新数据全部写到Writeable Store (WS)，只读数据存储在Read-Optimized Store (RS)。 ? 查询时需要将RS和WS中的数据合并处理。 1) WS和RS均采用列存储，分享相同 的物理设计，包括投影、段等； 2) WS中的段与RS中的段一一对应； 3) WS中SK是显示存储的，RS中SK根 据列属性值的存储位置计算得到； 4) WS中的数据通过Tuple Mover实现 与RS中数据的Merge； Writeable Store Tuple Mover Read-Optimized Store
- 8. RS中数据存储和压缩(cont.) ? 压缩列就是投影中的排序列，且压缩列中的 distinct值很少。 Salary 使用Run-Length Encoding将连续的列属性值转 化为三元组（列属性值，在列中第一次出现 的位置，出现次数） 3000 3000 3000 (3000, 0, 3) 8000 8000 8000 8000 (8000, 3, 4) 整个列就可以使用多个三元组来表示 所有三元组使用B树索引来管理，B树 索引中所有节点不留空闲空间，使用 大数据块来存节点以降低B树的层数
- 9. RS中数据存储和压缩(cont.) ? 压缩列不是投影中的排序列，且压缩列中的 distinct值很少。 Salary 8000 3000 3000 8000 8000 3000 8000 列属性值转化为二元组（列属性值，该列属性 值出现在列中位置的Bitmap） (8000, 1001101) (3000, 0110010) 因为distinct值很少，所以每个二元 组中的Bitmap都很稀疏，可以继续 使用Run-Length Encoding对Bitmap 进行压缩 构造B树将列中的每个位置映射给该位置上的列属 性值，以快速定位列中每个位置上的列属性值
- 12. WS中数据存储 ? WS中的数据比RS中的数据少很多，所以不进 行数据压缩。 ? 投影中每列的更新数据都使用二元组（列属性 值，SK）来表示，且针对SK建B树索引。 ? 投影中的排序属性列使用附加的二元组（排序 属性值，该排序属性值第一次出现的SK）来表 示，且针对排序属性值建B树索引。 ? 先查询排序属性列二元组的B树索引，再查询 其他列二元组的B树索引。
- 13. WS中数据存储(cont.) EMP1(name, age | age)的更 新数据 Name列更新数据 的二元组 SK Name Age Jill 1 1 Jill 24 Tom 2 2 Tom 24 Rose 3 3 Rose 25 Bob 4 4 Bob 25 Bill 5 5 Bill 27 排序属性列的附 加二元组 (针对排序 属性建B树 索引) 24 3 27 5 当使用排序属性进行查询时，先查询 排序属性列二元组的B树索引，获取符 合条件的SK，再查询其他列二元组的B 树索引获取对应的属性列值 1 25 (针对SK建 B树索引) C-Store直接使用BerkeleyDB来管理WS！