什么是 LP (Linear Program) optimization
假設(shè)有一萬塊錢傀顾，要買 3 支股票：Google, Tesla, Roku充岛。就增長率來說，肯定是 Roku 比 Tesla 好，Tesla 比 Google 好；但是馍忽，Google 比 Tesla 風險小，Tesla 又比 Roku 小燕差。這時候要怎么分配這錢去買股票呢遭笋？
一般來說，我們會控制風險在一定范圍內(nèi)谁不，可以表達為 Risk(all) < r。Google, Tesla, Roku 的投資額為 X1, X2, X3徽诲，增長率為 G1, G2, G3, 風險為 R1, R2, R3. 其實我們要求 max(Y):
Y = X1*G1 + X2*G2 + X3*G3
同時要滿足以下條件:
X1 + X2 + X3=10000
(R1*X1 + R2*X2 + R3*X3)/10000 < r
X1 > 0, X2 > 0, X3 > 0
上面的式子就叫做 LP optimization刹帕。LP solver 可以給出解 (X1', X2', X3') 得到 Y 的最大值。
上面式子有 3 個一階變量谎替，然而實際情況中我們可以有上萬個一階變量偷溺。
Job resource modeling
本章思路取自于 Morpheus [OSDI 16]
Job resource utilization 是一個 time series metrics。對于某個 job钱贯，根據(jù)其之前的 resource utilization挫掏，我們可以 infer model，然后用該 model 去優(yōu)化調(diào)度秩命。比方說尉共，我知道一個 Job 要用多少資源褒傅，就可以把 over-reserved 的資源分配給其他 jobs。
怎么去 infer model 呢?
一般來說袄友，我們給每個時間段取一個值殿托。比如 1-minute window，那么一小時的的 Job 我們就會有 60 個值剧蚣，定義為 X = (X1, X2, ... X60)支竹。假設(shè)有100 份過往數(shù)據(jù) S = (S1, S2, ...S100)。
定義 S[j, i], 表示第 j 份數(shù)據(jù)第 i 個時間段的鸠按。如果 X[i] > S[j, i]礼搁，就是 over-allocate；如果 X[i] < S[j, i]目尖，就是 under-allocate -- 各自都有 penalty馒吴。一個好的 model 就是要得出解 X 使得整體的 penalty 最小”把悖可以表達為求最小 Y：
Y = a*PO(X) + (1-a)*PU(X)
其中 a 是常量參數(shù)募书，PO(X) 是 over allocation penalty, PU(X) 是 under allocation penalty。
Over-allocation penalty
多分配出來的資源數(shù)量就可以等價于 penalty测蹲。對于第 j 份歷史數(shù)據(jù)莹捡，得出 PO(X)[j] = X - S[j]。但是少分配并不能是負數(shù)扣甲，不然就是獎勵了篮赢，所以更正為 PO(X)[j] = max(X - S[j], 0)。注意 max() 是 non-linear function琉挖，就不能用 LP 了启泣。然而，這個式子可以變成兩個 linear function:
PO(X)[i] = X - S[i]
X >= S[i]
和
PO(X)[i] = 0
X < S[i]
然后去比較兩個式子得出的最小 Y 哪個更小示辈。這也叫做 lossless transformation寥茫。
PO(X) 可以表達為:
Under-allocation penalty 更加復雜，但思路大同小異矾麻。最后也是得出一個 linear function纱耻。最后就可以用 LP optimization solver 來得出解 X，也就是我們所要的 Model 了险耀。
擴展閱讀 Morpheus: Towards Automated SLOs for Enterprise Clusters
