JavaScriptを有効にしてください

執筆論文の解説「パーソナライズされたコンテンツ配信のための低遅延分散KVSの構築」

 ·  ☕ 7 分で読めます

    この記事は 自作 DBMS Advent Calendar 2020 の 22 日目の記事です.

    自作 DBMS という趣旨とは少し異なりますが,

    DBMS (や DBMS っぽいもの)を自作している人々が自分の実装を自慢し合ったり苦しさを共有したりするアドベントカレンダー

    Disk-Oriented, In-Memory, KVS, RDBMS, OLTP, OLAP, HTAP なんでもアリ。

    ストレージエンジンだけでもよし、実行エンジンだけでもよし、既存の DBMS の上に何かのっけて分散 DBMS にしたとかでもよし。

    ということなので,私が情報処理学会の第 82 回全国大会で発表を行った「パーソナライズされたコンテンツ配信のための低遅延分散 KVS の構築」という論文についての解説記事です.

    論文は以下より無料で閲覧できます.

    パーソナライズされたコンテンツ配信のための低遅延分散 KVS の構築

    また本記事は以前に VR アカデミアで行った発表とほぼ同様のものとなります.

    はじめに

    従来の一般的な Web アプリケーションではデータストアに RDB を用いて構築することが多かった. しかし,高トラフィックで応答速度が要求されるコンテンツ配信などのケースでは,RDB では性能に限界があった.

    そこで,応答速度が要求される用途では Key-Value Store (KVS) が用いられ,トラフィックが多い環境では分散 KVS が用いられてきた.

    本記事では既存の分散 KVS が抱える問題とパーソナライズされたコンテンツ配信に特化した分散 KVS の構築手法について解説する.

    コンテンツ配信とは

    ここでは大量のユーザに対して安定して Web を介して高速にコンテンツを配信するサービスをコンテンツ配信と呼ぶ

    • 大量のユーザーに配信するためには
      • 複数のアプリケーションノードを用いる
      • 複数のアプリケーションノードへ接続をロードバランサで分散をする
      • 分散 KVS を用いてアプリケーションノードのデータ同期を行う

    という手法が一般的に用いられる

    身近なところでの代表的なコンテンツ配信のサービス例

    • Twitter
    • pixiv
    • ABEMA
    • YouTube

    パーソナライズされたコンテンツ配信とは

    昨今のコンテンツ配信では,利便性向上や効果的なマーケティングのために,リッチなコンテンツ配信が求められるようになり, ユーザーごとに異なるデータをユーザからの問い合わせ後に生成してコンテンツを配信するようになった.

    具体的には

    • 広告配信
    • レコメンデーション
    • 検索エンジン
    • 通知管理システム

    前述のシステムでは以下の 3 点を同時に満たす必要がある

    • 高速な応答速度で
    • ユーザー毎に異なるデータを
    • 安定して配信する

    つまりパーソナライズされたコンテンツ配信とは「ユーザーごとに異なるデータをユーザからの問い合わせ後に生成し応答するコンテンツ配信」と言い換えることができる.

    具体的に広告配信のリアルタイム買い付けの RTB(Real Time Bidding)では業者間のオークションの応答速度に要件があり,多くはネットワーク遅延を含め 100 ミリ秒である.

    一般に広告配信アプリケーションの処理は,50 ミリ秒以内に収める必要があると言われており,したがってコンテンツ配信に用いる分散 KVS はそれよりも高速に応答することが求められる.

    以下を満たすものを要件とする.

    • 10 ミリ秒以下高速な応答性能
    • 単一のユーザに一貫性のあるデータの提供
    • 前述する 2 つの要素を安定して提供する

    一般的な分散 KVS を用いた際の構成例と問題

    一般的な分散 KVS を用いた際の構成例

    応答速度が遅くリクエスト数が増えると問題となる

    分散 KVS 間でのデータ同期の遅延が発生する

    • 分散 KVS はネットワーク越しの問い合わせになるため応答速度が遅い
    • 問い合わせ数が増加すると応答速度が低下する
    • 更新クエリが増えると分散 KVS のレプリケーション通信がボトルネックとなりデータの同期で遅延が発生する

    既存研究/技術はなにが解決できなかったのか

    • 同期遅延
      • Master/Slave 方式の分散 KVS の Slave をアプリケーションノードに置くことで解決
      • ⇢ しかし,レプリケーションラグが発生するためデータが常に最新とは限らない
    • 応答速度の遅延
      • キーシャーディング方式の分散 KVS を用いることで分割統治により同期を省くことができる
      • ⇢ しかし,シャーディングされるノードが必ずしもアプリケーションノードと同一ノードには配置されないため応答速度が遅延する

    同期遅延

    Master/Slave 方式の分散 KVS の Slave をアプリケーションノードに置くことで解決

    ⇢ しかし,レプリケーションラグが発生するためデータが常に最新とは限らない

    Master/Slave 方式の分散 KVS を用いた際の同期遅延

    応答速度の遅延

    キーシャーディング方式の分散 KVS を用いることで分割統治により同期を省くことができる

    ⇢ しかし,シャーディングされるノードが必ずしもアプリケーションノードと同一ノードには配置されないため応答速度が遅延する

    キーシャーディングの分散 KVS を用いた際の応答速度の遅延

    提案手法

    提案手法では,パーソナライズされたコンテンツ配信におけるデータの特性に着目し,単一のクライアントでのみの一貫性で要件を満たせることから,クライアント中心一貫性を用いた分散 KVS を提案する.

    提案手法のシステムアーキテクチャ

    応答性能の確保

    • 分散 KVS をコンテンツ配信アプリケーションと同一のノードに配置する
    • プロセス間通信でデータを交換することでネットワーク遅延を廃する

    単一ユーザの一貫性の確保

    • ロードバランサでユーザのコンテンツ配信アプリケーションへの接続を常に同一ノードに固定する
    • 以降ユーザには同一ノードで一貫性のあるデータ提供する
    • この状態を一貫性モデルの 1 つ,クライアント中心一貫性を確保しているに等しい状態である

    評価

    評価方法について

    • 評価を行うため提案手法のプロトタイプの実装を行った
    • memcached 互換のプロトコルで通信できる分散 KVS を Go 言語で実装した
    • ロードバランサの機能を用いてユーザの接続先ノードの固定した
      • ロードバランサーには HAProxy を用いた
      • 接続先ノードの固定には HAProxy の stick table を用いた
    • 実装はGitHub リポジトリで公開している
      • きれいな実装にはなってない

    評価は 2 つの観点から行う

    • 既存技術との応答速度の比較
    • 単一ユーザにおいて一貫性が保証できているか

    応答速度の評価方法

    提案手法の応答時間を測定し評価する. 評価の際には既存技術である Redis の応答時間を提案手法と比較する.

    評価には memtier_benchmark を用いた.

    実際の環境を模倣し以下の環境で評価をした.

    既存手法は単一ノードに別ノードよりネットワーク経由での接続

    提案手法は単一ノードないにおいての Unix Domain Socket での接続

    memtier_benchmark の引数は以下の通り

    --threads=16 --requests=10000

    並列パイプライン数(–pipeline) は 1 ~ 10 で変化させた.

    応答速度の評価結果

    提案手法と既存技術(Redis)による応答速度の比較

    応答速度の評価まとめ

    提案手法と既存技術の Redis の平均応答時間は

    • 提案手法が 4.32 ミリ秒
    • Redis が 16.79 ミリ秒

    提案手法による 10 ミリ秒以上の応答の高速化を確認した. 既存技術では応答時間の要件を満たせない一方,提案手法では要件を容易に充足できることも確認した.

    一貫性の評価方法

    提案手法でユーザ単位のデータの一貫性を確認する.

    評価に用いる以下の仕様の実験用アプリケーションを作成した.

    ユーザーの識別子ごとに何回のアクセスがあったかを分散 KVS に記録し,最新の値を分散 KVS から取得しレスポンスする.

    これを複数ノード配置し前段にロードバランサを設置しロードバランスを行う. クライアント側が計測しているリクエスト回数と分散 KVS で計測された数を比較し一貫性の評価を行った.

    一貫性の評価まとめ

    実験の結果,クライアントがリクエストした回数とレスポンスの結果は常に一致しており,クライアント自身が書き込んだ値を読み出すことができる一貫性が正しく機能していることを確認した.

    おわりに

    プロトタイプ実装を用いた実験では応答速度の要件を満たし,既存技術と比較し平均応答速度が 10 ミリ秒以上高速化された.

    一貫性においてはクライアント中心一貫性が正しく確保できていることを確認した.

    提案手法では今後の課題として,ノードダウン時や入替時の一貫性の担保がある.

    共有

    bootjp / ぶーと
    著者
    bootjp / ぶーと
    ミドルウェアエンジニア / 7年後に分散データベース研究の世界に貢献することを目指して


    目次