ISUCON公式Blog

WINNER'S PRIZE \1,000,000



   

ローカル環境でISUCON9予選のアプリケーションとベンチマーカーはGoとMySQLとDockerがあれば、Macなどローカル環境で動かすことができます。

ソースコードの取得

まず、ソースコード一式をもってきます
$ go get -d github.com/isucon/isucon9-qualify
$ cd $GOPATH/src/github.com/isucon/isucon9-qualify


初期データの作成

ベンチマーカー、アプリケーション両方が使う初期データの生成をします。
$ cd initial-data
$ make

makeを実行するとDocker コンテナの中で初期データの作成を行い、
initial-data/result
に結果が出力され、
webapp/sql
以下へのコピーも行われます。
パスワードの生成があるため、時間がかかります。

画像データの展開

初期データの画像とベンチマーカーが使う画像をダウンロードする必要があります。
ファイルは github releaseからダウンロードできます。1.5GB程度のファイルが2つとなりますので、回線状況のよいところでのダウンロードをおすすめします。

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

初期画像データダウンロード
$ cd webapp/public
GitHub releases から initial.zip をダウンロード
$ unzip initial.zip
$ rm -rf upload
$ mv v3_initial_data upload

ベンチマーク用画像データダウンロード
$ cd initial-data
GitHub releases から bench1.zip をダウンロード
$ unzip bench1.zip
$ rm -rf images
$ mv v3_bench1 images


データベースの作成と初期化

isucariデータベースとユーザの作成をします。
$ cd webapp/sql
$ cat 00_create_database.sql | mysql

mysqlのポート、ユーザとパスワードは環境に合わせて指定してください。
初期化はinit.shを実行します。
$ cd webapp/sql
$ ./init.sh

環境変数によってMySQLのホストやポート番号を変更できます。詳しくはinit.shの中をご覧ください。

アプリケーションの実行

Goの参考実装を起動してみます。
Goのバージョンは1.12以上で確認しています。
$ cd webapp/go
$ GO111MODULE=on go run api.go main.go

この状態で、ブラウザで http://localhost:8000/ をみるとISUCARIのログイン画面がでてくるはずです。
MySQLのホストやポート番号を変更する場合は、
webapp/sql/init.sh
を参考に環境変数を指定してください。試せるログインユーザは
docs/manual.md
に書かれています。

外部サービスの起動

アプリケーションは起動してますが、外部サービスがないため、購入時などにエラーになります。

payment service、shipment service の起動が必要です。

まず、各サービスをbuildします。
$ cd $GOPATH/src/github.com/isucon/isucon9-qualify
$ make

payment service、shipment service とベンチマーカーのバイナリができます。

それぞれ別ターミナルにて、
$ ./bin/payment

port 5555でpaymentが
$ ./bin/shipment

port 7000 で shipmentが起動します。
これでISUCARIが使えるようになるはずです。

ベンチマークの実行

ベンチマーカーがpayment、shipmentサービスを内包しているので、立ち上げた両サービスは停止する必要があります。

アプリケーションのみが起動していることを確認したら
$ ./bin/benchmarker

とすると、initializeのフェーズからベンチマークが動き始めます。

ベンチマーカーとアプリケーションを別ホストで動かす場合は、benchmarkerの起動時にURLを設定する必要があります。詳しくは
README.md
か ヘルプ
benchmarker -h
を参考にしてください。

参考までに MacBook Pro (13-inch, 2018, Four Thunderbolt 3 Ports) Intel Core i5 4 CPU モデルでの初期スコアは
2019/09/13 00:12:29 main.go:180: === final check ===
2019/09/13 00:12:29 main.go:212: 3020 0
{"pass":true,"score":3020,"campaign":0,"language":"Go","messages":[]}

これぐらいになりました。httpsでの通信がないためか予選時よりスコアは高くなっています。

なお上記の環境でベンチマークを実行すると、ファンがうねり、バッテリーが1-2%減ります。用法用量を気をつけて実行してください。よいスコア出ましたら、以下のissueに実行した環境と変更点など報告してもらえると、嬉しいです。

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

どうぞお試しください。
Read more...

9/12 22:00 自己申請による失格について再度検討を行った結果を追記しました
9/12 18:00 平文での格納について一部表現を変更しました
9/11 21:38 本選出場の取り消し無効にする対応を追記しました
9/11 17:30 bcrypt についての一部表現を訂正しました
9/11 17:09 経緯についての追記を行いました

ISUCON9 予選においてレギュレーション違反があり、本選出場者の繰り上がり対応を行いました。

経緯としては、マニュアルの制約事項にあった「パスワードを平文で保存すること禁止する」が該当しました。パスワードの保存の規定については、ISUCONの競技の性質上すべてをチェックすることは難しく、参加者の申告に基づき判断をしております。そのため、競技終了後すぐに判断することは出来ずこのタイミングとなりました。

[9/11 17:30 追記]
運営の対応についていくつかのポイントで説明責任があると考え、追記いたします。

◾️ 問題作成の経緯について
課題アプリケーションのパスワード保存にbcryptを採用した経緯ですが、参考実装を提供する各言語で実装があり、saltの付与やストレッチングが可能であり安全なアルゴリズムとして広く利用されていると判断し、採用しました。

ベンチマークの試行中において、キャンペーン機能による大量の購入リクエストを行うため、ログインが多く発生するようになっています。その結果として課題アプリケーションに問題作成者自ら取り組んだところでも、bcryptによるCPU使用率が目立つことは認識しておりました。

bcryptによる負荷の対処方法として、サーバを追加、軽量なハッシュ関数での代替、あるいは平文での保持を開発チームにおいて想定しましたが、現実の問題として、パスワードなどの情報流出などの事件が発生しており、安全性の高くないアルゴリズムの利用、平文での格納は一般的に推奨されない実装方法だという認識を同時に持ちました。
※9/12 18:00 一部表現を変更しました

ISUCONの課題アプリケーションとして、bcrypt の負荷を解決し高いスコアを出す方法がサーバの追加の一つだけであることは避けたく、bcryptの変更禁止ではなく軽量なハッシュ関数での代替を可能とする、「平文での格納を認めない」という文言をマニュアルに追加しました。例え、bcryptの維持であってもそれを検証することは難しく、参加者からの申告をもって失格の判定を行えば十分であろうと想定しておりました。
※bcryptについて、一部表現を訂正しました

■競技中に繰り返し質問をしたにも関わらず回答が得られなかった内容で失格とするのは問題があるのではないかという意見について
当日のサポートチャットのログを掲載しながら説明いたします。このサポートチャットはそれぞれの日に参加している参加者全員が見ることができるもので、 #general という参加者全員が参加しているチャンネルでのやりとりです。該当のレギュレーションについては何度かサポートチャットで話題にあがりました。

12:12 表記について指摘があり説明を行いました
dis02


14:34 表現について指摘があり修正をすることになりました
dis01


14:41 #announce  という運営からのお知らせのみを発信するチャンネルにて、マニュアルの更新を行ったことを案内しました
dis05


15:16 該当チームより質問がありましたが回答しませんでした
dis03


16:00 再度、該当チームより質問がありましたが回答しませんでした
dis04


当日、2度に渡りメンションがありましたが、回答がされていないことを確認しました。未回答となったことについては不親切であり、参加者の方には不満と感じる点であったかと思います。申し訳ありません。

背景を説明させていただきますと、競技の前提条件をまとめた予選マニュアルにこのように記載しています。
サポートは事前に連絡のあったDiscord のチャンネルにて行いますが、基本的に、予選環境の構成・操作方法やベンチマーカーの処理内容については返答しません。 また、以下のURLにこれまで返答された質問などがまとめられています。 何かある時には一度ご覧ください。
ISUCONでは基本的にマニュアルに記載があることについての質問には未回答としたり「マニュアルを読んでください」という回答を行うことが多くあります。

マニュアルに記載があること以上の情報を提供することは1日目と2日目の情報量に差が出てしまうため慎重に行いたいというのが運営側の姿勢です。競技中もDMにて質問が寄せられることが多いため「個人情報やアカウント情報のやりとり以外の、問題に関するお問い合わせはDMではなく #general にお願いします」といったアナウンスも行っています。

とはいえ、全ての質問に答えないということはもちろんなく、マニュアルの記載ミスやバグと思われる挙動についてはサポートチャットにて回答を行っていました。該当チームより質問があった際は「明確に定義して回答するべきものではない」「マニュアルに書いてある以上のことは答えようがないから未回答でよい」という運営側の判断がありましたが、参加者にとっては不親切であったかと思います。答えられません、といった回答をするべきであったと考えます。

■ ブログに書いてあったことを根拠として処理するのは問題があるのではという意見について
書いてあることが全てではないと考えますので、該当チームの方へ連絡する際にはこのような文面でありました。事実でない場合は失格処分の取り消しを行う体制でした。
ブログに書かれているパスワードの保存の実装が事実であれば、運営チームで
協議した結果としては失格に相当だと判断いたしました。



■ レギュレーション確認が出来ないポイントについて、ブログで情報を公開したことにより後出しで失格となるのは問題があるのではないかという意見について
ブログについては運営から「是非ブログを書いてください」と促しているように、積極的に情報を共有していただき次回の参加者やご自身の振り返りのためにお願いしていることですので問題としては切り分けて考えていただきたいと思っています。ブログを書くと失格になるというのは間違いであり、内容に問題があれば対処を行うというだけですので誤解のないようお願いいたします。

イベントのハッシュタグがついた状態でブログエントリが公開された段階で運営側で協議を開始し対応を行った形ですが、他の参加者の方から「不正行為にあたるのではないか」「データベース上の領域に平文の文字列はそのままの形で保存されるのは平文で保存ではないか」「平文がそのまま保存されているのは明確にルールに違反する」といった連絡が運営側に寄せられました。

前述したように「参加者からの申告をもって失格の判定を行う」というスタンスであったため、公開された情報を元に別のチームの参加者からの問い合わせに応えるという形で失格という判断にいたりました。



追記は以上となります。これまでに9回開催した全てのISUCONの運営窓口を担当していますので、参加者の皆さんが本気で問題と向き合っていることや、一年に一度の楽しみとして参加していただいているのは実感しています。参加者の皆さんには出来るだけ公平な状況で競技に臨んでいただきたいという運営側のスタンスが強く出てしまった点があったかと思いますが、今回のような望まない形で話題になってしまうのは本意では有りません。

これまでにISUCONの運営に関わってきていただいた多くの皆さん、楽しいと言ってくださる参加者の皆さんに対して誠意を持って運営を行ってきたと思いますので、これからも楽しく、挑戦しがいのある問題や環境を作っていけるよう、皆様のご協力をいただければ幸いです。


ISUCON9 運営実行委員会 櫛井

[9/11 21:38 追記]
運営チームで協議をおこない、本選出場者の繰り上がり対応が適切ではないと判断したため本選出場の取り消しを無効とすることとしました。なお、繰り上がりとなったチームについてはそのまま本選出場できるものとします。
自己申告により本選出場辞退されたチームについては意向を確認中で、希望されれば本選出場できるものとします。特にレギュレーションなどで定義していませんが、運営判断ということでご理解いただければと思います。

[9/12 22:00 追記]
チーム「H::W::A::Abyss::Abyss::Abyss」は競技後にレギュレーション違反の自己申請があり失格とさせていただきました。レギュレーション違反対応の再検討の際、自己申請による失格についても再度検討を行い、運営の方針変更による失格とさせていただきました。
Read more...

予選の問題作成を担当したメルカリの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やソースコードを読ませていただくと、ひとつひとつ丁寧に改善したことで出た本当に素晴らしい結果だと認識しております。予選を通過した皆様が本選でもよい結果をだすことを信じております。

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


Read more...

↑このページのトップヘ