All Articles

ISUCON10予選を全体2位/学生1位で通過した(shallowverse)

こんにちは，y1rです． ark, akkyと，チームshallowverseでISUCON10予選に参加しました． このチームでISUCONに参加するのは2回目で，前回のISUCON9は予選敗退でした． 今回は全体2位，学生1位で予選を通過できましたので，やったことを紹介します．

最後1時間のベンチマークの様子．この後大騒ぎした． 最後1時間のベンチマークの様子

公開リポジトリはこちら．

役割分担

y1rはGoに不慣れだったので，アプリケーションの実装についてはコメントとデバッグをするだけで，実装はしないことにしました． arkとakkyでペアプロをした方が，デバッグの時間が短くてすむことが練習から分かったので，ペアプロを採用しました．

  • y1r: インフラ，デバッグ，デプロイ，ベンチマーク&プロファイリング等雑用．
  • ark: GoとSQLが書ける．すごい．SQLに詳しい．
  • akky: GoとSQLが書ける．すごい．静的解析に詳しい．

準備

2日間集まって対策をしました． 事前に練習していないことは本番でできないので，前回通過できなかったISUCON9の予選を徹底的に解き直しました． 前回の僕らは，外せないトランザクションを外してしまっていたことが判明し，N + 1の解決方法を重点的に見直しました． あわせて，複数台構成の練習もしました． また，Goの静的解析インターンに参加していたakkyが，GoのソースコードからSQL文を抽出してテーブルごとにまとめてくれる解析ツールを作ってくれました．

当日

10:00 ~ 12:00

y1rが複数台構成の設定を見直して，できるようになりました（今更）． ISUCON9予選のベンチマークが35000程度になって喜んでいました． みんなでご飯を食べて気持ちを高めました．

開始 ~ スコア1200まで (15:30)

全員でマニュアルを音読して，以下のことが判明しました．

  • botからのアクセスがあること

  • スコアに直結するAPI

    • POST api/chair/buy
    • POST api/estate/req_doc

  • 落としてはいけないAPI

    • POST api/chair
    • POST api/estate

対応方針として，botからのアクセスはnginxで弾く，これら4つのAPIは追って確認する，と決めました． また，kataribeで調べたところnazotteが遅いことが分かりました．

よって役割分担として，y1r(インデックス，bot対応，DBを103に)，ark + akky(nazotteのN + 1削除)としました． nazotteは，（arkが競技プログラミングに精通していることから）goで実装またはライブラリを利用する案もありましたが， 今回は実装量が少なく済みそうなDBでの処理としました．

それらへの対応を済ませた後，積み残していた4つのAPIを見始めました．

POST api/chair/buy

akkyがUPDATEにWHERE句が使える，と教えてくれたので対応をお願いして，トランザクションがなくなりました．

POST api/chair, api/estate

arkがN + 1を削除してくれました(bulk-insert)．

POST api/estate/req_doc

DBアクセスがないので見ませんでした．

y1rは，nazotteやlow_price, 検索系のAPIが遅いのが気になってインデックスを貼ったり実行計画を確認しました． ちょうどこの頃，ベンチマーカーが使えなかったので，ベンチがなくてもできる小さい検証を色々できてよかったです．

並行して，ark + akkyがlow_priceの高速化に取り組みました． 大量のリクエストをさばくため，毎回のリクエストごとにSQLを発行するのではなく， 数秒毎にSQLを発行することで，low_priceの反映頻度を削減しました． しかし，この方針はベンチマーカーのverifyをpassできずに諦めました．

スコア1400まで (18:30)

nazotteが未だに遅かったので，困っていました．実行計画を見てみると，緯度，経度の複合インデックスがうまく使えていないことが分かりました． akkyが，MySQL8だとSRIDを指定しないとSPATIAL INDEXが使えない，という記事を見つけてくれて，SPATIAL INDEXを知りました． これはMySQLにPOINT型でカラムを作っておくと使えるインデックスで，これがあれば矩形の絞り込みなしに高速に実行できそうだとなりました．

ただ，そのインデックスをこれまで使ったことがなかったので，手で初期データ(estate)からPOINT型を持つテーブル(estate2)を新しく生成して，実行計画を確かめました． その結果，我々が使っていたMySQL 5系の場合はSRIDがなくてもインデックスが使え，確かに早くなることが実行計画から分かりました． よって，この実装をark + akkyにお願いすることにしました．

スコア2000まで (20:00)

y1rは，APIの分散に取り組もうと考えました． まずはestateとchairで別のAPIサーバへの分割を検討しましたが，DBがボトルネックだったことから試しませんでした． そこでDBのCPU負荷を分散させたかったのですが，よくコードを見てみるとJOINがないことに気づきました．

よって，DBを以下のようにテーブルごとに分けることにしました． コードの改修が必要だったので，akkyに手伝ってもらい，ペアプロして，デプロイまでしました．

  • 101: nginx, chair-api, estate-api
  • 102: chair-db
  • 103: estate-db

この頃，検索系のAPIが遅いことが問題になっていました． これは，多すぎるLIKEが問題だと考え，以下の方針を検討しました．

  • N回LIKEを使用しているfeaturesについて，順序をつけておくことでLIKEを1回に
  • featureごとのboolのカラムをつける（LIKEなし）

しかし，実装難易度と残り時間からこの実装は諦めました． 他に思いついた案として，「COUNT（全データ）と実際のデータ（paginationあり）をまとめて取ってくる」がありました． この方針も，結局はMySQL 5.7ではWITHが使えないなど一筋縄ではできず，色々試しましたが時間の関係で断念しました．

スコア4000まで (21:00)

y1rは，DBが詰まっていたので，DBのパラメータチューニングが効くと思い調べてきた秘伝のタレを貼りました． しかしDBの初期化に時間がかかるようになってしまい，初期化の処理を高速化する必要がありました． よって，akkyに手伝ってもらって，chair dbとestate dbの初期化をgoroutineで並列化してもらい， あわせて，不必要なデータのinsertをやめました．

この変更で，DB初期化に間に合うようになりました． この後はベンチマークガチャをしつつ再起動試験をして，スコア4072が出たので終了としました．

よかったこと

  • みんな仲良く

    • 実装難易度と性能の面からどうやって実装するか全員で決定

  • 根拠のある最適化

    • kataribe
    • 未知の手法(SPATIAL INDEX)に挑戦する前に，本当に早くなるか実行計画から検証

  • デバッグ時間の最小化

    • SQL文の構文エラーを防ぐため，mysqlコマンドで対話的にSQL文をチェック
    • ベンチマーカーなしで高速にデバッグできるよう，ブラウザから挙動を確認

最後に

2回目の出場でしたが，運に恵まれて良いスコアを出すことができました． 3人で議論しながら作業をしていましたが，最後までワイワイでき，結果以前に楽しかった印象の方が大きいです． このような面白いコンテストをずっと行っておられる，運営の皆さんに感謝いたします．

みんなで晩ごはん． みんなで晩ごはん

ISUCON後にエナジードリンクを飲む． エナジードリンク

本選もがんばります！！！

Published 3 Sep 2020

Machine Learning Platform EngineerYuichiro Ueno on Twitter