# Quaestor: Query Web Caching for Database-as-a-Service Providers > [!abstract] 概要 > 今日、ウェブの性能は主にエンドデバイスとクラウドサービスの間の往復遅延で決まる。性能を改善するには、サービスはデータへのアクセス遅延を最小化する必要がある。本論文は、既存のコンテンツ配信とウェブキャッシュの基盤に依拠する、低遅延への新しい手法を提案する。中心となる発想は、調整可能な一貫性保証、とくに有界な陳腐化(bounded staleness)のもとで、アプリケーションに依存しないクエリ結果とレコードのキャッシュを可能にすることである。QUAESTOR(Query Store)は、有効期限型と無効化型の両方のウェブキャッシュを取り込むために、2 つの鍵となる概念を用いる。(1) 陳腐化している可能性のあるデータを示す Expiring Bloom Filter というデータ構造、(2) キャッシュヒット率を最大化するために統計的に導出したキャッシュ有効期限である。分散クエリ無効化パイプラインによって、キャッシュ済みクエリ結果の変更はリアルタイムに検知される。提案するキャッシュアルゴリズムは、データ中心のクラウドサービス(たとえばデータベース・アズ・ア・サービス)が、遅延と陳腐化の上限を交換する新しい手段を与える。QUAESTOR は、低遅延ウェブサイト向けのクラウドサービスであるバックエンド・アズ・ア・サービスのプラットフォーム Baqend の中核技術である。シミュレーションと実験の両方で、QUAESTOR の拡張性と性能の実証的な根拠を示す。結果は、読み取り中心の負荷では QUAESTOR のキャッシュにより最大 10 倍の高速化が得られることを示している。 ## 論文情報 | 項目 | 内容 | |---|---| | 著者 | [[Felix Gessert]]([[Baqend]])・[[Michael Schaarschmidt]](Cambridge)・[[Wolfram Wingerath]](Hamburg)・[[Erik Witt]](Baqend)・[[Eiko Yoneki]](Cambridge)・[[Norbert Ritter]](Hamburg) | | 発表会議 | VLDB 2017(PVLDB Vol. 10, No. 12, pp. 1670-1681) | | 種別 | システム論文(手法と実装、EC2 実験、モンテカルロ・シミュレーション、本番事例) | | 対象 | 集約指向の NoSQL(MongoDB と Redis)上の DBaaS。REST/HTTP で動的データを配る任意のシステムに適用可能とされる | ## 概要 DBaaS のクエリ結果とレコードを、ブラウザ・ISP・CDN・リバースプロキシといった既存の HTTP キャッシュで配る方式を示した論文である。有効期限型キャッシュはサーバから無効化できないため、陳腐化の可能性をクライアントに知らせる Expiring Bloom Filter(EBF)で鮮度を補正する。無効化型キャッシュには、ストリーム処理基盤 InvaliDB が更新の影響を受けるクエリを実時間で検知して purge を送る。TTL は統計モデルで推定する。読み取り中心の負荷では、キャッシュなしと比べてスループットが 11 倍になり、クエリ遅延は平均 3.2 ms まで下がった。 ## 問題設定 ページ読み込み時間の遅れの原因はバックエンド、フロントエンド、ネットワーク遅延の 3 つである。2017 年時点で平均的なサイトの表示には 100 を超える HTTP リクエストが要り、それらの往復遅延が最大の要因になる。遅延は物理的な往復時間で下限が決まるため、データをクライアントに近づけるしかない。 既存の DBaaS は REST API で提供されるものの、いずれも有効期限型の HTTP キャッシュを活用していない。ウェブキャッシュは不変ファイルにしか使えず、クエリ結果のような予測不能に変わるデータは静的な TTL と相性が悪いと考えられてきた。TTL が長ければ陳腐な読み取りが増え、短ければヒット率が落ちる。 図1(Figure 1): 単純なニュースサイトを、冷えたブラウザキャッシュと温まった CDN キャッシュで、EC2 の各リージョンから読み込んだときの平均初回読み込み時間。Baqend を Firebase、Parse、Kinvey、Azure Mobile Services と比較している。 ![[_attachments/2017__VLDB__Quaestor-Query-Web-Caching-for-Database-as-a-Service-Providers/fig01-page-load-comparison.png]] 解くべき課題は次の 3 つである。 1. 無効化検知: ある更新が、キャッシュ済みクエリの結果集合を変えるか。 2. キャッシュ整合: DBaaS が無効化できないキャッシュの整合をどう保つか。 3. キャッシュ可能性: どのクエリとレコードをキャッシュし、最適な TTL はいくつか。 図2(Figure 2): クエリのウェブキャッシュにおける 3 つの中心課題。 ![[_attachments/2017__VLDB__Quaestor-Query-Web-Caching-for-Database-as-a-Service-Providers/fig02-three-challenges.png]] ## 提案手法 ### Expiring Bloom Filter(整合) EBF は、あるクエリまたはレコードが陳腐化している可能性があるかを答えるデータ構造である。偽陽性は不要な再検証を招くだけで一貫性には影響しないため、許容する。クライアントは接続時に平坦な Bloom filter を受け取り、クエリの前に SDK が EBF を引いて、通常のキャッシュ読み込みか再検証かを決める。サーバ側の EBF はカウンティング Bloom filter として持ち、TTL が切れたクエリを取り除く。クライアントは、再検証済みのクエリを次の EBF 更新まで新鮮とみなす差分ホワイトリストも持つ。 生成時刻 t1 の EBF を使う時刻 t2 のクエリは、Δ = t2 − t1 の Δ-原子性を満たす(定理 1、背理法で証明)。EBF は最初のクエリを再検証に昇格させて最新の EBF を同乗させる形で、Δ 秒ごとに非破壊で更新する。サイズを TCP の初期輻輳ウィンドウ(約 14.6 KB)に合わせると 1 往復で送れ、陳腐なクエリが 20,000 件のとき偽陽性率は 6%である。読み取りは EBF の複製、書き込みはテーブルごとの分割で伸ばし、Redis 実装は 1 インスタンスあたり毎秒 15 万を超える処理を支える。 図3(Figure 3): QUAESTOR のクライアント・サーバ構成。番号は EBF の取得、陳腐化判定、キャッシュ応答、再検証の順序を表す。 ![[_attachments/2017__VLDB__Quaestor-Query-Web-Caching-for-Database-as-a-Service-Providers/fig03-architecture.png]] ### 一貫性保証 Δ-原子性に加え、単調書き込み(データベースが保証)、自分の書き込みの読み取り、単調読み取り(クライアントが最新の読み取り版を保持)を既定で与える。因果一貫性と強い一貫性(線形化可能性)は、キャッシュミスを増やす代わりにクライアントが選べる。さらに、楽観的並行性制御に基づく ACID トランザクションも提供する(詳細は省略されている)。 図4(Figure 4): QUAESTOR が提供する一貫性水準と、それぞれの実現方法。 ![[_attachments/2017__VLDB__Quaestor-Query-Web-Caching-for-Database-as-a-Service-Providers/fig04-consistency-levels.png]] ### InvaliDB(無効化検知) キャッシュ済みクエリはすべて InvaliDB に登録される。InvaliDB は書き込みの後像(after-image)を全登録クエリと照合し、add(結果集合に入る)、remove(出る)、change(残ったまま更新)の通知を出す。id リスト形式の結果は add と remove だけで無効化し、オブジェクトリスト形式は change でも無効化する。 図5(Figure 5): オブジェクトが更新されるときの add、change、remove の通知。 ![[_attachments/2017__VLDB__Quaestor-Query-Web-Caching-for-Database-as-a-Service-Providers/fig05-notifications.png]] 処理は、クエリ取り込み、変更ストリーム取り込み、照合の 3 つで、Apache Storm 上に分散する。照合は、到着するデータとアクティブなクエリの両方を互いに直交にハッシュ分割する。各ノードは全クエリの一部と全更新の一部だけを担当するため、単一ノードの性能が全体を制限しない。ORDER BY・LIMIT・OFFSET を含むクエリは状態を持つため、順序に関する状態を別の層でクエリごとに分割して保持する。結合と集約は未対応である。 図6(Figure 6): InvaliDB の負荷分散。9 ノードで、各ノードが一部のクエリと一部の更新だけを受け持つ。 ![[_attachments/2017__VLDB__Quaestor-Query-Web-Caching-for-Database-as-a-Service-Providers/fig06-invalidb-workload.png]] ### 統計的 TTL 推定と結果表現 キャッシュ済みレコードは、次の更新の直前に失効するのが理想である。各レコードの書き込み到着をポアソン過程とみなし、結果集合 n 件の最初の書き込みまでの時間は、レートの和 λmin = λw1 + … + λwn の指数分布に従う。分位点関数 F⁻¹(p, λmin) = −ln(1−p)/λmin が、確率 p で失効前に書き込みが来る TTL を与える(式 1)。分位点を変えると、ヒット率と無効化数を交換できる。クエリの TTL は初期値をこの推定で決め、無効化のたびに実測 TTL を使って指数移動平均で更新する(式 2)。クエリ結果は、id リスト形式かオブジェクトリスト形式かをコストモデルで選ぶ。前者は省スペースでレコード単位のヒット率が高いが往復が増える。 図7(Figure 7): クエリキャッシュの一連の流れ。EBF 取得、再検証、キャッシュ応答、無効化を順に示す。 ![[_attachments/2017__VLDB__Quaestor-Query-Web-Caching-for-Database-as-a-Service-Providers/fig07-end-to-end.png]] ## 新規性 - 動的なクエリ結果を、標準のウェブキャッシュ(有効期限型と無効化型の両方)だけで、有界な陳腐化の保証つきで配る最初の手法だと主張する。 - 陳腐化情報を 1 つの EBF に集約し、クライアントが選ぶ Δ を許す。Pileus はクライアントが各レプリカから時刻を取得するため、この点で拡張性が劣ると位置づける。 - 更新ストリームとクエリ集合の両方を分割する無効化検知により、更新スループットにも登録クエリ数にも性能が縛られない。代償は結合が現実的でなくなることである。 - レコード単位の書き込みレートから、クエリの TTL を初回から推定し、無効化で収束させる。Alex プロトコルは新規クエリに推定を与えられず、Alici らの方式はオフライン学習が要ると対比する。 ## 実験設定 YCSB を拡張した自作フレームワーク(多スレッド・多クライアント)を使う。MongoDB は m3.xlarge 3 台(シャード 2、設定サーバ 1)、QUAESTOR サーバ 3 台、EBF と active list の Redis が各 1 台で、EC2 アイルランドに置き、負荷は北カリフォルニアから与える。CDN には Fastly(往復 4 ms)を使う。比較対象は、キャッシュなし(Orestes DBaaS)、CDN のみ、EBF によるクライアントキャッシュのみである。10 表、各 10,000 文書、表ごと 100 の異なるクエリ(平均 10 件を返す)を生成し、Zipf 分布でキーを選ぶ。各点は 5 分間の負荷で測る。陳腐化の解析は、全順序のタイムスタンプが得られるモンテカルロ・シミュレーションで行う。InvaliDB は別に、c3.large の 1〜16 ノードで、毎秒 1,000 挿入のもとに通知遅延を測る。 ## 実験結果 - 読み取り 99%の負荷(クエリと読み取りが半々、書き込み 1%)で 3,000 接続のとき、QUAESTOR はキャッシュなしの 11 倍、EBF のみの 5 倍、CDN のみ(InvaliDB あり)の 69.5%増のスループットを出した。クライアントと QUAESTOR 間の平均往復遅延は 145 ms だった。クエリの平均遅延は 3.2 ms、読み取りは 17.5 ms である。クエリのほとんどはクライアントキャッシュのヒット(遅延ほぼ 0)、CDN のヒットは約 4 ms、ミスは約 150 ms だった。 - クエリ数を 1,000 から 10,000 に増やすと、レコードがクエリ結果に含まれる副作用で読み取りのヒットが増え、読み取り遅延は 20 ms から 15 ms へ下がった。クエリ遅延は、クライアントのヒット率低下で上がる。CDN のヒット率は安定している。 - 更新率を上げるとクライアントのクエリヒット率は下がるが、EBF の更新間隔の影響は小さい。更新率が高いと TTL も短くなるため、更新間隔を縮めても陳腐化が増えるだけで利得が出ない。 - 文書数を 10,000 から 1,000 万まで増やすと、キャッシュが埋まるまでに時間がかかる。クエリ遅延は 13.8、5.5、11.9、34.8 ms と非単調で、読み取り遅延は 70、40.2、27.2、133 ms だった(表1)。 - 陳腐化の実測はシミュレーションで行った。クライアントの陳腐化は EBF の更新間隔で決まる。CDN の陳腐化は常に 0.1%未満だった。TTL の推定分布は、真の TTL 分布と大半で近く、裾の長い部分で誤差が大きい。 - InvaliDB は、1〜16 ノードのすべてで、1 ノードあたり 300 万 ops/s まで 99 パーセンタイル遅延 20 ms 未満、400 万 ops/s まで 30 ms 未満だった。約 500 万 ops/s で遅延が急増して限界に達した。スループットはノード数に線形に伸びた。 - 本番では、Baqend の顧客 Thinks が、テレビ番組での紹介時に 50,000 同時ユーザ(毎秒 2 万超の HTTP リクエスト)を捌き、CDN ヒット率 98%、コンバージョン率 7.8%(業界平均の約 3 倍)だった。DBaaS サーバ 2 台と MongoDB シャード 2 つで足りた。 図8(Figure 8): クラウド上の評価。Figure 8a スループット、Figure 8b 読み取り遅延、Figure 8c クエリ遅延、Figure 8d クエリ数と平均遅延、Figure 8e クライアントと CDN のヒット率、Figure 8f クエリ遅延のヒストグラム。 ![[_attachments/2017__VLDB__Quaestor-Query-Web-Caching-for-Database-as-a-Service-Providers/fig08-cloud-evaluation.png]] 図9(Figure 9): EBF の更新間隔ごとの、更新率とクライアントのクエリキャッシュヒット率。 ![[_attachments/2017__VLDB__Quaestor-Query-Web-Caching-for-Database-as-a-Service-Providers/fig09-hit-rate-update.png]] 表1(Table 1): Zipf 定数 0.99 で文書数を増やしたときの性能。 ![[_attachments/2017__VLDB__Quaestor-Query-Web-Caching-for-Database-as-a-Service-Providers/table1-document-counts.png]] 図10(Figure 10): 10 と 100 クライアント、更新間隔ごとの、陳腐な読み取りとクエリの割合。 ![[_attachments/2017__VLDB__Quaestor-Query-Web-Caching-for-Database-as-a-Service-Providers/fig10-staleness.png]] 図11(Figure 11): QUAESTOR の TTL 推定と真の TTL の累積分布。 ![[_attachments/2017__VLDB__Quaestor-Query-Web-Caching-for-Database-as-a-Service-Providers/fig11-ttl-cdf.png]] 図12(Figure 12): 指定した遅延上限を満たす InvaliDB のスループットとクラスタサイズ。 ![[_attachments/2017__VLDB__Quaestor-Query-Web-Caching-for-Database-as-a-Service-Providers/fig12-invalidb-throughput.png]] ## 考察 - 読み取りの多い負荷が前提で、更新が増えるほど TTL が短くなり、キャッシュの利得は縮む。スケールの上限は基盤データベースの書き込みスループットで決まるとされる。 - 無効化型キャッシュ向けには Δ を Δ − ΔInvalidation に調整すると、再検証を CDN が捌けてバックエンドの負荷が減る。 - 論文は、ジオレプリケーションとは直交し、組み合わせられるとする。特定の地理配置に調整したジオレプリケーションのほうが速い場合はあると認めており、比較はしていない。 - HTTP/2 が普及すれば、id リスト形式を常に選べる、EBF の更新が先頭ブロッキングを起こさない、といった単純化が可能になると展望する。 - 結合と集約は InvaliDB で未対応であり、集約は進行中の課題である。 ## 強み / 弱点・課題 - 強み: 専用のキャッシュサーバやレプリカ拠点を要さず、既存の HTTP 基盤と CDN で低遅延を得る。クライアントが Δ を選べる。EBF の性質を定理で示している。InvaliDB の線形スケーリングを、遅延上限つきで実測した。本番の事例で効果を確かめている。 - 弱点・課題: 結合と集約が使えない。トランザクションの詳細と、id リスト対オブジェクトリストのコストモデルは、紙幅を理由に省かれている。クライアント側の陳腐化率は、更新間隔 50 秒で最大 0.45 程度に上るシミュレーション結果がある。ジオレプリケーション系(Pileus など)との実測比較はない。評価は著者らの自社システムと自作のベンチマークで行われている。 ## 関連 - ソース: [[@2008__VLDB__Scalable Query Result Caching for Web Applications]] - 概念: [[Webキャッシュ]] / [[ブルームフィルタ]] / [[有界な陳腐化]] / [[キャッシュ無効化]] / [[コンテンツ配信ネットワーク]] - エンティティ: [[Baqend]] / [[Felix Gessert]] / [[Michael Schaarschmidt]] / [[Wolfram Wingerath]] / [[Erik Witt]] / [[Eiko Yoneki]] / [[Norbert Ritter]] / [[MongoDB]] / [[Redis]] / [[Fastly]] / [[YCSB]] / [[Ferdinand]] ## 出典 - `.raw/papers/2017__VLDB__Quaestor-Query-Web-Caching-for-Database-as-a-Service-Providers.pdf`