調べたこと、作ったことをメモしています。雑多なメモはこっち:https://memo.shimazu.me/

ISUCON10 予選に出てみました

練習もしてなかったのでどうせ本戦通らんでしょ〜という感じでお昼の14時頃から気楽にやり始めたものの、思ったより手詰まりにならず常時やることがたくさんあり、最終的には時間ギリギリまでいろいろ試していました。 最後のベンチマークの結果は1768でした。

時系列を追ってやったことを書いていきます。

はじめの準備

  • vscodesshする
  • localhostでサイトが開けることを確認する
  • gitでソースを管理する
  • etckeeperをいれて/etcをgitで管理する
  • goじゃなくてnodejsを有効にする

アプリの動作確認

まずはじめにベンチマークを回し、動作確認をしました。 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なのに集合処理をしていない・・・

ということで、クエリを1つにしてみることにしました。 まず、latitude, longitudeをひとつのGeometry型のカラムに入れるための初期化スクリプトを1つ増やしました。

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;

また、これを使って以下のようなクエリを投げると、1つのクエリで取ってこれるようになります。

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のお引越し

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の3つにindexが張られていれば良さそうです。 しかし、create index idx on estate(rent, popularity, id)なんてやってもindexは使われていないようです。なんで・・・? 2

ORDER BYの最適化に関する公式のガイドを見てみたところ、どうやらDESCとASCが一緒だとだめだったりするようです。 これは最後まで解決しませんでした。。。

rent >= N and rent < N

2番めに遅いクエリの実際の値をみてみると以下のようなものでした。 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で返すJSONmemcachedに取っておいて、もしキャッシュがあれば使うことにしました。

使うところのコードはこんな感じ。とても雑に検索の内容と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でログインした直後あたり(つまり一番最初)からずっと寝ていたもう一人のチームメンバーが、終了1時間くらい前に起きてきたのでこれをお願いしました。 椅子の縦、横、高さの小さい2辺がドアに入るかを確かめればよいので、それだけをクエリに渡すコードを書いてもらいました。

結果:1768

感想

普段仕事でやっている内容ではないのでその場で勉強しながらでしたが、徐々にスコアが上がっていくのは楽しかったです。 勉強になりそうなので、過去のISUCONなども少しずつ解いていってみたいですね。 他の方のwrite upも楽しみにしています。


  1. 本当はmysqldumpslowを使ったほうが良かったと思いますが、そのコマンドの存在と使い方はコンテスト中に知りました。。。

  2. あとでDiscord見ていた感じだと、idとpopularityを1カラムにまとめてしまえば良いみたいですね。