この記事は 自作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を用いてアプリケーションノードのデータ同期を行う
という手法が一般的に用いられる
身近なところでの代表的なコンテンツ配信のサービス例
- pixiv
- ABEMA
- YouTube
パーソナライズされたコンテンツ配信とは
昨今のコンテンツ配信では，利便性向上や効果的なマーケティングのために，リッチなコンテンツ配信が求められるようになり， ユーザーごとに異なるデータをユーザからの問い合わせ後に生成してコンテンツを配信するようになった．
具体的には
- 広告配信
- レコメンデーション
- 検索エンジン
- 通知管理システム
前述のシステムでは以下の3点を同時に満たす必要がある
- 高速な応答速度で
- ユーザー毎に異なるデータを
- 安定して配信する
つまりパーソナライズされたコンテンツ配信とは「ユーザーごとに異なるデータをユーザからの問い合わせ後に生成し応答するコンテンツ配信」と言い換えることができる．
具体的に広告配信のリアルタイム買い付けのRTB(Real Time Bidding)では業者間のオークションの応答速度に要件があり，多くはネットワーク遅延を含め100ミリ秒である．
一般に広告配信アプリケーションの処理は，50ミリ秒以内に収める必要があると言われており，したがってコンテンツ配信に用いる分散KVSはそれよりも高速に応答することが求められる．
以下を満たすものを要件とする．
- 10ミリ秒以下高速な応答性能
- 単一のユーザに一貫性のあるデータの提供
- 前述する2つの要素を安定して提供する
一般的な分散KVSを用いた際の構成例と問題
- 分散KVSはネットワーク越しの問い合わせになるため応答速度が遅い
- 問い合わせ数が増加すると応答速度が低下する
- 更新クエリが増えると分散KVSのレプリケーション通信がボトルネックとなりデータの同期で遅延が発生する
既存研究／技術はなにが解決できなかったのか
- 同期遅延
- Master/Slave方式の分散KVSのSlaveをアプリケーションノードに置くことで解決
- ⇢しかし，レプリケーションラグが発生するためデータが常に最新とは限らない
- 応答速度の遅延
- キーシャーディング方式の分散KVSを用いることで分割統治により同期を省くことができる
- ⇢しかし，シャーディングされるノードが必ずしもアプリケーションノードと同一ノードには配置されないため応答速度が遅延する
同期遅延
Master/Slave方式の分散KVSのSlaveをアプリケーションノードに置くことで解決
⇢しかし，レプリケーションラグが発生するためデータが常に最新とは限らない
応答速度の遅延
キーシャーディング方式の分散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の平均応答時間は
- 提案手法が 4.32ミリ秒
- Redisが16.79ミリ秒
提案手法による10ミリ秒以上の応答の高速化を確認した． 既存技術では応答時間の要件を満たせない一方，提案手法では要件を容易に充足できることも確認した．
一貫性の評価方法
提案手法でユーザ単位のデータの一貫性を確認する．
評価に用いる以下の仕様の実験用アプリケーションを作成した．
ユーザーの識別子ごとに何回のアクセスがあったかを分散KVSに記録し，最新の値を分散 KVSから取得しレスポンスする．
これを複数ノード配置し前段にロードバランサを設置しロードバランスを行う． クライアント側が計測しているリクエスト回数と分散KVSで計測された数を比較し一貫性の評価を行った．
一貫性の評価まとめ
実験の結果，クライアントがリクエストした回数とレスポンスの結果は常に一致しており，クライアント自身が書き込んだ値を読み出すことができる一貫性が正しく機能していることを確認した．
おわりに
プロトタイプ実装を用いた実験では応答速度の要件を満たし，既存技術と比較し平均応答速度が10ミリ秒以上高速化された．
一貫性においてはクライアント中心一貫性が正しく確保できていることを確認した．
提案手法では今後の課題として，ノードダウン時や入替時の一貫性の担保がある．
