競技プログラミングはISUCONの役に立つ 【ISUCON10予選参加記】
単なる普通のISUCON参加記です。 そんなに競技プログラミングの話はないので、そういう話を期待していた人はごめんなさい。
こういうのは忘れないうちに書かないと書けないがち。
ISUCON10にチーム「:羽付きのお札:」で nana ( 菜々🕴 (@nonamea774) / Twitter ) と yu3 ( ゆー (@yu3mars) / Twitter ) のメンバーで出て、最終1195点（時間中の最高点は1400点ほど）で予選落ちでした。
開始前日まで
チームでどの言語を使うかを事前にGo言語に決めて、Go言語の勉強ついでに、練習として去年の予選問題を解いたりしていた。 ちなみに自分では23,000点ぐらい（当時のスコアで言うと全体の6位くらい）出せていた（もちろん他の人のブログとかを参考にした）。
開始直前
nanaは偶然にも（？）東京に来ていたので私の部屋で一緒にやることにした。yu3とはslack call等でコミュニケーションを取る。 開始が遅れたのでゆっくり朝食をとった。
なぞって検索
開始するとさっそくポータルが502で落ちていた…まあ数分で見えるようになったので問題を呼んだりsshで入れることを確認したり、実際にブラウザで触ったりした。 明らかに「なぞって検索」がやばそう。案の定広い範囲を囲うとめちゃくちゃ遅い。 ポータルが不調で、まだベンチマークに掛けられなかったので、なぞって検索について考える。
こういう二次元データを囲った範囲に入る点を求めるのは、大抵なんらかの賢いデータ構造（kd-treeとかそういうやつ）が必要になるはず（これは割と競技プログラミングの経験が役に立った感じ）。 でもこれを手で実装するのはしんどそうで、nanaに相談したら、GISデータとかをmysqlとかでうまく扱える仕組みがあるはず、と教えてくれたので調べることにした。 なるほどたしかに、Geometryという形式で格納して、Spatial indexを有効にしておくといい感じにやってくれるらしい。 のでこれを実装することにした。
物件の追加クエリとかスキーマ定義はまだいいとして、初期化時に使う.sqlファイルを更新するのがだるい。 コンテスト後にgenerated columnsというのがあるというのを知ったが、このときは知らなかったので、Rubyでクエリ文をパースするスクリプトを書いて書き換えた。
途中で、「椅子を通せるドアかどうかを判定する方法」（椅子にはH,W,Dの情報、ドアにはH,Wの情報が与えられるので、椅子を直方体だと思ったときにうまく回転させることでドアを通せるかどうか）を計算するのに、すべての回転を調べるのは非効率なのでなんとかしたい、という相談をnanaから受けた。 ちょっと考えると椅子の大きさのうち、最大のものは考えなくて良い（その方向を奥行き方向に持ってくれば、残り2方向がドアを通せれば良く、それで通せなければ通らない）ことに気付いた。 ここでも競技プログラミングの経験が効いた気がする。
実装が終わってちゃんと動くようになると、ちゃんとスコアが跳ねて喜ぶ。（700店くらい？） そしてスロークエリログを眺めると自明にインデックスを張れる場所があるので張ると、さらにスコアが跳ねた。 この時点で20位ぐらいだったかな？
インフラまわりとかデプロイ周りとか
基本的にゆーさんとnanaに任せていたので詳しくはわかっていないけど、botを弾くとかが若干効果があったのかな？
デプロイはmake deployとかを叩くと、Makefileにssh hogehogeとか書いてあるのでそれでローカルのバイナリとかをサーバーに送って、アプリ等を再起動する、というあたたかみのある方法になった。
とはいえ、ISUCONの短時間という制約ではそんなに悪くない方法だと思う。終了後に知ったetckeeperとかは今後試してみたい。
物件・椅子の入稿
ここまで来て、原因不明の「critical error」でスコアが0になることが何度か起きた。
とくにエラーが起きるような変更は見当たらなかったのでだいぶ悩んだが、スロークエリログを眺めると、COMMITで5秒かかっていて、どうやらここでタイムアウトしているらしい。
アプリを眺めると明らかに物件・椅子の入稿がやばい（トランザクション内で、csvの行数だけINSERTが発行される）ので、これをどうにかすることを考える。
nanaが文字列結合等を駆使して巨大なINSERTを1回だけ発行する方法を、私がPrepareをつかって1クエリの負荷を低減する方法を実装した。
結果的に同じとこをいじることになったのは、短い時間の使い方としては失敗だったかも。
ちなみにどちらの実装でもタイムアウトは回避でき、failは回避できるようになった。
検索クエリの改善
ここまで来て、物件・椅子の検索が支配的になってきたので、これを考える。 うまく行きそうなインデックスを張ってみるが、範囲指定が2個出てきたりすると、普通に張ったのでは速くならないっぽいので困ってしまった。 実はMySQL8にすると行けるらしいが、知らなかったしかなり罠が多かったみたいなので、うっかり足を踏み入れなくてよかったかもしれない（？）
大きさに関するクエリは、範囲として指定できるのがそれぞれ4種類（＋指定なし）しかない。
したがって、範囲に0〜3のIDを割り振れば、HeightRank = 2みたいなクエリになってインデックス使えそう、となって実装し始めるが、これは最終的には間に合わなかった。
ここもgenerated columnsを知っていればサクッと実装できた気がするので悲しい。
nanaは色や椅子の種類をIDに変換するコードを書いていた。けっこうバグってたけど最後にはちゃんと動いていた。
DBの負荷分散
mysqlがCPUの85〜95%程度を食っていたので、この負荷を分散したかったが、更新があるのでレプリケーションは実装間に合わなさそう（この時点で残り1時間程度）、と思って却下した。 しかし、終了後に教えてもらったこととして、このアプリは椅子と物件でJOINすることがないので、二つのデータベースを別マシンに分けることで、負荷分散が比較的簡単に可能という構造になっていた。 このあたりは、よくアプリの構造を観察することで見つけられたはず（こういうところも競技プログラミングみがある）で、かなり悔しいポイント。 物件検索と椅子検索でそれぞれ半分くらい時間がかかっていたので、もしDB分割をやっていれば、2倍程度のスコアになったと思われ、これは本戦出場ライン近辺になるので、取り組めていれば…と悔やむ。
終了後
終了後は高速に nanaとチーム「百万円ドリブン」の twitter.com と、偶然来ていた ten986 (@ten986) / Twitter とうしとらに打ち上げに行った（そのあとさらに2軒はしごした）。びーるうめえ。
良かった点
事前に練習したおかげで、Go言語の実装・コード読解で詰まることが少なかった。 チームメンバーと互いに相談して、より良い解決策に近づけた。 競技プログラミングの経験を役に立てられた。
反省点
DBに関する知見（generated columns）がまだまだ足りない。 アプリの構造をよく観察するべき。 決勝に進みたい！
試してみたい点
Go言語、静的型付け言語とは何だったのかというレベルで静的検査が弱くてつらいので、Rust使いたい（ほんまか？？？？？）
