【要約】The world beyond batch: Streaming 101

少し前の記事になりますが、オライリーにGoogleのTyler Akidau氏が[ストリーム処理についての記事](https://www.oreilly.com/ideas/the-world-beyond-batch-streaming-101)を投稿していたので要約してみました。

とはいえ、一気に読んで訳したものですので、相応に粗く、用語の統一も多分ずれがあり、流れがわかればいい内容となっていますので、その前提で。
ただ、コメントは歓迎します。*ここにまとめた私自身も理解できていない点が多々あると思いますので。*

以後の内容は[オライリーの記事のライセンス](http://www.oreilly.com/terms/#licenses)より、[CC BY-NC-SA 1.0](https://creativecommons.org/licenses/by-nc-sa/1.0/deed.ja)になります。

* * * 

# The world beyond batch: Streaming 101

```
これはデータ処理に対する革新を示す2部作文章の1作目。
```

ストリーム処理はビッグデータの中での大きな流れになっている。

- ビジネスにおいて、よりタイムリーなデータが求められるようになっており、ストリーム処理は低レイテンシを達成するためのいい手段
- 巨大かつ無限に発生し続ける特性を持つデータは様々なビジネスで生じており、それらのデータに対応が容易
- 継続してデータを処理し続けるというモデルにより、リソース使用量が予測しやすくなる。

このように、ビジネスサイドではストリーム処理に対するニーズが増大しているにも関わらず、ストリーム処理システムの大半はバッチのそれに比べて未成熟な状態にとどまっている。だが、最近進化が著しいのもまた事実。

最近のストリーム処理に対する流れは、直近5年以上Googleで大規模ストリーム処理システム（MillWheel、Cloud Dataflow）の構築を行ってきた身としては喜ばしい限りだ。私はまたストリーム処理について皆が理解してもらいたい。それによって、特に現状存在しているバッチ処理システムとギャップが生じている処理をストリーム処理に正しく移行する流れを作りたい。

それについて、私はO’Reillyの方々に招かれ、 Strata + Hadoop World London 2015においてバッチとさよならするような公演を行うことが出来た。
その内容は多岐にわたるため、2回に分けて投稿する。

- Streaming 101
  - 1個目の投稿においては、詳細に踏み込む前に背景に対する説明と、いくつかの用語に対する明確化を行う。そのうえで、バッチとストリームというデータ処理に対する共通的なアプローチの概要を説明する。
- The Dataflow Model
  - 2個目の投稿においては、いくつかのユースケースに対する実例を示すことで、バッチ＋ストリームを共通的に扱う扱うモデルについて説明する。その後、新しい概念のシステムと、既存のバッチ処理、ストリーム処理システムの比較を行う。

## 背景

はじめに、以後議論したい内容に対する重要な背景情報について説明する。
それは以下の3要素からなる。

- Terminology
  - 複雑な内容について明確に話すために、用語の定義を行う。いくつかの言葉はもともと別の用途でも用いられる言葉であるため、その際は明確に用途を説明する。
- Capabilities
  - ストリーム処理システムの欠点についても明確にする。そのうえで、データ処理システムのエンジニアに対して、今後最新のデータ利用者のニーズに対応するために持つべき心得について提案する。
- Time domains
  - はじめにデータ処理に関連する時刻に対する重要事項2つを説明し、その2つに関連した困難さについて明らかにする。

#### Terminology: ストリーム処理とは何か？

この先に進む前に、まずはストリーム処理とは何かについて明確にする。
ストリーム処理という言葉は様々な用途に使用される。（簡単のため、これまではそれを曖昧に使用してきた。）それによって本当の所のストリーム処理とは何か、やストリーム処理は実際にどのようなことが可能なのかについて誤解を招きがちであるため、それを明確にしたい。

問題のうち最も重要な点はストリーム処理とは何かについて様々な記述があるということ。（永続的なデータ、近似した結果など）　そこから、口語的に様々な用語が生まれてきた。（ストリーム処理実行エンジンなど）　この用語群に対する明確さの欠如は、しばしばストリーム処理が「近似値」や「投機的結果」しか求めることが出来ないかのような誤解を招いてきた。

よく設計構築されたストリーム処理システムは結果の正確さ、一貫性、再実行性を既存のバッチ処理システムと同様に達成出来る。そのため、私は概念上は無限のデータに対して対応可能なように設計されたタイプのデータ処理エンジンを明確に「ストリーム処理」と分離して呼ぶことが適すると考える。（正確に言うとこの性質を実現可能なシステムとして、真のストリーム処理と、マイクロバッチ実装が含まれる。）

様々なケースのストリーム処理という用語の用途も含め、下記のような性質を明記可能と思われる。

- Unbounded data
  - 常に増大し続け、本質的には無限に発生するデータ。これがしばしば「ストリームデータ」と呼ばれる。しかしながら、このストリーム処理か、バッチかの切り分けに用いるには前述したとおり、そういったデータに対応できるものを一律で呼ぶとバッチも混ざるため、適さない。ただし、これらのデータセットの区別としては「ストリーム」を無限のデータ、「バッチ」を有限なデータとして扱うのが適している。
- Unbounded data processing
  - 永遠に処理が継続するモデルは前述のとおり無限のデータへ適用される。しかし、それだけの区切りであればバッチを繰り返すようなモデルも無限のデータに対応可能となる。そのため、誤解を招かないよう明確に無限のデータ処理という形で記述する。
- Low-latency, approximate, and/or speculative results
  - これらの特徴がしばしばストリーム処理エンジンに結びついて語られる。バッチ処理の場合、基本は生成されるのは完全なデータとなる。当然、バッチを近似値の算出にも用いることができるが、ストリーム処理に比べると劣る。

ここまででわかったように、ストリーム処理という言葉を使用した場合、無限のデータを処理する実行エンジン以上の意味はない。上記以外の意味を持つ場合、明示的に単語を分けて説明する。これはCloud Dataflowで我々がとってきたスタンスでもある。

#### ストリーム処理の誇張された制約

次にストリーム処理で「何ができないか？」について述べる。
ただ、ここで強調したいのは「よく設計されたストリーム処理基盤はどのように出来るか？」をこの記事で語っていること言うこと。
ストリーム処理システムはこれまで低レイテンシである代わりに不正確で投機的な結果しか取得できず、ラムダアーキテクチャのようなバッチシステムと結合して結果整合性で正しい結果を得るような用途にしか使えないととられ、ニッチな領域に押し込まれてきた。

ラムダアーキテクチャについて詳しくない方のために説明すると、ラムダアーキテクチャとはバッチ処理システムとストリーム処理を並行して動作させ、同じ処理を実行するというもの。
ストリーム処理システムは低レイテンシを提供するものの、近似としての結果しか算出することができない（なぜなら、ストリーム処理システムは正確性を保証できないから）。そのため、後からバッチシステムによる正確な結果を提供するというものだった。
これは元はStormの開発者であるNathan Marzによって提案されたもので、それ自体は非常に成功したモデルだったと今では考えられる。なぜなら、ストリーム処理が正確性に欠け、バッチ処理は特定のモデルにしか適用が難しい状態で、ラムダアーキテクチャでそれを多少なりとも両立できるモデルを構築できたのだから。しかし、不幸なことにラムダアーキテクチャを維持することはつまりは２つの独立したシステムを管理し、結果をマージする必要があるため、非常に大変な結果となった。

強い一貫性を持つストリーム処理エンジンを構築するべく尽力している中で、ラムダアーキテクチャの原理は多少不快に感じた。そのため、私はラムダアーキテクチャを用いるのではなく、ストリーム処理のモデルのみでシステムを構築する記事を見たとき非常にうれしかった。その記事では喜ばしいことにストリーム処理の２種類の実行形態について展望が示されていた。
その記事ではKafkaのような再送可能なコンポーネントをストリーム処理間で挟むことにより、単一のジョブ／パイプライン定義でデータ処理を実現するKappaアーキテクチャにつながる概念が示されていた。概念自体に名前が必要かどうかは微妙なところだが、その概念自体は全面的に賛同する。

実際のところ、適切に設計されたストリーム処理システムの持つ機能はバッチ処理システムの上位集合になると私はこの記事で主張する。実際、Flinkは「バッチモード」の動作であっても中身自体は全てストリーム処理の機構の上で動作している。この機構は素晴らしい。

その結果、無限のデータ処理のため構築され、当初は堅牢なデータ処理基盤と組み合わせることが必須だったストリーム処理システムは成熟するにつれ、ラムダアーキテクチャを過去のものにできる。実際それは現実味を帯びてきていると考えている。実際のところ、自前でバッチ処理を行う際に必要になる要素は下記の２つだと思われる。

- 1.正確性:バッチと同一の結果

本質的には正確性は一貫したストレージに落とし込むことが出来る。ストリーム処理システムは状態をチェックポイントとして保存する手段が必要で、その手段はマシン障害が発生した場合でも一貫性を保つ必要がある。Spark Streamingが公開された数年前の当初、Spark Streamingは暗雲立ち込めるストリーム処理の世界における一貫した篝火だった。だが、最近は強い一貫性を持たずに乗り切ろうとするストリーム処理も多い。だが、実際のところ、At most onceでものになるとは思えない。
繰り返すが、なぜこのポイントが重要かというと、強い一貫性を持ったデータ保存手段はExactly Onceを実現するためには必須の要素であり、この要素を守ることで、ストリーム処理がバッチ処理を上回る可能性につながる。あなたがストリーム処理の結果の厳密性を気にしないという状態でもない限り、強い一貫性を持った状態保持機構を持たないストリーム処理システムを排除することをお勧めする。バッチシステムは正しい答えが取得できるか否かを事前に気にする必要はない。同様の性質を満たせないストリーム処理で時間を浪費しないことをお勧めする。
もしストリーム処理システムにおける強い一貫性について気になるなら、MillWheelとSpark Streamingの論文を読むことをお勧めする。これらの論文は両方一貫性の重要性について深く述べている。

- 2.時間について推測可能なツールであること

これはバッチを超える要素となる。
処理時間が推測可能なツールは無限の、非ソートで偏りのあるデータを処理する上では重要な要素となる。最近の爆発的に増大するデータは既存のバッチシステムの機能をオーバーし、ストリーム処理システムと同等の時間推測性を満たすことが困難になっている。以後とその次の記事ではそのポイントに焦点を当てて説明する。
まず初めに、時刻領域について基礎的な理解をする必要がある。その後、無限かつ非ソートで偏りのあるイベントデータをについて掘り下げる。残りはそれらのデータに対してストリーム処理とバッチ処理を用いた場合の共通的な手法について述べる。

#### 発生時刻 vs. 処理時刻

説明できるレベルで無限のデータ処理について理解するためには、時刻ドメインに対する明確な理解が必要。あらゆるデータ処理システムにおいて、「時刻」というと下記の2つが存在する。

- 発生時刻: 実際にイベントが発生した時刻
- 処理時刻: イベントがシステムに到着した時刻

全てのユースケースにおいて発生時刻が必須というわけではないが、大体のケースにおいて考慮する必要はあるだろう。発生時刻を用いる必要がある例としては、Billingや、異常検知といったアプリケーションがある。

理想的な環境においては、発生時刻と処理時刻は常時同じ値となり、Eventが発生した直後に処理されていることになる。ただ、実際はそのように甘くない。加えて、発生時刻と処理時刻のずれはゼロでないだけでなく、入力ソースや実行エンジン、ハード等の構成によって変動する。そのずれは下記のような要素を内包する。

- 共有リソースの制限：ネットワーク混雑や分断、CPUの共有
- Softwareの要因：分散処理のロジックや競合
- データの性質：キーの分散偏り、スループットの分散、到着状況の分散（例えば、しばらく端末を機内モードにしておけば、その間に発生したイベントの到着は遅れる）

結果として、実世界システムの発生時刻と処理時刻の処理進行状況を図に示すと、Figure1の赤線のようになる。

![Figure1.jpg](https://qiita-image-store.s3.amazonaws.com/0/9616/8f43f5c8-eafb-4818-2935-4944f1d17612.jpeg)
**Figure1 時刻ドメインのマッピング例**
*X軸がシステムにおける、ある発生時刻に対する完全性を示す。ある時刻Xのデータを全て処理完了した場合、X軸上の値が進行することになる。Y軸は処理時刻の進行を示す。基本は処理システムにおいてそのデータを観測した時刻となる。*

黒い点線は理想的な、発生時刻と処理時刻は常時同じ値となっている状況となる。だが、実世界のアプリケーションでは赤線のようになる。実際のこの例では、黒い点線と赤線のずれは初期の段階と、グラフの真ん中ほど、あとはグラフの最後で非常に理想的な状況に近づく。黒い点線と赤線の差分は、発生時刻と処理時刻間のずれの値となる。このずれは主に処理パイプラインの中で発生する。

発生時刻と処理時刻とのマッピングは静的ではない。このことは発生時刻を気にする場合、あるEventを観測したコンテキスト内でデータが全てそろい、分析できるわけではないという形で専ら現れる。厄介なことに、これは無限のデータを分析するためのデータであっても対応しきれているわけではない。実際に無限のデータ群を扱うにあたり、入力データに対して何かしらのWindowの概念が導入されることが多い。以後で説明を述べるが、Windowingは無限のデータを何かしらの一時的な境界に沿って区切ることを意味する。

もし、データ解析において発生時刻を厳密に用いる必要があるなら、処理時刻を用いたWindowを用いることは本来はできないが、実際のシステムではそういう設計になっている。発生時刻と処理時刻の間の相関制御がない場合は、いくつかのイベントは異なる処理時刻 Windowに含まれて実行され、正確性に影響を与える。この問題については次の投稿で詳細を説明する。

だが、さらに厄介なことに、発生時刻 Windowingは無限の、非ソートで偏りがあるというデータの文脈においては、完全性に対する問題を誘発する。どれだけずれがあるのかはわからない中で、どのように「この発生時刻までのデータの処理は完了している」と言えるのか？実世界のアプリケーションにおいてはそう簡単には実現できない。実際のところ、現状のデータ処理システムはその完全性においては一定の仮定／制約を置く形となっているが、これは無限のデータを扱うにあたっては大きな欠点にもなる。

無限のデータを有限のバッチに区切り、結果としてデータが揃う形にするのではなく、実世界の複雑で不確定なデータでやっていくためのツールを設計するべき。新しいデータが取得されたら、古いデータが更新されたり破棄される可能性があるため、あらゆるシステムはデータの完全性を維持するために、データのセマンティクスを固定するよりはそういった性質を持つデータに追従し続ける方が望ましい。

Cloud Dataflowで使用しているデータモデルを用いるようなシステム構築について掘り下げていく前に、背景情報の共通的なデータ処理パターンについて補足しておく。

## Data processing patterns

時刻という観点で、有限データ無限データ共通で用いることができるコアとなる利用パターンを説明する。
バッチ処理とストリーム処理の２パターンについて処理と関連する諸事項について確認する。

#### Bounded data

有限のデータを処理するのは誰もがわかるように、シンプルなものとなる。
下記の図のように、図の左側に存在しているデータ全体に対して処理を適用すればいい。
このようなケースを扱うには、MapReduceをはじめとしたいくつかのデータ処理エンジン（バッチ処理基盤か、適切に設計されたストリーム処理基盤）で対応可能で、図の右側には入力を元に作られた新たな構造化データが出力される。

![Figure2.jpg](https://qiita-image-store.s3.amazonaws.com/0/9616/f5808754-6d31-30fb-a255-35c86795a14e.jpeg)
**Figure2 有限のデータを伝統的なバッチ処理エンジンで処理する際の構成**
*有限の非構造データ（左）をそれに対応した構造化データ（右）に変換*

しかし、もちろんのこと実際にこのデータの処理を行うにあたり、無限のバリエーションが存在するものの、全体としてのモデルは非常にシンプル。
そのため、無限のデータセットを処理するタスクの方がより興味深い。
では、この無限のデータセットを処理するためにとることのできる様々な手段について、伝統的なバッチエンジンから、よりそちらに向く構成として設計されているストリーム処理エンジン／マイクロバッチ処理エンジンまで見ていこう。

#### Unbounded data - batch

バッチ処理エンジンは無限のデータを前提にして設計されたものではないが、初期は無限のデータに対して処理をする際に用いていた。
予想されるように、このアプローチはバッチ処理可能とするために無限のデータを一定の期間で区切った有限のデータの集合とし、バッチ処理で順次処理していくものとなる。

#### Fixed windows

無限のデータをバッチ処理の繰り返しで処理する際に共通的な方式は、入力データを固定サイズのWindowに区切る方式となる。
特に入力データがログのような存在の場合、ディレクトリ名やファイル名で単純に区切ることができ、そこには時刻ベースのソートも行われた状態になっているため、区切り方は単純な構成となる。

しかし、実際のところほとんどのシステムはこのようなシステムで完全性を維持するためには課題がある。
もし、ログ出力がネットワーク分断によって遅れた場合はどうなるか？もし処理する前にシステム全体からイベントを共有の場所に集約しなければならないとしたらどうなるか？モバイルデバイスからのログだった場合は？これは、ソートする際に何かしらの緩めるような緩和のアプローチをとる必要があることを意味する。（もし、ある時間帯のすべてのイベントを収集し終わるまで処理を遅らせる場合、データが遅れ続ければ処理することは出来ない。）

![Figure3.jpg](https://qiita-image-store.s3.amazonaws.com/0/9616/d1c3cfe6-b3df-e44c-34be-b139689b47bc.jpeg)
**Figure3 無限のデータに対して固定Window長の従来のバッチ処理を実行**
*無限のデータを有限になるよう、固定サイズのWindowに区切って処理する構成*

#### Sessions

セッションのような、より洗練されたウィンドウ分割を行って無限のデータをバッチで処理しようとすると、より課題は大きなものとなる。セッションは一般的には特定ユーザに対する活動期間と非活動期間の差分を基に定義される。典型的なバッチエンジンで処理しようとした場合、しばしばセッションはバッチを跨いで処理する必要が出てきてしまう。（図の中の赤の箇所のように）バッチサイズが大きくなるにつれて、分割数は小さくなっていくが、その分処理のタイミングは遅れてしまう。もう一つのオプションは前回実行時に終了しなかったセッションを前回結果から集約する特殊ロジックを追加することだが、これは複雑さがさらに増大する。

![Figure4.jpg](https://qiita-image-store.s3.amazonaws.com/0/9616/e9d2cfb1-b13d-e845-f5a2-f97574bc5f6d.jpeg)
**Figure4 無限のデータに対して固定Window長の従来のバッチ処理を実行し、Sessionに区切る例**
*無限のデータを有限になるよう、固定サイズのWindowに区切って処理する構成を取った場合、SessionがWindowを跨いでしまう例*

セッションを扱う際に古典的なバッチエンジンを用いた場合、理想的な計算をすることは困難。よりよい手法は、ストリーム処理の作法に則ってセッションを構築すること（詳細は後述）。

##### Unbounded data — streaming

大体のバッチベースの無限のデータ処理手法のアドホックなやり方に対して、元々ストリーム処理システムは無限のデータのために構築されている。前述したように、多くの実世界のアプリケーションにおいては分散したデータソースが存在しており、そのようなデータを扱うにつれて以下のような性質を持つケースがあるのがわかるだろう。

- 発生時刻に関してソートされていないデータ
  - これは時刻順に処理したいようなデータ処理パイプライン上で実際には時刻順でないイベントが流れることを意味する。
- 様々な発生時刻の偏り
  - これはこのくらいの期間の間にこれだけの量のデータが来るということをあらかじめ想定することができないことを意味する。

これらの特徴を持つデータに対してはいくつかアプローチが存在する。ここではそれらのアプローチを下記の４グループに分類する。

- 時間非依存化
- 近似値使用
- 処理時刻ベースのWindowing
- 発生時刻ベースのWindowing

これらのアプローチについてみてみる。

#### 時間非依存化

時間に依存しない処理構成は本質的に時間と無関係のデータに使用される。その場合、ストリーム処理で処理する際には特別な対応は不要で、単に到着した順に処理すればいい。ただ、ストリーム処理はそもそもこのような時間に依存しない処理はあまり考慮していない。このようなケースにおいては、バッチ処理の方が無限データを一定区間に区切って独立処理することが可能となり、より適切な対応が可能だろう。いくつか事例を確認するが、多くの時間はかけない。

##### Filtering

時間非依存の中での典型的なものはフィルタリングとなる。Webシステムのログを処理する際に特定ドメインを経由しないログを弾くケースを考えてみる。その場合、ログを取得した際に特定ドメインを経由してなければ弾く形になるだろう。このような場合、データはある１レコード単体自身にのみ依存し、他のデータへの依存は発生しない。

![Figure5.jpg](https://qiita-image-store.s3.amazonaws.com/0/9616/2359f3c1-b1e5-32ba-55dd-cf48afdb185c.jpeg)
**Figure5 無限のデータに対するフィルタリング**
*データ集合（左から右に流れる）をフィルタし、同質のデータに絞る構成*

##### Inner-joins

時間非依存の処理のもう一つの事例はInner-join(またはhash-join)がある。ある２つの無限のデータをjoinするとき、時間的な要素は発生しない。ある１つのソースからデータが到着したら、それを単純に保持しておき、２つ目のソースから到着した際にjoinして出力すればいい。（実際のところ、片側のソースからのデータが蓄積していくと、時刻ベースのケースのように、あふれるようなケースも発生しえる。）

![Figure6.jpg](https://qiita-image-store.s3.amazonaws.com/0/9616/69a465f7-67c7-dfaa-922e-153b889aefd1.jpeg)
**Figure6 無限データに対する内部結合**
*複数のデータソースから発生したデータが揃った場合に結合する構成*

だが、Outer-joinのセマンティクスを取る場合、データが揃わない問題について考える必要が出てくる。だが、対応するデータがこの後到着するか否かについては実際のところ分からない。そのため、時刻ベースの処理のように、何かしらのタイムアウトの機構を入れ込む必要がある。この時間要素はWindowingでくわしく述べる。

#### 近似値使用

![Figure7.jpg](https://qiita-image-store.s3.amazonaws.com/0/9616/39f95c42-061c-3d5c-a977-e1360eeb7dde.jpeg)
**Figure7 無限データに対する近似処理**
*複雑なアルゴリズムを通し、入力データは足りないものの、それを問題ない内容に近似させる構成*

二つ目の時間非依存のアルゴリズムとしてはTop-NやストリームK-Means等の近似アルゴリズムとなる。近似アルゴリズムは無限の入力ソースを取得し、望んでいたものを実際に望むよう近似させて提供する。設計上の利点は、近似アルゴリズムを適用することで全体のオーバーヘッドを低減させることが可能であること。欠点は、その近似結果を得るために適用されるアルゴリズムが複雑であること。そのため、再利用性には欠ける場合が多い。

注目すべき点として、これらのアルゴリズムには典型的には時間に絡む要素を持っており、到着したタイミングで処理し、基本は処理時刻を用いて処理が行われること。これは誤差を一定の範囲内に収めるためにアルゴリズムをどう設計するかが重要なポイントとなる。これらの誤差範囲が到着順に処理するデータに基づいて予測されている場合は、ソートされていないデータや偏りは特に問題にならない。

近似アルゴリズムは興味深いものの、本質的には時刻非依存のもう一つの事例でしかない。有用ではあるものの、この先においては焦点としない。

#### Windowing

残る２つの無限のデータに対するアプローチは両方Windowingの派生パターンとなる。これらの違いの差分を詳しく見ていく前に、Windowingとは何か、を明確にしておく。Windowingとは、単純に言うとデータソースからデータを取得する際の概念で、一時的な境界を設けて処理用に有限の塊に切り分けることをさす。以下の表で、３つの異なるWindowingのパターンについて示している。

![Figure8.jpg](https://qiita-image-store.s3.amazonaws.com/0/9616/0bafa73e-c7d0-5509-62e4-ea4241cff42b.jpeg)
**Figure8 Windowing戦略例**
*無限のデータに対するある３つのキーに対するWindow分割例。ここでは整列されたケースと整列されないケースがあることに注目*

- Fixed windows

Fixed windowsとは、時間を固定長で区切って使用するもの。典型的には、fixed windowsはデータセット全体に対して均一な区切りを作成し、これはaligned windowsの事例となる。いくつかのケースにおいては、Keyをベースに分割するなどの異なるサイズを持つWindowに分割することもある。これらはデータ毎に異なるものの、時間で整列できないWindowを用いるよりは余程適切に負荷分散が可能。

- Sliding windows

Fixed windowsを一般化すると、Sliding windowsは固定長と固定の区間を持つものとして定義される。もし区間よりも長さの方が大きい場合、その部分はwindow同士でオーバーラップすることとなる。区間と長さが等しい場合、Fixed windowsとなる。もし区間の方が長さよりも大きい場合、多少奇妙なサンプリングWindowとなり、データ全体から一部を抽出するものとなる。Fixed windowsと同じく、Sliding windowsも典型的なものは整列されているものの、特定のユースケースにおけるパフォーマンスの最適化のために非整列状態で用いることもある。尚、図を見ると一部のデータを区切っているように見えるかもしれないが、Sliding windowsの区切りはデータ全体に対して実施される。

- Sessions

動的なWindowsの例として、sessionsはいくつかのタイムアウト時間のようなアクセスタイミングの抜けによって、開始～終了までのイベントのシーケンスで構成される。Sessionsは時間と共にユーザがどのようなふるまいをしたかを、関連するイベントを紐づけて分析をする。興味深い点として、Sessionsへの解析を行う場合、その関連するイベントの時系列的な長さは事前に予測することは出来ず、あくまで実際に発生したデータに依存する形になる。Sessionsは実質的に異なるサブセットのデータ間で決して同じにならないため、非整列Windowの標準的な例となる。

二つの時刻に対するドメインとして、処理時刻と発生時刻があるが、これについて２つがどう違うのかを今後見ていく。処理時刻ベースのWindowingの方が既存のシステムにおいてはよくみられる存在のため、まずは処理時刻ベースの方から。

##### 処理時刻ベースのWindowing

![Figure9.jpg](https://qiita-image-store.s3.amazonaws.com/0/9616/fef98ab1-0e4c-7fef-2850-68e2cf998420.jpeg)
**Figure9 処理時刻ベースの固定長にWindowingした例**
*無限データを処理時刻ベースの固定長にWindowing分割した場合の構成*

処理時刻ベースでWindowに区切る場合、システムは本質的にはその時間が経過するまで入力データをバッファリングしておくというアプローチをとる。例えば、5分の固定長Windowに区切る場合、システムは入力データを処理時間が5分経過するまでバッファリングし、経過した後にその区切りを以て下流に送るために処理する形になるだろう。

処理時刻ベースのWindowingにはいくつかの優れた点がある。

- シンプルである

実装は非常にシンプルで、データの入れ替わりについて気にする必要はない。到着した順にデータを処理し、結果を出力すればいい。

- データがそろっているかの判定が簡単

システムはある一定期間のWindowについて、完全な情報を得ることができ、データを全て受信したかどうかについても判断できる。これはつまり処理時刻で処理する限り、"遅れた"データについて扱う必要がないということにもなる。

- データソースについての情報が欲しい時、それを厳密に算出できる

サイトに対する毎秒のリクエスト回数を算出したいとする。その場合、処理時間Windowingなら一定時間内に処理したリクエスト数をカウントすることで、障害検出などの目的を果たすことができる。

だが、いい点に対して、処理時間Windowingには大きな欠点がある。
もしデータ解析で「発生時刻」に関連する質問が出た場合、「発生時刻」の順にデータがデータソースに入力されない限り、処理時刻Windoingでは実際の値を算出することができない。とはいえ、厄介なことに実際のところ、分散したデータ発生元が存在するケースにおいて、「発生時刻」順にソートされたデータは実世界では基本的に存在しない。

簡単な例として、モバイルアプリから情報を収集して、利用状況の統計算出を行うケースを考えてみよう。モバイルデバイスはしばしば、予期せずオフライン状態に突入する。（接続断、飛行機に乗って移動する際の機内モード等）　その間に記録されたデータはモバイルデバイスがオンラインに復旧するまで送信されない。　これは、データが到着した時と、実際の時刻は分、時刻、日、週単位（あるいはそれ以上）ずれることになることを意味する。これが処理時刻Windowingにおいて、実際に「発生時刻」でソートできない理由である。

他の例として、分散したデータソースが存在し、システム全体が正常であるという前提のもとでは発生時刻ベースでソート（または、それにきわめて近い）状態のデータが収集される環境を考えてみる。だが、正常である状況でソートされた状態で提供されるというのは、常にそうであるというわけではない。複数の大陸に分散したサービスを扱うということは、ネットワーク帯域の変動や問題が発生する際にずれが拡大し、予期しない領域に達することもある。そのような状況で処理時刻をベースにWindowingを行うということは、発生時刻の観点で見た場合に、古いデータと新しいデータを混ぜて処理することになる。

このようなケースにおいて、我々が欲しているのは本来は発生時刻から到着までに時間がかかっても対応可能な頑強な方式。それを満たすのは発生時刻ベースのWindowingとなる。

##### 発生時刻ベースのWindowing

発生時刻ベースのWindowingにおいては、データソースから有限の量に区切って取得したデータを、実際にイベントが発生した時刻に反映する必要がある。これはWindowingの最も大事な基準。だが、悲しいことに今日使用されているほとんどのデータ処理システムはその機構をネイティブでサポートしていない（HadoopやSpark Streamingのようなまともな一貫性モデルを保持したシステム実行基盤においては、そういった機構を作りこむことは出来るものの）

以下の図は無限のデータソースを1時間ごとのWindowに区切ったWindowingの一例。

![Figure10.jpg](https://qiita-image-store.s3.amazonaws.com/0/9616/163a4caa-c56f-274e-e262-3a33eaab0cbf.jpeg)
**Figre10 発生時刻ベースの固定長にWindowingした例**
*無限データを発生時刻ベースの固定長にWindowingした構成。白い線で、実際の発生時刻と処理時刻のWindowが異なる例を示している。*

図中の太い線が個別データの興味深い点を示している。この２つのデータは処理時刻Windowingで区切った場合、実際の発生時刻とことなるWindowで処理されてしまう。そのため、発生時刻に厳しいユースケースにおいて処理時刻Windowingで処理をした場合、実際とは違う結果が算出されてしまう。予想されるように、発生時刻の正確さは発生時刻Windowingで大きな利点となる。

他の無限データに対する発生時刻Windowingの利点として、動的にサイズ調整を行うWindowを作成可能ということがある。Sessionのような事例においてはある固定の任意のWindowサイズでデータを区切ることができない。（前述のとおり）

![Figure11.jpg](https://qiita-image-store.s3.amazonaws.com/0/9616/d558ab98-9ade-d299-6ef1-34cada7a859d.jpeg)
**Figure11 発生時刻ベースのSession用Window分割**
*データを発生時刻ベースでSessionのWindowに区切る際の構成。白い線で、実際の発生時刻とSessionが異なる例を示している。*

もちろん、こういった強力なセマンティクスは容易には実現できないし、発生時刻を用いる限り例外はない。発生時刻Windowingは実際の処理時刻よりも長くWindowを保持する必要が出てくるため、２点の忘れてはいけない欠点が存在する。

- Buffering

Windowの生存時間が延びるため、より多くのデータをバッファリングする必要が出てくる。ありがたいことに、永続化ストレージは他の処理リソース（CPU、ネットワーク、帯域メモリ等）に比べると安価なリソースとなる。そのため、この問題への対処は強一貫性ストレージと既存のメモリ上キャッシュを搭載したシステムを考えるよりはシンプルとなる。また、いくつかのデータ統合処理においては、すべてのデータ確保しておく必要はなく（sumやavg等）、代わりに集計結果をインクリメンタルに更新しながら保持していればいい。

- Completeness

現状、あるWindowに対するデータがすべて到着したかを認識するためにいい手法はない。そのため、「どのタイミングでWindowを出力すればいいか？」に困る。実際のところ、それについては明確な解はない。多くの形式のデータ入力に対して、MillWheelで行われているように、経験則的な判断をするほかない。（詳細は次の記事で述べる）

そのため、正確さが最も重要なケース（特にBilling等）における唯一の現実的な選択肢はWindowの出力結果を後から更新するための手段を提供すること。その上で、データが遅れて到着するごとに出力結果が更新することが求められる。このようなWindowの完全性をどう扱うかは非常に興味深いトピックだが、これは具体的な例とともに、次の記事で述べる。

## 結論

多くの情報が述べられているが、ここで一度振り返ってみよう。
その上で、次の記事でより深く掘り下げていく。
この記事は退屈であったかもしれないが、その分次の記事は興味深い内容から始めることができる。

#### まとめ

この記事をまとめると下記になる。

- 技術の明確化のために、"ストリーム処理"を実行エンジンに対して狭義の明確化を行い、関連する用語、無限のデータや近似・投機的な結果はストリーム処理とは異なるものであるということを説明した。
- 優れた設計で構築されたバッチ処理システムとストリーム処理システムの対比から、ストリーム処理はバッチ処理の純粋な上位互換な存在であり、ラムダアーキテクチャのような概念からくる、ストリーム処理がバッチ処理に劣るような考えについては、ストリーム処理が未成熟だったから発生したものであるということを説明した。
- ストリーム処理がバッチ処理を上回るために必要になる２つの要素、「正確性」と、「時間について推測可能なツールであること」について提案した。
- 発生時刻ベースと、処理時刻ベースの２つの時刻の概念とその違いと、その違いからくる困難さについて示した。そこから、このような発生時刻ベースのデータ処理を行う場合、完全を確立することは出来ないため、データが到達するごとに時刻を越えて結果を更新する手法について提案した。
- データ処理を行う際の共通的なパターンとして、時間非依存なケース、近似結果を求めるケース、処理時刻ベースのWindowing、発生時刻ベースのWindowingについて示した。

続きは次の記事をお楽しみに。

* * * 

*著者： [Tyler Akidau](https://www.oreilly.com/people/09f01-tyler-akidau)*
*本投稿： kimutansk*
![License.jpg](https://licensebuttons.net/l/by-nc-sa/3.0/88x31.png)

# この記事をご覧の方に

この記事の続きは下記になります。良ければご覧ください。

- **[【要約】The world beyond batch: Streaming 102](http://qiita.com/kimutansk/items/c6b7cccd976ff00cb1fd)**