Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
【VAアカデミア用】パーソナライズされたコンテンツ配信のための低遅延分散KVSの構築
Search
bootjp / ぶーと
May 22, 2020
Research
0
11
【VAアカデミア用】パーソナライズされたコンテンツ配信のための低遅延分散KVSの構築
bootjp / ぶーと
May 22, 2020
Tweet
Share
More Decks by bootjp / ぶーと
See All by bootjp / ぶーと
Raftとは? 仕組みから考える得意なこと苦手なこと/What is Raft? Strengths and Weaknesses Based on Its Mechanism
bootjp
7
2.9k
Spannerはなぜ原子時計が必要だったのか?/あるいはSpanner Cloneはなぜ不要にできたのか? / Why did Spanner need an atomic clock? Or Why could Spanner Clone not be needed?
bootjp
1
50
Other Decks in Research
See All in Research
論文読み会 SNLP2024 Instruction-tuned Language Models are Better Knowledge Learners. In: ACL 2024
s_mizuki_nlp
1
270
「Goトレ」のご紹介
smartfukushilab1
0
450
「人間にAIはどのように辿り着けばよいのか?ー 系統的汎化からの第一歩 ー」@第22回 Language and Robotics研究会
maguro27
0
510
3次元点群の分類における評価指標について
kentaitakura
0
110
-SSII技術マップを通して見る過去・現在,そして未来-
hf149
1
580
marukotenant01/tenant-20240826
marketing2024
0
500
ミニ四駆AI用制御装置の事例紹介
aks3g
0
130
SSII2024 [OS2] 大規模言語モデルと基盤モデルの射程
ssii
PRO
0
460
#SRE論文紹介 Detection is Better Than Cure: A Cloud Incidents Perspective V. Ganatra et. al., ESEC/FSE’23
yuukit
3
1.2k
クラウドソーシングによる学習データ作成と品質管理(セキュリティキャンプ2024全国大会D2講義資料)
takumi1001
0
170
SSII2024 [PD] 30周年記念特別企画SSII 技術マップ / LLMサーベイ
ssii
PRO
0
740
Harnessing the Power of Vicinity-Informed Analysis for Classification under Covariate Shift
nanofi
3
300
Featured
See All Featured
Easily Structure & Communicate Ideas using Wireframe
afnizarnur
190
16k
Teambox: Starting and Learning
jrom
131
8.7k
Building Better People: How to give real-time feedback that sticks.
wjessup
359
19k
The Brand Is Dead. Long Live the Brand.
mthomps
53
38k
VelocityConf: Rendering Performance Case Studies
addyosmani
322
23k
Art, The Web, and Tiny UX
lynnandtonic
294
20k
Learning to Love Humans: Emotional Interface Design
aarron
270
40k
Building Adaptive Systems
keathley
36
2.1k
A Philosophy of Restraint
colly
202
16k
Keith and Marios Guide to Fast Websites
keithpitt
408
22k
Six Lessons from altMBA
skipperchong
26
3.3k
Let's Do A Bunch of Simple Stuff to Make Websites Faster
chriscoyier
502
140k
Transcript
None
パーソナライズされたコンテンツ配信のた めの低遅延分散KVSの構築 Building Low-latency Distributed KVS Optimized for Personalized Content
Delivery 上田 義明/ぶーと Supership 株式会社/放送大学
アジェンダ • 本構築手法の背景と課題 • コンテンツ配信とは • パーソナライズされたコンテンツ配信とは • 一般的な分散KVSを用いた際の構成例と問題 •
既存研究/技術はなにが解決できなかったのか ◦ Master/Slave方式の分散KVSを用いた際の構成 ◦ キーシャーディングの分散KVSを用いた際の構成 • 提案手法の紹介 • 評価 • おわりに/質疑応答
本構築手法の背景と課題 • 従来のアプリケーションではデータストアにRDBを用いることが多かった • 一方RDBでは応答速度が要求されるケースでは性能に限界があった • そこで,応答速度が要求される用途ではKey-Value Store (KVS) が用いられた
• 一般にコンテンツ配信では,複数のアプリケーションノードを用いるため,複数ノー ドのKVSからなる分散KVSを用いる
コンテンツ配信とは • 大量のユーザに対して安定して高速にコンテンツを配信する • 大量のユーザーに配信するために ◦ 複数のアプリケーションノードを用いる ◦ 複数のアプリケーションノードへ接続をロードバランサで分散をする ◦
分散KVSを用いてアプリケーションノードのデータ同期を行う • 代表的なサービス例 ◦ Pixiv ◦ imgur ◦ YouTube ◦ ニコニコ動画
パーソナライズされたコンテンツ配信とは • 利便性向上や効果的なマーケティングのために,リッチなコンテンツ配信が求めら れるようになった • ユーザーごとに異なるデータをユーザからの問い合わせ後に生成してコンテンツを 配信するようになった • 代表的なシステム例 ◦
広告配信 ◦ レコメンデーション ◦ 検索エンジン ◦ 通知管理システム
パーソナライズされたコンテンツ配信とは • 前述のシステムでは以下の3点を同時に満たす必要がある ◦ 高速な応答速度で ◦ ユーザー毎に異なるデータを ◦ 安定して配信する •
ユーザーごとに異なるデータをユーザからの問い合わせ後に生成し応答 するコンテンツ配信のこと
パーソナライズされたコンテンツ配信とは • 広告配信のRTB(Real Time Bidding)では応答速度に要件があり,多くはネット ワーク遅延を含め100ミリ秒である • 一般に広告配信アプリケーションの処理は,50ミリ秒以内に収める必要があると言 われている •
したがってコンテンツ配信に用いる分散KVSは以下を満たす必要がある ◦ 10ミリ秒以下高速な応答性能 ◦ 単一のユーザに一貫性のあるデータの提供 ◦ 2つの要素を安定して提供する
一般的な分散KVSを用いた際の構成例と問題
一般的な分散KVSを用いた際の構成例と問題
一般的な分散KVSを用いた際の構成例と問題 • ネットワーク越しの問い合わ せになるため応答速度が遅 い • 問い合わせ数が増えると応 答速度が低下する
一般的な分散KVSを用いた際の構成例と問題
一般的な分散KVSを用いた際の構成例と問題 • 分散KVSノードのデータ同期 に遅延が発生する
一般的な分散KVSを用いた際の構成例と問題 • 分散KVSはネットワーク越しの問い合わせになるため応答速度が遅い • 問い合わせ数が増加すると応答速度が低下する • 更新クエリが増えると分散KVSのレプリケーション通信がボトルネックとな りデータの同期で遅延が発生する
既存研究/技術はなにが解決できなかったのか • 同期遅延 ◦ Master/Slave方式の分散KVSのSlaveをアプリケーションノードの置くことで解決 ◦ ⇢レプリケーションラグが発生する • 応答速度の遅延 ◦
キーシャーディング方式の分散KVSを用いることで分割統治により同期を省くことができ る ◦ ⇢アプリケーションノードと同一ノードにデータをもつ分散 KVSは配置できない
既存研究/技術はなにが解決できなかったのか • 同期遅延 ◦ Master/Slave方式の分散KVSのSlaveをアプリケーションノードの置くことで解決 ◦ ⇢レプリケーションラグが発生する
Master/Slave方式の分散KVSを用いた際の構成例
Master/Slave方式の分散KVSを用いた際の構成例 • レプリケーションラグが発生し ,必ずしも最新のデータがか えらない
既存研究/技術はなにが解決できなかったのか • 応答速度の遅延 ◦ キーシャーディング方式の分散KVSを用いることで分割統治により同期を省くことができ る ◦ ⇢アプリケーションノードと同一ノードにデータをもつ分散 KVSは配置できない
キーシャーディングの分散KVSを用いた際の構成
キーシャーディングの分散KVSを用いた際の構成 • シャーディングの場合必ずし も同一ノードのKVSにデータ があるとは限らないため遅延 が発生する • 別ノードへ取得に行く場合は 大きく遅延するため, 安定した性能とはいえない
既存研究/技術はなにが解決できなかったのか • 同期遅延 ◦ Master/Slave方式の分散KVSのSlaveをアプリケーションノードの置くことで解決 ◦ ⇢レプリケーションラグが発生する • 応答速度の遅延 ◦
キーシャーディング方式の分散KVSを用いることで分割統治により同期を省くことができ る ◦ ⇢アプリケーションノードと同一ノードにデータをもつ分散 KVSは配置できない
提案手法 - アプローチ • 応答性能の確保 ◦ 分散KVS をコンテンツ配信アプリケーションと同一のノードに配置する ◦ プロセス間通信でデータを交換することでネットワーク遅延を廃する
• 単一ユーザの一貫性の確保 ◦ ロードバランサでユーザのコンテンツ配信アプリケーションへの接続を常に同一ノードに 固定する ◦ 以降ユーザには同一ノードで一貫性のあるデータ提供する ◦ この状態を一貫性モデルの1つ,クライアント中心一貫性を確保しているに等しい状態で ある
提案手法 - 構成図
評価 - 概要 • 評価を行うためプロトタイプの実装を行った ◦ memcached互換のプロトコルで通信できる分散 KVSをGo言語で実装した ◦ ロードバランサの機能を用いてユーザの接続先ノードの固定した
◦ 実装は以下のリポジトリで公開している ▪ https://github.com/bootjp/turbo-ubiquitous-store • 評価は2つの観点から行う ◦ 既存技術との応答速度の比較 ◦ 単一ユーザにおいて一貫性が保証できているか
評価 - 応答速度 • 提案手法の応答時間を評価する • 既存技術であるRedisの応答時間を評価し提案手法と比較する • 評価には memtier_benchmark
を用いた • 実際の環境を模倣し以下の環境で評価をした. ◦ 既存手法は単一ノードに別ノードよりネットワーク経由 ◦ 提案手法は単一ノードないにおいての Unix Domain SocketでのIPCでの評価 • memtier_benchmark の引数は以下の通り ◦ --threads=16 --requests=10000 ◦ 並列パイプライン数(--pipeline) は1 ~ 10で変化させた
評価 - 応答速度
評価 - 応答速度 既存技術と比較し,平均 し10ms以上の高速化 要件の10ms以下の応 答速度の達成
評価 - 応答速度 まとめ • 提案手法と既存技術のRedisの平均応答時間は ◦ 提案手法が 4.32ミリ秒 ◦
Redisが16.79ミリ秒 • 提案手法による10ミリ秒以上の応答の高速化を確認した. • 既存技術では応答時間の要件を満たせない一方,提案手法では要件を容 易に充足できることも確認した
評価 - 一貫性 • 提案手法でユーザ単位のデータの一貫性を確認する • 評価に用いる以下の仕様の実験用アプリケーションを作成した ◦ ユーザーの識別子ごとに何回のアクセスがあったかを分散 KVSに記録し,最新の値を分
散KVSから取得しレスポンスする ◦ これを複数ノード配置し前段にロードバランサによりロードバランスを
評価 - 一貫性 • 評価方法 ◦ クライアント側が計測しているリクエスト回数と分散 KVSで計測された数を比較し一貫性 の評価を行った ◦
100並列の各100回のリクエストを行った
評価 - 一貫性 まとめ • 実験の結果,クライアントがリクエストした回数とレスポンスの結果は常に 一致しており,クライアント自身が書き込んだ値を読み出すことができる一 貫性が正しく機能していることを確認した
おわりに • 実験では応答速度の要件を満たし,既存技術と比較し平均応答速度が10 ミリ秒以上高速化された. • 一貫性においてはクライアント中心一貫性が正しく確保できていることを確 認した • 提案手法では今後の課題として,ノードダウン時や入替時の一貫性の担 保がある
質疑応答