C-Store

港控/mmm° 2022-12-25 10:58 100阅读 0赞

原文：https://blog.csdn.net/landhero/article/details/77939020  
参考：https://blog.csdn.net/qiaojialin/article/details/89507354

C-Store是一个为了快速查询而设计的关系型数据库，它的论文发表于2005年的VLDB。 为了达到更快的查询性能，C-Store按列存储数据，同一个表中的不同列可能被存在不同的、可能有重叠的Projection中。 虽然C-Store没有提出什么新的技术，但它是第一次将与列存储相关的技术整合到一起，成为一个真正理论上可用的系统，所以其设计和系统架构仍被广泛借鉴。 HPE Vertica这款商业存储系统，就是基于C-Store设计并实现的。

本文主要基于其VLDB2005的论文，介绍C-Store中的相关概念与设计。

# C-Store数据模型 #

由于C-Store是关系型数据库，所以在C-Store中，表的Schema也和普通关系型数据库一致。 例如，有如下两张表：一张是员工表，EMP，其中有姓名、年龄、部门和工资这几列；另一张表是部门表，DEPT，有名称和楼层这两列。

<table>  员工表EMP  
 <thead> 
  <tr> 
   <th colspan="1"> Name</th> 
   <th colspan="1"> Age</th> 
   <th colspan="1"> Dept</th> 
   <th colspan="1"> Salary</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>Bob</td> 
   <td>25</td> 
   <td>Math</td> 
   <td>10K</td> 
  </tr> 
  <tr> 
   <td>Bill</td> 
   <td>27</td> 
   <td>EECS</td> 
   <td>50K</td> 
  </tr> 
  <tr> 
   <td>Jill</td> 
   <td>24</td> 
   <td>Biology</td> 
   <td>80K</td> 
  </tr> 
  <tr> 
   <td>Alice</td> 
   <td>23</td> 
   <td>Art</td> 
   <td>20K</td> 
  </tr> 
  <tr> 
   <td>Jason</td> 
   <td>28</td> 
   <td>Physics</td> 
   <td>30K</td> 
  </tr> 
  <tr> 
   <td>John</td> 
   <td>27</td> 
   <td>Chemistry</td> 
   <td>40K</td> 
  </tr> 
 </tbody> 
</table>

<table>  部门表DEPT  
 <thead> 
  <tr> 
   <th colspan="1"> Name</th> 
   <th colspan="1"> Floor</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>EECS</td> 
   <td>2</td> 
  </tr> 
  <tr> 
   <td>Math</td> 
   <td>5</td> 
  </tr> 
  <tr> 
   <td>Physics</td> 
   <td>7</td> 
  </tr> 
  <tr> 
   <td>Chemistry</td> 
   <td>10</td> 
  </tr> 
  <tr> 
   <td>Biology</td> 
   <td>16</td> 
  </tr> 
  <tr> 
   <td>Art</td> 
   <td>24</td> 
  </tr> 
 </tbody> 
</table>

这两张表是C-Store中的逻辑表，虽然在表中我们标注了每一行，但是在C-Store中，逻辑表是不存放数据的，只是用来提供查询的Schema的，C-Store中的数据是存放在关联到逻辑表的几个Projection中。 C-Store的Projection有如下特点：1. 存储了逻辑表中的一列或多列；2. 按照其中的一列或者多列的组合进行排序；3.可能会存放其他逻辑表中的列。例如，EMP表可能有如下三个Projection。

<table>  Projection1  
 <thead> 
  <tr> 
   <th colspan="1"> Name</th> 
   <th colspan="1"> Age</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>Alice</td> 
   <td>23</td> 
  </tr> 
  <tr> 
   <td>Jill</td> 
   <td>24</td> 
  </tr> 
  <tr> 
   <td>Bob</td> 
   <td>25</td> 
  </tr> 
  <tr> 
   <td>Bill</td> 
   <td>27</td> 
  </tr> 
  <tr> 
   <td>John</td> 
   <td>27</td> 
  </tr> 
  <tr> 
   <td>Jason</td> 
   <td>28</td> 
  </tr> 
 </tbody> 
</table>

<table>  Projection2  
 <thead> 
  <tr> 
   <th colspan="1"> Dept</th> 
   <th colspan="1"> Age</th> 
   <th colspan="1"> DEPT.Floor</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>EECS</td> 
   <td>27</td> 
   <td>2</td> 
  </tr> 
  <tr> 
   <td>Math</td> 
   <td>25</td> 
   <td>5</td> 
  </tr> 
  <tr> 
   <td>Physics</td> 
   <td>28</td> 
   <td>7</td> 
  </tr> 
  <tr> 
   <td>Chemistry</td> 
   <td>27</td> 
   <td>10</td> 
  </tr> 
  <tr> 
   <td>Biology</td> 
   <td>24</td> 
   <td>16</td> 
  </tr> 
  <tr> 
   <td>Art</td> 
   <td>23</td> 
   <td>24</td> 
  </tr> 
 </tbody> 
</table>

<table>  Projection3  
 <thead> 
  <tr> 
   <th colspan="1"> Name</th> 
   <th colspan="1"> Salary</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>Bob</td> 
   <td>10K</td> 
  </tr> 
  <tr> 
   <td>Alice</td> 
   <td>20K</td> 
  </tr> 
  <tr> 
   <td>Jason</td> 
   <td>30K</td> 
  </tr> 
  <tr> 
   <td>John</td> 
   <td>40K</td> 
  </tr> 
  <tr> 
   <td>Bill</td> 
   <td>50K</td> 
  </tr> 
  <tr> 
   <td>Jill</td> 
   <td>80K</td> 
  </tr> 
 </tbody> 
</table>

上面的Projection1有姓名和年龄两列，按照年龄排序。Projection2中有部门、年龄以及部门对应的楼层，按照楼层进行排序。Projection3中有姓名和工资两列，按照工资进行排序。 Projection按照一列或者多列进行排序，能够更高效的压缩和更快速的查询。 查询时，C-Store会先选择一组相对合适的Projection，然后进行计算。 为了支持同一个表能够放在不同的节点上，C-Store中的一个Projection按照排序列的取值范围，划分为不同的Segment，Segment支持备份。

有时候，查询可能需要同一个逻辑表中的多个Projection才能完成，例如如果上述例子中，想要同时查询姓名和部门，这就需要Projection1和Projection2。 所以C-Store支持将多个Projection的列构造成一条记录，这个操作一般叫Tuple Construction。 C-Store实现Tuple Construction的逻辑比较简单，就是记录了一下每一个值的行号，然后在两个Projection之间记录一个叫Join Index的表，告诉这两个Projection要怎么去做Join。

# C-Store架构 #

## 基本架构 ##

Writeable Store (WS)Read-Optimized Store (RS)Tuple Mover

C-Store的基本架构如上图所示，有两种类型的节点，一种是为了读优化的并且是只读的(RS)，另一种是可以写的(WS)。 插入、更新、删除等操作都发动到WS，而查询会发到RS和WS，并合并二者的结果。 数据周期性的通过一个叫Tuple Mover的组建从WS移动到RS。

**RS**是为了读而进行优化的，主要是对不同的列采用了不同的编码方式。 针对某一列，C-Store根据它是否是Projection的排序列，以及该列的取值个数，来决定采取何种编码方式。 具体说来，有如下几种：

*  是排序列，并且取值的个数比较少，例如1,1,2,2,2,2,2,2,2,2,3,3,3,3,3。 C-Store会将这中列表示成一个三元组(v,f,n)的集合，v表示值，f表示该值的起始位置，n是该值一共的个数。 这里的例子可以表示为：(1,1,2), (2,3,8),(3,11,5)。
 *  不是排序的列，取值的个数比较少，例如0,0,1,1,2,1,0,2。对于这种列，采用Bitmap编码方式：(0, 11000010), (1, 00110100), (2,00001001)。
 *  是排序列，取值个数比较多，例如1,4,7,7,8,12。这种情况下按照块进行编码，每块内记录第一个值，其他的值都记和前面的差值，(1,3,3,0,1,4)。
 *  不是排序列，取值的个数比较多，在这种情况下，直接记录值，不进行编码。

**WS**是为了支持写的，WS中的每一列都用一个从行号到取值的B+树表示，对排序列，还记录一个取值到行号的B+树，以方便查询。

**Tuple Mover**周期性的把WS中的数据移动到RS中。 C-Store中的更新是通过一个删除加一个插入实现的，所以Tuple Mover的主要工作是载入RS中的数据，删掉在WS中被删除的，然后添加WS中新的数据。

## 事务支持 ##

C-Store期望大部分的事务都是只读的，只有商量的支持更新的事务。 为了避免只读的事务有任何锁操作，C-Store使用了Snapshot Isolation的策略。 C-Store周期性的对已经提交的事务进行Snapshot，而只读的Transaction只能查询这些Snapshot而不是最新提交的结果。 对于少量的可以更新的事务，C-Store采用了传统的2PC。

## 查询执行 ##

C-Store的查询执行和传统的Sql操作没有什么不同，主要是多了一个根据Bitmap来Filter数据的操作。 C-Store的查询优化最重要的一步是选出一组Projection。

# 总结 #

我认为，C-Store对分析型数据库而言，有着重要的意义。 在C-Store以前，大家会讨论不同的数据序列适合什么样的编码，会思考如何通过Data Mirror实现查询加速，会考虑到分布式数据存储中的事务支持，但是是C-Store，将这些技术糅合在一起，设计出一个分析型的列存储关系型数据库。 当然，从细节设计和实现上来讲，C-Store不可能说是尽善尽美，这些很多在商业产品HPE Vertica中都有改善，但我认为C-Store跨出了重要的一步，这一步不那么完美， 似乎也并不重要。

C-Store

发表评论取消回复

还没有评论，来说两句吧...

相关阅读