面向CLAIMS基于Smart物化策略的列存储设计与实现

张晗,周敏奇

(华东师范大学数据科学与工程学院,上海200062)

面向CLAIMS基于Smart物化策略的列存储设计与实现

张晗,周敏奇

(华东师范大学数据科学与工程学院,上海200062)

物化是列存储数据库查询中必不可少的操作,物化策略和物化技术在查询执行过程中起着至关重要的作用.因此设计一种针对列存储数据库的物化策略尤为重要.提前物化生成的元组中存在无关属性;而延迟物化对选择率较高的查询可能无法优化其性能,且某些列会被访问多次.针对以上缺点,本文提出了有别于上述两种策略的策略——Smart物化策略.本文提出了在逻辑查询计划中使用结构——projection,该结构是由用户选取查询所需的属性来生成的,相当于对全表进行物理上的切分;在查询开始时,能减少直接加载到内存的数据量,避免额外的开销.在构建逻辑查询计划过程中,Smart物化策略将projection作为扫描操作标准来对数据进行按列划分,根据一组语句集中对列访问的相关性来对下一次查询所需要的列进行预测,将所需要的列加入到一个最合适的projection中来进行物化.本文通过在分布式内存数据库CLAIMS上使用TPC-H数据集来验证其有效性.

projection;Smart物化;数据压缩

0 引言

随着互联网技术的发展、计算机硬件的不断更新、企业及政府信息化的不断深入,行存储数据库所涉及应用的复杂性越来越高.海量数据管理、实时数据分析、商务智能、决策支持等应用对系统的可扩展性、数据分析的实时性提出了新的挑战.在实时海量数据分析方面,基于行存储的传统关系型数据库技术逐渐显得性能低下,并形成了数据处理技术的瓶颈,尤其是在超大数据集的汇总、关联操作方面操作开销越来越大.而列式数据库系统采用基于按列存储的存储策略,适用于面向企业决策分析领域的实时数据分析处理,尤其在金融交易数据分析上应用广泛.

按列存储在复杂数据查询中,因其只读取相关列的数据,大大减少内存数据量和I/O(Input/Output)开销,从而提高了查询的效率;同时,在列上建立索引使得信息检索的速度达到秒级.数据压缩是列存储数据库的显著特点之一,通过算法将数据文件进行合理压缩,减少存储的数据量.现有列式存储引擎C-store[1]可以直接对压缩数据格式进行操作,减少了操作过程中的数据量,提高了读操作的速度.对于现代CPU(Central Processing Unit)而言,CPU在缓存中找到有用的数据称为命中;当缓存中没有CPU所需的数据时(未命中),CPU才访问内存.所以,CPU访问内存的频率越低(也称未命中频率),查询的效率就越高,在列式数据库中使用数据成组迭代技术有助于提高缓存的命中.同时,列式存储具有高度的可压缩性,从而提高了CPU的吞吐量.延迟物化作为列式存储的关键技术之一,其使得查询引擎并不直接在物理上的数据进行操作,而是以指针形式处理数据,保证数据的完整输出,尽可能地推迟构建元组的时间.然而物化作为影响列存储数据库的性能关键,最需要考虑的问题是何时将不同列组合构建成新的元组.提前物化会导致在构建过程中添加与查询语句无关的属性,而延迟物化通过推迟元组的构建,从而达到构建元组属性最少、生成元组最少的效果;但是某些列会访问两次以上,浪费了CPU资源.针对上述问题,本文提出了一种Smart物化方式,不同于传统的提前物化和延迟物化,该物化方式仅将相关属性构建进元组中,同时在该策略中使用projection的结构来避免对某些列访问两次,造成CPU资源的浪费.本文主要贡献在以下3个方面.

(1)提出了一种新的物化策略—–Smart物化.

(2)为CLAIMS系统底层设计列存储引擎.

(3)在CLAIMS系统上验证Smart物化策略的有效性.

论文的内容安排如下:第1节主要介绍列存储数据库使用的相关技术;第2节介绍现有列存储数据库中的物化策略;第3节介绍基于Smart物化的优化方案;第4节主要针对基准数据集TPC-H与不同的分布式内存计算模型进行性能对比;第5节总结Smart物化策略在数据分析系统以及CLAIMS系统上性能的提升.

1 相关工作与技术

按列存储的概念早在1985年的论文[2]中即已提出,简称DSM(A Decomposition Storage Model),是列数据库的雏形,但是这种技术在当时并没有得到足够的重视.近些年来,在以Michael Stonebraker、Daniel J.Abadi、Peter Boncz为首的一批专家的大力提倡下,围绕列存储数据库的商业价值以及列数据库主要关键技术(包括存储压缩、延时物化、成组叠代、查询优化、索引、加密等)的研究和应用快速发展,在金融数据分析领域开辟出了一条新道路.文献[3]明确指出,在不断变化的时代中,指望一个数据库产品就能够一统天下的日子已经一去不复还了.目前开源列数据库有C–Store、rasdaman、MonetDB等,商用列数据库有Sybase IQ、Vertica Analytic Database、ParAccel Analytic Database、EXASOL EXASolution等.

1.1 数据压缩

在当前计算速度快速增长的时代,I/O渐渐成为硬件瓶颈,计算带宽远远高于I/O带宽,尽管数据存储的硬件从原先的普通硬盘SATA发展到SSD,数据持久化方式从HDFS发展到内存中的mem-cache,I/O的劣势仍然明显.虽然在现有数据库中使用了多种方式来平衡计算与I/O速度的差距,但是考虑到商用的使用环境,将数据进行压缩仍显得尤为必要[4-5].

公式(1)说明了数据压缩的必要性,同时性能指标如下.

其中,B为I/O带宽,C r表示压缩比,Q为查询带宽,D为解压缩带宽,R为生成结果的带宽,B C r表示数据传输的带宽,即表示数据处理过程的带宽.查询过程中主要分为两个阶段,数据传输阶段和数据处理阶段.数据传输主要的瓶颈是I/O,在分布式情况下网络传输也作为衡量指标;数据处理细分为两个阶段,数据解压缩和数据查询,这个阶段主要的开销在于CPU的处理速度上.这两个阶段与生产者和消费者模型类似,哪个环节慢就会拖累整个过程,并成为生成结果的带宽.当I/O为瓶颈时,数据传输的开销会更大,此时CPU会等待数据从磁盘导入到内存中,对数据进行解压缩.此外当集群计算资源不足时,解压缩速度越快,查询时间也越短.但在计算资源富足时,则压缩比越大越好.使用专门针对列式存储的压缩算法,有助于执行引擎直接对压缩数据进行操作.在开源的存储引擎parquet、ORC中,都将数据压缩作为必要的操作.

1.1.1 字典压缩

字典压缩模式可能是在当今数据库中最为常见的一种压缩模式.通过这种方式可以将经常使用的模式替换成很小的编码,建立编码与被替换的模式之间的映射关系,将这样的映射关系作为字典进行查询.如图1所示.

字典压缩的优势是将每个属性的内容映射成简短的编码,以此来调高属性元素的频繁度.如果在列上建立索引,可将不同元组属性中的相同成分保存在同一条目中,减少保存元组所需要的条目.

然而列式存储的字典压缩也存在一定缺陷,例如,基准测试集TPC-H中的大表LINEITEM中的属性L EXTENDEDPRICE,经由字典压缩后,生成的字典表的耗时较大,增加了额外的开销.

图1 字典编码Fig.1 Dictionary coding

1.1.2 行程编码

行程编码将列中相同元素统一转换成一个值进行表示,这种方案比较适合已经排过序且大小比较合理的列,通过三元组进行管理(值、起始位置、长度).

如果使用行存储,那么存储的数据必须是稀疏的或是大量重复的数据,否则产生的三元组的数量将会接近元组的数量,产生更大的额外开销.面对TPC-H数据集,该编码帮助减少的数据量也非常有限.它比较适用于已经排好序的、包含极少不同元素的列存储数据,比如交易操作的数据集.

1.1.3 位图编码

当列中的元素个数有限时,位图编码更为合适.该方法通过0或1来表示元素在某位置上是否存在来进行编码,将元组转换成为二元组的形式(元素值、表示出现位置的位图).行存储利用这种编码方式来生成索引,来提高查询速度.相比较行存储,列式存储更为直接的将数据进行转换和去重.在无序和较少不同元素的列中,位图编码发挥的作用更大.然而当数据选择率高时,生成的位图会更加稀疏,不利于存储.所以使用位图编码时,应该更加慎重考虑使用场景.

1.1.4 轻量级压缩

字典压缩、行程编码、位图编码等3种压缩方式,对按列存储的数据格式的优化简单而直接,然而各自都存在缺点.针对测试数据集TPC-H来说,LINEITEM中的属性L EXTENDEDPRICE不管用哪种压缩方式都不能将压缩比提高到0.4.面对较大的数据量,需要使用通用压缩的方法以将该列切分成数据块进行压缩.相比较重量级压缩,通用压缩虽然不能极大地压缩数据达到最好的压缩比,但极快的解压缩速度是其优点.在优化分布式数据库的网络方面,解压缩速度是作为考虑的因素.Snappy[6]压缩具有较快的速度、高稳定性和较好的鲁棒性,其压缩速度可达到250 MB/s,无需汇编代码.Google数据中心大量使用了该算法进行压缩,压缩数据达到PB级,可以保证其稳定性.我们选用该压缩算法作为CLAIMS系统压缩方案中的一个算法.

1.2 分布式内存数据库CLAIMS

CLAIMS是分布式内存OLAP系统,主要提供高可用的实时查询和数据的实时注入.作为关系型数据库,支持SQL92标准,设计采用传统迭代器模型并使用弹性流水线并发提高查询速度[7].作为内存数据库,CLAIMS将数据加载到内存中驻存,数据在内存中进行计算,避免了多余的I/O开销[8].作为分布式数据库,CLAIMS采用主从节点的模式(Master/Salve),集群中有唯一的主节点作为任务的调度者,主要负责接收SQL语句,解析并生成查询计划树,通过任务调度器将任务分发给其他从节点,收集并汇总从节点返回的结果信息;从节点主要计算主节点分发的任务,并将执行结果返回给主节点.

主节点(Master)由SQL解析器(SQL Parser)、查询优化器(Query optimizer)、元数据管理器(Catalog)、资源管理器(Resource)、任务调度器(Scheduler)、协调器(Coordinator)等6个部件组成;而从节点(Salves)主要包括执行器(Executor)、资源管理器(Resource)、本机调度器(Coordinator)和存储引擎(Stroage)等4部分.如图2所示.

图2 CLAIMS架构Fig.2 The architecture of CLAIMS

2 列存储数据库中的物化策略

本文在实现的物化方案中智能地调整元组构建所需的属性,使其物化产生的元组在一系列查询语句中达到较好的效果.

执行一个查询计划的原始方法是对运算进行适当的排序,并且将每个运算的结果存储在磁盘上直到它被另一个运算所需要,这种策略叫做物化.在现今硬件技术的发展下存储设备单位价格降低,大容量内存成为可能,因此可以将较大的中间结果物化到内存中,以此来提高查询性能.物化技术作为提高数据库查询性能的重要手段是数据库领域研究的热点,例如Vertica通过对延迟物化和提前物化这两种物化策略的权衡,选择代价较低的物化策略,来提高查询速度.本文通过分析大数据的数据特征以及影响物化的操作、查询语句的频率和列与列之间的相关性,提出基于列存储的分布式内存数据系统的物化策略.

2.1 提前物化

提前物化是尽可能早的构建元组,以便在查询计划中生成需要的元组值.在列存储数据库中,列数据将被加载到内存中进行解压缩,并被拼接成行数据.提前物化的好处是,列在查询过程中被访问,将其直接物化到中间结果中,减少了额外访问的开销.但会带来以下问题:所有数据都被解压缩;无关属性添加到元组增加了查询的开销;内存资源不足.

2.2 延迟物化

延迟物化针对压缩的列式数据有着很高的性能,例如列数据库c-store中所实现的列式查询引擎可以直接针对压缩数据进行操作[9].同时,延迟物化能在查询计划中推迟构建元组时间,以生成较少的元组,提高查询速度.由Daniel的文章[10]中可以知道在查询中延迟物化的效果会更加好,特别是复杂查询语句.在列式执行引擎中,join操作最为影响性能,尤其是有很高选择率的join操作或者join操作生成的结果接着进行聚合操作的情况,而针对复杂join操作使用延迟物化策略能够得到良好的性能.但是延迟物化也有一定缺陷,它会在查询计划中导致某些列被多次访问.假设某列首先通过匹配谓词来获得位置信息,然后再次访问来获取值;当查询过程中没有使用到索引时,列是被访问了两次,例如在join操作之后再进行排序就会造成额外的成本开销.即使在查询过程中使用流水线模式和高速缓存,CPU的计算资源依然会有一部分浪费在查找数据块位置上.具体见算法1.

上述算法表述:从判定条件的条件F中,将条件所在的列分别用位向量选择标定;生成的位向量与相关列进行逻辑与运算;根据之后生成的查询结果物化元组,如果SQL语句中有聚集操作,需将物化的元组进行聚集操作;生成最后的结果.

3 Smart物化

针对前两种物化策略的缺陷进行优化的Smart物化是基于动态projection来进行物化的策略.基于动态projection的关系型数据库可以选择查询树中任何一个算子进行物化操作.在查询计划树中向上迭代逻辑projection,直到在任何需要的算子位置进行物化[11-12].该物化策略在行存储CLAIMS系统进行验证.

3.1 projection

CLAIMS系统中存在名为projection的结构,实际上是一种在行式存储中减少数据量的结构.在数据注入这一过程中,根据建表与构建projection的信息,将元组按照用户自定义projection所含有的属性成分生成新的元组[13],以此来避免过多不必要的数据加载到内存中,将内存池的大小控制在一个可控的范围内,不会使得某一台机器因为内存不足而宕机

在同一表上会有多个projection,projection是行存储直接进行物化的标准,每一个projection在数据注入阶段,都会生成一个符合自己模式(schema)的元组.这就导致同一元组的不同属性可能会落盘多次,数据在内存中产生了冗余,大大浪费存储空间;而频繁地执行换入换出策略将产生大量的I/O操作,降低了查询速度[14].

图3 projection的结构Fig.3 The structure of projection

为了解决上述问题,本文将数据由行存储转换成列存储,将projection仅仅作为逻辑结构在查询树中向上迭代,根据查询优化器执行列剪枝,将逻辑结构的projection中的属性不断优化,减少所需要的属性个数.为了保证数据可以复用,根据一段时间内输入的查询语句生成最优的projection,将projection中对应的列式结构进行物化,从而降低数据的选择率,减少数据量,加快查询速度.

尽管在逻辑查询计划中以projection进行操作的,但实际上底层数据存储的形式是按照列进行存储的,projection只是持有属性的元数据,因此在同一个表构建多个projection时,内存仅仅维护一份数据,在确定物化的时机时,会生成最优的projection;同时底层文件系统存储的列式结构数据将根据最优的projection生成数据并物化到内存中.

3.2 底层列式数据结构

目前Hbase以及Facebook开发的persto数据库的底层设计都是列簇的形式.列簇不是将元组拆分成单列,而是将多列以簇的形式作为整体进行管理.Hbase表中的每一列,都归属于某一列簇,而列簇仅仅是表的一部分.projection由原来的全表部分属性的组合,重新定义为列簇.细化projection的投影范围,将原有projection由列簇projection替代.

图4 projection中的列簇Fig.4 The family of column in projection

3.3 动态projection算法

根据每次查询产生的查询树,向上迭代projection得到最优projection[15],将其物化结果存放在内存中.而当同一组的每条查询语句得到的最优projection相差不大时,则生成最大包含的projection,以保证每条语句所需要的列信息都囊括在当前的projection中.然而这会造成projection渐渐扩张成为全表的projection,这样就无法减少数据选择率.

针对projection的动态生成,需要检测查询语句与projection中列的相关性.通过每次查询产生需要的列来与全表中列进行权重的更新.我们选取权重较大,且相差不多的列生成projection.具体见算法2.

对于每一条属于Q中的q来说,参考表中属性进行聚类,并分配到第i个簇中.通过与簇中语句进行比较距离,距离主要是两条SQL语句中相同属性的个数来确定.如果语句q与ri属性有差距不大,那么将不相同的属性设置一个权重添加到第i个簇中.每一个簇中的属性列表就是构成projection的参考.使用贪心算法确定ri中的哪些属性应该用来动态生成projection.

根据查询语句的不断变化,该算法将延迟地改变projection的属性.projection在扩张与收缩的物化过程中,一直保留一份projection,此方案减少了内存中冗余的数据,同时也减少了I/O操作,其代价的仅为内存中元组切分或拼接的操作,显然开销是微不足道的.

4 实验

4.1 实验环境

基于CentOS release 6.5(Final)系统,CPU型号为Intel(R)Xeon(R)CPU E5-2620 0@ 2.00 GHz,双路,共12核,可超线程到24核,每各节点拥有165 G的内存和1T大小的硬盘,每个节点之间通过千兆网进行互联.选取标准的基准数据TPC-H进行测试,分别测试扩展因子为1、10以及100的数据,其中TPC-H数据集有8个事实表.TPC-H是用3NF实现的,TPC-H基准测试的度量单位是每小时执行的查询数—–QphH@size,其中,Qph是Query-per-hour(每小时查询),H表示每小时系统执行复杂查询的平均次数,size表示数据库规模的大小,它能够反映出系统在处理查询时的能力[16].

4.2 实验设计

本文将Smart物化实现于分布式内存关系型数据库CLAIMS上,以此来进行其性能评估. CLAIMS是开源的分布式内存数据库,运行在NUMA架构的集群上,支持数据实时注入和实时查询.列式存储的缺点是在写过程中增加了拆分元组的操作,增加了CPU的开销,而在读操作上进行了优化.同时,数据在内存中的复用也作为性能考核的指标,不过内存中数据的复用是显然的,随着构建projection的增加,先前版本会不断地增加数据量,造成内存和磁盘上的数据膨胀,同时频繁的换入换出也增加了I/O的开销.

实验1:将列式版本与之前版本进行内存中数据量的比对

在CLAIMS上构建全表大小的projection以及不同种的projection,原CLAIMS以行的形式存储,必然会造成数据的冗余,从而增加了内存的负担以及I/O开销.图中可以看到数据量在列式的情况下并没有多余的增长,而原CLAIMS内存中的数据在不断的膨胀.同时操作系统也会频繁地进行换入换出操作,降低查询效率.

图5 内存中的数据量Fig.5 The delay of three materialization strategies in di ff erent query

表1 在不同SQL语句中3种物化策略的时延Tab.1 Simulation results of parametric estimation

通过比较表中查询语句的结果可以得出,Smart物化在初期的物化时延其实与延迟物化是一样的.但随着查询语句间相关性的比对,projection将被保持在一个最大包含的相关属性的范围内,在后期则不再需要进行物化操作,而能将之前生成好的元组直接给下一次查询进行使用,减少了I/O以及物化的开销;同时如果某一列的权重过低,Smart物化策略会重新进行物化,排除掉这一列.

5 结论

CLAIMS系统当前版本并不支持列式存储的格式,同时数据会在构建表的过程中造成冗余. Smart物化策略解决了列数据在何时物化成元组,同时Smart物化能尽量减少物化过程中的元组数量.在不同的执行语句中,不同的选择率导致需求的projection不尽相同,但是通过动态收缩projection的大小,物化过程中元组的数据量大小能够得以维护.

[1]STONEBRAKER M,ABADI D J,BATKIN A,et al.C-store:A column-oriented DBMS[C]//International Conference on Very Large Data Bases.DBLP,2005:553-564.

[2]COPELAND G P,KHOSHAFIAN S N.A decomposition storage model[C]//ACM SIGMOD International Conference on Management of Data.ACM,1985:268-279.

[3]STONEBRAKER M,ETINTEMEL U.“One Size Fits All”:An idea whose time has come and gone[C]// International Conference on Data Engineering.IEEE,2005:2-11.

[4]CORMACK G V.Data compression on a database system[J].Communications of the ACM,1985,28(12): 1336-1342.

[5]黄鹏,李占山,张永刚,等.基于列存储数据库的压缩态数据访问算法[J].吉林大学学报(理学版),2009,47(5):1013-1019.

[6]Google Snappy[EB/OL].[2017-04-01].https://github.com/google/snappy.

[7]WANG L,ZHOU M,ZHANG Z,et al.Elastic pipelining in an in-memory database cluster[C]//ACM SIGMOD. ACM,2016:1279-1294.

[8]SIKKA V,RBER F,GOEL A,et al.SAP HANA:The evolution from a modern main-memory data platform to an enterprise application platform[J].Proceedings of the Vldb Endowment,2013,6(11):1184-1185.

[9]ABADI D,MADDEN S,FERREIRA M.Integrating compression and execution in column-oriented database systems[C]//ACM SIGMOD International Conference on Management of Data.DBLP,2006:671-682.

[10]ABADI D J,MYERS D S,DEWITT D J,et al.Materialization strategies in a column-oriented DBMS[C]// 2007 IEEE 23rd International Conference on Data Engineering.IEEE,2007:466-475.

[11]CORNELL D W,YU P S.An ef f ective approach to vertical partitioning for physical design of relational databases [J].IEEE Transactions on Software Engineering,1990,16(2):248-258.

[12]BRYANT R E,HALLARON D R O’.深入理解计算机系统[M].龚奕利,雷迎春,译.北京:机械工业出版社,2011.

[13]IDREOS S,KERSTEN M L,MANEGOLD S.Self-organizing tuple reconstruction in column-stores[C]//ACM SIGMOD International Conference on Management of Data.ACM,2009:297-308.

[14]杨传辉.大规模分布式存储系统[M].北京:机械工业出版社,2013.

[15]BRUNO N,CHAUDHURI S.To tune or not to tune?:A lightweight physical design alerter[C]//International Conference on Very Large Data Bases.VLDB Endowment,2006:499-510.

[16]TPC Benchmark H[EB/OL].[2017-04-01].http://www.tpc.org/tpch/.

(责任编辑:李艺)

Design and implementation of Smart materialization for column-store in CLAIMS

ZHANG Han,ZHOU Min-qi
(School of Data Science and Engineering,East China Normal University, Shanghai 200062,China)

Materialization is a necessary operation in the process of query execution. Materialization strategy and materialization technology play an important role in the process of query execution.Therefore,it is necessary to design a materialization strategy for column-store database.According to the shortcomings of early materialization and later materialization,we provide a strategy named Smart materialization that are dif f erent from the two strategies mentioned above.Here we need to def i ne a concept in the logical query plan—projection,the structure is used to select the desired attributes,the physicaltable is cut by column,to ensure that the structure at the beginning of the query can reduce the direct load to memory of the amount of data,to avoid additional overhead.In the logical query plan,the projection is divided by columns,and the next required columns are predicted according to the relevance of the query in a set of queries,and the required columns are stabilized in one of the most appropriate projection.We use the data set of TPC-H to verify its validity worked on the disturbed in-memory database—CLAIMS.

projection;Smart materialization;data compression

TP311

A

10.3969/j.issn.1000-5641.2017.05.004

1000-5641(2017)05-0030-10

2017-06-19

国家自然科学基金(61672233)

张晗,男,硕士研究生,研究方向为内存数据库系统.E-mail:chxiaoyifeng1992@gmail.com.

周敏奇,男,副教授,研究方向为对等计算、云计算、分布式数据管理、内存数据库管理系统. E-mail:mqzhou@sei.ecnu.edu.cn.