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

论文摘要

Skyline查询作为解决多目标优化问题的一种有效手段,在多标准决策和用户偏好查询等诸多领域中有着广泛应用。然而,随着人类可以采集和利用的数据信息的急剧增长,使得如何处理海量数据的Skyline查询成为急需解决的问题。云计算为海量数据的查询处理提供了强大的计算能力和存储能力,能够有效解决海量数据的Skyline查询问题。然而,云计算环境下数据中心的故障频发问题为并行查询处理提出了严峻挑战。故障的发生不仅影响查询结果的正确性,而且会由于大量计算任务的撤销而浪费计算资源和严重影响用户的查询体验。当前分布并行Skyline查询研究主要关注于算法的响应时间、渐进性和负载均衡等性能,并未充分考虑故障发生后的容错查询处理问题。为此,对基于水平数据划分和基于垂直数据划分的分布式数据集上的容错并行Skyline查询问题进行了深入的研究。首先,针对基于水平数据划分的主-从式分布并行Skyline查询算法中参与者节点的故障问题,提出了一种基于水平数据划分的主-从式容错并行Skyline查询算法MsFTPS-Hpd。该算法中,为每个参与者分别维护k个独立的数据副本。协调者接收用户提交的查询请求后,首先将查询请求转发给各参与者,然后等待各参与者返回局部Skyline,并周期性地向各参与者发送心跳检测消息;参与者收到协调者转发的查询请求后开始独立并行地计算局部Skyline,并且每计算出δ个Skyline数据点就保存一次中间结果至可靠节点,当参与者计算结束后,将局部Skyline返回给协调者;协调者收齐各参与者的局部Skyline以后重新计算Skyline,所得结果即为全局Skyline。MsFTPS-Hpd算法要求参与者应答收到的心跳检测消息,如果协调者发送至某参与者的心跳检测消息在规定时间内得不到应答,则表明该参与者发生故障,此时由协调者将故障参与者的计算任务迁移到副本节点,并恢复正常查询处理。理论分析和实验结果表明,MsFTPS-Hpd算法不仅能够以较小的数据传输量为代价获得较好的容错处理能力,而且在故障节点数增多时仍然能够保持比较快速稳定的查询响应时间。其次,针对基于水平数据划分的主-从式分布并行Skyline查询算法中协调者的性能瓶颈问题和故障问题,提出了基于水平数据划分的全分布式容错并行Skyline查询算法FDFTPS-Hpd。该算法摒除了协调者的使用,各参与者地位对等且可以相互直接通信。用户将查询请求提交给任意一个参与者,并由该参与者将查询请求转发给所有其他参与者;各参与者收到查询请求后独立并行地计算局部Skyline并对本地计算结果按照数据点支配能力排序;各参与者结束本地处理后,迭代地选择本地最优的k个Skyline数据点与所有其他参与者交换并互相剪枝,直到所有参与者的局部Skyline数据集为空时迭代结束;迭代结束后各参与者都获得了完整的全局Skyline,由最先完成计算的参与者向用户返回最终结果。FDFTPS-Hpd算法利用各参与者互为数据备份并相互监测状态。各参与者周期性地向自己负责的若干个参与者发送心跳检测消息并要求应答,如果发送给某参与者的心跳检测消息超过规定时间仍未得到应答,则表明该参与者发生故障。由于每个参与者都由k个参与者负责监测,故规定某参与者故障后,由率先发现其故障的参与者接替其计算任务,并恢复正常处理。理论分析和实验结果表明,对于基于水平数据划分的分布式数据集上的并行Skyline查询问题,FDFTPS-Hpd算法不仅能够高效实现容错并行查询,而且相对于主-从式分布并行Skyline查询算法,其查询响应时间和查询效率更优。最后,针对当前基于垂直数据划分的分布式Skyline查询算法中无法支持容错并行Skyline查询的问题,提出了基于垂直数据划分的容错并行Skyline查询算法FTPS-Vpd。该算法中,为每个节点分别维护k个独立的数据副本。master接收用户发起的查询请求后,首先将查询请求转发给各slave,然后周期性地向各slave发送心跳检测消息并等待各slave返回局部Skyline;各slave收到查询请求后将本地存储的那一维度数据划分成均等的d份（d为数据集维数）,每个slave分别负责其中一个数据子集的局部Skyline计算任务;局部Skyline计算过程中slave每隔一段时间保存一次中间结果至可靠节点,计算结束后将局部Skyline返回给master;master收齐所有局部Skyline后重新计算Skyline,所得结果即为全局Skyline。FTPS-Vpd算法要求slave应答收到的心跳检测消息,如果master发送给某slave的心跳检测消息超过规定时间仍未得到应答,则表明该slave发生故障,此时由master将故障slave的计算任务迁移到副本节点,并恢复正常查询处理。理论分析和实验结果证明,FTPS-Vpd算法相对于现有基于垂直数据划分的分布式Skyline查询算法,不仅具有较强的容错查询能力,而且有效地优化了查询响应时间和查询效率。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景和意义
• 1.2 Skyline 查询
• 1.2.1 Skyline 查询定义
• 1.2.2 Skyline 查询特点
• 1.2.3 Skyline 查询分类
• 1.3 云计算概述
• 1.4 数据中心故障分析
• 1.5 容错技术
• 1.6 主要研究内容
• 1.7 论文组织结构
• 第二章 相关研究
• 2.1 集中式Skyline 查询
• 2.2 分布并行Skyline 查询
• 2.2.1 基于水平数据划分的分布并行Skyline 查询
• 2.2.2 基于垂直数据划分的分布并行Skyline 查询
• 2.3 容错查询处理
• 2.4 本章小结
• 第三章 基于水平数据划分的主-从式容错并行Skyline 查询算法研究
• 3.1 数据副本放置及选择策略
• 3.1.1 数据副本放置策略
• 3.1.2 数据副本选择策略
• 3.1.3 实例分析
• 3.2 基于水平数据划分的主-从式容错并行Skyline 查询算法
• 3.2.1 Baseline 算法
• 3.2.2 MsFTPS-Hpd 算法
• 3.3 实验结果与分析
• 3.3.1 结果保存周期δ对算法性能的影响
• 3.3.2 无故障情况下的算法性能
• 3.3.3 单个节点故障情况下的算法性能
• 3.3.4 多个节点故障情况下的算法性能
• 3.4 本章小结
• 第四章 基于水平数据划分的全分布式容错并行Skyline 查询算法研究
• 4.1 基于水平数据划分的全分布式并行Skyline 查询算法
• 4.1.1 Nav?e 算法
• 4.1.2 FDPS-Hpd 算法
• 4.2 基于水平数据划分的全分布式容错并行Skyline 查询算法
• 4.2.1 数据副本维护
• 4.2.2 FDFTPS-Hpd 算法
• 4.3 实验与结果分析
• 4.3.1 不同k 值对算法性能的影响
• 4.3.2 无故障情况下的算法性能
• 4.3.3 单个节点故障情况下的算法性能
• 4.3.4 多个节点故障情况下的算法性能
• 4.4 本章小结
• 第五章 基于垂直数据划分的容错并行Skyline 查询算法研究
• 5.1 基于垂直数据划分的分布并行Skyline 查询算法
• 5.2 基于垂直数据划分的容错并行Skyline 查询算法
• 5.3 实验与结果分析
• 5.3.1 无故障情况下的算法性能
• 5.3.2 单个节点故障情况下的算法性能
• 5.3.3 多个节点故障情况下的算法性能
• 5.4 本章小结
• 第六章 结束语
• 6.1 研究工作总结
• 6.2 未来工作展望
• 致谢
• 参考文献
• 作者在学期间取得的学术成果
• 作者在学期间参加的科研项目