本選の問題作成を担当した面白法人カヤックの @ken39arg です。
本選に参加した皆様お疲れ様でした。
優勝した「最大の敵は時差」チームの皆様おめでとうございます。
また、問題の作成を通じて私自身も成長することができました。 協力してくださった多くの皆様には大変感謝をしております。ありがとうございました！
https://github.com/isucon/isucon8-final
今回、惜しくも本選に参加することのできなかった皆様にもぜひ挑戦していただきたいと思っております。お時間のあるときに遊んでみてください！
倒しがいがあり楽しめる問題になったのではないかと自負しております。
ページはSPAとなっていて、主な機能は下記で一見とてもシンプルです。
ユーザー登録とログイン 椅子の注文と取り消し ローソク足チャート
このアプリケーションに、 SNS「いすばた」へのシェア機能 を追加しようとしたところ、想定を超えるユーザー流入があったため、急遽サービスメンテナンスに突入した。 しかし、プレスリリースを出していたため10月20日18時までに公開しなければならない！
というのがお題となっておりました。
また、今回の問題はこれまでのようなレギュレーションに加えて、それなりにきちんとした仕様書が用意されていました。
8年前に始まったISUCONですが、当時と比べて技術はだいぶ進化し、現在では単純にHTMLを返すだけというwebアプリケーションは減ってきました。 かわりに多くのアプリケーションが、クロスプラットフォームで動作するように作られるようになり、サーバーサイドアプリケーションはjsonやgRPCなどのプログラムが読みやすい情報を返し、様々なクライアントアプリがそれを利用するという形に変わってきました。
そのため、ほとんどの場合は外部公開しないものであってもAPI定義書くらいは用意しているのが一般的になってきたのでは無いでしょうか？
それは3つの外部サービスと密な関係があり、それらのサービスはAPIドキュメントは公開されているが、実装の中身は全くわからないというものです。
ネタバラシを含めて説明します。
APIドキュメントとクライアントライブラリが存在する あらゆるアクションのログを10秒以内に送らなければならない 並列性能が低くrate limitが存在している(10並列, 20req/sec) 仕様上
APIドキュメントとクライアントライブラリが存在する 並列性能は高いが、決済確定処理に時間がかかる
初期状態ではシェア機能は無効化されている 驚異的な拡散力で1度シェアをすれば必ず3人ユーザーが増える 取引が成立するときにボタンが表示されていたら注文に対して1回必ずシェアをする
初期状態は、これらのサービスを素直に利用しているだけの実装となっているため、 サービスの特性を適切に分析した上で、まとめるところはまとめたり、遅延させるところは遅延させるなどをする必要がありました。
正直、業務経験がものをいうので学生には難しい問題になってしまうと思ったのですが、 「ISUCONの決勝は好きなように問題を出せば良い」という神の声が聞こえたので「すまんが学生の優勝はまだ早い」という気持ちで罠を仕掛けていきました。
また、上記の特徴は冷静な目があればすべて把握することができるようになっておりました。
ログ分析サービスに関しては、ドキュメントにすべてが書いてあるうえに、仮にドキュメントを読まなかったとしても「429 Rate Limit Exceeded」が多発するようになるため具体的な制限を知るために仕様に立ち返る機会があったはずです。
いすこん銀行に関しては、ポイントとなる処理時間に関する情報はドキュメントにはありませんでしたが、プロファイリングツールなどで、APIそのものや関数の処理時間を計測すれば、API毎に傾向があることはつかめたはずです。
シェア機能に関しては、それ自体の説明はあまりありませんでしたが、TODOコメントや、 競技開始前のプレゼン、マニュアルなどで何度もシェア機能に触れていたため、ポイントとなることはわかるだろうという気持ちでいました。
このPARTITIONですが、
また、PARTITIONによってPRIMARY KEY がid単独ではなくidとcreated_atの複合キーになってしまうなどのデメリットがあるため、PARTITIONを剥がすとMySQLの負荷を下げられたはずです。
しかし、PARTITIONを剥がすという経験はおそらく業務においてもほぼしたことが無いと思いますので、どうやって剥がすかをすぐに思いつくかが一つのポイントだったと思います。結論から言うとテーブルを作り直してコピーするのが最も簡単な方法でした。
※ ちなみに万が一
※ 実際のサービスでは、データが数億件になるような場合や、定期的なデータの消込みのために1日単位で利用するといったケースが多いかと思います。
最新のtradeを求めるために下記のクエリを実行していました。
実際に「ORMで自動的に
この問題は、リリース直後やテストなどでデータ量の少ないうちは全く問題にならないため非常に気づきにくいのですが、データ量が増えると猛威を振るうというもので、問題を作る際に是非入れたいと思っていた要素でした。
ちなみに、この実装が言語毎の初期スコアの差を生み出しており、 特にGolangにおいては1レコードのみしかfetchしないためアプリケーションのメモリを全く消費しないという問題があったため、普通は絶対にしないありえない実装をしてしまいました。
しかし、よく見ると「自分の注文」であるため、userはすべて同じ(=自分)で、tradeのみ対策すればよいというものでした。 また GET /info の方は一回あたりせいぜい数件しか返ってこないので無視しても良かったかもしれません
実際に遅いのは間違いないのですが、クリティカルな問題かというと微妙な遅さで「さてどうしよう？」と頭を悩ませるものとなっておりました。 しかし、仕様には「infoに返すデータは原則1秒以内に反映する必要がある」という記載があり、裏を返すと「infoに返すデータは原則1秒間キャッシュしても良い」ということになるため、 このクエリにとらわれずにキャッシュしてしまえば、1秒に1回ほどしか実行されないものとなるためクエリ自体の対策は不要だったかもしれません。
また「パスワードはbcryptでハッシュ化しなければならない」と仕様に明記されていたため対策できないような錯覚をさせていましたが、コスト(ストレッチング回数)に関しては何も言及していないためコストを最小値にすると大幅にCPUが改善するものでした。
実際に既存の11,763件のユーザーデータのパスワードはすべてbcryptでハッシュ化されてはいたもののコストはバラバラで半分はcost=4になっていました。
また、ほとんどのベンチマークシナリオは1回ログインしたらそのままなので、序盤はスコアに大きな影響を与えません。 しかし、実は1/10のユーザーが同じbank_idに対して総当たりログインを仕掛けてくるアタッカーに設定されていたため、シェア機能の有効化によって同時接続ユーザーが増えてくるとかなり効いてくるというものでした。
気づきはしても、対応するにはそこそこの時間がかかると思うので、どのタイミングで手を出すか迷ったかとおもいます。
この設定を単純にキャッシュしようとすると複数台構成にするときに工夫が必要となります。また、後述する取引処理のループを作ると、キャッシュ更新が思ったより難しいという、意外と複雑なマスターデータ問題となっておりました。
これに関しては、わかりやすかったという意見と、量に圧倒されたという意見に分かれたように感じましたが、今どき1ファイルのアプリケーションなんてほぼ無いだろう？という気持ちと、後述の大ボスに挑むための大ヒントとするためにこの構成にしておりました。
しかし、13時の時点でほとんどのチームが一度も有効化したことがなかったため、運営部屋では「シェア機能に関してだけネタバラシをしにいくか」何度も議論をしていました。 最終的にはほとんどのチームが有効化していたので安心しましたが、なかなか使われなかったのは問題としてのアピールが少し足りなかったのかもしれないと感じており課題だと思っています。
さらに、ユーザー数をカウントして、アプリケーションが処理できるギリギリで無効化するという作戦を取れば、ベンチマーク開始早々に一気にユーザーを増やして、そこから増やさないという方法を取ることもできました。 自然増加が途中からめっきり増えなくなっていたのはそういうことを意識してのことでした。
特に、この問題は各言語毎にスコア上昇の特性に差はありますが、後述の特別賞さえ超えてしまえばどんな施策をしても、 その施策+シェア率の調整で面白いほどスコアが上がっていく気持ちいい問題になっていたので、調整可能であるというヒントを出しても良かったかもしれません。
ご覧の通り、この問題はたったの3人で8時間という限られた時間の中で取り組むには非常にボリュームが大きくなっておりました。 また、すべての言語で同じ施策をした場合に、同じようにスコアを上げていったり、言語による有利や不利が出ないように問題を作るということは大変困難で決勝ということもあり半分くらいは諦めてしまいました。
さらに、経験値の問題で最終的には学生の方が不利になると思っていたこともあり、特別賞に関しては、学生や社会人、言語の選択などにとらわれない、どのチームも平等に狙えるものにしていこうという思いで検討し、 その結果、「基本をきっちり押さえれば十分にねらえること」、「ログ分析APIへの非同期送信を完成させること」の2つを条件とすることにしました。
そしてチューニングを繰り返した結果、下記をクリアすればどの言語でも達成可能であるようにしました。
LIMIT 1 N+1 indexチューニング、及びPARTITION剥がし 静的ファイル配信 ログ分析APIで シェア機能を10%以上有効化すること 更に少なくとも以下の理由から下記2つだけは必ずクリアする必要がありました。
LIMIT 1
仮にgoを選択しQueryRowを選び1行しかフェッチしないようにしていたとしても、MySQLの負荷がボトルネックとなり超えられない壁となっておりました。
ログ分析APIで
上述の通り 20req/sec のratelimitがかかっているため、ログ送信を行うGET以外のリクエストを合計20req/secしか捌くことができません。 これを超えると「ログが欠損しています」というエラーが出て事後テストをfailするようになるため、この問題を解決しない限り絶対に15000には届きませんでした。
もちろん、初手で複数サーバー化をしたりbcryptを先に行うなど対策の順番は様々ですので、必ずしもこの通りではないかもしれませんが、似たり寄ったりの手数でスコア15000は到達可能だったはずです。
ただし、シェア機能を完全にfalseにしていた場合は、CPUが余っているのにユーザーが来ないという状況に陥って手詰まりになってしまった可能性はありました。
このことに関しては、できるだけスコアにガチャ要素や意図しない裏技をなくした上で、ユーザー数を自由にコントロールさせたいというシェア機能のコンセプトがありましたのでご理解いただければと思います。
銀行APIに関しては上述しておりますが、RunTradeの特徴をいくつか下記に上げます。
売り注文と買い注文を 1:N にマッチングし取引を成立させる関数である 無限再起している(例: go, python) 処理がとにかく複雑な気がする 関数分割しているため、銀行APIの呼び出しが散らかっている 初期状態では 詳しくは仕様を!
この処理の課題deadlockが なかなか終わらないため同時に 取引が成立しないと、SNSシェアでユーザーが増えない
一言で言うと「deadlockをなんとかして早くしろ」ということなのですが、一度に2つのことを解決しようとするとなかなかうまくいきません。
そこで順を追って対策をしていくとうまくいきスコアはみるみる上がっていきます。
実際私自身、今回の問題のドメイン知識が皆無だったため、適当に仕様を決めたので、取引処理に関してだけでもより良い方法がいくつもあったはずです。
事前調整ではスコア100,000 以上は狙える問題でしたので、そのあたりに関しては、出題チームで100,000を超えた @fujiwara やpython移植中に効率的なrunTradeに気がついた @methane さんなどがどこかで語ってくれるかもしれません。
また、私自身もまだスコア50,000くらいまでしか出せていませんので、これから延長戦の期間でさらなる高みに挑戦して、もしいいスコアが出せたらどこかで紹介しようと思っています。
また、goのみが
しかし、これらはdeadlockをなくしたり外部APIをうまく逃がしたりするということを解決してしまえば他の言語も追いつけた差です。
逆にgoの場合はこのスコアからsend_bulkやshareに対応しない限りは何をしてもスコアが伸びないという状況になってしまい精神的に辛く、一方で、他の言語はどんどん伸びていったと思うので、その分もしかしたらgo以外の方が面白かったという可能性もあるかと思います。
この件に関してこちらからは以上です。
想定していた1台での最大スコアが20000弱でしたので、この構成かつrunTrade未着手でここまでいくのか！？と非常に驚きましたが、GET /info でのキャッシュと
複数台構成にしたらもっと伸びたと思います(例えばinfoとsigninなどオンメモリ専用機と注文処理専用機など役割を変える)。しかし、複数台構成を不具合なく構成するのは困難なものになっていたと思いますので、そのやらなかった判断も素晴らしかったのではないでしょうか？
正直想定していたものとはだいぶ違いましたがこれがISUCONの面白さでただただ見事だったと言わざるを得ません。
一方、競技時間中に最大スコアを記録し、惜しくも2位となった「takedashi」は上記で言うところの完全クリアまでたどり着いているようでした。
しかし、再起動試験においてエラーが多発し、1度目はtimeout多発によるfail、2度目はstatus codeが400で返ってくるという事態が発生し減点により結果を伸ばすことができませんでした。(htmlが返ってきていたのでアプリケーションの問題ではなさそうということしか原因はわかりませんでした。)
rebootによる再起動試験をしていたら、もしかしたら競技時間中に気づくことができたかもしれませんが、気づいたとしても対策できるような問題でも無い気がしますので、これもまたISUCONの面白さではないでしょうか？
そのほかのチームに関しては、シェアの有効化をできずに負荷を上げきれなかったチームや、send_bulkに気づけなかったチームなど、特別賞に至るまでの壁を超えるのに苦戦したチームを多数見受けられました。
何はともあれ、みなさまお疲れ様でした。
これも大会の主催と運営をしてくださっている941さんを始めとしたLINEの皆様のおかげです。(合宿や予選で集まるの楽しかった〜！)
また、大会を通じてスムーズにベンチマークできるサーバー環境を用意してくださったGMO ConoHaの皆様には、大会での完璧な環境だけでなく、出題のために何台ものサーバーをかなりの期間自由に使わせていただきました。感謝してもしつくせません。
さらに、ダメ元でお願いしたところ本選でも10/29まで1週間の延長戦を用意してくださりました。(みなさん！！！ 1チーム1物理ですよ！)
本当にありがとうございます。
問題の作成にあたり、予選でDeNAチームの活躍を目の当たりにして私達の力の入り具合も大きく変わりました。
正直、予選終了時には問題は画面以外9割型できていたのですが、もっと面白くするために大幅に作り変えることになりました。 また、予選で使った素晴らしいポータルが決勝でも簡単に使えるものであったため、ポータル作成の時間をすべて問題のブラッシュアップに当てることができました。
事前解答には平日であったにも関わらず、下記4チームの皆様にご協力をいただきました。
ガチムチレンジャー 白金動物園 Oops 流れ弾
特に白金動物園には7時間で全クリされ、ガチムチレンジャーにはrunTrade直列化なしで想定以上にスコアを伸ばされるという結果が、我々を混乱に陥れ、PARTITIONを追加するなど初期データの作りに大改革をもたらしました。
おかげさまで事前解答時よりもだいぶ面白くなったのではないかと思っております。
私が作ったgoによる初期実装を各言語への移植する作業は、下記のオールスターメンバーに対応していただきました。
python = methaneさん ruby = sorahさん perl = mackeeさん php = mix3さん
また、ログをポータルでリアルタイムに見たいんですよねーと言ったら、sugyanさんからpull-requestがやってきたときはとても感激いたしました。
そして、社内のチャンネルに突然投げたSOSに即反応して、ISUCOINの画面を作ってくれた mp3さん本当にありがとうございました。
なにより、問題を考え、ポータル、プロビジョニング、ブラックボックスAPIを担当し、そして、私がベンチやアプリを作り直す度に何度も解き直してくれた fujiwaraさんには本当に感謝しております。 おそらく私と合わせて2人で軽く300回はベンチを回したと思いますw
皆様本当にありがとうございました。
以上、カヤックから fujiwara と ken39arg がお送りいたしました。
来年はカヤックに5回目の優勝を持ち帰れるように参加者として優勝を目指します!
カヤックでは一緒に優勝してくれるメンバーをいつでも募集しております!!
重ね重ねありがとうございました。
本選に参加した皆様お疲れ様でした。
優勝した「最大の敵は時差」チームの皆様おめでとうございます。
また、問題の作成を通じて私自身も成長することができました。 協力してくださった多くの皆様には大変感謝をしております。ありがとうございました！
本選問題の公開
Twitterでアナウンスされているとおり、GitHubで問題の公開をしております。https://github.com/isucon/isucon8-final
今回、惜しくも本選に参加することのできなかった皆様にもぜひ挑戦していただきたいと思っております。お時間のあるときに遊んでみてください！
倒しがいがあり楽しめる問題になったのではないかと自負しております。
課題アプリケーション
今回の課題は仮想椅子取引所「ISUCOIN」というアプリケーションです。
ページはSPAとなっていて、主な機能は下記で一見とてもシンプルです。
このアプリケーションに、 SNS「いすばた」へのシェア機能 を追加しようとしたところ、想定を超えるユーザー流入があったため、急遽サービスメンテナンスに突入した。 しかし、プレスリリースを出していたため10月20日18時までに公開しなければならない！
というのがお題となっておりました。
また、今回の問題はこれまでのようなレギュレーションに加えて、それなりにきちんとした仕様書が用意されていました。
8年前に始まったISUCONですが、当時と比べて技術はだいぶ進化し、現在では単純にHTMLを返すだけというwebアプリケーションは減ってきました。 かわりに多くのアプリケーションが、クロスプラットフォームで動作するように作られるようになり、サーバーサイドアプリケーションはjsonやgRPCなどのプログラムが読みやすい情報を返し、様々なクライアントアプリがそれを利用するという形に変わってきました。
そのため、ほとんどの場合は外部公開しないものであってもAPI定義書くらいは用意しているのが一般的になってきたのでは無いでしょうか？
アプリケーションに潜む大きな特徴
さて、画面からは分かりづらいですが、このアプリケーションには大きな特徴があります。それは3つの外部サービスと密な関係があり、それらのサービスはAPIドキュメントは公開されているが、実装の中身は全くわからないというものです。
ネタバラシを含めて説明します。
1. ログ分析サービスAPI
POST /send_bulkという一括送信APIがあるが、提供されているライブラリには実装されていない
2. いすこん銀行API
POST /check予約済みを含まない残高確認ができる (50ms〜)
POST /reserve金額を指定して決済予約を行う (70ms〜)
POST /cancel reserveした予約を取り消す(80ms〜)
POST /commit reserveした予約を決定する (300ms~)
3. SNS いすばたシェア
初期状態は、これらのサービスを素直に利用しているだけの実装となっているため、 サービスの特性を適切に分析した上で、まとめるところはまとめたり、遅延させるところは遅延させるなどをする必要がありました。
正直、業務経験がものをいうので学生には難しい問題になってしまうと思ったのですが、 「ISUCONの決勝は好きなように問題を出せば良い」という神の声が聞こえたので「すまんが学生の優勝はまだ早い」という気持ちで罠を仕掛けていきました。
また、上記の特徴は冷静な目があればすべて把握することができるようになっておりました。
ログ分析サービスに関しては、ドキュメントにすべてが書いてあるうえに、仮にドキュメントを読まなかったとしても「429 Rate Limit Exceeded」が多発するようになるため具体的な制限を知るために仕様に立ち返る機会があったはずです。
いすこん銀行に関しては、ポイントとなる処理時間に関する情報はドキュメントにはありませんでしたが、プロファイリングツールなどで、APIそのものや関数の処理時間を計測すれば、API毎に傾向があることはつかめたはずです。
シェア機能に関しては、それ自体の説明はあまりありませんでしたが、TODOコメントや、 競技開始前のプレゼン、マニュアルなどで何度もシェア機能に触れていたため、ポイントとなることはわかるだろうという気持ちでいました。
初期データと初期スコア
初期データは ordersに588,980件、tradeに235,919件、userに11,763件のデータが入っており、ordersとtradeは1時間毎にcreated_atによるRANGE PARTITIONを切っているという状態でした。このPARTITIONですが、
DROP PARTITIONも
TRUNCATE PARTITIONも利用していないため、競技中には不要なものでした。
また、PARTITIONによってPRIMARY KEY がid単独ではなくidとcreated_atの複合キーになってしまうなどのデメリットがあるため、PARTITIONを剥がすとMySQLの負荷を下げられたはずです。
しかし、PARTITIONを剥がすという経験はおそらく業務においてもほぼしたことが無いと思いますので、どうやって剥がすかをすぐに思いつくかが一つのポイントだったと思います。結論から言うとテーブルを作り直してコピーするのが最も簡単な方法でした。
ALTER TABLE orders RENAME orders_old;
CREATE TABLE orders # 略
INSERT INTO orders SELECT * FROM orders_old;
DROP TABLE orders_old;
※ ちなみに万が一
DROP PARTITIONをしていたらデータが飛びます。
※ 実際のサービスでは、データが数億件になるような場合や、定期的なデータの消込みのために1日単位で利用するといったケースが多いかと思います。
いくつかの小ネタ
LIMIT 1
が無い問題
最新のtradeを求めるために下記のクエリを実行していました。
SELECT * FROM trade ORDER BY id DESC
実際に「ORMで自動的に
LIMIT 1が追加されることに慣れていたため、生のSQLを扱うときにもLIMIT 1を指定しなかった」という問題に何度か直面したことがありました。
この問題は、リリース直後やテストなどでデータ量の少ないうちは全く問題にならないため非常に気づきにくいのですが、データ量が増えると猛威を振るうというもので、問題を作る際に是非入れたいと思っていた要素でした。
ちなみに、この実装が言語毎の初期スコアの差を生み出しており、 特にGolangにおいては1レコードのみしかfetchしないためアプリケーションのメモリを全く消費しないという問題があったため、普通は絶対にしないありえない実装をしてしまいました。
いわゆるN+1問題
おなじみのループクエリをGET /ordersと
GET /infoに存在する自分の注文を取得する処理に仕込んでおりました。
しかし、よく見ると「自分の注文」であるため、userはすべて同じ(=自分)で、tradeのみ対策すればよいというものでした。 また GET /info の方は一回あたりせいぜい数件しか返ってこないので無視しても良かったかもしれません
ロウソク足チャート
GET /infoに存在するロウソク足チャートを出すための下記クエリは、誰がどう見ても対応したくなるようなもので、さらに時/分/秒の3回分実行されていました。
SELECT m.t, a.price, b.price, m.h, m.l
FROM (
SELECT
STR_TO_DATE(DATE_FORMAT(created_at, '%Y-%m-%d %H:%i:00'), '%Y-%m-%d %H:%i:%s') AS t,
MIN(id) AS min_id,
MAX(id) AS max_id,
MAX(price) AS h,
MIN(price) AS l
FROM trade
WHERE created_at >= ?
GROUP BY t
) m
JOIN trade a ON a.id = m.min_id
JOIN trade b ON b.id = m.max_id
ORDER BY m.t
実際に遅いのは間違いないのですが、クリティカルな問題かというと微妙な遅さで「さてどうしよう？」と頭を悩ませるものとなっておりました。 しかし、仕様には「infoに返すデータは原則1秒以内に反映する必要がある」という記載があり、裏を返すと「infoに返すデータは原則1秒間キャッシュしても良い」ということになるため、 このクエリにとらわれずにキャッシュしてしまえば、1秒に1回ほどしか実行されないものとなるためクエリ自体の対策は不要だったかもしれません。
パスワードのbcrypt
パスワードをbcryptでハッシュ化していましたが、これがアプリケーションがCPUをつかうほぼ唯一の箇所でした。また「パスワードはbcryptでハッシュ化しなければならない」と仕様に明記されていたため対策できないような錯覚をさせていましたが、コスト(ストレッチング回数)に関しては何も言及していないためコストを最小値にすると大幅にCPUが改善するものでした。
実際に既存の11,763件のユーザーデータのパスワードはすべてbcryptでハッシュ化されてはいたもののコストはバラバラで半分はcost=4になっていました。
mysql> select count(*) from user where password like '$2a$04$%';
+----------+
| count(*) |
+----------+
| 5371 |
+----------+
mysql> select count(*) from user where password like '$2a$10$%';
+----------+
| count(*) |
+----------+
| 1060 |
+----------+
ログインに5回連続失敗したときは403を返して良い
仕様にはログインに連続で失敗した場合は403を返して良いと記載されておりますが、実装はされておらずTODOコメントが記載されていました。また、ほとんどのベンチマークシナリオは1回ログインしたらそのままなので、序盤はスコアに大きな影響を与えません。 しかし、実は1/10のユーザーが同じbank_idに対して総当たりログインを仕掛けてくるアタッカーに設定されていたため、シェア機能の有効化によって同時接続ユーザーが増えてくるとかなり効いてくるというものでした。
気づきはしても、対応するにはそこそこの時間がかかると思うので、どのタイミングで手を出すか迷ったかとおもいます。
settingのマスターデータ問題
POST /initializeでベンチマーク中に使用する外部APIのキーが更新されますが、初期実装ではこれをDBに保存し外部APIを使う度にSELECTするようになっていました。
この設定を単純にキャッシュしようとすると複数台構成にするときに工夫が必要となります。また、後述する取引処理のループを作ると、キャッシュ更新が思ったより難しいという、意外と複雑なマスターデータ問題となっておりました。
モジュール分割
パフォーマンスには影響しませんが、これまでのISUCONではほぼ1ファイルでアプリケーションが作られていたのに対して、言語によって細かい差があるものの、原則としてcontrollerとmodelにモジュール(パッケージ)が別れており、更に外部APIは公式モジュールを作るつもりで作っておりました。これに関しては、わかりやすかったという意見と、量に圧倒されたという意見に分かれたように感じましたが、今どき1ファイルのアプリケーションなんてほぼ無いだろう？という気持ちと、後述の大ボスに挑むための大ヒントとするためにこの構成にしておりました。
講評
この問題には様々な課題が用意されていますが、「シェア機能」 というものが最大の面白さだと思っておりました。しかし、13時の時点でほとんどのチームが一度も有効化したことがなかったため、運営部屋では「シェア機能に関してだけネタバラシをしにいくか」何度も議論をしていました。 最終的にはほとんどのチームが有効化していたので安心しましたが、なかなか使われなかったのは問題としてのアピールが少し足りなかったのかもしれないと感じており課題だと思っています。
シェア率の調整
< 10 などで調整しても問題なかったと思いますが、美しくやるならuser.id % 10 < 1などで調整するのが良かったかと思います。
さらに、ユーザー数をカウントして、アプリケーションが処理できるギリギリで無効化するという作戦を取れば、ベンチマーク開始早々に一気にユーザーを増やして、そこから増やさないという方法を取ることもできました。 自然増加が途中からめっきり増えなくなっていたのはそういうことを意識してのことでした。
特に、この問題は各言語毎にスコア上昇の特性に差はありますが、後述の特別賞さえ超えてしまえばどんな施策をしても、 その施策+シェア率の調整で面白いほどスコアが上がっていく気持ちいい問題になっていたので、調整可能であるというヒントを出しても良かったかもしれません。
特別賞
今回は特別賞として スコア15000 を設定いたしました。この特別賞を決めた基準を説明したいと思います。ご覧の通り、この問題はたったの3人で8時間という限られた時間の中で取り組むには非常にボリュームが大きくなっておりました。 また、すべての言語で同じ施策をした場合に、同じようにスコアを上げていったり、言語による有利や不利が出ないように問題を作るということは大変困難で決勝ということもあり半分くらいは諦めてしまいました。
さらに、経験値の問題で最終的には学生の方が不利になると思っていたこともあり、特別賞に関しては、学生や社会人、言語の選択などにとらわれない、どのチームも平等に狙えるものにしていこうという思いで検討し、 その結果、「基本をきっちり押さえれば十分にねらえること」、「ログ分析APIへの非同期送信を完成させること」の2つを条件とすることにしました。
そしてチューニングを繰り返した結果、下記をクリアすればどの言語でも達成可能であるようにしました。
POST /send_bulkを使う
仮にgoを選択しQueryRowを選び1行しかフェッチしないようにしていたとしても、MySQLの負荷がボトルネックとなり超えられない壁となっておりました。
POST /send_bulkを使う
上述の通り 20req/sec のratelimitがかかっているため、ログ送信を行うGET以外のリクエストを合計20req/secしか捌くことができません。 これを超えると「ログが欠損しています」というエラーが出て事後テストをfailするようになるため、この問題を解決しない限り絶対に15000には届きませんでした。
もちろん、初手で複数サーバー化をしたりbcryptを先に行うなど対策の順番は様々ですので、必ずしもこの通りではないかもしれませんが、似たり寄ったりの手数でスコア15000は到達可能だったはずです。
ただし、シェア機能を完全にfalseにしていた場合は、CPUが余っているのにユーザーが来ないという状況に陥って手詰まりになってしまった可能性はありました。
このことに関しては、できるだけスコアにガチャ要素や意図しない裏技をなくした上で、ユーザー数を自由にコントロールさせたいというシェア機能のコンセプトがありましたのでご理解いただければと思います。
用意した課題の完全クリア
さて、この問題の大ボスが銀行APIと取引処理(RunTrade)です。銀行APIに関しては上述しておりますが、RunTradeの特徴をいくつか下記に上げます。
POST /ordersの後に比較的重いクエリを叩いた後で同期的に実行される
この処理の課題
POST /ordersや
DELETE /order/{id} に影響を与えるPOST /ordersがくると10sのタイムアウトを食らってしまう
一言で言うと「deadlockをなんとかして早くしろ」ということなのですが、一度に2つのことを解決しようとするとなかなかうまくいきません。
そこで順を追って対策をしていくとうまくいきスコアはみるみる上がっていきます。
- deadlock
POST /orders
、DELETE /order/{id}、runTrade
それぞれでuserとordersのロックをとっていましたが、runTradeだけlockの順番が逆だったことに気づきましたでしょうか？ (POST:userのみ、 DELETE:user→orders、runTrade:orders→user)これによりdeadlockが発生しやすくなっていました。
この順番を正しくするためにrunTradeでのロック順をuser→ordersに変更するか、あるいはuser,orderのどちらかだけがlockを取ればdeadlockを回避できるようになったはずです。 POST /orders
の高速化
仕様を見るとPOST /orders
ではレスポンスでidのみしか返しておらず、トレードが成立したかどうかはGET /info
やGET /orders
で把握するようになっていたことがわかると思います。
またrunTrade
はそもそも引数にorderやuserをとっていないことから、runTradeを非同期に実行して良いことが理解できたと思います。
また、modelが分割されていたことも大ヒントとなっており、無限ループをどこかで作り runTradeを呼び続けるコードを書くのに10行も必要なかったのでは無いかと思います。
さらに、runTradeをPOST /ordersから剥がすことでその前に行っていた比較的重いクエリも不要になることがわかります
- RunTradeの高速化
RunTradeで利用している銀行APIは遅く、仮に1:1の取引処理であってもAPIリクエストだけで最低でも440ms(=70ms+70ms+300ms)のリクエスト処理時間を必要とします。 そのため、どんなに頑張っても2trade/secの壁を超えていくことはできません。
ここで bank.Commitの「予約は5分間保証される」というルールを思い出すことができると、transactionのcommit後に非同期で bank.Commit を投げて良いという判断ができます。この対応をすることで300ms高速化できるので秒間トレード数を3倍近く増やすことができます。
さらなるチューニング、オープンワールドへ
上記までたどり着くのに8時間という時間はかなり短いものですが、万が一ここまですべてを達成していたとしてもまだまだやることはたくさんありました。実際私自身、今回の問題のドメイン知識が皆無だったため、適当に仕様を決めたので、取引処理に関してだけでもより良い方法がいくつもあったはずです。
事前調整ではスコア100,000 以上は狙える問題でしたので、そのあたりに関しては、出題チームで100,000を超えた @fujiwara やpython移植中に効率的なrunTradeに気がついた @methane さんなどがどこかで語ってくれるかもしれません。
また、私自身もまだスコア50,000くらいまでしか出せていませんので、これから延長戦の期間でさらなる高みに挑戦して、もしいいスコアが出せたらどこかで紹介しようと思っています。
言語差に関して
上述の通り特別賞に至るまでは言語の差はそこまで大きくならないようにしたつもりですが、/send_bulkの対応など非同期化の部分でgoの方が有利になっていた部分があったことは否めません。
また、goのみが
LIMIT 1の付与のみでスコアが5000点前後まで跳ね上がるようになっておりました。これは言語特性の問題で並行処理に強いため、
POST /ordersが詰まっても、
GET /infoなどの他処理にプロセスを使うことができたためだと思います。
しかし、これらはdeadlockをなくしたり外部APIをうまく逃がしたりするということを解決してしまえば他の言語も追いつけた差です。
逆にgoの場合はこのスコアからsend_bulkやshareに対応しない限りは何をしてもスコアが伸びないという状況になってしまい精神的に辛く、一方で、他の言語はどんどん伸びていったと思うので、その分もしかしたらgo以外の方が面白かったという可能性もあるかと思います。
この件に関してこちらからは以上です。
上位チームの解答
ブログを拝見したり直接話した限りですが、優勝した「最大の敵は時差」はrunTradeに関して一切手をつけていませんでした。また驚くべきことにサーバーもapp:db=1:1 で2台しか利用していませんでした。想定していた1台での最大スコアが20000弱でしたので、この構成かつrunTrade未着手でここまでいくのか！？と非常に驚きましたが、GET /info でのキャッシュと
POST /signinでのbanはしっかりと実装されていました。 また、クライアント側から
db.SetMaxOpenConnsをしたことで注文処理は遅いがそれ以外でガンガン稼ぐということに成功してこのスコアが出たのだと思います。
複数台構成にしたらもっと伸びたと思います(例えばinfoとsigninなどオンメモリ専用機と注文処理専用機など役割を変える)。しかし、複数台構成を不具合なく構成するのは困難なものになっていたと思いますので、そのやらなかった判断も素晴らしかったのではないでしょうか？
正直想定していたものとはだいぶ違いましたがこれがISUCONの面白さでただただ見事だったと言わざるを得ません。
一方、競技時間中に最大スコアを記録し、惜しくも2位となった「takedashi」は上記で言うところの完全クリアまでたどり着いているようでした。
しかし、再起動試験においてエラーが多発し、1度目はtimeout多発によるfail、2度目はstatus codeが400で返ってくるという事態が発生し減点により結果を伸ばすことができませんでした。(htmlが返ってきていたのでアプリケーションの問題ではなさそうということしか原因はわかりませんでした。)
rebootによる再起動試験をしていたら、もしかしたら競技時間中に気づくことができたかもしれませんが、気づいたとしても対策できるような問題でも無い気がしますので、これもまたISUCONの面白さではないでしょうか？
そのほかのチームに関しては、シェアの有効化をできずに負荷を上げきれなかったチームや、send_bulkに気づけなかったチームなど、特別賞に至るまでの壁を超えるのに苦戦したチームを多数見受けられました。
何はともあれ、みなさまお疲れ様でした。
最後に
本選も予選同様にトラブルなく開催することができました。これも大会の主催と運営をしてくださっている941さんを始めとしたLINEの皆様のおかげです。(合宿や予選で集まるの楽しかった〜！)
また、大会を通じてスムーズにベンチマークできるサーバー環境を用意してくださったGMO ConoHaの皆様には、大会での完璧な環境だけでなく、出題のために何台ものサーバーをかなりの期間自由に使わせていただきました。感謝してもしつくせません。
さらに、ダメ元でお願いしたところ本選でも10/29まで1週間の延長戦を用意してくださりました。(みなさん！！！ 1チーム1物理ですよ！)
本当にありがとうございます。
問題の作成にあたり、予選でDeNAチームの活躍を目の当たりにして私達の力の入り具合も大きく変わりました。
正直、予選終了時には問題は画面以外9割型できていたのですが、もっと面白くするために大幅に作り変えることになりました。 また、予選で使った素晴らしいポータルが決勝でも簡単に使えるものであったため、ポータル作成の時間をすべて問題のブラッシュアップに当てることができました。
事前解答には平日であったにも関わらず、下記4チームの皆様にご協力をいただきました。
特に白金動物園には7時間で全クリされ、ガチムチレンジャーにはrunTrade直列化なしで想定以上にスコアを伸ばされるという結果が、我々を混乱に陥れ、PARTITIONを追加するなど初期データの作りに大改革をもたらしました。
おかげさまで事前解答時よりもだいぶ面白くなったのではないかと思っております。
私が作ったgoによる初期実装を各言語への移植する作業は、下記のオールスターメンバーに対応していただきました。
また、ログをポータルでリアルタイムに見たいんですよねーと言ったら、sugyanさんからpull-requestがやってきたときはとても感激いたしました。
そして、社内のチャンネルに突然投げたSOSに即反応して、ISUCOINの画面を作ってくれた mp3さん本当にありがとうございました。
なにより、問題を考え、ポータル、プロビジョニング、ブラックボックスAPIを担当し、そして、私がベンチやアプリを作り直す度に何度も解き直してくれた fujiwaraさんには本当に感謝しております。 おそらく私と合わせて2人で軽く300回はベンチを回したと思いますw
皆様本当にありがとうございました。
以上、カヤックから fujiwara と ken39arg がお送りいたしました。
来年はカヤックに5回目の優勝を持ち帰れるように参加者として優勝を目指します!
カヤックでは一緒に優勝してくれるメンバーをいつでも募集しております!!
重ね重ねありがとうございました。
