VLDB 2024 OpAdviser

VLDB 2024 An Efficient Transfer Learning Based Configuration Adviser for Database Tuning

动机

评估配置需要资源和时间来运行工作负载，这是优化数据库时的主要成本。给定一个调优任务，搜索空间的构造和搜索优化器的选择是影响调优效率的主要因素。
虽然先前的研究试图通过选择重要的旋钮和开发高级搜索优化器，在实践中应用先前研究的调优系统来提高调优效率，但仍然存在以下问题和挑战：

1. 无效的大搜索空间

选择重要的knob可以加速调优过程。但是全局重要旋钮的静态选择并不适用于各种工作负载，而为了选择特定于工作负载的重要旋钮在之前的实践中需要在不同的配置上执行许多目标工作负载。不幸的是，这种方法是高成本的。
针对每个旋钮选择适当的值范围是有用的。这是因为探索默认范围的空间是资源密集型的，浪费了大量不可行区域的实验；并且有效的范围可能因为工作负载的不同而不同，手册中的默认值范围是广泛的，而不是针对特定的工作负载设置的。

2. 不同调优任务的固定搜索优化器

尽管存在各种的搜索优化器，但是没有一个搜索优化器可以主导所有的调优任务。简单的启发式方法不能捕获调优任务（tuning task）与不同优化器性能之间的关系，无法推荐最佳搜索优化器。

贡献

OpAdviser利用从之前调优任务中收集的历史数据和构建的bechmark数据来自动构建紧凑的搜索空间并为给定任务选择适当的搜索优化器。

• 通过从类似的历史任务中提取有前途的几何图形来获得workload-specific的重要旋钮及其有效范围（迁移学习）
• 捕获任务特征与候选优化器性能排名的关系来推荐合适的搜索优化器（数据驱动的方法）

结构总览

组件：

• controller 通过与终端用户和数据库实例交互来控制调优过程
• data repository 存储不同的调优任务的历史observations（${ \theta_j^i,f(\theta_j^i,w_i) }, i^{th}$任务，$w_i$目标调优任务），obsevations包含所有的可配置旋钮，保证其维度相同
• space constructor 生成一个紧凑的搜索空间
• optimizer adviser 选择最合适的搜索优化器
• configuration generator 生成最优的配置

工作流程

1. 用户提供调优目标，调优预算，数据库实例，目标工作负载，开始迭代调优
2. controller在云数据库上应用新的配置，执行工作负载并获得数据库性能
3. 存储observation到data repository
4. 使用目标和历史任务的observations，space constructor识别相似的任务并通过组合有希望的范围构建一个紧凑的搜索空间
5. optimizer adviser 分析搜索空间和历史观测，提取目标任务的meta-feature，输入meta-ranker（根据基准数据预训练获得）。meta-ranker预测optimizers的性能排名并推荐排名靠前的
6. 根据搜索空间和推荐的搜索优化器，在configuration generator推荐有希望的配置并传递到controller
7. 迭代2-6，直到预算耗尽，获得最优的配置，返回给用户

搜索空间的构建

为了识别出基于特定工作负载的重要旋钮和旋钮值范围，同时减少目标工作负载的运行，我们借助相似的历史任务，去获得紧凑的搜索空间。同时，该紧凑搜索空间是考虑任务相似性相应地动态调整区域，已避免对搜索空间的过度修剪。
输入：之前任务(source task)的观测，目标任务(target task)
输出：紧凑的目标搜索空间

相似任务识别

不同调优任务的历史观测值可以提供有价值的信息。这是由于相似的工作负载运行在不同的硬件环境下可能共享与硬件无关的旋钮的常见范围；不同的工作负载也可能共享相同的不好的搜索区域。因此，对于给定的目标任务，检查相似的历史任务可以揭示类似的有希望的区域。
本文用目标任务和源任务在不同配置下是否具有相似的性能排名（基于目标观测值的一致排名对比率_ratio of concordant ranking pairs_$S(i,t)$）来获得相似性。

$f^{‘}$:性能模型(在离线阶段用随机森林训练获得) ；$F(i,t)$表示目标任务和$w_i$源任务之间具有的一致排名对的数量；$H^t$表示目标任务下的observations数量
$F(i,t)$的计算：在目标任务的observation下，目标任务的性能和在$f^{‘}$预测的性能进行比较，获得排名一致的observation数量。
在每一次迭代中，计算数据资源库中的所有源任务与当前目标任务的相似度，过滤掉相似度s低于0.5的源任务。

有效区域提取

如何通过考虑源任务与目标任务的相似性来提取有效区域？
需要从第i个任务中提取到的最小的有意义的值范围G：
构建G：（1）当观测到的性能大于$f^i_b$，将该观测到的配置加入到G中；（2）当随机采样到的预测性能大于$f^i_b$，加入G

当目标任务与当前源任务相似度高的时候，$f^i_b$趋近于$f_{best}^i$，使得提取的区域紧凑；当当目标任务与当前源任务相似度低的时候，提取的区域大，防止对搜索空间的过度裁剪。

重要旋钮选择策略

基于历史观测，利用SHAP（通过解释配置之间的性能变化来衡量功能的重要性）识别重要的旋钮。丢弃仅仅表现具有负贡献的旋钮，其旋钮的有效范围设置为0。

多数加权表决

最后一步是生成目标搜索空间，包括重要的旋钮及其值范围。本文采用多数加权投票策略来汇总候选任务的建议。
对第i个任务分配一个与其目标任务相似度成正比的权重
选择重要旋钮：一个旋钮是否丢弃，取决于多数源任务是否同意。这种方法不需要设置重要旋钮的数量这个超参数。
确定旋钮的值范围：对每个保留的旋钮，枚举提取的有效范围，保留多数投票保留的部分。

进一步避免负迁移

1. 将目标任务作为选民，使用当前目标观测生成参考有效区域。在计算目选民的权重时，在未见过的配置上测试泛化能力。这种留一模型能够更好地泛化到未见过的配置。OpAdviser使用第四次迭代中的历史任务来暖启动空间建议，从第6次迭代开始引入目标模型。
   这一步可以解决当没有历史观测数据时的冷启动问题。例如，寻求优化自己的应用程序的小型终端用户在离线数据收集存在挑战，他们在开始调优的时候没有历史数据。当_target concordant ordering ratio_超过0.5的时候，OpAdviser通过基于目标观测提取有效区域来构建搜索空间。

2. 从所有的候选的任务中采集k个任务并不进行替换，而不是利用全部的任务。这为目标空间的生成增加随机性，避免陷入局部最优。

搜索优化器推荐

依赖于一般启发式方法进行搜索优化器的选择是有挑战且不可靠的。例如从GA转换到DDPG的迭代次数的确定是很复杂的。另外，启发式方法依赖于人类经验，这可能无法涵盖具有不同特征的各种调优任务。
本文提出一种数据驱动的方法，利用机器学习模型来调整任务选择。通过预训练模型，OpAdviser利用从不同优化器的运行历史中提取的知识，直接生成预测，而无需在当前任务上实际运行候选优化器。

元特征提取

对每个调优任务，提取以下元特征。这些元特征表征调优任务，并且可以影响不同搜索优化器的调优性能。

1. 空间特征

旋钮的数量，搜索空间的大小，连续型和离散型旋钮的比例

2. 响应面特征

响应面的差异主要来源于不同的工作负载和硬件环境。采用一个相似向量（包含当前的任务和之前每个任务的一致排名对的比例S(i,k)）

3. 调优过程特征

使用当前迭代次数作为特征

离线数据生成

训练模型，需要数据来演示不同候选优化器在特定条件下的表现，但是对所有潜在的调优任务执行详细的测试成本是高昂的。
本文采用主动学习技术来选择样本进行测试和标记，以用更少的测试工作来有效收集数据，并且获得相对重要的数据。
首先通过变换搜索空间和响应特征生成一组候选的调优任务；我们迭代选择不确定性最高的任务进行测试。例如使用主动学习指标classification margin，余量margin最小的样本代表最大的不确定性。
此过程持续进行，直到达到所需的决策裕度水平或测试预算耗尽。

元排名器构建

利用收集到的数据，我们继续构建学习模型，即元排名器（meta-ranker）
输入：任务的元特征，两个候选的搜索优化器
输出：在给定任务上候选优化器相对的表现排名

具体实现

本文采用的LambdaMART，使用梯度提升决策树，优化成对的损失函数，去捕捉不同调优场景下的优化器的相对性能

元排名器训练过程进行数据结构化，m表示元特征，$o_i$表示独热编码的候选优化器，I表示一个标识符，当$o_i$的性能超过$o_j$时，I为1，否则为0。

在线阶段

OpAdviser从目标任务提取元特征，和候选的一对优化器输入到元排名器，推荐排名靠前的优化器。

优点

这个方法能够考虑任务的特征去获得优化器的性能。与预测最佳优化器的直接分类模型相比，通过考虑成对性能可以提取更多信息。此外，与回归模型相比，meta-ranker仅需要优化器对之间的比较，并且可以更好地处理噪声数据和不同尺度的数据。

实验

• 使用吞吐量作为最大的目标，比较200次迭代（每个迭代中3分钟的压力测试）
• 4个工作负载：Sysbench (RO), Sysbench (WO), Sysbench (RW), Twitter
• 候选的优化器：MBO, SMAC, DDPG, GA
• 数据存储库：为meta-ranker生成训练数据，通过调整调优旋钮产生390个不同的空间，变换9个工作负载，一共生成3510调优任务。从中标记48个任务，记录在不同的调优迭代和4个候选优化器下的性能观测。为了保证比较的公平，将保留数据存储库中存在的目标工作负载的任何观察结果。

比较

与LlamaTune、Hunter、DB-BERT、ResTune、OtterTune、CDBTune、SMAC比较，OpAdviser能够在一半的调优预算中实现相同的最优的吞吐量。

开销分析

在离线训练阶段，一个任务的表及过程消耗2400分钟（4x200x3，一次迭代3分钟压力测试，一共200次迭代）。标记48个调优任务，一共花费20天（4个数据库实例并行）
在线阶段，OpAdviser虽然在算法上需要更多的时间（秒级别），但是借助历史任务观测构建一个紧凑的搜索空间，能够识别具有较少目标工作负载运行的更好配置。

泛化性分析

在不同数据大小和硬件设置下，实验OpAdviser的性能