Zenn
🪑

ISUCON14 参加記(最終28,148点、入賞)

2024/12/14に公開
ISUCON
tech

はじめに

ISUCONとは、与えられたサーバアプリケーションの高速化を目指して競う競技です。
3人1チームで参加でき、毎年開催されています。上位入賞者には賞金もあります。

競技は8時間かけて行われ、その間に各チームが各々の方法で与えられたアプリケーションを高速化します。
計測は独自のベンチマーカーが行い、アプリケーションに大量の負荷をかけてスコアが算出されます。

改善するアプリケーションや詳細なレギュレーションは競技開始と同時に公開されるため、
当日にいかに素早いフットワークで動けるかが勝負になっています。

メンバー

チーム「うどんきれいなGo」で参加しました。
ISUCON8から毎年同じメンバーで参加しています。

takutaka1220: インフラが得意、主にインフラ担当
iceman5499(私): iOS が得意、主にアプリケーション担当
yush1ga: 機械学習/データエンジニアリングが得意、主にアプリケーション担当

3人がそれなりに触れる最大公約数な言語としてGoを使用しています。

出題内容

今回の課題アプリケーションを簡単に説明すると、タクシー配車アプリのようなものでした。
ユーザとイス（タクシー）が座標空間上にランダムに点在し、空いてるイスを待機中のユーザにマッチングさせて配イスする、というサービスです。

ユーザは初乗り運賃と距離運賃を支払い、この売り上げを最大化させるというミッションです。
初期状態ではサービスが重くて利用しづらく、マッチングロジックも貧弱で待ち時間も長いです。

イスにはそれぞれ速度のパラメータがあったり、サービスが展開されている地域が2つあり、移動は全てそれぞれの地域内で完結しているなどといった味付けもあります。

事前準備

今年はCPUプロファイルにGrafana Pyroscopeを使うことにしました。
簡単に導入できる上にブラウザで結果を確認しやすく、また3人で利用する場合は無料利用枠に収まっていてちょうどよかったです。

デプロイツール郡は去年作成したものを使い回す形にしました。
mitamaeと軽いシェルスクリプトを使って3台の各サーバを自動でセットアップ・デプロイします。
（このへんは去年に引き続きtakutaka1220がやってくれました）

作業内容

自分がした変更を中心に書きます。大きめのトピックは他のメンバーがやった部分も書いていますが、細かい部分は把握してないので割愛。

paymentGatewayURLのキャッシュ

ベンチマーク開始時に値を渡されて、それ以降不変であるためキャッシュ可能でした。
あとでAppを2台に分けることも考えて渡された値はDBに書き込みつつ、一度読み取って以降は使い回す形式にしました。

あとあと、この変更のせいでベンチを2回回すと落ちるという問題に遭遇してしまいました。
初期化時にキャッシュを消してなかったせいだったので、initializeの時点でキャッシュクリアするようにしました。

テーブルにインデックスを貼る

スロークエリやコード内で使用されているSELECTなどを見て、必要そうなテーブルにインデックスを貼っていきます。

chair_locationsテーブルをいい感じにする

chair_locationsテーブルにはイスの全ての移動履歴が記録されていました。
これを利用するエンドポイントにおいて、SQLのLAG関数を用いて過去分全ての移動距離を計算しており、重いエンドポイントとなっていました。
移動履歴はそれ以外に利用用途がなく、単にイスごとの現在位置と合計移動距離さえあれば十分な状況でした。

この無駄をなくすために、chair_locationsテーブルを改修して現在位置と合計移動距離を管理する方針にしました。
対象テーブルは常にINSERTされるテーブルでしたが、これをUPSERTするクエリに変更しました。
また初期データも存在していたため、それを集計して新しい構造の初期データとして再構成する必要がありました。
なかなか手間がかかる作業ですが、TablePlusでポチポチやって頑張りました。

ここで、どう修正を加えてもエラーが起きてしまうという問題に遭遇しました。
クエリのミスやGoの構造体の定義のtypoなどを疑って調査しましたが原因が見つからず、いよいよprintfデバッグを始めたものの文字がprintされず混乱しました。
最終的な原因は「デプロイスクリプトが誤っていて、Appをデプロイできていなかった」というオチでした😇
今まで修正を加えて点が伸びていたつもりになっていた部分は、全てDBのインデックス修正のみで加点されていたようでした。

他に、計算結果が合わないというバグにも遭遇しました。
以下が実際に記述していたUPSERTのクエリなのですが、

間違ったクエリ
INSERT INTO chair_locations (chair_id, latitude, longitude, total)
VALUES (?, ?, ?, ?)
ON DUPLICATE KEY UPDATE
	latitude = VALUES(latitude),
	longitude = VALUES(longitude),
	total = total + ABS(latitude - VALUES(latitude)) + ABS(longitude - VALUES(longitude))
;

上記のクエリはtotalの値が常に0（初期値から変化しない）になってしまいます。
原因はtotalに代入するすぐ上の2行でlatitudeとlongitudeを更新している部分で、これによってABSの中の結果が常に0になっていました。
SQLは宣言的なイメージが強かったので、前の文の副作用が現在の式に反映されていることになかなか気づけませんでした。
totalの行を先頭に移動させて解決しました。

色々沼ってしまい1時間以上かかってしまいましたが、なんとか完了させて結構スコアを伸ばせました。

各種アクセストークンをキャッシュ

今回はDBヘビーな傾向がなかなか解決されなかったため、各種ミドルウェアによるアクセストークンのフェッチをキャッシュすることにしました。
アクセストークンは変更されないこと、フェッチした結果はIDしか使用されないことを確認したので、アクセストークンに対応するIDをオンメモリにキャッシュしました。
CharID、OwnerID、UserIDそれぞれに対して行いました。

スコアには微量の効果があったような気がします。

DB分割時に1人のユーザに複数のイスが配イスされる不具合

DBとAppを別々のサーバに分割する作業をtakutaka1220が行っていた際、レースコンディションっぽい現象が確認されうまく分割できませんでした。
調査の結果、定期的に実行される配イスのマッチングジョブにレースコンディション耐性がないことが判明しました。

ジョブはタイマー処理で定期実行されますが、前回処理の完了を待たずに次の処理を開始することができてしまう構造でした。これにより同じコードブロックが並列に走りうる状態でした。
一度配イスされたユーザに別のジョブが並列で配イスを行うことで、多重に配イスされてしまいました。

対応として、UPDATE文に以下のようにchair_id IS NULLの条件を加えて、すでに配イス済みのユーザに別のイスをセットしないようにしました。

UPDATE rides SET chair_id = ? WHERE id = ? AND chair_id IS NULL

これで対応が完了する想定だったのですが、実際は問題は解決していませんでした。
そもそもこれで問題が解決するのであれば、DB分割する前の、AppとDBが同一サーバにある状態でも問題が発生していたはずです。

真の原因は、DBを担当するサーバでも配イスジョブが定期実行されてしまっていたことでした。
ISUCON環境では初期状態では全てのサーバでサービスが正常稼働しているため、DBサーバでもAppが動いていて、そのAppが初期状態のままジョブを実行してレースコンディションを引き起こしていました（takutaka1220が発見）。

DBサーバでAppとジョブを停止して、無事サーバ分割が完了しました。

マッチングロジックの改善

初期状態のマッチングロジックはひどいもので、ただのランダムでした。
地域間の区別もなかったため、遠い別の地域から遅いイスがゆっくりやってくる、という地獄のような光景が広がっていたのだと思います。

ここのロジックは非常に改善の余地がありそうでしたが、凝った構造を競技時間内に完成させるのも難しいため、単に最も早くユーザに到着するイスを選ぶ、というものにしました。
ただし例外的に、地域間が異なる場合は配イスさせないようにしました。

地域はコード上では取り扱われていませんがアプリケーションマニュアルには記述があり、実データを眺めているとクラスタが存在しそうでした。
実際にyush1gaがイスの位置をプロットしてくれて、それは確信に変わりました。

この調査結果から、ユーザとイスの距離が200を超えているものは選択肢に入れないことにしました。

この変更はyush1gaが実装してくれて、スコアにかなり響いてました。
また地域を区別するロジックも効いていたようで、地域の区別を外すとスコアが明確に下がっていました。
遠くのイスを向かわせるよりは、空きが出るのを待ったほうがマシだったみたいです。

クライアントのポーリング間隔を30ms → 1000msに変更

ユーザやイスは定期的に自分の状態をpullする構造になっていました。

マニュアルにはSSE（Server-Sent Events）を利用してリアルタイムにクライアントに状態を通知するよう示唆されていました。
個人的にはSSEでコネクションを貼り続けるのは高コストになりかねないと思ったのと、そもそもSSEとイベント通知の仕組みを時間内にうまく作れる自信がありませんでした。

悶々とマニュアルやコードを眺めていると、クライアントが常に最新の情報を保つ必要はないのではないかと気づきました。
思い切って30msになっていたポーリング間隔を1000msまで一気に拡大したところ、ベンチは落ちないしスコアは50％くらい上がるという絶大な効果がありました。

この後さらに間隔を引き延ばしたらベンチがランダムに落ち始めてしまったので、よくわからないけど1000msをギリギリのラインとして採用しました。

その他、ちょこちょこキャッシュを入れたりインデックスを見直す

引き続きDBヘビーだったため、細かいですが不変なデータに対してキャッシュを入れたり、インデックスを見直したりしました。

去年Failで終了したことから今年はやや慎重めになり、終盤は大きくコードをいじりませんでした。

最終的に、いじれるパラメータをちょこちょこいじったりしつつ、ランダムで落ちないことや再起動試験をして何度もベンチを回しつつ、いい感じのスコアで安定したところで終了にしました。

結果

最終的に、
サーバA: App
サーバB: DB
サーバC: 未使用
という構成で28,148点でフィニッシュしました。

順位は24位で、初の（旧）本戦ライン突破となりました。
チームとして本戦ラインが1つの目標となっていて、何年もあと一歩か二歩及ばずの順位を繰り返してきたので、本戦ライン突破はかなり嬉しかったです。

また偶然ですが副賞としてはてな賞もいただけることになりました。はてなさんありがとうございます。

感想

Pyroscope

あまり活用できませんでした。
今回はDBヘビーな状態がずっと続いていたので、単に活用する機会がありませんでした。
導入の楽さは良かったので、来年も使っていくかもしれません。

シナリオベースの攻略

今年の問題は難しく、やるだけ系のタスク（DBに埋め込まれた画像をnginxで配信するとか）が少なかった上に、わかりやすい要改善箇所も一筋縄ではいきませんでした。
課題はわかるけど、それを手早く解決させる見通しが立たず手が出せない、というものが多かったです。
実際14時くらいは全然スコアが振るわず、今年は例年よりダメかもという気持ちになっていました。

しかし終盤にアプリケーションマニュアルを読み込んだことによる改善がかなり効いてきて、一気に持ち直すことができました。

近年の出題は単なるコードの改善ではスコアが伸びにくいものが続いており、その経験がシナリオを読み込む動きに繋がったので、毎年参加していたことによる経験でうまくいったという感じがしました。

おわり

Discussion