QoS感知调度Paragon核心思想
这次介绍的论文来自于计算机界的核心期刊：《ACM Transactions on Computer System》，全名是《QoS-Aware Scheduling in Heterogeneous Datacenters with Paragon》。文章刊登于2013年，有些年头了，但如果留意过之前介绍的几篇论文的引文，就会注意到这篇论文被后面的研究者多次引用、是一篇非常经典的论文。
论文试图解决两个问题：第一，在一个成规模的数据中心中，往往有几十个不同型号的机型。运行的应用在不同的机型上的表现有好有坏，如何让调度器感知、并尽量将这些进程调度到合适的机型上运行，是一个需要重点探讨的问题；第二，在混布场景下，运行于同一台机器上的多个进程之间，很容易因为争抢某些公共的资源而导致运行质量受损。那么非常自然地，我们就会想在调度的时候，是不是能将会发生干扰的这些程序尽量的错开。识别两个程序会相互干扰到什么程度，是决定如何错开这些进程的基础。
论文中提到的Paragon，就是作者对上述两个问题的一个解决方案。文章的核心贡献在于，将上述问题构造成了”推荐系统”、使用协同过滤(Collaborative Filtering)相关思想进行建模求解。这个思路在2013年来看，是一个比较新鲜、有趣的想法。
为阐明问题，文章作者在2.1节中先用经典的给用户推荐电影的系统(netflix)来做类比，说明了核心计算过程：
假定一个视频网站，收集了m个用户对n个视频的打分信息\(A_{m,n}\)，我们可以对其进行奇异值分解(SVD),得到\(U\)、\(\Sigma\)、\(V\)三个矩阵：
\[A_{m, n} = \begin{vmatrix} a_{1,1} & a_{1,2} & \dots &a_{1,n} \\ a_{2,1} & a_{2,2} & \dots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m,1} & a_{m,2} & \dots & a_{m,n} \end{vmatrix} = U \cdot \Sigma \cdot V^T\]其中,
\[U_{m, r} = \begin{vmatrix} u_{1,1} & \dots & u_{1,r} \\ u_{2,1} & \dots & u_{2,r} \\ \vdots & \ddots & \vdots \\ u_{m, 1} & \dots & u_{m, r} \end{vmatrix}, V_{n, r} = \begin{vmatrix} v_{1,1} & v_{1, 2} & \dots & v_{1,n} \\ \vdots & \vdots & \ddots & \vdots \\ v_{r, 1} & v_{r, 2} & \dots & v_{r, n} \end{vmatrix}\] \[\Sigma _{r,r} = \begin{vmatrix} \sigma_1 & \dots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \dots & \sigma_r\end{vmatrix}\]这三个矩阵的含义可以大致解释如下1：
- \(\Sigma_{r,r}\): 表示这个数据可以将视频分成r个相似性比较高的组。比如喜剧、动作片等。矩阵中的\(\sigma\)值的大小表达这个分类的可信程度。
- \(U_{m, r}\)：表达用户对某个类别的视频的偏好程度。比如矩阵中的\(u_{i,j}\)，就表达出第i个用户对第j个类别的视频的喜好程度。
- \(V_{n,r}\)：类似的，矩阵\(V\)表达视频归属于某个类别的可能性。比如矩阵中的\(v_{i,j}\)，表达的是第i个视频属于第j个类别的可能性。
但在现实中，不可能拿到所有用户对所有的电影的打分情况，因此矩阵\(A\)是不完整的。这就需要一个算法去对那些缺失的”项”进行猜测，填补空白。论文中提到的算法就是PQ-reconstruction。首先我们记\(Q_{m,r} = U, P^T_{r,n} = \Sigma \cdot V^T\)，那么可以构造一个待迭代改进的矩阵\(R = Q \times P^T\), 然后通过梯度下降法（Stochastic Gradient Descent, SGD）反复迭代\(P, Q\)两个矩阵的值，使得\(R\)的\(L_2\)范式2最小(cost function)：
\[\begin{align*} & \epsilon_{u,i} = r_{u,i} - q_i \cdot p^T_u \\ & q_i \gets q_i + \eta(\epsilon_{u,i} p_u - \lambda q_i) \\ & p_u \gets p_u + \eta(\epsilon_{u,i} q_i - \lambda p_u) \\ \end{align*}\]上述式子反复迭代，直至 \({\lvert \epsilon \rvert}_{L_{2}} = \sqrt {\sum_{u,i} {\lvert \epsilon_{u,i} \rvert}^2}\)收敛。收敛以后，用迭代结果的\(R=Q \times P^T\)，就是一个”猜测”出来的预估矩阵\(R\)。换句话说，经过这些计算之后，通过查矩阵\(R\)，我们可以”猜”任意一个用户i对任意一个视频j的喜好程度。
回到论文的原始问题上来，这个论文如何用上述工具解决目标问题的呢？对于第一个问题，判断”某个进程对某个机型的喜好程度”，那么只需要将上面的”用户”和”视频”，替换成”进程”和”机型”。Paragon手头上维护着一个很大的矩阵\(A\)，其行是已经调度上去的众多进程，列是已知的所有机型。当有一个新的进程需要被调度的时候，Paragon先把这个进程抽样的扔到几个机型上跑一阵子看看，观察数据得到一个不完整的矩阵\(A\)(矩阵\(A\)的最后一行就是这个”新”的未知进程、其中只有选中的那几个机型对应的列有数值)，而后通过PQ-reconstruction预估、填补出这个进程对其他机型的喜好程度、作为调度程序的打分依据。需要注意的是，其实这里也顺带的用新采集的数据，update了一下\(A\)中的其他进程与各机型的相关程度。
对于第二个问题，就比较复杂些。作者首先引入了\(SoI\)(Source of Interference)的概念。两个进程会发生干扰，一定在某些公共资源上二者发生了争抢。\(SoI\)就是表达一个进程对某个资源的使用的强烈程度的值。对于一个新来的、待调度的进程，调度器需要计算一个进程上来以后对机器上已有的进程的影响(caused)和机器上已有进程对这个新进程的影响(tolerance)，而这个”敏感度”，同样可以通过类似的上述过程计算得到(row为进程、col为\(SoI\)指标，矩阵\(A\)的值表达”敏感度”，先调度到几台机器上跑些数据后估算出其他)。
在现实的场景下，随着一个集群规模下进程数目、机型、\(SoI\)累积数据的增多，模型矩阵\(A\)的精度将会越来越精准，使得调度算法的表现自动的迭代提升。通过PQ-reconstruction，Paragon能够预估出”未见过”的进程对机型和\(SoI\)相关资源的偏好程度。个人以为，在这两点上Paragon的表现非常的诱人、值得参考借鉴。
About Me
