ISUCON14に参加しました(6659点)

今年もSaza, MoririnとチームMONOSとしてISUCON14に参加しました。 結果は6659点で総合277位でした。 前回(総合13位 学生3位)と比べるとかなり悔しい結果になりましたが、一日楽しめました。

GitHubレポジトリ: https://github.com/saza-ku/isucon14

ISUCON13(前回)：https://onoe.dev/blog/isucon13

前日まで

チームでの練習として13・12本戦・9予選をやっていました。 今年は自分一人での練習はあまりできませんでした。

前回と同様にSazaが作ってくれた便利なテンプレートを使っていて、セットアップやデプロイ、計測までを簡単に実行できるようになっています。 alp, pt-query-digest, pprof, netdataに加えて今年はOpenTelemetry&Jaegerによるトレーシングもできるようになりました。 ベンチマークが終了するとIssueに全ての結果が書き込まれるようになっています。
参考: https://github.com/saza-ku/isucon14/issues/66

当日

序盤

今年は初動のセットアップがかなりスムーズに進み、10:30頃には初期計測が完了しました。

自分は最初にGET /api/chair/notificationのリクエストの多さを見て、RetryAfterMsを30msから3000msに伸ばしました。 他2人はIndexを貼ったり、秘伝のタレや複数台構成をやったりしてくれました。

[10:29] 643(#2) : 初動の簡易計測(3718092)
[10:33] 654(#3) : 初動のフル計測(6fdc857)
[10:48] 1717(#5) : ride_statusesのindex追加(#6)
[10:53] 2961(#7) : RetryAfterMsを3000msに(#8)
[10:56] 2019(#9) : chair_locationsのindex追加(#10) (おそらく#8が入っていないため点数が下がっている)
[10:59] 3204(#11) : ridesのindex追加(#13)
[11:02] 3950(#12) : chairsのindex追加 (f68c81a)
[11:17] 4965(#16) : MySQLを2台目に(#13)
[11:24] 4837(#18) : chairsのindex追加(#19)
[11:39] 4796(#20) : 秘伝のタレ(#21)

中盤

午前からずっと時間をかけていたdistance_tableの切り分けが昼過ぎに完了しました。 一番上にあったスロークエリに関連するものです。 まずdistance_tableとなっているサブクエリを丸ごと切り出して一つのテーブルにします。 そしてchair_locationsテーブルへの書き込みをする時点で、total_distanceとtotal_distance_updated_atを計算しておくようにします。 さらにchair_locationsテーブルへの書き込みをするエンドポイントであるPOST /api/chair/coordinateはデータ反映の遅延が許されているため、バッチ処理でdistance_tableを更新するようにします。 chair_locationsテーブルへの書き込みが1箇所しかないということにMoririnが気づいてくれて実装することができました。

Count: 164  Time=1.14s (186s)  Lock=0.00s (0s)  Rows=4.9 (797), isucon[isucon]@isucon1
  SELECT id,
  owner_id,
  name,
  access_token,
  model,
  is_active,
  created_at,
  updated_at,
  IFNULL(total_distance, N) AS total_distance,
  total_distance_updated_at
  FROM chairs
  LEFT JOIN (SELECT chair_id,
  SUM(IFNULL(distance, N)) AS total_distance,
  MAX(created_at)          AS total_distance_updated_at
  FROM (SELECT chair_id,
  created_at,
  ABS(latitude - LAG(latitude) OVER (PARTITION BY chair_id ORDER BY created_at)) +
  ABS(longitude - LAG(longitude) OVER (PARTITION BY chair_id ORDER BY created_at)) AS distance
  FROM chair_locations) tmp
  GROUP BY chair_id) distance_table ON distance_table.chair_id = chairs.id
  WHERE owner_id = 'S'

[12:22] 4895(#26) : getLatestRideStatusのN+1削除(#27)
[12:55] 5750(#35) : distance_tableを切り分け(#22)

終盤

ここから全員が詰まります。 各種リソースは足りているのに、ユーザー数が増えず負荷がかからない状態になりました。 ベンチマーカーの挙動を見ながらユーザーの評価を向上させるべく、SazaとMoririnがマッチングアルゴリズムの改善や各種パラメータの調整に取り組んでくれましたが、どれもうまくいかない状態でした。
実装ブランチ1(WIP): https://github.com/saza-ku/isucon14/tree/fix-matcing
実装ブランチ2(WIP): https://github.com/saza-ku/isucon14/tree/fix-matcing-2

自分とMoririnはN+1の解消を進めていましたが、実装をバグらせてうまくいかない状態でした。 自分はchairPostCoordinateのN+1改善を進めていました。batch処理までは実装できたのですが、その後のN+1の改善は最終的に実装できませんでした。
実装ブランチ(WIP): https://github.com/saza-ku/isucon14/tree/coordinate-named-exec

N+1を解消してもユーザーが増えない限り意味がないという判断で、自分はN+1解消を中断してGET /api/app/notificationにおけるSSE(Server-Sent Events)の実装に取り掛かりました。RideIDごとにチャネルで管理し、ride_statusesテーブルの更新時にキューにPush、Popしてレスポンスを返すように実装しました。しかしこれも最終的にはうまく動きませんでした。
実装ブランチ(WIP): https://github.com/saza-ku/isucon14/tree/notification

結局昼過ぎからスコアは伸びませんでした。かなり苦しかったです。 最終的に計測ツールを削除してからガチャを回して6659点になりました。

[13:37] 6304(#44): chairPostCoordinateのbatch処理(#45)
[17:50] 6659 : 計測ツール削除(30d5b06 )

反省

マッチングアルゴリズムがボトルネックになっていて、それを改善できないと他のボトルネックが現れない状態だったのかなと思います。

自分はインフラ周りの改善の方が得意なので、ボトルネックがリソース不足として現れずにユーザーの評価・ベンチマーカーの挙動として現れるという状況はかなり苦手なんだなと分かりました。

ユーザー・ベンチマーカーの挙動を把握できるようにするというのはとても大事なので今後改善していきたいです。

終わりに

今年も楽しめました。来年からは学生チームではなくなりますが、また頑張りたいと思います。