基于众包工作流的多用户协同whaT-if分析工具的研究和实现

摘要

随着计算机网络与数据库技术的迅速发展和广泛应用，商业智能系统中的分析型处理（OLAP）在各种商业领域中扮演越来越重要的角色。随着数据处理技术在企业的成功应用，传统的OLAP数据分析操作（对数据进行聚集、汇总、切片和旋转等）已经不能适应当前大数据量、深度分析的需要，因而需要路径分析、时间序列分析、图分析、what-if分析等复杂的统计分析模型。
　　其中what-if分析是基于历史数据，对假设场景进行分析的重要手段，它可以为决策者提供重要的预测信息，是一种非常重要的决策支持分析过程，也是OLAP的深入应用之一。
　　但是随着大数据时代的来临，传统OLAP技术遇到了前所未有的挑战，已经无法胜任大数据分析的要求。目前，大数据OLAP系统均是以MapReduce的计算模型为依托的，但MapReduce的优势在于以批处理模式处理大数据集，在实时响应需求方面效率仍有待提高。在what-if分析处理中，delta表合并算法是最关键的一步，但传统的delta表合并算法在这种新的计算模型下，时间和空间上都受到严重制约。所以这种基于历史数据的应用场景假设分析需要更加有效的what-if数据视图生成机制的支持。
　　同时，随着OLAP的不断发展和企业级业务的需求变化，what-if分析已经很难由单一的用户独立完成，而是需要不同部门、不同层次用户的协同处理，而且处理过程也可能是分阶段来进行的。因此，在what-if分析中就需要多用户的协同处理机制的支持，并通过不同用户之间的协同来完成企业级决策的假设分析。
　　因此，本文针对大数据、多用户环境下what-if查询处理策略进行了研究，主要工作包括:
　　(1)在传统的delta表合并算法的基础上，提出了基于Bloom Filter和Distributed Cache两种改进方法以提高在大数据OLAP系统中what-if数据视图的生成性能，从而提高what-if的查询处理能力。在标准SSB数据集上与Hive进行对比的实验表明，基于Bloom Filter的what-if算法比在Hive上实现的效率提高了30％，而当delta表较小时，基于Distributed Cache的what-if算法的性能提高幅度更大。
　　(2)由于MapReduce本身适用于以批处理模式处理大数据集，过多的产生中间数据会增加磁盘IO的次数，影响了算法的效率。因此，本文将各what-if分析算法移植到Spark环境下，作为一个内存计算框架，Spark使用内存替代了HDFS存储中间结果，因此可以大大减少磁盘IO的次数，从而提升算法的效率。基于标准SSB测试数据集上的性能分析与实验结果表明，基于BloomFilter的算法和基于Distributed Cache算法，在性能上较于MapReduce中都有了大幅度的提高。
　　(3)针对what-if分析中需要多用户的协同处理，提出使用众包工作流的机制。为此提出了基于回溯式PDS的众包工作流算法和基于反馈式PDS的众包工作流算法。这两种算法都可以在不同用户之间的协作下对what-if分析目标进行业务上的分解，并采用预合并多版本假设数据更新的算法，将分解后的众多子delta表汇总生成最终的delta表，实现从业务逻辑到假设数据更新的转换。但不同的是，基于回溯式PDS的众包工作流算法在任务无法被完成时可以重新对任务进行分解，保证最终解决方案的正确性和可行性，但过多的回溯过程将会造成时空资源的浪费，所以又提出了基于反馈式PDS的众包工作流算法作为补充，牺牲部分任务的完成度来换取时空效率的提升。基于以上算法，本文设计实现了众包工作流，给出了Delta表生成算法的运行情况示例，结果显示众包工作流可以合理的分解what-if分析目标，并最终形成可以被what-if算法使用的delta表。

目录

声明

摘要

第一章 引言

1．1 研究背景

1．2 研究现状

1．2．1 what-if查询处理策略

1．2．2 大数据下的what-if查询处理策略

1．2．3 多版本what-if分析数据合并策略

1．2．4 众包及众包工作流的应用现状

1．2．5 what-if分析工具现状

1．3 研究内容

1．4 论文组织结构

第二章 相关技术介绍

2．1 决策支持与what-if分析

2．2 Hadoop

2．2．1 MapReduce思想

2．2．2 Hadoop项目背景

2．2．3 Hadoop架构

2．2．4 Hadoop应用技术

2．3 Hive

2．3．1 Hive相关背景

2．3．2 HiveQL

2．3．3 Hive内部相关实现

2．4 Spark

2．4．1 Spark体系框架

2．4．2 弹性分布式数据集

2．4．3 Spark的运行机理

2．5 本章小结

第三章 大数据OLAP系统下的what-if查询处理策略

3．1 相关定义

3．2 基于BloomFilter_delta合并的what-if算法

3．2．1 Bloom Filter

3．2．2 LeftBDM算法

3．2．3 BloomFilter_delta合并算法

3．3 基于DistributedCache_delta合并的what-if算法

3．4 Spark环境下的what-if算法

3．5 实验结果与分析

3．5 Spark环境下的实验与分析

3．6 本章小结

第四章 基于众包工作流的Delta表生成算法的设计与实现

4．1 Delta表的生成

4．2 众包工作流

4．2．2 PDS(price-divide-solve)算法

4．3 基于众包工作流的delta表生成算法

4．3．1 众包分层

4．3．2 基于回溯式PDS的众包工作流算法

4．3．3 基于反馈式PDS的众包工作流算法

4．4 多版本Delta表合并

4．4 众包工作流的运行与测试

4．4．1 实验环境与案例

4．4．2 众包工作流运行示例

4．4 本章小结

第五章 总结与展望

5．1 总结

5．2 未来工作

致谢

参考文献