ISUCON公式Blog

WINNER'S PRIZE \1,000,000



商標「ISUCON」利用の
ガイドラインはこちら
スポンサー各社からの応援特設ページ ISUCON10 個人スポンサー

ISUCON10 予選結果と本選出場者決定のお知らせにてアナウンスしているとおり、ISUCON10 予選ではベンチマーカーの不具合により、スコアが 0 点となってしまう、あるいは正常に終了しない事象が発生しておりました。そのため、競技終了後、本不具合を修正した上で運営にて全チームに対して追試を行いました。

予選レギュレーション上は、"競技時間内の最後に記録されたスコア" (最終スコア) を本選出場チームの選出に利用する、と定めています。しかし、本不具合を鑑み、最終スコアが 0 点であったが、再起動を伴う追試にて予選最終結果 25 位のスコアを上回ったチームについて、最終スコアが本不具合によるものではないかを確認しました。

その結果、以下のチームについて、本不具合がなければ最終スコアが 0 点となっておらず、本来であれば本選出場チームに含まれていたと考えられるため、運営チームで協議の結果、別途本選出場チームとして選出することにいたしました。ここでは、「不具合の影響を受けていた本選出場チーム」と呼ぶことにいたします。

予選終了後のアナウンスでは、本来用意していた一般枠・学生枠に加え、不具合の影響を受けていた本選出場チームとなったのは下記の1チームのみであるとアナウンスしていました。

・ 一般枠(不具合の影響を受けていた本選出場チーム)
 ・第5西東京市
・ 学生枠(不具合の影響を受けていた本選出場チーム)
 ・(該当チームなし)

しかし、選手の方からご指摘があり、運営チームにて再度調査したところ、実際は下記の3チームが不具合の影響を受けていた本選出場チームであったことが分かりました。集計の際、下記で追加されている 2 チームが不具合の影響を受けていた事は確認できていましたが、最終的に本選出場者を決定した際、考慮から漏れておりました。

・一般枠(救済出場)
 ・第5西東京市
 ・牡蠣の鋭利な殻が指に突き刺さり利き手を負傷
・学生枠(救済出場)
 ・BruteForce

なお、当初不具合の影響を受けていた本選出場チームとアナウンスされていなかった「牡蠣の鋭利な殻が指に突き刺さり利き手を負傷」「BruteForce」につきましては、本選出場権に変化はございません。

本選出場チームの追加について
上記の判断によって、「牡蠣の鋭利な殻が指に突き刺さり利き手を負傷」「BruteForce」が、不具合の影響を受けていた本選出場チームに変更されたことにより、一般枠25チーム、学生枠5チームそれぞれに1チームずつ空き枠が生じました。

この事実について運営チームで協議した結果、最終提出スコアを基準として、新たに以下の2チームを本選出場チームとして追加することを決定いたしました。

・ 一般枠
 ・curl gotti
・学生枠
 ・ワンランク上のジロリアン

なお上記2チームは、予選終了直後の運営チームによるベンチマーカー実行 (追試) には成功しています。予選終了時、追試については全チームに対して実施していましたが、再起動試験については最低限のチームに対してのみの実施となっておりました。そのため、上記 2 チームについては再起動試験が行われておりません。そして、予選終了から時間が経過しているため、予選終了直後を再現した状態での再起動試験を行うことはできません。

従って、上記2チームはレギュレーションに記載された再起動試験は行われていませんが、運営判断で本選出場チームといたします。

以上を踏まえ、以下の33チームを本選出場チームといたします。

一般枠: 上位25チーム + 不具合の影響を受けていた本選出場2チーム
・FCCPC_かみのやま温泉
・shallowverse (学生)
・FetchDecodeExecWrite
・一口坂46
・がんもどき (学生)
・takonomura (学生)
・ニル侍
・hoge
・チーム中目黒乗り過ごし
・101010
・SunPro
・ウー馬場ーイーツ
・第5西東京市 (不具合の影響を受けていた本選出場チーム)
・勉強不足の分は有り余る才能でカバーしようかなと思っております
・MN
・へしこず
・カレーおじさん
・牡蠣の鋭利な殻が指に突き刺さり利き手を負傷 (不具合の影響を受けていた本選出場チーム)
・SNE
・メンチカツ
・ヌルポインターマリアユニバース
・百万円ドリブン
・はしもとせいこ
・hidekiy
・:innocent::innocent::innocent: (学生)
・ふんばり温泉チーム
curl gotti

学生枠: 上位25チームを除いた学生上位5チーム + 不具合の影響を受けていた本選出場1チーム
・BruteForce (不具合の影響を受けていた本選出場チーム)
・計算機科学実験及演習5
・Azeit
・いすこんがさき、しゅうろんはあと
・アサシン
ワンランク上のジロリアン

失格チームのアナウンス漏れについて
予選終了後のアナウンスでは、最終提出スコアが本選出場圏内であったものの再起動後のチェックによって失格となったチームとして以下のとおり公表していました。

最終スコアが上位25チームに含まれていたが、再起動後のチェックに失敗したため失格
・theorem
・ultra_fast_gopher
・rust_kanzen_rikai
・今年も運動会被り
・NaruseJun

最終スコアが上位25チームを除く学生上位5チームに含まれていたが、再起動後のチェックに失敗したため失格
・Provisional Penguin
・INJ

上記7チームに加え、下記の2チームは、最終提出スコアが本選出場圏内にあったものの、運営チームのベンチマーカー再実行 (追試) によってスコアが 0 点となっていたため失格となっていました。しかし、先のアナウンスの中に含まれておりませんでした。

焼き肉ジャンボチキン
釜中の鯖(学生)

アナウンスは以上です。


ISUCONの予選が始まったのはISUCON3からですが、これまでは土曜と日曜の2日間にわけて開催をしてきました。ISUCON10では初の予選1日開催となり、1日あたりの参加者が最も多い回となりました。このため、当初想定していた以上にインフラ準備に時間がかかってしまい開催時間が遅れてしまったり、ポータルの過負荷により不具合が生じてしまったり、結果発表に時間がかかってしまったり、選定ロジックに不備があり追加で本選出場が決まったりと、参加者の皆さんにはご心配とご迷惑をおかけし申し訳ありませんでした。

参加者の皆さんに良質な問題を届けたい、情報格差や回答環境にバラつきが出ず公平になるよう出来うる限りの準備をしたいという運営側の都合ではありますがご理解いただけると幸いです。今回も参加者の方から指摘があった部分について再度見直しを行い、対応について決定をしました。「運営グダグダだな」と思われても仕方ない面はありますが、参加者の皆さんにとって公平であり、今後も安心して参加していただけるコンテストを目指しておりますので引き続きISUCONを宜しくお願いいたします。
Read more...

ISUCON 10 予選問題作問担当の @yosuke_furukawa です。ISUCON 10 の予選お疲れさまでした。このブログでは、 ISUCON 10 の予選問題の解説と講評を行います。

問題については下記のURLにて公開されています。
http://github.com/isucon/isucon10-qualify

動作確認をしたい場合は README.md を確認の上、検証してみてください。

課題アプリケーション ISUUMO について

ISUCON10 の予選の問題は、 ISUUMO と呼ばれるイスに合う物件を検索するサイトでした。せっかくリクルートが作問担当になったので、リクルートならではのものにしたいのと、ずっと社内ISUCONでポリシーとして持っていた「実際に起きているパフォーマンス問題に近い課題を設定したい」という思いから作りました。
pasted image 0
ISUUMO トップ画面



リクルートらしさを出そうということで、実際に社内で開発している SUUMO を元にしました。 Bot からのリクエストが多かったり、「なぞって検索機能」があるのは実際の状況・機能を元にしています。
pasted image 1
なぞって検索画面



フロントエンドは Next.js で構築し、予め静的ページとしてビルドしています。なぞって画面に Leaflet と呼ばれる地図用ライブラリを使ったり、 なぞった領域の凸包を取るために、 monotone-convex-hull-2d と呼ばれるライブラリを使ったりとかなり工夫しています。興味あればご一読ください。実際にはフロントエンドはチューニング対象ではなく、 実際のリクエストがどう使われてるかを確認するためと、再起動試験時にAPIの整合性の確認をするために使われています。

解説

今回の問題は位置情報を使ったものであり、参加者の皆様にとってはあまり馴染みのないものであったのではないかと思います。いくつかこちらが回答した内容を元に、用意したチューニングポイントについて解説します。

ちなみに予選作問チームの一人がリハーサルで実施した際の最高点数は 8000 点程度でした

安い椅子と物件を検索するAPI(low_priced)にindexが効いてない

トップページにある安い椅子と物件を検索する API があり、そこの SQL に index が効いてません。実際に計測すると、本APIへのリクエスト数が多く Query が遅いことがわかります。
SELECT * FROM chair WHERE stock > 0 ORDER BY price ASC, id ASC LIMIT ?
SELECT * FROM estate ORDER BY rent ASC, id ASC LIMIT ?
ORDER BY を狙って index を貼らないとスコアが上がりにくくなっています。特に初期段階ではベンチマーカーは椅子と物件の検索しかしません。ここをまずは対処する必要があります。

椅子、物件検索 API に index が効いてない

椅子と物件を検索する際に、毎回 popularity が降順 (DESC) であり、 ID の昇順 (ASC) で検索をしています。降順と昇順が組み合わさった ORDER BY は デフォルトでインストールされてる MySQL 5.7 では単純に index を貼っても効きません

SELECT * FROM estate WHERE latitude <= ? AND latitude >= ? AND longitude <= ? AND longitude >= ? ORDER BY popularity DESC, id ASC

降順の index を効かせたかったのと位置情報の検索を見て、 MySQL 8 に上げた人たちも多かったです。

MySQL 8 にしても良いのですが、単純に実施してしまうと 設定の違いにより、パフォーマンスが劣化することもあります。現実に運営側の事前検証ではそこまで点数が上がりませんでした。

popularity は単純にマイナスをつければ昇順に変更できるので想定回答としては負の値をinitialize で入れてしまうか、 MySQL の generated columns を使って 負の値を持った popularity を作ってそこに入れるというのを想定していました。

CREATE TABLE isuumo.estate
(
id INTEGER NOT NULL PRIMARY KEY,
name VARCHAR(64) NOT NULL,
description VARCHAR(4096) NOT NULL,
thumbnail VARCHAR(128) NOT NULL,
address VARCHAR(128) NOT NULL,
latitude DOUBLE PRECISION NOT NULL,
longitude DOUBLE PRECISION NOT NULL,
rent INTEGER NOT NULL,
door_height INTEGER NOT NULL,
door_width INTEGER NOT NULL,
features VARCHAR(64) NOT NULL,
popularity INTEGER NOT NULL,
popularity_desc INTEGER AS (-popularity) NOT NULL # generated column でカラムを追加する
);

ALTER TABLE estate ADD INDEX estate_popularity_id_idx(popularity_desc, id); # popularity_desc にインデックスを貼る


この辺りの ORDER BY を狙って index を貼れるかどうかが最初のポイントでした。ここを抜けるとベンチマーカーからの負荷の掛け方が変化し、なぞって検索や CSV 入稿といった処理が増え、データの量も増えていきます。また、 Bot からのリクエストも増えていきます。

なぞって検索に N+1 がある

なぞって検索の API の内部を詳しく見ると「なぞった範囲の緯度経度の最小値と最大値を取り、一度検索し、 検索にヒットしたものの中で与えられた多角形の範囲内にあるか」を一つずつ確かめている箇所があります。

この部分は所謂 N+1 処理になっています。「多角形の範囲内にあるか」に関しては少し工夫すれば SQL で一度の処理で絞り込めます

緯度経度を POINT 型にして一つにまとめたカラムを事前に用意しておいた上で、 ST_Contains を使って検索すれば一度の検索で多角形の中にある物件を検索できます。

ST_Contains は空間インデックスを使う時に一度、最小外接矩形 (MBR) を使ってオブジェクトを絞り込みます。最小外接矩形 (MBR) の絞り込みは前述の「緯度経度の最小値と最大値を取ってフィルタする処理」に該当します。空間インデックスを使うと前段で絞り込みをやる必要がなくなり、 N+1 も解消することが可能です。

point       POINT AS (POINT(latitude, longitude)) STORED NOT NULL
SELECT * FROM estate WHERE ST_Contains(ST_PolygonFromText(%s), point) ORDER BY popularity_desc, id LIMIT ?

さらにこの処理をする上で SPATIAL INDEX を貼れば上記のSQLにも index が効くようになります。※ MySQL 5.7 では Generated Columns に SPATIAL INDEX を貼る場合は STORED にしなければいけません。
ALTER TABLE estate ADD SPATIAL INDEX estate_point_idx(point);
なぞって検索の処理をどうやって効率化するかは各チームで対応が異なった部分でした。SQLで一度で取るのではなく、アプリケーション側で多角形内にあるかを検証するチームも多かったです。

予選突破した上位陣のブログを読むと、なぞって検索の効率化に早めに着手し解決できているチームが多く、予選通過のキーポイントになっていると感じました。

bot によるリクエストがある

この部分も本家の SUUMO 由来の処理です。 bot からリクエストが来ることが多く、実際には bot のリクエストは椅子購入や物件資料請求といったコンバージョンにつながらないので、503エラーで弾いても問題ないことが当日のマニュアルに記載されています

https://gist.github.com/progfay/25edb2a9ede4ca478cb3e2422f1f12f6#bot-%E3%81%8B%E3%82%89%E3%81%AE%E3%83%AA%E3%82%AF%E3%82%A8%E3%82%B9%E3%83%88
/ISUCONbot(-Mobile)?/
/ISUCONbot-Image\//
/Mediapartners-ISUCON/
/ISUCONCoffee/
/ISUCONFeedSeeker(Beta)?/
/crawler \(https:\/\/isucon\.invalid\/(support\/faq\/|help\/jp\/)/
/isubot/
/Isupider/
/Isupider(-image)?\+/
/(bot|crawler|spider)(?:[-_ .\/;@()]|$)/i

上記の正規表現で Bot からのリクエストかどうかを検出することが可能です。 検出したら 503 のステータスコードで返せば Bot に邪魔されなくなります。

この部分は単に実装されてないだけなので、実装すればある程度の効果を生みます。マニュアルを良く読めば書いてあるので、マニュアルをきちんと読んでいるかがポイントでした。

アプリケーションのミドルウェアで実装するのを想定していましたが、手前においた nginx 部分で対処するチームも一定数いました。どちらで制御しても構いません。言語ごとの正規表現エンジンの実装の差異によって有利不利が働く可能性もありましたが、どちらにせよ大差はなさそうでした。

また、「開始してすぐに実装したものの、スコアに大きな変更がなかった」という旨のエントリを書いている参加者がいましたが、実はベンチマーカーは初期の時点では Bot からのリクエストをほとんど送りません。なぞって検索や椅子、物件の検索が効率化されて負荷レベルが上がってくるとやっと送るようになります。

マニュアルに記載があるからと言って闇雲に実装をするのではなく、ある程度負荷の状況を見ながら優先順位をつけて対処策を実装する必要があります。

estate と chair で DB を別サーバに分ける

DB をテーブルごとに別サーバに分けるのも効果的です。特に chair テーブルと estate テーブル間に JOIN が存在しないため、2つのデータベースに分割して、検索処理を分散させることが可能です。
pasted image 2
App / DB x 2 で3台構成を組む例



今回の問題は DB の CPU が100%に張り付くケースが多いです。しかも1台分のスペックはそこまで強くありません。3台構成の際に App x2 / DB x1 にするのではなく、 App x1 / DB x2 にすることで負荷分散ができます。

検索条件にも Index を貼る

椅子や物件の検索条件はユーザーからの指定に従って検索条件が複雑に変わる仕様でした。

そのため rent や price, height といった条件でも検索に来ることがあります。さらに slow-query のログを詳細に読むと、検索条件にも index が効いておらず、遅いことを示すログが出ています。

pt-query-digest などのクエリ解析ツールを使って遅いクエリを特定すること、それに従って検索条件にも index を貼った方が効果的です。
ALTER TABLE chair ADD INDEX chair_price_idx(price, stock);
ALTER TABLE chair ADD INDEX chair_height_idx(height, stock);
ALTER TABLE chair ADD INDEX chair_kind_idx(kind, stock);

ALTER TABLE estate ADD INDEX estate_rent_door_width_idx(rent, door_width);
ALTER TABLE estate ADD INDEX estate_rent_door_height_idx(rent, door_height);

実はベンチマーカーは price と rent に検索条件が多めに実施してくるように設計してあります。この辺りもアクセスログ、クエリーログをきちんと確認できていたかを問う箇所でした。

ログを出すのを止める

アプリケーション側で SQL やリクエストの内容をロギングしている箇所があります。通常時にはログは出すべきですが、高負荷時にはそこも問題になり得るので、ログをオフにしておく対応をすると多少効果があります。

ちなみに Go の場合 echo というフレームワークを使っています。echo のログが初期に設定されている debug モードだと整形された JSON がログに出力されます。この部分が高負荷状況では特に問題になります。

Bulk Insert を行う

CSV入稿時に1件ずつ INSERT している箇所があります、csvファイルにはデータが1000行存在するため、1000回 INSERTする事になります。 まとめて一気に INSERT する方が良いでしょう。

1000回程度の INSERT なら、さほど効果がないように見えますが、負荷が上がる終盤にこの対応をしていないと CSV 入稿時にタイムアウトする確率が上がります。 CSV 入稿はタイムアウトであっても失敗した場合は即 Fail 扱いになるので、対処しておかなければ失格になる可能性が上がります

その他のチューニングポイントとなり得る箇所

上述した対応を運営側では行い、 8000 点台を記録する事ができました。ただし、この他にもいくつかチューニングできるポイントはあります。以下はブログを読んだ中にあったチューニングのアイデアを抜粋させていただいてます。

  • SELECT FOR UPDATE をやめて、 UPDATE と affected_rows の処理にし、ロックの時間を減らす。
  • OR検索を UNION ALL に変更し、 index が効くようにする。
  • API のレスポンス値をアプリケーションサーバのインメモリにキャッシュし、メモリから返すようにする。

  • すべての処理を適用した際にどこまで点数が上がるのかは運営でもまだ未検証です。

    講評

    皆様お疲れさまでした。
    運営側で参加者のブログを確認していると、やはり「なぞって検索を効率化できたかどうか」、「AppとDBサーバの分割を適切にできているか」が予選通過のターニングポイントのように感じています。
    なぞって検索は敢えて処理が複雑に作られており、読み解くことも中でやってる処理を改善することも難しく感じるように設計されています。

    また、3台構成の設計も従来の常識にとらわれずにリソースの状況とアプリケーションのコード内容から DB を分けるという設計ができるのかがポイントでした。

    尻込みせずになぞって検索の高速化に挑戦し、常識にとらわれずに3台構成の設計ができたチームが突破をしていました。実力とチャレンジスピリットの両方が備わったチームがきちんと突破できていると思います。

    謝辞

    問題の作問やりませんか?と声をかけてくれた 941 さんをはじめ、会場を提供し、夜遅くまで残って会場の整備をしてくれた LINE 社の皆様、本選の問題が忙しいにもかかわらず予選問題の回答とフィードバックをくれた 白金動物園の皆様、直前のインフラ構築で忙しいながらもギリギリまで不具合や障害の解決に付き合っていただいた CyberAgent 社の皆様、誠にありがとうございました。

    最後に非常に拙い運営になってしまいご迷惑をおかけしましたが、最後まで付き合っていただいた参加者の皆様、ありがとうございました。

    Read more...

    2020.09.23 20:15 本選出場チームに変更があったので内容を更新
    --
    ISUCON10 オンライン予選の利用言語比率を公開します。オンライン予選は490チームの参加があり、運営で把握ができたのは468チームとなりました。

    オンライン予選 利用言語比率

    利用率の全体ランキングは以下の通りです。

    Go      276組 59.0%
    Ruby     81組  17.3%
    Python   47組  10.0%
    Nodejs   29組  6.2%
    PHP     18組  3.8%
    Rust      8組  1.7%
    Perl       7組  1.5%
    Elixir     1組  0.2%
    original-ruby 1組  0.2%


    本選出場が決まった33チームに限定すると以下となります。

    Go    28組  84.8%
    Nodejs  2組   6.1%
    Rust    1組  3.0%
    Ruby   1組  3.0%
    PHP    1組  3.0%    

    昨年の言語比率はこちら
    Read more...

    ↑このページのトップヘ