ISUCON5出題を担当したtagomorisです。参加者のみなさん、楽しめましたか?

今回の出題も予選に引き続いて@kamipoさんと一緒に行いました。また各言語実装、ならびにAPIサーバ実装を@hydrakecatさん、@najeiraさん、@makingさん、@taroleoさん、そして本選からあらたに@hokacchaさんにもお手伝いいただきました。イベントがなんとか行えたのはこの方々のおかげです。また本選前の時期にISUCONの準備に集中させてくれた所属先のTreasure Dataの同僚にも感謝しています。

今年は例年よりさらにHTTPリクエストが各サーバ間を頻繁に行き来する問題でしたが、NHNテコラスさんに非常によい環境を用意していただきました。分散ベンチマーク環境も比較的快適な状態で使ってもらえたようで良かったと思います。

このエントリでは以下、今回の本選の問題がどのようなものであったか、何をすれば高スコアを出せるかについて解説をしていきます。 全てのソースコードは以下のリポジトリにおいて公開されています。サーバ環境のプロビジョニングのための一式やデータ生成スクリプトなども入っているため、物理的な構成を除けば本選と同様の環境を作成できるはずです。

https://github.com/isucon/isucon5-final/

今回の出題にはAPI endpointと呼ばれるいくつかのサーバプログラムも関わるため、環境の再現は少し難しいかもしれません。別途Google Compute Engine上で動作するイメージを作成・公開しようかと思っています。少し気長にお待ちください。

本選問題「AirISU」

今回の問題のコンセプトは「間違ったマイクロサービス」でした。ざっくりと機能を説明するとYahoo! PipesやIFTTTに近い、と言えるかもしれません。外部サービスにリクエストを送り、その結果をまとめてユーザに返す、という機能のサービスです。

これまでのISUCONの問題と大きく異なる点として、主催者側が外部にブラックボックスとして(複数の)APIエンドポイントを設け、参加者のチューン対象となるWebアプリケーションはベンチマークツールからのリクエスト(と保存されている設定)に応じてその外部APIにリクエストを送り、その結果をまとめてベンチマークツールへのレスポンスとする、というアプリケーションだったというものです。これまではISUCONのアプリケーションは単体で閉じたものばかりだったため、今回の問題はかなり異なる傾向だったと言えるのではないかと思います。またリクエスト/レスポンスでJSONを多く扱うという点も目新しかったかもしれません。

環境としても今回はRDBMSとしてPostgreSQLを用い、OSは予選から引き続きUbuntuでしたがバージョンは14.04でした。 またベンチマークツールは予選で書いたもの(Java8)を手直しして使用したものなので、今回は詳しくは解説しません。これはそのうち単体のライブラリとして切り出して公開しようかと思っています。

アプリケーション並列度

今回のアプリケーションは初期状態だと、とにかく外部APIへのリクエストを送ってからレスポンスを待たされるという特性があります。後述の処理によりAPIへのリクエスト数自体を減らすことはできるものの、どうしてもゼロにはできません。ボトルネックとしてはCPUではなく、HTTPのI/O待ちとなります。こういった特性を見ると、アプリケーションはまずプロセス/スレッドの並列度を可能な限り上げてしまうのが高スコアへの第一歩だと言えるでしょう。これを見越して、ベンチマークツールも50スレッド並行でユーザ環境にアクセスをしにいくという設定でした。

RubyやPerlだと初期状態でのスコアは1000点前後になっていましたが、Golangなどの実装では初期状態では10000点が出るというのは、このあたりの並列性の向き不向きが言語によって如実に出たところかと思います。Ruby/Perlなどでもプロセス数を増やすことで比較的近いスコアに簡単に到達するため、出題側では特に問題視しませんでした。(初期状態で合わせておくことも考えましたが、いろいろ設定に不自然な点が出てしまうため、それも行いませんでした。)

各APIへの並列リクエスト

主に問題となる
/data
へのリクエストがひとつあると、アプリケーションは(ユーザによりますが)4つから7つのHTTPリクエストをAPIエンドポイントに発行しなければならないというのが今回の特徴のひとつです。初期実装ではこれらのリクエストはすべて直列で、つまりひとつずつ順番にリクエストを送ってはレスポンスを待っていました。各APIエンドポイントはそれなりにレスポンスが遅いため(これはsleepを入れて調整していたからですが)、APIエンドポイントへの通信をすべて並列に行えば、一番遅いAPIのレスポンスが返ってきたところで
/data
のレスポンスを返せるようになります。

これも正直に言って、言語によって向き不向きが大きく出るところです。出題者の想定ではこの特性から、今回はGolangおよびNode.jsが強いのではないかと想定していました。実際にはあまり単純に並列化してもエラーが出る罠(次項)が用意してあり、そこをクリアする必要があったことも影響しているかもしれません。

429 Too Many Requests + HTTP/2

外部APIは7種類用意されていましたが、これらは実際には4つのサーバプログラムで提供されており、2種類のAPIを提供するものが3つ存在しました。そしてそのうちのひとつはデフォルトで https を用いるようになっており、このサーバに HTTP/1.1 であるユーザに関する(リクエスト内のtokenが同じ)リクエストふたつを並行して送ると、片方で 429 Too Many Requests を返す(これにより
/data
がベンチマーカーのチェックを通らなくなる)という挙動をするよう設計されていました。 この挙動を見た参加者の側では、tokenが同じリクエストについては直列化する、あるいはAPIエンドポイント単位で直列化するなどの戦略を採ったところが多かったようです。

しかしこのAPIは実は HTTP/1.1 と HTTP/2 の両方に応答するものになっていました。このサーバは想定として以下のようなものを考えていました。

  • 1ユーザあたり1コネクションのみしか受け付けず、同時に2コネクション目がきたら 429 Too Many Requests を返す
  • HTTP/2 の場合は1コネクションで複数リクエストを並行して発行できる

  • わざわざhttpsでというのがヒントのつもりでしたが、気付いたチームもあったようでほっとしています。

    実際にはコネクション単位ではなくリクエスト単位で制御しているため少し無理のある設定なのですが、HTTP/2のプロトコルとしての特性を考えると、そこまでおかしくもないだろうと思いそのままにしました。実装は Node.js の http2 モジュールを使い、curl + nghttp2 では正常にリクエストが通ることを確認していましたが、参加者チームがいくつか試したライブラリではうまく通信ができなかったとのことで、まだまだHTTP/2まわりの実装はこなれていないというのが実情かもしれません。実装に h2o + mruby などを用いることも考えたのですが、今回は時間的な制約から見送ってしまっていました。

    APIの特徴にあわせたキャッシュとLast-Modified/If-Modified-Since

    今回APIとして提供された機能はそれぞれいくつか特徴があり、おおむね以下のようになっています。

  • ken, ken2: 業界で有名な KEN_ALL.CSV を元データに郵便番号から引いた住所のリストを返す
  • surname, givenname: 特定の名字・名前データベースを元に、クエリ文字列が前方一致するデータのリストを返す
  • tenki: 現在の天気、っぽい文字列を適当に返す
  • perfectsec, perfectsec_attacked: tokenに対して何らかの key, onetime_token のリストや attacked token list を返す

  • データを見ていくと ken/ken2 や surname/givenname についてはそうそう変わりようがないことはわかるかと思います。実際これらのデータは全く変わらず、一度引いたデータは時間無制限でキャッシュしてもよいものになっていました。またこれらのAPIは全ユーザのリクエストが引くようになっていたため、ここをまずキャッシュすると大きくスコアが上がったものと思います。(とはいえ、過去のキャッシュに頼ると最後の計測走行で性能は出なかったでしょう。最終的な計測走行では作業時には決して流れないよう分けられていたデータセットを用いてベンチマークが行われたためです。)

    tenkiは3秒毎にレスポンスの内容が変わるAPIでした。このため普通には毎回問合せる必要がありますが、このとき前回問合せのレスポンスヘッダにあった Last-Modified を用いて If-Modified-Since リクエストヘッダをつけて問い合わせることで 304 Not Modified が即座に返ってくるという特性がありました。

    perfectsec は前述の 429 Too Many Requests を返すAPIでしたが、データの内容そのものは一見意味のないもので、また実際、常に変化するものでした。いっぽう perfectsec attacked は一見意味のないデータを返すのは同じですがレスポンスヘッダに Last-Modified がついており、これも If-Modified-Since をつければ高速に 304 Not Modified を返すという特性のものでした。これはキャッシュが効くものの有効期間はランダムとなっており、即座に変わってしまうためこれも毎回リクエストを送って確認する必要があるはずのものでした……が、後になって最短でも3秒(3100ms)経過しないと変化しないというバグが混入していたことを発見しました。

    出題意図としては各APIのデータ特性やHTTPリクエスト/レスポンスヘッダなどの詳細からAPI単位でのキャッシュ制御をぜひ頑張ってほしかったのですが、上述バグの影響もあってか一律長めにキャッシュする(perfectsec以外は)、という戦略が優勝チームにおいて多大な効果を発揮したようです。もうすこしキャッシュ有効期間を精密にコントロールしたほうが、出題意図に正確に沿った実装になったかもしれません。

    Accept-Encoding: gzip

    /data
    のレスポンスがこなれてくると比較的ほかのリクエストの重要度が増してきます。今回のベンチマークはCSSやJavaScriptファイルにもそれなりにアクセスしてくるものだったので、ここを効率化しておくのはある程度の効果があったはずです。特に今回は比較的サイズの大きなファイルがいくつか含まれていました。

    ベンチマーカーは今回
    Accept-Encoding: gzip
    に対応し、それらのコンテンツの一致チェックはベンチマーカー側でgzip展開した後のデータのchecksumを取って行っていました。このため、あらかじめgzip圧縮したデータをnginxなどから配信することで大きなトラフィックと負荷の削減になったのではないかと思います。実際のWebサービスでもJavaScript/CSSの転送量が意外に馬鹿にならないので、覚えておくと良いと思います。

    サーバ再起動

    ISUCONは毎回決勝のスコアについては、作業時間後にサーバ再起動を行ってからの一発計測で決定しています。これはソフトウェアやシステムとしての安定性、サーバ設定が確実にできているか、過去のベンチマーク走行において作られた意図しないキャッシュなどにスコアが依存していないかの確認など、さまざまな意味を含んでいます。

    今回の測定ではこの最後のベンチマーク走行で fail してしまったチームが非常に多く、これは少し残念なところでした。学生賞の対象チームは全チーム fail してしまったため該当なしとなったほどです。これに較べて上位のチームに関してはほぼこのような fail がなかったため、さすがという印象でした。

    再起動チェックは本当に重要です。来年は気をつけましょう。

    総評

    主な技術的なポイントとしては上述のものを盛り込みました。他にも細かい点はいくつかあり、そこで fail してしまった上位チームもありましたが、スコアを出すという部分ではこれらのポイントが重要だったのではないかと思います。

    これらを全て実現できたチームは存在しませんし、全てに気付けたチームもなかったと思います。それは出題者の誘導不足というものもあったかもしれませんが、上位スコアを出したチームの間でもそれぞれ戦略が異なっていたため、得意不得意によって着目したところに差があったとも言えるでしょう。(最終的にfailしたとはいえ)チーム.datは並列姓を重視して高いスコアを記録していたようです。個人的にはそれを意図して問題を作っていたため、懇親会で話を聞いたときに嬉しく思ったのを覚えています。

    反省点: ベンチマークのバグ

    今回、ベンチマーカのシナリオコードにはいくつかのバグがありました。

    参加者から見て明確だったのは、ベンチマークツールは違反を検出している(それが走行結果詳細に表示される)のに、結果としては FAIL にならず SUCCESS としてしまう、というものです。これは動的生成されるJavaScriptの内容チェックと、APIが返すデータの有効期限チェックの2点に存在し、それぞれ状況が確認されたあと、参加者へのアナウンスとともに作業時間中に修正されました(FAILするようになりました)。

    もう一点が1分の負荷走行中に並行して走っていた動作チェッカの挙動です。本来の意図では、テスト用データセットからチェック対象をランダムに選択して一定のチェック処理を走行する、完了したらチェック対象の選択からやりなおし、それを時間いっぱい繰り返す、という想定でした。しかしチェック処理の繰り返しを記述したところでチェック対象の選択をやりなおさないバグを作り込んでしまい、これにより、ベンチマーク実行時に grade が "micro" もしくは "small" のユーザが選択されてしまうと、tenki APIやperfectsec APIのチェックが事実上働かなくなってしまっていました。

    このバグが発見されたのは午後のかなり遅い時刻であり、また発見した段階から競技終了まで、
    /data
    のチェックばかり繰り返しCSS/JSのチェックが一度しか行われないという、影響度としては低いバグだと思い込んでいました。このため、このバグについては修正を行わず競技終了を迎えました。しかし実際には長いキャッシュ保持期間を設定してしまっていても偶然チェックを通過することがあり、しかしベンチマーク実行回数が多いほどチェックにひっかかる試行を発見してしまうという影響が出ていたはずで、特にキャッシュを長く保持しようと試行錯誤していた場合(そもそもその方針が誤りになるような問題設定にしたかったのですが)、経過および結果に少なからぬ影響を与えていた可能性が高いです。その戦略は実質的に自分の想定になかったため、後日になるまで気付けませんでした。

    反省点としては2点です。ひとつは、動作チェッカは(初期チェックでなく負荷走行中であっても)固定か、あるいはそれに近いデータをチェックに用い、偶然の要素を入れないこと。もうひとつは挙動の異なるユーザデータがあるのであれば、その全パターンについて漏れなく挙動チェックを繰り返すことです。この重要な2点の実装ができていませんでした。

    最終的な結果に重大な影響を与えたバグであったと思います。この場を借りて出場者の方にお詫びいたします。

    (tagomoris)