kenju's blog

About Programming and Mathematics

Google Advertising Systemで使われているストリーム処理アーキテクチャ"Photon"

Photonは、Google Advertising Systemで使われている、ストリーミングデータの処理システムの別称。

Photon is deployed within Google Advertising System to join data streams such as web search queries and user clicks on advertisements. It produces joined logs that are used to derive key business metrics, including billing for advertisers.

広告配信におけるCTR予測ロジックの論文を読んでいた時に参考文献として書いてあって知った。本質的には広告は関係なくて、リアルタイムで、順序関係なく送られてくるストリーミングデータの整合性を担保し、各チャンクのストリームを結合するためのアーキテクチャ

Paperは https://static.googleusercontent.com/media/research.google.com/ja//pubs/archive/41318.pdf から読むことができる。

論文メモ

Photon is...

  • Photonとは、地理的に分散しているシステム間で、ストリーミングデータを、リアルタイムで、結合する仕組み

Advertising Systemにおける利用例

  • Google Advertising Systemにおいて、検索クエリログとクリックログを同じユーザーのデータで分析可能な形にJoinするために利用されている
  • 広告は、利益に直結するため高い整合性も求められることに加え、高いレイテンシとスケーラビリティが求められる。それを解決するために考案されたのがこのPhotonというアーキテクチャ
  • すごくシンプルなIN/OUT:query_idを用いて、Query EventとClick Eventを紐付け、Joined Click Eventとして出力する

f:id:itiskj:20171224115706p:plain

IdRegistry

f:id:itiskj:20171224120710p:plain

IdRegistry Server Architecture

f:id:itiskj:20171224121211p:plain

Sharding

  • event_idの独立性を活かして、各IdRegistryはシャーディングされている
    • "To take advantage of the event_id independence, we partition the event_id space handled by the IdRegistry into disjoint shadrds such that event_ids from separate shards are managed by separate IdRegistry servers"
  • シャード数は動的に変更される
    • "we use a timestamp-based sharding configuration, which defines the number of shards to use at any given instance of time"

f:id:itiskj:20171224122313p:plain

Dispatcher/Joiner/EventStore

  • Query EventとClick Eventを結合する部分のより詳細な設計
  • Dispatcherが、JoinerにClick Logsを送る。この時、at-least-once semanticsを担保するために、Joiner側にログが送信できたことを確認するまで送信リトライする
    • Dispatcherは、at-lease-semanticsを担保するためのメカニズム
  • JoinerがEventSource/Dispatcherから送られてきたログを結合し、結合に成功したらIdRegistryにclick_idを挿入する
    • この時IdRegistryを参照し、すでに結合されているかどうかをみて一意性を担保する
    • Joinerは状態を持たない、一意性の担保はIdRegistryの責務とする f:id:itiskj:20171224121703p:plain

参考

Photon: Fault-tolerant and scalable joining of continuous data streams

他にもPhotonについてブログ記事を書いている人がいた。