什么是 LP (Linear Program) optimization
假設(shè)有一萬塊錢，要買 3 支股票：Google, Tesla, Roku。就增長率來說，肯定是 Roku 比 Tesla 好，Tesla 比 Google 好；但是，Google 比 Tesla 風(fēng)險(xiǎn)小，Tesla 又比 Roku 小。這時(shí)候要怎么分配這錢去買股票呢？
一般來說，我們會(huì)控制風(fēng)險(xiǎn)在一定范圍內(nèi)，可以表達(dá)為 Risk(all) < r。Google, Tesla, Roku 的投資額為 X1, X2, X3，增長率為 G1, G2, G3, 風(fēng)險(xiǎn)為 R1, R2, R3. 其實(shí)我們要求 max(Y):
Y = X1*G1 + X2*G2 + X3*G3
同時(shí)要滿足以下條件:
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 個(gè)一階變量，然而實(shí)際情況中我們可以有上萬個(gè)一階變量。
Job resource modeling
本章思路取自于 Morpheus [OSDI 16]
Job resource utilization 是一個(gè) time series metrics。對(duì)于某個(gè) job，根據(jù)其之前的 resource utilization，我們可以 infer model，然后用該 model 去優(yōu)化調(diào)度。比方說，我知道一個(gè) Job 要用多少資源，就可以把 over-reserved 的資源分配給其他 jobs。
怎么去 infer model 呢?
一般來說，我們給每個(gè)時(shí)間段取一個(gè)值。比如 1-minute window，那么一小時(shí)的的 Job 我們就會(huì)有 60 個(gè)值，定義為 X = (X1, X2, ... X60)。假設(shè)有100 份過往數(shù)據(jù) S = (S1, S2, ...S100)。
定義 S[j, i], 表示第 j 份數(shù)據(jù)第 i 個(gè)時(shí)間段的。如果 X[i] > S[j, i]，就是 over-allocate；如果 X[i] < S[j, i]，就是 under-allocate -- 各自都有 penalty。一個(gè)好的 model 就是要得出解 X 使得整體的 penalty 最小?？梢员磉_(dá)為求最小 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ù)量就可以等價(jià)于 penalty。對(duì)于第 j 份歷史數(shù)據(jù)，得出 PO(X)[j] = X - S[j]。但是少分配并不能是負(fù)數(shù)，不然就是獎(jiǎng)勵(lì)了，所以更正為 PO(X)[j] = max(X - S[j], 0)。注意 max() 是 non-linear function，就不能用 LP 了。然而，這個(gè)式子可以變成兩個(gè) linear function:
PO(X)[i] = X - S[i]
X >= S[i]
和
PO(X)[i] = 0
X < S[i]
然后去比較兩個(gè)式子得出的最小 Y 哪個(gè)更小。這也叫做 lossless transformation。
PO(X) 可以表達(dá)為:
Under-allocation penalty 更加復(fù)雜，但思路大同小異。最后也是得出一個(gè) linear function。最后就可以用 LP optimization solver 來得出解 X，也就是我們所要的 Model 了。
擴(kuò)展閱讀 Morpheus: Towards Automated SLOs for Enterprise Clusters
