Journal of Frontiers of Computer Science and Technology ›› 2011, Vol. 5 ›› Issue (09): 804-814.

• 学术研究 • Previous Articles     Next Articles

Fault-Tolerant Parallel Skyline Computation in Cloud Computing Environment

WANG Yuan, WANG Yijie, DENG Ruipeng, PEI Xiaoqiang   

  1. National Key Laboratory for Parallel and Distributed Processing, College of Computer Science, National University of Defense Technology, Changsha 410073, China
  • Received:1900-01-01 Revised:1900-01-01 Online:2011-09-01 Published:2011-09-01

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

王 媛, 王意洁, 邓瑞鹏, 裴晓强   

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

Abstract: Cloud computing provides great opportunities for distributed and parallel Skyline query in large multi- dimensional 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.

Key words: Skyline query, distributed and parallel computing, cloud computing, data center, fault-tolerance

摘要: 云计算为分布并行Skyline查询提供强大存储能力和计算能力的同时, 其大规模数据中心固有的故障频发特性给可靠Skyline查询处理带来极大挑战。现有研究致力于提高Skyline算法的响应时间、渐进性、负载均衡等各项性能, 不能保证故障情况下查询继续正确执行。为此, 提出一种容错并行Skyline查询算法(fault-tolerant parallel Skyline, FTPS)。该算法通过故障监测和任务迁移, 使得能够在查询过程中及时发现故障, 并将故障节点的计算任务迁移到副本节点, 保证查询的正确执行。理论分析和实验证明, FTPS算法能够在不影响正常Skyline查询处理性能的情况下获取较好的容错处理性能。

关键词: Skyline查询, 分布并行计算, 云计算, 数据中心, 容错