ストリームでのウィンドウ集計：タンブリング(Tumbling)、ホッピング(Hopping)、スライディング(Sliding)ウィンドウ
リアルタイムストリーム処理の話でよく出てくる以下のウィンドウ集計について、パッとわかる日本語の説明がなかったから認識を書いてみた。
各項目最初の2, 3行でつまりなんなのかを説明しようとしているが、それ以降はちょっと細かい話なので混乱したくない場合は見ない方がいいかも。
時間軸での集計前提。
タンブリングウィンドウ集計
一言でいうと「一定時間ごとの集計」。
例えば10秒毎の流れてくるツイートを知りたいといったときにはタンブリングウィンドウ集計を選択することになる。
このウィンドウ関数を起動してから10秒たったらその10秒間のツイート数が、さらにその10秒後にはその10秒間のツイート数が取得できる感じ。
ポイントは1つのイベントは1つのウィンドウにしか属さないということ。「オーバーラップしない」と表現されるかもしれない。
10秒のサイズのタンブリングウィンドウ集計結果を1時間貯めて足し合わせると1時間のイベント数が漏れ無く重複なくわかる。
これはストリーム処理というかどちらかというとバッチ処理のイメージに近い。デイリー集計とかアワリー集計とかだ。
タンブリングウィンドウ集計が明確にアワリー集計などと違う1つのポイントは、タンブリングウィンドウの場合集計タイミングがウィンドウ関数実施のタイミングに依存することだ。
アワリー集計の場合は起動タイミングに関わらず例えば3時台の集計であれば3時0分0秒から3時59分59.999...秒までの集計ということになるが、1時間のサイズのタンブリングウィンドウ集計の場合、それを2時10分に起動していたなら3時～4時直前の集計結果は取得できず、3時10分から4時9分59.999...秒の集計結果は取得できることになる。
タンブリングウィンドウ集計のために与えられる引数は1つで、ウィンドウサイズ（時間）だけだ。ここで与えられた値が10秒なら、10秒間の集計結果を10秒毎に出力することになる。
ホッピングウィンドウ集計
一言でいうと「一定時間ごとに出力する最近一定時間の集計」。
例えば5秒ごとに最近10秒間ののツイート数を知りたいといったときにはホッピングウィンドウ集計を選択することになる。
このウィンドウ関数を起動してから5秒たったタイミングでの最近10秒間のツイート数が取得でき、さらに5秒たつとそのタイミングでの最近10秒間のツイート数が取得できる。
この5秒というのはウィンドウが前進する時間と言える。英語でホップサイズとかアドバンスなんとかとか出てきたらたぶんこのことだ。
タンブリングウィンドウと異なる点は1つのイベントは複数のウィンドウに属し得るということだ。「オーバーラップする」と表現されるかもしれない。
ホップサイズ5秒ウィンドウサイズ10秒のホッピングウィンドウ集計結果を1時間貯めて足し合わせると、1時間分のイベント数集計としては漏れは無いが大量に重複する。そのため1時間分の集計としては全く正しくない。
ユースケースについては項目の最初に例を書いたが、このような性質のためタンブリングウィンドウ集計のユースケースとはかなり異なる。
タンブリングウィンドウよりこちらはずっとストリーム処理的な感じがする。
ホッピングウィンドウ集計のために与えられる引数は2つで、ウィンドウサイズとホップサイズだ。
実はこのウィンドウサイズとホップサイズが同じだとタンブリングウィンドウになる。両方とも10秒であれば、10秒間の集計結果を10秒毎に出力することになって、イベントは複数のウィンドウに属さなくなる（オーバーラップしない）。
スライディングウィンドウ集計
一言でいうと「いつでも出力できる最近一定時間の集計」。
例えば知りたいと思ったときに最近10秒間のツイート数をわかるようにするにはスライディングウィンドウ集計を選択することになる。
これは普通にブラウザからツイッターにアクセスしてトレンドを見ることと同じイメージだ。
ツイッターは実際にはより複雑なロジックでトレンドワードを出力していると思うが、単純化して考えれば、僕たちがWebページにアクセスした瞬間の最近1時間のツイート人気ワードが出ているようなものだ。
スライディングウィンドウ集計にはホップサイズが無いので与えられる引数はウィンドウサイズだけだ。
実はスライディングウィンドウはホッピングウィンドウと同じだ、と言われることがある。
ホッピングウィンドウのホップサイズ微小時間版がスライディングウィンドウだという立場だ。
スライディングウィンドウのイメージを掴むのであればこの認識で問題ないと思うのだが、厳密には違う。
厳密部分についてここから自分の認識を書くが、この認識は相当怪しいし、混乱するだけかもしれないのでご注意。
実はスライディングウィンドウとホッピングウィンドウは仕組みが根本的に違う。
ホッピングウィンドウはホップサイズ毎にウィンドウが確定して、ウィンドウがたくさんあるイメージなのだが、スライディングウィンドウというウィンドウは1つしかなくて、そのウィンドウがスライドし続けているイメージだ。
ホッピングウィンドウ集計は起動すればホップサイズ毎に結果をプッシュしてくるが、スライディングウィンドウ集計は起動するだけでは結果をプッシュしてこない。スライディングウィンドウはただその時の状態を持っているだけで、クライアントが問い合わせるとはじめてその状態が返ってくる。
スライディングウィンドウ集計は3つの中では一番ストリーム処理的な集計だと思う。
タンブリングウィンドウ集計とホッピングウィンドウ集計の実装は専用のフレームワークを使わなくても直感的で簡単だ。しかしスライディングウィンドウ集計を自分で実装しようとすると途端に難しくなる。
流れてきたイベントを（集計中の）状態に加算するだけでなく、ウィンドウから外れた（期限切れになった）イベントを減算しなければいけないからだ。
例えば10秒のサイズのスライディングウィンドウ集計を実装する場合、単純に考えれば集計状態をプロセスのメモリに持って、イベントがきたらスレッドを作って、そのスレッド内で集計状態をすぐに加算、その後10秒だったら減算すればよい。
しかしこの方法はちょっと考えてもスレッド数が爆増する。データ量が10 Events per second(EPS)くらいであれば問題にならないかもしれないが、千EPS、一万EPSとなってくるともう不可能だ。また、ウィンドウサイズを1時間にしたいとかになるとこれも問題になる。分散処理したとしてもあまりに非効率だ。
効率化するために工夫が必要になってくる。もっともSparkなどのフレームワークを利用すればこのような工夫を考える必要はない。
