@2008__VLDB__Scalable Query Result Caching for Web Applications

# Scalable Query Result Caching for Web Applications > [!abstract] 概要 > Web アプリケーションを動かすとき、バックエンドのデータベースシステムは性能上のボトルネックになりやすい。データベース部分をスケールさせる一般的な手法はクエリ結果キャッシュであるが、高いキャッシュヒット率を保ちながら、データベースの更新に対してキャッシュの一貫性を効率よく保つという課題がある。 > 本論文では、完全に分散した一貫性管理を備えた、プロキシ型として初の協調クエリ結果キャッシュである Ferdinand を提案する。高いキャッシュヒット率を維持するため、Ferdinand は各プロキシサーバ上のローカルなクエリ結果キャッシュと分散キャッシュの両方を用いる。一貫性管理は、高いスケーラビリティを持つ publish / subscribe システムで実現する。 > 完全に動作する Ferdinand のプロトタイプを実装し、他のいくつかのクエリキャッシュ手法と性能を比較評価した。その結果、Ferdinand が既存システムに対して得た性能向上には、高いキャッシュヒット率と一貫性管理の両方が不可欠であることを示した。 ## 論文情報 - **タイトル**: Scalable Query Result Caching for Web Applications - **著者**: [[Charles Garrod]] / [[Amit Manjhi]] / [[Anastasia Ailamaki]] / [[Bruce Maggs]] / [[Todd Mowry]] / [[Christopher Olston]] / [[Anthony Tomasic]] - **所属**: [[Carnegie Mellon University]](Garrod・Ailamaki・Maggs・Mowry・Tomasic)、[[Google]](Manjhi)、Yahoo! Research(Olston)、[[EPFL]](Ailamaki)、Akamai Technologies(Maggs)、Intel Research Pittsburgh(Mowry) - **掲載**: PVLDB 1(1), Proc. VLDB '08, Auckland, New Zealand, pp. 550-561 - **発表年**: 2008 年 8 月 - **対象システム**: [[Ferdinand]] ## 概要データベース駆動の動的 Web コンテンツを配信するプロキシ群が、互いのクエリ結果キャッシュを DHT で共有し、更新通知を publish/subscribe のトピックで配る構成を提案した論文である。無効化の対象を絞るため、アプリケーションのクエリ・更新テンプレートをオフラインで解析して、マルチキャストグループへの対応づけを決める。中央データベースはプロキシのキャッシュ内容を追跡せず、一貫性管理の負荷を負わない。TPC-W ブックストア、RUBiS オークション、RUBBoS 掲示板で評価し、協調キャッシュと publish/subscribe 型の一貫性管理の双方が性能向上に効くことを示した。 ## 問題設定 - **背景**: CDN は静的コンテンツのスケールには有効だが、動的コンテンツは利用者ごとにリアルタイムで生成され、バックエンドのデータベースへ問い合わせる。アプリケーションサーバの処理をプロキシへ移すのは容易でも、中央のデータベースサーバは依然としてボトルネックとして残る。 - **従来手法の限界**: データベースのレプリケーションは、更新の一貫性プロトコルのためにサーバ間の低遅延通信を要し、利用者に近い配置と両立しない。既存のプロキシ型クエリキャッシュは、(1) 一貫性の維持が非効率で更新の多い負荷に弱く、(2) キャッシュヒット率が低くスケーラビリティが頭打ちになる、という 2 点で制限される。 - **課題**: 高いヒット率を保つことと、更新に対して一貫性を効率よく保つことを、中央サーバに負荷を集めずに両立する。 - **前提とする一貫性**: 多くのクエリキャッシュと同様、複数文トランザクションの一貫性は緩める。単一文トランザクションだけなら完全な一貫性を保証する。 ## 提案手法 ### アーキテクチャ利用者は中央サーバではなくプロキシサーバへ直接接続する。各プロキシは、静的 Web キャッシュ、アプリケーションサーバ、データベースキャッシュ、キャッシュ一貫性モジュールを持ち、publish/subscribe 基盤と DHT オーバーレイに参加する。アプリケーション側の変更は、データベースドライバを Ferdinand 独自のものに差し替えるだけである。 ![[_attachments/2008__VLDB__Scalable-query-result-caching-for-web-applications/fig01-ferdinand-architecture.png]] *Figure 1: Ferdinand の全体アーキテクチャ* プロキシ内のキャッシュは、データベースクエリとその結果(マテリアライズドビュー)の単純な対応表である。クエリが来ると次の順で処理する。 1. ローカルキャッシュ(ローカルキャッシングモジュール)を引く 2. ミスなら DHT がクエリをハッシュし、そのクエリの「マスター」プロキシへ転送する 3. マスターのキャッシュにもなければ、マスターが中央データベースへ問い合わせ、結果をキャッシュして元のプロキシへ返すキャッシュ機構は単純さを優先し、リレーション単位の表現や、過去の結果から未見のクエリの結果を合成する処理は採らない。処理が軽く済むためである。 ![[_attachments/2008__VLDB__Scalable-query-result-caching-for-web-applications/fig02-proxy-components.png]] *Figure 2: Ferdinand プロキシサーバの構成要素* 更新は常に中央データベースへ転送し、同時に一貫性モジュールが関連するマルチキャストグループへ更新通知を publish する。通知を受けたプロキシは、影響を受けうるキャッシュ済み結果を無効化する。協調キャッシュの利点は、更新で無効化されるまでの間、各クエリが中央データベースで 1 回しか実行されない点である。代償は、全体がミスしたときの遅延が増える点(まずマスターへ転送するため)と、一貫性機構の複雑化である。 ### QUMA 問題とオフライン解析各プロキシはクエリ結果をキャッシュするとき、関連するマルチキャストグループを subscribe し、更新のたびに関連グループへ publish する。ある更新の影響を受けるクエリは、その更新の publish 先グループの少なくとも 1 つを subscribe していなければならない。この、クエリと更新を publish/subscribe のグループへ対応づける問題を **query / update multicast association(QUMA)** 問題と呼ぶ。良い対応づけは、(1) 更新通知が届いたグループ内のクエリにすべて影響する、(2) 更新が publish されないグループを subscribe しない、(3) 関連するクエリを同じグループにまとめて 1 回の通知で済ませる、を満たす。データベースの要素ごとにグループを作るのは非効率なので、まとめて読み書きされるデータのクラスタに 1 つのグループを対応させる。 Web アプリケーションのデータベース要求は、少数の静的なテンプレート(実行時にパラメータが束縛される)から成ることが多い。クエリ・更新テンプレートの各組に対し、Levy と Sagiv のクエリ・更新独立性解析を拡張して、証明可能に独立な組を判定する。実行時のパラメータ束縛をグループ名に埋め込めば(例: `GroupU1:name=?`)、名前が一致した場合にだけ通知が届き、無関係な通知が減る。グループ数はテンプレートのパラメータ値の数に比例して増えるが、既存の publish/subscribe は大量のグループを効率よく扱える。等価述語による選択なら精密に対応づけられ、範囲述語・結合・集約では実行時パラメータを埋め込めず無関係な通知が増える。 | テンプレート | 対応するグループ | |---|---| | U1(INSERT) | {GroupU1:name=?, GroupU1} | | U2(UPDATE) | {GroupU2} | | Q3 | {GroupU1:name=?, GroupU2} | | Q4 | {GroupU1} | | Q5 | {GroupU1, GroupU2} | 上表は Figure 3 にあたる在庫アプリケーションの正しい QUMA 解の例である。プロトタイプでは各ベンチマークの QUMA 解を手作業で作った。自動化は可能と見ており、著者らは自動化を進めている。 ### 二段のマルチキャストと正しさの保証各グループには、マスタープロキシとの通信に使う「マスター」グループが別にある。ローカルミスのとき、プロキシはクエリに関連するノンマスターグループをすべて subscribe し、確認応答を待ってからクエリをマスターへ転送する。マスターも関連するマスターグループを subscribe して確認を待ってから中央データベースへ転送する。更新時はまずマスターグループにだけ通知を出す。影響を受けるマスタープロキシは無効化したうえで、対応するノンマスターグループへ再 publish する。この二段構成が必要なのは、publish/subscribe が同一グループの購読者間で通知の配送順を制約しないからである。マスターグループを介さないと、ノンマスターのプロキシが結果を無効化した直後に、マスターが通知を受ける前の古い結果を取り直し、その古い結果を無期限にキャッシュしうる。 publish/subscribe が (1) 購読の確認応答を返し、(2) 購読確認から購読解除の開始までの publish をすべて通知する、という 2 つの性質を満たし、中央データベースが標準の one-copy serializability よりやや強い保証(非並行トランザクション T1 が T2 より先にコミットすれば直列順序でも T1 が先)を与えるなら、定理 1(更新 U の影響を受けるクエリ結果 q は、q をすでにキャッシュしている、またはこれからキャッシュするすべてのプロキシから取り除かれる)を証明した。証明の骨子は、マスタープロキシで無効化されること(補題 1)、他のすべてのプロキシで無効化されること(補題 2)を、購読確認と publish の時刻の前後関係で示すものである(付録 A)。あるキャッシュのビューは一時的に古くなりうるが、無期限に古いままにはならない。 ## 新規性 - 完全分散の一貫性管理を持つプロキシ型の協調クエリ結果キャッシュとして、著者らの知る限り初の提案である。DHT をデータベースクエリのキャッシュに使った性能研究も先行がないと述べている。 - テンプレートのオフライン解析でクエリ・更新を publish/subscribe のトピックへ対応づける QUMA の枠組みを、トピック型 publish/subscribe による一貫性管理に接続した。 - 一貫性管理が、すべての更新を中央データベースで受ける場合でも、スケーラビリティの律速になりうることを初めて定量的に示した。 - 著者らの過去の研究(CIDR 2005 の設計案、SIGMOD 2006 の秘匿データ、ICDE 2007 の無効化の手掛かり)は、単層キャッシュと単一プロキシでの実現可能性評価にとどまっていた。本論文は初の本格的な実装と評価である。 ## 実験設定 - **環境**: Emulab テストバッドの、3 GHz Xeon・メモリ 1 GB・10,000 rpm SCSI ディスクのサーバを使用した。プロキシ群は 100 Mbit スイッチで中央データベースへ接続した(集中型プロキシ基盤)。CDN 型の展開は、プロキシ間およびプロキシ・データベース間の遅延を独立変数として増やして模した。 - **実装**: 独自コンポーネントはすべて Java 1.5.0。各プロキシは Apache Tomcat を静的キャッシュ兼サーブレットコンテナとして動かす。協調キャッシュの DHT は Pastry、一貫性管理は Pastry 上の分散マルチキャスト基盤 Scribe(Castro らの Scribe であり、Meta の Scribe とは別物)を使う。ディスクベースのキャッシュ表は MySQL4 のリレーションで実装し、バックエンドも MySQL4 である。Scribe はノード障害時に配送の信頼性を保証しないため、その場合は Ferdinand が全キャッシュを一括で破棄する。障害時の評価は今後の課題とした。 - **ベンチマーク**: TPC-W ブックストア(書籍の人気を Zipf 分布に改変。商品 100 万件、登録利用者 86,400 人、480 MB。閲覧ミックス 12 プロキシ、ショッピングミックス 8 プロキシ)、RUBiS オークション(商品 33,667 件、利用者 10 万人、990 MB、8 プロキシ)、RUBBoS 掲示板(8 プロキシ、1.6 GB)。データベース要求のうち更新の割合は、ブックストアのショッピングミックスで約 14%、オークション約 7%、掲示板約 2% である。Web 要求あたりでは、いずれも 20-25% の Web インタラクションが更新を伴う。 - **比較対象**: NoProxy(プロキシなしの 3 層)、NoCache(Web・アプリケーションサーバだけを複製し、プロキシ側でキャッシュしない)、SimpleCache(各プロキシが独立したクエリキャッシュを持ち、ミスは直接中央へ送る。一貫性管理は publish/subscribe)、Ferdinand。一貫性管理の比較には、中央が全プロキシへ更新をブロードキャストする Broadcast も加えた。 - **指標**: 応答時間しきい値(既定 3 秒、90% のインタラクションが満たす)の下で維持できる最大スループット(WIPS)。ウォームなキャッシュで、約 6 時間の長時間実行の後に測定した。 ## 実験結果まず、NoProxy から Ferdinand までの 4 方式のスループットを 4 種のワークロードで比べた。Ferdinand はすべてのワークロードで SimpleCache を上回った。 ![[_attachments/2008__VLDB__Scalable-query-result-caching-for-web-applications/fig04-throughput-comparison.png]] *Figure 4: 他のスケーラビリティ手法との比較スループット* - **ブックストア(閲覧ミックス)**: NoProxy 比で 13.4 倍、SimpleCache 比で約 3 倍にスケールした。 - **オークション**: SimpleCache 比で 40% 向上し、NoCache 比で約 3 倍となった。ただしオークションは現在時刻を埋め込んだクエリが多く、そもそもキャッシュヒットしない。 - **掲示板**: SimpleCache 比で約 80% 向上し、NoCache 比で約 2.5 倍となった。 - NoCache は、データ集約的なブックストアと掲示板では NoProxy をわずかに上回るだけであった。Web・アプリケーションサーバの複製だけでは、中央データベースが律速する。キャッシュミス率は Table 1 のとおりで、Ferdinand は全ワークロードで SimpleCache より低い。あるプロキシのローカルキャッシュにないクエリ結果でも、別のプロキシがすでにキャッシュしている可能性が高いことを示す。 | ワークロード | SimpleCache | Ferdinand | |---|---|---| | ブックストア閲覧ミックス | 17% | 7% | | ブックストアショッピングミックス | 22% | 14% | | オークション | 40% | 17% | | 掲示板 | 20% | 11% | 次に、サーバ間往復遅延を変えて、ブックストア閲覧ミックスのスループットを測った。 ![[_attachments/2008__VLDB__Scalable-query-result-caching-for-web-applications/fig05-latency-throughput.png]] *Figure 5: サーバ間往復遅延に対する Ferdinand と SimpleCache のスループット* 遅延が増えると両方式とも劣化する。Ferdinand の劣化の方が大きい。両キャッシュにミスしたクエリが、高遅延のホップを複数回たどるためである。Ferdinand は 50 ms 付近まで SimpleCache を上回る。60 ms では SimpleCache が僅差で上回る。80 ms では、どちらもショッピングカートのサーブレットを 3 秒以内に応答できなくなる。この悪化の一部は、指標が「各インタラクションを 90% しきい値以内に返せること」を要求する点に由来し、多数のデータベース要求を発行するサーブレットが効いている。60 ms でも Ferdinand は 100 WIPS 超の負荷を、しきい値をわずかに超える程度で支えられた。最後に、publish/subscribe 型の一貫性管理をブロードキャスト型と比べた。 ![[_attachments/2008__VLDB__Scalable-query-result-caching-for-web-applications/fig06-broadcast-comparison.png]] *Figure 6: ブロードキャスト型一貫性管理との比較スループット* - ブックストアの両ミックスで、Broadcast は Ferdinand のキャッシュミス率が律速になる前に、一貫性管理がボトルネックになった。 - 閲覧ミックスでは、DHT 型の協調キャッシュを持つ Broadcast が SimpleCache をわずかに上回るだけであった。ショッピングミックスでは更新率が高く、SimpleCache が Broadcast を上回った。 - オークションと掲示板は読み取り中心で、更新は毎秒約 10 件にとどまり、どちらの方式でも通知を容易に配れた。 ## 考察 - 協調キャッシュ(ヒット率)と publish/subscribe 型無効化(一貫性管理の効率)の両方が、Ferdinand の性能向上に不可欠である。 - ブロードキャストや、中央がキャッシュ内容を追跡するディレクトリ方式は、いずれも中央サーバの負荷になる。Ferdinand は中央に一貫性の管理状態を持たせない。 - 高遅延環境では、まずマスターへ転送する協調キャッシュの代償が支配的になる。著者らは、アプリケーションが多数のクエリを直列に発行しないよう書き換える、独立クエリを並列に実行する、コンパイラ最適化に似た手法でアプリケーションとデータベースの相互作用を自動的に改善する、といった対応を挙げる。 - 現状は、再利用される見込みの低い結果も含めてすべてをキャッシュするので、subscribe・無効化通知・unsubscribe の手間が一貫性管理を圧迫する。オフラインとオンラインの適応的な手法で、使われそうにない結果のキャッシュを避けることを今後の課題とした。 - 関連研究の位置づけとして、IBM の DBCache・DBProxy と NEC CachePortal は集中型の一貫性管理を持つ。DBProxy はリレーション単位の表現で、未キャッシュのクエリを既存の結果から合成できる。完全レプリケーション(C-JDBC)は全更新のブロードキャストが必要でスケールしにくく、部分レプリケーション(GlobeDB・GlobeTP)はデータ配置の問題が生じる。クエリキャッシュはワークロード変化に自動で適応できる点で有利である。 ## 強み / 弱点・課題 - **強み**: 一貫性管理を publish/subscribe に任せ、中央サーバが各プロキシの状態を持たない設計にした。アプリケーションの変更は JDBC ドライバの差し替えだけで済む。正しさを、通知の到着順を仮定せずに証明した。3 種の標準ベンチマークで、要素ごとの寄与を分解して評価した。 - **弱点・課題**: - QUMA 解を手作業で作っており、自動導出は未達である。範囲述語・結合・集約では無関係な通知が増える。 - 複数文トランザクションの一貫性は保証しない。 - 証明は publish/subscribe とデータベースが信頼できることを仮定する。Scribe はノード障害時に配送を保証せず、障害時の全キャッシュ破棄と障害評価は未実施である。 - サーバ間往復遅延が 60 ms を超える環境では、協調キャッシュの転送コストが利得を上回り、SimpleCache を下回る。 - ベンチマークの一部(オークションの時刻埋め込みクエリ)では、そもそもヒット率が上がらない。 - 評価は 8-12 台のプロキシで、Zipf 分布に改変したブックストアなどの合成ワークロードに限られる。ディレクトリ方式との比較は実施しておらず、今後の課題としている。 ## 関連 - 概念: [[分散キャッシュ]] / [[キャッシュ無効化]] / [[分散メッセージブローカ]] / [[一貫性ハッシュ法]] / [[コンテンツ配信ネットワーク]] - エンティティ: [[Ferdinand]] / [[Carnegie Mellon University]] / [[MySQL]] ## 出典 - [[.raw/papers/2008__VLDB__Scalable-query-result-caching-for-web-applications.pdf]]