1. 背景-什么是流計算

在傳統的數據處理流程中，總是先收集數據，然后將數據放到數據庫中，當人們需要的時候通過查詢對應的數據進行處理。這樣看起來沒什么大問題，但是當我們遇到以下場景的時候就有問題了。比如：金融風控，雙十一搶購，推薦系統等，這類系統有一個共同的特點，就是對時效性要求非常高。

所謂“時光一逝不復返，往事只能回味“。我們舉一個簡單的例子，當前你的余額寶賬戶有3000塊，你去商場消費了2000。這時候觸發支付寶結算，假設支付寶處理這筆數據需要10秒，而10秒之內，你接著又消費了2000，這時候應該提示你余額不足了，但由于結算程序還在處理，實際上余額還有3000，那么你這2000又結結實實可以消費了。10秒后支付寶反應過來了，這時候錢已經扣了，找誰還錢去啊，這樣引發了很大的金融風險。

其實還有一個簡單的辦法，支付寶在結賬的時候（10秒鐘之內）禁止消費，又帶來的問題是交易量下跌，這樣的損失更加接受不了，所以這就對數據的實時處理要求非常高，這1秒的數據這1秒就要處理完，下一秒的數據可能又是其它的情況了。數據就像流水一樣不斷變化，我們需要實時的處理數據。

2. 流式計算優化之拓撲排序

2.1 流式計算

流式計算就是實時查詢并且對數據進行計算，假設我們遇到了如下計算場景：

A = D + B B = C + E C = D + E

我們需要計算得到 A 的值，如何才能最快的計算出結果呢？我們可以從以下幾個方面來分析問題。

2.2 單線程

如果是單線程的情況，我們只能線性的去執行任務，最開始計算 a = d + b，先計算 d，然后計算 b，而 b = c + e，只能再去計算 c，而 c = d + e。先計算出 d 和 e 相加得出 c，然后計算 c 加 e 得出 b，最后計算 d 加 b 得出 a。最后我們統計計算 a，一共做了多少次計算：

d 2次 e 2次 c 1次 b 1次 a 1次

這里顯而易見，我們做了2次重復計算。有2種方法去解決這個問題：一種是加緩存，一種是拓撲排序。

• 緩存

增加緩存的方法如下，計算 a 的時候先計算 d 和 b，計算 d 之后把 d 先緩存，然后計算 b，由于 b=c+e，那么需要先計算 c，而 c=d+e，最后需要計算 d+e，而 d 已經緩存了直接從內存取出，再接著計算 e，放入緩存，這樣計算 b=c+e 的時候只需要計算 c，e 直接從內存取出。緩存雖然可以解決上面的問題，但也有缺點，首先緩存需要占用內存空間，其次緩存都有淘汰機制。

• 拓撲排序

我們可以根據上述的關系，得到如下的依賴圖：

拓撲關系依賴圖

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

2.2 多線程

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

并發線程時序圖

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

如果我們按照如下思路，還可以進一步節省計算資源，在上面拓撲排序的基礎上，加入層級的概念，比如：

層次劃分的拓撲關系依賴圖

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

3. 流式計算優化之IO合并

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

根據層次關系的拓撲依賴圖，我們計算的順序可以按照如下方式進行：先從簡單點的情況，然后擴展到復雜的情況。

• IO合并

首先我們假設 d 和 e 都是 IO 計算，如果按照之前介紹的拓撲排序然后再并發的思路，那么我們會同時啟動2個線程，分別計算 d 和 e。雖然多線程不會增加時間，但是多了一次 IO 操作，帶來的影響就是 IO 是有瓶頸的，如果系統的 IO 操作變多，會導致系統抖動和延時，假如我們可以把 d 和 e 做 IO 合并，即一次就可以把 d 和 e 都讀取出來，那么系統 IO 的容量就可以提高1倍（實際不到1倍的提升）。

• IO不能合并

有2種情況：

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

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

4. 流式計算優化之分支預測

• 假設計算場景：

if ( isWeekend) {readIO(A); } else {readIO(B); }

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

• 分支預測機制

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

• 預取緩存策略

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

5. 參開資料

1.?Dependency Resolving Algorithm

2.?Topological sorting

總結

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

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。