kotamanegiの取り扱い説明書

のんびり趣味の事を書いてます。

量子競プロ学習サービスQookbookについて

この記事は 競プロ Advent Calendar 2023 の 13 日目の記事として書かれました。

未踏ターゲット事業で、競プロ風に量子コンピュータの勉強ができるサービスQookbookを開発しています。

目次

自己紹介

大阪大学大学院情報科学研究科 コンピュータサイエンス専攻M2のkotamanegi (@small_onions) です。 競技プログラミングでは、1か月弱ほど前に国際大学対抗プログラミングコンテスト (ICPC) アジア地区横浜大会にて競プロ人生ではじめて銅メダルをいただきました。

その他にも、伊野研究室で量子回路シミュレータの高速化をしたり、株式会社ALGO ARTISで最適化を学んだりしています。

さて、本題のQookbookの話に移ります。

何ができるの?

物理学の事前知識なしで、競技プログラミングのように問題を解きながら量子情報の知識を身に付けることができます。 左側には問題文やテキストが表示されるスペースが、右側にはソースコードを書き込むためのスペースがあります。 ソースコードを書いたらweb上でそのまま実行しながらデバッグができ、うまく動作しそうであれば提出して採点を受けることができます。

舞台裏になる問題作成ツールなどにも力を入れており、競技プログラミングにおける「インタラクティブ問題」が簡単に書ける仕組みを作成しています。 システム面の補強と並行して、将来的に次のようなコンテンツを追加していきたいと思っています。

なぜ作ろうとしたのか?

量子コンピュータの世界には、競プロerや情報系の方が好きそうな話題がゴロゴロと転がっているのに、別分野のように見えて敷居が高くなかなか参入できないからです。 僕が量子コンピュータの世界に飛び込んだきっかけは、藤井先生のつぶやきでした。

この後に藤井先生の下で、量子回路シミュレータ Qulacs の開発を担当するなど様々な経験をさせていただきました。 特に興味を持ったのはノイズなどで生じた誤りを訂正する量子誤り訂正や、量子プログラムをより単純な制御命令列に変換する量子コンパイラなどの分野でした。 量子誤り訂正については、表面符号と呼ばれる誤り訂正符号について 焼きなまし法で誤り訂正を行うという研究 や、 フェニック木 (BIT) を用いて誤り訂正を高速化するという研究 など、どこかで聞き覚えがあるアルゴリズムを使った研究がされています。

https://qiita.com/SamN/items/c2b6b4c28bae922bc634 より引用。表面符号では青色マスを2つペアにして繋ぐことで誤り訂正を行っています。繋ぎ方によって正しく誤りを訂正できる確率が変わります。

量子コンパイラについては、できるだけ計算資源を有効活用して短時間で計算が終わるように、様々な最適化手法を使ってスケジューリング問題を解くという研究がなされています。 有名な例として、量子回路を格子手術の命令列に落とし込むために、タイルを変形するパズル問題を解くという研究があります。

A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery (https://arxiv.org/abs/1808.02892)のFig.11より引用。 ヒューリスティックコンテストで出てきそうな図です。

このような研究を面白いと思いながら勉強していく中で痛感したのは、学習時点では地に足が付かないような内容が多く、内容の理解がとても難しいということです。 当時から初学者向けの教材は Quantum Native Dojo などネットの教材も含めて沢山ありましたが、難しい部分に行くにつれ自分がどこまで理解しているのかわからなくなっていきました。 理解を深めるために演習問題などを解くわけですが、実はちゃんと理解していないのにスルーしてそのまま進み、後でつまづきに気が付くといったことも頻繁にありました。

それに対して競技プログラミングは、理論の理解度が自己判定しやすいため確実に一歩ずつ進めるという特徴があります。 学びたいトピックに対して大量の演習問題があり、問題を解くプログラムを提出するとその場で採点されて採点結果が返ってきます。 演習問題を解くことまでは書籍でもできるのですが、その後の採点プロセスまでもを自動化することで、人力では不可能な刻み幅で理解度を判定することができています。

この競技プログラミングの特徴を、量子プログラミングの学習にも持ち込めないかと考えてQookbookの開発を始めました。 量子プログラミングもまた一つのプログラミングの系統で、アルゴリズムpythonプログラムなどとして記述されるので、いろいろと頑張れば競技プログラミングの枠組みに落とし込めそうだと考えました。 技術についても、高校生の頃に作った kotamanegi online judge のノウハウや、競技プログラミングなどで培った狂気の実装力を活用すれば1年弱で開発できるだろうと見積もり、未踏ターゲットに応募したところありがたいことに採択されて今に至ります。

最後に

競技プログラミングはコンテストが醍醐味の一つなので、もちろんコンテストをやります! 1/14(日)の13:00-17:00に、スコアを競う短期マラソン形式のコンテストを開催する予定です。

ささやかですが、副賞としてAmazonギフト券も用意しています。

  • 1位: 1万円
  • 2位: 5千円
  • 3位: 3千円
  • 4位〜10位: 1千円

コンテスト中も外部資料の参照はOKなので、もし予定が合えば気軽に参加していただけると嬉しいです。

謝辞

本サービスは、未踏ターゲット事業の支援を受けて開発しています。 未踏ターゲット事業では、担当PMの徳永PM様・鈴木TA様をはじめとして様々な方に助言をいただきました。 助言をいただけなければ、ここまで開発を進めることはできなかったように思います。 ここに深く感謝の意を表します。

ICPC 2023 Yokohama Regional 参加記

2023年11月25-26日に開催されたICPC 2023 Yokohama Regionalにチームkotamanegi_marunageで参加し、10完大学別順位3位・全体4位でした。 メンバーはvwxyzさん・kuhakuさん・kotamanegiで、コーチがolpheさんでした。

1日目 — リハーサル

僕は13時45分ごろに会場に着いて食事を取ったりしていました。

無事(?) 3人+1人で集合できて、受付時間内に会場に入ることができました。 リハーサルについて、Dをバグらせながらも、なんとか無事全問題をACすることができました。 リハーサル後は筑波大のチームGoodBye2023と一緒にサイゼリヤで食事を取っていました。

2日目 — コンテスト本番

チームメンバー(僕含む)は朝が弱いのでギリギリまで会場入りできませんでした。 記憶では9時ちょうど着ぐらいだったと思います。

コンテスト

戦略は、

  • kotamanegi: PCのセットアップとA問題のFA狙い
  • vwxyz: Bがインタラクティブ以外なら担当、そうでなければC問題以降を見る
  • kuhaku: Bがインタラクティブなら担当、そうでなければC問題以降を見る

でした。 結果としてはCを除く全問題ACの10完で、ある程度うまく戦略がはまったのではないかなと思います。

以下は記憶から掘り起こしてきた時系列情報です。

  • 0:00 問題とログイン用パスワードの封筒をうまく破ることに失敗。10秒程度のロス。
  • 0:08 FAは逃したものの、A問題を順当にAC。 vwxyzさんがB問題を書き始める。
  • 0:25 Bのサンプルが合わず、僕が読んですぐ解法が思い浮かんだD問題を実装しはじめる。
  • 0:40 DをAC。kuhakuさんにFを実装してもらい、その間に僕はB問題を考えていた。
  • 0:50 FをAC。僕がB問題を実装することに。
  • 0:58 BをAC。この時に10位前後で、阪大代表としてのプレッシャーが襲ってくる。とりあえず僕がK問題を、他の2人でE問題を解くことに。
  • 1:24 EをAC。僕がK問題を実装して、その間に2人でGとH問題の解法を考えてもらう。
  • 2:16 苦戦しながらKをAC。僕がG問題を読んだら5分ぐらいで解法が思い浮かび、そのまま実装。
  • 2:46 GをAC。H問題がフローということでライブラリ写経したり、解法のバグ直しなどを始める。
  • 3:52 HをAC。上位と比べて1完差があり、厳しい気持ちに。IとJを読み始める。
  • 4:10前後 J問題の解法(解説スライドのAC2)を思いつく。実行時間に関する証明ができていなかったのでvwxyzさんに止められたが、PCが空いているのでとりあえず実装することに。
  • 4:32 JをAC。最後にIに着手して、凸包の天啓が降る。
  • 4:50前後 サンプルが合うが、提出してみるとREで落ちてしまう。細かいところを変えて提出を繰り返す。
  • 4:58 IをAC。ラストスパートということで半分運任せの提出を繰り返しており、ふと採点結果欄を見たらACしていたので喜びを分かち合うよりも通っていた事に呆然となっていた。

5年の振り返り

B1から阪大の選手として5年間出場し続け、とうとう今年最後の年になりました。 最近は阪大内で活発に活動する競プロerが増えてきたのもあり、戦い続けるか悩んでいました。 本業の研究は勿論ですが6月から未踏ターゲットのPJが始動し、さらにAA社のアルバイトも入ったため練習時間を確保する事が困難になるのは明らかでした。 更にコーチを誰にお願いするか等の悩みもあり、「競プロにがっつり向き合う時間もないのだし、かつての先輩方のように後続の支援に回る事が自分の使命になるんだろうな」と思いつつ、選手として燃え尽きたいという気持ちとの板挟みになっていました。

5年間でのYokohama Regionalでの成績は初年度から21位→4位→4位→8位となっていました。そして今回の凍結前の順位は8位だったと思います。 凍結後の1時間でIとJの両方を通すことができたのは、5年間煮詰めた執念によるものだったのかもしれません。

結局全体での順位はまた4位でしたが、大学別では3位だったので初めて表彰台にのぼりメダルを受け取るという経験ができました。 競技終了2分前のブザービートACがなければあり得なかった展開だっただけにその現実を頭が受け入れていなくて挙動不審になっていたし、今となっては非常に恥ずかしいです。 まさか阪大が3位で表彰を受ける未来がくるとは想像できなかったもので…。

もう一つのハイライトとして、今年ついに阪大から3チームYokohama Regionalへの進出を決めることができました。

阪大からの国内予選の通過チーム数は5年間で1チーム→1チーム→2チーム→2チームと、通過チーム数が伸びていき今年ついに3チーム輩出することができました。 これはひとえに選手みなさんの努力と、阪大競プロ部RAINBOUに尽力いただいた方々・ICPCという場を設けてくださった方々・陰で支えてくださった皆様によるものだと思います。交流でもたくさんの方とお話しできて楽しかったです。本当にありがとうございました。





↑物理好きさんごめんね~🤣



宣伝

未踏ターゲットというIPA事業の支援を受けて、競プロライクに楽しく量子コンピュータの利用方法を学べるサービスを開発しています。 競プロ Advent Calendar 2023 - Adventar にも12月13日に寄稿する予定なのでよろしくお願いします。

ICPC2023 国内予選 参加記

2023年7月8日に開催されたICPC2023 国内予選にチームkotamanegi_marunageで参加し、5完14位でした。 メンバーはvwxyzさん・kuhakuさん・kotamanegiで、コーチがolpheさんでした。

コンテスト前

僕は12時に会場入りして、会場設営などを少しお手伝いしていました。 そのあとはリハーサルやプリンタの出力確認、初動の計画をしていました。

コンテスト中

今年の初動は問題文を印刷してから、僕がA問題を早解きするという計画でした。 初動はうまく行き、0:03:32でA問題を通すことができました。 A問題を通した直後、B問題に目を通したところ簡単に実装できそうだったので実装し、少しバグを出しながらも0:22:39にB問題を通しました。

その後は、D問題を僕とvwxyzさんが、C問題をkuhakuさんが解くことになりました。 D問題は解が7以下であることに気が付き、計算量が怖かったもののとりあえず総当たりコードを書くことになりました。 C問題とD問題の双方ともにバグを出してPCを取り合いながらも実装を進め、0:53:06にC問題が、0:58:46にD問題が通り4完でそこそこ良い順位に収まりました。

E問題は時間計算量 O(n^2 log^2 n) 程度のセグ木を用いた解法が思いついたのでそれを実装しつつ、裏でvwxyzさんとkuhakuさんに簡単な解法を考えてもらうことにしました。 実装量が多くバグに手こずっていると、kuhakuさんが簡単な解法を思いついて実装を交代することになりました。 結局バグが取れずに両方ともペナを出し、少し書き直した僕の解法で2:25:28にE問題のACを取ることができました。 この時点で13位程度になり、安心して順位表を眺めていました。 G問題を考察していたんですが、最小費用流に帰着できそうだね、と言ってたらそのまま終了しました。

コンテスト後

阪大から3チーム予選(ほぼ)通過が出たということで、達成感でいっぱいになりました。 コンテスト後半の成績的に阪大から3チーム予選通過しそうだな、という直感こそありましたが、ボーダーをきちんと覚えておらず不安でした。 コンテスト終了直後に順位表のボーダーを再確認し、3チームの予選通過が確定したことを確認できました。

3チーム通過しましたが、僕のチームは結構反省点が多い結果に終わりました。 E問題までの実装スピードが遅かったため、上位の決め手になるFとG問題に時間を割くことが難しく辛い気持ちになっていました。 実装ゲーが出たときに貢献できるよう、アジア地区予選でも頑張ります。

ICPC 2022 アジア地区予選 参加記

2022年12月27~28日に開催されたICPC 2022 Asia Yokohama RegionalにチームTLE_WARLDで参加しました。 メンバーはWA_TLEさん・vwxyzさん・kotamanegi、コーチはBadlyluckyさんです。 最初に結果を書くと、ABDEFGの6完で8位でした。

前日

初日のリハーサルやチーム紹介が予想以上に早く終わり、食事予約などを早めの時間に変更するなどで大忙しでした。 18:30から梅蘭金閣で飲茶セットを食べ、20:00には解散・各自就寝という理想的なスケジュールで動くことができました。 bairan-tougen.jp

コンテスト当日

早く寝たのが功を奏したのか、寝坊はしませんでした。 寝坊に備えて、部屋の鍵が共有できるホテルを選んでいたのですが、共有鍵は使われることなく終わりました。本当に良かったです。

コンテスト直前期

6:30に起床し、7:30ごろから朝食をとりました。 朝食会場には競プロerらしき方々を時々お見受けしました。宣伝の成果ですね(?)

a8pfactory.hatenablog.com

8:30ごろにホテル前で集合し、会場に向かいました。 名前が非常に似ている方とお話をしていたら、いつの間にか競プロerの列が後ろに出来上がっていてびっくりでした。

コンテスト中

コンテスト開始後すぐに、CLionの設定とA問題の確認をしました。 A問題は単純なスケジューリング問題だったので、すんなりとACできました。 実際にスケジュールを出力する必要があったので、ちょっとだけ面倒でした。

vwxyzさんにB問題を任せて、僕はしばらく他の問題を見ることにしました。 WA_TLEさんに問題概要を伝えながら取り組むべき問題を精査していました。

  • C: 難しそう
  • D: おそらく簡単枠、ただの実装
  • E: WA_TLEさんが解けたと主張していたので見なかった
  • F: 幾何、スルー
  • G: 木の制約が気になるが、簡単枠に見えた
  • H: 数学ゲー、スルー
  • I: 組合せ論、ちょっと考えたけど難しい
  • J: 幾何、スルー
  • K: スケジューリング問題、頑張れば解けなくもない実装枠

Bが通ったあと、WA_TLEさんからG問題の解法を教えてもらったので実装しました。 実はこれは嘘解法で、いったんWA_TLEさんにE問題を実装してもらった後、vwxyzさんが正しい解法に書き換えて無事ACできました。

マシンが空いている時間帯を見計らって、D問題を実装しACしました。 最初のsourceパターンを回転する代わりに、目標のtargetパターンを90度回転すればsourceパターンの座標系を変形することなく実装できました。 工夫をすれば実装が簡単にできるという面白い問題でした。

その後は、F問題などとK問題を反復横跳びしていたらコンテストがいつの間にか終了していました。 K問題を通せていれば4位ということで、悲しみでいっぱいです。

コンテスト後

カツサンドやドーナツを食べながら、スポンサーセッションを見学しました。 LegalForce社がLegalOn Technologies社に社名変更していたり、いい生活社のロゴが変わっていたりと、3年前のICPC2019からの時の流れを感じて懐かしい気持ちになりました。

解説を聞いた後は、交流を楽しんでいました。 企業の方からICPC初参加の方まで、様々なバックグラウンドの方がいらっしゃり大変楽しめました。

感想

久しぶりのICPCオンサイトということもあり、少し懐かしさを感じる場面が多かったです。 僕が3年前にオンサイトに初出場した後は、コロナ禍の影響でオンライン開催が続いていました。 今回こうしてオンサイトとして現地で集まれたのは運営とスポンサーの方のおかげだと思っています。 本当にありがとうございました。

天下一 Game Battle Contest 2021 Autumn 参加記

概要

天下一 Game Battle Contest 2021 Autumnにkotamanegiとして参加し、優勝しました。 前回の天下一 Game Battle Contest 2021 Springと合わせて2連覇を達成しました。 f:id:kotamanegi:20210923231731p:plain

ソースコードgithub.com にあります。

ラクティスセッション

時間がなく参加出来なかったのでぶっつけ本番になりちょっと不安でした。

コンテスト前半戦

まず問題文などを読みに行くと、今回はproduction環境とstaging環境が用意されておりstaging環境でテストが出来るということが判明しました。 このためproduction環境用とstaging環境用にプログラムをそれぞれ別々のコマンドで起動できるようサンプルやMakefileを改造しました。

その後はとりあえずサンプルプログラムを稼働させてスコアが出ることを確認しました。 次に各ゲームエージェントから最も近い資源を選んで向かうようにするとスコアが少し上がりましたが、この頃physics0523(@butsurizuki)さんがスコアをメキメキと上げていて周りが3桁台の時にすでに2000点に乗っており内心かなり焦りました。

突破口を探るべく実験していたところ、資源が出現する前に出待ちをするとスコアが大きく向上し1位に躍り出ました。

コンテスト後半戦

1位にはなったものの後ろから追われていたので、人が集まってきた段階で資源が消滅するより前に次の資源に移動するという処理を追加すると更にスコアが上がりました。 開始2.5時間もすると改善点が見つからなくなり、どの資源を優先的に取るかなどの細かい部分のパラメータチューニングをしていたらコンテストが終わりました。

感想

1位になってからは早く終わってくれと祈りながらビジュアライザを眺めづつポチポチ手動でパラメータを変えていました。 後続の追い上げが厳しかったので他人の失敗を喜ぶ悪い子になっていました。ごめんなさい。

次回も対戦よろしくおねがいします。

ISUCON11本選 kotamanegiの参加記

概要

ISUCON11本選にチームkotamanegiとして一人で参加し、学生2位になりました。 主要な改善点・工夫は

  • 自動デプロイスクリプトを書く
  • DBのindexをきちんと構築する
  • 負荷が大きくなってきた場合の強制タイムアウト処理を実装する
  • DBとZipファイルの処理を行うサーバとそれ以外の処理を行うサーバに3台のマシンを分離させる。

の4点でした。 結果は全体11位/学生2位となり、賞金10万円+Splunk賞とYahoo賞の2つの企業賞を獲得できました。 Splunk賞は全体11位、Yahoo賞はスコア下4桁が8200に最も近い学生チームが受賞ということで2つも受賞できてラッキーでした。

開戦前

チーム紹介など

f:id:kotamanegi:20210920114156j:plain

この時は賞金を取れると予想していなかったので期待に答えられなくてスマンやで〜と思っていました。 ですが優勝こそ逃したものの賞金は獲得できたので有言実行に近い結果を残せました。

僕は期待を裏切らない男です。(イキリ)

事前準備

複数台与えられた時のシステム構成を考えていました。 DB1台+Web2台で、Web2台間はnginxでいい感じに振り分けるつもりでした。

作業のタイムライン

作業メモをとっていないので順序は適当です。

前半戦

まずベンチマークをとった後、サーバにログインしようとするとエラーが出て質問を投げました。ISUCONポータルへの再ログインやGitHubへの新規SSH鍵の登録などをしていると治ったのですが、原因は謎です。

ログイン出来るようになった後は、初手でDBサーバを分離しました。 mysqlでroot権限でログインするためにsudo mysqlが必要だったのはしばらく困りましたが、基本的には予選と同じ流れでうまく行きました。

分離後、この段階でようやく当日マニュアルを読みはじめました。 学内システムの高速化というテーマだったので、成績確認よりもまずは提出物確認・アナウンスの確認を高速化した方がよいのかなぁと感じました。

提出物がzipで管理されていたので、ディスクIOを分離するために提出物確認APIを別サーバに分離するとジャッジ中の点数は上がりましたが途中で整合性が取れずにFailするようになってしまいました。

後半戦

サーバの負荷をtopコマンドで確認すると、DBサーバのCPU使用率がMAXのまましばらく停滞していることに気が付きました。とりあえずIndexを張ってみると途中でFailすることはなくなったものの、最後の整合性チェックでは相変わらずFailのままでした。

成績確認に関連するAPIがエラーを出していたので確認するとどうやらリクエスタイムアウト後も処理が続行されてDBサーバに負荷を掛け続けているらしいということがわかりました。 そこで同時実行数の設定値以上の数のリクエストが来たらtime.sleep(inf)を実行し強制的にタイムアウトにするという仕組みを実装しようと考えました。 さすがにこの解き方は想定外ではないかと思って質問を投げるとルール上OKとの返事が返ってきたので安心して実装できました。 この改善策を入れるとFailすることはなくなりました。

最後に細かい改善を入れたり、アナウンス用のDBサーバを別途用意しようとして失敗したりしている内に時間切れになりました。 アナウンス用のDBサーバを立てるのは想定解法だったらしいので悲しいです。

分析

成績確認用のAPIが原因でFailしがちだったのでそこを修繕出来て良かったと思っています。 Redisへの載せ替えなどは考えたのですが、再起動試験でFailしそうだと予想して予めインストールされていたソフトウェアだけを使ったのが結果として良かったと感じました。

アナウンス用のDBを別途用意するのは途中まで実装していたのですが、外部キー制約に引っかかってしまい解消することが出来ませんでした。外部キー制約そのものは外すと本選終了後のテストでコードレビューされてFailするのかなと考えていたので、まさか外しても良いものだとは思ってもいませんでした。外してよいかを質問でちゃんと確認しなかったのは反省点です。

Discordの感想戦

「推測するな、計測せよ」という標語がDiscordのあちこちで飛び交っていて、ほぼ推測のみの野生の勘と運だけで乗り切れてしまったとは言える雰囲気でなく心の中で懺悔していました。 結局会話の中でそれがバレてしまったんですが、「よくそんな丸腰でここまで来れたな」と言われてしまい、自分の運の強さを再認識した感じです。

来年は今年より成長している予定なので計測ツールを持っていこうと思います。

感想

ISUCON初参加初本選初優勝は果たせませんでしたが、初参加初本選初入賞は果たせたので大満足です。賞金10万円は欲望の赴くままに使わせていただこうと思います。

ISUCON11予選 kotamanegiの参加記

概要

ISUCON11予選にチームkotamanegiとして一人で参加し、学生枠で本選に出場できることになりました。 主要な改善点・工夫は

  • DBのindexをきちんと構築する
  • SQLのうちLIMIT句が効きそうなところに追加する
  • 自動デプロイスクリプトを書く
  • POST /api/condition/:jia_isu_uuid に対する実装の、確率でリクエストを破棄する処理を削除

の4点でした。 結果は全体40位/学生4位となり初参加でしたが本選に出場できるほどの好成績を残せました。

開戦前

チーム編成について

初参加なので他人に迷惑をかけたくないという気持ち & 本選に行けると思っていなかったのがあって今回は1人で参加しました。 今年のISUCONに参加してみて、僕の実力で戦えそうな雰囲気だったので来年はぜひチームで出てみたいです。

事前準備

複数台与えられた時のシステム構成だけを考えていました。 DB1台+Web2台で、Web2台間はnginxでいい感じに振り分けるつもりでした。

作業のタイムライン

メモを取っていないため時系列は適当になっています。

開戦 ~ 3時間経過地点まで

  • 0:00 当日マニュアルが開かなくて焦る。 とりあえずAWS Cloud Formationにダウンロードしてきた設定ファイルを投げて環境構築してもらう。
  • 0:05 当日マニュアルが開けるようになる。 初回のベンチマークを実行する。
  • 0:30 scpでファイルの転送が出来るようになる。 ホームディレクトリの内容を全て(!)ダウンロードする。
  • 0:40 ダウンロードしてリポジトリにpushしようとしたが、~/localディレクトリが異常に大きいことに気づく
  • 1:30 ~/localディレクトリのGoコードは外部ライブラリであることに気づく
  • 2:00 各サーバに置いてあるレポジトリについて自動でgit pullするデプロイスクリプトを書く
  • 2:30 ~/webapp/go内のコードを読んでいる最中に、ポータルの質問コーナーを見てアプリケーションマニュアルの存在に気づく
  • 3:00 Goコードを書き換えて実行ファイルを送り込むが、変更が反映されなかった

3時間 ~ 5時間経過地点まで

  • 3:05 ps -axでプロセスを見てみると~/webapp/go/isuconditionを実行しているプロセスを発見する
  • 3:30 サービス名がisucondition.goであることを突き止める
  • 4:00 デプロイスクリプトを書いて改造Goサーバが動作することを確認
  • 4:05 topコマンドでMySQLサーバがボトルネックになっていることを発見、別サーバに分離する作業を始める
  • 5:00 別サーバに分離が完了、ついでにPOST /api/condition/:jia_isu_uuid も分離

5時間経過 ~ 最後まで

  • 5:05 DBにindexを張る作業を始める
  • 5:30 EXPLAINを付けてSELECT文を実行してもindexが使われず、原因究明を始める
  • 5:40 DB系ファイルの転送を忘れていたことが発覚しデプロイスクリプトを修正
  • 6:00 ボトルネックが解消しMySQLサーバのCPU使用率が130%前後に落ち着く、この時スコアが3.5万程度になる
  • 6:30 POST /api/condition/:jia_isu_uuid に対する実装の、確率でリクエストを破棄する処理を削除
  • 7:00 MySQLサーバのCPU使用率が200%に再び戻る、スコアが変化しないことから他のエンドポイントの改善を始める
  • 7:10 SQLにLIMIT句を付ける作業を行い、ベンチマーク実行
  • 7:15 ポータルに障害発生しアクセスできなくなったが、一瞬7万点までスコアが上昇したことが確認できた
  • 7:16 DBを見ているとisu_conditionだけがカラム数80万に達しておりここがボトルネックと判断
  • 8:15まで 障害が発生している間にPOST /api/condition/:jia_isu_uuid をバッチ処理に切り替える実装を書いていた
  • 8:15 競技再開、ベンチマークを実行するが点数が変化せず困惑する
  • 8:30 サーバ側のgitレポジトリ内の内容を操作した結果pullが正常に行えず変更が反映されていないことを確認し、再度ベンチマークを実行
  • 8:32 スコアが1000になりPOST /api/condition/:jia_isu_uuid が動いてないことがわかる
  • 8:35 変更をrevertして元の7万点コードに戻す、何回か実行していると7.5万点までは上がった
  • 8:45 コンテスト終了

分析

自動デプロイスクリプトを初手で書いたのは後半の作業効率の向上にとても効いたと思っています。 万が一環境を破壊したとしてもすぐに環境再構築が出来るというのは精神的にもメリットが大きかったです。 再起動スクリプトも仕組んでいたので再起動試験にも安心して対応できました。

DB的な面では、EXPLAIN句を知っていたおかげでindexが使われていないという致命的なミスを発見できたのが嬉しかったです。 知らなかったらスコアが低いままだったのを考えるとEXPLAIN句は重要な役割を果たしてくれました。

アプリケーション的な改善は後回しにしていたらほぼ改変する暇がなくなってしまいました。 DBの改修で手一杯になっていたのでサーバ構築の事前準備をしていたら時間が取れたのかもと後悔しています。

感想

インフラ系の環境構築コンテストは初めてだったのですが、高速化の様子がうまく可視化されていて楽しかったです。 本選はもうちょっと対策して賞金を狙っていきたいと思います(強欲)