我們可以根據(jù)上述的關(guān)系，得到如下的依賴圖：

實際上我們得到了一個 DAG 的圖，可以看出如果要計算 a，我們需要先計算 d 和 b，而計算 b 需要計算 c 和 e，而計算 c 又需要計算 d 和 e，即一件事情依賴另外的一件。這樣的例子在生活中有很多，比如早晨起來，你必須先穿襪子才能穿鞋子，而穿鞋子之前你必須得先穿上褲子。這些問題都可以用拓?fù)渑判騺斫鉀Q，思路就是深度優(yōu)先遍歷，優(yōu)先找出最底層的節(jié)點，然后找出次底層的，依次得出結(jié)果。最后我們會得到如下的順序：d e c b a，即按照如下順序計算，每個節(jié)點只需要計算一次，在不產(chǎn)生順序沖突的同時，得出最短的計算時間。

2.2 多線程

上面是單線程的情況，如果是多線程的情況，當(dāng)然只要我們有足夠的資源，多線程肯定是理論上計算時間最短的。但導(dǎo)致的一個問題就是重復(fù)計算，浪費計算資源，下面是多線程執(zhí)行流程圖：

即如果開啟6個線程執(zhí)行，那么最終執(zhí)行的時間可能是 （這里假定 d 的執(zhí)行時間比 e 長） d c b a，我們把 e 的計算時間給節(jié)省掉了，多線程的情況對緩存來說可以說是災(zāi)難性的后果，比如計算 a 開始的時候就開始計算 d 了，而計算 c 的時候 d 如果沒有計算完，c 也取不到 d 的緩存，導(dǎo)致緩存可以說是沒有太大用處。如果緩存可以取到，才可以節(jié)省計算資源。

如果我們按照如下思路，還可以進(jìn)一步節(jié)省計算資源，在上面拓?fù)渑判虻幕A(chǔ)上，加入層級的概念，比如：

加入層級之后，比如 d 和 e 的層數(shù)都是4，那么 d 和 e 可以并行計算，而 c,b,a 的層級分別是3,2,1，進(jìn)行串行計算。這里很明顯，如果層數(shù)相同的則進(jìn)行并行計算，層數(shù)不同則串行計算，好處是：1.節(jié)省計算資源 2.是節(jié)省了計算時間。

3. 流式計算優(yōu)化之IO合并

流式計算還有一種優(yōu)化是對內(nèi)存操作和 IO 操作做區(qū)分，并進(jìn)行優(yōu)化，比如上述情況，如果 d 和 e 開啟并行計算，c,b,a 線性計算，從計算的角度來看待，確實是最優(yōu)的計算方式。但是考慮到計算分為內(nèi)存計算和 IO 計算，而且 IO 計算的延時比內(nèi)存計算高幾倍到十幾倍，因此我們主要的策略就是對 IO 計算做優(yōu)化，一個比較好的優(yōu)化思路就是對 IO 做合并，或者對 IO 計算做緩存，下面主要講述對 IO 計算合并。

根據(jù)層次關(guān)系的拓?fù)湟蕾噲D，我們計算的順序可以按照如下方式進(jìn)行：先從簡單點的情況，然后擴展到復(fù)雜的情況。

• IO合并

首先我們假設(shè) d 和 e 都是 IO 計算，如果按照之前介紹的拓?fù)渑判蛉缓笤俨l(fā)的思路，那么我們會同時啟動2個線程，分別計算 d 和 e。雖然多線程不會增加時間，但是多了一次 IO 操作，帶來的影響就是 IO 是有瓶頸的，如果系統(tǒng)的 IO 操作變多，會導(dǎo)致系統(tǒng)抖動和延時，假如我們可以把 d 和 e 做 IO 合并，即一次就可以把 d 和 e 都讀取出來，那么系統(tǒng) IO 的容量就可以提高1倍（實際不到1倍的提升）。

• IO不能合并

有2種情況：

1. 如果 d 和 e 是訪問的不同的數(shù)據(jù)庫，那么我們的 IO 不能做合并，我們就只能讀取2次。

2. 接著我們增加下 IO 合并的復(fù)雜程度，比如現(xiàn)在有 d,e,c 這3個節(jié)點是 IO 計算，d 和 e 可以做 IO 合并，而 c 需要等待 d 和 e 做 join 操作之后，才能確定讀取哪些 IO，這樣我們做 IO 合并的時候只能先把 d 和 e 做合并，而不能把 c 做合并，因為在 d 和 e 做 join 操作之后，我們才知道 c 要去查什么數(shù)據(jù)，因此也做不了合并。不過上述問題也是可以優(yōu)化的，這一部分的優(yōu)化可以通過分支預(yù)測和預(yù)取操作來解決。2個數(shù)據(jù)做 join 操作就是找到2個數(shù)據(jù)集的合集部分，比如一個數(shù)據(jù)集是數(shù)學(xué)成績，一個數(shù)據(jù)集是地理成績，下面我們需要找出數(shù)學(xué)成績大于60分，而且地理成績大于90的學(xué)生，那么我們就是找到2個數(shù)據(jù)集的交集部分，即2個數(shù)據(jù)集做 join 操作。

4. 流式計算優(yōu)化之分支預(yù)測

• 假設(shè)計算場景：

可以看到，如果今天是周末，則讀取 A，如果今天不是周末，則讀取 B。由于 A 和 B 都是 IO 操作，比較耗時，如果 A 和 B 能夠合并讀取，那么我們當(dāng)然很開心，我們只需要讀取一次就可以了。假如 A 和 B 不能夠做 IO 合并，那么遇到的問題是，我們需要先判斷是否是周末才能夠明白到底去讀取哪個 IO，假如我們引入分支預(yù)測機制。

• 分支預(yù)測機制

上述條件，假設(shè)進(jìn)入 A 條件的概率是80%，而進(jìn)入 B 條件的概率是20%，如果采用分支預(yù)測，我們會直接跳過判斷，直接去讀取 A，然后再去計算判斷條件，如果條件判斷錯誤，再回過頭去讀取 B，這樣帶來的好處是如果判斷正確，那么節(jié)省了大量的判斷時間，如果判斷錯誤，那么就會重新讀取 B，時間反而變長了。前提是預(yù)測的足夠準(zhǔn)確，會提高計算的效率。

• 預(yù)取緩存策略

對應(yīng)的計算還有預(yù)取操作。還是上面的例子，要計算上面的語句，可以根據(jù)統(tǒng)計學(xué)來判斷，哪些數(shù)據(jù)有很大的概率需要去取的，優(yōu)先把這些數(shù)據(jù)放進(jìn)緩存，下次計算直接去內(nèi)存取數(shù)據(jù)，而不需要從 IO 取數(shù)據(jù)，這一部分就是熱點數(shù)據(jù)，很多時候會把這部分熱點數(shù)據(jù)保存在分布式的緩存中，能夠很大的提高效率。當(dāng)然預(yù)取的機制，緩存的一致性和緩存淘汰的機制對數(shù)據(jù)命中的效率影響非常大，另外在機器重新啟動后，緩存沒有建立起來之前，系統(tǒng)面臨著沒有緩存的情況，導(dǎo)致在啟動階段會有大量延時的情況，這些都是需要考慮的問題。

5. 參開資料

1.?Dependency Resolving Algorithm

2.?Topological sorting

總結(jié)

以上是生活随笔為你收集整理的流式计算优化：时效性 [王方浩视角]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。