抄訳 MillWheel: Fault-Tolerant Stream Processing at Internet Scale(2013)

November 23, 2022

MillWheelは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が大きくなりそう。