本選の問題作成を担当したさくらインターネットの江草です。
ISUCON9 本選参加された皆様、本当にお疲れさまでした。また、優勝したチーム「白金動物園」の方々、おめでとうございます！
今回は予選両日ともに学生一人チームがトップで予選通過する快挙など、イベント的には良い意味で波乱が巻き起こり運営一同大変興奮しておりました。


1. 問題の公開

今回の本選問題のソースコード、データ、および本選では非公開だった決済APIやベンチマークなど全ての要素を公開しております。本選問題についてはdockerで簡単に展開出来るようになっておりますので、ぜひ復習や学習にお役立てください。

https://github.com/isucon/isucon9-final

2. 課題アプリケーション概要

今回出題した内容は、開業を間近に控えた鉄道の座席予約を題材とした「ISUXPRESS予約」です。
isuxpress


2020年1月1日に開業する夢の超特急の座席予約サイトという設定で、なんとなく動きはするもののパフォーマンスが劣悪なアプリケーションを今日（！）リリースするので予約を開始する8時間後までになんとかしてくれ、というストーリーとなっています。

行える操作は日時を指定した列車の検索、指定席・自由席の予約から支払い、予約済み座席のキャンセルのみで、これだけ見ると特段の派手さはありません。しかし、細かく内容を噛み砕いていくと極めて複雑なアプリケーションであることがわかります。
一つでも条件のマッチを間違えると運行していない区間を走る列車を予約できたり、多重発券を行ってしまったりと即座に破綻を起こしますし、普段何気なく使われている「窓際の席ならどこでもよい」「3人まとめて予約したらなるべく近くの座席を取る」などの指定がいかに凶悪な条件かを思い知らされることとなります。


3. フロントエンドについて

フロントエンドはVue.jsを用いSPAとして実装されています。操作方法がわかりやすいUIとしました。ベンチマークとスコアには全く関係ありません。
ただし、検索結果の表示や予約内容の確認など、参考実装通りの挙動をすることを求めました。


4. サーバ環境

アリババクラウドさんの 
ecs.sn1ne.large
を採用しました。
CPUは2コア (Intel(R) Xeon(R) CPU E5-2682 v4 @ 2.50GHz)、メモリは4GBの、オーバーコミットのないインスタンスです。ネットワーク帯域も100Mbpsです。

ただし、今回のアプリケーションではメモリに全ての切らない環境を再現するために、Linuxにはメモリを1GBしか認識させていません。CPUは2コアで、メモリ1GBの環境を再現しています。
参加者にはこちらのインスタンスを3台提供しました。
デプロイには Docker Compose を採用しており、ホストのUbuntu 18.04にはDockerとNginxのみをインストールしています。

詳しくは ISUCON9本選問題のリポジトリを参照してください。


5. 課題アプリケーションの特徴

5.1. 過去問題との類似性と違い

座席のチケット予約という題材はISUCONにおいて特に目新しいものではなく、ISUCON2 本選とISUCON8 予選で既に2回出題されています。座席の取り合いというトランザクション処理のお手本のような題材であることと、椅子取りゲームというISUCONに絡めやすいネタであることから、出題する立場からすればまず最初に思い付く出題内容と言ってもいいでしょう。

今回の問題で今までと異なる点は、 
特定の席の予約状況の扱いが複雑である
という点です。

例えば、東京-大阪間を運行している列車を考えたとき、特定の座席が東京-大阪という始発駅から終着駅までの全区間において占有されることもあれば、東京-名古屋間のチケットを乗客A、名古屋-大阪間のチケットを乗客Bが取る、というようなパターンもあり得ます。

また、予約時だけではなく座席検索の時点でこの区間を考慮した空席/予約済判定を行わなければならず、安易な実装を行うと大幅にパフォーマンスが低下します。

5.2. 規模

各チューニングポイントについて解説する前に、本アプリケーションの規模について軽く触れておきます。

DBで扱うマスタのレコード量は、それぞれ以下の通りでした。
  • 時刻マスタ : 2,807,913件
  • 列車マスタ : 70,272件
  • 座席マスタ : 3,942件
  • 駅マスタ : 82件
  • 運賃マスタ : 81件
まず目を引くのは時刻マスタの量の多さでしょう。
今回は競技用マシンに搭載されているメモリが1GBと低めに設定されているため、何も考えず全部メモリに載せると容易に搭載されているメモリを食い潰してしまうため、力技で解決することは難しいのも特徴です。

5.3. 特にチューニングの余地があったエンドポイントについて解説

5.3.1. 
列車検索

エンドポイント：
GET /api/train/search

とにかく一番遅いエンドポイントです。全てのシナリオはこの列車検索を通るため、このエンドポイントをいかに速くできるかが重要なポイントです。

初期実装では、列車の発着時間や料金、空席状況を1列車毎にN+1のクエリで取得しています。発着時刻や料金はJOINや副問い合わせを使い、出来るだけクエリ数を削減する必要があります。

空席状況は1列車毎に、「普通席」「普通席(喫煙所付近)」「プレミアム席」「プレミアム席(喫煙所付近)」と4種類の空席状況を個別のクエリで取得しています。これらも10編成×4種別まとめて取得できるようなSQL文を書くことでクエリ数を減らすことができました。

また、インデックスも適切に張る必要がありますが、単純にインデックスを 
train_master
に対して設定するとクエリ結果の順番が列車名順でなくなってしまいます。インデックスを張る場合には、順序にしたがって主キーを設定し、 
ORDER BY
を適切に設定する必要がありました。


5.3.2. 
座席検索

エンドポイント：
GET /api/train/seats

初期実装では乗車区間重複のチェックをアプリケーション側で実装するようになっています。このため、 
reservations
と 
seat_reservations
の間でN+1のクエリが発生しています。

これらのテーブルをJOINし、乗車区間重複のチェックもSQLで行うことで、1度のクエリで空席情報を取得することができます。

乗車区間の重複は、駅IDが順番に並んでいることを利用します。

golang

seatReservationList := []SeatReservation{}

query = `

  SELECT sr.*

  FROM seat_reservations sr, reservations r, station_master std, station_master sta

  WHERE

    r.reservation_id = sr.reservation_id AND

    std.name=r.departure AND

    sta.name=r.arrival AND

    r.date=? AND r.train_class=? AND r.train_name=? AND sr.car_number=?

`

if train.IsNobori {

  query += "AND ((sta.id < ? AND ? <= std.id) OR (sta.id < ? AND ? <= std.id) OR (? < sta.id AND std.id < ?))"

} else {

  query += "AND ((std.id <= ? AND ? < sta.id) OR (std.id <= ? AND ? < sta.id) OR (sta.id < ? AND ? < std.id))"

}



err = dbx.Select(

  &seatReservationList,

  query,

  date.Format("2006/01/02"),

  trainClass,

  trainName,

  carNumber,

  fromStation.ID, fromStation.ID, toStation.ID, toStation.ID, fromStation.ID, toStation.ID,

)


また、このクエリを高速に処理するためにはJOINして検索するためのインデックスを張っておく必要があります。これだけでもこのエンドポイントの処理時間が1/10程度になります。


5.3.3. 
仮予約

エンドポイント：
POST /api/train/reserve


参考実装のロジックを始まりから終わりまで箇条書きにすると次の通りになります。

  • いろいろなチェック
    • 予約可能期間
    • 予約しようとした列車が、止まらない駅で乗降しようとしていないか
    • 予約しようとした列車が、運行していない区間で予約しようとしていないか
  • あいまい予約(ロジック1)
    • 予約シートが自由席ならbreakする
    • 当該列車の1号車から16号車まで全部のシート情報を列挙する
    • リクエストに基づいて、1つの号車内でまとめて人数分取れる席を探す(それを号車分回す)
    • 空いている席を人数分確保できれば、リクエストで空だったシート情報に埋め込む
  • 座席指定予約(ロジック2)
    • 当該列車の予約一覧を取得
      • 予約が見つかれば、予約について乗車区間を計算し、リクエストの区間と重複していないか判定する
        • 区間重複していれば、座席まで重複していないか判定する
    • 予約シートが自由席ならbreakする
  • 運賃計算
  • 仮予約登録
  • 仮予約成功レスポンス

ネストしているのはそのまま参考実装中のforのネストを表現しています。

参考実装のあいまい予約では、あくまでもリクエストで 
空になっているシート情報をあいまい予約ロジックで作って（埋めて）そのまま指定席予約のロジックに通す
実装になっており、すでにあいまい予約ロジックの中で候補席を見つけた時点で予約可能なのは確定なのですから、わざわざ後ろに構えている指定席予約ロジックを通さず即予約でも問題ない事に気づけると、スコアアップに繋がります。　（参考実装では、あいまい予約は 
指定席情報を作るだけ
に過ぎません）

DBをロックしている範囲も広いため、ロックは車両毎にかけ、できるだけロック範囲を限定することで予約重複を避けつつ座席検索が可能になります。

座席指定予約では 
reservations
および 
seat_reservations
でN+1問題が発生しています。参考実装のアプローチは 
同じ列車の予約情報が無ければ確実に予約可能(広範囲)
→ 
乗車区間が被らなければ予約可能(中範囲)
→ 
座席の重複判定(狭範囲)
となっており、同じ列車に対して座席予約を行うと線形に遅くなる実装です。空席情報の取得と同様にテーブルをJOINしてSQLの発行回数を減らす手法が考えられます。


5.3.4. 
予約キャンセル

エンドポイント：
POST /api/user/reservations/:item_id/cancel


アプリケーションの処理は簡単なSELECTとDELETEだけのため、ほとんど対応することはありません。しかしながら、外部の決済APIのキャンセルが遅いため、1リクエストあたり1秒かかってしまいます。

レスポンスに時間がかかる原因が外部APIであることを突き止めることが一つ目のポイントとなります。

ベンチマークの仕様に、

> 60秒間の負荷走行ののちに、5秒以上待ってから、整合性チェックを行います。 このタイミングまでに、外部決済サービスのキャンセルなど処理の整合性をとってください。

と記載されていることから、キャンセル処理はバックグラウンドで実行しても良いことがわかります。これらを元に、決済のキャンセルは5秒以内毎にバッチ処理でバルクキャンセルするという実装を行い、レスポンスを早く返すことができるようになります。

6. ベンチマーカー

ベンチマーカーは大まかに以下の順序でベンチマークを実施します

1. pretest
2. benchmark
3. finalcheck

ベンチマーカーは、課題アプリケーションが以下のような挙動となっている場合、失格判定を下します。
  • 初期実装のまま
    • 列車検索などでタイムアウトが発生するため
  • 静的ファイルに変更が加えられている
  • 検索結果が１件も帰ってこない
  • pretestにおいて、初期データと明らかに異なるデータがレスポンスに含まれている
  • 不正な条件で予約ができる
  • 料金計算が間違っている

6.1. pretest

pretestは実際のベンチマーク処理を行う手前に行われるテストです。
課題アプリケーションとして仕様を明らかに満たせていない場合は即失格とし、次のベンチマーク処理へと進まずに0点のスコアがつけられます

競技が開始したばかりの段階では、このpretestで失格となるチームが多かったように見受けられました。pretestで失格となる状況からいかに（問題を増やさないようにしつつ）抜け出せるかが本選における難所の１つでした。


6.2. benchmark

benchmarkはアプリケーションに負荷をかけつつ、エンドポイントごと成功した回数(これがのちにスコアとして計上されます)を記録します。

available_days
の数値をいきなり大きくする場合はベンチマーカーからの負荷を捌ききれずにタイムアウトとなり、減点されていました。本選の課題アプリケーションはユーザの動きが読みやすく（検索して、予約して、・・・）、alpのようなツールで簡易に調査することでも負荷傾向を調べることが可能でした

HTTPサーバのアクセスログから負荷傾向を調査し、ボトルネックとなっている箇所を適切にピックアップする必要がありました

6.2.1. 基本的なシナリオ

検索から決済完了まで行うごくシンプルなシナリオ(通常シナリオ)や、曖昧予約を行うシナリオが用意されていました。
基本的に、通常シナリオでは課題アプリケーションが正常に動作していれば失格になることはありません。ただし、予約できない条件において予約が成功してしまうと失格となります。

例えば以下のような処理を行い、不正な条件での予約が通らないかチェックしていました
  • 同じ座席を複数予約
  • 指定した列車が止まらないはずの駅の乗車（あるいは降車）するように予約
  • 指定した列車が止まらないはずの区間から乗車（あるいは降車）するように予約
また、予約詳細画面や予約一覧画面では正しい料金を表示する必要があり、この部分もベンチマーカーからチェックが行われていました

一方、曖昧検索を行うシナリオではベンチマーク実施中になんども曖昧検索を行うように実装されていました。そのため、初期の曖昧検索では課題アプリケーションのレスポンスがどんどん遅くなり、タイムアウトで減点され、スコアを稼ぐことができませんでした。


6.2.2. シーズンを表現するシナリオ

本選では参加者が制御できるパラメータとして 
available_days
が用意されていました

ベンチマーカーでは 
available_days
の値に応じて月単位で負荷が上がるようになっていました。加えて、4/29 ~ 5/6 はゴールデンウィーク、7/24 ~ 8/9 には五輪ということで、その期間を含む場合は負荷が増大する仕様となっていました。

available_days
は366まで指定可能（うるう年であるため）で、アプリケーションを限界までチューニングしても、ベンチマーカーはそれを上回る負荷をかけられる見込みでした。値の範囲が広い分適切に設定するのが難しく、現在のアプリケーションの状態を適切に把握しつつ調整する必要がありました。


6.2.3. 異常シナリオ

異常シナリオでは、不正な予約が行えないかチェックしていました。
  • * 存在しない座席の予約
  • 不正な区間で予約
  • 同じ座席を同時に予約
    • ロック機構に不備がないかチェックする目的
不正な予約が通らないよう、条件判定や排他制御を適切に行う必要がありました。

6.3. finalcheck

finalcheckは課金APIから課金情報を取得し、料金と予約の整合性チェックを行います。

予約関連のHTTPハンドラを改修する際、条件判定でバグを発生させてしまったり、処理中にエラーが発生しているにも関わらず成功ステータスを返してしまっていると、benchmarkを乗り越えてもここで失格とされていました。

6.4. 失格判定の不備について

アンケートでは、コード改修を行っていないのに失格判定になる（あるいはその逆の）現象が起きていたとのお声をいただきました。

運営部屋では随時参加者のジョブで出力されたログを確認しており、明らかにベンチマーカーのバグであると思しきログが出ていないかチェックしていました。ですが、アプリケーション側で具体的にどのような改修が行われて得点・判定に至ったのかまではわからないため、失格判定になっていてもそれが異常であると断定できませんでした。

考えられる原因の１つに、一部のテーブルにおいてPRIMARY KEYが設定されておらず、ORDER BYによる順序制御がなかったためにPRIMARY KEYの設定で順序が変わってしまい、pretestで失格判定になる場合がありました。この問題はデータベースに起因しており、課題アプリケーションのコード修正のみで解決しないため、原因追求が難しかったと思われます。


初期スコア

Go言語での参考実装ですが、列車検索が遅すぎて初期スコアが出ません。次の通りDBにIndexを作ると、1500点くらい獲得できます。

create index train_timetable_master01 ON train_timetable_master (date, train_class, train_name, station);



総評

今回のアプリケーションはSQLクエリ一つ一つの実行時間は長くないものの、とにかくクエリ数が多いような問題としました。変動しない情報はメモリに載せることもしつつ、全ては乗り切らないのでメモリだけでは解決しません。多くの処理がSQLで表現できるような条件となっているので、出来るだけクエリ数を減らし、適切なインデックスを張ることが重要なポイントでした。

また、日付を跨ぐようなロジックはないため、日付によるパーティショニングやサーバの分離なども効果があると思われます。区間を考慮した予約の条件が複雑でアプリケーション規模も大きかったため、コンテスト時間中に全ての対策を行うのは困難だったと思われます。


最後になりましたが、お忙しい中参考実装の移植をお手伝い頂いた皆様、事前回答にご協力頂いた皆様、インフラ提供して頂いたアリババクラウドの皆様、櫛井さんをはじめとする主催のLINEの皆様、感謝申し上げます。