C-store

A Column-oriented DBMS

abstract

introduction

优化更新和优化读的数据结构之间存在矛盾。比如,当数据是按条目到达顺序存储时,可以在列的末尾以批处理或事务方式有效地插入新数据项。但是,这样读的代价会比较大。然而,以非数据到达顺序存储将使插入的代价昂贵。

C-Store从一个全新的角度解决了这个难题。将一个read-optimized的列存储和一个面向更新/插入的writeable store组合在一个系统中,由tuple mover连接。在top level,有一个小型的writeable store(WS)组件,它的体系结构支持高性能插入和更新。还有一个更大的组件称为read-optimized store(RS),它能够支持非常大量的存储。RS只支持一种非常受限的插入形式,即记录从WS批量移动到RS,这是tuple mover要做的。

image-20210429205327568

查询必须同时访问两个存储系统中的数据。插入被发送到WS,而删除必须被发送到WS。在RS中标记,以便稍后由元组移动器清除。更新实现为插入和删除。为了支持高速tuple mover,通过高效的有序合并方法将元组从WS批量移动到RS。

features of C-Store

  1. 一个混合架构,其中WS针对频繁插入和更新进行了优化,RS针对查询性能进行了优化。
  2. 表中的数据以不同顺序在几个overlapping projetions中冗余存储,以便使用最有利的projection来解决查询。
  3. 使用多种编码方案中的一种高度压缩列。
  4. 面向列的优化器和执行器,具有不同于面向行系统中的原语。
  5. 使用足够数量的overlapping projections,通过K-safety实现高可用和改进性能。
  6. 使用快照隔离以避免2PC和锁。

C-Store在物理上存储多组列集。在一个group中每个列按某些属性排序。按相同属性排序的列组称为 projection ;同一列可能存在于多个投影中,可能按每个投影中的不同属性排序。多个排序器可以优化查询。

在这里可以看出projection的概念和通常的projection不同。

存储overlapping projections进一步提高了性能,即使某个服务器发生故障,也可以访问数据。我们称能容忍K次故障的系统为K-safe。

data model

image-20210429212712875

image-20210429212725069

将排序键附加到由竖线分隔的投影上来指示projection的排序顺序。

image-20210429212927647

每个projection horizontally划分为1个或多个segment,segment被赋予一个Sid。在一个projection中基于sort key划分segment。

storage key在RS中编号为1、2、3,并不是物理存储的,而是从列中的元组的物理位置推断出来的。storage key在WS中物理存在,并以整数表示,比RS中任何段的最大整数storage key都大。

join index (sid, storage_key)

image-20210429214528175

RS

encoding

self order the column ordered by values in that column(按列中的值排序,即该列在sort key中)

foreign-order by corresponding values of some other column in the same projection(该列不在sort key中)

  • self order few distinct values:三元组序列(v, f, n)表示,v是存储在列中的值,f是v在列中第一次出现的位置,n是v在列中出现的次数。

  • foreign order few distinct values: (v, b), v是存储在列中的值,b是一个位图,表示该值存储在哪个位置

    • 0,0,1,1,2,1,0,2,1, we can Type 2-encode this as three pairs: (0, 110000100), (1, 001101001), and(2,000010010)
  • Self-order, many distinct values:将列中的每个值表示为与列中前一个值的增量。

    • 1,4,7,7,8,12 would be represented by the sequence: 1,3,3,0,1,4
  • Foreign-order, many distinct values: leave the values unencoded

WS

WS也是一个列存储,实现了与RS相同的物理设计。因此,WS中存在相同的projection和join index。但是,存储表示形式有很大的不同,因为WS必须以事务方式有效地更新。

SK 显示存储

WS的水平分区方式与RS相同,因此RS segment与WS segment之间是1:1的映射。

假设WS size比较小 不压缩; 直接表示所有数据。因此,每个projection使用b -树索引,以保持逻辑排序键顺序。

WS projection中的每一列都表示为(v, sk),这样v是列中的值,sk是其对应的storage key。每个对在storage key上用b树表示。每个projection的sort key被另外表示为(s, sk),这样s是一个排序键值,sk是描述s第一次出现的storage key。同样,这个结构表示为sort key上的b树。要使用sort key search,可以使用后一个b -树查找storage key,然后使用前一个b -树集合查找记录中的其他字段。

storage management

projection中的一个segment中的所有列存储在一个服务器节点上。join index和segment存储在一起。ws和相同key range的rs存储在一起。

tuple mover

将创建一个新的RS segment,我们称之为RS’。然后,它从RS段的列中读入块,删除delete record vector值小于或等于low water mark的任何RS项,并合并来自WS的列值。然后将合并的数据写入新的RS段,该段随着合并的进行而增长。这种old master/new master将比就地更新策略更有效,因为基本上所有数据对象都将移动。需要维护join index.