当前位置: 代码迷 >> 其他数据库 >> C-Store论文翻阅笔记
  详细解决方案

C-Store论文翻阅笔记

热度:82   发布时间:2016-05-05 08:15:06.0
C-Store论文阅读笔记

C-Store论文由今年的图灵奖获得者Mike Stonebraker提出来,整体架构在数据库领域相当不错。数据库采用读写分开存的架构,只写块的数据定期会和只读块儿的数据进行合并,产生新的只读块儿。而C-Store在只读块儿部分做了读优化操作,这一点相当不错。

1. 数据模型

猜想商业数据库的Clustrix的存储数据模型就是收到了这篇论文的影响,所以才会有C-Store论文中提到的这样的数据模型构造。首先需要明确的一点是,C-Store本身是列数据库,所以存储数据是按照列为单位来进行存储,这样就可以玩出很多花样来,比如列压缩,列索引之类的。对于查询方面的优化是无疑的。

在数据模型方面,有两个重要的概念,一个是projection,一个是Segment。可以这么理解,projection是对表的纵切,而Segment是对表的横切。举一个实际的例子:

NameAgeDeptSalary
Bob255Math
Bill27EECS50K
Jill24Biology80K

那么一个projection可以是这样

NameAge
Bob25
Bill27
Jill24

一个Segement可以是这样
| Name | Age |
| -------- | ----- |
| Bob | 25 | 5 |

projection更类似与一个列族的概念,而Segement更像是一个行表的概念,只是对一个projection进行切分。

2. 压缩模型

列数据相对于行数据库而言,最大的优势就是压缩了,在C-Store这篇论文里面,针对RS(Rea-optimized Store)这一块儿的数据进行了压缩,论文里面探讨了四种情况下的压缩方案:

  1. Self-order,few distinct values:内排序并且少许不一样的数据,也就是说,这一列的数据是排好序的同时,重复数据比较多,那么压缩方案就好办了。利用一个三维向量表示(v,f,n),其中v表示value,f表示该value出现的位置,n表示该value重复的次数,例如在12-18号位置出现了4,那么就可以表示为(4,12,7)。
  2. Foreign-order,few distinct values: 这种情况下,采用位图压缩的方式对这一列进行压缩,例如一个列的值序列如下为 0,0,1,1,2,1,0,2,1,那么压缩的方式为(0,110000100),(1,001101001),(2,000010010)也就是如果该value出现在哪一号位置,就在对应的位图位置上置1。
  3. Self-order,many distinct values: vaues:在这种情况下,前面的两种压缩方案都不会适用了,在C-Sotre论文中提到了一种增量压缩的方式,在一列数据中,每一个值都可以由他的前一项进行推导出来,例如一个列数据序列1,4,7,7,8,12,那么压缩之后,这个序列变为:1,3,3,0,1,4。
  4. Foreign-order,many distinct values: 在这种情况下,压缩基本不可能实现,但是可以用一颗紧凑的B+树对其进行索引。
  相关解决方案