👻

ISUCON 5 決勝の天気APIの解説

2020/10/01に公開

ISUCON

tech

ISUCON 5が終わりました。

出題担当のtagomorisさん、kamipoさん、お疲れ様でした。非常に大変だったと思いますが、お手伝いさせてもらって刺激を受けましたし楽しかったし、良い経験になりました。ありがとうございます。

941さん、各言語の担当者の方々、参加者のみなさんも、お疲れ様でした。

来年もお手伝いしたいし、いや自分自身も参加もしたいし、迷うところです。

さて、ISUCON 5 決勝での天気予報APIを実装しましたので、APIの挙動や意図などを記しておきます（全体の講評は ISUCON5 本選問題の公開と講評をご覧ください）。

zipcode

クエリパラメータとして zipcode を渡していましたが、APIはこれを見ていません。ところがアプリ側はzipcodeを渡すようになっています。

アプリ側の実装の意図については把握していませんが、おそらくキャッシュをしにくくするための罠のようなものだったのかもしれません。

応答

APIは以下のようなレスポンスを返します。

HTTP/1.1 200 OK
Content-Length: 68
Content-Type: application/json; charset=utf-8
Date: Mon, 02 Nov 2015 06:25:35 GMT
Last-Modified: Mon, 02 Nov 2015 15:25:33 JST

{
    "date": "Mon, 02 Nov 2015 15:25:33 JST",
    "yoho": "晴れのち雨"
}

普通のJSON APIです。天気の情報が返ってくることが分かります。

速度

APIは応答に500msほど時間がかかります。

遅いAPIになるように内部で待ち処理を入れています。遅いAPIをどう扱うか(他のAPIと並列にするなど)も問題のポイントであるため、このようになっています。

予測不能

何度かAPIを呼び出すと分かりますが、yoho の内容は刻一刻と変化し、規則性がありません。

予測できる内容だと、事前に結果リストを作成して応答するだけになってしまい、問題の意図から外れてしまいます。そのため予測できないようにしました。

選択肢の多さ

天気は「晴れ」「曇り」「雨」のような単純なものだけではなく「大雪時々雨か雷雨」のようなものまで、合計で408種類ありました。

選択肢が少ないと、実際にAPI呼び出しをせずにランダムに応答しても正解してしまう確率がそれなりにあります。

例えばベンチマーカーの実装が「アプリが応答する天気が間違っていた場合にもFailさせずにスコア加算しないだけ」だった場合に、ランダム応答が有効な戦術になり得るので、それを防ぐために選択肢を多めにしました。

キャッシュ

このAPIでも、キャッシュは非常に有効な作戦です。ただしいくつか注意すべき点があって、単純にキャッシュするとうまくいかないようになっています。

キャッシュ可能時間

最初のレスポンスをキャッシュするだけで完成！では面白くないので、キャッシュ可能な時間は短くなるようにしました。

APIを何度か呼び出すと分かりますが、時間経過によってレスポンスの内容が変化します。このためレスポンスは長時間はキャッシュできず、定期的に新しい内容を取得する必要が生じます。

APIのレスポンス内容が変わる周期が約3秒だというのは、レスポンス内の date の変化を見ていると分かります。連続でAPIを呼び出してレスポンスを見ていると、しばらく同じ内容だったのが違う内容に変わり、そのときに date が3秒進んでいる……ということが繰り返し確認できます。

現実にはこんなに頻繁に天気予報は変わらないのですが、課題の都合上このようになっています。それとも天気とは何かの比喩なのでしょうか……。

キャッシュのしかた

APIのレスポンスを、レスポンス取得時点から3秒でキャッシュしてはいけません。JSON内の date かヘッダーの Last-Modified を起点にして3秒にする必要があります。

このAPIは「内容が3秒周期で更新されるようなので date から約3秒間はキャッシュできそうだ」という推測でキャッシュするのであって、Cache-Control: max-age=3 のような明示的に許可されたキャッシュではないからです。

Thundering Herd

キャッシュを単純な実装にしていると、キャッシュが切れたタイミングで複数のクライアントがAPIを呼び出すことになります。APIが遅いので、APIを呼びだそうとした複数のクライアントが長く待たされることになります。

キャッシュ時間が短いことで、この問題がベンチマーク中に何度も発生するようになっています。

キャッシュの有効期限切れがアプリ実装によるものではなく、API側のレスポンスを更新する周期に依っているのが対策の難しいところです。アプリ側のキャッシュまわりの処理で一部のリクエストだけで早めにキャッシュMissさせて、新しいキャッシュが作られるようにする……というような典型的な Thundering Herd 対策ができないためです（早めにキャッシュ更新しようとしても、API側の内容が新しくなっていない）。

ただ実際にはベンチマーカーはちょっとだけ古い天気情報は許容するようになっていたので、キャッシュ時間を3.1秒くらいにしていたら、わりと高スコアを狙えたかもしれません。

他には例えば、APIをひたすら呼び出してキャッシュを新しくしていくワーカーを別で作ったりすると、スコアアップが狙えそうです。

参考: キャッシュシステムの Thundering Herd 問題

Last-Modified

キャッシュは非常に有効な作戦だと思われますが、別の方法として Last-Modified と If-Modified-Since を用意していました。HTTP仕様に関する知識があるとスコアアップできる、という意図です。

curlなどでヘッダーみていれば Last-Modified の存在に気づきます。ヘッダーだけでなくボディのJSON内の date にも Last-Modified と同じ内容が入っています。そこから「もしかして天気の情報が更新された時刻なのかな？」「更新時刻といえば Last-Modified が HTTP にはある」という連想でヘッダーを見てみれば、Last-Modified を発見できます。

その先は Last-Modified と If-Modified-Since を知っているかどうかです。

さて If-Modified-Since をリクエストに含めて送り、天気の情報が更新されていない間は、以下のようなレスポンスが返ります。

HTTP/1.1 304 Not Modified
Date: Tue, Mon, 02 Nov 2015 06:25:35 GMT

このときAPIは、500msを待たずに即座にレスポンスを返します。

304の場合のAPIは高速に応答しますので、仮にキャッシュ実装をしなくとも、If-Modified-Since を使えばかなりスコアアップできます。約3秒間は304になるので、API呼び出しの多くがとても高速化されるためです。

もちろんキャッシュとの組み合わせも有効でしょう。キャッシュの有効期限が切れたらAPIを呼び出すことになりますが、ここで If-Modified-Since を使えば、レスポンスが更新されていない場合は高速に応答されます。このため Thundering Herd の緩和にもなると思います。

感想・その他

ISUCONでは、ややキャッシュが万能すぎる側面もあるので、内容が更新される周期は3秒固定ではなく、ある程度のバラつきがあるようにして、キャッシュしにくくしたほうがよかったかもしれません。

今回はやっていませんがレスポンスに Cache-Control: no-cache を入れておいて、「キャッシュはダメだって言ってるだろ！」ということで後半に周期を変えるような罠も考えられますし、HTTPヘッダーはちゃんと見ておくとよいでしょう。

この記事はQiitaの記事をエクスポートしたものです