nomeaning blog.

ISUCON 14 参加記

12/08に開催されたISUCON 14に@icchy、@whywaitaとのチーム『第9西東京市』で参加し、総合2位を獲得しました。 ISUCON 8本戦以来となる上位入賞を果たすことができ、感無量です。

タイムライン

image.png

10時～12時 (DBの分離とインデックスの設定) 900pt → 5000pt

初動としては、whywaitaさんにAWSの初期設定やMySQLのスロークエリやKataribeの設定をしてもらいつつ、わたしとicchyはコンテストのマニュアルの読み込みを行なった。その後、わたしはクエリを読んでのINDEXの設定と今後のクエリ変更を楽にするために SELECT * をカラム名を明示する形で書き変える変更を行ないました。

早い段階でMySQLの負荷が大きな問題になりそうなことが分かったために、MySQLを独立したサーバーに移動する作業をwhywaitaさんが担当してくれたのですが、これがなかなか厄介でした。そのサーバーで動いていたマッチングを停止しなかったため、アプリサーバーとDBサーバーの両方でマッチング処理が実行され、競合が発生してしまったのです。その結果、ベンチマークを通過できなくなってしまいました。また、並行してSQLの改善作業も行っていたため、そちらが原因だと誤解し、原因特定に30分以上かかってしまいました。

これに気づいた後はDBの分離の効果と、INDEXを設定した効果で約5000点程度出るようになりました。

12時～14時 (DBクエリの改善) 5000pt → 7500pt

ここからwhywaitaさんがマッチング機能の改善、icchyさんが通知関連のSSE化、そしてわたしがその他のDBクエリの細かな改善を担当する形で分担して進めました。

DBクエリの改善においては、まずchair_locations周りに以下の変更を加えた結果、スコアが約7500pt程度まで向上しました：

  • 椅子の移動距離の最適化

    chair_locationsテーブルで計算されていた椅子の移動距離をchairsテーブルに移動し、逐次更新するよう変更。

  • 最終位置のキャッシュ化とテーブルの削減

    chair_locationsテーブルでは最終位置しか利用していなかったため、その情報をchairsテーブルに書き込む形に変更し、chair_locationsテーブルを削除。

14時～15時 (距離順の一括マッチング) 7500pt → 20000pt

whywaitaさんが進めていたマッチングの改善が一旦の完成を見せました。

具体的には、rideを距離が長い順に、椅子を速い順に並び替えた上で、rideに対して最も近い椅子をマッチングするという貪欲法を採用しました。この方法により、ランダムなマッチングと比較してはるかに合理的な結果が得られるようになり、スコアが大きく伸びて20000ptを超えることができました。

15時～17時 (1+Nの除去とマッチングの洗練) 20000pt → 30000pt

DBやクエリ関連の改善として、以下の取り組みを実施しました：

  • MySQLの更新

    自家製ビルド版のMySQLにアップデート。

  • ride_statusesの最新情報の追加

    最新の1件を取得することが多いride_statusesの情報をrideテーブルに追加し、効率化を図りました。

  • nearByChairsの1+N問題の解消

    クエリの改修により、1+N問題を除去。

  • 運賃計算結果のキャッシュ化

    運賃計算結果が後から変わることがないため、chairテーブルに結果を保存するよう変更。これにより、appGetRidesの1+N問題を解消しました。

また、whywaitaさんがマッチングアルゴリズムの改善を進め、移動距離と速度、すなわち所要時間を考慮した貪欲法を導入しました。

これらの改善を積み重ねることでスコアが細かく向上し、最終的に30000ptに到達しました。

17時～18時 (30000pt→55000pt)

icchyさんがSSEの投入を試みましたが、椅子がライドの完了通知を受け取る前に、別の新しいライドの通知を受け取りました (CODE=15) というエラーに悩まされ、デバッグが難航しました。

そのコードを読んでいる際に、通知系のRetryAfterMsパラメータを特に調整していないことを思い出し、試しに値を変更してスコアの変化を確認することにしました。

通知の間隔を20ms → 40ms → 80msと徐々に増やしていくと、スコアはそれに応じて36000pt、44000ptと大きく伸びていき、最終的に400msでは55000ptまで到達することができました。

一方で、この段階になるとSSE未投入のコードでも椅子がライドの完了通知を受け取る前に、別の新しいライドの通知を受け取りました (CODE=15)が発生するようになり、原因究明は最後まで終わりませんでした。ただし、発生確率が十分低い状態で安定していたため、最終形として受け入れました。

その後は「ポケットサイン賞」を狙い、スコアが2つの素数の積になるまでベンチマークガチャを回して終了を迎えました。

感想

今回の問題は、適切な規模感で構成されており、高得点を狙うためにはシナリオをしっかり考える必要があるという、非常によくできた内容でした。そのおかげで、最後まで楽しむことができました。また、インフラ面でも、毎回恒例だったベンチマーカーのキュー待ちが一切なく、最初から最後まで安定して動作しており、過去最高に快適な環境でした。

今回のチームでの参加は9回目となりますが、その経験が活きて、チーム内での連携や分担はある程度うまくいったのではないかと思います。