こんにちは、ISUCON11本選問題の作問を担当したtemmaです。普段はVTuberを見る活動をしています。この記事では、本選問題で改善対象となった「ISUCHOLAR」について、問題の概要と実際の競技の様子を解説します。

なお、本選問題は以下のメンバーで作問しました。
NTTコミュニケーションズ株式会社
 ・kawase
 ・Osumi
team takonomura
 ・takonomura
ヤフー株式会社
 ・karino
 ・takahashi
 ・hattori
東京工業大学デジタル創作同好会traP
 ・hosshii
 ・temma
 ・toki

ISUCHOLARとは

ISUCHOLARはどこかの大学で使われている学内システムです。シラバスを見たり、科目を履修したり、成績を確認したり何でもISUCHOLARを使って行われます。

ということで本選問題のテーマは「学内システム」でした。過去のISUCONでは、出題各社が実際に提供しているサービスに因んで出題されることが多かったと思います。今回は、学生と社会人の混成チームということで予選・本選のどちらかは学生らしいテーマにしたいという思いがあり、このテーマに決まりました。案出しの段階では動画配信プラットフォームやフードデリバリーサービス、音声SNSなどがありました。

ちなみに、現実の学内システムに不満があるわけでは無いです。

isucon/isucon11-final - GitHub

問題の解説

出題の意図

ISUCON11の本選問題も予選同様に「教科書的な問題でありつつも、解きごたえのある問題」であることを心がけて作問しました。

NginxとMySQLにアプリケーション(外部サービス無し)という構成になっているのも、過去のISUCONのベーシックな形を意識したためです。競技用サーバーがすべて同じスペックだったということもあり、インフラ担当の方には少し味気なかったかもしれません。加点についても「課題の提出」と「お知らせ一覧の取得」の成功回数に対して固定で点が割り振られているだけで、倍率のような概念はありませんでした。

上記のような点が分かりやすい一方で、予選よりシナリオの依存関係が複雑になっており本選らしい難易度になっていたのではないかと思います。特に、エンドポイントごとにまとめて扱う単位が異なっていたことが全体像の把握を難しくしていたように感じます。

また、予選に比べて変更のスコープが大きい改善ポイントの割合が増えていたため、コードリーディングの速さや仕様を把握する力も要求されたのではないかと思っています。

そうなった要因の一つに、テーブル間の依存関係が複雑だったことがあります。初期状態では、以下のようになっていました。
今回のように外部制約キーが存在する場合は、IDEの機能やtblsのようなツールを使ってER図を生成すると便利です。
1p7Z4SU

シナリオ

ここでいうシナリオとは、ベンチマーカーがユーザーの行動を模す際に従う規則のことです。ベンチマーカーの仕様と言うほうが分かりやすいかもしれません。

ISUCHOLARには学生と教員の2種類のユーザーが存在し、各ユーザーは以下のシナリオにしたがって負荷走行を行っていました。

iDYVJc5

赤色になっている「課題提出」と「お知らせ一覧取得」が加点対象です。

シナリオは図の下側に示すような「科目の登録から、科目の終了まで」を大枠として設計されています。科目は教員によって登録されると、学生が履修するまで待機状態になります。待機状態の科目を1人でも履修するとカウントダウンが始まり、ベンチマーカー内で設定した定員(50人)に達するか2秒経過した時点で履修を締め切ります。履修が締め切られると講義が始まり、講義が5回行われると科目は終了します。

加点対象である課題提出やお知らせ一覧取得の上限回数は、「科目数」と「その科目を履修している学生」の積に比例して決まっているため、スコアを伸ばすためにはこの一連の処理がより早く回るように改善していく必要があります。
アプリケーションマニュアルには、この流れを仄めかす内容が散らばっているはずなので、図を片手にぜひ読み返してみてください。

上記を踏まえて下図のような2パターンを考えた時、加点対象の上限数はほぼ同じですが科目全体の負荷傾向は異なります。すべてのエンドポイントが十分改善された状態では、「定員に達している場合」の方がリクエスト数が少なく済み、履修の待ちも短かくなるため早く回ります。ただし、成績確認や課題提出の待ち、課題のダウンロードなどは対象科目の履修者数が多くなると負荷や待ち時間が大きくなる処理ですので、改善状況によっては「定員に達しない場合」の方が早くなることがあります。

1XFiSZ8


また、「履修登録」と「課題提出」では科目毎に学生の行動を待機しています。履修登録の前の「成績確認」や課題提出の前の「お知らせ確認」が1人でも遅れると全員待たされるため、エンドポイントごとの累積レスポンス時間に加えて、それぞれの平均レスポンス時間にも注意しながら改善する必要がありました。これは遅いエンドポイントが一つでもあるとユーザー体験は損なわれるという思想をスコアに反映するためです。

加えて、シナリオの間で待機することで学生毎のシナリオ進行度が揃うようになり、結果として特定のエンドポイントにアクセスが集中するようになっていました。これは、成績公開時にアクセスが集中するといった現実のアクセス傾向を踏まえた仕様です。

以上のようなシナリオの一部でも紐解けると、改善の方針を立てやすかったのではないかと思います。
一方、これらのシナリオを時間内に考えることが難しいことも身に沁みて分かっていたので、特定のエンドポイントがalp等の統計上に残り続けたり、CPU使用率の高い処理・累計レスポンスタイムの大きいエンドポイントとして統計に出ない部分が律速になったりすることで、競技体験を損なうことがないように注意しました。

改善例

以下では想定していた改善の例をシナリオを踏まえつつ解説します。

構成

実際の競技では、序盤から中盤にかけてアプリケーションとDBの2台構成に移行し、その後3台構成に移行したチームが多いと思います。
3台目をどのように使うか多くの選択肢が考えられますが、一例として以下のような構成が考えられます。

G4rwdDb
この例では、高負荷になりやすいお知らせ関連の処理を3台目で扱うようにしています。

成績の確認

二重ループ内でクエリを実行したり、複数のJOINやサブクエリを同時に含んだクエリを実行したりするため、DBに大きな負荷がかかるエンドポイントです。

参考実装ではタイムアウトが頻発しています。ベンチマークのログに出力していたように、成績取得でタイムアウトした学生は10秒間スリープするため、このエンドポイントを改善しないことにはスコアを伸ばしにくい作りになっています。
必ず改善しないといけないにもかかわらず、エンドポイント単位でキャッシュできなかったり、GPAやtotal scoreなど更新のタイミングが異なる値を使用していたりと、改善に一工夫必要な部分だったと思います。

改善例を紹介する前に、成績確認のレスポンス形式を振り返ります。
{
"summary": {
"credit": 総得単位数,
"gpa": GPA,
"gpa_t_score": 学内における自身のGPAの偏差値,
"gpa_avg": 学内のGPAの平均値,
"gpa_max": 学内のGPAの最大値,
"gpa_min": 学内のGPAの最小値
},
"courses": [{
"name": 科目名,
"code": 科目コード,
"total_score": 自身が獲得した総合点,
"total_score_t_score": 履修者における自身の総合点の偏差値,
"total_score_avg": 履修者の総合点の平均値,
"total_score_max": 履修者の総合点の最大値,
"total_score_min": 履修者の総合点の最小値,
"class_scores": [{
"class_id": 講義のID,
"title": 講義名,
"part": 講義の回,
"score": 提出課題の採点結果,
"submitters": 課題の提出者数
}, ...]
}, ...]
}

競技中は、以下のようなN+1の解消から取り組んだチームが多いのではないでしょうか。
query(履修科目一覧の取得)
for 履修科目 in 履修科目一覧 {

query(講義一覧の取得)
for 講義 in 講義一覧{
query(課題の提出者数の取得)
query(自分の提出課題の採点結果の取得)
}

query(履修者総合点一覧の取得)
}

ナイーブに改善すると以下のようになります。総合点一覧の取得がN+1のままで残っていますが、ここをSQLでうまく取得するためにはもうひと踏ん張り頭を使わないと難しいと思いますので、AとBを並列化する程度が妥協点ではないでしょうか。
query(履修科目一覧の取得)

// A
query(履修科目一覧に対応する講義一覧の取得)

科目と講義を紐付けるJOIN相当の処理

query(各講義の課題の提出者数の取得)
query(各講義の自分の提出課題の採点結果の取得)

講義と採点結果を紐付けるJOIN相当の処理

// B
for 履修科目 in 履修科目一覧 {
query(履修者総合点一覧の取得)
}

N+1と同時に気になるのが、GPAの一覧を取得するクエリだったと思います。明らかに重たい処理であることは分かるものの、適切に解釈しようとするとかなり時間を取られそうで一見手を出しにくかったのではないでしょうか。

ですが、クエリの実行部分を見ると引数に定数しか取っておらずリクエスト間で同じクエリを実行していることが分かります。マニュアルに書いてあるように、GPA一覧は科目が終了したタイミング以外では更新されないので、科目の終了と終了の間の呼び出しはリクエスト間で使い回すことができ、クエリの実行回数を抑制できます。

当日はN+1の改善とGPA一覧取得のcoalescingの2つが達成できていれば、上位入賞を狙えたように思います。

一方、ここまでの改善ではある程度早く回るようになると、ベンチマークの後半で再度タイムアウトが発生するようになります。

これはベンチマークの進行に伴い、学生あたりの履修済み科目数が増えBのループ数が増加するためです。Bのループ、つまり科目の総合点一覧の取得数を抑えたいわけですが、すでに終了している科目では更新されないことに気づけば永続的にキャッシュして良いことが分かります。
query(履修科目一覧の取得)

終了している科目についてキャッシュを参照

// 終了していない科目はDBを参照
{
// A
query(履修科目一覧に対応する講義一覧の取得)

科目と講義を紐付けるJOIN相当の処理

query(各講義の課題の提出者数の取得)
query(各講義の自分の提出課題の採点結果の取得)

講義と採点結果を紐付けるJOIN相当の処理

// B
for 履修科目 in 履修科目一覧 {
query(履修者総合得点一覧の取得)
}
}

この改善はN+1と同じぐらいのタイミングで入れるチームが多いと予想していたのですが、実際に改善できたチームは少ない印象です。

この方針とは別に、無駄なJOINを削減したり、総合点の計算を逐次行うという方法でもDBの負荷を抑えることが可能です。
-- 改善前
SELECT IFNULL(SUM(`submissions`.`score`), 0) AS `total_score` -- NULL: 提出していない || 採点されていない
FROM `users`
JOIN `registrations` ON `users`.`id` = `registrations`.`user_id`
JOIN `courses` ON `registrations`.`course_id` = `courses`.`id`
LEFT JOIN `classes` ON `courses`.`id` = `classes`.`course_id`
LEFT JOIN `submissions` ON `users`.`id` = `submissions`.`user_id`
AND `submissions`.`class_id` = `classes`.`id`
WHERE `courses`.`id` = ?
GROUP BY `users`.`id`;

-- 改善後
SELECT COUNT(`user_id`) FROM `registrations` WHERE `course_id` = ?; -- 履修人数の取得

SELECT IFNULL(SUM(`submissions`.`score`), 0) AS `total_score` -- NULL: 採点されていない
FROM `submissions`
JOIN `classes` ON `classes`.`id` = `submissions`.`class_id`
WHERE `classes`.`course_id` = ?
GROUP BY `submissions`.`user_id`;

-> 2つ目のクエリでは、「科目を履修しているものの課題を一つも提出していない人」の総合点が取得できないため、履修者数を別で取得する


最後にGPAのクエリ自体の改善を紹介します。
-- 改善前
SELECT IFNULL(SUM(`submissions`.`score` * `courses`.`credit`), 0) / 100 / `credits`.`credits` AS `gpa`
FROM `users`
JOIN (
SELECT `users`.`id` AS `user_id`, SUM(`courses`.`credit`) AS `credits`
FROM `users`
JOIN `registrations` ON `users`.`id` = `registrations`.`user_id`
JOIN `courses` ON `registrations`.`course_id` = `courses`.`id` AND `courses`.`status` = ?
GROUP BY `users`.`id`
) AS `credits` ON `credits`.`user_id` = `users`.`id` -- 各生徒の取得単位数の取得
JOIN `registrations` ON `users`.`id` = `registrations`.`user_id`
JOIN `courses` ON `registrations`.`course_id` = `courses`.`id` AND `courses`.`status` = ?
LEFT JOIN `classes` ON `courses`.`id` = `classes`.`course_id`
LEFT JOIN `submissions` ON `users`.`id` = `submissions`.`user_id` AND `submissions`.`class_id` = `classes`.`id`
WHERE `users`.`type` = ?
GROUP BY `users`.`id`

-- 改善後
SELECT `users`.`id` AS `user_id`, SUM(`courses`.`credit`) AS `credits`
FROM `users`
JOIN `registrations` ON `users`.`id` = `registrations`.`user_id`
JOIN `courses` ON `registrations`.`course_id` = `courses`.`id` AND `courses`.`status` = ?
GROUP BY `users`.`id` -- 各生徒の取得単位数の取得

SELECT `submissions`.`user_id` AS `user_id`, IFNULL(SUM(`submissions`.`score` * `courses`.`credit`), 0) AS `weighted_score`
FROM `submissions`
JOIN `courses`.`classes_id` = `submissions`.`class_id` AND `courses`.`status` = ?
GROUP BY `submissions`.`user_id` -- 各生徒について、履修済み科目の総合点数にその科目の単位数を掛けたものを合計して取得

-> 各学生について weighted_score/100/credits を計算


課題の提出・ダウンロード

課題の提出からダウンロードまでは以下の手順で行われます。下図の右側に示すように、提出の段階で講義ごとのディレクトリに分けて書き出すことで、cpを省いたりダウンロード時のDBアクセスを減らしたりすることが可能です。

xJ5l4l1

参考実装では提出されたPDFファイルをメモリに読み切ってから書き出すようになっているので、streamで書き出すようにするとメモリ確保を削減できます。

課題のダウンロードに関しては、zipコマンドではなく各言語のライブラリでzipを生成すると、プロセス起動・終了のオーバーヘッドを削減できます。加えて、ある程度早くなるとzip生成時のdeflateがCPU使用率の上位に上がってきます。帯域には余裕があるはずなので、圧縮レベルを下げることでCPU負荷を抑えられます。実際にはstored(無圧縮)を採用しているチームがほとんどでした。

お知らせ一覧・詳細の取得

お知らせ一覧・詳細の取得はリクエスト数が多く、それなりにCPUを使用しているエンドポイントです。

お知らせ系のエンドポイント(GET /api/announcements, POST /api/announcements, GET /api/announcements/:announcementID)の処理を3台目に切り出す方針は、分かりやすく効果の高い改善だと想定していました。

お知らせには科目名が必要なため、科目名を非正規化する必要がありますが、お知らせ追加時にメインのDBを参照するなどの方法で対応できます。

DBを複数台に分割しなかった場合でも、JOIN相当の処理をアプリケーション側で行うことでDBの負荷を下げるなどの改善が可能です。

また、参考実装では一覧取得のページングがOFFSETとLIMITの組み合わせで実現されています。OFFSETを使用するとオフセット数分のrowを頭から数える必要があるため、レコード数の増加に応じてパフォーマンスが劣化します。今回はページング用のリンクヘッダを介して、リクエスト時のクエリパラメーターを指定していたため、ページ数ではなく前回の最初・最後のレコードのIDを使用することでseek方式のページングに差し替えることが可能でした。これは科目検索のページングも同様です。

豆知識として、ここで用いられていたようなJOINやWHERE、ORDER BY、複合INDEXなどが同時に用いられたクエリの改善を行う際には、
EXPLAIN ANALYZE
SHOW INDEX
等で実行順序やコスト、cardinalityといった役に立つ情報が得られることを知っておくと便利です。

その他

初期状態ではMySQL8.0を使用しています。MySQL8.0では、デフォルトでbinlogが出力される点には注意が必要です。

また、今回は十分な外部制約キーを初めから設定した状態で問題を提供しました。外部制約キーは参照整合性を担保する上で便利な機能ですが、INSERT・UPDATE・DELETE時に参照先・参照元レコードを確認する必要があるため、追加のCPUオーバーヘッドが生じます。

同様に、参考実装でトランザクションを取っている部分は全てアプリケーションとして正しい仕様であり、レスポンスの整合性を保つために必要なものでした。アプリケーションとしては正しいものの、ユーザーがそこまでの精度を求めていないという想定のもと、トランザクションを外しても許容するようなベンチマーカーとなっています。

つまり、「ユーザーのニーズを満たす範囲で整合性を提供すれば良い」というコンセプトです。同時に、レスポンス内で整合性が取れていなくても許容されるといった点は、実世界で想定されるニーズとズレが大きすぎるのではないかという指摘はその通りで、そのせいでguess要素が強くなってしまったという認識は作問側も感じています。これは作問の都合上うまく調整できなかった部分なので申し訳ないと思っていますが、少なくとも背景には上記のようなコンセプトを持っていたことを理解して頂ければ幸いです。

本選参加者のwriteupでは、本記事で解説しきれなかった改善点(各種N+1や細かなオンメモリ戦略)やなるほどなと唸るような工夫が惜しみなく解説されていました。ISUCON11 関連エントリまとめにまとまっているので、ぜひ読んでみてください。

講評

今回の本選問題はかなりシナリオ依存の問題になっていて、大きくスコアが上昇するような改善は少なかったと思います。一方で、少しずつでも改善を入れれば点数が伸びるように作問側も気をつけたので、その点を感じていただけていれば幸いです。

点数に関しては「リソースをうまく使い切れたか」「成績取得をどの程度改善できたか」「課題のダウンロードをどの程度改善できたか」の3つが上位入賞のキーになっていたようです。大きく点が伸びるポイントとして、複数台構成への移行とGPA計算のcall supression、zipの無圧縮の3つが想定され、少なくともこの3つなしに10万点を超えるのは難しかったのではないでしょうか。

競技当日の様子として、10時から12時にかけて早めに点数を伸ばしたチームは、アプリケーションとDBの2台構成に加えて、お知らせ一覧の取得か課題提出・ダウンロードのいずれかに改善が入っていたように思います。インデックスを貼るだけといった改善がなかった分、例年に比べて序盤の立ち上がりはかなり静かだった印象です。

その後、15時頃までに上記の残りや各種N+1の改善、細かなオンメモリ戦略によるクエリの削減などが反映されるようになり、15時前後で成績取得の改善が見られるようになったという流れでした。15時以降は一つ峠を超えて負荷傾向の変化を観測しているようなチームも見られ、上位に見慣れたチームの名前が並んでいたのでかなり安心しました。

結果として、ベテランのfujiwara組が優勝し、改善も見事の一言に尽きるものでした。自他共に言及されていたように、「手が止まることがなかった」ことが優勝の要因だと思いますが、その背景には確実な改善を手早く行いつつも、マクロな視点から優先度を適切に判断し、時にはアグレッシブな改善にチャレンジするといった、確かな経験と技術に裏打ちされた能力があるように感じました。

謝辞

作問という機会を提供してくださったLINEの皆様をはじめ、協力してISUCONを作り上げた作問チームの皆様、アドバイザリーとして常に見守り助言をくださった白金動物園の皆様、各言語実装を担当してくださった移植者の方々、事前解答に協力してくださった:innocent::innocent::innocent:, isucon_friends, シン・鍋部の皆様、今回みなさんとISUCON11の運営に携われたことを大変ありがたく、光栄に思っています。ありがとうございました。

最後にISUCON11の予選や本選に参加していただいたチーム、スポンサーをしてくださった企業の皆様、ISUCON11を応援し盛り上げてくださった全ての人に感謝申し上げます。