予選の問題作成を担当したメルカリのkazeburoです。

ISUCON9の予選に参加していただいた皆さま、ありがとうございました。
お楽しみいただけましたでしょうか。

また、主催の941さんをはじめとするLINEの皆様、ポータルの作成と運用をやっていただいたさくらインターネットの皆様、問題作成と事前回答に協力にいただいた皆さま、サーバ環境を提供していただいたアリババクラウドの皆さま、本当にありがとうございました。

問題の公開

今回の予選問題のソースコード、データ、およびプロビジョニングに使用した設定ファイルなどは以下のリポジトリで公開しております。アプリケーション、ベンチマーカーを起動する手順もありますので、手元で挑戦することもできるかと思います。

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

蛇足ですが、本リポジトリのコミット数は1,700以上、PRも400件以上あり、これまでのisuconのコードの中でも規模の大きなものとなっています。

課題アプリケーション

今回課題となったアプリケーションは、椅子を売りたい人/買いたい人をつなげるフリマアプリ「ISUCARI」です。
a1

参加者より「弊社の椅子が勝手に売られている!」などの声も上がった商品画像は、941さんより提供していただきました。

新着商品タイムライン、カテゴリ・ユーザごと商品一覧、取引をしている商品一覧や商品詳細といったページがあり、購入や売れた商品の配送に関わる機能もあります。ソースコード中の webapp/docs/APPLICATION_SPEC.md にアプリケーションの使い方を簡単にまとめてあります。予選に参加したけど見ていない方、これから問題にチャレンジする方も参考にしてもらえると良いかと思います。

アプリケーションの参考実装のソースコードとは別に、2つの外部サービスである「決済サービスAPI」「配送サービスAPI」があり、購入や配送の際にアプリケーションからこれらのAPIと通信を行います。

ISUCARIは「安全なカード決済」・「お互い匿名で安心配送」をうたってますので、決済情報がウェブサービスに渡らないようにする非通過化を実装しています。CORSにより決済情報を直接決済サービスAPIに渡し、一時的なtokenのみがアプリケーション内で扱われるようになっておりました。また、配送サービスAPIを介することでお互いの住所を知らせず、匿名で椅子が取引されるサービスとなっています。

フロントエンドについて

今回の問題のフロントエンドはReact.jsを用いたほぼ完全なSPAとして実装されており、サーバ側は常に同一のstaticなHTMLを返すアーキテクチャとなっていました。

フロントエンド側でReact.jsによるDOMレンダリングが行われた後はログイン状態の判定、データの取得、前述した決済サービスAPIとの通信をフロントエンド側から直接行っていました。この構成にすることで言語に関わらず初期実装では固定されたassetsを返すのみとなっていました。

今回のAPIはコードを読むだけでどのような用途に使われるのかを読み解くのは簡単ではなかったので、アプリケーションを実際に動かすことでなんのために使われるエンドポイントであるかを直感的に理解できるようにしています。

サーバ環境

ISUCON9 予選では、アリババクラウドの東京リージョンの指定したサーバインスタンスを最大3台まで起動して利用できるようにしました。

今回利用したインスタンスのタイプは「ecs.sn1ne.large」という vCPU数2個、メモリ4GBというスペックで、ストレージには「Ultra クラウドディスク」を使いました。ecs.sn1ne.largeはCPU非共有型のインスタンスで安定した性能が確保されています。インターネット側の通信は最大 100Mbps、VPC内の通信は1Gbpsまで通信ができる環境となります。ubuntu 18.04 LTSをベースに問題のソースコード、データベース(MySQL)、リバースプロキシ(nginx)、アプリケーションサーバ(Go)が起動するOSイメージを参加者に共有し、インスタンスはこのイメージから起動する形としました。

ベンチマークは3台のうち、指定された1台のインターネット側のIPアドレスに対して検証と負荷のリクエストを送ります。1台よりも多くのインスタンスを使う場合は、最初の1台からリクエストを振り分ける必要があり、どうサーバを使い分けるかも問題を解く上で重要になります。

ベンチマーカーを実行したインスタンスは、12 vCPUの「ecs.sn1ne.3xlarge」を利用しています。同じ東京リージョンに設置しました。
※初稿の公開時、インスタンスのモデルが正しくなかったため訂正しました

AOSSL化

OSイメージにはSSLの証明書が含まれており、ベンチマーカーからはhttpsでのリクエストを行いました。決済や配送のAPIも当然httpsでのリクエストが必須で、常時SSL化の環境が実現されてました。

共有したOSイメージにて起動した状態では、nginxの設定がubuntuのパッケージでインストールしたままの、ほぼデフォルトで状態であるため、ベンチマーク中にnginx が使うCPUが高くなります。パフォーマンスを出すためにはいくつかのチューニングが必要でした。HTTP/2を有効にしたチームが多くあったかと思います。

なお、HTTP/2でのリクエストが行えるよう、ベンチマーカーのGoのバージョンは
Transport.ForceAttemptHTTP2
をサポートする、リリースされたばかりの 1.13 を利用しています。

データ量

初期データは商品数 50,000件、ユーザ数 4,000人、カテゴリ数 43件あり、合計で200MB程度となっています。商品のうち90%が10%のユーザから出品され、400人が100個以上出品、のこりは数個というかなり偏っている状態となっていました。また取引が完了した商品が30%ほどありました。

また、購入者が購入する親カテゴリはそれぞれ1つに決まっており、ソファーカテゴリを購入するユーザはソファーカテゴリのみを購入している状態となっておりました。

スコア、ベンチマーク、キャンペーン

今回のISUCONでは、例年と違い、スコアはリクエスト数から計算されるものではなく、取引が完了した椅子の価格の合計をベースに次の計算式でスコアとしています。単位はISUCON8本選で仮想通貨として取引されたイスコインです。
取引が完了した商品(椅子)の価格の合計(イスコイン) - 減点 = スコア(イスコイン)

減点は、レスポンスのタイムアウトやコンテンツに不足がある場合にエラーの内容に応じて行われます。

スコアを最大化するためには、よりたくさんの取引が完了することが必要ですが、ベンチマーカーは出品した上で各APIの回遊をし、購入処理となるため、各APIの高速化が必須となります。なお、初期の段階では商品は100イスコインでしか出品されません。

キャンペーン機能

アプリケーションの初期化エンドポイントである
/initialize
campaign
というキーの値で 0 よりも大きな数字を返すことで、キャンペーン機能を有効にすることができます。数字は0から4までとなり、数字が大きくなると同時にアクセスするユーザも増えていきます。これはISUCON3でのworkload、ISUCON8本選でのSNSシェア機能に着想を得た機能です。

さらに、人気者出品と私たちが呼んでいるイベントが起きます。人気者出品ではあるユーザが商品を1つ出品をすると、多くのユーザがその商品を目指して購入リクエストを送ってきます。人気者出品は8秒ごとに発生し、取引が正常に完了すれば、ISUCARIサービスが信頼を得て、出品される商品の単価があがっていきます。

高いスコアを出すためには、キャンペーン機能を最大まで上げて同時アクセス数を増やし、さらに人気者出品で発生する1つの商品の負荷の集中を緩和して、出品される商品の単価をあげていく必要がありました。

参照実装

ISUCON9予選で、最適化の中心となった主だったエンドポイントについて紹介します。

新着・カテゴリ新着・ユーザごと新着商品

全ての商品、指定されたルートカテゴリの商品、ユーザごとの出品商品がならぶエンドポインです。
GET /new_items.json
GET /new_items/%d.json
GET /users/%d.json
がこれにあたります。

初期状態ではデータベースのインデックスが不足していたり、カテゴリ、出品者、購入者とわかりやすいN+1がありました。ここを改善していくと、着実にスコアがあがったかと思います。

カテゴリについては更新がありませんでしたので、ソースコードに直接書いたチームが多かったと思われます。その過程でカテゴリのネタに気づいたチームも多かったようです。出品者・購入者についてはJOINで取得するか、必要なユーザ情報をIN句を使い一気に取得してアプリケーションの中でデータを保管するなどの方法でアプローチしたチームが多かったようです。

取引一覧

ユーザが出品した商品あるいは購入した商品が並びます。SQLで
(buyer_id = ? OR seller_id = ?) 
という条件があり、さらに、購入された商品または購入した商品については外部サービスである配送サービスAPIを参照し、配送のステータスを取得する処理がありました。

1つ目のORクエリに関しては、次のようにUNIONクエリをつかった形式に書き換えることでINDEXで十分に絞り込みが可能な状態になります。
SELECT * FROM items WHERE seller_id = ?
UNION
SELECT * FROM items WHERE buyer_id = ?

過去のISUCONでもこの解法があったかと思います。

2つ目の課題のとなる配送サービスAPIですが、APIのレスポンスにかかるレイテンシがベンチマーク走行中のみ遅延を入れて 0.8秒かかるようにしてあります。アクセスログの分析をしたチームは気づいたかと思いますが、取引中の商品が多くなればレスポンスがかなり遅くなります。

この外部APIが遅い問題を解決する方法として、必要な回数のAPI呼び出しを非同期・並列で行うことでかかる時間を短くする方法が考えられます。また、参照実装に同梱のドキュメントをみると実は必要のないAPIアクセスが多くあり、実際にはほとんどのアクセスをせずに済むことがわかります。

ただ、ベンチマーカーでのチェックの仕様により、取引一覧でのAPIアクセスは実は必要がなく、配送ステータステーブルの情報を表示すればエラーにならないようになっておりました。

購入

購入には上で説明したキャンペーン機能により多くのユーザが、1つの商品に対して一挙に押し寄せます。さらに購入時にはトランザクション中に2つの外部サービス、配送サービスAPIと決済サービスAPIに対してリクエストを送るようになっていました。

このため、ロック待ちが多く発生し、エラーやタイムアウトが多く発生し、単価の上昇がなくなったり、ベンチマーク自体が失敗になるなどの状況が生まれます。

対策としては、mutexやflockによる排他制御が考えられます。1つの商品につき1つのトランザクションのみが開始されるようアプリケーションにて制御を行い、ロックが解放された直後のトランザクション開始前に商品が購入できるステータスにあるかどうかをチェックすると、データベースに負荷がかからず素早くレスポンスが可能となるかと思います。そのほかに外部サービスの呼び出しを並列化するなどの対策があったようです。

なお、決済サービスは同じ商品に対して複数回購入するとクリティカルなエラー扱いになり、一度発生しただけでベンチマークが失敗するようになっていました。また決済サービスには失敗するカード番号が存在しており、必ず成功するわけではありませんでした(失敗するカード番号についてはドキュメントに記載されておりません)。

ログイン

上記の対策をしてくると、最後に残るのがログイン時のbcryptの処理です。ISUCON8の本選でもbcryptが使われており、記憶に残っていた参加者も多かったようです。

bcryptの処理には0.1秒ほどかかり、CPUもかなり必要とします。そこでCPU使用率をさげるため、sleepをいれて処理を遅らせるなどの対策でログインをさぼると、人気者出品の発動に必要な人数が集まらず、スコアが上がらなくなってしまいます。

今回の予選では3台までサーバインスタンスが利用可能でしたので、ログインが他のアプリケーションの動作に影響を与えないよう、サーバインスタンスを追加してログイン処理専用とする方法も考えられたでしょう。


講評

今回ISUCON9の予選問題は、2つの外部サービスの導入、複数台構成に加えてアプリケーションの内容も増えて盛りだくさんな内容でした。ベンチマーカーの実装や初期データの生成、サーバのプロビジョニングと運営にとっても課題が多くありました。いくつかの不備がありましたが、多くの参加者の皆様に8時間にわたり取り組むことができるものが提供できたのではないかと思います。

盛りだくさんなアプリケーションではあるのですが、ひとつひとつのボトルネックを解消すればスコアが着実にあがるように設計し、また分析や実装に多くの時間が使えるようベンチマーク試行によってスコアがバラつかないよう安定させることも意識しておりました。

また、スコアをリクエスト数ではなく、売り上げにしたことも今回の特徴です。そして、アプリケーションが速くなり、いつでも快適に使えるだけではなく、ユーザが求めているものを調べ、ビジネスをより成功させるというのもISUCONの中に含められないかと考えました。

その狙いがあり、今回のアプリケーションでは、初期データにおいてユーザが購入するカテゴリを偏らせ、新着商品一覧でそのユーザが購入するカテゴリにあわせて一覧を返すことで数%ですが、スコアがあがるようになってます。マニュアルにもそれを匂わすことが書いてありました。

予選2日とも、学生の1人チームがトップになったことは私たちにとっても驚きでした。ただ、blogやソースコードを読ませていただくと、ひとつひとつ丁寧に改善したことで出た本当に素晴らしい結果だと認識しております。予選を通過した皆様が本選でもよい結果をだすことを信じております。

改めて、参加していただいた皆様、運営に協力していただいた皆様、マニュアル確認しましょう、ありがとうございました。