でこてっくろぐ ねお

でこてっくろぐ(http://dekokun.github.io/)から進化しました。でこらいふろぐ(http://dekolife.hatenablog.com/)の姉妹版。デコテックログ(deko tech log)である

Varnishによる一貫性を考慮した積極的キャッシュ戦略実験

この記事は、はてなエンジニアアドベントカレンダー2016の9日目の記事です。昨日は id:cockscomb による Swift 3 の Data とポインタ使いこなし術 - Hatena Developer Blogでした。今日はISUCON 6の予選問題とVarnishを組み合わせてみた話を書きます。

はじめに

みなさんは今年の夏に行われたISUCON6には参加しましたか?私は参加しましたが予選落ちでした。また、最近、私は業務でVarnishというHTTPキャッシュサーバに触ることが多いです。 今回、ISUCON6が終わった後、Varnishで何ができるかの検証がてらISUCON6の予選問題で少しトリッキーな実装をした話を書きます。

実装の方針は以下のとおりです。

  • キャッシュに必要な実装以外は出来る限りアプリケーションには手を入れない
  • 全てのリクエストをキャッシュサーバを通す
  • 更新は即座に反映させつつ出来る限りキャッシュヒット率を高くする

本記事では、どのようにすればその作戦が可能になるのか、実際に行ってみてどうだったかなどをまとめます。

ISUCON6 予選問題について

どのようなアプリケーションかについて詳しくは ISUCON6 予選問題の解説と講評 を読むと分かるのですが、Wikipediaのようなアプリケーションでした。 複数のキーワードとその解説が載っており、キーワードの解説内に別のキーワード名が出現している場合は、そのキーワードへのリンクが自動的に貼られます(以下この記事では"キーワードの自動リンク機能"と呼びます)。 また、ユーザはログインすればキーワードとその解説の投稿が可能であり、更にはてなスターのような、投稿に対してスターをつけるような機能がありました。

ISUCONで最初に用意された実装ではこのキーワードの自動リンク機能が非常に遅く、ここをどのように対処するかが勝負の分かれ道でした。

リポジトリ

運営が用意したリポジトリをforkして以下で作業をしていました。

GitHub - dekokun/isucon6-qualify

今回の記事で扱うのは以下ファイルです。

  • アプリケーションコードはwebapp/go以下
  • キャッシュサーバの設定はwebapp/config/default.vcl

作戦

最初にも書きましたが、以下3点の作戦で進めました

  • キャッシュに必要な実装以外は出来る限りアプリケーションには手を入れない
  • 全てのリクエストをキャッシュサーバを通す
  • 更新は即座に反映させつつ出来る限りキャッシュヒット率を高くする

proxyサーバアプリケーションサーバの間にVarnishを入れ、全ての参照リクエストについてキャッシュが存在すればそれを返し、存在しなければVarnishがアプリケーションサーバにリクエストしてその結果を返します。 なお、この方針ではISUCONのベンチマークの得点は極めて低いです。理由なども以下に記載しています

なぜキャッシュで進めようとするのか

  • 最近仕事でよくVarnishに触れていることもあり、Varnishを活用すると何がどこまで出来るのかを実際に実装して試してみたくなったため
  • 上記に関連して、一度、"参照リクエストをキャッシュしつつキャッシュデータを適切に破棄して更新結果は即座に反映されるようにする"というのをやってみたかったから
    • “いつかはやるぞ"と思いつつ、なかなか始められていなかったところにちょうど手頃そうな規模感なISUCONの予選問題がふってきたから

構成

以下のような3段構成になっています。実際のISUCON予選問題はマイクロサービス化しておりもう少し複雑なのですが、この記事を読む上では以下の構成を認識していれば十分です。ISUCON予選を解いた人のためにもう少し解説すると、今回は説明の単純化のためにIsudaの話しかしません。この記事を読む上ではIsutarやIsupamはなかったこととして考えて頂いて問題ありません。 nginxからのリクエストは全てVarnishを通り、VarnishはリクエストがGETリクエストかつキャッシュがあればそれを返し、それ以外の場合はAppにリクエストを渡すという構成です。

     |
  [nginx]
     |
 [Varnish]
     |
 [App(golang)]

正確にはESIでのVarnishからAppの呼び出しがあるので上記以外のHTTPの流れもあるのですが、そちらについては以下で説明します。

レスポンスをキャッシュさせるとどのような問題が起きるか

動的なサービスにおいてレスポンスをキャッシュさせるには色々と考えなくてはいけないことがあります。今回のISUCON予選のアプリケーションでは以下2つの大きな問題を解決する必要がありました。

  • ページが更新された時にどのように即座に新しいデータを反映させるか?
  • ページ全てをキャッシュできない

以下で問題の詳細及び解決策の案、今回はどのように解決したかについて記述します

ページが更新された時にどのように新しいデータを反映させるか?

ページをキャッシュするということは何もしなければキャッシュ期間中は同じページが出続けることになります。今回のISUCONでは、データの更新が反映されていないと点数が下がってしまう作りになっていたため、キーワードの更新があった場合はそのページのキャッシュを破棄することが必要です。 実際のサービスでも、更新直後に更新対象のページにアクセスした際に更新結果が表示されていないとユーザが違和感を覚える場合が多いかと思います。

更新内容の反映は更新があったキーワードのページのキャッシュを破棄するだけでいいかというとそれだけではありません。 今回のISUCON予選問題では新たにキーワードが投稿されたタイミングで既存のページでもそのキーワード文字列を含むページでは自動的にリンクが貼られる必要があるため、適切にそれらを探し出してキャッシュデータを破棄する必要があります。

ページが更新された時にどのように新しいデータを反映させるか?解決策案

  1. キャッシュ期間を短めにしてデータを更新してもキャッシュは破棄しない
  2. 更新があった際に全キャッシュを破棄する
  3. 更新があった際に更新に関係するページのキャッシュを破棄する

1. については、キャッシュ期間を短くするとダイレクトにキャッシュヒット率が低下するため今回は採用しません。実際のサービスにキャッシュを入れることを考えた場合はこの方式が実装は一番簡単になるので、必要な要件とキャッシュヒット率とを考えた上でこの方式を採用する場合は多いかなと思います。 2. は更新が多いとキャッシュヒット率が極端に低下するため、あまりうれしくはなさそうです。更新頻度の低いサービスであれば採用する余地はありそうです。 3. は、適切にこれを実装出来るのであればこの方式が一番キャッシュヒット率が上がり嬉しそうです。今回はこちらを採用しています。

ページ全てをキャッシュできない

ISUCON予選のアプリケーションにはログイン機能が存在し、ログインすると全ページにおいて"Hello, ○○(ユーザ名)“という表記が出ます。 これにより普通にページ全てをキャッシュしてしまうと"ログインした際に別のユーザ名が表示される"等の問題が起きることになります。 このような問題は一般的なサービスでも、ログイン機能がある場合よく起きるのではないかなと思います。

f:id:dekokun:20161209112806p:plain

ページ全てをキャッシュできない 解決案

  1. ユーザ名の表示したさとキャッシュのしたさとその他の実装の難易度を天秤にかけて各ページのユーザ名は表示しなくて良いことに決める
  2. ユーザ名などはJS等で別途読み込む
  3. Cookieを見てログインしていたらキャッシュを返さない
  4. Cookie毎にキャッシュを保持
  5. VarnishのESIによるテンプレート分割(ISUCON予選問題だと、"Hello, ○○さん" の部分だけ別のテンプレートとして扱い、メインのページでそのテンプレートを呼び出す記述を書きVarnishがそれぞれを合体させる)してそれぞれキャッシュ

1.2. はHTMLの構造が変わってしまいISUCONのベンチマーカのチェックが通らなくなるので今回は採用できません。実際にこの方針が採用できる場合、キャッシュ周りの実装は極めてシンプルになるのでお薦めです。 3.についてはログインユーザにキャッシュが返せずキャッシュヒット率が下がってしまいます。が、全参照ユーザの中でログインユーザの割合の少ないようなサービスでは有効です。 4. は、1ページ1ユーザ毎に1つのキャッシュを用意する必要が出てきて、キャッシュヒット率が下がってしまいます。こちらも 3. と同様にログインユーザの割合が少ない場合や、ログインユーザが非常に高頻度に同じページにアクセスするような状況では有効な手立てになります。 5. については、複雑な構成になってしまい運用に難が出る、アプリケーションサーバへのリクエスト数が増えがちではありますが、とにかく必要な部分を必要な分だけキャッシュするという戦略が取れるため、今回はこの方式を選択しています。

実装

今回、キャッシュサーバとしてVarnishを使用しているため、Varnishではどのような実装で上記戦略を実施することができるのかを解説していきます。

必要な部分でキャッシュを行い、それ以外ではキャッシュを行わない

リクエストの全てがVarnishを通る構成であるため、どのページはキャッシュ可能でどのページはキャッシュしないかをアプリケーションサーバが指示する必要があります。

今回は、キャッシュするかどうかだけ指定したい状態でエンドポイント毎の細かなキャッシュの生存期間制御などは行わず、キャッシュさせたくないエンドポイントではHTTPヘッダに Cache-Control: no-cache を付与し、キャッシュさせたいエンドポイントでは Cache-Control: public, max-age=86400 を付与しています

https://github.com/dekokun/isucon6-qualify/blob/dba81a180ca7b722e45727f11278c19587e9d103/webapp/go/isuda.go#L49-L55

更新時の適切なキャッシュの破棄

更新時のキャッシュの破棄のためには、以下が必要です。

  1. キャッシュに対するタグ付け
  2. データの更新時にタグを指定してのキャッシュの破棄

キャッシュに対するタグ付け

Varnishはアプリケーションサーバからのレスポンスヘッダをタグとして使用することができます。今回は、KEYWORDという名前のHTTPヘッダでそのキーワードのIDを指定しています。

https://github.com/dekokun/isucon6-qualify/blob/dba81a180ca7b722e45727f11278c19587e9d103/webapp/go/isuda.go#L145

   w.Header().Set("KEYWORD", strconv.Itoa(e.ID))

データの更新時にタグを指定してのキャッシュの破棄

データの更新が走った際にタグを指定して関連するページのキャッシュの破棄を行います。 今回は、関連するページはMySQLのFULLTEXT インデックスを使用して取得しています。この記事の本筋とは関係ないため説明は省略しますが、詳しくはこのあたりを見るといいかなと思います。 https://github.com/dekokun/isucon6-qualify/blob/dba81a180ca7b722e45727f11278c19587e9d103/webapp/go/isuda.go#L58

rows, err := db.Query(`select id from entry where match(description) against(?);`, keyword)

FULLTEXT インデックス使用のためのALTER文は以下のとおりです。

alter table entry add fulltext( description ) WITH PARSER ngram;

キャッシュの削除は、VarnishのBans という機能を利用しています。VarnishのVCLに以下のように書いておくと、VarnishにINVALIDATEメソッドでHTTPリクエストを送ることで必要なタグをBANすることができます。

https://github.com/dekokun/isucon6-qualify/blob/dba81a180ca7b722e45727f11278c19587e9d103/webapp/config/default.vcl#L32-L33

  if (req.method == "INVALIDATE") {
ban("obj.http.KEYWORD = " + req.http.X-INVALIDATED-KEYWORD);

例えば、以下のようなcurlリクエストを送ることでで、アプリケーションサーバがレスポンスを返す際に Keyword: 1 というHTTPヘッダを付与していたキャッシュが消えることになります。

curl varnishhost -XINVALIDATE --header 'X-INVALIDATED-KEYWORD: 1'

後は、以下のようにデータの更新時に必要なタグを付与してVarnishにリクエストを送るようにアプリケーションを改修すればOKです。現在はキャッシュの破棄が必要なタグの数だけHTTPリクエストを送っていますが、VarnishのVCLを操作して複数のタグを許容するようにすれば1リクエストで済むと思います(未検証)

https://github.com/dekokun/isucon6-qualify/blob/dba81a180ca7b722e45727f11278c19587e9d103/webapp/go/isuda.go#L72-L78

VarnishのESIによるテンプレート分割

ESI とはEdge Side Includesの略で、VarnishでのESIとは、キャッシュサーバがアプリケーションサーバから返されるデータを読んでその中のタグを解釈し、必要に応じて別のデータを取りに行くような機能のことです。これだけでは意味がわからないと思いますので以下でもう少し簡単に説明します。

ESIの簡単な例

今回のISUCON予選の問題を簡略化して説明します。

/ のアプリケーションサーバのレスポンス

(前略)
    <div class="container">
      <p>Hello <span class="isu-account-name">dekokun</span></p>


<esi:include src="/index_keyword?page=1" /> (<-ここに注目!ここでESIを使用してます)

    </div>
(後略)

/index_keyword?page=1アプリケーションサーバのレスポンス

<article>
  <h1><a href="/keyword/%e3%81%a7%e3%81%93%e3%81%8f%e3%82%93">でこくん</a></h1>
  <div><a href="http://13.78.91.40/keyword/%E3%81%A7%E3%81%93%E3%81%8F%E3%82%93">でこくん</a>は、いつも元気に働いている社会人です。
(後略)

/ のVarnishのレスポンス。まずアプリケーションの/を叩き、その後 /index_keyword?page=1 のキャッシュでesi:includeの部分を埋めて返す。これにより、 Hello dekokun の部分は動的に生成しつつ重いキーワードの自動リンク機能はキャッシュを返すことが可能。

(前略)
    <div class="container">
      <p>Hello <span class="isu-account-name">dekokun</span></p>


<article>
  <h1><a href="/keyword/%e3%81%a7%e3%81%93%e3%81%8f%e3%82%93">でこくん</a></h1>
  <div><a href="http://13.78.91.40/keyword/%E3%81%A7%E3%81%93%E3%81%8F%E3%82%93">でこくん</a>は、いつも元気に働いている社会人です。
(中略)

    </div>
(後略)

ESIについて詳しくは以下をご参照下さい。

Content composition with Edge Side Includes — Varnish version 4.0.4 documentation

ESIの設定

VarnishはデフォルトではESIが有効になっていないので、VCLで以下のように有効にする必要があります。

https://github.com/dekokun/isucon6-qualify/blob/dba81a180ca7b722e45727f11278c19587e9d103/webapp/config/default.vcl#L67

set beresp.do_esi = true;

ISUCON予選問題でのESIの実装

上記例に出したようにユーザによって動的に表示が変わる部分と、キャッシュをしたいキーワード部分を別テンプレートに切り出す作業を行います。

基本的にキャッシュしつつ動的な部分は正確にキャッシュしないようにしたところテンプレートを非常に細かく分割する必要が発生し、ESIで呼び出されたHTMLの中から更にESIで別のHTMLが呼び出されるような多段のESIがいたるところに出現し、最高で4段のネストしたESI呼び出しが発生しました。

以下の赤枠で囲った1つ1つが、テンプレートを分割してESIでVarnishから呼び出されている部分になります。つまり、Varnishへの1リクエストが4リクエストに増幅しているわけで、今回のISUCON問題のように、"とてつもなく重い機能(キーワードの自動リンク機能)を徹底的にキャッシュしたい。そのためには同時リクエスト数は増えても構わない" という場合以外はこの方式はむしろ性能が劣化する原因になるので注意です。

f:id:dekokun:20161209114759p:plain

結果

上記の対応を行うことで全てのページにおいて一番重いキーワード生成部分は完全にキャッシュされ、データの更新時には必要なキャッシュだけ破棄されるような環境は整ったのですが、如何せんそもそもキーワードの自動リンク機能部分のキャッシュの生成にかかるコストが高すぎて、"キャッシュに必要な実装以外は出来る限りアプリケーションには手を入れずに" という制約の上ではISUCONのベンチマークをかけても全くスコアが出ませんでした。 ISUCONのベンチマーカーはPOSTリクエストの割合が高く、キャッシュがかなり頻繁に破棄される状態だというのも点数が低い原因になっています。

今後行いたいこと

以下行いたいですね。

  • ISUCONアプリケーションをFastlyで配信する
    • VarnishからFastlyに載せ替える みたいなブログを書きたい
    • 実際は既に配信はできる状態になっているのですが、ここに書くには余白が足りない
  • アプリケーションに手を入れてキーワード生成部分を高速化し、どれくらいの点数が出るのか見てみる
  • 今回はデータの更新で即座にキャッシュを破棄していたため、その次にアクセスするユーザには長時間待たせることになってしまっていたが、、Varnishに古いデータを返させつつアプリケーションサーバにリクエストを送り裏でキャッシュを生成させるような実装にしたい
    • その場合は新しいキャッシュができるまで古いデータが返ることになるのでISUCONのベンチマークツールにはエラーとして認識されそうではある

今回使ったVarnishの各機能に対する感想

キャッシュにタグ付けを行いタグ指定でのPurge

非常に夢がある機能です。これによって動的なアプリケーションでも出来る限りVarnishにキャッシュさせつつ更新は即座に反映することができます。タグ付けを適切に行えば、更新データに関連するキャッシュを全て綺麗に瞬時に消し去ることができます。

ESI

ESIによって実現される、"ページの一部だけキャッシュされて残りはキャッシュされていない"というような状況は、ただでさえ人間の頭に負担になる"キャッシュ"というものが更に複雑なものになってわけがわからなくなるなと強く感じました。基本的には使うべき機能ではないと感じます。開発時にVarnishがないとアプリケーションが動かないという状況にもなり、動作確認が行いづらくそちらでもあまり好ましくないなと感じます。 ESIを使うのと同等のことは、JSでAPIを叩いてDOM書き換えを行うことでできる(ただし、ESIと比較してブラウザからアプリケーションサーバまでのレイテンシは余計にかかりますが…)ので、そちらを採用したほうがアプリケーションを書く側としても一般的で分かりやすく良さそうです。

最後に

ここ1年ほど仕事でVarnishを触ることが多く、VarnishのタグPurge機能やESL機能に触れれば触れるほど"これなら全ての参照リクエストへのレスポンスをキャッシュさせつつリアルタイムなアプリケーションが作れる!そういうコンセプト実装をしたいなぁ"と感じていたところにちょうどまさにそういう構成が力を発揮しそうなアプリケーションがISUCONという形で与えられたため、是非やってみようと思ってやってみました。 実際にやってみたところで、そのような構成が実際に可能なこと、ELSの難解さやタグPurgeの強力さを肌で感じることができ、とても良い経験になったなと思います。

最近はFastly等のキャッシュPurgeが高速なCDNも登場しており、全てをCDNにキャッシュさせるような動的ページも作っていきたいなと夢が広がりますね。

明日のアドベントカレンダーid:Windymelt です!!!