Twitterのパーソナライズされた通知

TwitterのエンジニアであるGary Lam氏はQCon London 2017でパーソナライズ通知について語った。講演では、パーソナライゼーションとレコメンデーションのアルゴリズムの概観、巨大なデータとTwitterのバイモーダルな性質に関わらず規模に応じた仕事の仕方について語られた。

パーソナライズドファンアウトは、ユーザーの関心事のみ通知を送る、というコンセプトだ。Lam氏が例としてあげたのはElon Muskの電気自動車についてのツイートだ。Elon Muskの全てのフォロワーに通知を送るのではなく、その中で電気自動車に関心のある人にだけ送る。

Lam氏によれば、パーソナライズドファンアウトアルゴリズムはふたつのことを追跡することで機能を果たす。

1. 要素に対する直近のエンゲージメント: ライク、リプライなど、あるユーザーがハッシュタグやアカウントに対して行ったアクション。氏はこのデータを最新に保つことの重要性を強調した。ユーザーは最近のツイートにしか興味を示さないからだ。
2. トップフォローイング: あるユーザーが数百人をフォローしていたとしても、その中の一部の人だけがトップフォローイング、つまり、もっとも興味のある人、だ。

アルゴリズムの導入で、最初に行ったのひとつのツイートから要素を取り出すことだ。それから、それぞれのフォロワーをチェックして、それらの要素が最近のエンゲージメントの中にあるかどうかを調べる。また、そのツイートがトップフォローイングがしたのかどうかもチェックする。このふたつの条件が真だった場合、ユーザーは通知を受け取る。そのツイートに関心がありそうだからだ。

Lam氏によればパーソナライズドファンアウトの問題は非対称性だ。あるユーザーが非常に多くのフォロワーを抱えている場合、そのユーザーがツイートすると、全てのフォロワーにこのアルゴリズムを適用する必要がある。一方で、数人のフォロワーしかいないユーザーもいる。

これを回避するために、データのコロケーションを活用している、と氏は説明する。それぞれのユーザーをシャードにし、最近のエンゲージメントとトップフォローイングを同じシャードにする。こうすることでアルゴリズムが実行された場合、ネットワークのホップが発生しないようにし、遅延を低減させる。

Lam氏は、最近のエンゲージメントは長い期間持続する必要はない、と指摘する。性質上、短命だからだ。したがってインメモリで保持をする。

シャードがダウンした場合、データの再構築は可能な限り高速に行われるように最適化されている。ユーザーが通知を受け取れることを保証するためだ。この再構築は、キューから前日のツイートを全てリプレイし、メッセージをバッチ処理して余分なデータを削除してからシャードに保存することで実現する。これは"slim firehose"として知られている作業だ。

トップフォローイングはオフラインの機会学習アルゴリズムで計算されている。このアルゴリズムはユーザー間のやりとりの履歴を見る。前もって計算しておくため、データはシャードのディスクにコピーされ、必要なときに遅延ロードされる。

氏はレコメンデーションについても話をした。パーソナライズドファンアウトとは多少の違いがある。ユーザーは通知を受けるためにフォロワーになる必要はない。コンテンツに興味があれば通知が受けられる。

この場合、イベントを購読するというより、それぞれのユーザーをループ処理したほうがいい。氏の説明によれば、こうすることでリソースが使いやすくなる。ユーザーの数、つまり、負荷のかかり方が予測しやすいやらだ。この処理ではいくつかのステップが実行される。

1. 関心低下: ユーザーが関心がなかったり、通知に興味を示さない場合は通知を送らない。
2. 候補者のソース: ユーザーIDは関連する通知のために交換される。これを実現するために使われているのはGraphJetというリアルタイムでグラフを処理するライブラリとオフラインでのマップリデュースアルゴリズムであるScaldingだ。
3. プッシュ: 通知をユーザーのデバイスに飛ばす。

講演の全体はオンラインで見れる。また、リアルタイム通知についてのSaurabh Pathak氏の講演もこの記事で取り上げている。