频道栏目
首页 > 网络 > 云计算 > 正文

列存储数据库C-Store介绍

2017-09-12 10:33:41      个评论    来源:landhero的专栏  
收藏   我要投稿

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,有名称和楼层这两列。

 

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

 

上面的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跨出了重要的一步,这一步不那么完美, 似乎也并不重要。

上一篇:数据分析入门之matplotlib
下一篇:算子调优之MapPartitions提升Map类操作性能
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训

版权所有: 红黑联盟--致力于做实用的IT技术学习网站