ISUCON10の予選を4位で通過しました

Satoshi Tajima
Sep 14, 2020 · 18 min read

こんにちは、Finatextでエンジニアをしている @s_tajima です。
先日行われたISUCON10の予選に、Finatextのエンジニア陣 @s_tajima / 石橋 @atsushi-ishibashi / @yami20 で参加しました。
チーム名は 一口坂46 です。オフィスの前の坂の名前です。

結果として、予選を4位で通過することができました!
私達のチームがどんな戦略でどんなことをやっていたかのブログです。
尚、このブログはチームメンバー3人での共著です。

リポジトリ

https://github.com/s-tajima/isucon10q-hz46-app

事前準備

他にもやっていた準備はあるのですが、特に役立ったものを3つほど紹介します。

事前練習用のEC2、当日のログアップロード用のS3バケット(後述) 等を作成するためのAWSアカウントを用意しました。
これは個人のAWSアカウントを使っているのですが、Organizationを使って今回のISUCON専用に作成しています。
これによって、チームメンバーに気軽にAdministrator権限のIAMを渡せるようになります。

チューニングを行う上で、ログからの情報分析はとても重要です。
アプリケーションのログ、Nginxのアクセスログ、MySQLのSlow Query Log等、様々な種類のログを出力することになります。

特に何も管理せず、ログを出しっぱなしにしてしまうとディスクが溢れる、複数回のベンチマーク分のログが混在してしまい分析がしにくいという問題があります。
一方で、ベンチマークのたびにログを削除してしまうと過去のベンチマークの情報の分析ができなくなってしまいます。

そこで、前述のAWS環境にS3バケットを用意して、ベンチマークのたびに主要なログをS3に退避 → サーバー上からは削除 というのができるようにしていました。

また、その作業を簡単にするために、必要なすべてのログを /var/log/isucon/ 下にまとめておく設定をしました。
更に、チームメンバー間で共有を低コストできるように、S3へのアップロードが完了したら、SlackにURLを通知する仕組みにもしてありました。

ベンチマーク実行時、サーバーのキャッシュやプロセスの状態によってスコアがぶれてしまわないように、ベンチマークの準備を整えるコマンドを用意しておきました。
具体的には $ make prepare を実行すると以下のような操作が一発で実行されます。

  • alp, pt-query-digestの実行し、この結果も /var/log/isucon に保存
  • S3へのログのアップロード & サーバー上からの削除 & Slackに通知 (前述の通り)
  • アプリケーションのgit pull
  • Goのアプリケーションのビルド
  • 各種ミドルウェアの設定の展開
  • # sync; sync; sync;
  • # echo 3 > /proc/sys/vm/drop_caches"
  • # sysctl -p
  • # systemctl daemon-reload
  • 各種ミドルウェア・アプリケーションの再起動

これはかなり有効にワークしました。
若干の反省点としては、スコアが上がってきてログの量が増えてくると、alpやpt-query-digestの実行時間もどんどん伸びて無視できなくなってくるので、競技用サーバー上ではログの分析をせず、別サーバーを使えるようにしておくという方向性もありかもなと思いました。

当日の体制

想定としては、大まかにこんな役割分担を考えていました。

@atsushi-ishibashi … Goのアプリケーションレイヤーのチューニング
@yami20 … データベース・クエリ周りのチューニング
@s_tajima … 主に競技用サーバーで作業し、OS/ミドルウェアのレイヤーの管理、ボトルネックの調査等

実際のところ、ここまできれいな分担にならなかった面もあるのですが、全員が同程度のスコアへの貢献をするというバランスがとれた感じだったと思います。
あと、ある1つの施策について、「2人でそれぞれ別のアプローチで解決を試み、先にいいかんじで動くようになったものを取り込む。」みたいな進め方ができたのでわりと手堅く進められた感じがします。

当日の流れ

  • 過去のISUCONで当日マニュアルを読み飛ばしたために痛い思いをしたことがあるので、今回は全員でしっかりと時間をとって熟読した。
  • スコアに結びつかないbotからのリクエストを弾くという概念が存在することを把握。
  • ~isucon/isuumo ディレクトリで $ git init し、予め作成しておいたリポジトリにPUSH。
  • $ make check で CPU/メモリ/DISK などのハードウェアスペックや、プロセスやLISTENの状況、systemdのunit-filesの状況等を一発で出力できるようにしていたので、ここから環境の大枠を把握。
  • AppArmorが有効なままだと、次のステップのログのPATH調整等が失敗してしまうのであらかじめDisableにしておく。
  • オペレーション的には3台とも同様なのでIterm2のBroadcast Inputで3台まとめて実行することも考えたが、再起動しなくなったら辛いので、おとなしく003から1台ずつ実行した。
  • ある程度のパフォーマンスの調整と、ログのPATHを調整したNginx/MySQLの設定を展開。
  • 前述の通りログはすべて /var/log/isucon/ の下に集めるようにした。
  • また、このタイミングで limits.conf / sysctl.conf あたりもいじってチューニングが進むとでてくるであろうToo many open filesやTIME_WAITの滞留を防ぐようにしておきました。 (というつもりだったけど今改めてみたら手違いでsysctl.confが修正できてなかった.. 確認不足…)
  • この状態で初回のベンチマークを実行。
  • 事前に打ち合わせていた通り、アプリケーションには初手でNew Relicを導入。
  • オーバーヘッドによるものか若干スコアが下がるが想定内。
  • PR自体は13:44にマージしているがベンチマーカーが利用可能になるまで待機してから実行。
  • 当日マニュアルの正規表現をNginxのconfに移すのが面倒だった。
  • 書き換え → configtest → curlで動作確認 を愚直に繰り返してなんとか動くところまで持っていった。
  • Nginxのドキュメントを見ていて、 nginx-regex-tester なるものが存在することがわかったので最終手段はこれを使うことも想定したが、今回はこれなしで済ませることができた。
  • chairの購入時には在庫があるかどうかを確認してなければsold out(404)として返す仕様のため、参照実装では以下のようにロックを取ってからUPDATEを行うという実装であった。
SELECT * FROM chair WHERE id = ? AND stock > 0 FOR UPDATE
UPDATE chair SET stock = stock - 1 WHERE id = ?
  • これをUPDATEのWHEREに在庫条件を入れることでロックせずに一本のクエリでchairの購入リクエストを処理できるようになった。
  • アクセスログをalpで集計してみると、GET /api/estate/search が重そうなことがわかる。
  • grep等でもう少し詳細にアクセスログを集計してみると、GET /api/estate/search のGETパラメータはある程度偏りがあるみたいだったのでキャッシュをすることに。
  • 最初はGoのアプリケーション側でやろうとしたが、Nginxでもいけそうだと気づいてNginx側で実装。
  • GET /api/chair/search もキャッシュしてみたがこちらはFailしてしまったので切り戻し。
  • なぞって検索を改善するために、空間インデックスを効かせるためのALTER TABLEを実施。
  • Explainしてもインデックスが効いているように見えないのが懸念点ではあったがとりあえずベンチマークを実施。
  • 案の定スコアは上がらず。
  • 1度のリクエストで何度も実行されうるなぞって検索のクエリを、1つ前のGEOMETRYカラムも活かしつつ1つにまとめた。
  • これは結構効いてスコアが上昇。
  • なぞって検索周りについてはどんな風にチューニングを進めたかもう少し詳しく解説します。
  • 実は初期の頃にchairとestateのメモリキャッシュを仕込んでいた。
  • estateはUPDATEがないため問題なく機能できたが、GET /api/chair/:id では在庫数も加味してレスポンスを決めるためchairのメモリキャッシュは使えていなかった。
  • GET /api/recommended_estate/:id ではchairのサイズ感だけが必要だったため、ここのみメモリキャッシュを使うように修正した。
  • 裏で002にElasticsearchを、003にMySQL8.0をインストールして使えるようにしておくという作業をしていた。
  • このタイミングで複数台構成への展開を開始し、データベースを003のMySQL8.0に。
  • estateとchairのCSV入稿が1レコードごとにDBへ処理されていることは初期時点で気づいたが、タイムアウトになると失格なだけでスコアの増減には影響がないため、その時点では手をつけなかった。
  • Indexの追加やGeneratedColumnの設定によりestateの方のみでタイムアウトが発生し始めたため、POST /api/estate のみをBulk Insertの実装に変更した。
  • データベースの値・コードからWHEREにrentを入れられそうなことに気づいてクエリを修正。
  • stateをrentが小さいものを20件返すという仕様だった。これだとrentにindexが貼っていたとしてもフルインデックススキャンになっていた。
  • estateのデータとしては初期データと POST /api/estate の追加のみでrentにUPDATEがかかることはなかった。
  • そう考えるとPOSTで新たに20位以内に食い込んでくるestateがあったとしても、初期データの20位のrentの値を最大値として抑えても問題がないため、rentにwhereをかけることができ、explainのtype.rangeにすることができた。(実際にdummyの20位は30102だったが、雰囲気で35000にしておいた笑)
  • (ただ実際のところrent ASCでindex効いてるなら下手にwhereした方がダメそうな気もする 。)

クエリの変更内容は以下のようなかたち

前)
SELECT * FROM estate ORDER BY rent ASC, id ASC LIMIT 20
後)
SELECT * FROM estate WHERE rent < 35000 ORDER BY rent ASC, id ASC LIMIT 20
  • 空間インデックスを適切に効かせるためにはMyISAMへの変更が必要そうということがわかった。
  • トランザクションの関係など、InnoDBでないとだめな要因がなさそうなことを確認し、CREATE TABLEを修正。
  • 結果的にベンチマークのエラーもなくスコアが上昇。
  • コネクションが10で制限されているのと、コネクションプールが有効化できていないことに気づいて対処。
  • オーバーヘッドになるものを外していこうということでNew RelicとEchoのDebugログを無効にした。
  • これが思いのほかスコアが伸びる要因になってびびった。
  • このタイミングで何度かベンチマークをまわしていて、4369 というスコアが出たのが今回の最高スコアだった。
  • このタイミングまでに何度かトライして失敗していたがついに動くように
  • ひたすらベンチマークをかけてベンチマークの安定性を確認。
  • 何度かに一度エラーになってしまうことがわかったが原因がよくわからないのでこれが追試で発動しないことを祈る。
  • また、Nginxのキャッシュの影響でベンチマークを短時間で2回連続で実行するとFailしてしまうというのがわかったのでTTLを調整。(本当は POST /initialize でキャッシュをパージする設定を入れたかったがサクッとできず断念。)

頑張ったポイント

やりたいこととしては以下の2つだった。

  • SELECT COUNT(*)のクエリを消す
  • 条件SELECTのクエリの改善

Elasticsearchへの移行

最初にコードを読んだ時点でElasticsearchへの移行を選択肢には入れておこうとチーム内ではコンセンサスを取っていた。細かくできることはやった段階あたりで移行に単独チャレンジすることとなった。この際に複数人で試行してみるという選択肢を取らなかったのは結果的に正解であった。というのも2時間弱くらいのチャレンジの後に断念することとなった。実装そのものとしては、Elasticsearchの経験不足により不具合はあるものの見込みは立っていたが、chairの初期データ30000件を POST /initialize の制限時間内に投入できないことの障壁が高すぎた。

アプリ上でソート

クエリの改善はちょっと諦めてLIMIT OFFSET無しの条件SELECTでchairをアプリ上でORDERしてLIMIT OFFSETの計算も行うことでSELECT COUNT(*)をなくし、(こっちは正しく計測はできてないが)filesortをDB側でやらないようにしてDBの負荷を下げることもできた。

ただ後ほど振り返ってみるとchairにあまりIndex貼ってなかったので、Index側で見直しても良かったのかもしれない。ここはfilesortを見たときに、アプリでやるか、Indexを確認するか、の2つの選択肢が浮かぶべきだった。一方でIndex増やすとCSV入稿のタイムアウト問題にchair側でも直面していた可能性はある。

APIのレスポンス的にもSlow Query的にも、そしてパッと見でもなぞって検索(このクエリ)が不穏で対策すべきだということは比較的序盤であたりが付いた。
とはいえ明らかに一般的なチューニングができるクエリではなく沼る可能性も高かったので、 @atsushi-ishibashi と相談して深追いするのは他の対応が終わってからにしようとジャッジ。

SELECT * FROM estate WHERE id = 14136 AND ST_Contains(ST_PolygonFromText('POLYGON((35.994612 137.816159,36.114427 137.812818,36.372260 138.050179,36.521118 138.229454,36.331307 138.516116,36.191508 138.514219,36.071036 138.341045,35.999367 138.054190,35.994612 137.816159))'), ST_GeomFromText('POINT(36.005700 138.261863)'))\G

かんたんに実施可能なindex適用やアプリケーション側での対応が一段落した16:30ころから「なにか抜本的な対策入れないと勝てないよね」という空気になり上記クエリのチューニングに着手。

クエリの見通しが悪すぎるので、いきなり全体最適を求めるよりも地道に潰していくべきだと判断。

ST_GeomFromText(‘POINT(? ?)’) については利用している引数が同レコード内にある緯度経度だけなのが特徴的だった。
initializeはここまでほとんど手をいれておらず時間に余裕があったのでStoredなGeneratedColumnで登録時に負荷を寄せるのが良さそうだなと判断。(Elasticsearch用の初期データ追加と併用すると厳しそうだったがそちらは断念していたのでこの手が可能に。)
ちなみにST_GeomFromText と POINT がどれくらいの計算リソースを使っているのかは知らなかった。
そしてこの対応のためにGeomFromを調べていてSPATIAL INDEXの存在を認識する。効果の程は分からないが、このユースケースならば必要になる局面あるでしょ…と半ば願望混じりにindexを追加。

ST_Contains(ST_PolygonFromText(‘POLYGON(…)’)の引数はリクエスト由来であるため同様の対応はできそうにないと判断。

ポリゴンの算出や内外判定をSQLでやらずにアプリ側に寄せればMySQLの負荷は逃がせるかもしれないと思ったが
→MySQLのエンジン以上の性能を自力実装できる可能性は如何程か?
→アプリ側でより酷いボトルネックを産んだり、安定性を損なう恐れはないか?
→てか自分の実装スピードで間に合う??沼じゃない??

あたりから超ハイリスクローリターンであると判断し、手を加えないことにした。

ここまでやってクエリの全体像をようやく正確に理解し、クエリ自体は長大だが普通に直前のクエリからのN+1を回避できることを認識してwhere句を統合。

  • 競技中にはチームメンバーに GenCol 化でmergeできたっぽい説明をしてしまったが、見通しと計算量がダメなだけで元の状態でマージすることもできたな…

最後に(後から気づいたが)SPATIAL INDEXはMyISAMでのみ有効なので、estateにクリティカルな状態管理がないことを確認した上でMyISAM化して無事高速・省エネ化に成功。(ただ実はSRIDを指定することでInnoDBのままでもINDEX効かせられたという情報を確認しました。未検証。)

本選に向けて

以前、僕 (@s_tajima) と、@yami20 と他のメンバーでISUCON予選に参加した際、スコア的には予選突破だったものの、追試でFailして失格になるという経験をしていたこともあり、今回も結果発表されるまで気が気じゃない感じでした。が、結果的に4位通過という嬉しい結果となりました!

毎年のことながら、このクオリティで、この規模の参加者に問題を提供する運用、作問の担当の方々には本当に頭が下がります。
本選もとても楽しみにしています!!

Finatext

THE Finatext Tech Blog

Finatext

THE Finatext Tech Blog

Satoshi Tajima

Written by

Finatext

THE Finatext Tech Blog