MillWheel: Fault-Tolerant Stream Processing at Internet Scale(2013)
November 23, 2022MillWheelはGoogleで開発されたストリーミング処理のフレームワークである。 開発者が羃等な処理をノードとする有向グラフを実装すれば、MillWheelがデータをノードに正確に一回だけ配信する。 ただし、転送が遅延しているデータは破棄される。 データは、キー、値、論理的な時刻の3組からなるレコードを単位として、ノードからノードに出力される。 向き先のノードは、レコードからキーへの関数を、根のノードから出力されるレコードに適用し、期待するキーに対応するレコードをノードに集約する。
論文でMillWheelの動機付けにつかわれたGoogle’s Zeitgeistは、Googleトレンドの前身であり、急激に検索回数の変化したキーワードを検知する。 Zeitgeistであれば、検索キーワードをキーにし、同じキーワードの検索のレコードをノードに集約し、レコード数を数える使い方をする。
正確に一回だけの配信を保証だけでなく、処理の遅延を抑えなければならない。 MillWheelは、ノードごとにlow watermarkを設定し、low watermarkより前のレコードが遅れてノードに届いた場合、そのレコードを破棄する。 あるノードのlow watermarkは、ノードが処理中のレコードで最も古いtimestampか上流のノードのlow watermarkのうち、より古い方である。
ノードはレコードを受信すると、受信済のレコードとの重複がないか調べる。重複がなければ、処理を実行する。 処理に成功すれば、ノードは送信元にACKを返す。 送信元はACKが返るまで送信を繰り返すが、ノードの受信後からACKまでに受信元がクラッシュすると、受信元にレコードが届いていても再送を繰り返すおそれがある。 そのため、送信元は、レコードを送信する時にレコードにはユニークなIDを割りあてる。 受信元のノードは、受信したレコードのIDを調べ、ACK前の処理中のレコードを再受信しないようにする。
論文へのリンク
雑記
MillWheelは、Dataflowに影響を与えた。 Dataflowはウィンドウサイズの幅を変えることでバッチ処理もストリーミング処理も統一的に実装できる。
low watermarkは前のノード以上の時刻になるので、例えば深い有向グラフだと、一部のレコードの遅延で全体のlow watermarkが大きくなりそう。