http://tech.adroll.com/blog/data-science/2015/12/08/data-science_event_processing.html の翻訳というかメモです。

AdRollは大規模な機械学習をインターネット広告オークションのインテリジェントな入札に活用しています。このポストでは、私たちのエンジニアリングにおけるデータのパイプラインを紹介していきます。特に、イベントストリームをリアルタイムに扱う部分の学習のアルゴリズムに関して深掘りします。

Overview

もし、インターネット上で過去数年間、バナー広告をご覧になったことがある方は、リアルタイムビッディング(RTB)というプロセスを経て配信された広告におけるgood chanceです。

RTB-basedな広告配信の中では、その名の通り、Webページがロードされる度に、リアルタイムで広告スペースに関するオークションが行われています。AdRollはこれらのオークションを私たちのお客さまを代行しています。ad exchangeはWebページがロードされる度に私達に入札リクエストを送ってきます、そして私たちは入札価格をレスポンスします。RTBオークションに参加することにおいて、沢山のエンジニアリングおよびデータサイエンスの課題に遭遇します。AdRollのデータサイエンスチームでは、リアルタイムにインプレッションの価値を決定することに注意を払っています。

ハイレベルには、BidIQと呼ばれる大規模機械学習プロダクトを使ってこの課題に対応しています。私たちはインプレッションがクリックそしてコンバージョンされる確立を過去の以下のことより学びました。過去の入札リクエスト、入札リクエストに対する私たちのモデルを使った予測、そして、いくつかの機能通して行った入札およびそれに伴う他の変数。もし、私たちのモデリングと学習アルゴリズムにご興味があれば、Matt WilsonのFactorization Machinesというポストをご覧ください。

私たちは学習アルゴリズムに注力して沢山の機能を開発しました。その中でもメジャーなものは入札リクエストから派生したものです。これらの機能は以下のようなものを含みます: geo-location, ad network, inventory source, 私たちが配信した広告のインプレッション, 時間, その他イロイロ。他には、インプレッションの際のクッキーや、ユーザーの過去の行動のようなものもあります。私たちのevent-processingシステムは内部ではchocolate chip(クッキーだからね！)と呼ばれていて、入札時間の中でのコンピュートを可能にしています。

Chocolate Chip

個々のクッキー(プロファイル)をリアルタイムで扱う上での一つのチャレンジは、プロファイルはクッキーの中に入っているにも関わらず、入札リクエストの中で扱うことができない点です。すなわち、クッキーとプロファイルのマッピングをkey-valueストアを使って行う必要があります。コストとベネフィットの両方のアプローチがあります。1つはクッキーにリアルタイムにデータをストアする。もう1つはkey-valueストアにオフラインでのテストやデータ解析を行うフレキシビリティを与える。私たちは後者を選択することにしました。私たちはバックエンドのkey-valueストアにAmazon DynamoDBを選択しました。私たちは過去に似たようなユースケースにDynamoDBを使うことで成功を収めたことがあるからです。

コアな機能として、chocolate chipはイベントを取得し、プロセッシング後にプロファイルをDynamoDBに保存します。データサイエンスチームがデザインおよび構築を行ったシステムはAdRollの様々な場所で使われています。データサイエンスチームにおけるユースケースとしては、データストリームのイベントの中から予測を行う事と、プロファイルの書き込みを出来る限りリアルタイムに行うというものです。これらのプロファイルは入札者によって取得され、私たちの機械学習モデルに取り込まれ、より正確なクリックとコンバージョンの予測に活用されます。これらのデータを学習するためにそのプロファイルの入札時間をロギングします。Chocolate chipはD言語で作られていて、私たちが開発したハイパフォーマンスなDynamoDBクライアントも含みます。

プロファイルの構築におけるハイレベルなコンセプトはシンプルで: valueをDynamoDBから取得して、現状のイベントでプロファイルの情報を上書きして、そして、プロファイルに書き込むというものです。しかし、AdRollにおいてはスケーリングとパフォーマンスが必要であり、高度に並列され、いくつかの分散コンピューティングの方法をサポートしなければなりません。更に、HTTPリクエストの数と増え続けるスループットを抑えるため、私たちは処理を小さいバッチとして動かしています。

Architecture

Chocolate chipは複数のデータのストリームを取り込みます。それぞれのストリームはイベント毎に構成されています。それぞれのイベントはAdRollのログの1行で、全てのイベントタイプは統一されたフォーマットのログに保存されます。クッキーはハッシュとイベントタイプ毎に分散されたワーカースレッドで処理されます。コンカレントなreadとwriteを扱う上での考慮事項としては、常にデータの競合を避けるということです。特に、複数のコンカレントなクッキー毎のread-build-writeサイクルをDynamoDBに取り込みたくありません。さもないと他のサイクルで処理されたイベントで上書きされてしまうかもしれないからです。それぞれのワーカースレッドでパーティショニングされたクッキーを扱うことによって、データの競合を避けることができます。競合はとてもよろしくありません。なぜなら、activeなクッキーは一定数発生するはずで、そのイベントはイベントストリームにおいて近いところにいる可能性が高いからです。もしクッキーによって分けないのであれば、複数のワーカーは同じクッキーを同時に扱うことができます。しかし、クッキーによるシャーディングが複数のノードにわたって行っている場合、それは私たちのシャーディング基本形態ではなく、それぞれのデータストリーム自身がクッキーによって分割されていないことを意味するためレプリケーションが行われてしまいます。

Chocolate chipをスケールさせるには、イベントタイプごとにシャーディングする必要があります。DynamoDBの hash-and-range key typeをprimary keyに使うとすると、hash keyはクッキーのハッシュで、range keyはイベントタイプになります。このプロパティを使でノードを分けることができ、私たちはそれぞれのイベントストリームを扱って、分割されたサブレンジのキーでそれぞれのイベントタイプのプロファイルを構築することができます。私たちの入力ストリームは順序が保証されていないため、イベントから構築したデータは変換可能である必要があります。hash-and-range keyの方法を使うことで、私たちは関連イベントに制限されることになります。これが意味する所は、もし異なるイベントストリームから部分的に構築したデータであっても、本来の値に再構築可能であるということです。これは入札時間において複雑さをもたらすことになりますが、イベント毎にシャーディングして構築しても影響がでない、結合されていない、且つ、交換可能な方法が他に見当たりません。

ワーカースレッドがキューからイベントを読み込んだら、他の異なるクッキーからデータを集めたのちにストアします。DynamoDBはバッチ読み込み/書き込みをサポートしているため、私たちはバッチサイズを25で使用しています。25個の異なるクッキーが登録されたら(おそらく複数のイベントがそれぞれのクッキーに含まれています)、バッチ読み込みリクエストがマスターに対して行われて、プロファイルは更新もしくは生成(もし存在しなかったら)され、そしてキャパシティに問題がなければ、slaveに対するレプリケーションが行われます。

Example feature: Exponential Moving Average

いくつかのイベントの中で、直近のイベントが過去ののイベントよりも学習するのに価値があるものとします。私たちがそういったデータを捉えるメカニズムとしてよく使用していたのは、Exponential Moving Average(指数平滑移動平均線)です。なぜこの機能が用いられていたかというと、当初はsimple moving average(単純移動平均線)を使っていたからです。私たちは特定のクッキーに対して過去数時間(単純移動平均と呼ぶべき機能)の配信した広告の量をケアしています。これを計算するには、全てのインプレッションに対するタイムスタンプをストアして、そして過去の時間の入札時間をカウントします。1時間以上前のデータを遅延消し込みすますが、要点としては全てのイベントがストアされていなければならないということです。

低レイテンシでなければならい環境下で、このシステムオペレショーションにかかるメモリのコストは非常に高いです。入札時間において、プロファイルデータをDynamoDBからTCPコネクションを通じて取得しますが、レイテンシはプロファイルにおけるTCPパケットの数と比例します。もし沢山の機能がこのようであれば、パケット数は増大し、レイテンシは増加し、受け入れがたいものとなります。

上記のような背景から、EMB(指数平滑移動平均線)を使うことになりました。EMAは固定のメモリ量だけを使って最近発生した数のイベントのみを保存することができます。

EMAの計算式は:

少し数式を扱います。これは以下の再帰的な定義と同等となります。

私たちが現在のEMAのvalueのために必要とする計算は、前回のvalueとタイムスタンプと、現在のタイムスタンプになります。注意深くみると、EMAの範囲を越えたイベントを追加することもできるのが分かります。私たちはexponential decay factor(指数関数型減衰)を適応するだけで良いのです。私たちは2つ目の機能をEMAの機能を使ってコストをかけずに構築することができます; 前回のイベントのタイムスタンプをストアしなければなりませんが、ということは、私たちはこれを抽出して他の機能にも使えるということです。

私たちのケースでは、これをインプレッションのカウントに使っています。私たちはそれぞれの秒をみて、その秒の中にインプレッションがあれば値は1、なければ0という風にカウントしています。これは以下のように言うことができて:

これは

イベントのi回目のタイムスタンプとなります。

EMAは経過時間として使えるカウンターです。一方で、私たちは過去の時間に関するイベントのカウントを保証できません。ですが、私たちは直近のイベントで大きなものをhigh valueとして、小さなものをlow valueとする機能を得ました。

Performance considerations in D

上記で記載したとおり、このシステムはDプログラミング言語で作られています。既存のデータ構造にstorm boltなプラグインを追加するより、こちらの方が既存の機械学習インフラを活用しやすく、既に開発していたin-houseなD言語経験を活かせたためです。さらに言うと、私たちのスタックすべてにおいて最適化できるといったメリットがあり、単なるレイヤの追加と比べてよりよい選択でした。

このようなシステムにより、メモリ管理はパフォーマンスにおける重要な位置付けになりました。私たちはソースコードのプロファイリングにより、単一マシンでのソースの挙動が、D言語のGCアロケーターにおけるグローバルなロックであることを発見しました。主に処理に対するバッファのプリアロケーションのコードの構造を見直すことと、スペシャライズドなJSONシリアライザおよびパーサーを使ったことによって、32ハイパースレッドのインスタンスで、1つのマシンで秒間20,000イベントのスループットを出せるようになりました。もう一つ、行ったオプティマイズとしては、D言語のGCは、このアプリケーションでのGCサイクルに入った際に、ヒューリスティックが貧弱であることを発見したため、自動GCを止めて、GC.collect()とGC.minimizeを叩くようにしました。これによって2〜3倍早いスループットを出せるようになりました。D言語のランタイムは最近のリリースでとても良くなりました。私たちは上記のような計測が詳細不要になることを望んでいます。

最終的に私たちは、ファンシーな詳細なオプティマイズをする必要がなくなり、ソリッドなパフォーマンスを叩き出せるようになりました。このソリッドなパフォーマンスの重要なアドバンテージは、我々はchocolate chipを真の意味での分散システムとしてビルドする必要がなくなったことです。つまり、私たちは非常に可用性が高く、低いメンテナンスコストなシステムを手に入れた、ということです。補足として、このパフォーマンスにより、私たちはまた、独自のメモリ管理テクニックをリアルタイム広告プライス用のプレディクションサーバーにも活用しています。これは本当にいかなるGCのサイクルによっても逃すわけにはいかないミリ秒単位のSLAに対応するものです。

Chocolate chipは絶大な予測力と学習アルゴリズムの精度をもらたし、私たちのexchangeにおける入札のインテリジェンスを飛躍的に向上させました。上記のEMA機能のリリースにより、何の副作用もなく、cost-per-clickを2パーセント抑えることができました。