数据库系统参数调优方法综述

曹蓉; 鲍亮; 崔江涛; 李辉; 周恒

doi:10.7544/issn1000-1239.202110976

数据库系统参数调优方法综述

曹蓉¹,
鲍亮^1,,
崔江涛^1,,
李辉^1,,
周恒^2,

1.
西安电子科技大学计算机科学与技术学院　西安　710071
2.
浪潮集团有限公司　济南　250014

基金项目: 国家自然科学基金项目（62172316）；教育部人文社会科学研究项目（17YJA790047）；陕西省软科学研究计划项目（2020KRZ018）；陕西省哲学社会科学重大理论与现实问题研究项目（20JZ-25）；陕西省重点研发计划项目（2019ZDLGY13-03-02）；陕西省自然科学基金项目（2019JM-368）；河北省重点研发计划项目（20310102D）

详细信息

作者简介:
曹蓉: 1992年生. 博士研究生. 主要研究方向为参数优化和机器学习

鲍亮: 1981年生. 博士，副教授，博士生导师. 主要研究方向为软件体系结构、云计算和大数据

崔江涛: 1975年生. 博士，教授，博士生导师. CCF杰出会员. 主要研究方向为数据与知识工程、数据安全和高维索引技术

李辉: 1983年生. 博士，教授，博士生导师. CCF高级会员. 主要研究方向为数据挖掘、知识管理与发现、大数据的隐私保护查询与分析

周恒: 1977年生. 硕士，高级工程师. 主要研究方向为数据库理论和数据挖掘

中图分类号: TP392
计量
- 文章访问数: 526
- HTML全文浏览量: 65
- PDF下载量: 174
出版历程
- 收稿日期: 2021-09-29
- 修回日期: 2022-02-22
- 网络出版日期: 2023-02-26
- 刊出日期: 2023-02-28

Survey of Approaches to Parameter Tuning for Database Systems

1.
School of Computer Science and Technology, Xidian University, Xi’an 710071
2.
Inspur Group Co., Ltd., Jinan 250014

Funds: This work was supported by the National Natural Science Foundation of China (62172316), the Ministry of Education Humanities and Social Science Project of China (17YJA790047), the Soft Science Research Plans of Shaanxi Province (2020KRZ018), the Research Project on Major Theoretical and Practical Problems of Philosophy and Social Sciences in Shaanxi Province (20JZ-25), the Key Research and Development Program of Shaanxi Province (2019ZDLGY13-03-02), the Natural Science Foundation of Shaanxi Province (2019JM-368), and the Key Research and Development Program of Hebei Province (20310102D).

摘要

摘要:
数据库系统具有大量的配置参数，参数配置不同会导致系统运行时很大的性能差异. 参数优化技术通过选择合适的参数配置，能够提升数据库对当前场景的适应性，因此得到国内外研究人员的广泛关注. 通过对现有的数据库参数调优方法进行总结分析，根据参数优化方法是否具有应对环境变化的能力，将现有工作分为固定环境下的数据库参数优化方法和变化环境下的数据库参数优化方法2类. 对于固定环境下的参数优化方法，按照方法是否具有从历史任务中学习的能力将研究工作分为传统的参数优化方法和基于机器学习的参数优化方法2类并分别进行介绍. 对于变化环境下的参数优化方法，按照不同的变化场景对现有工作进行分类介绍. 最后，总结了现有工作中各类方法的优缺点，并对目前研究中待解决的问题和可能发展的方向进行了讨论.
- 数据库系统 /
- 参数调优 /
- 性能调优 /
- 机器学习 /
- 自治数据库
Abstract:
Database systems contain a vast number of configuration parameters controlling nearly all aspects of runtime operation. Different parameter settings may lead to different performance values. Parameter tuning can improve the adaptability of database to current environment by selecting appropriate parameter settings. However, parameter tuning faces several challenges. The first challenge is the complexity of parameter space, while the second is the insufficient samples caused by the expensive performance measurements. Moreover, the optimal parameter configuration is not universal when the environment changes. Therefore, regular users and even expert administrators grapple with understanding and tuning configuration parameters to achieve good performance. We summarize and analyze the existing work on parameter tuning for database systems and classify them into two categories: tuning approaches under fixed environments and tuning approaches under changed enviroments, according to whether the approaches have the ability to cope with environmental changes. For the first one, the research work is divided into traditional parameter tuning and machine learning-based parameter tuning according to whether the approaches can learn from historical tasks. For the second one, the existing approaches are introduced according to different environmental change scenarios, respectively. Finally, we summarize the pros and cons of various approaches and discuss some open research problems for parameter tuning.
- database systems /
- parameter tuning /
- performance tuning /
- machine learning /
- self-driving database

HTML全文

开放最短路径优先（open shortest path first, OSPF）^[1]协议和中间系统到中间系统（intermediate system to intermediate system, IS-IS）协议是互联网目前使用的2个典型的域内路由协议^[2]，这2个协议采用最短路径将报文从源地址转发到目的地址. 在OSPF和IS-IS中，每个路由器通过交互链路状态通告获得整个网络的拓扑结构，然后该路由器通过迪杰斯特拉算法计算以自身为根的最短路径树，最后该路由器根据最短路径树构造出自己的路由表. 当网络出现故障时，OSPF和IS-IS采用重新收敛机制来应对网路中的故障. 但是研究表明^[3-5]，它们的重新收敛时间大概在几秒甚至几十秒左右，在路由协议重新收敛的过程中受这些故障影响的报文将会被丢弃，严重影响了网络的性能，大大降低了用户的体验. 互联网部署的实时应用对网络的收敛时间提出了更高的要求^[6-8]. 传统的路由协议无法满足实时应用对网络收敛时间的要求^[9]. 为此，业界提出利用路由保护算法来解决此问题，研究表明路由保护算法^[10]可以大大降低由于故障造成的网络中断时间，显著减少报文丢失.

在已有的路由保护算法中，最经典的方法是IP快速重路由（IP fast rerouting, IPFRR）^[11]，该算法可以选择事先计算好的备份下一跳绕过故障，从而降低由于故障造成的报文丢失率. 与最短路径路由相比，IPFRR有明显的优点：可以立即重新转发数据包，而不是等待路由重新收敛（通常为几秒甚至几十秒），从而避免在路由重新收敛阶段出现路由环路和数据包丢失问题^[12].

路由保护算法最核心的技术是如何为每个结点计算到达目的结点的无环路备份下一跳. 下游规则（downstream criterion, DC）^[13]是一种经典的无环路计算规则，该规则选择距目的地址更近的邻居结点作为备份下一跳. 以目的结点构造有向无环图（directed acyclic graph, DAG），也可以计算出无环路备份下一跳. 基于最大邻接顺序的最大可选择性路由算法（maximum alternative routing algorithm, MARA）^[14]的核心思想就是将网络拓扑转换为DAG. 但是文献[13-14]算法和网络拓扑结构密切相关，在某些拓扑结构中故障保护率较低. 在DAG图中，每条链路仅有1个方向，这个要求大大降低了结点可以计算出无环路备份下一跳的可能性. JNHOR-SP（shortest path compatible Joker-capable next hop optimality routing）^[15]利用路由结点排序和Joker链路来提高DAG图的故障保护率，网络中的Joker链路具有2个方向，但是由于计算Joker链路算法的缺陷，JNHOR-SP平均仅能提供95%左右的故障保护率. 基于报文入端口的无环路路由（loop free inport-dependent, LFID）^[16]通过扩展DAG，将部分链路修改为双向链路，从而同时解决网络故障和网络拥塞问题，但是LFID的故障保护率为88.9% ~ 98.2%. Not-Via^[17]和段路由^[18]（segment routing, SR）可以保护网络所有可能的单故障，但是二者需要借助辅助机制的协助，在实际中部署比较困难.

已有的路由保护算法存在4个方面的问题：1）无法应对网络中所有可能的单故障情形；2）需要额外辅助机制的协助；3）不支持增量部署；4）需要存储多个备份下一跳. 我们拟设计一个路由算法，该算法满足4个要求：1）每个路由器存储2个下一跳，其中一个为最优下一跳，另外一个为备份下一跳；2）可以应对网络中所有可能出现的单故障情形；3）不需要额外辅助机制的协助；4）支持增量部署. 基于此本文提出了一个满足这4个要求的基于转发图的域内路由保护算法（an intra-domain routing protection algorithm based on forwarding graph, RPBFG）. 受JNHOR-SP和LFID这2个算法的启发，本文通过构造转发图来解决DAG图故障保护率较低的问题. 在转发图中，每条链路可能存在2个方向，这将明显提高故障保护率. 与JNHOR-SP和LFID不同的是，RPBFG可以提供100%故障保护率. 我们将在后面的章节中详细介绍什么是转发图，如何构造转发图，如何利用转发图计算无环路备份下一跳.

本文的主要贡献包括4个方面：

1）提出了以最大化故障保护率为目标，转发图包含反向最短路径树为约束条件的路由保护算法模型RPBFG.

2）针对提出的路由保护算法模型，首先提出了利用RPBFG解决快速构造转发图的算法，然后利用转发图为每个结点计算唯一一个备份下一跳.

3） RPBFG是对当前链路状态路由协议的扩展，不会改变路由协议报文的交互过程. RPBFG需要的数据都可以从链路状态路由协议中获得，唯一的变化是路由计算部分，因此RPBFG支持增量部署.

4）在11个真实网络拓扑中进行了实验，实验结果表明RPBFG不仅可以支持100%的单故障保护，而且具有较小的路径拉伸度.

根据这4点贡献的描述可知RPBFG可以应对网络中所有可能的单故障情形，不需要额外辅助机制的协助，支持增量部署，每个结点存储唯一一个到达目的地址的备份下一跳. 因此RPBFG可以解决文中描述的已有路由保护算法存在的4个问题.

1. 相关工作

已有研究^[19]证实，互联网中每天都会出现大量的网络故障. 为了应对互联网中频繁出现的故障，业界提出了路由保护算法^[20]，从而尽量降低由于故障造成的损失. 根据报文在转发过程中是否需要辅助机制的协助，可以将路由保护算法分为2类：第1类不需要借助辅助转发机制；第2类需要借助辅助转发机制.

第1类路由保护算法主要包括等价多路径路由（equal cost multipath routing, ECMP）、无环路备选条件（loop-free alternates, LFA）、U-turn、MARA-MA、基于扩展最短路径的最大可选择性路由算法（maximum alternative routing algorithm-shortest path extension, MARA-SPE）等；第2类路由保护算法主要包括Not-Via、SR、多配置路由（multiple routing configuration, MRC）、报文携带故障（failure carrying packet, FCP）等. 第1类算法和目前使用的路由协议是兼容的，因此支持增量部署. 然而第2类路由保护算法需要对目前使用的路由协议进行修改，实现难度较大. 本文重点研究第1类路由保护算法，下面将分别介绍这类路由算法.

OSPF协议增加了对ECMP的支持，但是ECMP仅仅支持代价相同的最短路径，因此对提高路由可用性的贡献比较有限^[21]. 为了应对ECMP在解决路由可用性方面存在的问题，国际互联网工程任务组（Internet Engineering Task Force, IETF）提出了快速重路由的基本框架. LFA就是基于此框架提出的无环路路由. LFA包括3种应对故障的保护条件：链路保护条件（link protection condition, LPC）、结点保护条件（node protection condition, NPC）和DC. 文献[22-23]分别介绍了如何通过调整链路权值和修改网络拓扑结构提高LFA的故障保护率. U-turn^[24]将选择备份下一跳扩展到计算结点邻居的邻居，即如果计算结点的邻居没有满足无环路规则的下一跳，但是计算结点的邻居的邻居有满足无环路规则的下一跳，则该邻居可以作为计算结点的备份下一跳，因此U-turn可以进一步提高故障保护率. MARA-MA^[14]以最大化最小连通性为目标构造DAG，MARA-SPE^[14]和MARA-MA的目标是一致的，但是MARA-SPE的约束条件为DAG必须包含最短路径树.

文献[25]提出了基于Not-Via地址的快速重路由机制. 在该算法中，网络中的每条链路都有2个地址，一个是正常的IP地址，另一个Not-Via地址. 该机制使用Not-Via地址显示的说明网络中出现故障的结点或者链路，从而使报文避开该故障. 基于隧道的路由保护算法^[26]为所有源目的对计算中转隧道结点，然而并不是所有的结点对之间都存在中转结点. 基于SR^[14]的路由保护算法将网络的路径分成一个个的小段，然后为这些段和网络结点分配Segment Routing的ID，通过对这些 Segment Routing ID进行有序的排列，就可以生成一条完整的转发路径.

MRC^[27]通过改变网络中链路的代价计算出多个配置图，这些不同配置图可以应对网络中出现的不同故障，从而达到提高路由可用性的目的，但是MRC部署开销较大. FCP^[28]的核心思路为：首先将报文遇到的故障存放在其头部，然后根据该头部信息更新网络拓扑结构，最后利用新的网路拓扑结构计算新的最短路径. FCP可以应对网络中的单故障问题，但是该方法需要改变路由协议，部署难度较大.

表1列出了RPBFG和已有路由保护算法的链路状态路由协议，在支持逐跳转发和支持100%的单故障保护等方面进行比较.

表 1 路由保护算法的比较

Table 1. Comparison of Routing Protection Algorithms

算法	是否是链路状态路由协议	是否支持逐跳转发	是否支持100% 的单故障保护
OSPF^[1]	√	√	×
LFA^[11]	√	√	×
MARA-MA^[14]	√	√	×
MARA-SPE^[14]	√	√	×
JNHOR-SP^[15]	√	√	×
LFID^[16]	√	√	×
SR^[18]	×	×	√
U-turn^[24]	√	√	×
Not-Via^[25]	×	×	√
MRC^[27]	×	×	√
FCP^[28]	×	×	√
RPBFG （本文）	√	√	√

下载: 导出CSV

| 显示表格

1）链路状态路由协议. 每个路由器根据网络拓扑结构做出最终的路由决策.

2）支持逐跳转发. 每个路由器基于目标地址查找数据报的下一跳，转发过程不需要借助额外机制的协助.

3）支持100%的单故障保护. 当网络出现单故障时，只要网络依然保持链路，数据报就可以被正确转发到目的地址.

2. 基于转发图的网络模型和问题描述

本节首先定义了反向最短路径树、转发图、故障保护率和路径拉伸度，然后对基于转发图的路由保护算法进行了形式化的描述. 为了便于读者阅读，将文中使用的部分符号总结在表2中.

表 2 本文定义的符号

Table 2. Symbols Defined in Our paper

符号	含义
G=(V, E)	网络拓扑图
V	网络中结点（路由器）的集合
E	网络中边（链路）的集合
r(d)	目的地址为d的反向最短路径树
G(d)	目的地址为d的转发图
P（v, G(d)）	转发图G（d）的故障保护率
bestn(v, d)	结点v到结点d的最优下一跳
backn(v, d)	结点v到结点d的备份下一跳

下载: 导出CSV

| 显示表格

2.1 网络模型

本文使用无向图G=（V, E）来表示一个网络，其中V是无向图中的结点集合，代表网络中的路由器，E是无向图中的边集合，代表网络中的链路. 对于网络中的任意一个结点 $v \in V$ ，bestn（v, d）表示结点v到结点d的最优下一跳，backn（v, d）表示结点v到结点d的备份下一跳. 下面给出反向最短路径树、转发图、故障保护率和路径拉伸度的定义.

定义1. 反向最短路径树. 对于目的结点d，其余结点到目的结点d都具有最短路径的树. r（d）表示目的地址为d的反向最短路径树.

定义2. 转发图. 按照一定的规则遍历无环路的有向图. G（d）表示目的地址为d的转发图.

定义3. 在转发图G（d）中，对于任意的结点 $v \in V,v \ne d$ ，如果v到d的最优下一跳出现故障，v依然可以到达目的地址d，我们称在G（d）中结点v可以被保护，否则结点v未被保护.

定义4. 转发图G（d）的故障保护率可以表示为 $P(v,G(d)) = \dfrac{{\displaystyle\sum\limits_{v \in V} {f(v,d)} }}{{|V| - 1}}$ ，其中当结点v被保护时f（v, d）=1，否则f（v, d）=0.

定义5. 路径拉伸度. 当网络出现故障时，利用路由保护算法计算出的所有源目的对之间的代价总和与利用最短路径计算出的所有源目的对之间的代价总和的比值.

我们通过一个简单的例子解释上面的定义1~5. 图1表示网络拓扑结构，链路上的数字表示该链路对应的代价. 图2表示以结点d为根的反向最短路径树，实线表示在反向最短路径树中的边，从图2中可以计算出每个结点到目的结点d的最优下一跳. 例如，f到d的最优下一跳可以表示为bestn（f, d）=c, k到d的最优下一跳是bestn（k, d）=j. 图3是以d为目的地址的转发图，从图3中可以计算出每个结点到目的结点d的备份下一跳. 在图3中实线箭头表示结点的最优下一跳，空心箭头表示结点的备份下一跳. 例如，f到d的备份下一跳可以表示为backn（f, d）=e, k到d的备份下一跳可以表示为backn（k, d）=h. 转发图是如何构造出来的，为什么利用转发图可以计算出结点的备份下一跳将在后面的章节中详细介绍.

图 1 网络拓扑结构

Figure 1. Network topology structure

下载: 全尺寸图片幻灯片

图 2 反向最短路径树

Figure 2. Reverse shortest path tree

下载: 全尺寸图片幻灯片

图 3 转发图

Figure 3. Forwarding graph

下载: 全尺寸图片幻灯片

2.2 问题描述

为了解决已有路由保护算法存在的4个问题，我们形式化地描述了本文需要解决的科学问题. 在已知网络拓扑结构G=（V, E）的前提条件下，对于目的结点 $d \in V$ ，如何构造一组转发图G（d）包含反向最短路径树r（d），从而使得故障保护率最高. 该问题可以形式化表示为

$\mathrm{Maximize} \frac{{\displaystyle \sum _{d\in V}{\displaystyle \sum _{v\in V,v\ne d}P(v,G(d))}}}{\left|V\right|}，$

(1)

$\mathrm{s}.\mathrm{t}.\quad G(d) \supseteq r(d)，$

(2)

其中式（1）为目标函数，即最大化故障保护率；式（2）表示反向最短路径树属于转发图.

3. 转发算法

在构造转发图的过程中，需要解决2个关键问题：1）如何设计遍历算法，即转发算法；2）如何给转发图中链路设置方向，从而使得该转发图包含反向最短路径树.

3.1 转发算法规则

对于问题1我们采用互联网部署的路由转发算法，这样设计的算法和互联网是兼容的，便于实际部署. 我们对转发算法进行简单地描述：在网络中，当路由器收到一个报文后，就会根据报文中目的地址的信息从路由表中查找对应的下一跳，然后将该报文直接发送给对应的下一跳. 具体的转发规则为：

1）如果最优下一跳路由器发生了故障，就从备份路由表中查找备份下一跳，将报文发送给备份下一跳；

2）如果收到的报文来自最优下一跳，也将报文发送给备份下一跳；

3）其他情况均将报文发送给最优下一跳.

下面通过一个例子来解释转发算法. 在图3中，假设报文的源地址是c，目的地址是d，当结点a出现故障时，结点c将报文转发给备份下一跳f，结点f发现该报文来自于自己的最优下一跳c，因此结点f将报文发送给其备份下一跳e，接着结点e将报文转发给最优下一跳b，最后b将报文转发给目的地址d.

3.2 基于遗传算法构造转发图的算法

下面重点描述如何解决问题2. 给定目的地址d，构造G（d）就是为网络拓扑中的链路设定特定的方向. 其中G（d）包含r（d）的条件比较容易实现，只需要在反向最短路径树r（d）的基础上构造转发图即可. 如何保证构造的图是转发图成为本文研究的重点和难点. 构造转发图就是为网络中的链路指定方向，对于网络中的链路 $(u,v) \in E$ ，每条链路有4种状态：第1种状态是该链路不在转发图中；第2种状态是该链路的方向为 $u \to v$ ；第3种状态是该链路的方向为 $v \to u$ ；第4种状态是 $u \to v$ 和 $v \to u$ 都在转发图中，用 $v - u$ 来表示. 如果 $(u,v) \in r（d）$ ，假设链路的方向为 $u \to v$ ，则该链路的状态只有 $u \to v$ 和 $v - u$ 这2种可能性；反之假设链路的方向为 $v \to u$ ，则该链路的状态只有 $v \to u$ 和 $v - u$ 这2种可能性. 通过上述分析可知当链路 $(u,v) \in r（d）$ 时，该链路的状态有2种可能性；当 $(u,v) \notin r（d）$ ，则该链路的状态有4种可能性；对于一个包含|V|个结点、|E|条边的网络拓扑来讲，有|V|−1条链路在反向最短路径树上，|E|+|V|+1条链路不在反向最短路径树上，因此链路状态的数量为 ${2^{|V| - 1}} \times {4^{|E| - |V| + 1}} = {2^{2 \times |E| - |V| + 1}}$ ，如果把所有的链路状态的组合都枚举出来，然后从中选择符合条件的转发图，在实际网络中部署是一种不现实的解决方案.

为了解决该问题，本文提出利用遗传算法来构造转发图，该算法包含2个步骤：1）计算以结点d为根的反向最短路径树r（d）；2）在r（d）的基础上，利用遗传算法构造转发图.

算法1（RPBFG算法）描述了利用遗传算法构造转发图的过程. 算法的输入为网络拓扑结构G=（V, E），输出为每个结点的备份路由表. 下面以目的地址d为例进行描述.RPBFG主要通过3个步骤实现：首先对网络中的链路进行编码，在链路编码的基础上生成初始转发图；然后利用选择、交叉和变异操作计算出最优个体，根据选择的最优个体构造出最优转发图；最后根据最优转发图计算出所有结点的备份下一跳.

算法1. RPBFG算法.

输入：G=（V, E）；

输出：backn（v, d）， $v \in V,v \ne d$ .

① for each $v \in V,v \ne d$

② 　backup（v, d） $\leftarrow \varnothing$ ；

③ end for

④ compute r（d）；

⑤ population $\leftarrow$ InitPopulation（G, d）；

/* 利用r（d）生成初始种群*/

⑥ for each $i \in \{ 1,2,…,m\}$ /*算法迭代次数*/

⑦　remains $\leftarrow$ RouWheelSel（population）；

⑧　children $\leftarrow \varnothing$ ；

⑨　for each parentA $\in$ remains

⑩　　parentB $\in$ random_select_remains；

⑪　　child $\leftarrow$ Cross（parentA, parentB）；

⑫　　child $\leftarrow$ Mutate（child）；

⑬　　children $\leftarrow$ children $\cup$ {child}；

⑭　　population $\leftarrow$ children $\cup$ remains；

⑮　end for

⑯ end for

⑰ FG $\leftarrow$ ComputeFG（Best（population））；

⑱ for each $v \in V,v \ne d$

⑲　backup（v, d） $\leftarrow$ ComputeBackup（FG）；

⑳ end for

㉑ return backup（v, d）， $v \in V,v \ne d.$

在介绍RPBFG之前，我们描述链路编码的算法和适应度函数. 首先描述链路编码的算法. 对于网络中的链路 $(u,v) \in E$ ，用2位二进制编码来表示链路的状态：因此每条链路有4种状态：00表示该链路不在转发图中，01表示该链路的方向为 $u \to v$ ，10表示该链路的方向为 $v \to u$ ,11表示该链路的方向为 $v - u$ . 例如网络中有5条链路，分别是（a, b）,（b, c）,（c, d）,（a, d）,（b, d），如果对应的链路编码为（1001101101），则表示链路（a, b）的方向为 $a \to b$ ，链路（b, c）的方向为 $c \to b$ ，链路（c, d）的方向为 $c \to d$ ，链路（a, d）的方向为 $a \to d$ ，链路（b, d）的方向为 $d \to b$ . 然后描述适应度函数. 为了保证RPBFG在满足最大化故障保护率的同时，尽可能降低重路由路径的路径拉伸度，本文的适应度函数=故障保护率+0.001×路径拉伸度. 下面详细介绍算法RPBFG的执行过程，如算法1所示. 将备份下一跳集合初始化为空（行①~③）；对于网络中的结点 $d \in V$ ，利用迪杰斯特拉算法计算反向最短路径树r（d）（行④）. 行⑤表示生成初始化种群，本文利用r（d）生成初始种群，所有种群的规模数为N，所有初始种群的编码相同. 遗传算法的迭代过程中迭代次数为m（行⑥），在每次迭代中，利用轮盘赌算法^[29]进行选择操作，该算法根据个体的适应度和累计概率计算个体被选择的概率，轮盘赌选择中个体的适应度越好越有可能被保留，如果要保留n个个体，则在现有的2n个个体中进行n次有放回抽样，每次抽样中每个个体被抽中的概率为 $p_i ={{{f_i}}}\big/{{\displaystyle\sum\limits_{j = 1}^N {{f_j}} }}$ ，其中p_i表示该个体被保留的概率，f_i表示该个体的适应度， $\displaystyle\sum\limits_{j = 1}^N {{f_j}}$ 表示所有个体适应度之和（行⑦ ）. 行⑪和行⑫分别表示交叉和变异操作. 本文使用的交叉方法为多点交叉. 具体方法为：首先将要执行交叉的2个个体分别表示为A和B，然后随机选择若干个位置（每个位置被选择的概率是提前设置好的），将这些位置记为{i₁,i₂,…,i_n}，而后将A和B中的{i₁,i₂,…,i_n}位置上的基因相互交换. 算法1中使用2个位置的基因表示1条边的方向，所以在交叉互换的过程中将基因两两视为一个整体，以确保边的方向信息作为整体被交换.

本文采用的变异方法为：用变异率p表示基因变异的概率，当1个染色体发生变异时，它的每个基因都按照概率p发生变异，当某个位置的基因发生变异时，如果基因未变异概率为1，则基因概率变异为0，反之，如果基因未变异概率为0，则基因概率变异为1. 为了保证变异后的染色体所表示的转发图不产生路由环路，在每次变异后都会检查其是否产生了环路，如果这次变异导致了环路，那就将该基因还原. 需要注意的是，染色体中表示最短路径树中有向边的基因不会发生变异，因为这些基因表示的是最优下一跳. 当迭代部分执行完毕以后，根据最优个体Best（population）中链路的方向利用ComputeFG（Best（population））计算出转发图（行⑰）；然后利用该转发图为网络中的其他结点计算到达目的地址d的备份下一跳，为结点 $v \in V,v \ne d$ 计算备份下一跳的算法如下：遍历结点v的不是最优下一跳的邻居结点v，如果该边的编码为10或者11，则结点u可以将结点v作为备份下一跳（行⑱~⑳）. 当算法1执行完毕以后，返回所有结点到达目的结点d的备份下一跳集合（行㉑）.

下面分析算法的时间复杂度. 算法1的行①~③的时间复杂度为 $O(|V|)$ ，行④的时间复杂度为 $O(|V|\lg |V| + |E|)$ ，行⑤的时间复杂度为 $O(N)$ ，行⑥~⑯的时间复杂度为 $O(N \times m)$ ，行⑰的时间复杂度为 $O(|E|)$ ，行⑱~⑳的时间复杂度为 $O(|V|)$ ，RPBFG的总时间复杂度为 $O(|V|)$ + $O(|V|\lg |V| + |E|)$ + $O(N)$ + $O(N \times m)$ + $O(|E|)$ + $O(|V|)$ ，即 $O(|V|\lg |V| + 2|E|{\text{ + }}N \times m)$ .

4. 实验及结果分析

本节将RPBFG与NPC，U-turn，MARA-MA，MARA-SPE进行比较，采用Python实现这5种算法. 实验采用了11种真实的网络拓扑结构^[30]，如表3所示，使用真实拓扑结构使得实验结果更加真实准确. 实验采用的度量指标包括故障保护率和路径拉伸度. 故障保护率反映了算法应对网络中发生故障的能力，该值越大说明算法应对故障的能力越强. 路径拉伸度表示当网络出现故障以后，重路由路径的代价和最短路径的代价的比值，该值越小说明利用路由保护算法计算出的路径代价和利用最短路径计算出的路径代价接近，给网络带来的额外开销越低.

表 3 真实网络拓扑

Table 3. Real Network Topology

网络拓扑	结点的数量	边的数量
Abilene	11	14
Ans	17	24
Arpanet19719	18	22
Arpanet19723	24	27
Arpanet19728	29	32
AttMpls	25	56
Belnet2004	18	34
Cernet	14	16
Agis	16	21
NJLATA	11	23
USLD	28	45

下载: 导出CSV

| 显示表格

4.1 故障保护率

本节比较算法RPBFG，NPC，U-turn，MARA-MA，MARA-SPE的故障保护率. 图4描述了5种算法在11个真实网络拓扑图中的故障保护率. 在所有实验的网络拓扑结构中RPBFG的故障保护率均为1.0，NPC，U-turn，MARA-MA，MARA-SPE的故障保护率均低于1.0. 例如，在Abilene中，NPC，U-turn，MARA-MA，MARA-SPE对应的故障保护率分别是0.48 ，0.75， 0.85 ，0.88，在Arpanet 19728中， NPC，U-turn，MARA-MA，MARA-SPE对应的故障保护率分别是0.07，0.23 ，0.81 ，0.84. 这是因为NPC，U-turn，MARA-MA，MARA-SPE使用一定的规则计算备份下一跳，因为这些规则和网络拓扑结构密切相关，在某些网络拓扑结构中无法为所有的源目的结点对计算符合这些规则的备份下一跳. 而RPBFG与网络拓扑无关，只要网络中存在的路径可以到达目的地址，RPBFG就可以计算出相应的重路由路径.

图 4 不同算法在真实拓扑中的故障保护率

Figure 4. Failure protection ratio of different algorithms in real topologies

下载: 全尺寸图片幻灯片

4.2 路径拉伸度

在计算路径拉伸度的过程中，为了体现公平性，只考虑2个算法都能保护的路径. 具体计算算法为：算法A可以保护所有源目的结点对的集合 $\alpha$ ，算法B可以保护所有源目的结点对集合 $\beta$ ，这2个集合的交集 $C = \alpha \cap \beta$ 就是需要计算的源目的结点对集合. 表4列出了RPBFG和NPC的路径拉伸度的平均值和方差. 表5列出了RPBFG和U-turn的路径拉伸度的平均值和方差. 表6列出了RPBFG和MARA-MA的路径拉伸度的平均值和方差. 表7列出了RPBFG和MARA-SPE的路径拉伸度的平均值和方差. 从表4~7可以看出，RPBFG的路径拉伸度的平均值和方差几乎明显低于其余4种算法. 在平均路径拉伸度方面，RPBFG比NPC，U-turn，MARA-MA，MARA-SPE分别降低了0.11%，0.72%，37.79%，36.26%.

表 4 NPC和PBFG路径拉伸度比较结果

Table 4. Comparison Result of Path Stretch for NPC and RPBFG

网络拓扑	NPC		RPBFG（本文）
网络拓扑	平均值	方差	平均值	方差
Abilene	1.0042	0.0334	1.0027	0.0208
Ans	1.0019	0.0205	1.0015	0.0191
Arpanet19719	1.0008	0.0125	1.0006	0.0110
Arpanet19723	1.0002	0.0044	1.0001	0.0041
Arpanet19728	1.0000	0.0009	1.0000	0.0010
AttMpls	1.0029	0.0269	1.0004	0.0121
Belnet2004	1.0000	0.0000	1.0000	0.0000
Cernet	1.0000	0.0000	1.0000	0.0000
Agis	1.0012	0.0165	1.0020	0.0269
NJLATA	1.0068	0.0427	1.0002	0.0026
USLD	1.0034	0.0270	1.0018	0.0201

下载: 导出CSV

| 显示表格

表 5 U-turn和RPBFG路径拉伸度比较结果

Table 5. Comparison Result of Path Stretch for U-turn and RPBFG

网络拓扑	U-turn		RPBFG（本文）
网络拓扑	平均值	方差	平均值	方差
Abilene	1.0206	0.1077	1.0116	0.0677
Ans	1.0198	0.0971	1.0119	0.0736
Arpanet19719	1.0153	0.0768	1.0123	0.0689
Arpanet19723	1.0097	0.0558	1.0096	0.0562
Arpanet19728	1.0032	0.0309	1.0039	0.0408
AttMpls	1.0216	0.1573	1.0016	0.0258
Belnet2004	1.0079	0.0977	1.0000	0.0000
Cernet	1.0143	0.0877	1.0143	0.0877
Agis	1.0139	0.0871	1.0114	0.0727
NJLATA	1.0226	0.1237	1.0001	0.0022
USLD	1.0155	0.0806	1.0069	0.0469

下载: 导出CSV

| 显示表格

表 6 MARA-MA和RPBFG路径拉伸度比较结果

Table 6. Comparison Result of Path Stretch for MARA-MA and RPBFG

网络拓扑	MARA-MA		RPBFG（本文）
网络拓扑	平均值	方差	平均值	方差
Abilene	1.5751	1.3749	1.0124	0.0737
Ans	1.6528	1.1185	1.0083	0.0599
Arpanet19719	1.2989	0.5774	1.0189	0.0970
Arpanet19723	1.3634	0.7351	1.0188	0.0939
Arpanet19728	1.3767	0.8556	1.0311	0.1455
AttMpls	2.2332	1.1413	1.0018	0.0275
Belnet2004	1.2587	0.2752	1.0000	0.0000
Cernet	1.6748	1.3387	1.0136	0.0925
Agis	1.4022	0.6273	1.0080	0.0616
NJLATA	1.7628	0.8202	1.0003	0.0045
USLD	2.2750	1.9101	1.0058	0.0415

下载: 导出CSV

| 显示表格

表 7 MARA-SPE和RPBFG路径拉伸度比较结果

Table 7. Comparison Result of Path Stretch for MARA-SPE and RPBFG

网络拓扑	MARA-SPE		RPBFG（本文）
网络拓扑	平均值	方差	平均值	方差
Abilene	1.5687	1.0068	1.0247	0.1066
Ans	1.5604	1.0055	1.0098	0.0648
Arpanet19719	1.1971	0.4711	1.0124	0.0767
Arpanet19723	1.2304	0.4412	1.0209	0.0984
Arpanet19728	1.2754	0.7457	1.0280	0.1383
AttMpls	2.1765	1.0243	1.0024	0.0310
Belnet2004	1.3648	0.4243	1.0000	0.0000
Cernet	1.7156	1.4256	1.0134	0.0905
Agis	1.4858	0.7040	1.0110	0.0744
NJLATA	1.7442	0.8013	1.0003	0.0045
USLD	2.1411	1.6796	1.0056	0.0403

下载: 导出CSV

| 显示表格

5. 结　　论

为了应对网络中频繁出现的故障，本文提出了一种基于转发图的域内路由保护算法（RPBFG），该算法通过构造最优转发图应对网络故障. 与已有路由保护算法不同，RPBFG仅为每个结点存储1个备份下一跳，这样可以大大降低存储开销. 我们首先描述了需要解决的关键科学问题；然后理论分析直接求解的复杂度；接着采用遗传算法来解决提出的问题，从而降低求解的复杂度；最后在11个真实拓扑中对RPBFG的性能进行了测试. 仿真测试表明该算法可以应对网络中所有可能的单故障情形，并且具有较小的路径拉伸度. RPBFG是一种域内路由保护算法，在未来的工作中将研究如何将RPBFG的核心思想应用到域间路由保护算法中，从而进一步提高网络的可用性.

作者贡献声明：耿海军提出了算法思路和实验方案，并撰写论文；孟卓负责执行实验方案；姚珊珊参与实验方案指导和对部分实验结果分析；杨静参与论文校对和实验方案指导；池浩田提出了指导意见并修改论文；尹霞提出方法的指导意见和审核论文.

图 1 数据库系统参数优化问题示意图

Figure 1. Overview of parameter tuning problem for database systems

下载: 全尺寸图片幻灯片

图 2 OtterTune机器学习流程^[3]

Figure 2. OtterTune machine learning pipeline^[3]

下载: 全尺寸图片幻灯片

图 3 强化学习元素与参数优化的对应关系^[50]

Figure 3. The correspondence between reinforcement learning elements and parameter tuning^[50]

下载: 全尺寸图片幻灯片

表 1 基于机器学习的数据库系统参数优化与性能预测方法

Table 1 Machine Learning-Based Parameter Tuning and Performance Prediction Approaches for Database Systems

类别	方法	机器学习技术	训练难度	目标
基于传统机器学习技术	iTuned^[1]	高斯过程回归	☆	参数优化
	OtterTune^[3,41]	因子分析、k-means、Lasso、高斯过程回归	☆	参数优化
	Ishihara等人^[42]	高斯过程回归	☆	参数优化
	iBTune^[43]	深度神经网络	☆☆☆	参数优化
	Rodd等人^[44]	神经网络	☆☆☆	参数优化
	Zheng等人^[45]	神经网络	☆☆☆	参数优化
	ACTGAN^[46]	生成式对抗网络、Lasso	☆☆☆	参数优化
	Siegmund等人^[47]	逐步线性回归	☆	性能预测
	Nair等人^[48]	分类与回归树	☆	性能预测
	DeepPerf^[49]	深度前馈神经网络、Lasso	☆☆☆	性能预测
基于深度强化学习技术	CDBTune^[50]	DDPG	☆☆☆	参数优化
基于深度强化学习技术	QTune^[51]	DS-DDPG	☆☆☆	参数优化
注：☆表示训练难度级别.

下载: 导出CSV

表 2 变化环境下的数据库系统参数优化与性能预测方法

Table 2 Parameter Tuning and Performance Prediction Approaches for Database Systems Under Environmental Changes

类别	方法	特点	目标
工作负载变化	OtterTune^[3,41]	根据工作负载特征向量进行映射	参数优化
	D-OtterTune^[56]	动态负载匹配	参数优化
	Rafiki^[38]	在代理模型中包含工作负载特征和最具影响力的参数	参数优化
	SOPHIA^[57]	结合工作负载预测和成本效益分析器确定何时更改参数配置	参数优化
	OPTIMUSCLOUD^[58]	针对动态工作负载对数据库和云配置参数进行联合调优	参数联合优化
	Kossmann等人^[59]	同时考虑工作负载预测和运行时性能监视来及时确定调优点	参数优化
	Kossmann等人^[60]	基于组件的自治数据库系统框架	参数优化
软件版本变化	Mühlbauer等人^[61]	识别跨软件变体和系统版本的性能变化	性能预测
硬件配置变化	Valov等人^[62]	性能预测模型在不同硬件平台间的迁移	性能预测
多种环境变化	Jamshidi等人^[63]	重用源环境数据	性能预测
	ResTune^[64]	采用元学习策略来提取历史任务的调优经验	参数优化
	Jamshidi等人^[65]	不同的环境中存在不同形式的可迁移知识，有助于学习性能预测模型	性能预测
	Javidian等人^[66]	配置参数的因果影响可以在不同环境中以高可信度进行迁移	性能预测
	BEETLE^[67]	选择最合适的源环境（Bellwether环境）	参数优化

下载: 导出CSV

表 3 各种参数优化方法的对比评估

Table 3 Comparative Evaluation of the Various Approaches for Parameter Tuning

方法	复杂性	样本需求	动态变化性	精确性	通用性
手工参数优化方法	☆	☆☆	☆	☆☆	☆
基于规则的参数优化方法	☆	☆☆☆	☆	☆	☆
基于模型的参数优化方法	☆	☆☆☆	☆	☆☆	☆
基于搜索的参数优化方法	☆☆	☆☆	☆	☆	☆☆☆
基于传统机器学习的参数优化方法	☆☆	☆	☆	☆☆	☆☆☆
基于深度强化学习的参数优化方法	☆☆☆	☆☆	☆☆	☆☆☆	☆☆
变化环境下的数据库参数优化方法	☆☆☆	☆☆	☆☆☆	☆☆☆	☆☆
注：星号数量标识不同方法在5个方面的表现，星号越多表现越好.

下载: 导出CSV

参考文献(68)

[1]	Duan Songyun, Thummala V, Babu S. Tuning database configuration parameters with iTuned[J]. Proceedings of the VLDB Endowment, 2009, 2(1): 1246−1257 doi: 10.14778/1687627.1687767
[2]	Van Aken D. On automatic database management system tuning using machine learning[D]. Pittsburgh, PA: Carnegie Mellon University, 2021
[3]	Van Aken D, Pavlo A, Gordon G J, et al. Automatic database management system tuning through large-scale machine learning[C] //Proc of the 2017 ACM Int Conf on Management of Data. New York: ACM, 2017: 1009−1024
[4]	Xu Tianyin, Zhang Jiaqi, Huang Peng, et al. Do not blame users for misconfigurations[C] //Proc of the 24th ACM Symp on Operating Systems Principles. New York: ACM, 2013: 244−259
[5]	Babu S, Borisov N, Duan Songyun, et al. Automated experiment-driven management of (database) systems[C/OL] //Proc of the 12th Workshop on Hot Topics in Operating Systems (HotOS). New York: ACM, 2009 [2021-09-10]. https://www.usenix.org/legacy/event/hotos09/tech/full_papers/babu/babu.pdf
[6]	李国良, 周煊赫, 孙佶, 等. 基于机器学习的数据库技术综述[J], 计算机学报, 2020, 43(11): 2019−2049 Li Guoliang, Zhou Xuanhe, Sun Ji, et al. A survey of machine-learning-based database techniques[J]. Chinese Journal of Computers, 2020, 43(11): 2019−2049 (in Chinese)
[7]	Chaudhuri S. An overview of query optimization in relational systems[C] //Proc of the 17th ACM SIGACT-SIGMOD-SIGART Symp on Principles of Database Systems. New York: ACM, 1998: 34−43
[8]	Kossmann D. The state of the art in distributed query processing[J]. ACM Computing Surveys, 2000, 32(4): 422−469 doi: 10.1145/371578.371598
[9]	Lu Hongjun. Query Processing in Parallel Relational Database Systems[M]. Los Alamitos, CA: IEEE Computer Society Press, 1994
[10]	Herodotou H, Chen Yuxing, Lu Jiaheng. A survey on automatic parameter tuning for big data processing systems[J]. ACM Computing Surveys, 2020, 53(2): Article No. 43
[11]	Huang Changwu, Li Yuanxiang, Yao Xin. A survey of automatic parameter tuning methods for metaheuristics[J]. IEEE Transactions on Evolutionary Computation, 2019, 24(2): 201−216
[12]	柴茗珂,范举,杜小勇. 学习式数据库系统: 挑战与机遇[J]. 软件学报,2020,31(3):806−830 Chai Mingke, Fan Ju, Du Xiaoyong. Learnable database systems: Challenges and opportunities[J]. Journal of Software, 2020, 31(3): 806−830 (in Chinese)
[13]	孙路明,张少敏,姬涛,等. 人工智能赋能的数据管理技术研究[J]. 软件学报,2020,31(3):600−619 doi: 10.13328/j.cnki.jos.005909 Sun Luming, Zhang Shaomin, Ji Tao, et al. Survey of data management techniques powered by artificial intelligence[J]. Journal of Software, 2020, 31(3): 600−619 (in Chinese) doi: 10.13328/j.cnki.jos.005909
[14]	孟小峰,马超红,杨晨. 机器学习化数据库系统研究综述[J]. 计算机研究与发展,2019,56(9):1803−1820 doi: 10.7544/issn1000-1239.2019.20190446 Meng Xiaofeng, Ma Chaohong, Yang Chen. Survey on machine learning for database systems[J]. Journal of Computer Research and Development, 2019, 56(9): 1803−1820 (in Chinese) doi: 10.7544/issn1000-1239.2019.20190446
[15]	Costa R L C, Moreira J, Pintor P, et al. A survey on data-driven performance tuning for big data analytics platforms[J]. Big Data Research, 2021, 25: 100206
[16]	Lu Jiaheng, Chen Yuxing, Herodotou H, et al. Speedup your analytics: Automatic parameter tuning for databases and big data systems[J]. Proceedings of the VLDB Endowment, 2019, 12(12): 1970−1973 doi: 10.14778/3352063.3352112
[17]	Yan Zhengtong, Lu Jiaheng, Chainani N, et al. Workload-aware performance tuning for autonomous DBMSs[C] //Proc of the 37th IEEE Int Conf on Data Engineering (ICDE). Piscataway, NJ: IEEE, 2021: 2365−2368
[18]	Van Aken D, Yang Dongsheng, Brillard S, et al. An inquiry into machine learning-based automatic configuration tuning services on real-world database management systems[J]. Proceedings of the VLDB Endowment, 2021, 14(7): 1241−1253 doi: 10.14778/3450980.3450992
[19]	Renouard J. MySQLTuner [CP/OL]. (2014-02-22)[2021-06-08].https://github.com/major/MySQLTuner-perl
[20]	Oracle Corporation. Oracle database performance tuning guides [EB/OL]. 2014[2021-06-08]. https://docs.oracle.com/cd/E11882_01/server.112/e41573/toc.htm
[21]	International Business Machines Corporation. IBM tuning guides [EB/OL]. 2012[2021-06-08]. https://www.ibm.com/docs/en/control-center/6.1.2?topic=processor-tuning-database-server
[22]	Microsoft Corporation. Microsoft Azure SQL database tuning guides [EB/OL]. 2021[2021-09-13]. https://docs.microsoft.com/en-us/azure/sql-database/sql-database-automatic-tuning
[23]	Oracle Corporation. WebLogic database tuning [EB/OL]. 2018[2021-06-08].https://docs.oracle.com/cd/E13222_01/wls/docs92/perform/dbtune.html
[24]	Xu Tianyin, Jin Long, Fan Xuepeng, et al. Hey, you have given me too many knobs!: Understanding and dealing with over-designed configuration in system software[C] //Proc of the 10th Joint Meeting on Foundations of Software Engineering. New York: ACM, 2015: 307−319
[25]	Jin Dongpu, Qu Xiao, Cohen M B, et al. Configurations everywhere: Implications for testing and debugging in practice[C] //Proc of the 36th Int Conf on Software Engineering. New York: ACM, 2014: 215−224
[26]	Kwan E, Lightstone S, Storm A, et al. Automatic configuration for IBM DB2 universal database[R]. New York: IBM, 2002
[27]	Storm A J, Garcia-Arellano C, Lightstone S S, et al. Adaptive self-tuning memory in DB2[C] //Proc of the 32nd Int Conf on Very Large Data Bases. New York: ACM, 2006: 1081−1092
[28]	Tian Wenhu, Martin P, Powley W. Techniques for automatically sizing multiple buffer pools in DB2[C] //Proc of the 2003 Conf of the Centre for Advanced Studies on Collaborative Research. New York: ACM, 2003: 294−302
[29]	Dias K, Ramacher M, Shaft U, et al. Automatic performance diagnosis and tuning in Oracle[C/OL] //Proc of the 2nd Biennial Conf on Innovative Data Systems Research (CIDR). 2005: 84−94. [2021-07-14].https://database.cs.wisc.edu/cidr/cidr2005/papers/P07.pdf
[30]	Yagoub K, Belknap P, Dageville B, et al. Oracle’s SQL performance analyzer[J]. IEEE Data Engineering Bulletin, 2008, 31(1): 51−58
[31]	Belknap P, Dageville B, Dias K, et al. Self-tuning for SQL performance in Oracle database 11g[C] //Proc of the 25th IEEE Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2009: 1694−1700
[32]	Narayanan D, Thereska E, Ailamaki A. Continuous resource monitoring for self-predicting DBMS[C] //Proc of the 13th IEEE Int Symp on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems. Piscataway, NJ: IEEE, 2005: 239−248
[33]	Tran D N, Huynh P C, Tay Y C, et al. A new approach to dynamic self-tuning of database buffers[J]. ACM Transactions on Storage, 2008, 4(1): Article No. 3
[34]	Sullivan D G, Seltzer M I, Pfeffer A. Using probabilistic reasoning to automate software tuning[J]. ACM SIGMETRICS Performance Evaluation Review, 2004, 32(1): 404−405 doi: 10.1145/1012888.1005739
[35]	Yoon D Y, Niu Ning, Mozafari B. DBSherlock: A performance diagnostic tool for transactional databases[C] //Proc of the 2016 Int Conf on Management of Data. New York: ACM, 2016: 1599−1614
[36]	Wei Zhijie, Ding Zuohua, Hu Jueliang. Self-tuning performance of database systems based on fuzzy rules[C] //Proc of the 11th Int Conf on Fuzzy Systems and Knowledge Discovery (FSKD). Piscataway, NJ: IEEE, 2014: 194−198
[37]	Zhu Yuqing, Liu Jianxun, Guo Mengying, et al. BestConfig: Tapping the performance potential of systems via automatic configuration tuning[C]//Proc of the 8th Symp on Cloud Computing. New York: ACM, 2017: 338−350
[38]	Mahgoub A, Wood P, Ganesh S, et al. Rafiki: A middleware for parameter tuning of NoSQL datastores for dynamic metagenomics workloads[C] //Proc of the 18th ACM/IFIP/USENIX Middleware Conf. New York: ACM, 2017: 28−40
[39]	Debnath B K, Lilja D J, Mokbel M F. SARD: A statistical approach for ranking database tuning parameters[C] //Proc of the 24th IEEE Int Conf on Data Engineering Workshop. Piscataway, NJ: IEEE, 2008: 11−18
[40]	Lima M I V, de Farias V A E, Praciano F D B S, et al. Workload-aware parameter selection and performance prediction for in-memory databases[C/OL] //Proc of the 33rd SBC Brazilian Symp on Databases (SBBD). 2018: 169−180. [2021-08-01].https://sbbd.org.br/2018/wp-content/uploads/sites/5/2018/08/169-sbbd_2018-fp.pdf
[41]	Zhang Bohan, Aken D V, Wang J, et al. A demonstration of the ottertune automatic database management system tuning service[J]. Proceedings of the VLDB Endowment, 2018, 11(12): 1910−1913 doi: 10.14778/3229863.3236222
[42]	Ishihara Y, Shiba M. Dynamic configuration tuning of working database management systems[C] //Proc of the 2nd IEEE Global Conf on Life Sciences and Technologies (LifeTech). Piscataway, NJ: IEEE, 2020: 393−397
[43]	Tan Jian, Zhang Tieying, Li Feifei, et al. iBTune: Individualized buffer tuning for large-scale cloud databases[J]. Proceedings of the VLDB Endowment, 2019, 12(10): 1221−1234 doi: 10.14778/3339490.3339503
[44]	Rodd S F, Kulkarni U P. Adaptive tuning algorithm for performance tuning of database management system[J]. arXiv preprint, arXiv: 1005.0972, 2010
[45]	Zheng Chonghuan, Ding Zuohua, Hu Jieliang. Self-tuning performance of database systems with neural network[C] //Proc of the 10th Int Conf on Intelligent Computing: Intelligent Computing Theory. Berlin: Springer, 2014: 1−12
[46]	Bao Liang, Liu Xin, Wang Fangzheng, et al. ACTGAN: Automatic configuration tuning for software systems with generative adversarial networks[C] //Proc of the 34th IEEE/ACM Int Conf on Automated Software Engineering (ASE). Piscataway, NJ: IEEE, 2019: 465−476
[47]	Siegmund N, Grebhahn A, Apel S, et al. Performance-influence models for highly configurable systems[C] //Proc of the 10th Joint Meeting on Foundations of Software Engineering. New York: ACM, 2015: 284−294
[48]	Nair V, Menzies T, Siegmund N, et al. Using bad learners to find good configurations[C] //Proc of the 11th Joint Meeting on Foundations of Software Engineering. New York: ACM, 2017: 257−267
[49]	Ha H, Zhang Hongyu. DeepPerf: Performance prediction for configurable software with deep sparse neural network[C] //Proc of the 41st IEEE/ACM Int Conf on Software Engineering (ICSE). Piscataway, NJ: IEEE, 2019: 1095−1106
[50]	Zhang Ji, Liu Yu, Zhou Ke, et al. An end-to-end automatic cloud database tuning system using deep reinforcement learning[C] //Proc of the 2019 Int Conf on Management of Data. New York: ACM, 2019: 415−432
[51]	Li Guoliang, Zhou Xuanhe, Li Shifu, et al. QTune: A query-aware database tuning system with deep reinforcement learning[J]. Proceedings of the VLDB Endowment, 2019, 12(12): 2118−2130 doi: 10.14778/3352063.3352129
[52]	Tibshirani R. Regression shrinkage and selection via the Lasso[J]. Journal of the Royal Statistical Society:Series B (Methodological), 1996, 58(1): 267−288 doi: 10.1111/j.2517-6161.1996.tb02080.x
[53]	Rasmussen C E. Gaussian processes in machine learning[C] //Proc of the 2003 Summer School on Machine Learning. Berlin: Springer, 2003: 63−71
[54]	Lillicrap T P, Hunt J J, Pritzel A, et al. Continuous control with deep reinforcement learning[J]. arXiv preprint, arXiv: 1509.02971, 2015
[55]	Hasselt H. Double Q-learning[J]. Advances in Neural Information Processing Systems, 2010, 23: 2613−2621
[56]	沈忱,邰凌翔,彭煜玮. 面向自动参数调优的动态负载匹配方法[J]. 计算机应用,2021,41(3):657−661 Shen Chen, Tai Lingxiang, Peng Yuwei. Dynamic workload matching for automatic parameter tuning[J]. Journal of Computer Applications, 2021, 41(3): 657−661 (in Chinese)
[57]	Mahgoub A, Wood P, Medoff A, et al. SOPHIA: Online reconfiguration of clustered NoSQl databases for time-varying workloads[C] //Proc of the 2019 USENIX Annual Technical Conf (USENIX ATC’19). Berkeley, CA: USENIX Association, 2019: 223−240
[58]	Mahgoub A, Medoff A M, Kumar R, et al. OPTIMUSCLOUD: Heterogeneous configuration optimization for distributed databases in the cloud[C] //Proc of the 2020 USENIX Annual Technical Conf (USENIX ATC’20). Berkeley, CA: USENIX Association, 2020: 189−203
[59]	Kossmann J, Schlosser R. A framework for self-managing database systems[C] //Proc of the 35th IEEE Int Conf on Data Engineering Workshops (ICDEW). Piscataway, NJ: IEEE, 2019: 100−106
[60]	Kossmann J, Schlosser R. Self-driving database systems: A conceptual approach[J]. Distributed and Parallel Databases, 2020, 38(4): 795−817 doi: 10.1007/s10619-020-07288-w
[61]	Mühlbauer S, Apel S, Siegmund N. Identifying software performance changes across variants and versions[C] //Proc of the 35th IEEE/ACM Int Conf on Automated Software Engineering (ASE). Piscataway, NJ: IEEE, 2020: 611−622
[62]	Valov P, Petkovich J C, Guo Jianmei, et al. Transferring performance prediction models across different hardware platforms[C] //Proc of the 8th ACM/SPEC Int Conf on Performance Engineering. New York: ACM, 2017: 39−50
[63]	Jamshidi P, Velez M, Kästner C, et al. Transfer learning for improving model predictions in highly configurable software[C] //Proc of the 12th IEEE/ACM Int Symp on Software Engineering for Adaptive and Self-Managing Systems (SEAMS). Piscataway, NJ: IEEE, 2017: 31−41
[64]	Zhang Xinyi, Wu Hong, Chang Zhuo, et al. ResTune: Resource oriented tuning boosted by meta-learning for cloud databases[C] //Proc of the 2021 Int Conf on Management of Data. New York: ACM, 2021: 2102−2114
[65]	Jamshidi P, Siegmund N, Velez M, et al. Transfer learning for performance modeling of configurable systems: An exploratory analysis[C] //Proc of the 32nd IEEE/ACM Int Conf on Automated Software Engineering (ASE). Piscataway, NJ: IEEE, 2017: 497−508
[66]	Javidian M A, Jamshidi P, Valtorta M. Transfer learning for performance modeling of configurable systems: A causal analysis[J]. arXiv preprint, arXiv: 1902.10119, 2019
[67]	Krishna R, Nair V, Jamshidi P, et al. Whence to learn? Transferring knowledge in configurable systems using BEETLE[J]. IEEE Transactions on Software Engineering, 2021, 47(12): 2956−2972 doi: 10.1109/TSE.2020.2983927
[68]	Pavlo A, Angulo G, Arulraj J, et al. Self-driving database management systems[C/OL] //Proc of the 8th Biennial Conf on Innovative Data Systems Research (CIDR). 2017 [2021-07-01].https://15721.courses.cs.cmu.edu/spring2020/papers/27-selfdriving/p42-pavlo-cidr17.pdf