The Dataflow Model を読んだ

The Dataflow Model: A Practical Approach to Balancing Correctness, Latency, and Cost in Massive-Scale, Unbounded, Out-of-Order Data Processingを読んだ

どんなもの？

• unbounded で順不同なデータを処理する上で、正確性、latency、costをいい感じにするアプローチについての考察

先行研究とくらべて何がすごい？

• 既存の考え方では、unboundedなデータに終わりがあると考えているのがおかしい
  • データの総量がどれくらいで、全てのデータがいつ揃うかということは考えない
  • ただ新しいデータが来て、古いデータは撤回されるということだけを考える

技術や手法の肝は？

• 下記が肝
  • windowing model
  • triggering model
  • incrementral processing model
  • scalable implementation

• Windowing
  • データセットを処理の固まりに分けていくこと
  • 時間ベースで分割する
  • 3種類のwindow
    • fixed
      • 固定長のwindow(時間、日)
      • windowはオーバラップしない
    • sliding
      • 固定長のwindow
      • 時間でslideしていく
      • windowはオーバラップする
      • fixed windowはsliding windowの特殊な場合
    • session
      • activityのある期間をcaptureしたもの
      • timeoutまでの期間を定義する

• Time domain
  • Event Time
    • イベントが実際に起こった時間
  • Processing Time
    • pipelineでそのイベントが観測された時間
• Window Mergingの流れ

• Triggers & Incremental Processing

  • Windowing
    • event timeのどの時点でデータがグループ化されるのかを決定する
  • Triggering
    • processing timeのどの時点でグループ化の結果がemitされたかを決定する

どうやって有効と検証した？

• FlumeJavaとMillWheelを用いて、Googleの実際のプロダクトに実装した
  • Youtube(Session window), Recommendation(Processing Time Triggers)等

議論はある？

次に読むべき論文は？

MapReduce: Simplified Data Processing on Large Clusters