Flink如何用窗格來優化視窗

對于處理時間類型的視窗（包含了翻滾視窗和滑動視窗），Flink會使用稱之為”pane”的技術來優化這類時間視窗的計算。

pane：中文譯為窗格。它将視窗劃分成多個規則的部分，這些部分可看作子視窗，可簡單了解為對視窗再次分片。

目前很多系統對滑動視窗進行查詢（計算）的通用解決方案是緩存每個輸入的元素，直到其不出現在所有的視窗中（随着時間的推移、視窗的滑動，元素對應的時間點将超出視窗的時間範圍）。既然每一個輸入元素都會同時屬于多個視窗，那麼這種方案會緩存一個元素直到它所歸屬的最後一個視窗被計算為止。

這種方案存在兩個主要的問題。首先，它要求緩沖區的大小是無界的：在任何一個時間點，目前視窗的所有元素都必須存在于緩沖區中，是以緩沖區的大小就取決于視窗的大小以及資料到達的速率。其次，對每個輸入元素處理多次會導緻很高昂的計算開銷。比如，對于下面這個滑動視窗示例，每個元素都會被處理四次（參考如下示意圖，假設對視窗大小為4分鐘，滑動步長為1分鐘的滑動視窗進行計算，則圖中每個正方形格子代表滑動步長的時間大小，以圖中深色格子為例，随着視窗的滑動其中的元素都會被計算四次）。随着視窗大小和滑動步長比例的增大，每個元素被處理的次數也随之增大。考慮到流處理系統中龐大的資料量以及快速的資料到達速率，減少大量的緩沖區空間需求以及計算次數就顯得尤為重要。

而基于窗格的計算優化是解決上述兩個問題的有效方式。窗格通過對視窗進行子聚合來減少對緩沖區的空間需求，通過在計算視窗時共享子聚合的結果來減少計算次數。我們仍然以上圖作為示例分析窗格機制，上圖中視窗流被分割為一分鐘的窗格（這裡窗格大小等于滑動步長并不是特意為之，窗格如果能被設定為滑動步長是最好的選擇，但有時并不一定能實作，具體窗格大小如何計算，後面我們會提及），每一個四分鐘大小的視窗都由四個連續的窗格組成。W3視窗由窗格P3-P6組成，每一個窗格都是四個視窗的組成部分，例如P5是視窗W2-W5的組成部分。為了完成對視窗的計算，我們先對窗格進行子聚合，而對視窗的聚合則建立在對四個窗格的聚合結果之上。

Flink對窗格的應用有其限制的場景。首先，必須是基于鍵分組過的視窗流，也就是視窗必須是基于鍵的；其次，Flink隻支援具備定時觸發器的處理時間（這一點也将計數視窗等非時間視窗排除在外）；第三，凡是配備了驅逐器的視窗都無法應用基于窗格的計算優化。

雖然窗格發揮優勢的對象是處理時間的滑動視窗，但因為翻滾視窗可以看作滑動視窗的特例（滑動步長即為視窗大小），是以基于窗格的計算優化也同樣适用于處理時間的翻滾視窗。

下面我們來看Flink對窗格的實作，在Flink中支援兩種類型的窗格：聚合窗格和累加窗格。類圖如下所示：

AbstractKeyedTimePanes為兩種類型的窗格提供模闆，它維護了最新的窗格引用，并将之前的窗格都存儲到一個隊列裡，隊列中始終維護着固定數量的窗格個數（個數為：視窗的大小除以窗格的大小）。在Flink中存儲窗格資訊的資料結構是KeyMap（它是對哈希表的一種特殊實作，這種實作的特點是能夠更高效地周遊元素），并提供了traverseMaps方法用于對KeyMap集合進行周遊，定義被周遊元素的處理邏輯需要實作接口：TraversalEvaluator。

AbstractKeyedTimePanes定義了兩個抽象方法，供子類實作：

addElementToLatestPane：将元素添加到最新的窗格中；

evaluateWindow：對視窗進行計算（最終依賴于各自對TraversalEvaluator接口的實作）；

AggregatingKeyedTimePanes和AccumulatingKeyedTimePanes是抽象類AbstractKeyedTimePanes的兩個派生類。AggregatingKeyedTimePanes類采用的計算函數是ReduceFunction，而AccumulatingKeyedTimePanes類采用的計算函數則是一般的WindowFunction。

這兩個派生類對上面兩個抽象方法的實作有很大的差别：AggregatingKeyedTimePanes是在addElementToLatestPane方法中即時計算窗格的值并更新，在evaluateWindow方法中其實作的AggregatingTraversal也是即時求值的。而AccumulatingKeyedTimePanes正好與之相反，其addElementToLatestPane隻是将元素加入到集合中，對應的WindowFunctionTraversal則是惰性求值（先收集元素，到最後再應用函數進行計算）。

窗格是可以“滑動”的（對應方法：slidePanes），對應到代碼實作上：就是将“目前”窗格加入到雙端隊列中，然後重新生成一個新的窗格對象作為“目前”窗格。

原文釋出時間為：2016-09-29

本文作者：vinoYang