【学习分享】基于DDPG算法的PostgreSQL系统调优
1.背景2020年PG.Asian中，感谢来自 中兴李忠良老师 的分享：
[*]【2020PG亚洲大会】李忠良：基于强化学习的数据库智能调参最佳实践_哔哩哔哩_bilibili
视频讲解逻辑很清晰。为了更好的消化这个研究，专门写一篇文章来梳理和思考，也顺便分享给大家。
<hr/>2.知识背景
本节是写给没有任何强化学习基础的同学看的，篇幅略长，了解过RL的同学直接跳过即可。
2.1 强化学习与马尔可夫决策过程
本节快速了解一下强化学习是什么，以及他作为一个通用算法工具，可以解决哪些问题。
2.1 Markov Decision Progress（MDP）
介绍几个概念，快速了解什么是马尔可夫决策过程。
[*]马尔可夫性：系统的下一个状态https://www.zhihu.com/equation?tex=s_%7Bt%2B1%7D仅与当前状态https://www.zhihu.com/equation?tex=s_t有关，而与以前的状态无关。即：https://www.zhihu.com/equation?tex=%5C%5B+P%5Cleft%5Bs_%7Bt%2B1%7D%7Cs_t%5Cright%5D%3DP%5Cleft%5Bs_%7Bt%2B1%7D%7Cs_1%2C%5Ccdots+%2Cs_t%5Cright%5D+%5C%5D
[*]马尔可夫状态转移矩阵：https://www.zhihu.com/equation?tex=%5C%5B+P%3D%5Cleft%5B%5Cbegin%7Bmatrix%7D+P_%7B11%7D%26+%5Ccdots%26+P_%7B1n%7D%5C%5C+%5Cvdots%26+%5Cvdots%26+%5Cvdots%5C%5C+P_%7Bn1%7D%26+%5Ccdots%26+P_%7Bnn%7D%5C%5C+%5Cend%7Bmatrix%7D%5Cright%5D+%5C%5D，用来标记一个系统中，不同状态之间进行转移的概率。如果状态转移确定了，那么从某个状态出发后，基于转移概率，可能存在多条轨迹（即 多个 马尔可夫过程）。
[*]马尔可夫决策过程：由元组https://www.zhihu.com/equation?tex=%5Cleft%28S%2CA%2CP%2CR%2C%5Cgamma%5Cright%29描述。其中：https://www.zhihu.com/equation?tex=S为有限的状态集,https://www.zhihu.com/equation?tex=A为有限的动作集,https://www.zhihu.com/equation?tex=P为状态转移概率,https://www.zhihu.com/equation?tex=R为回报函数,https://www.zhihu.com/equation?tex=%5Cgamma+为折扣因子，用来计算累积回报。
[*]马尔可夫决策过程中，状态转移矩阵是包含当前时刻动作，以及执行当前时刻动作后从环境获得的回报的。即：https://www.zhihu.com/equation?tex=P_%7Bss%27%7D%5E%7Ba%7D%3DP%5Cleft%5BS_%7Bt%2B1%7D%3Ds%27%7CS_t%3Ds%2CA_t%3Da%5Cright%5D
<hr/>2.2 强化学习
举个最简单的例子
一个机器人（agent）在复杂的迷宫环境（env）中探索，探索的最终目标是找到一个出口。
机器人在环境中不停的执行动作，当前处于某个状态（st）。每次对环境执行动作（即 at）后都能从环境收获到一个反馈（到达终点 or 没到达终点，即 reward）。然后进入下一个状态 st+1。
st+1 是由 (st,at)决定的，或者说 从(st,at) 到 st+1的映射 是 env的一个不变属性。
那么强化学习要解决的问题是：让机器人学会这样一个策略——对于任意状态st，机器人都知道应该采取哪一个都工作at，从而到机器人到达终点时，获得的总奖励最多。即，学习一个从st到at的概率分布：https://www.zhihu.com/equation?tex=%5C%5B+%5Cpi%5Cleft%28a%7Cs%5Cright%29%3Dp%5Cleft%5BA_t%3Da%7CS_t%3Ds%5Cright%5D+%5C%5D(1.1)
2.2 DDPG算法的基本原理
DDPG算法是若干RL算法当中应用范围较广的一种。为了理解此处场景里为什么选用DDPG，先介绍一下业界几类常用的RL算法。
2.2.1 常见RL算法
从算法框架结构可以分为下述三种：Policy-Based & Value-Based & Actor-Critic Based
[*]Policy-Based
[*]典型算法：Policy-Gradients
[*]基础逻辑：学习这样一个映射关系 state ——> action distribution.
[*]等待一个episode完毕了，基于整个episode来回溯每个state时候采取的action。对于t时刻，基于st输出的动作分布at，比如（0.2,0.3,0.5）。如果当前apisode选择了概率为0.5的动作，则用从当前时刻开始的折扣后总回报来更新这个概率为0.5的动作，下次再次被选择的频率。（这背后有一个逻辑，如果折扣后的回报较大，那么这个动作被再次选择的概率就会变大；反之亦然）
[*]缺点：因为要回溯整个episode，因此无法每次都更新，需要整个episode结束后才可以更新
[*]优点：天生可以学习 连续动作空间下的state ——> action distribution 映射关系，输出是一个分布，比如高斯分布
[*]Value-Based ：
[*]典型算法：DQN
[*]基础逻辑：学习这样一个映射关系（state，action）——> value，即 学习 执行每个动作的预期收益是多少，Q(s,a)。
[*]Loss-Function：当前(state,action)的预测值，与 (state,action)的实际值的diff。其中， (state,action)的实际值 Q(st,a) 取决于 当前获得的reward 以及上一轮更新时候的 maxQ(st+1,at+1)
[*]在连续动作空间的问题场景中，＇不同动作＇变成了无限个动作，value-based方法的学习样本数量发生数量级膨胀，因此难以学习和收敛。
[*]每次执行动作后，都可以立刻获取reward们，并进行更新
[*]Actor-Critic Based
[*]典型算法：Actor-Critic，A3C
[*]背景：
[*]AC算法可以看作是DQN算法的一种扩展。DQN算法在选择动作并进行执行时，采取的是e-greedy策略。相比而言，还有一种潜在的更优策略是把 e-greedy策略 用参数化的模块进行替换。
[*]AC算法也可以看作是PG算法的扩展。PG算法的逻辑是：一条路走到黑，等待一个episode结束后，再回溯每一个state，并更新 状态到动作分布的映射。相比而言，一个更好的做法是有一个函数，能够在每次执行动作结束后，都给策略网络一个标量反馈（用来评估这个动作分布采样后的实际收益）。那么这个函数就是Q(s,t)。
[*]优点：可以单步更新，可以应用在离散&连续的动作空间
<hr/>从学习方式可以划分为：On-Policy & Off-Policy
基于 policy function 以及 value function进行更新时，待更新网络 和 与环境交互并获得样本的网络 是否一致，可以将学习策略分为 on-policy 以及off-policy
[*]On-Policy：当前epoch采集的样本对网络进行训练，完成训练后，进入下一个epoch时，丢弃上一时刻的样本。
[*]特点：
[*]不同epoch样本的重要性不同，用完丢弃的策略后给训练带来很大噪声
[*]部分场景中，整个episode结束后才会获得可用来训练的reward，因此整个网络的更新频率也不稳定
[*]收敛更快，但是不一定是最优解
[*]典型算法：
[*]A3C
[*]Off-Policy：data利用率相对较高，但是面临收敛和稳定性问题。
[*]特点：
[*]收敛慢，但是算法更加健壮，因为其数据来源多样随机，更加能够遍历系统的多个状态。
[*]典型算法：
[*]DQN
2.2.2 DDPG算法简介
Deep Deterministic Policy Gradient，即即深度确定性策略梯度算法：Hui Niu：【Typical RL 10】DDPG
具体参考上文（网上文章很多，不赘述），该算法几大要点如下：
[*]经验池回放技术
[*]能够在连续的动作空间进行学习
[*]针对每个actor函数和critic函数，都提供了两个网络（估计网络 和 现实网络）
Policy-FunctionValue-Function估计网络输出实时的动作，供智能体进行采样基于agent预测的动作，估计下个state的价值现实网络辅助更新value-network估计当前state的价值
[*]软更新策略（对比DQN的硬更新）
[*]actor输出动作，在采样前添加uo noise来实现探索（UO过程在时序上具备很好的相关性）
[*]能够输出连续的动作空间
<hr/>2.3 数据库系统的调优方案
之前也没系统性研究过这个topic，借这个机会好好学习一下。
数据库调优：通过调节参数，满足用户对数据库系统的性能期望。
问题背景：
[*]每次新业务上线都需要重新调优，人力成本巨大
[*]DBA仅能调节小部分容易理解的&直观影响性能的参数，部分与性能存在隐式关联的参数无法有效调节
[*]不同数据库系统直接的调优经验无法迁移（硬件切换/业务负载类型切换时，问题道理相似）
业务目标：通过自动调优技术，一方面减少DBA运维代价；另一方面，让性能和响应能力提升
主流调优技术：
技术类型核心优点缺点基于规则将人工经验沉淀为规则1.速度快
2.可解释性好3.稳定性好1.对环境和鲁棒性不好
2.得不到最优解基于参数搜索传统组合优化问题，如启发式探索，遗传算法等1.简单，稳定性好
2.不依赖于环境/人工经验1.每次都需要从0探索，无法复用历史经验，计算开销巨大
2.无法求解全局最优基于监督学习手工标注：（如workload特征、硬件环境特征等）—> 最优参数。然后利用监督学习算法进行求解1.模型训练好后，参数求解很快
2.对标准样本有独立同分布的特殊要求，实际中难实现1.监督数据难以获取
2.系统变化后，需要重新搜集数据并训练基于强化学习自监督1.能够从历史经验中进行学习
2.模型训练好后，参数推荐较快3.不需要样本相互独立，可以相互关联（而调参行为中，样本相互之间恰好带有时序性，做不到完全独立）1.需要仔细按照mdp进行建模
2.训练较慢3.思路介绍
3.1 如何将参数调优过程建模为MDP
数据库的调优过程：
MDP的关键要素：
[*]Agent：智能调参引擎
[*]Environent：数据库环境
[*]State：从数据库环境中采集的数据库 性能指标
[*]Action：智能调参引擎 输出的 数据库系统配置参数
[*]Reward：一般基于TPS 或者 请求的时延 来换算
3.2 算法描述
预测流程：
[*]启动数据库，然后加载一个业务负载。在加载负载前后，各采集一次数据库系统的状态。加载前后的状态差值，就是状态 st
[*]将 st 输入到策略网络中，即可得到动作分布 u(st)
[*]给u(st)中添加 ou noise，然后采样得到动作 at，即 数据库的配置
[*]将生成的配置加载到数据库环境，然后重启，再加载下一轮的业务负载，然后将数据库系统状态求差值，得到st+1
[*]rt = func(tps,latency)
[*]将样本(st,at,rt,st+1)存储到样本池
剩余算法完全套用DDPG即可
3.3 业务视角下的工程系统架构
iztune-agent：引擎客户端
pg-agent：从pg采集系统参数，并和iztune-agent进行交互
混合表征模块 ：feature = f(数据库当前配置，数据库当前性能参数)
奖励函数设计模块：视频没展开介绍具体的reward function
pg本身200+配置
[*]部分配置不适合做推荐（比如ip地址）
[*]基于lasso算法，按照配置参数对性能的影响进行排序
[*]结合dba人工意见，最后选择了12个参数
对比一下ottertune：14228：数据库自动调优工具-ottertune-论文笔记，大致思路是：先推荐一小部分参数没，再逐步推荐更多的参数。
4.总结
压测工具需要解耦：目前不同业务方使用这套系统，需要自行撰写压测脚本。
[*]自行生成合适的负载，应该是一个RL-Environment的重要特征
增加决策机制：推荐的参数不合适，直接上生产有风险。需要加一层决策机制，提供双保险。
5.个人思考
RL的工程落地研究 = MDP建模 + 场景特定的工程实现
OLTP系统的优化目标（尤其是基于云的架构）怎么定义，本身就是一个trade off的问题。
目前本文的研究中，reward function是既定的，意味着关于某种特定优化目标的潜在映射关系已经在embedding在了RL-Model当中。
但在更多情况下，非线性系统的多个优化目标之间如何组合（即reward-function如何设计），很多时候是不同业务场景下，业务方自行决策的。
这意味着，相比于把reward function通过训练embedding在模型中；还有一种潜在的设计模式，是将模型的学习目标也作为网络的一个重要输入。这种设计模式的收益是：模型可以更加适用于不同业务场景的负载，并具备一定的泛化能力。
关联参考：多目标强化学习。安利下自己的研究：Joint Critics Mechanism: A Universal Framework for Multi-targets Visual Navigation）
页:
[1]