云计算环境下的容错并行Skyline查询算法研究  

Fault-Tolerant Parallel Skyline Computation in Cloud Computing Environment

作　　者：王媛[1] 王意洁[1] 邓瑞鹏[1] 裴晓强[1] 

机构地区：[1]国防科学技术大学计算机学院并行与分布处理国防科技重点实验室,长沙410073

出　　处：《计算机科学与探索》2011年第9期804-814,共11页Journal of Frontiers of Computer Science and Technology

基　　金：国家自然科学基金No.60873215;国家重点基础研究发展规划(973)No.2011CB302601;湖南省自然科学杰出青年基金No.S2010J5050;高等学校博士学科点专项科研基金No.200899980003~~

摘　　要：云计算为分布并行Skyline查询提供强大存储能力和计算能力的同时,其大规模数据中心固有的故障频发特性给可靠Skyline查询处理带来极大挑战。现有研究致力于提高Skyline算法的响应时间、渐进性、负载均衡等各项性能,不能保证故障情况下查询继续正确执行。为此,提出一种容错并行Skyline查询算法(fault-tolerant parallel Skyline,FTPS)。该算法通过故障监测和任务迁移,使得能够在查询过程中及时发现故障,并将故障节点的计算任务迁移到副本节点,保证查询的正确执行。理论分析和实验证明,FTPS算法能够在不影响正常Skyline查询处理性能的情况下获取较好的容错处理性能。Cloud computing provides great opportunities for distributed and parallel Skyline query in large multidimensional datasets. Simultaneously, the inherent high frequency of failures in large-scale datacenters posts new challenges to query reliability. Existing researches focus on improving the response time, progressiveness and load balancing, etc. of Skyline algorithms, but they become disabled in the presence of failures. To solve this problem, this paper proposes a fault-tolerant parallel Skyline algorithm （FTPS）. With failures detection and tasks migration, FTPS can detect failures quickly and migrate the computation tasks to a duplicate node. When failures happen, the query processing is also guaranteed. Theoretical analysis and extensive experiments prove that FTPS performs well in fault-tolerance without deteriorating other performances of Skyline query.

关 键 词：SKYLINE查询 分布并行计算 云计算 数据中心 容错 

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