Flink 原理與實現：Window 機制

IreneNewsom 8年前發布 | 23K 次閱讀技術分布式/云計算/大數據

Flink 認為 Batch 是 Streaming 的一個特例，所以 Flink 底層引擎是一個流式引擎，在上面實現了流處理和批處理。而窗口（window）就是從 Streaming 到 Batch 的一個橋梁。Flink 提供了非常完善的窗口機制，這是我認為的 Flink 最大的亮點之一（其他的亮點包括消息亂序處理，和 checkpoint 機制）。本文我們將介紹流式處理中的窗口概念，介紹 Flink 內建的一些窗口和 Window API，最后討論下窗口在底層是如何實現的。

什么是 Window

在流處理應用中，數據是連續不斷的，因此我們不可能等到所有數據都到了才開始處理。當然我們可以每來一個消息就處理一次，但是有時我們需要做一些聚合類的處理，例如：在過去的1分鐘內有多少用戶點擊了我們的網頁。在這種情況下，我們必須定義一個窗口，用來收集最近一分鐘內的數據，并對這個窗口內的數據進行計算。

窗口可以是時間驅動的（Time Window，例如：每30秒鐘），也可以是數據驅動的（Count Window，例如：每一百個元素）。一種經典的窗口分類可以分成：翻滾窗口（Tumbling Window，無重疊），滾動窗口（Sliding Window，有重疊），和會話窗口（Session Window，活動間隙）。

我們舉個具體的場景來形象地理解不同窗口的概念。假設，淘寶網會記錄每個用戶每次購買的商品個數，我們要做的是統計不同窗口中用戶購買商品的總數。下圖給出了幾種經典的窗口切分概述圖：

上圖中，raw data stream 代表用戶的購買行為流，圈中的數字代表該用戶本次購買的商品個數，事件是按時間分布的，所以可以看出事件之間是有time gap的。Flink 提供了上圖中所有的窗口類型，下面我們會逐一進行介紹。

Time Window

就如名字所說的，Time Window 是根據時間對數據流進行分組的。這里我們涉及到了流處理中的時間問題，時間問題和消息亂序問題是緊密關聯的，這是流處理中現存的難題之一，我們將在后續的EventTime 和消息亂序處理中對這部分問題進行深入探討。這里我們只需要知道 Flink 提出了三種時間的概念，分別是event time（事件時間：事件發生時的時間），ingestion time（攝取時間：事件進入流處理系統的時間），processing time（處理時間：消息被計算處理的時間）。Flink 中窗口機制和時間類型是完全解耦的，也就是說當需要改變時間類型時不需要更改窗口邏輯相關的代碼。

Tumbling Time Window
如上圖，我們需要統計每一分鐘中用戶購買的商品的總數，需要將用戶的行為事件按每一分鐘進行切分，這種切分被成為翻滾時間窗口（Tumbling Time Window）。翻滾窗口能將數據流切分成不重疊的窗口，每一個事件只能屬于一個窗口。通過使用 DataStream API，我們可以這樣實現：
```
// Stream of (userId, buyCnt)
val buyCnts: DataStream[(Int, Int)] = ...

val tumblingCnts: DataStream[(Int, Int)] = buyCnts
  // key stream by userId
  .keyBy(0) 
  // tumbling time window of 1 minute length
  .timeWindow(Time.minutes(1))
  // compute sum over buyCnt
  .sum(1)
```
Sliding Time Window
但是對于某些應用，它們需要的窗口是不間斷的，需要平滑地進行窗口聚合。比如，我們可以每30秒計算一次最近一分鐘用戶購買的商品總數。這種窗口我們稱為滑動時間窗口（Sliding Time Window）。在滑窗中，一個元素可以對應多個窗口。通過使用 DataStream API，我們可以這樣實現：
```
val slidingCnts: DataStream[(Int, Int)] = buyCnts
  .keyBy(0) 
  // sliding time window of 1 minute length and 30 secs trigger interval
  .timeWindow(Time.minutes(1), Time.seconds(30))
  .sum(1)
```

Count Window

Count Window 是根據元素個數對數據流進行分組的。

Tumbling Count Window
當我們想要每100個用戶購買行為事件統計購買總數，那么每當窗口中填滿100個元素了，就會對窗口進行計算，這種窗口我們稱之為翻滾計數窗口（Tumbling Count Window），上圖所示窗口大小為3個。通過使用 DataStream API，我們可以這樣實現：
```
// Stream of (userId, buyCnts)
val buyCnts: DataStream[(Int, Int)] = ...

val tumblingCnts: DataStream[(Int, Int)] = buyCnts
  // key stream by sensorId
  .keyBy(0)
  // tumbling count window of 100 elements size
  .countWindow(100)
  // compute the buyCnt sum 
  .sum(1)
```

Sliding Count Window
當然Count Window 也支持 Sliding Window，雖在上圖中未描述出來，但和Sliding Time Window含義是類似的，例如計算每10個元素計算一次最近100個元素的總和，代碼示例如下。
```
val slidingCnts: DataStream[(Int, Int)] = vehicleCnts
  .keyBy(0)
  // sliding count window of 100 elements size and 10 elements trigger interval
  .countWindow(100, 10)
  .sum(1)
```

Session Window

在這種用戶交互事件流中，我們首先想到的是將事件聚合到會話窗口中（一段用戶持續活躍的周期），由非活躍的間隙分隔開。如上圖所示，就是需要計算每個用戶在活躍期間總共購買的商品數量，如果用戶30秒沒有活動則視為會話斷開（假設raw data stream是單個用戶的購買行為流）。Session Window 的示例代碼如下：

// Stream of (userId, buyCnts)
val buyCnts: DataStream[(Int, Int)] = ...

val sessionCnts: DataStream[(Int, Int)] = vehicleCnts
  .keyBy(0)
  // session window based on a 30 seconds session gap interval 
  .window(ProcessingTimeSessionWindows.withGap(Time.seconds(30)))
  .sum(1)

一般而言，window 是在無限的流上定義了一個有限的元素集合。這個集合可以是基于時間的，元素個數的，時間和個數結合的，會話間隙的，或者是自定義的。Flink 的 DataStream API 提供了簡潔的算子來滿足常用的窗口操作，同時提供了通用的窗口機制來允許用戶自己定義窗口分配邏輯。下面我們會對 Flink 窗口相關的 API 進行剖析。

剖析 Window API

得益于 Flink Window API 松耦合設計，我們可以非常靈活地定義符合特定業務的窗口。Flink 中定義一個窗口主要需要以下三個組件。

Window Assigner：用來決定某個元素被分配到哪個/哪些窗口中去。

如下類圖展示了目前內置實現的 Window Assigners：
Trigger：觸發器。決定了一個窗口何時能夠被計算或清除，每個窗口都會擁有一個自己的Trigger。

如下類圖展示了目前內置實現的 Triggers：
Evictor：可以譯為“驅逐者”。在Trigger觸發之后，在窗口被處理之前，Evictor（如果有Evictor的話）會用來剔除窗口中不需要的元素，相當于一個filter。

如下類圖展示了目前內置實現的 Evictors：

上述三個組件的不同實現的不同組合，可以定義出非常復雜的窗口。Flink 中內置的窗口也都是基于這三個組件構成的，當然內置窗口有時候無法解決用戶特殊的需求，所以 Flink 也暴露了這些窗口機制的內部接口供用戶實現自定義的窗口。下面我們將基于這三者探討窗口的實現機制。

Window 的實現

下圖描述了 Flink 的窗口機制以及各組件之間是如何相互工作的。

首先上圖中的組件都位于一個算子（window operator）中，數據流源源不斷地進入算子，每一個到達的元素都會被交給 WindowAssigner。WindowAssigner 會決定元素被放到哪個或哪些窗口（window），可能會創建新窗口。因為一個元素可以被放入多個窗口中，所以同時存在多個窗口是可能的。注意， Window 本身只是一個ID標識符，其內部可能存儲了一些元數據，如 TimeWindow 中有開始和結束時間，但是并不會存儲窗口中的元素。窗口中的元素實際存儲在 Key/Value State 中，key為 Window ，value為元素集合（或聚合值）。為了保證窗口的容錯性，該實現依賴了 Flink 的 State 機制（參見 state 文檔）。

每一個窗口都擁有一個屬于自己的 Trigger，Trigger上會有定時器，用來決定一個窗口何時能夠被計算或清除。每當有元素加入到該窗口，或者之前注冊的定時器超時了，那么Trigger都會被調用。Trigger的返回結果可以是 continue（不做任何操作），fire（處理窗口數據），purge（移除窗口和窗口中的數據），或者 fire + purge。一個Trigger的調用結果只是fire的話，那么會計算窗口并保留窗口原樣，也就是說窗口中的數據仍然保留不變，等待下次Trigger fire的時候再次執行計算。一個窗口可以被重復計算多次知道它被 purge 了。在purge之前，窗口會一直占用著內存。

當Trigger fire了，窗口中的元素集合就會交給 Evictor （如果指定了的話）。Evictor 主要用來遍歷窗口中的元素列表，并決定最先進入窗口的多少個元素需要被移除。剩余的元素會交給用戶指定的函數進行窗口的計算。如果沒有 Evictor 的話，窗口中的所有元素會一起交給函數進行計算。

計算函數收到了窗口的元素（可能經過了 Evictor 的過濾），并計算出窗口的結果值，并發送給下游。窗口的結果值可以是一個也可以是多個。DataStream API 上可以接收不同類型的計算函數，包括預定義的 sum() , min() , max() ，還有 ReduceFunction ， FoldFunction ，還有 WindowFunction 。WindowFunction 是最通用的計算函數，其他的預定義的函數基本都是基于該函數實現的。

Flink 對于一些聚合類的窗口計算（如sum,min）做了優化，因為聚合類的計算不需要將窗口中的所有數據都保存下來，只需要保存一個result值就可以了。每個進入窗口的元素都會執行一次聚合函數并修改result值。這樣可以大大降低內存的消耗并提升性能。但是如果用戶定義了 Evictor，則不會啟用對聚合窗口的優化，因為 Evictor 需要遍歷窗口中的所有元素，必須要將窗口中所有元素都存下來。

源碼分析

上述的三個組件構成了 Flink 的窗口機制。為了更清楚地描述窗口機制，以及解開一些疑惑（比如 purge 和 Evictor 的區別和用途），我們將一步步地解釋 Flink 內置的一些窗口（Time Window，Count Window，Session Window）是如何實現的。

Count Window 實現

Count Window 是使用三組件的典范，我們可以在 KeyedStream 上創建 Count Window，其源碼如下所示：

// tumbling count window
public WindowedStream<T, KEY, GlobalWindow> countWindow(long size) {
  return window(GlobalWindows.create())  // create window stream using GlobalWindows
      .trigger(PurgingTrigger.of(CountTrigger.of(size))); // trigger is window size
}
// sliding count window
public WindowedStream<T, KEY, GlobalWindow> countWindow(long size, long slide) {
  return window(GlobalWindows.create())
    .evictor(CountEvictor.of(size))  // evictor is window size
    .trigger(CountTrigger.of(slide)); // trigger is slide size
}

第一個函數是申請翻滾計數窗口，參數為窗口大小。第二個函數是申請滑動計數窗口，參數分別為窗口大小和滑動大小。它們都是基于 GlobalWindows 這個 WindowAssigner 來創建的窗口，該assigner會將所有元素都分配到同一個global window中，所有 GlobalWindows 的返回值一直是 GlobalWindow 單例。基本上自定義的窗口都會基于該assigner實現。

翻滾計數窗口并不帶evictor，只注冊了一個trigger。該trigger是帶purge功能的 CountTrigger。也就是說每當窗口中的元素數量達到了 window-size，trigger就會返回fire+purge，窗口就會執行計算并清空窗口中的所有元素，再接著儲備新的元素。從而實現了tumbling的窗口之間無重疊。

滑動計數窗口的各窗口之間是有重疊的，但我們用的 GlobalWindows assinger 從始至終只有一個窗口，不像 sliding time assigner 可以同時存在多個窗口。所以trigger結果不能帶purge，也就是說計算完窗口后窗口中的數據要保留下來（供下個滑窗使用）。另外，trigger的間隔是slide-size，evictor的保留的元素個數是window-size。也就是說，每個滑動間隔就觸發一次窗口計算，并保留下最新進入窗口的window-size個元素，剔除舊元素。

假設有一個滑動計數窗口，每2個元素計算一次最近4個元素的總和，那么窗口工作示意圖如下所示：

圖中所示的各個窗口邏輯上是不同的窗口，但在物理上是同一個窗口。該滑動計數窗口，trigger的觸發條件是元素個數達到2個（每進入2個元素就會觸發一次），evictor保留的元素個數是4個，每次計算完窗口總和后會保留剩余的元素。所以第一次觸發trigger是當元素5進入，第三次觸發trigger是當元素2進入，并驅逐5和2，計算剩余的4個元素的總和（22）并發送出去，保留下2,4,9,7元素供下個邏輯窗口使用。

Time Window 實現

同樣的，我們也可以在 KeyedStream 上申請 Time Window，其源碼如下所示：

// tumbling time window
public WindowedStream<T, KEY, TimeWindow> timeWindow(Time size) {
  if (environment.getStreamTimeCharacteristic() == TimeCharacteristic.ProcessingTime) {
    return window(TumblingProcessingTimeWindows.of(size));
  } else {
    return window(TumblingEventTimeWindows.of(size));
  }
}
// sliding time window
public WindowedStream<T, KEY, TimeWindow> timeWindow(Time size, Time slide) {
  if (environment.getStreamTimeCharacteristic() == TimeCharacteristic.ProcessingTime) {
    return window(SlidingProcessingTimeWindows.of(size, slide));
  } else {
    return window(SlidingEventTimeWindows.of(size, slide));
  }
}

在方法體內部會根據當前環境注冊的時間類型，使用不同的WindowAssigner創建window。可以看到，EventTime和IngestTime都使用了 XXXEventTimeWindows 這個assigner，因為EventTime和IngestTime在底層的實現上只是在Source處為Record打時間戳的實現不同，在window operator中的處理邏輯是一樣的。

這里我們主要分析sliding process time window，如下是相關源碼：

public class SlidingProcessingTimeWindows extends WindowAssigner<Object, TimeWindow> {
  private static final long serialVersionUID = 1L;

  private final long size;

  private final long slide;

  private SlidingProcessingTimeWindows(long size, long slide) {
    this.size = size;
    this.slide = slide;
  }

  @Override
  public Collection<TimeWindow> assignWindows(Object element, long timestamp) {
    timestamp = System.currentTimeMillis();
    List<TimeWindow> windows = new ArrayList<>((int) (size / slide));
    // 對齊時間戳
    long lastStart = timestamp - timestamp % slide;
    for (long start = lastStart;
      start > timestamp - size;
      start -= slide) {
      // 當前時間戳對應了多個window
      windows.add(new TimeWindow(start, start + size));
    }
    return windows;
  }
  ...
}
public class ProcessingTimeTrigger extends Trigger<Object, TimeWindow> {
  @Override
  // 每個元素進入窗口都會調用該方法
  public TriggerResult onElement(Object element, long timestamp, TimeWindow window, TriggerContext ctx) {
    // 注冊定時器，當系統時間到達window end timestamp時會回調該trigger的onProcessingTime方法
    ctx.registerProcessingTimeTimer(window.getEnd());
    return TriggerResult.CONTINUE;
  }

  @Override
  // 返回結果表示執行窗口計算并清空窗口
  public TriggerResult onProcessingTime(long time, TimeWindow window, TriggerContext ctx) {
    return TriggerResult.FIRE_AND_PURGE;
  }
  ...
}

首先， SlidingProcessingTimeWindows 會對每個進入窗口的元素根據系統時間分配到 (size / slide) 個不同的窗口，并會在每個窗口上根據窗口結束時間注冊一個定時器（相同窗口只會注冊一份），當定時器超時時意味著該窗口完成了，這時會回調對應窗口的Trigger的 onProcessingTime 方法，返回FIRE_AND_PURGE，也就是會執行窗口計算并清空窗口。整個過程示意圖如下：

如上圖所示橫軸代表時間戳（為簡化問題，時間戳從0開始），第一條record會被分配到[-5,5)和[0,10)兩個窗口中，當系統時間到5時，就會計算[-5,5)窗口中的數據，并將結果發送出去，最后清空窗口中的數據，釋放該窗口資源。

來自： http://wuchong.me/blog/2016/05/25/flink-internals-window-mechanism/

本文由用戶 IreneNewsom 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。

轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。

本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！

本文地址：http://www.baiduhome.net/lib/view/open1464180387911.html

技術分布式/云計算/大數據