Share
Embed
Transcript
62 slides
-
niconicoの検索システムの概要 • データサイズ • コンテンツ数: 約3,000万doc • 性能要件 • 参照系
• ピークタイムで1,300req/secの検索リクエスト • 99.9%のリクエストを1秒以内にレスポンス • 更新系 • ピークタイムで1,000msg/secのコンテンツ更新メッセージ • 1分以内反映 -
システム構成 Elasticsearch サービス 更新系 参照系 API サーバ バッチサーバ 検索者 サービス
サービス 検索システム ログ基盤 -
システム構成 Elasticsearch サービス 更新系 参照系 API サーバ バッチサーバ ログ基盤 検索者
サービス サービス 検索システム • Elasticsearch Version 6.8を利用 • 2012年にVersion 1.xで運用開始し、 順次アップグレード • Version 7.xへのアップグレードも 計画中 • 構成 • データノード: 40台 • 突発的な負荷が予想される際に は臨機応変に増減 • マスターノード: 3台 -
システム構成 Elasticsearch サービス 更新系 参照系 API サーバ バッチサーバ 検索者 サービス
サービス 検索システム • 同義語辞書構築 • ユーザ情報インデックスのデータ生成 • ユーザのフォロー関係・視聴関係の クラスタリング ログ基盤 -
システム構成 Elasticsearch サービス 更新系 参照系 API サーバ バッチサーバ 検索者 サービス
サービス 検索システム • 同義語辞書 • ユーザのクラスタ情報 ログ基盤 -
システム構成 Elasticsearch サービス 更新系 参照系 API サーバ バッチサーバ 検索者 サービス
サービス 検索システム • データ更新を行うサブシステム • 主にGo言語で構築 更新系 APIサーバ Rabbit MQ DB 書き込み ワーカー My SQL Elasticsearch ES 書き込み ワーカー コンテンツ 更新 メッセージ ログ基盤 -
システム構成 Elasticsearch サービス 更新系 参照系 API サーバ バッチサーバ 検索者 サービス
サービス 検索システム • コンテンツ検索APIを提供するサーバ • 言語はScala • フレームワークはFinagle • フィルタチェインで下記の流れを記述 • 同義語辞書からの同義語取得 • 検索者が所属するクラスタ情報の取得 • 検索者の視聴履歴情報の取得 • ESのクエリ生成 • ESへのリクエスト -
システム構成 Elasticsearch サービス 更新系 参照系 API サーバ バッチサーバ 検索者 サービス
サービス 検索システム ログ基盤 -
ランキングソートの処理の流れ • 9/10 19:00に動画ID:sm9のランキングスコア合計が800→900になったときの例 Elasticsearch 動画 サーバ 更新系 参照系 API
サーバ ランキングスコア合計: 800 動画ID: sm9 ランキングスコア増加量 9/10 19:00 9/10 18:00 +50 … 9/9 19:00 +300 9/9 18:00 +150 -
ランキングソートの処理の流れ • 9/10 19:00に動画ID:sm9のランキングスコア合計が800→900になったときの例 Elasticsearch 動画 サーバ 更新系 参照系 API
サーバ 更新メッセージ(再生数更新) 動画ID: sm9 再生数: 432 ランキングスコア合計: 900 ランキングスコア合計: 800 動画ID: sm9 ランキングスコア増加量 9/10 19:00 9/10 18:00 +50 … 9/9 19:00 +300 9/9 18:00 +150 -
ランキングソートの処理の流れ • 9/10 19:00に動画ID:sm9のランキングスコア合計が800→900になったときの例 Elasticsearch 動画 サーバ 更新系 参照系 API
サーバ ランキングスコア合計: 800 動画ID: sm9 ランキングスコア増加量 9/10 19:00 9/10 18:00 +50 … 9/9 19:00 +300 9/9 18:00 +150 動画サーバ側で再生数・コメント数・マイリスト数 に基づいて計算されて送られてくる 更新メッセージ(再生数更新) 動画ID: sm9 再生数: 432 ランキングスコア合計: 900 -
ランキングソートの処理の流れ • 9/10 19:00に動画ID:sm9のランキングスコア合計が800→900になったときの例 Elasticsearch 動画 サーバ 更新系 参照系 API
サーバ 更新メッセージ 動画ID: sm9 ランキングスコア合計: 900 ランキングスコア合計: 800 動画ID: sm9 ランキングスコア増加量 9/10 19:00 9/10 18:00 +50 … 9/9 19:00 +300 9/9 18:00 +150 +100 -
ランキングソートの処理の流れ • 9/10 19:00に動画ID:sm9のランキングスコア合計が800→900になったときの例 Elasticsearch 動画 サーバ 更新系 参照系 API
サーバ 更新メッセージ 動画ID: sm9 ランキングスコア合計: 900 ランキングスコア合計: 800 動画ID: sm9 ランキングスコア増加量 9/10 19:00 +100 9/10 18:00 +50 … 9/9 19:00 +300 9/9 18:00 +150 +100 -
ランキングソートの処理の流れ • 9/10 19:00に動画ID:sm9のランキングスコア合計が800→900になったときの例 Elasticsearch 動画 サーバ 更新系 参照系 API
サーバ ランキングスコア合計: 800 動画ID: sm9 ランキングスコア増加量 9/10 19:00 +100 9/10 18:00 +50 … 9/9 19:00 +300 9/9 18:00 +150 • 64bit longの配列 -
ランキングソートの処理の流れ • 9/10 19:00に動画ID:sm9のランキングスコア合計が800→900になったときの例 Elasticsearch 動画 サーバ 更新系 参照系 API
サーバ ランキングスコア合計: 800 動画ID: sm9 ランキングスコア増加量 9/10 19:00 +100 9/10 18:00 +50 … 9/9 19:00 +300 9/9 18:00 +150 -
ランキングソートの処理の流れ • 9/10 19:00に動画ID:sm9のランキングスコア合計が800→900になったときの例 Elasticsearch 動画 サーバ 更新系 参照系 API
サーバ ランキングスコア合計: 800 動画ID: sm9 ランキングスコア増加量 9/10 19:00 +100 9/10 18:00 +50 … 9/9 19:00 +300 9/9 18:00 +150 24時間分のランキングスコア の増加量の総和を取って ソートする -
ソートの負荷軽減 • 動画のコンテンツ数は1,600万 • 「ゲーム」などのタグで検索すると、700万件程度ヒットする • ソート時に、700万件のコンテンツについて24時間分のランキングスコア 増加量情報の総和を取るのは負荷が⾼い • 負荷軽減策を考える必要がある
• Elasticsearchのrescoreという機能が有効 • 負荷の⼩さい近似式などでスコアを計算してソートした後、そのトップN件を 厳密な式でスコアを計算してソートする機能 -
ランキングソートの処理の流れ • 9/10 19:00に動画ID:sm9のランキングスコア合計が800→900になったときの例 Elasticsearch 動画 サーバ 更新系 参照系 API
サーバ 更新メッセージ 動画ID: sm9 ランキングスコア合計: 900 ランキングスコア合計: 800 動画ID: sm9 ランキングスコア増加量 9/10 19:00 +100 9/10 18:00 +50 … 9/9 19:00 +300 9/9 18:00 +150 +100 -
ランキングソートの処理の流れ • 9/10 19:00に動画ID:sm9のランキングスコア合計が800→900になったときの例 Elasticsearch 動画 サーバ 更新系 参照系 API
サーバ 更新メッセージ 動画ID: sm9 ランキングスコア合計: 900 ランキングスコア合計: 800 動画ID: sm9 ランキングスコア増加量 9/10 19:00 +100 9/10 18:00 +50 … 9/9 19:00 +300 9/9 18:00 +150 24時間ランキングスコア 増加量近似値: 600 -
ランキングソートの処理の流れ • 9/10 19:00に動画ID:sm9のランキングスコア合計が800→900になったときの例 Elasticsearch 動画 サーバ 更新系 参照系 API
サーバ ランキングスコア合計: 800 動画ID: sm9 ランキングスコア増加量 9/10 19:00 +100 9/10 18:00 +50 … 9/9 19:00 +300 9/9 18:00 +150 24時間ランキングスコア 増加量近似値: 600 第1ソートでは、近似値 でソート -
ランキングソートの処理の流れ • 9/10 19:00に動画ID:sm9のランキングスコア合計が800→900になったときの例 Elasticsearch 動画 サーバ 更新系 参照系 API
サーバ ランキングスコア合計: 800 動画ID: sm9 ランキングスコア増加量 9/10 19:00 +100 9/10 18:00 +50 … 9/9 19:00 +300 9/9 18:00 +150 24時間ランキングスコア 増加量近似値: 600 トップN件を、 24時間分のランキングスコア 増加量情報の総和を取って ソートする -
ランキングソートの処理の流れ • 9/10 19:00に動画ID:sm9のランキングスコア合計が800→900になったときの例 Elasticsearch 動画 サーバ 更新系 参照系 API
サーバ ランキングスコア合計: 800 動画ID: sm9 ランキングスコア増加量 9/10 19:00 +100 9/10 18:00 +50 … 9/9 19:00 +300 9/9 18:00 +150 24時間ランキングスコア 増加量近似値: 600 • 25時間のスコア増加量の総和である • 再生数・コメント数・マイリスト数が更新 されないコンテンツの値が残り続ける -
ランキングソートの処理の流れ • ⽇次バッチで24時間再⽣されていないコンテンツのランキング近似値は消す Elasticsearch 動画 サーバ 更新系 参照系 API サーバ
ランキングスコア合計: 800 動画ID: sm9 ランキングスコア増加量 9/10 19:00 +100 9/10 18:00 +50 … 9/9 19:00 +300 9/9 18:00 +150 24時間ランキングスコア 増加量近似値: 600 バッチ サーバ -
ランキングソートの検索クエリ(1) "query": { "function_score": { "query": { …タグ検索のクエリ }, "functions":
[ { "field_value_factor": { “field”: “[ランキング近似値]", "factor": 1, "missing": 0 } } ], "boost_mode": "replace” 第1ソート • Rescoreを利用する場合は、Fieldでなく Score(デフォルトでは単語関連度)でしか ソートできない • Function scoreのfield value factorで ランキング近似値を指定 -
ランキングソートの検索クエリ(2) "rescore": [ { "window_size": 1000, "query": { "rescore_query": {
"function_score": { "query": { ...タグ検索のクエリ }, "functions": [ { "script_score": { "script": { “id”: ”[スコア増加量計算のスクリプト]", "params": { ...スクリプトに渡すパラメタ 第2ソート } } }, "score_mode": "multiply", "boost_mode": "replace", "boost": 1 } }, "query_weight": 0, "rescore_query_weight": 1, "score_mode": "total" } } ] } • RescoreするトップNの値 • ノードごとのトップNであることに注意 • 10シャードなので実際はトップ1万 -
rescoreでどの程度⾼速化できたか Rescoreあり Rescore無し 1回目 0.540s 1.628s 2回目 0.508s 1.125s 3回目
0.430s 1.066s 4回目 0.539s 1.094s 5回目 0.465s 1.142s 平均 0.496s 1.211s • キーワード「ゲーム」で検索し、約700万件動画がヒットしたときの レスポンスタイム • 約60%⾼速化 • 複雑な計算式からなるソートの⾼速化にrescore機能が有効であることが分かる -
パーソナライズドソーシャルサーチ(2) • コンテンツに対する好みは千差万別 • あるユーザにとって⾯⽩いコンテンツが、他のユーザにとってはあまり⾒たくないような コンテンツであることもある • コンテンツ投稿者・⽣主名には⾮常に被りが多い • 「⿊猫」が部分⽂字列として⼊るニックネームを設定しているクリエイターなどは⾮常に多い
• 検索者の傾向に応じてパーソナライズしたソート順を提供することで、検索者が ⽬的とするコンテンツ・ユーザに早く到達できるようにする • 動画検索のパーソナライズドソートの研究例を解説する -
背景 (1) • ソーシャルネットワークサービスにおけるコンテンツ検索では、 ソーシャルサーチが検索精度の向上に効果的である • 動画や⾳楽、⽣放送番組などのマルチメディアコンテンツの 検索では、その内容が⾃然⾔語で⼗分に説明されているとは 限らない •
SNSとしての機能を持つCGMサイトのコンテンツ検索においては、 検索者とコンテンツ作成者のフォロー関係や視聴関係などの情報を 利⽤することで、検索精度を向上することができる可能性がある Personalized social search based on the user's social network, (David C, 2009) The anatomy of a large-scale scocial search engine (Horowitz, D,2010) -
Louvain法(1) • ソーシャルネットワークに対して凝集型階層的グラフクラスタリングの⼀⼿法 であるLouvain法を適⽤して⽣成した階層構造のクラスタ情報をコンテンツDB に格納してコンテンツ検索時のスコア付けに使⽤する • Louvain法(V. D. Blondel, 2008)とは、Newmanのモジュラリティという
指標をもとにした⾼速かつ⾼精度でコミュニティ構造を抽出できる、 代表的なグラフクラスタリングアルゴリズム • Louvain法は、処理の繰り返しごとに得られるコミュニティ構造を保持する ことで、解像度の異なる階層的なコミュニティ構造を得ることができるという 特徴を持っている -
Louvain法(2) • ニコニコ動画のフォロー関係に対して Louvain法を適⽤したときの例 • Louvain法で抽出した階層的クラスタ構造の トップの階層をバブル図で可視化したもの • ⻘っぽいクラスタ︓男性が多い •
⾚っぽいクラスタ︓⼥性が多い • 円の⼤きさはクラスタに含まれる⼈数を反映 -
Louvain法(4) • 「バイク・⾞載動画・ツーリング・ニコ⽣・政治」 のクラスタが、第2階層ではさらに細かな クラスタになっている • 4-6段程度の構造になる • 階層構造を考慮したスコアリングを⾏うことで ユーザの細やかな嗜好を反映できると考え
Louvain法を採⽤ 国会中継リンク ニコ生・日記・AKB48・洋楽 ツーリング バイク -
システム構成 Elasticsearch サービス 更新系 参照系 API サーバ バッチサーバ (1) (2)
検索者 (3) (4) (5) (6) (7) (8) (9) (10) (11) (12) (13) ログ基盤 -
システム構成 Elasticsearch サービス 更新系 参照系 API サーバ バッチサーバ (1) (2)
検索者 (3) (4) (5) (6) (7) (8) (9) (10) (11) (12) (13) ログ基盤 フォロー関係ログと視聴ログに対して、 Louvain法でグラフクラスタリングを行う (spark graphx を利用) -
システム構成 Elasticsearch サービス 更新系 参照系 API サーバ バッチサーバ (1) (2)
検索者 (3) (4) (5) (6) (7) (8) (9) (10) (11) (12) (13) ログ基盤 ユーザのクラスタ情報を Redisに格納する -
システム構成 Elasticsearch サービス 更新系 参照系 API サーバ バッチサーバ (1) (2)
検索者 (3) (4) (5) (6) (7) (8) (9) (10) (11) (12) (13) ログ基盤 • 動画の新規投稿イベントを受け取る • クラスタ情報DBから動画投稿者の クラスタ情報を取得する • 合わせてコンテンツDBに書き込む -
システム構成 Elasticsearch サービス 更新系 参照系 API サーバ バッチサーバ (1) (2)
検索者 (3) (4) (5) (6) (7) (8) (9) (10) (11) (12) (13) ログ基盤 • クラスタ情報DBから検索者のクラスタ情報を 取得する • 検索者のクラスタ情報と、動画投稿者の クラスタ情報のクラスタ間類似度をもとに ヒットしたコンテンツをスコアリングし、 ソートして提示する -
システム構成 Elasticsearch サービス 更新系 参照系 API サーバ バッチサーバ (1) (2)
検索者 (3) (4) (5) (6) (7) (8) (9) (10) (11) (12) (13) ログ基盤 -
• フォロー関係と視聴関係のクラスタ情報を使⽤する。以降はフォロー関係をもとに説明する • 視聴関係は、視聴ログから「誰が誰の動画を⾒たか」というユーザ同⼠の関係を抽出して ⽣成したネットワーク • ユーザa, b,…, pからなる ソーシャルネットワークを考える
• Louvain法を適⽤すると、 階層的なクラスタ構造が得られる クラスタ情報(1) -
階層図にすると、下記のようになる クラスタ情報(2) b a c g f e d h
j i k l n m o p 1 3 5 6 4 2 第2層目 第1層目 -
クラスタ情報(3) • 階層の数をN、ユーザ が第層⽬で所属するコミュニティのidを$,& としたとき、 ユーザのフォロー関係クラスタ情報$ を下記のような配列として表現 • 下記の例で説明すると、ユーザ が所属するフォロー関係
クラスタ情報) は $ = [$,,, $,-, … , $,/] ) = [1, 4] b a c g f e d h j i k l n m o p 1 3 5 6 4 2 第2層目 第1層目 -
スコアリング(1) • ⼤量のコンテンツがヒットした際のレスポンス時間を 短縮するために、ランキングソートと同様にElasticsearchの rescoreで2段階でスコアリング = 9 :単語関連度スコア + ,
:再生数スコア + - :コンテンツ鮮度スコア + ; :コメント鮮度スコア + < :フォロー関係クラスタ間類似度 + = :視聴関係クラスタ間類似度 1段階⽬: コンテンツの投稿⽇時が新しい順によりソート 2段階⽬: 1段階⽬のソート結果の上位件について、ユーザのクラスタ情報を 利⽤したスコアによりソート -
スコアリング(2) • ⼤量のコンテンツがヒットした際のレスポンス時間を 短縮するために、ランキングソートと同様にElasticsearchの rescoreで2段階でスコアリング = 9 :単語関連度スコア + ,
:再生数スコア + - :コンテンツ鮮度スコア + ; :コメント鮮度スコア + < :フォロー関係クラスタ間類似度 + = :視聴関係クラスタ間類似度 1段階⽬: コンテンツの投稿⽇時が新しい順によりソート 2段階⽬: 1段階⽬のソート結果の上位件について、ユーザのクラスタ情報を 利⽤したスコアによりソート -
クラスタ間類似度(1) • 検索者とコンテンツ投稿者のフォロー関係クラスタ情報の類似度の 計算⽅法を例として説明する • 検索者Aのフォロー関係クラスタ情報を? = ?,, , ?,-
, … , ?,/ コンテンツ投稿者Bのフォロー関係クラスタ情報 @ = [@,, , @,- , … , @,/ ]としたとき、AとBのフォロー関係クラスタ間 類似度(? , @ )は下記の式で計算する ?, @ = 1 E &F, / ?,&, @,& , = I 1 ( = ) 0 ( ≠ ) -
クラスタ間類似度(2) • 下記の階層図の例で説明すると • ユーザaとユーザbのクラスタ間類似度︓ 1.0 • ユーザaとユーザdのクラスタ間類似度︓ 0.5 •
ユーザaとユーザlのクラスタ間類似度︓ 0.0 b a c g f e d h j i k l n m o p 1 3 5 6 4 2 第2層目 第1層目 -
評価実験 • CGMサイトであるニコニコ動画に提案アルゴリズムを実装し、 検索者が興味のあるコンテンツを⾒つけるためにクラスタ情報が 有⽤であることを確認する • 下記のネットワークに対しlouvain法を適⽤し、クラスタ情報を⽣成する • フォロー関係 •
視聴関係 • 検索システムの規模(2018年4⽉2⽇) • 約1500万件の動画を検索対象として保持している • フォロー関係、視聴関係のネットワークの規模 ネットワークの種類 ノード数 エッジ数 フォロー関係 9,194,596 109,471,657 視聴関係 3,047,813 48,378,044 -
評価実験 • CGMサイトであるニコニコ動画に提案アルゴリズムを実装し、 検索者が興味のあるコンテンツを⾒つけるためにクラスタ情報が 有⽤であることを確認する • 下記のネットワークに対しlouvain法を適⽤し、クラスタ情報を⽣成する • フォロー関係 •
視聴関係 • 検索システムの規模(2018年4⽉2⽇) • 約1500万件の動画を検索対象として保持している • フォロー関係、視聴関係のネットワークの規模 ネットワークの種類 ノード数 エッジ数 フォロー関係 9,194,596 109,471,657 視聴関係 3,047,813 48,378,044 ユーザの7日分の視聴履歴について、最後まで動画を視聴した履歴のみを抽出し、 動画の視聴者と動画の投稿者の関係にマッピング -
評価実験 • CGMサイトであるニコニコ動画に提案アルゴリズムを実装し、 検索者が興味のあるコンテンツを⾒つけるためにクラスタ情報が 有⽤であることを確認する • 下記のネットワークに対しlouvain法を適⽤し、クラスタ情報を⽣成する • フォロー関係 •
視聴関係 • 検索システムの規模(2018年4⽉2⽇) • 約1500万件の動画を検索対象として保持している • フォロー関係、視聴関係のネットワークの規模 ネットワークの種類 ノード数 エッジ数 フォロー関係 9,194,596 109,471,657 視聴関係 3,047,813 48,378,044 -
評価実験の⽅法(1) • クラスタ間類似度の重みの値を0.1から0.3まで変えていく • ユーザに本アルゴリズムを利⽤した検索機能を利⽤してもらい、 重みの値が⼤きい時と⼩さい時のクリック率を⽐較する • 検索者が興味を持っているコンテンツを探すときに、 クラスタ間類似度の指標が役に⽴っているかどうかを確かめる =
9 :単語関連度スコア + , :再生数スコア + - :コンテンツ鮮度スコア + ; :コメント鮮度スコア + < :フォロー関係クラスタ間類似度 + = :視聴関係クラスタ間類似度 -
評価実験の⽅法(2) • クラスタ間類似度の重みの値を0.1から0.3まで変えていく • ユーザに本アルゴリズムを利⽤した検索機能を利⽤してもらい、 重みの値が⼤きい時と⼩さい時のクリック率を⽐較する • 検索者が興味を持っているコンテンツを探すときに、 クラスタ間類似度の指標が役に⽴っているかどうかを確かめる =
9 :単語関連度スコア + , :再生数スコア + - :コンテンツ鮮度スコア + ; :コメント鮮度スコア + < :フォロー関係クラスタ間類似度 + = :視聴関係クラスタ間類似度 • 本検索機能を利用してもらうユーザには、本ソート順が検索者の 視聴履歴を反映したものになっていることを案内している • 重みを0.0にするパターンについては、検索者に提示される動画の 傾向が明らかに検索者の視聴傾向を反映しないものとなり、機能が 壊れているようにも見えてしまうため、試行していない -
• フォロー関係クラスタ間類似度の重み< 、視聴関係クラスタ間類似度の重み = を0.1から0.3まで変えたときのクリック率を⽰す • 各重みパターンの間のクリック率に差があるどうかをRyan法よる多重⽐較で 確かめる 視聴関係クラスタ間類似度 0.1
0.2 0.3 フォロー関係 クラスタ間類似度 0.1 41.6 (36,808) 43.2** (37,978) 42.0 (38,327) 0.2 42.1 (38,856) 42.1 (38,999) 43.3** (38,433) 0.3 42.4 (38,093) 43.4** (37,876) 42.7 (37,728) 評価実験の結果(1) -
• フォロー関係クラスタ間類似度の重み< 、視聴関係クラスタ間類似度の重み = を0.1から0.3まで変えたときのクリック率を⽰す • 各重みパターンの間のクリック率に差があるどうかをRyan法よる多重⽐較で 確かめる 視聴関係クラスタ間類似度 0.1
0.2 0.3 フォロー関係 クラスタ間類似度 0.1 41.6 (36,808) 43.2** (37,978) 42.0 (38,327) 0.2 42.1 (38,856) 42.1 (38,999) 43.3** (38,433) 0.3 42.4 (38,093) 43.4** (37,876) 42.7 (37,728) 評価実験の結果(1) • 各類似度による指標の重みの値を0.1より大きくした パターンのクリック率が向上している • 視聴関係クラスタ間類似度、フォロー関係クラスタ間類 似度の指標が、検索者が見たいと感じるような動画を 探すときに役立っていると考えられる -
おわりに • 下記について説明した • niconicoのコンテンツ検索システムの概要 • Elasticsearchを⽤いたタグベースの動画ランキングの実現 • SNSの機能を持つCGMサイトにおけるコンテンツ検索を対象とした、 パーソナライズドソーシャルサーチのアルゴリズム
• パーソナライズドサーチに関してはまだ改善の余地がある • ランキング学習でスコアリング式の重みパラメータの調整 • node2vecなどのgraph embeddingの⼿法で算出するノードの ベクトル間の距離をスコアリングに利⽤する⽅式なども⽐較検討