ISUCON公式Blog

WINNER'S PRIZE \1,000,000



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

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...

    ※9.14 11:00 ベンチマーカーの不具合による本選出場チームのスコアが正しくなかったため修正しました
    ※9.14 14:38 スコアが正しくなかった2チーム(BruteForce,牡蠣の鋭利な殻が指に突き刺さり利き手を負傷)のスコアを正しいものに修正しました
    ---
    全てのチームのスコアを掲載いたします。再起動試験でfailになっているものも含むため、順位ではありません。あくまで参考値となることをあらかじめご了承ください。


    7744 theorem
    4100 FCCPC_かみのやま温泉
    4072 shallowverse
    3804 FetchDecodeExecWrite
    3642 一口坂46
    3407 がんもどき
    3349 ultra_fast_gopher
    3228 takonomura
    3134 ニル侍
    3086 hoge
    3016 チーム中目黒乗り過ごし
    2971 焼肉ジャンボチキン
    2861 101010
    2844 SunPro
    2837 ウー馬場ーイーツ
    2742 第5西東京市
    2723 今年も運動会被り
    2684 勉強不足の分は有り余る才能でカバーしようかなと思っております
    2676 MN
    2624 へしこず
    2608 カレーおじさん
    2419 牡蠣の鋭利な殻が指に突き刺さり利き手を負傷
    2412 rust_kanzen_rikai
    2404 SNE
    2370 NaruseJun
    2338 メンチカツ
    2335 ヌルポインターマリアユニバース
    2281 百万円ドリブン
    2261 はしもとせいこ
    2210 hidekiy
    2204 😇😇😇
    2158 ふんばり温泉チーム
    2109  curl gotti
    2088 イキリ社会人
    2074 fujiwara組
    2072 team rdk
    2040 京都すいーつ
    2019 じゅうまんこわい
    2012 うどんきれいなGo
    1997 再起動非対応
    1971 チーム4年目
    1966 デュアル同好会
    1965 くすサポISUCON部
    1960 fffff
    1934 酒酒酒
    1868 ラディカル・グッドスピード/脚部限定
    1839 NaNでもないや
    1832 王数軒
    1828 実践入門
    1801 4回目の正直
    1768 kokeshi
    1747 釜中の鯖
    1736 ゆるふわ穏健派
    1727 スタンプラリー
    1721 計算機科学実験及演習5
    1695 イスイスユカイ
    1691 motsu鍋
    1685 ito組
    1684 morupoppo
    1680 しょーなんさいくる
    1665 example.com
    1656 失敗から学ぶISUCONの正しい歩き方 the Revenge
    1648 長濱ねるさんが好きです
    1642 BruteForce
    1637 スライディング土下座
    1635 iwamot solo
    1631 オシャレ怪盗スワロウテイル
    1621 カラアゲネイティブ
    1616 yet-another-houti
    1609 ト
    1605 3y3s
    1601 よしとの部屋
    1601 RE: ゼロから始めるISUCON
    1581 tmp
    1574 Rotten acorns
    1567 駆け出しエンジニア
    1550 oops
    1541 TeamYVR
    1535 Takedashi
    1527 チャーハンとコシャリ
    1516 エンボディパイプ椅子
    1503 金で解決
    1501 ぬるかん
    1479 ひとは
    1475 チーム豚キムチ2307
    1473 クソアニメ同好会
    1461 takoshi
    1446 HRD
    1437 Provisional Penguin
    1422 ( (0) / (0)) ☆祝☆
    1411 yugo
    1399 gosoudan2
    1394 Hound SHIBA
    1392 ニューポート・ジャズ・フェスティバル・イン・斑尾
    1373 アイムウェイ
    1345 Azeit
    1343 できの悪いウォーターフォール開発
    1342 春告鳥
    1341 cryptid
    1334 kb
    1333 むし,うさぎ,いぬ
    1329 console.log
    1320 にんじゃ
    1303 チームおだいばこ
    1302 エンジニアならWebサーバくらい作ったらどうだ
    1302 たんぽぽの上の刺身
    1301 いすこんがさき、しゅうろんはあと
    1300 ここにチーム名を入れる
    1295 ぱろぱろ
    1292 流れ弾
    1281 ノーザンサウザンハウジング
    1277 Excel職人は卒業しました
    1275 jc
    1274 DrinkAndRoot
    1264 bassbone
    1263 Anago
    1257 チームcyma
    1256 都営三田線東急目黒線直通急行日吉行
    1253 INJ
    1247 SNP
    1245 3tai
    1244 カンガルーと犬とゴリラ
    1230 soba
    1224 neko狼乱数
    1221 routemario
    1220 飲んだくれ懸垂派
    1208 turtle
    1205 だじゃれハッピー
    1195 うにふぁ
    1195 :羽付きのお札:
    1189 Full Managed Kitamurakai
    1188 k02
    1184 わかんないッスー!!!
    1173 アサシン
    1168 炉端焼きの目覚め
    1167 and factory 2
    1167 Team YAKARA
    1143 KIDS
    1139 塩昆布
    1138 null
    1129 Trust Rust
    1125 さばかんちゃーはんかれー
    1122 ワンランク上のジロリアン
    1108 boulder
    1090 運用週
    1085 パケットキャプチャーデコ
    1081 riroshi
    1080 L&R
    1078 会社の犬(放し飼い)
    1067 ぼっちでビール飲みたいかっぱ
    1066 四丸八
    1061 jigowatt
    1052 おきのんち
    1049 ムーザルペッパー
    1048 BanBanジー
    1045 proto
    1044 乙なる
    1044 ナナチ
    1040 wangan(老)
    1039 ICE_CREAM_SANDWICH
    1034 bow-wow
    1024 あかべこ
    1018 俺たち
    1017 omu
    1014 dblab
    1008 ムロホシステムB
    1008 yagyu
    1004 大きなかべさん
    998 ishikawa-pro's
    990 ますのすし
    987 reiga.jp
    984 ハスキー犬
    982 GG
    980 ixs
    980 どおふでしょう
    977 かけうどん
    972 ドラゴンせんべい
    970 大佐串枡
    958 🙇🙇‍♀️🙇‍♂️
    952 ls
    949 かしわもち
    947 わたくつオレンジジュース
    945 :p
    945 uh
    934 HIASOBI
    932 りしれ供さ小
    932 寺子屋
    929 hetenko
    921 Kansable
    921 便利三兄弟
    921 Let's not forget to register this year
    916 脆弱性探し隊
    915 クラプラ
    915 たまごくらぶ
    913 TEAM THE BOCCHI!
    912 馬と犬とパンク太郎
    910 カオスの弟子
    902 Goメダ珈琲
    887 裏ドラ
    886 NEMEX
    842 即日安心カードローン
    836 solo
    829 ちゅかちゅかちゅかぴ〜♪
    828 Wani
    828 牡蠣を食べろ
    815 railsへの執着はもはや煩悩の域であり、開発者一同は瞑想したほうがいいと思います。
    814 お仕事ください
    812 チームhammer
    810 痛風予備軍
    808 kyuridenamida
    807 and factory 1
    806 岡山のR社
    803 げんき玉
    793 ぞうさんチーム
    791 しおだいふく
    782 外神田
    779 沈黙の春
    776 umaru
    776 チームビギナーズラックに全振り
    775 ドリーミーメイト
    774 EnableCheats
    770 BPM200
    767 hiyashita_isu
    763 Team Anokomiya'20
    763 ピッッア🍕
    759 サービス:ターミネーター
    749 DREAM TEAM TRIANGLE
    749 システムはともだち
    748 Meister
    734 チームりんご
    731 unselected children
    728 雑用係
    727 んなぁ
    724 おすし
    722 らんちぅ
    720 gathering
    705 whiteboard
    699 ragiFC☆
    698 BYTE KING☆
    696 oupp
    695 ウデムシlab
    692 ちーむレッド
    689 ニューウェーブ
    688 可もなく不可もなく
    685 7D
    683 rm
    683 沼
    682 nobuta
    679 おいら大地
    677 京都動物園
    673 言語学研究室
    672 たまGo
    671 EastLab
    662 コーヒーフロート
    662 カツカツ
    661 calmato
    657 100日後に再起動するSRE
    651 天空騎士団
    648 よんなー
    648 チーム浅はか
    645 ITF.
    644 開運パワーイン
    641 京都おけまる
    638 blackeyes
    635 小和根
    635 北北西に曇と往き隊
    633 元同僚
    630 T3
    630 チームオガヨシ
    629 たまにはトメィトゥじゃなくてカエラ
    629 metsukare
    625 ソフトウェア設計学講座
    624 sun house
    621 肉
    616 mi_chan
    615 kawakichi
    615 3対2
    614 南の島のヨネ
    614 eqval
    613 Ophiuchus_two
    613 Sun Microsystems
    613 白川郷テーマパーク
    612 Wild-Family
    611 Herausforderer
    611 フロントエンドの人
    610 Team++
    610 TT
    608 0x20
    607 Mt.SpringNail
    607 Fratty
    606 チーム鉄塔
    605 茅ヶ崎乃風
    604 CCC
    604 チームV
    601 MCTオイル
    600 KK
    596 炎上に誘いし社畜の牡蠣達
    595 でじぴよ
    589 締切駆動開発
    587 コロッケ
    586 y3110w:D!ff
    583 01c
    578 pasoc
    577 mayahiro
    577 ㌠
    576 the hs7
    572 Bamboo
    571 instant instances
    568 らぴおそろ
    566 ひ
    566 ごはんを食べます
    564 アラフォーだってできるもん!
    562 shimaidon
    562 上智大学エレクトロニクスラボ
    561 エンジョイ侍
    559 いい感じにする人達
    556 抽王吹奏楽団
    554 人望激熱
    550 ふぉるふぉる
    545 FPaS
    540 TED
    539 DONE IS BUTTER THAN PERFECT
    538 kinpira
    537 Team.TadashiMaru
    530 漬物
    529 ろっく
    525 no-preserve-root
    524 Blossom Crown
    522 Chairs
    521 手羽先テクノロジーズ
    518 zenito9970
    518 おしはかる穏健派
    518 d-collapse
    518 つんでれムササビ研究所
    514 元e3
    510 YOT
    509 costcomasters
    505 vector a(3);
    504 チームファイトファイトファイファイビーチ
    502 sotozaki
    501 金は命より重い
    500 TEAMD
    497 iii
    496 Capr1Net
    496 nika
    495 wakiaiai
    488 team ^k.(s|z).k.$
    488 いっけな〜い遅刻遅刻
    487 踊る七面鳥
    486 Orca
    485 Watalab
    484 gekogeko
    483 今別府すてぃお
    483 Gonroku
    478 aimai-chan
    477 okaryo
    476 PuniPuni
    475 まいく
    471 oystersから集いし精鋭たちの集まり
    467 butter-neko
    465 bogosort
    465 DenDen
    465 おすか
    460 脳筋ソルジャー
    459 パスカルダビンチ
    459 橙鯛好き
    457 Ochaneko
    457 チームありか
    445 いろはす
    444 harakan
    444 えび研究所
    442 天空の玉子
    438 ぶるーあいずほわいとどらごんず
    434 限界集落大学院卒
    433 mint
    408 pngn
    405 tentaclez
    403 chicchi
    392 tar
    389 おのこば
    386 百哩人
    382 滑り込みセーフ
    370 YO!HEYHEYHEY!
    368 ツナ缶
    365 はやいTシャツ屋さん
    362 ハッピーヒーローズ
    358 urchin
    327 ごった煮
    312 大反省
    225 .dat
    225 インターネット蟹工船
    219 high-end-tapioca
    216 サクサクモリモリ
    0 映画監督の夢
    0 p2d
    0 70.7kg
    0 Tmp
    0 benchmark.yml
    0 ex-gate
    0 TO
    0 狼と神々の犬部
    0 meguryohika
    0 e-sucon-lab
    0 jspしか触れないorz
    0 sohmens
    0 GJapan
    0 ノルコーポレーション
    0 ponponpain
    0 ワイハリマ
    0 torumagedon
    0 meguro9
    0 ボトムズ
    0  ろどす
    0 チームロアナプラ
    0 格安SIM
    0 papico
    0 あたまのわるいひと
    0 本番落としてごめんなさい
    0 a
    0 ぞい
    0 プリキュアオールスターズ
    0 ichigen
    0 きそたにや
    0 ソレイユ
    0 HHKBは実質0円
    0 Team Zono '20
    0 とりあえずモヒート
    0 da-rio_republic
    0 cat ねこ.nya
    0 hidden soup
    0 Citius
    0 チーム川村
    0 Hound AKITA🐕
    0 ヒメテキ
    0 SUPER OTAKU
    0 ケーキ屋さん見習い
    0 no.module.named
    0 CatBoys
    0 ジェンガクラッシャー
    0 チームおにやんま
    0 刺身屋
    0 ytl
    0 tamanug.nmi
    0 草
    0 チーム人間性
    0 IQ1
    0 山形組
    0 Train
    0 元なんちゃらレンジャー
    0 uemurash
    0 ガヴリールドロップキック
    0 いきなりヘイジーIPA
    0 すしだいどこや
    0 おやおやおやおや
    0 そり
    0 ぶっちぎり
    0 ブラザーズ!
    0 Engagement
    0 果報は寝て待て.dev
    0 ssh
    0 24-200
    0 waiwai
    0 大和田純愛組
    0 :thinking_face:
    0 デデデ20
    0 Ramanujan
    0 DONE IS BETTER THAN PERFECT
    0 shakuGo
    Read more...

    ISUCONについての理解、問題の解き方について深く学ぶことができるオンラインイベント「ISUCON 夏期講習 2020」を開催しました。

    当日は、ISUCON9優勝の白金動物園のメンバーでありISUCON10の出題者でもある @rosylilly さんに講師をしていただきました。






    どんな問題をどのように解くべきかという視点ではなく「8時間で出来ることは少ない」という前提に立ち、事前の準備しておくべきものや心構えについて教えていただきました。ぜひ参考にしていただいて、ISUCON本選出場を目指してください!
    Read more...

    本選の問題作成を担当したさくらインターネットの江草です。
    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

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

    6.1. pretest

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

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


    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. 失格判定の不備について

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

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

    考えられる原因の1つに、一部のテーブルにおいて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の皆様、感謝申し上げます。
    Read more...

    ↑このページのトップヘ