こんにちは，y1rです． ark, akkyと，チームshallowverseでISUCON11本選に出場し，6位を獲得しました． traP賞とTVer賞をいただけることになり，大変嬉しく思っています． 本記事では，問題の構成と，shallowverseの取り組みについて紹介します． 使用したツールなどは予選の参戦記をご確認ください． 高速化のネタバレしかないので，ご注意ください．

問題の構成

今回の課題は「学内システムISUCHOLAR」でした．このシステムは，教員と学生が利用するもので，履修登録から課題提出，成績開示に至るまで，教務系の全てが統合された便利なシステムです．

シナリオ

• 教員が科目を開講する
• 学生が履修登録する

• 教員が科目に対して複数回の講義を行い，以下を繰り返す

  • 学生が講義ごとに提出を行う
  • 教員が講義ごとに提出課題をダウンロードする
  • 教員が講義ごとに採点を行う
  • 学生が評価を確認する

テーブル

• ユーザテーブル users
• 科目テーブル courses
• 履修登録テーブル registrations
• 講義テーブル classes
• 講義毎の課題提出と成績テーブル submissions
• お知らせテーブル announcements
• お知らせの未読管理テーブル unread_announcements テーブルは正規化されており，適切にJOINを行ってアプリケーションが構築されていました．

用意されていたエンドポイントなど詳しい構成は，後ほど公開されるであろう公式講評にゆずります．

shallowverseの取り組み

shallowverseの公開リポジトリはこちら． 予選に比べ，なにがボトルネックになっているかが分かりづらく，様々な改善に手をつけましたが，何が効果があったのかはよく分かっていません． ここでは，エンドポイントごとに考えたことと改善策をまとめて紹介します．

お知らせと未読管理 (announcements API)

教員は，講義ごとにお知らせをすることができました．例えば，「講義室の場所」や「課題提出期限の変更」などがお知らせにあたります． ISUCHOLARは，学生ごとに未読管理を行っており，どのお知らせが未読であるかと，全部で何件の未読があるかを計算しています．

具体的には，以下のような実装が行われていました：

• 教員がお知らせを行うと，各受講生ごとに，未読管理テーブルに「未読である」ことがINSERTされる
• 学生がお知らせの一覧を確認すると，未読管理テーブルを参照して何件の未読があるか確認する
• 学生がお知らせの詳細を確認すると，未読管理テーブルを更新して既読にする

お知らせは講義ごとに行われるため，お知らせは講義の数よりも多いことが予想されました． そのためshallowverseは2つに分けて改善を行いました．

改善1: お知らせが未読であることは，未読管理テーブルに対応する行がないことで表現する

最初の実装は，お知らせの登録に対して未読管理テーブルに受講生分の行をINSERTする必要がありました． これを遅延させるため，お知らせの登録時には未読管理テーブルにINSERTせず，「学生がお知らせの詳細を確認したとき」に既読をINSERTするようにしました． つまり，未読ではなく，既読を管理するように変更しました．

改善2: Redisに移行

さらに，この既読管理テーブルをRedisに移行し，MySQLの負荷を削減することを狙いました． SAdd, SCard, SIsMember, FlushAll (初期化) を使ってユーザごとの既読お知らせの集合を実装しました．

提出課題のアップロードとダウンロード

また，今回のシナリオでは講義 x 受講生の数だけ課題が提出されるため，課題のアップロードの改善も行いました．

アップロードの改善

課題のアップロードについて，以下のような実装が行われていました：

• 課題をアップロードするリクエストが来る

• トランザクション

  • データベースに問い合わせ，課題の提出期限が到来していないことを確認する
  • ローカルディスクに課題を保存する

shallowverseは，以下の改善を行いました．

改善1: ローカルディスクへの書き込みをトランザクションの外でやる

トランザクション時間を削減するためには，遅いローカルディスクへの書き込みを防ぐ必要があります． 厳密にコードの意味を保ってトランザクションを短くする方法として，テンポラリファイルへ事前に書き込んでおき，トランザクション中でテンポラリファイルを移動することを検討しました． ここでファイル移動は，ファイルシステムのメタデータの更新のみで済むので，ファイル全体を書き込む従来の実装よりも高速になることが予想されます． 色々試した結果，意味は変わりますが，トランザクションの外で移動しても問題ないことが分かりました．

改善2: ローカルディスクへの書き込みを遅延させる

改善1は，トランザクション時間を短くすることにはなりますが，ユーザへのレスポンス時間を削減することにはなりません． これを削減するため，goroutineを用いてローカルディスクへの書き込みをレスポンス後に非同期で行いました． しかし，これは後続の教員によるダウンロードが改善されると問題になる可能性はあったかもしれません．

(本選中に間に合わなかった) ダウンロードの改善検討

本選中は間に合いませんでしたが，教員によるダウンロードの改善を検討します． もともとは以下の実装でした：

• トランザクション

  • 課題の提出を締め切る
  • 提出課題をコピーして，適切なファイル名に変更する
  • zipコマンドで圧縮する
• zipコマンドで生成されたアーカイブをレスポンスとして返す

これは大変非効率な実装です．あるファイルについて，どのように読み書きされるかを考えると：

• ファイルコピー

  • ファイルをディスクから読み込む
  • ファイルをディスクに書き込む

• zipコマンドで圧縮

  • ファイルをディスクから読み込む
  • ファイルをディスクに書き込む

• レスポンスとして返す

  • ファイルをディスクから読み込む

結果として3回のreadと，2回のwriteが必要です（ページキャッシュが利用できたとすればもっと改善されます）．

実際は，ファイルを適切な名前にリネームしてzipで返すことができさえすればよいので， ファイル名をrenameしながらオンメモリでzipすることで，1回のreadで十分なはずです． Goの標準ライブラリ archive/zip packageを使用すれば，ファイル名と内容を独立に決められるため，容易に実装できたと思います． さらに，課題の提出を締め切ったあとにこれ以上提出は増えないので，ファイルの読み込みは（提出を締め切る）トランザクション終了後に遅延させても問題ないはずです．

成績計算の高速化

ISUCHOLARの成績開示エンドポイントは，自分のGPAと科目ごとの得点のみならず， 全学生のGPAの統計量（最大・最小・平均・標準偏差）と，科目ごとの偏差値などを返すため，非常に重たいエンドポイントとなっていました． そのためshallowverseは2つに分けて改善を行いました． これらは，MySQL slowlog において改善が見られたものの，ISUCONのスコアの面では改善が見えづらかったです．

改善1: 各学生のGPA計算の前処理化

各学生のGPAの計算を，成績確認時ではなく，成績登録時に行うように変更し，確認時にはSELECTのみで行えるようにしました． GPAの計算自体は，SQLのgenerated columnで実装されています． INSERT INTO ... ON DUPLICATE KEY UPDATE を使って，うまく差分で合計得点を計算しています．

改善2: 科目ごとの成績計算の前処理化

科目ごとの成績についても，成績確認時ではなく，成績登録時に行うように変更し，確認時にはSELECTのみで行えるようにしました．

感想

非常に解きごたえがある，ボトルネックの分かりづらい問題で，スコアを大きく伸ばすことはできませんでしたが，非常に楽しかったです． 昨年の本選9位よりも良い6位をいただけまして，とても嬉しいです． もっと精進を進め，来年も参加・賞金獲得できるように頑張っていきます． 運営の皆さん，今年もありがとうございました！！！