ISUCON 10 予選問題作問担当の @yosuke_furukawa です。ISUCON 10 の予選お疲れさまでした。このブログでは、 ISUCON 10 の予選問題の解説と講評を行います。
問題については下記のURLにて公開されています。
http://github.com/isucon/isucon10-qualify
動作確認をしたい場合は README.md を確認の上、検証してみてください。
ISUUMO トップ画面
リクルートらしさを出そうということで、実際に社内で開発している SUUMO を元にしました。 Bot からのリクエストが多かったり、「なぞって検索機能」があるのは実際の状況・機能を元にしています。
なぞって検索画面
フロントエンドは Next.js で構築し、予め静的ページとしてビルドしています。なぞって画面に Leaflet と呼ばれる地図用ライブラリを使ったり、 なぞった領域の凸包を取るために、 monotone-convex-hull-2d と呼ばれるライブラリを使ったりとかなり工夫しています。興味あればご一読ください。実際にはフロントエンドはチューニング対象ではなく、 実際のリクエストがどう使われてるかを確認するためと、再起動試験時にAPIの整合性の確認をするために使われています。
ちなみに予選作問チームの一人がリハーサルで実施した際の最高点数は 8000 点程度でした。
降順の index を効かせたかったのと位置情報の検索を見て、 MySQL 8 に上げた人たちも多かったです。
MySQL 8 にしても良いのですが、単純に実施してしまうと 設定の違いにより、パフォーマンスが劣化することもあります。現実に運営側の事前検証ではそこまで点数が上がりませんでした。
popularity は単純にマイナスをつければ昇順に変更できるので想定回答としては負の値をinitialize で入れてしまうか、 MySQL の generated columns を使って 負の値を持った popularity を作ってそこに入れるというのを想定していました。
この辺りの ORDER BY を狙って index を貼れるかどうかが最初のポイントでした。ここを抜けるとベンチマーカーからの負荷の掛け方が変化し、なぞって検索や CSV 入稿といった処理が増え、データの量も増えていきます。また、 Bot からのリクエストも増えていきます。
この部分は所謂 N+1 処理になっています。「多角形の範囲内にあるか」に関しては少し工夫すれば SQL で一度の処理で絞り込めます。
緯度経度を POINT 型にして一つにまとめたカラムを事前に用意しておいた上で、 ST_Contains を使って検索すれば一度の検索で多角形の中にある物件を検索できます。
ST_Contains は空間インデックスを使う時に一度、最小外接矩形 (MBR) を使ってオブジェクトを絞り込みます。最小外接矩形 (MBR) の絞り込みは前述の「緯度経度の最小値と最大値を取ってフィルタする処理」に該当します。空間インデックスを使うと前段で絞り込みをやる必要がなくなり、 N+1 も解消することが可能です。
さらにこの処理をする上で SPATIAL INDEX を貼れば上記のSQLにも index が効くようになります。※ MySQL 5.7 では Generated Columns に SPATIAL INDEX を貼る場合は STORED にしなければいけません。
予選突破した上位陣のブログを読むと、なぞって検索の効率化に早めに着手し解決できているチームが多く、予選通過のキーポイントになっていると感じました。
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
上記の正規表現で Bot からのリクエストかどうかを検出することが可能です。 検出したら 503 のステータスコードで返せば Bot に邪魔されなくなります。
この部分は単に実装されてないだけなので、実装すればある程度の効果を生みます。マニュアルを良く読めば書いてあるので、マニュアルをきちんと読んでいるかがポイントでした。
アプリケーションのミドルウェアで実装するのを想定していましたが、手前においた nginx 部分で対処するチームも一定数いました。どちらで制御しても構いません。言語ごとの正規表現エンジンの実装の差異によって有利不利が働く可能性もありましたが、どちらにせよ大差はなさそうでした。
また、「開始してすぐに実装したものの、スコアに大きな変更がなかった」という旨のエントリを書いている参加者がいましたが、実はベンチマーカーは初期の時点では Bot からのリクエストをほとんど送りません。なぞって検索や椅子、物件の検索が効率化されて負荷レベルが上がってくるとやっと送るようになります。
マニュアルに記載があるからと言って闇雲に実装をするのではなく、ある程度負荷の状況を見ながら優先順位をつけて対処策を実装する必要があります。
App / DB x 2 で3台構成を組む例
今回の問題は DB の CPU が100%に張り付くケースが多いです。しかも1台分のスペックはそこまで強くありません。3台構成の際に App x2 / DB x1 にするのではなく、 App x1 / DB x2 にすることで負荷分散ができます。
そのため rent や price, height といった条件でも検索に来ることがあります。さらに slow-query のログを詳細に読むと、検索条件にも index が効いておらず、遅いことを示すログが出ています。
pt-query-digest などのクエリ解析ツールを使って遅いクエリを特定すること、それに従って検索条件にも index を貼った方が効果的です。
実はベンチマーカーは price と rent に検索条件が多めに実施してくるように設計してあります。この辺りもアクセスログ、クエリーログをきちんと確認できていたかを問う箇所でした。
ちなみに Go の場合 echo というフレームワークを使っています。echo のログが初期に設定されている debug モードだと整形された JSON がログに出力されます。この部分が高負荷状況では特に問題になります。
1000回程度の INSERT なら、さほど効果がないように見えますが、負荷が上がる終盤にこの対応をしていないと CSV 入稿時にタイムアウトする確率が上がります。 CSV 入稿はタイムアウトであっても失敗した場合は即 Fail 扱いになるので、対処しておかなければ失格になる可能性が上がります。
SELECT FOR UPDATE をやめて、 UPDATE と affected_rows の処理にし、ロックの時間を減らす。 OR検索を UNION ALL に変更し、 index が効くようにする。 API のレスポンス値をアプリケーションサーバのインメモリにキャッシュし、メモリから返すようにする。
すべての処理を適用した際にどこまで点数が上がるのかは運営でもまだ未検証です。
運営側で参加者のブログを確認していると、やはり「なぞって検索を効率化できたかどうか」、「AppとDBサーバの分割を適切にできているか」が予選通過のターニングポイントのように感じています。
なぞって検索は敢えて処理が複雑に作られており、読み解くことも中でやってる処理を改善することも難しく感じるように設計されています。
また、3台構成の設計も従来の常識にとらわれずにリソースの状況とアプリケーションのコード内容から DB を分けるという設計ができるのかがポイントでした。
尻込みせずになぞって検索の高速化に挑戦し、常識にとらわれずに3台構成の設計ができたチームが突破をしていました。実力とチャレンジスピリットの両方が備わったチームがきちんと突破できていると思います。
最後に非常に拙い運営になってしまいご迷惑をおかけしましたが、最後まで付き合っていただいた参加者の皆様、ありがとうございました。
問題については下記のURLにて公開されています。
http://github.com/isucon/isucon10-qualify
動作確認をしたい場合は README.md を確認の上、検証してみてください。
課題アプリケーション ISUUMO について
ISUCON10 の予選の問題は、 ISUUMO と呼ばれるイスに合う物件を検索するサイトでした。せっかくリクルートが作問担当になったので、リクルートならではのものにしたいのと、ずっと社内ISUCONでポリシーとして持っていた「実際に起きているパフォーマンス問題に近い課題を設定したい」という思いから作りました。
ISUUMO トップ画面
リクルートらしさを出そうということで、実際に社内で開発している SUUMO を元にしました。 Bot からのリクエストが多かったり、「なぞって検索機能」があるのは実際の状況・機能を元にしています。
なぞって検索画面
フロントエンドは 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 ?ORDER BY を狙って index を貼らないとスコアが上がりにくくなっています。特に初期段階ではベンチマーカーは椅子と物件の検索しかしません。ここをまずは対処する必要があります。
SELECT * FROM estate ORDER BY rent ASC, id ASC LIMIT ?
椅子、物件検索 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つのデータベースに分割して、検索処理を分散させることが可能です。
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 点台を記録する事ができました。ただし、この他にもいくつかチューニングできるポイントはあります。以下はブログを読んだ中にあったチューニングのアイデアを抜粋させていただいてます。すべての処理を適用した際にどこまで点数が上がるのかは運営でもまだ未検証です。
講評
皆様お疲れさまでした。運営側で参加者のブログを確認していると、やはり「なぞって検索を効率化できたかどうか」、「AppとDBサーバの分割を適切にできているか」が予選通過のターニングポイントのように感じています。
なぞって検索は敢えて処理が複雑に作られており、読み解くことも中でやってる処理を改善することも難しく感じるように設計されています。
また、3台構成の設計も従来の常識にとらわれずにリソースの状況とアプリケーションのコード内容から DB を分けるという設計ができるのかがポイントでした。
尻込みせずになぞって検索の高速化に挑戦し、常識にとらわれずに3台構成の設計ができたチームが突破をしていました。実力とチャレンジスピリットの両方が備わったチームがきちんと突破できていると思います。
謝辞
問題の作問やりませんか？と声をかけてくれた 941 さんをはじめ、会場を提供し、夜遅くまで残って会場の整備をしてくれた LINE 社の皆様、本選の問題が忙しいにもかかわらず予選問題の回答とフィードバックをくれた 白金動物園の皆様、直前のインフラ構築で忙しいながらもギリギリまで不具合や障害の解決に付き合っていただいた CyberAgent 社の皆様、誠にありがとうございました。最後に非常に拙い運営になってしまいご迷惑をおかけしましたが、最後まで付き合っていただいた参加者の皆様、ありがとうございました。
