ymyzk’s blog

ISUCON7 本選で学生枠1位になりました

—

by

Yusuke Miyazaki
in

チームMLとして @ishiy1993 と2人で ISUCON7 の本選に出て，学生枠の1位 (全体の7位) になりました．使用した言語は Python で，最終スコアは 19,172 でした．満足のいくスコアではありませんでしたが，我々が今持っている力は出し切れたかなあと思っています．

問題

近いうちに問題の詳細が公開されると思うので簡単にまとめると，今回のお題はクッキークリッカーを複数人でプレイできるようなものでした．通信は基本的に WebSocket で行われるという特徴がありました．

追記: GitHub で参考実装やベンチマーカーを含むリポジトリが公開されました

事前の準備

予選は論文締め切り直後に出場したためあまり準備をせずに参加してしまったのですが，本選では以下のようなことを事前に準備することが出来ました．

  • 開始直後の作業手順書
  • サーバーセットアップ用のスクリプト
  • ミドルウェア設定の秘伝の?タレ
  • Python の MySQL や Redis のライブラリの使い方
  • Lint (flake8) の準備など

今回の問題は WebSocket が主だったので，事前に準備したプロファイラが役に立たない部分も多かったのですが，サーバーのセットアップ用のスクリプトなど役立つ部分もあったので，ちゃんと準備をしたのは良かったように思います．

やったこと

多少時系列が間違っているかもしれませんが，大体以下のようなことをやりました．

  • マニュアルを熟読
  • サービスを実際に使ってみる
  • サーバーのセットアップ
  • iPad 2台でサーバーのモニタリングを行えるように
  • 初期スコアを Python と Node.js でとる
    • 最初は Python でやるつもりだったが，「WebSocket + Python はつらいかも」と思ったので，書けそうな Node.js でもベンチを取った
    • Go はあまり得意ではないので選択肢には入りませんでした…
    • Node.js の方がスコアが良さげでしたが，あまり差がなかったので得意な Python をここで選択しました
  • ベンチ中のサーバーの負荷を見たり Nginx のプロファイリングの結果を見たり
    • 「アプリケーションサーバーの負荷が偏るとスコアが伸び悩みそう」
    • 「WebSocket のやりとりの部分のどの部分が重いのか分からなくてつらい」
    • 「Nginx と MySQL のプロファイリングがほぼ役に立たない」
  • コードを一通り読む
    • 「asyncio…!」
  • どの部分の負荷が高いのかが分からないので status・addIsu・buyItem の実行回数をカウントする仕組みを入れる
    • status・addIsuが大体同じ回数くらいでbuyItem が一桁少なかった印象
  • m_item テーブルの内容が不変なことに気づいたので，起動時に読み込んでキャッシュ
  • アプリケーションサーバーの負荷分散を行う仕組みの導入
    • Redis で情報を共有
    • 各アプリケーションサーバーが受け持つ部屋の数が同じになるように分散
    • アプリケーションサーバーと部屋を1対1対応させる
  • status・addIsu・buyItem の実行時間を取る仕組みの導入
  • get_status の高速化に取り組む
    • 「current_time 以前の adding の総和をキャッシュしたい」
    • 「トランザクションが複雑なので下手に手を入れて fail したくない」
    • 上のような理由でメモリや Redis を使ってキャッシュするのは避けて，MySQL だけでなんとかする方法を考えることにしました
    • 色々試しましたが最終的に，以下のようなものを実装しました
      • get_status で current_time 以前の adding の総和を計算
      • current_time 以前の adding を DELETE して，代わりに計算した総和を INSERT
      • 毎回これをやると逆に遅くなるので current_time 以前の adding が一定数以上たまったときのみこの処理を実行
    • この方法だと複雑な calc_status に手を入れずに高速化することが出来ました
  • DB を見ていると巨大な数が入っているので，これらの計算が遅くないか気になる
    • REPL で適当に大きい数の演算を試してみるが，高速に計算されたので問題ないものとして無視することにする
  • アプリケーションサーバーの負荷分散があまりうまくいっていなかったので改善する
    • サーバーの CPU 負荷を定期的に Redis に登録するようにする
    • CPU 負荷が低そうなサーバーに WebSocket をつないでもらうようにする
  • アプリケーションサーバーの負荷が最大でも50%に到達しないくらいだったので，プロセス数を増やすことにする
    • 2プロセス/1アプリケーションサーバーでもまだ少し余裕があったので，最終的に3プロセス/1アプリケーションサーバーに
    • アプリケーションサーバーと DB サーバーの負荷がいい具合になったので，サーバー構成は最初と同じアプリケーションサーバー3台とDBサーバー1台のままでした
  • この時点で残り時間が少なく，短時間で打てる手がなくなってきたのでミドルウェアの設定等に秘伝のタレを投入
    • 若干スコアが改善
  • 再起動試験
  • 負荷分散がうまくいくかどうかでかなりスコアが変わったのでベンチマークを連続して回す
  • いい感じに負荷が分散できていて，ベストスコア 18,964 が出たタイミングで終了

スコア

最初のベンチマークの結果が 2,364 で最終のベンチマーク結果が 18,964 でした．再起動後の試験でベストスコアの 19,172 が出たようで驚きがありました．(結果発表の時に最終のベンチと違うスコアが出たので fail したと思っていました．) また負荷分散がうまくいったかどうかでかなりスコアが上下しています．

最終結果は以下の通りです．最終スコアでも再起動後のスコアでも特に順位は変わりませんでした．

感想

  • Python 実装は asyncio を使って実装されていて，従来の Flask や Bottle を使ったものとは違う考え方が必要でした
    • asyncio はちょっと書いたことがある程度でしたが，全くの未経験よりは大分ましだったように思います
  • Go を選んで多倍長整数に苦しんだチームが多かったようですが，我々のチームは意図せずこの問題を回避できていました
    • 上にも書いたように多倍長整数の計算速度を簡単にチェックして問題があるかどうかは一応競技中に確認しています
  • 途中，競技用のサーバーに SSH の攻撃が来ていて，これが負荷分散に影響を与えていたようで厳しい部分がありました…
  • MySQL を使ったトランザクション処理が多用されていて，これをオンメモリにするという部分には手を出せませんでした
    • 他のチームのスコアを見ていて劇的にスコアを上げるチームがほぼなかったので地道な改善を続ければ良いかなという気分になってしまっていました
    • 2人チームだったので大規模な実装変更を試す人員を割けなかったという理由もあります
    • 講評や他のチームの話を聞いていると思い切った変更をしていかないと社会人枠で上位を取るのは厳しいなと思いました (学生枠で出場できるのは今年が最後の予定)
  • 予選も本選も我々のチームはあまり大規模な変更はせずに，少ない変更で地道にスコアを上げていくような戦略だった気がします
    • 目標が学生枠1位で全体での優勝は狙っていなかったのであまり無理をしなかったという理由もあります

最後に

目標としていた学生枠の1位を取ることが出来たのは良かったですが，まだまだ勉強すべきことがたくさんあることも実感させてくれくれました．

また，チーム名 ML で Python をつかっていたので，ML を Machine Learning の略だと誤解されていた気がしていますが，チーム名の ML は Meta Language の略です．OCaml や Haskell を愛する❤️メンバーの気持ちが表れたチーム名です．

最後になりましたが，運営の皆さまには楽しいイベントを提供して下さりありがとうございました．

関連