摘要：随着数据规模和分析需求的日益增长，数据库面向联机分析处理（on-line analytical processing，olap）应用的查询性能变得愈发重要.cedar是一款基于读写分离架构的分布式关系数据库，由于它主要面向联机事务处理（on-line transaction processing，oltp）业务，在面对分析处理负载时性能表现不足.对于这个问题，很多研究表明列存储技术能够有效地提高i/o（input/output）效率，进而提升分析处理的性能.在cedar上提出了一种列存储机制，分析了其适用场景并针对这种机制改进了cedar的数据扫描和批量更新方法.实验结果表明，该机制能大幅度地提升cedar分析处理性能，并且对事务处理性能的影响控制在10%以内.
关键词：分布式数据库 列存储 联机分析处理(olap)
俞文谦, 胡爽, 胡卉芪. 面向cedar的列存储设计与实现[j]. 华东师范大学学报(自然科学版)
0 引言
近年来, 计算机硬件的快速发展使得各行各业中数据的采集、存储、传输及处理能力日益提升, 数据规模逐渐扩大, 对数据分析处理的需求也不断增长. olap[]是一种帮助企业从大量数据中提取价值信息的软件技术, 能为企业管理人员提供有效的决策支持.在应用需求的推动下, olap技术迅速发展起来.与此同时, 数据库面向olap应用的查询性能也越来越受到研究学者的关注.
cedar[]是由华东师范大学数据科学与工程学院基于oceanbase 0.4.2研发的高通量、可伸缩、高可用的分布式关系数据库.作为一款主要面向oltp业务的数据库, cedar使用行式存储的方式组织数据, 以整行为单位操纵数据.然而分析处理型负载的特点是涉及的数据量特别大, 并且只需要获取少数属性列的数据.这使得cedar在面对分析处理型负载时会有大量冗余的i/o开销, 导致查询性能表现不足.因此, 优化分析处理的性能成为了cedar面临的挑战之一.
对于这个问题, 很多学者的研究表明列存储技术能够有效地提高i/o效率, 进而提升分析处理的性能. 1985年, copeland等人首次提出并分析了列存储模型[].与行存储相比, 列存储能够对数据进行更细粒度地读取, 查询时只需从磁盘读取需要的属性, 无需读取其他冗余的属性.因此, 列存储在分析处理负载下能表现出更高的i/o效率[].另外, 列存储的各列数据类型相同且列值连续存储, 使得采用编码技术获得的压缩效果通常优于行存储[].随着数据规模和分析需求的急速增长, 列存储的优势变得越来越突出, 围绕着列存储的研究与实践也不断涌现出来:相关技术如petraki等人提出的列存储上自适应的一体化索引[]、lang等人提出的针对冷数据压缩的列存储格式data blocks[]等; 基于行列混合存储的数据库系统如snappydata[]、hana atr[]等; 基于新型硬件gpu的数据库系统如sqream db[]、mapd[]等.
综上所述, 为提高cedar面向olap应用的查询性能, 满足企业数据分析处理的需要, 本文基于cedar设计并实现了列存储机制.本文的主要贡献如下.
(1) 基于cedar读写分离架构的特点设计了列存储机制, 并分析了其适用的场景.
(2) 针对列存储机制, 提出并分析了列存储数据扫描和批量更新算法.
(3) 在cedar上实现了列存储机制, 并通过实验验证了该机制能大幅度地提升cedar的查询性能, 且对其事务处理性能影响极小.
论文内容安排如下:第1节描述cedar系统架构; 第2节阐述cedar列存储机制的设计, 分析cedar列存储机制的适用场景; 第3节介绍cedar列存储机制的实现, 包括列存储文件格式、基于该格式的数据扫描及批量更新算法; 第4节通过实验验证该列存储机制的高效性和分析其适用场景; 第5节总结全文.
1 cedar系统架构oceanbase[]是阿里巴巴研发的分布式关系数据库, 现已广泛应用于阿里巴巴、蚂蚁金服等关键业务. cedar在oceanbase 0.4.2开源版本上, 新增了高可用的三集群架构、存储过程、二级索引、快照隔离级别、可扩展事务提交等特性. cedar系统架构如所示.
| 图 1 cedar系统架构fig.1 the architecture of cedar |
cedar由一主集群、两个备集群组成; 在单个集群中有4类服务器, 是rootserver (rs)、updateserver (ups)、mergeserver (ms), 以及chunkserver (cs). rs是cedar的总控节点, 管理cs和ms的上下线、元数据及数据的分布, 负责集群之间的选主, 在一个集群中只有一个rs. ups是cedar集群中唯一能接受写入的服务器, 负责执行数据更新的操作, 在内存表中维护着增量数据, 一个集群中只有一个ups. ms负责接收并解析客户端的查询请求, 对请求中的sql语句进行词法分析、语法分析及生成执行计划等步骤后, 将请求转发到相关的服务器, 最后将合并结果返回给客户端, 在一个集群中可部署多台ms. cs负责存储着基线数据, 在一个集群中可部署多台cs.
cedar采用读写分离的结构, 把数据分为基线数据和增量数据[]:基线数据是只读的, 由cs负责存储和管理; 增量数据是新增、删改、更新的数据, 存储在ups的内存中.受限于ups内存大小, 当增量数据的大小达到阈值时, cedar会冻结当前的增量数据, 且将其与原基线数据进行合并, 最终生成新基线数据.
2 列存储机制的设计2.1 设计思路cedar列存储机制的设计目标是提升其分析处理性能, 同时不影响其事务处理性能.首先, 对cedar的架构进行分析.在cedar中数据的更新不会立即持久化到磁盘上, 而是先保存在ups的内存中, 等到合并阶段才进行批量持久化, 故cedar具有"延迟更新, 批量写入"的特点.对于列存储机制, "延迟更新"使得原有事务处理性能不受到影响; "批量写入"使得数据存储方式的选择更加灵活, 在合并阶段采用列式存储方式, 从而提高cedar分析处理性能.考虑到应用负载日益多元化, 行式存储和列式存储都有各自适用的场景.为了让性能达到最优, cedar需要同时具备两种数据访问方法.因此, 本文在原cedar架构基础之上, 新增一个读写列存储数据的列式访问方法模块.由于基线数据的存储与管理由cs负责, 故本文提出的列存储机制实现在cs上.列存储机制架构设计如所示.
| 图 2 cs上列存储机制架构fig.2 the architecture of columnar storage on the cs |
中cs的数据存取器用于磁盘存储访问, 实现数据的查询读取以及增量更新数据的批量写入的功能.在cs磁盘上的数据可以行、列存储格式分别进行组织, 行式存储的数据文件为sstable, 列存储的数据文件为parquet, 其数据访问接口分别由cs中的行式访问方法、列式访问方法实现.该设计的优势是, 受益于cedar"延迟更新, 批量写入"的特点, 列存储机制下事务处理产生的数据更新不会引起磁盘i/o, 而是维护在内存中, 这保证了事务处理的良好性能.值得注意的是, 由于存储方式的选择权转移到了用户上, 故用户能否选择合适的存储方式变得尤为重要.本文在第2.3节中将对这个问题进行具体分析.
2.2 列存储数据的一致性cedar采用多副本策略管理数据, 将数据的副本存放在多个cs上.通常情况下, cedar对列存储数据进行访问时, 需要融合cs的基线数据和ups的增量数据, 再将符合查询条件的数据返回.由于此时cs的基线数据是只读的, 故在多个cs上读到的数据是相同的.然而在合并阶段期间, 每一个cs的合并进度会各不相同.例如一些cs已经完成数据的合并, 生成新版本的parquet, 而另一些cs还未完成.这就造成了一种情况的出现:执行相同的查询语句, 从不同的cs上读取到parquet的内容可能不同.对此, cedar为保证查询结果是一致的, 采取的策略是:如果查询使用是旧版本的parquet, 会将冻结数据和新的增量数据融合; 如果查询使用的是新版本的parquet, 则只融合新的增量数据[].如此, 列存储机制下数据的一致性得以保证.
2.3 列式存储适用场景的分析当cedar具有两种存储方式后, 要使cedar的性能得到充分发挥, 用户需要考虑选择适合的存储方式.为解决这个问题, 本文对cedar在不同存储方式下的数据访问代价进行了对比分析, 得出了列式存储的适用场景.以下列面向olap应用的查询为例进行分析, 令该查询为query, 具体如下.
select class, count(all stu_name) as total from student group by class;
对于查询query, 首先ms对其进行sql解析, 生成并执行查询计划, 将数据读取请求发送到基线数据所在cs上; cs收到请求后从磁盘读取基线数据到内存, 同时向ups拉取增量数据, 然后cs合并两种数据后将结果集返回给ms; ms对结果集进行处理后将最终结果返回客户端.由于两种存储方式的区别在于磁盘上数据的组织方式, 因此本文对cedar数据访问代价的对比分析主要集中在cs上. cedar的数据访问需要经过磁盘数据传输和预处理两个阶段, 其代价cost (query)近似为
| $ \begin{align} {\rm cost} ({\rm query})\approx\dfrac{k\cdot {\rm size}_{\rm block}}{h_{\rm disk}} {\rm cost} ({\rm preprocess}), \end{align} $ | (1) |
其中,
由于硬件环境和查询请求相同, 数据传输单位大小、数据传输能力、结果集大小均相等, 因此行式存储方式与列式存储方式的数据访问代价主要区别在于数据传输量和预处理的开销上.
对于行式存储方式, 多个记录之间连续放置, 且通常采用snappy[]压缩.查询时需将请求的记录集完整地读入到内存, 然后通过投影操作获取需要的列, 则
| $ \begin{align} k_{\rm row}\approx\dfrac{n_{\rm record}\cdot {\rm size}_{\rm record}\cdot r_{\rm compress}}{{\rm size}_{\rm block}} \end{align} $ | (2) |
其中,
由于从磁盘读取到内存的数据需要进行snappy格式解压操作, 故预处理代价为
| $ \begin{align} {\rm cost}_{\rm row} ({\rm preprocess})=\dfrac{k_{\rm row}\cdot {\rm size}_{\rm block}}{h_{\rm decompress}}, \end{align} $ | (3) |
其中
对于列式存储方式, cedar先对数据进行rle[]编码, 再使用snappy压缩降低磁盘存储的开销.执行查询时只需读入请求需要的列, 无需读入多余的列, 则
| $ \begin{align} k_{\rm column}\approx \dfrac{n_{\rm record}\cdot n_{a_i}\cdot {\rm size}_{a_i} \cdot r_{\rm encode}\cdot r_{\rm compress}}{{\rm size}_{\rm block}}, \end{align} $ | (4) |
其中,
与行式存储方式不同, 列式存储方式从磁盘读取到内存的数据不仅需要进行解压操作, 还需要进行解码操作.因此预处理代价为
| $ \begin{align} {\rm cost}_{\rm column}({\rm preprocess})=\dfrac{k_{\rm column}\cdot {\rm size}_{\rm block}}{h_{\rm decompress}} \dfrac{n_{\rm record}\cdot n_{a_i}\cdot {\rm size}_{a_i}\cdot r_{\rm encode}}{h_{\rm decode}}, \end{align} $ | (5) |
其中
通过两种存储方式的数据访问代价对比分析, 可以推出行式存储的数据访问代价大于列式存储的数据访问代价时, 即cost
| $ \begin{align} &\big(\dfrac{1}{h_{\rm disk}}\! \!\dfrac{1}{h_{\rm decompress}}\big)\!\cdot\! r_{\rm compress}\!\cdot\! ({\rm size}_{\rm record} \!-\!n_{a_i}\!\cdot\! {\rm size}_{a_i}\!\cdot\! r_{\rm encode})\!>\!\dfrac{n_{a_i}\!\cdot\! {\rm size}_{a_i}\!\cdot\! r_{\rm encode}}{h_{\rm decode}}. \end{align} $ | (6) |
由式(6)可以看出, 当查询涉及的列数越少、rle编码的压缩比越低、单位时间内rle解码的数据量越大时, 列存储机制的数据访问代价相比行存储的越低. rle编码的压缩比与数据重复率有关, 这是因为rle编码使用数值和数值重复的次数来表示一些连续相同的数据, 从而达到压缩数据的效果.例如字符串aaabbbcccc, 经过rle编码后得到3a3b4c, 降低了文件所占用的存储空间.当数据重复率越高时, rle编码的压缩比就越低.需要注意的是, 单位时间内rle解码的数据量是由系统采用的算法决定的.因此, 在用户的角度上, 需要考虑的主要因素有查询涉及的列数和数据重复率.在查询涉及的列数较少、数据重复率较高的场景下, 采用列式存储方式更具有明显的优势.该结论将在本文第4节的实验中进行验证.
3 列存储机制的实现根据列存储机制的设计, 需要在cedar上增加一个列式访问方法模块, 用于完成对列存储数据读取和写入的基本操作.该模块的实现主要包括3个部分:列存储文件格式、基于该格式的数据扫描算法及批量更新算法.列存储文件格式是列存储机制中最基本的数据结构, 对列存储数据的操作都在其上进行; 数据扫描算法决定cedar是如何访问列存储文件; 数据批量更新算法决定cedar是如何生成列存储文件.在本节中将依次介绍这3个部分.
3.1 列存储文件格式列存储文件格式是cedar列存储机制的核心部分, 它决定数据在磁盘上的组织方式, 关系着数据存取的效率和磁盘存储空间的开销.考虑到减少对上层应用系统的侵入性, 提高系统应用场景的扩展性, 本文采用的列存储文件格式为parquet[]. parquet是一种流行的开源列式存储格式, 支持投影下推和谓词下推, 并能使用多种数据压缩和编码方式处理海量数据. parquet数据结构如所示.
| 图 3 parquet数据结构fig.3 the data structure of parquet |
parquet由magic number、行组、页脚和footer length组成. magic number用来校验该parquet, 关系表被水平切分存放在多个行组中, 一个行组包含多个列块, 列块由多个数据块组成, 并且各数据块块头存放着该块的元数据. footer length存储着元数据的信息, 可利用它来定位页脚.页脚存放着文件的元数据和各个行组的元数据.
3.2 列存储的数据扫描算法面对分析处理型负载时, cedar需要从cs上获取列存储基线数据.为此, 本文基于parquet的结构特点, 提出了一种数据扫描算法——列存储数据扫描算法.该算法负责根据查询条件从parquet中读取数据到内存, 实现列存储机制的数据访问功能, 具体见算法1所示.由于parquet的元数据记录该行组中各属性的最大值和最小值, 可通过这些值实现基于行组的过滤.在载入行组元信息后, 由于列存数据文件按照逻辑行的主键排序, 如果查询条件中包含了主键, 则使用二分查找法过滤掉一部分的行组(行2-8);然后使用除主键以外的列查询条件, 遍历剩下的行组元数据, 根据每个列的查询条件, 得到其结果集, 并判断是否与行组对应列上的范围值产生重叠, 若其交集为空集, 则过滤掉这个行组, 否则, 将该行组读入到内存(行9-18).
算法1是cedar列存储机制性能优化的重点, 其算法效率对查询性能具有巨大的影响.因此, 本文对该算法进行时间复杂度分析.假设关系表
在合并阶段, cedar需要将cs的旧版本列存储数据与ups的增量数据进行融合, 生成新版本列存储数据.因此, 本文提出了一种数据批量更新算法, 负责将cedar的数据转换成parquet, 具体见算法2所示.算法2中, 数据表中每一个属性列由一个列数据写入器column_writer负责, 每个列数据写入器拥有各自的数据块, 存放着数据缓存.在算法开始时会依次初始化列存储的数据文件parquet_file和各列对应的列数据写入器; 然后不断地从基线数据存取器获取需要写入的记录, 遍历每一条记录的数据项, 各列数据写入器将对应的数据项进行rle编码写入其数据块缓存中, 当这个数据块缓存达到阈值时, 将数据写到列块column_chunk中; 最后当前处理的记录达到parquet_file的行组限制时, 将各个列块column_chunk进行snappy格式压缩后写入parquet_file, 若当前parquet_file大小达到阈值, 则创建新的parquet_file进行存储.
算法2的效率决定着cedar列存储机制数据持久化的性能, 故对其进行时间复杂度分析.假设关系表
本文在开源的分布式数据库cedar上实现了列存储机制.实验服务器配置信息如下: inter(r) xeon(r) e5-2680 cpu, 168 g内存, 千兆以太网, centos release 6.5(final) 64位操作系统, 在一台服务器上rootserver(rs)、updateserver(ups)、mergeserver(ms), 以及一个chunkserver(cs)各部署一个.
4.2 单表聚合函数性能测试实验目的:测试单表情况下列存储机制对系统的聚合函数性能影响.
实验设置:本测试使用某企业具有128列属性的核心业务表, 并生成50万行、100万行、200万行、500万行及1 000万行数据集, 分别在原cedar版本和引入列存储机制后的新版本上进行测试. sql语句包含olap应用常见的聚合操作, 例如count、sum等.实验结果如所示.
| 图 4 聚合函数性能fig.4 the performance of the aggregate functions |
描述的是cedar引入列存储机制前后的聚合函数性能对比, 横坐标表示数据集大小, 纵坐标表示查询响应时间.可观察到数据集较小的时候, 两者的查询响应时间差距较小, 随着数据集规模的扩大, 两者的响应时间都呈现增长趋势, 但引入列存储机制后的增长率低于原cedar的增长率; 当数据集达到1~000万行时, 原cedar的查询响应时间是引入列存储机制后的3.11倍.由于现实业务表中数据的重复项较多, 这造成了数据重复率会随着数据集规模的增大而提高, 压缩的效果也越显著, 降低了i/o开销. cedar在引入列存储机制后的查询性能得到提升, 且随着数据集的增大, 性能的提升越显著, 展现出其良好的扩展性.
4.3 事务处理性能测试实验目的:测试列存储机制对系统的事务处理性能影响.
实验设置:本测试使用具有50万行、128列属性的数据表, 不断增加连接并发数, 分别在原cedar版本和引入列存储机制后的新版本上进行测试.测试工具为sysbench.事务包含的语句有插入一条新记录的操作、一次4个主键列的等值查询.对18个非主键列进行一次更新操作.结果如所示.
| 图 5 事务处理性能fig.5 comparison transaction processing performance |
展现了cedar引入列存储机制前后的事务处理性能的变化, 横坐标表示cedar连接并发线程数目, 纵坐标表示cedar每秒处理的事务数量(transaction per second, tps).可观察到随着并发线程数目的增多, 两者的tps都呈现增长趋势, 但差距并不明显.可见cedar在引入列存储机制后对事务处理性能的影响较小, 这是因为cedar中数据的更新不会立即持久化到磁盘上, 节省了i/o的开销. cedar列存储机制的性能损失一直维持在10%以内, 体现出列存储机制具有低侵入性.由于cedar行存储机制采用了块索引、块缓存、行缓存的三级缓存设计, 对查询性能进行了优化处理.相比之下, 列存储机制并没有设计缓存, 其在这个查询上的性能处于劣势, 最终造成了列存储机制的tps略低于行存储机制的结果.因此, 针对列存储机制的缓存设计将是进一步深入优化的方向之一.
4.4 查询涉及的列数对性能的影响实验目的:测试单表情况下查询涉及的列数对系统的查询性能的影响.
实验设置:本测试使用具有50万行、128列属性并且各字段长度相等的数据表, 分别在原版本和引入列存储机制后的新版本上进行测试. sql语句包含有count、sum等聚合函数.查询语句涉及的列数分别为1列、2列、4列、8列、16列、32列及64列.考虑到原版本缓存机制会缓存规模较小的数据, 而olap负载涉及的数据规模特别大, 因此本文消除了缓存带来的影响, 使测试结果更具意义.结果如所示.
| 图 6 查询涉及的列数对性能的影响fig.6 the performance impact of the number of columns in a query |
描述的是查询涉及的列数对系统的查询性能的影响, 横坐标表示查询涉及的列数, 纵坐标表示查询响应时间.可看观察到查询涉及的列数较少时, 引入列存储机制后的性能要优于引入前的性能; 随查询涉及的列数的增多, 两者的响应时间都呈现增长趋势, 但列存储机制的查询响应时间增长率明显高于原cedar的增长率.在查询涉及列数达到16列以后, 引入列存储机制后的性能要劣于引入前的性能; 当查询涉及列数达到64列时, 引入列存储机制后的查询响应时间是原cedar的1.29倍.这验证了本文第2.3节中的结论:查询涉及的列数是影响两种存储方式数据访问代价差异的主要因素之一; 当查询涉及的列数越多时, 列存储机制的劣势越突出.因此, 可以总结该机制适合于查询涉及的列数较少的场景中.
4.5 数据重复率对查询性能的影响实验目的:测试单表情况下数据重复率对cedar的查询性能影响.
实验设置:本测试使用10张具有50万行、128列属性并且各字段长度相等的数据表, 其各列平均数据重复率分别为0%、25%、50%、99%、99.9%.在原版本和引入列存储机制后的新版本上进行测试. sql语句包含有在2个非主键列上做全表的count、sum的聚合函数操作.基于同样的原因, 测试消除了原版本缓冲机制的影响.结果如所示.
| 图 7 数据重复率对查询性能的影响fig.7 the effect of data repetition on performance |
描述的是数据重复率对系统的查询性能的影响, 横坐标表示数据表各列的平均数据重复率, 纵坐标表示查询响应时间.可观察到随数据重复率的增长, 原行存储机制的查询响应时间几乎无变化, 而列存储机制的查询响应时间不断地降低, 两者响应时间的差距逐渐增大; 当数据重复率达到99.9%时, 原行存储机制的查询响应时间是列存储机制的1.59倍.这验证了本文2.3节的结论:数据重复率是影响两种存储方式数据访问代价差异的主要因素之一; 随着数据重复率提高, 列存储机制的性能优势越大.因此, 该机制更适合于数据重复率较高的场景中.
5 结语随着各行各业数据规模和分析需求的增长, 数据库面向olap应用的查询性能越来越受到重视.本文基于读写分离架构的分布式数据库cedar, 设计了一种列存储机制, 分析了其适用场景, 并在cedar中实现了该机制.通过实验证明, 本文所设计的列存储机制能够有效地提升cedar的分析处理性能, 并且对事务处理的性能影响极低; 在查询请求涉及列数较少、各列中数据重复率较高的场景下, 该机制对查询性能提升的效果越显著.但本文的列存储机制仍有更深入优化的空间, 如缓存、延迟物化、基于代价的查询执行策略及面向新硬件的查询优化将会成为未来研究的重点.
参考文献
| [1] | codd e f, codd s b, salley c t. providing olap (on-line analytical processing) to user-analysts:an it mandate[j]. |
| [2] | 华东师范大学.面向大型银行应用的高通量可伸缩分布式数据库系统cedar[db/ol].[2018-05-16]. . |
| [3] | copeland g p, khoshafian s n. a decomposition storage model[c]//acm sigmod international conference on management of data. new york: acm, 1985: 268-279. |
| [4] | abadi d, madden s, hachem n, column-stores vs. row-stores: how different are they really?//proceedings of the 2008 acm sigmod international conference on management of data. new york: acm, 2008: 967-980. |
| [5] | raman v, attaluri g, barber r, et al. db2 with blu acceleration:so much more than just a column store[j]. |
| [6] | petraki e, idreos s, manegold s. holistic indexing in main-memory column-stores[c]//acm sigmod international conference on management of data. new york: acm, 2015: 1153-1166. |
| [7] | lang h, funke f, boncz p a, et al. data blocks: hybrid oltp and olap on compressed storage using both vectorization and compilation[c]//international conference on management of data. new york: acm, 2016: 311-326. |
| [8] | ramnarayan j, mozafari b, wale s, et al. snappydata: a hybrid transactional analytical store built on spark[c]//international conference on management of data. new york: acm, 2016: 2153-2156. |
| [9] | lee j, han w s, na h j, et al. parallel replication across formats for scaling out mixed oltp/olap workloads in main-memory databases[j]. the vldb journal, 2018, 27(3): 421-444. |
| [10] | sqream. sqream sqream db[db/ol].[2018-06-16]. . |
| [11] | root c, mostak t. mapd: a gpu-powered big data analytics and visualization platform[c]//proceeding of the siggraph'16 acm siggraph 2016 talks. new york: acm, 2016: article no 73. doi: . |
| [12] | 阳振坤. oceanbase关系数据库架构[j]. |
| [13] | 黄贵, 庄明强. oceanbase分布式存储引擎[j]. |
| [14] | google. google snappy[db/ol].[2018-06-16]. . |
| [15] | salomon d. data compression:the complete reference[m]. new york: springer-verlag inc, 2000. |
| [16] | apache. apache parquet[db/ol].[2018-06-16]. . |