ISUCON10 予選に出てみました
練習もしてなかったのでどうせ本戦通らんでしょ〜という感じでお昼の14時頃から気楽にやり始めたものの、思ったより手詰まりにならず常時やることがたくさんあり、最終的には時間ギリギリまでいろいろ試していました。 最後のベンチマークの結果は1768でした。
時系列を追ってやったことを書いていきます。
はじめの準備
アプリの動作確認
まずはじめにベンチマークを回し、動作確認をしました。 topを見てみたところ、mysqlが80%, nodeが20%程度CPUを使っていることがわかりました。 つまり、mysqlを別のマシンに載せ替えるだけで20%程度はスコアが上がりそうです。
また、どういう動作をするアプリなのかということをサイトを操作してみて、以下のような点を確認しました。 はじめに全体のおおよその動作を確認することで、コードを読むときに何をしようとしているのかがわかりやすくなったと思います。
- トップページ
- たくさん物件や椅子がでてくる
- 椅子の検索
- 検索項目のチェックボックスがある
- 物件の検索
- 同上
- 椅子の詳細ページ
- 物件もでてくる
- 椅子の購入操作ができる。
- 物件の詳細ページ
- なぞって検索ページ
- いかにも何かありそう
結果：初回ベンチマーク484
Slow Queryの確認
mysqlが重いことがわかったので、Slow Queryのログを有効にし、サイトを手動で動かしてみました。1
- indexがつかわれていなさそう。初期化スクリプトも確認したところ、全く設定されていなさそうだということを確認しました。
- なぞるページを開くと大量のクエリが出る
- なぞるページで広い範囲を検索すると0.5sとかかかる
indexを張ってみる
SQLを思い出すために、alter tableやらcreate indexやらを書いてみました。 適当に、よく使われていそうなestate.rentにインデックスを張ってみて/initializeにPOSTして動作を確認したりしていました。
結果：変化なし
なぞってページの最適化
なぞってページのクエリについてコードを見ながら確認してみたところ、以下のような動作をしていることがわかりました。
- まず最初のクエリでbounding box内に入る全ての物件を取ってくる
- その後、各物件に関してselectを投げて範囲内にあるかST_Containsで確認する
SQLなのに集合処理をしていない・・・
ということで、クエリを１つにしてみることにしました。 まず、latitude, longitudeをひとつのGeometry型のカラムに入れるための初期化スクリプトを１つ増やしました。
ALTER TABLE isuumo.estate ADD place_point GEOMETRY; UPDATE isuumo.estate SET place_point = POINT(latitude, longitude); ALTER TABLE isuumo.estate MODIFY COLUMN place_point GEOMETRY NOT NULL;
また、これを使って以下のようなクエリを投げると、１つのクエリで取ってこれるようになります。
SELECT * FROM estate WHERE ST_Contains(ST_PolygonFromText(%s), place_point) ORDER BY popularity DESC, id ASC LIMIT %d;
最後に、初期化スクリプトにSPATIAL INDEXを足しました。
CREATE SPATIAL INDEX place_point_index ON estate(place_point);
結果： 509 (without SPATIAL INDEX), 627 (with SPATIAL INDEX)
botに503を返す
nodeのCPUがあまりそうだったので、expressでパパっとスキップするmiddlewareを書きました。 正規表現はレギュレーションのドキュメントからコピペしてそのまま貼りました。
const REGEXPS = [ /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, ] module.exports = function (req, res, next) { const ua = req.get('user-agent'); for (regex of REGEXPS) { if (ua.match(regex)) { res.status(503).end(); return; } } next(); }
結果：670
mysqlのお引越し
mysqld.confのbind-addressを消して、nodeサーバーのIPのためのユーザーを作ってあげればOKでした。
mysql> CREATE USER 'isucon'@'[SOURCE_IP]' IDENTIFIED BY 'isucon'; Query OK, 0 rows affected (0.00 sec) mysql> GRANT ALL PRIVILEGES ON *.* TO 'isucon'@'[SOURCE_IP]'; Query OK, 0 rows affected (0.00 sec)
+20%程度かなと思っていたので、まぁ妥当な数字が出たように思います。 CPU使用率はmysqlがほぼ100, nodejsは20%程度でした。 node側のCPUを使い切るのが目標になります。
結果：786
椅子購入クエリの最適化
なんとなく（←ひどい）「悪いUPDATEいるんじゃないかなあ」と思ったので眺めてみたところ、椅子の購入でわざわざSELECTしてからUPDATEしているのを見つけました。 stockがゼロだった場合には404を返す必要があるので、affectedRowsを使って以下のように変更しました。
const id = req.params.id; await beginTransaction(); const result = await query("UPDATE chair SET stock = stock - 1 WHERE id = ? AND stock > 0", [ id, ]) if (result.affectedRows != 1) { res.status(404).send("Not Found"); await rollback(); return; } await commit(); res.json({ ok: true });
結果：851
mysqldumpslowの確認
ここで、次に何をするかを見極めるため、もうすこしslow queryをきちんと見てみることにしました。 mysqldumpslowをつかうとクエリごとの集計結果が見られるということだったので、使い方を調べつつやってみました。
$ sudo mysqldumpslow -s t /var/log/mysql/mysql-slow.log
Reading mysql slow query log from /var/log/mysql/mysql-slow.log
Count: 829 Time=0.08s (65s) Lock=0.00s (0s) Rows=20.0 (16580), isucon[isucon]@[...]
SELECT * FROM chair WHERE stock > N ORDER BY price ASC, id ASC LIMIT N
Count: 351 Time=0.09s (31s) Lock=0.00s (0s) Rows=25.0 (8775), isucon[isucon]@[...]
SELECT * FROM estate WHERE rent >= N AND rent < N ORDER BY popularity DESC, id ASC LIMIT N OFFSET N
Count: 276 Time=0.11s (29s) Lock=0.00s (0s) Rows=20.0 (5520), isucon[isucon]@[...]
SELECT * FROM estate where (door_width >= N AND door_height>= N) OR (door_width >= N AND door_height>= N) OR (door_width >= N AND door_height>=N) OR (door_width >= N AND door_height>=N) OR (door_width >= N AND door_height>=N) OR (door_width >= N AND door_height>=N) ORDER BY popularity DESC, id ASC LIMIT N
Count: 204 Time=0.08s (16s) Lock=0.00s (0s) Rows=25.0 (5100), isucon[isucon]@[...]
SELECT * FROM estate WHERE rent >= N ORDER BY popularity DESC, id ASC LIMIT N OFFSET N
Count: 144 Time=0.08s (11s) Lock=0.00s (0s) Rows=25.0 (3600), isucon[isucon]@[...]
SELECT * FROM chair WHERE price >= N AND price < N AND stock > N ORDER BY popularity DESC, id ASC LIMIT N OFFSET N
Count: 111 Time=0.08s (9s) Lock=0.00s (0s) Rows=25.0 (2775), isucon[isucon]@[...]
SELECT * FROM estate WHERE door_width >= N AND door_width < N ORDER BY popularity DESC, id ASC LIMIT N OFFSET N
Count: 96 Time=0.08s (7s) Lock=0.00s (0s) Rows=25.0 (2400), isucon[isucon]@[...]
SELECT * FROM estate WHERE door_height >= N AND door_height < N ORDER BY popularity DESC, id ASC LIMIT N OFFSET N
Count: 144 Time=0.05s (7s) Lock=0.00s (0s) Rows=1.0 (144), isucon[isucon]@[...]
SELECT COUNT(*) as count FROM chair WHERE price >= N AND price < N AND stock > N
Count: 171 Time=0.04s (6s) Lock=0.00s (0s) Rows=25.0 (4275), isucon[isucon]@[...]
SELECT * FROM estate WHERE rent < N ORDER BY popularity DESC, id ASC LIMIT N OFFSET N
Count: 72 Time=0.09s (6s) Lock=0.00s (0s) Rows=25.0 (1800), isucon[isucon]@[...]
SELECT * FROM chair WHERE color = 'S' AND stock > N ORDER BY popularity DESC, id ASC LIMIT N OFFSET N
Count: 111 Time=0.06s (6s) Lock=0.00s (0s) Rows=1.0 (111), isucon[isucon]@[...]
SELECT COUNT(*) as count FROM estate WHERE door_width >= N AND door_width < N
Count: 69 Time=0.08s (5s) Lock=0.00s (0s) Rows=25.0 (1725), isucon[isucon]@[...]
SELECT * FROM chair WHERE kind = 'S' AND stock > N ORDER BY popularity DESC, id ASC LIMIT N OFFSET N
Count: 78 Time=0.07s (5s) Lock=0.00s (0s) Rows=25.0 (1950), isucon[isucon]@[...]
SELECT * FROM chair WHERE height >= N AND height < N AND stock > N ORDER BY popularity DESC, id ASC LIMIT N OFFSET N
Count: 96 Time=0.06s (5s) Lock=0.00s (0s) Rows=1.0 (96), isucon[isucon]@[...]
SELECT COUNT(*) as count FROM estate WHERE door_height >= N AND door_height < N
Count: 66 Time=0.08s (5s) Lock=0.00s (0s) Rows=25.0 (1650), isucon[isucon]@[...]
SELECT * FROM estate WHERE door_width >= N ORDER BY popularity DESC, id ASC LIMIT N OFFSET N
半分位の時間が
SELECT * FROM chair WHERE stock > N ORDER BY price ASC, id ASC LIMIT N
のクエリに取られていそう・・・
chairの値段順クエリ
price ASCが困っていそうだったので、indexを張ってみた。
CREATE TABLE isuumo.chair ( id INTEGER NOT NULL PRIMARY KEY, name VARCHAR(64) NOT NULL, description VARCHAR(4096) NOT NULL, thumbnail VARCHAR(128) NOT NULL, price INTEGER NOT NULL, height INTEGER NOT NULL, width INTEGER NOT NULL, depth INTEGER NOT NULL, color VARCHAR(64) NOT NULL, features VARCHAR(64) NOT NULL, kind VARCHAR(64) NOT NULL, popularity INTEGER NOT NULL, stock INTEGER NOT NULL, INDEX price_index (price) );
結果：1187
再度mysqldumpslow
Reading mysql slow query log from /var/log/mysql/mysql-slow.log
Count: 302 Time=0.11s (32s) Lock=0.00s (0s) Rows=20.0 (6040), isucon[isucon]@[...]
SELECT * FROM estate where (door_width >= N AND door_height>= N) OR (door_width >= N AND door_height>= N) OR (door_width >= N AND door_height>=N) OR (door_width >= N AND door_height>=N) OR (door_width >= N AND door_height>=N) OR (door_width >= N AND door_height>=N) ORDER BY popularity DESC, id ASC LIMIT N
Count: 348 Time=0.08s (29s) Lock=0.00s (0s) Rows=25.0 (8700), isucon[isucon]@[...]
SELECT * FROM estate WHERE rent >= N AND rent < N ORDER BY popularity DESC, id ASC LIMIT N OFFSET N
Count: 165 Time=0.07s (12s) Lock=0.00s (0s) Rows=25.0 (4125), isucon[isucon]@[...]
SELECT * FROM estate WHERE rent >= N ORDER BY popularity DESC, id ASC LIMIT N OFFSET N
Count: 132 Time=0.08s (10s) Lock=0.00s (0s) Rows=25.0 (3300), isucon[isucon]@[...]
SELECT * FROM estate WHERE door_height >= N AND door_height < N ORDER BY popularity DESC, id ASC LIMIT N OFFSET N
Count: 135 Time=0.07s (9s) Lock=0.00s (0s) Rows=25.0 (3375), isucon[isucon]@[...]
SELECT * FROM chair WHERE price >= N AND price < N AND stock > N ORDER BY popularity DESC, id ASC LIMIT N OFFSET N
Count: 96 Time=0.08s (7s) Lock=0.00s (0s) Rows=25.0 (2400), isucon[isucon]@[...]
SELECT * FROM estate WHERE door_width >= N AND door_width < N ORDER BY popularity DESC, id ASC LIMIT N OFFSET N
Count: 135 Time=0.05s (7s) Lock=0.00s (0s) Rows=1.0 (135), isucon[isucon]@[...]
SELECT COUNT(*) as count FROM chair WHERE price >= N AND price < N AND stock > N
Count: 132 Time=0.05s (6s) Lock=0.00s (0s) Rows=1.0 (132), isucon[isucon]@[...]
SELECT COUNT(*) as count FROM estate WHERE door_height >= N AND door_height < N
Count: 72 Time=0.09s (6s) Lock=0.00s (0s) Rows=25.0 (1800), isucon[isucon]@[...]
SELECT * FROM chair WHERE kind = 'S' AND stock > N ORDER BY popularity DESC, id ASC LIMIT N OFFSET N
Count: 177 Time=0.04s (6s) Lock=0.00s (0s) Rows=25.0 (4425), isucon[isucon]@[...]
SELECT * FROM estate WHERE rent < N ORDER BY popularity DESC, id ASC LIMIT N OFFSET N
Count: 66 Time=0.09s (5s) Lock=0.00s (0s) Rows=25.0 (1650), isucon[isucon]@[...]
SELECT * FROM chair WHERE color = 'S' AND stock > N ORDER BY popularity DESC, id ASC LIMIT N OFFSET N
Count: 96 Time=0.05s (5s) Lock=0.00s (0s) Rows=1.0 (96), isucon[isucon]@[...]
SELECT COUNT(*) as count FROM estate WHERE door_width >= N AND door_width < N
次はestateテーブルに対するdoor_width/heightととrentに関するクエリが時間がかかっているっぽいですね。
door_width/heightにインデックス
とりあえず、door_width/heightにインデックスを張ってみることにしました。
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, INDEX rent_index (rent), INDEX door_size_index_another (door_width, door_height, popularity, id) );
結果：1302
popularity desc, id ascとの苦闘
mysqlコマンドでいろいろcreate indexをしつつexplainを見てインデックスがうまく使われているか見てみました。
SELECT * FROM estate WHERE rent >= N AND rent < N ORDER BY popularity DESC, id ASC LIMIT N OFFSET N
このクエリを最適化しようと思ったとき、rentとpopularity, あとidの３つにindexが張られていれば良さそうです。 しかし、create index idx on estate(rent, popularity, id)なんてやってもindexは使われていないようです。なんで・・・？ 2
ORDER BYの最適化に関する公式のガイドを見てみたところ、どうやらDESCとASCが一緒だとだめだったりするようです。 これは最後まで解決しませんでした。。。
rent >= N and rent < N
２番めに遅いクエリの実際の値をみてみると以下のようなものでした。 SELECT * FROM estate WHERE rent >= 50000 AND rent < 100000 ORDER BY popularity DESC, id ASC LIMIT 25 OFFSET 75;
rent >= 50000 AND rent < 100000で検索をかけてみると、かなりのクエリがこのレンジのようです。 同じようなクエリが多いため、とりあえずクエリの結果をキャッシュしておいて同じクエリならそのまま返すようにすればよさそうです。
ということで、res.jsonで返すJSONをmemcachedに取っておいて、もしキャッシュがあれば使うことにしました。
使うところのコードはこんな感じ。とても雑に検索の内容とqueryParamsなどをキー(memKey)に突っ込んでいます。時間がなかったことが伺えますね・・・
const memjs = require("memjs"); const client = memjs.Client.create(); ... app.get("/api/estate/search", async (req, res, next) => { ... const mGet = promisify(client.get.bind(client)); const mSet = promisify(client.set.bind(client)); const memKey = `${searchCondition}-${queryParams.join('_')}-${pageNum}-${perPageNum}`; try { const result = await mGet(memKey); if (result) { res.setHeader('content-type', 'application/json; charset=utf8') res.send(result); return; } } catch (e) { next(e); return; } ... try { ... const result = { count, estates: camelcaseKeys(estates), }; await mSet(memKey, JSON.stringify(result), {expires: 60}); res.json(result); } catch (e) { ...
公式のmemjsのドキュメントにはcallbackしか書かれていないですが、どうやらこれ、Promiseも返せるっぽいということをあとで気づきました。
あと、物件の入稿をすると結果が変わってしまうので、入稿するとキャッシュを全て破棄するようにしました。
...
await client.flush();
await commit();
res.status(201);
res.json({ ok: true });
結果：1727
door_width, heightのAND/ORを節約
sshでログインした直後あたり（つまり一番最初）からずっと寝ていたもう一人のチームメンバーが、終了１時間くらい前に起きてきたのでこれをお願いしました。 椅子の縦、横、高さの小さい２辺がドアに入るかを確かめればよいので、それだけをクエリに渡すコードを書いてもらいました。
結果：1768
感想
普段仕事でやっている内容ではないのでその場で勉強しながらでしたが、徐々にスコアが上がっていくのは楽しかったです。 勉強になりそうなので、過去のISUCONなども少しずつ解いていってみたいですね。 他の方のwrite upも楽しみにしています。
