第一章 绪论
1.1 研究背景与意义
随着云计算的迅速发展，如何处理和挖掘由社会网络、生物信息学、电子商务和医疗保健等广泛应用程序生成的大型数据集已成为一个日益重要且具有挑战性的问题。为了便于大数据分析，业界涌现出了许多大数据分析框架（Big Data Analytics Frameworks，
BDAFS）来执行并行数据处理。例如 Hadoop MapReduce[1,2]和 Spark[3,4]。由于这些框架旨在支持各种类型的应用，它们向用户提供了越来越多的配置参数进行适配。例如，Spark 作为一个流行的云计算大数据分析框架，有超过 180 个配置参数[2]，这些配置参数的设置往往对应用性能有着决定性的作用。
大量的配置参数导致配置优化问题的复杂性不断增加，给用户、开发人员和管理员带来了极大的负担[5]。先前的研究[6]表明，用户往往采用默认配置运行应用程序。然而，不同的应用程序需要设置与自身特征相符的配置参数，才能提升性能，默认配置往往导致性能不佳。为了降低运行成本，人工调优方法在工业上得到了广泛的应用，但是参数的优化需要工作人员对 BDAFS 及其应用有深入的了解，而且非常繁琐和耗时。因此，有必要寻找自动调整给定 BDAFS 和应用程序配置参数的方法，以获得最佳性能。
目前，自动化优化配置的一种简单方法是尝试各种参数组合，根据性能表现选择最佳配置，然而由于参数搜索空间巨大，参数组合很多，这种方法是不现实的。另一类方法通过建立一个基于领域知识的分析模型来预测和优化 BDAFS 的性能。这些分析模型是基于过度简化的 BDAFS 假设[7]，而且由于 BDAFS 在不断演化，当拥有新特性或者发布新版本时，往往需要重新分析。同时，另一类基于学习的方法由于将应用性能看作一个受配置参数影响的黑盒函数，屏蔽了 BDAF 的内部复杂性，具有优异的性能表现和适用性，最近受到了广泛关注。然而，由于以下两个挑战，BDAFS 的自动配置调优仍然非常困难，是一个值得深入研究的问题。
.....................
1.2 国内外研究现状
配置参数优化问题是云计算研究和开发领域中最重要的问题之一，近十几年来被广泛关注。目前已经有很多方法被提出，这些方法大致可以被分为 4 种，包括基于模型的优化方法、基于仿真的优化方法、基于搜索的优化方法和基于学习的优化方法。
基于模型的优化方法，是通过待调优系统的先验领域知识构建一个性能分析模型，然后通过此模型预测和优化系统其中 Starfish[8-11]为从简单到任意复杂的 MapReduce程序引入了一个基于成本的优化器，关注这些程序的配置参数空间中存在的优化可能性。在数据量较小的情况下，通过分析器详细收集 MapReduce 程序运行中的统计信息，然后使用一个细粒度的成本估计引擎来计算实际数据量下的运行时间。
Predator[12]不将优化问题视为纯粹的黑盒问题，而是利用从 MapReduce 配置实践中获得的有用经验来帮助优化过程。优化器以配置到作业执行时间的关系为目标函数，根据 Hadoop MapReduce 参数的不同级别将其划分为不同的组，以缩小搜索空间。此外，优化算法利用子空间划分的思想来防止局部最优问题的发生，并通过降低在搜索空间中访问非期望点的概率来减少搜索时间。
其它诸如 MR-COF[13]等论文采用的都是这种基于模型方法。这种方法的优点是，因为依赖于对待调优系统的执行过程分析来进行优化，可以不用通过实验获取样本。缺点是，对于高度复杂的系统，尤其是像大数据分析框架这样与硬件资源等高度相关的系统，难以准确地分析系统的运行时特征。
.......................
第二章 相关理论与技术
2.1 随机森林
Leo Breiman[33]吸收了 Amit 和 Geman[34]的早期工作，提出了随机森林方法。随机森林是 Geman 提出的 bagging 思想的一种延伸，与 boosting 方法互为竞争对手。它既可以用于分类，也可用于回归。同时，输入变量既可以是连续变量，也可以是枚举变量。
随机森林方法应用了集成学习理论，集成学习就是通过使用多个数学模型进行学习，每个数学模型可以采用相同或者不同的学习方法，得到输入变量与目标的关系，然后通过某种特定的规则整合多个模型，从而综合利用每种学习方法的优点，得到比单个数学模型模拟更好的结果。顾名思义，在随机森林方法中，数学模型就是决策树，它是由多个决策树组成的模型，且各个决策树之间没有关联。
随机森林包含了一系列决策树，每个决策树都是一个相对简单的模型，由根节点、中间节点、叶子节点组成，根节点包含了用于训练的样本全集，其中中间节点为一个判断条件，包含了满足从根节点到此节点的路径上所有节点的判断条件的样本，叶子节点即是分类或回归的结果。预测的过程就是根据输入，从根节点开始根据逻辑原理“IF-THEN”判断选择哪条路径到达下层节点，递归进行直至到达叶子节点获得目标值。
随机森林的建立过程其实本质上是建立不同决策树的过程，整个过程由行、列采样两部分组成。其中行采样的含义是，假设训练集中的样本个数为 N，采用有放回采样的方式重复多次抽样获得 N 个样本集合，作为一个决策树的输入数据，这样得到的集合中会有重复，但保证了每颗决策树使用的不是全部样本，且每棵树使用的样本各不相同。列采样的意思是假设一个样本有 M 个输入变量，每个节点都随机选择其中 m 个变量(m << M)。决策树利用这 m 个变量来确定节点的最佳分裂点，并进行最大可能地生长，而不进行剪枝，最终通过所有决策树的决策结果来预测新的输入样本。其中，在分类问题中，采用多数投票方式来决定分类结果。在回归时，输出所有结果平均值。
.........................
2.2 拉丁超立方抽样
拉丁超立方抽样是一种由 Mckay[35]等人发明的均匀采样方法，Ronald L. Iman 等人[36]进一步发展了该方法。LHS 可用于生成输入值以估计输出变量函数的期望值，经过一系列的研究证明，拉丁超立方体采样能比简单随机采样更详尽地探索模型参数空间。
拉丁超立方体抽样可以被看作是一个折衷的过程，它融合了随机抽样和分层抽样的许多理想特征，并且比随机抽样产生更稳定的分析结果。与随机抽样和分层抽样一样，拉丁超立方体抽样是一种概率过程，即一个权重可以与概率计算中使用的每个样本元素相关联。与随机抽样一样，拉丁超立方体抽样比分层抽样更容易实现，因为不需要确定每层和每层的概率。然而，拉丁超立方体抽样确实具有在自变量元素的每个元素范围内密集分层的特性，这一特性更接近分层抽样的特性。因此，拉丁超立方体抽样显示了随机抽样（不涉及分层）和分层抽样（在参数空间上分层）之间的特性。
拉丁超立方体抽样的关键是根据每个输入变量的概率分布函数进行分层，确保每层具有相同的概率和整个参数空间的每一部分都会被采样。为了保证每一个输入变量的各区间都会被均匀采样，通常把变量取值范围划分为 k 个区间，每个区间的概率为1/k。这样整个参数空间被划分为一个个概率相等的空间，空间内的随机一点即为采样样本。
简单的说就是，假设对一个 n 维参数空间进行采样，从中获得 k 个样本。该抽样方法具体执行步骤如下：
（1）将每一个参数取值范围分成互不重叠的 k 个区间，保证每个区间都具有相同的概率（如果每一维都是均匀分布，则每个区间的长度相同）。
（2）在每一个参数的每一个区间中随机抽取一个点，得到 n*k 个点。
（3）每一个参数不放回抽取任意一个区间的点，组成向量。重复 k 次，得到 k个 n 维向量。
..............................
3.1 性能预测与优化问题分析 ................................................ 15
3.2 性能预测与优化问题定义 ............................................. 16
3.3 性能预测与优化问题概述 .................................... 17
第四章 性能预测与优化方法实现 ....................................... 27
4.1 性能预测与优化方法介绍 ................................. 27
4.2 Testbed 构建方法 ............................................ 28
4.3 性能预测模型 .................................... 29
第五章 实验结果与分析 ...................................... 39
5.1 实验环境与过程 .......................................... 39
5.1.1 实验环境 ............................................... 39
5.1.2 实验评价指标 ........................................... 40
第五章 实验结果与分析
5.1 实验环境与过程
5.1.1 实验环境
本文拟采用一个主节点、五个从节点来搭建实验 Spark 集群，Spark 框架以内存计算作为优点，为了模拟实际生产环境，需要使用大内存的机器。因此，在阿里云这一公有云环境上进行实验，使用 6 个阿里云 ECS 实例（其中 1 个通用（g5）类型节点作为主节点，5 个内存（r5）类型节点作为从节点）。实验中主节点、从节点及软件版本如表 5.1、表 5.2 和表 5.3 所示。
.......................
第六章 总结与展望
6.1 工作总结
随着互联网的飞速发展，数据量不断增加，数据分析系统也越来越复杂。一个大数据框架如 Spark 通常拥有 100 多个配置参数用来控制应用程序的行为，并且往往对应用程序性能有着决定性影响。但通常用户不具备大数据框架的领域知识，结合应用程序的特征和框架的特性来设置配置参数，往往采用默认配置。因此如何自动优化Spark 配置参数，提升应用程序性能，减少时间成本是亟待解决的问题。
基于这样的背景，本文查询了国内外相关的研究成果，对大数据分析框架的配置参数优化问题进行了深入的研究与探讨，提出了一种自动化优化配置参数的工具AutoTune。在考虑了实际应用场景下优化时间限制和高维参数搜索空间的前提下，提出了与实际环境受配置影响相同的 Testbed 环境构建方法和广泛覆盖搜索空间的优化算法，从而实现了高效地自动化配置优化。本文具体包含的工作有以下几个方面：
（1）分析和定义了 Spark 框架性能预测与优化问题，并对问题进行数学建模。先详细定义了影响 Spark 应用程序的相关因素，确定变量和不变量等约束条件，最后对该问题进行数学建模，将约束、目标函数等用数学表达式表达出来，同时确定了待优化配置参数空间。
（2）设计并实现了一个 Testbed 构建方法，用来解决由于实际应用场景下存在优化时间限制，无法进行过多次数搜索或者获取训练样本的问题。通过在小规模，但是足够精确地捕获实际生产环境受配置影响的 Testbed 环境下，运行缩减了输入数据量的应用，可以获得更多的训练样本，提高性能预测模型的准确性。
（3）提出了一个结合机器学习算法和搜索算法的迭代式参数优化算法。通过采用探索策略，使用拉丁超立方体采样算法来保证在高维参数搜索空间上的搜索样本的广泛性。通过开发策略，使用参数缩减算法不断地减小搜索范围，寻找局部最优解。迭代过程中不断优化随机森林模型，预测不同配置下性能表现，指导探索和开发过程。
（4）通过实验检验本文提出的 Testbed 构建方法和性能预测与优化算法。实验验证主要包括两部分，首先使用 nDCG 指标比较相同时间下 Testbed 和实际生产环境下训练得到的机器学习模型的准确性。然后分别使用参数优化算法与其它 5 种优化算法搜寻最佳配置，比较其优化结果。
参考文献(略)