面向大规模机群的可扩展OLAP查询技术  

Scalable OLAP Queries Processing Towards Large Cluster

作　　者：王会举[1,2] 覃雄派[1,2] 王珊[1,2] 张延松[3] 李芙蓉[1,2] 

机构地区：[1]数据工程与知识工程教育部重点实验室(中国人民大学),北京1008722 [2]中国人民大学信息学院,北京100872 [3]中国人民大学中国调查与数据中心,北京100872

出　　处：《计算机学报》2015年第1期45-58,共14页Chinese Journal of Computers

基　　金：国家"九七三"重点基础研究发展规划项目基金(2014CB340403);国家重大科技专项基金(核高基项目2010ZX01042-001-002);国家自然科学基金(61170013;61272138);中国人民大学科学研究基金(中央高校基本科研业务费专项资金(10XNI018))资助~~

摘　　要：大数据时代,由中低端硬件组成的大规模机群逐渐成为海量数据处理的主流平台之一.然而传统基于高端硬件平台设计的并行OLAP查询算法并不适应这种由不可靠计算单元组成的大规模并行计算的环境.为改善其在新计算环境下的的扩展性和容错性,该文对传统数据仓库的数据组织模式及处理模式进行改造,提出了全新的无连接雪花模型和TRM执行模型.无连接雪花模型基于层次编码技术,将维表层次等关键信息压缩进事实表,使得事实表可以独立处理数据,从数据模型层保证了数据计算的独立性;TRM执行模型将OLAP查询的处理抽象为Transform、Reduce、Merge 3个操作,使得OLAP查询可被划分为众多可并行执行的独立子任务,从执行层保证了系统的高度可扩展特性.在性能优化方面,该文提出了Scan-index扫描和跳跃式扫描算法,以尽可能地减少I/O访问操作;设计了并行谓词判断、批量谓词判断等优化算法,以加速本地计算速度.实验表明:LaScOLAP原型可以获得较好的扩展性和容错性,其性能比HadoopDB高出一个数量级.In big data era,a large computer cluster composed of low-end servers has become one of the most popular platforms for massive data analysis.While traditional OLAP query processing algorithms that are implemented on high-end servers don＇t adapt to the large and less reliable parallel computation environment.To improve its scalability and fault tolerance,we modified the conventional data schema and processing style of data warehouse,and proposed join-free snowflake（JFSS）and TRM execution model.Based on hierarchy encoding,JFSS schema compresses dimension hierarchies＇ information into fact table,which gives a fact table the ability of processing data independently without dimension tables,and ensures the computation independence of data from schema level.TRM execution model abstracts all data warehouse processing into three operations：Transform,Reduce and Merge（TRM execution model）,and divides an OLAP query into massive independent tasks,which ensures the large scalability and fault tolerance of the system from execution level.To optimize the performance,we proposed Scan-index algorithmand jump scan algorithm to reduce I/Os as much as possible,and designed batch evaluation of predicates algorithm,parallel evaluation of predicates algorithm etc.,to accelerate the processing speed of each data node.Experimental results show that,the prototype system,LaScOLAP yields high scalability and fault tolerance,and its performance is an order of magnitude higher than HadoopDB.

关 键 词：大规模可扩展 OLAP查询 无连接雪花模型 TRM执行模型 跳跃式扫描 Scan-index 大数据 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]