ISUCON10予選に出た

先週土曜日(9月12日)に開催されたISUCON10の予選に出場していました。

ISUCONというのは、「いい感じにスピードアップコンテスト」の略で、与えられたWebサービスを高速化し、その速さでつけられる得点で競う大会です。

isucon.net

isucon.net

三人までのチームで参加できるので、私(@suzusime)、kurimotzくん(@chestnut314 )、aotsukiくん(@RikuAotsuki)(ともに京大マイコンクラブの後輩)と一緒にチーム「狼と神々の犬部」として参加しました*1。kurimotzくんが2度目の参加、私とaotsukiくんは初参加でした。

結果、0点で残念ながら本戦には出場できませんでした。0点になってしまったのは最後にいろいろミスってまともに動作しなくなってしまったのが原因ですが、それがなかったとしてもまあ本戦にいける点数にはなっていなかったように思います。

練習

  • 5日前に集まって(といってもオンラインですが)、ISUCON9の予選問題を皆で解きました。 - プロファイルの取り方、MySQLへのインデックスの貼り方、N+1問題の解決法などを確認しました。
    • このときはPythonを使いましたが、メンバーが少しJavaScriptのほうが得意(?)なのと型があると嬉しいということで本番ではnode.js(TypeScript)にすることにしました。
  • 練習のあと、やっぱりNewRelicとかいうのを使えるとよさそうということで無料提供に申し込み、本番前日にNewRelicを突っ込んでもう少し練習するなどしました。

isucon.net

本番振り返り

本番は練習と同じく、直接集まることはなくSlackのテキストチャットとボイスチャット(Slack Call)を使って連絡しながら行いました。

9時前

予選は10時開始18時終了予定ということで、生活リズムが狂いがちな中、なんとか8時頃には起きました。……が、運営より準備が想定より長くかかっているため開始が12時以降になるとのアナウンス。参加者Discordで「12時までに始まることはありますか?」「ないです」という旨のやりとりがなされていたのを確認し、少し寝ることにしました。

Discordで「いい感じに少し眠るコンテスト」って言っていた人がいてよかったです。

12時20分

結局開始は12時20分になりました。半分くらい食べたとんかつ弁当を冷蔵庫にしまって競技開始です。

最初は2手に分かれました。kurimotzくんとaotsukiくんはドキュメント読み、私は初期実装を起動したりする係になりました。 与えられた踏み台サーバーへの接続用sshconfigが私のWindowsではそのまま動かなかったり(WindowsのOpenSSHでは踏み台利用で問題が起きがちなことを知っていたので少し調べましたが、適当なところで諦めてWSLからSSHすることにしました)、手元にトンネルを掘らないとWebサービスに繫げない仕様など、少し戸惑うことはありましたが無事にログインし動作確認をすることができました。

コロナ禍の時事ネタということで出前サービスあたりかなと予想していたのですが、そんなことはなくISUUMOなる物件検索サイトが題材でした*2

なお、この段階で今年はnode.jsの参考実装がTypeScriptではない素のJavaScriptであることが判明しましたが、そのままいくことにしました。

その後、最初の手を入れていない段階で試しにベンチマークの点数を見てみたいところでしたが、参加者向けポータルの不具合(というより過負荷?)でベンチマーカーが起動できない状態だった*3ので、初期状態でのベンチマークは諦めてaotsukiくんにNewRelicのコードを差し込んでもらいました。

13時頃

ドキュメント読み班からの報告で「今年は去年と違ってBotを弾く要件があって、わざわざそんなことが書かれているのだからやれば効きそう」というのがあったので、やることにします。これはUserAgentを見て弾くという要件なのですが、それなら入り口たるNginxでやるのがよかろうということで、比較的Nginxに詳しい私が担当することにしました。

弾くべきUserAgentはドキュメントに正規表現で与えられていたのですが、そのままコピペするだけでは nginx -t が構文エラーを吐きました。

与えられた正規表現を見ると理由もなさそうなのに (?: )(キャプチャ内容を記憶しない括弧)が使われていたりして、そのへんが悪いのかと思って怪しげな表現を消したりしていましたが、それではまだ通りませんでした。 結局、怪しげなパターン以外を少しずつ設定ファイルに足してはテストにかけて構文エラーで怒られないところまでやる、という方法をとりました。

観測の結果、半角スペースとセミコロンがパターンの中に含まれると構文エラーが出ることがわかりました。エスケープの方法がよくわからなかったので、単純にこれらをパターンに含めない(=ブロックしない)ことにしました(完全にBotをブロックすることはできなくなりますが、そのような例は少ないことが想像されたため)。

なお、与えられた正規表現がどういった方言なのか(PCREなのか)についてclarを送ってみましたが、ノーコメントということでした(そこに何かポイントがあったのでしょうか)。

あとの2人は同時並行でデータベースにインデックスを貼ったり、アプリのコードを見て怪しげなクエリを解きほぐす作業をしてくれました。

このへんでベンチマークができるようになったため試してみましたが、Botを弾く設定ではほとんど点数が上がらず、インデックスを貼るのは効いたな、という感じでした(手元に点数の記録が残っていないのであまり確かなことが言えないのですが……)*4

15時頃

さて、Nginxの設定が終わったので私もアプリとデータベースの改修のほうに合流しました。

計測の結果*5時間がかかっていそうということで最初に俎上に上がったのが、選んだ椅子に適した物件の一覧を表示する recommended_state APIのクエリでした(top の結果からもDBアクセスがボトルネックになっていそうな結果でした)。 これは6つの条件をORでくっつけた条件で物件を選び出すもの(見た目からしてやばそう)でしたが、それが「どの向きでもいいから椅子が扉から入るかどうか」という条件であることが解明され、椅子の高さ、幅、奥行きのうち小さい2つを用いて検索すれば2つの条件のORにできることが(かなり早々に)わかっていました。

-- before
SELECT * FROM estate where (door_width >= ? AND door_height>= ?) OR (door_width >= ? AND door_height>= ?) OR (door_width >= ? AND door_height>=?) OR (door_width >= ? AND door_height>=?) OR (door_width >= ? AND door_height>=?) OR (door_width >= ? AND door_height>=?) ORDER BY popularity DESC, id ASC LIMIT ?

-- after
SELECT * FROM estate WHERE (door_width >= ? AND door_height >= ?) or (door_width >= ? AND door_height >= ?) ORDER BY popularity DESC, id ASC LIMIT ?

が、なぜかくっつけただけで等価なはずの条件で検索しているのにベンチマークが結果不正で落ちていました。いくつか手でリクエストを送って結果をデバッグログに出して眺めてみると、確かにたまに異なる結果が返っていることがわかりました。

それで頑張っていろいろ原因を探していたのですが、DBへのクエリ自体をprintf*6してみたところ、そもそもクエリが「椅子の高さ、幅、奥行きのうち小さい2つ」で組み立てられていないことが判明しました。 ……JavaScriptの配列の sort() をそのまま使うと「要素を文字列に変換してからソートする」のが原因でした、はい。

これを修正するとベンチマークが通りました。たしか560点くらいで今回の最高値がここで出ていたと思います。

17時頃

これで一段落はしたのですが、先ほどのクエリについて、ORは遅いらしいからUNIONに変えようというので、kurimotzくんが奮闘を続けてくれました。 なのですが、なぜか正しい値が返らないということが続いたため、私は値の簡易チェックツールを作ったり、Nginxの入り口を別のアプリとは別のサーバーにする設定などしていました。

そんなこんなしているうちに、「データベースにある各物件に対して、扉の幅、高さのうち大きい方、小さいほうを予め計算してデータベースに入れておけばrecommended_stateでORがいらなくなるのでは」というアイデアが出ました。 それでいけそう、ということでUNIONはやめてそちらを実装することに(初期化APIを呼んだときにデータベースをいじれば、その時間はベンチマーク結果に影響しないようでした)。aotsukiくんが高速に実装してくれました。

その間は並行してnazotte(なぞって検索)の挙動の確認などをしていました。

これは与えた多角形に含まれる物件の一覧を表示する機能なのですが、この部分のコードを見ると、「DBにまず(多角形を含む)矩形に含まれる物件を問い合わせ、そのそれぞれの物件に対して多角形に含まれるかをDBに問い合わせて判定する」ということをしていました。 ぱっと見てN+1問題が起きてはいるのですが、後半の多角形衝突判定がどう考えても重いため、このようにしているのは妥当に見えました。

というより、これを改善するためには多角形判定をJS側で自力実装するしかなさそうで、厳しそうなので見送ることにしました*7。 なお、後でDiscordでの感想戦を眺めた限りでは自力実装していたチームも結構あり、またそこの誤差で死んでいるという報告もありました。見送った判断は妥当だったかなと思います。

19時頃

DBをメモリに載せてしまえば速くなるのではないかという話になります。 また、3台のサーバーのうちまだ2台(Nginxに1台、アプリケーション及びDBに1台)しか使っていなかったので、データベースの「椅子」「物件」のテーブルを別のデータベースにしてしまえばいいのではないかというアイデアも出ました*8。 ここからはこの2つを並行してやっていくことになります(私は主にデータベース分割のほうをしていました)。

しかし、前者は適切なメモリ割り当て量がなかなかわからない、後者は別のマシンからのDBへのアクセスがなかなかできない(セキュリティ周りの設定で手間取った)という問題で難航します。一度はDBにメモリを割り当てすぎてメモリを食い潰し、SSHで操作できなくなってしまって運営にサーバーの再起動をお願いする羽目にもなりました(すぐに対応していただけてありがたかったです)。

DBをメモリに載せるほうは、一応成功したのですが、ベンチマークしたところ点数がめちゃくちゃ落ちたため導入しないことにしました。

DBの分割も、終了20分前あたりになってようやく成功します。 が、ベンチマークを走らせようとする段になって問題発生。 「アプリを手動で起動した場合は正常に動くのに、systemdで起動した場合はrecommended_estateなどの一部機能が動かない」という謎現象に直面しました。競技終了後には再起動試験があるので、systemdで起動するようにしておかなければならないのですが、それがうまくいかないのです(競技中はprintfデバッグのしやすさなどから適宜手動起動に切り替えていました)。

パニックになっていろいろ試したのですが、うまく動かないまま試合終了。 終了3秒前くらいに思い出したように投げたベンチマーク結果(460点くらいが出た)は終了後に結果が返ったので無効。結局少し前のバグっていたときの0点が最終的なスコア(本戦出場チーム以外は参考得点扱いではありますが)になりました。

反省

翌日になってkurimotzくんが究明してくれたことですが、最後の「systemdで正常に動かない」問題は、「systemdで起動するときだけenv.shという(初期設定の)環境設定ファイルを読み込んでいた」かつ「アプリ側はenv.shの設定がないときだけ別サーバーのDBを読みに行くようになっていた」ことが原因でした。

const dbinfo = {
  host: process.env.MYSQL_HOST ?? "127.0.0.1",
  port: process.env.MYSQL_PORT ?? 3306,
  user: process.env.MYSQL_USER ?? "isucon",
  password: process.env.MYSQL_PASS ?? "isucon",
  database: process.env.MYSQL_DBNAME ?? "isuumo",
  connectionLimit: 100, // 最初は10
};
const dbinfo2 = { // estate
  host: process.env.MYSQL_HOST ?? "10.164.20.102",
  port: process.env.MYSQL_PORT ?? 3306,
  user: process.env.MYSQL_USER ?? "isucon",
  password: process.env.MYSQL_PASS ?? "isucon",
  database: process.env.MYSQL_DBNAME ?? "isuumo",
  connectionLimit: 100, // 最初は10
};

あまりの凡ミスで悲しくなります。周りの話を聞くに、このDB分割が正常に動けばかなり点数が上がっていたようで、あと少し時間があればというところ。

また、最後の最後までこれに手をとられていたせいで、計測ツールのコードを除去したりログを吐かない設定にするなどの基本的なことに手が回らなかったのも惜しいところです。 こういった最後の調整のために最低30分くらいは残しておくべきだったなと思います。

内容的な面ではrecommended_stateという一つのAPIの改善にこだわりすぎたのが第一によくなかった点かなと思います。一箇所の最善を求めて時間を費やすのではなく、もっと広く目を向けるべきでした。

とはいえ、これはそもそも「ORをUNIONにするとどれほど速くなることが期待できるか」といった知識に欠けたことが原因の一つで、他に「{データベースをメモリに載せると、データベースを垂直分割すると、データベースに計算をさせる部分を除くと}どれだけ速くなることが期待できるか」分からず雰囲気でやっていたことも含めて、経験不足というのが根源的な原因であろうと思います。

ISUCONは短い時間で必要な措置を見極めて実装するという競技の性質上、試しに実装しなくても見切れる経験・知識が大事なのではないかなと思うところです。

終わりに

思ったことがうまく実装できず、実装できたところもあまり点数上昇に結びつかなかったことから、残念ではありました。

が、練習、本戦通して学べたことは多くありました。私としては特に、座学ではよく分かっていなかったデータベースまわりの感覚が実践を通して少し分かったのが大きかったです。あと8時間超ぶっ続けでやるとめちゃくちゃ疲れること、疲れた状態では判断力が低下することも……。

チーム競技はICPC国内予選以来ですが、やはり一人でやるより楽しいです。来年もISUCONがあるならぜひ出たいと思います。 運営の方々、長時間の準備と対応お疲れ様でした*9。そして、ありがとうございました。

次は今回の反省を活かしもう少し手際よくやっていきたいですね。めざせ100万円!

*1:なお、チーム名はSNS部方式(各人3つずつ単語を選んだ9つを合わせ、その中から3つランダムに選びつなぎ合わせる)で決めたものです。

*2:解説・講評記事によれば今回の作問担当がリクルートのチームで、自社サービスネタということらしいです。私はSUUMOがリクルートに運営されてることを知りませんでしたが……。

*3:なお、これの補償措置ということで競技時間は8時間から40分延びて21時までになりました

*4:講評によると最初のうちはBotを弾いてもあまり点数が上がらないという仕様だったようです

*5:実は練習のときと違ってNewRelicがDBの詳細を吐いてくれない問題があったのですが

*6:JSなのでconsole.logですが

*7:競プロの幾何問題か?

*8:データベースをいじった経験はほとんどなかったけれど、ソシャゲ会社のインフラエンジニアをやっている先輩の愚痴を聞いていたため「垂直分割」という言葉だけは知っていたのです。

*9:まだ本戦があるので終わっていませんが。