ISUCON10 予選敗退^H^H突破した

id:uzulla、id:moznion と共に curl gotti というチーム名で出場しました。このメンバーでやるのは去年に引き続き 2 回目。

三行で

• 最高得点 2125 で予選通過ならず
  • 繰り上がり当選した！！！
• ほぼいつもの力が出せた。ので実力不足である。。
• とても楽しめた良問だった。ありがとうございます

多分この辺の施策をやったんだと思う

• condition.json を静的に返す
• 雑に INDEX 張る
• features の LIKE 検索を正規化して撲滅
• xxxRangeId カラムを追加
• なぞって検索の N+1 改善
• PHP のチューニング
• DB のチューニング
• ORDER BY popularity DESC, id ASC をどうにかする
• DB 2 台構成に
• Bot に 503 を返す

自分が考えたことや手を動かしたことは分かるんだけど、それ以外のチームメンバーがやったことはあまり把握していないので事実とは違う可能性がある。

アプリケーション概観を掴んで作戦を立てる

とりあえず読み慣れてる Ruby でコードを全部読んだ。LeafCage/foldCC.vim は最高。

vim の fold が快適で他のエディタに移れない

チームの scrapbox にエンドポイント一覧ページを作り、各エンドポイントが何をやっているかをそこに書き込んでいった。

全部読んだのでアプリケーション概観を書いて情報共有。

今思うと GET /api/recommended_estate/:id の SQL 素通りしたのマジかよってなるんだけど、当時はザッと見て「見てるカラム数少ないし INDEX 張るだけでなんとかなるんちゃう」って思っていた。。

この辺りでベンチ実行できたので alp, pt-query-digest を採取。まぁ GET /api/chair/search, GET /api/estate/search から倒そうねって感じになり、

• レギュレーション通りに Bot に 503 を返せるように＆ condition.json を静的に返す
• 雑に INDEX 張って次を考える
• features の LIKE 検索を正規化

の 3 ルートに分岐した。僕は INDEX を担当したので

-- GET /api/estate/low_priced 用
alter table isuumo.estate add index rent_and_id(rent, id);

-- GET /api/recommended_estate/:id 用
-- door_width, door_height は一旦無視
alter table isuumo.estate add index popularity(popularity);

-- GET /api/chair/low_priced 用
-- order by 狙いで stock は無視
alter table isuumo.chair add index price_and_id(price, id);

を張った。ここでも recommended_estate の SQL を考えるのを諦めていることがわかってツラい。

xxxRangeId カラムを追加

「検索をどうしたら良いか何も分からん。単体で INDEX 張りまくって INDEX マージに任せるか！ MySQL 8.0 にしたら賢くなって勝つるんじゃね？」みたいな雑談をしつつ (割と本気だったけど、今回クエリキャッシュもかなり効いていたので、8.0 選ばなくて良かったのかもしれない)、どんな複合インデックスにしたら良いのか何も分からんのでとりあえずベンチマーカーが送ってくるクエリパラメータを眺める。

   8 depthRangeId=0&page=0&perPage=25
   1 depthRangeId=0&page=1&perPage=25
   1 depthRangeId=0&page=2&perPage=25
   4 depthRangeId=0&page=3&perPage=25
   1 depthRangeId=0&page=4&perPage=25
  15 depthRangeId=1&page=0&perPage=25
   3 depthRangeId=1&page=1&perPage=25
   3 depthRangeId=1&page=2&perPage=25
   3 depthRangeId=1&page=3&perPage=25
   6 depthRangeId=1&page=4&perPage=25
   9 depthRangeId=2&page=0&perPage=25
   2 depthRangeId=2&page=1&perPage=25
   5 depthRangeId=2&page=2&perPage=25
   2 depthRangeId=2&page=4&perPage=25
   8 depthRangeId=3&page=0&perPage=25
   2 depthRangeId=3&page=1&perPage=25
   5 depthRangeId=3&page=2&perPage=25
   3 depthRangeId=3&page=4&perPage=25

あれ、depth や width そのものじゃなくて ID 送ってきてるんだ！ なるほど min,max 取り出してたコードはそういうことか、って言いつつ、「初期データ弄るねー」って言ってカラム追加してデータ移行。

alter table isuumo.chair add column depth_range_id integer, add column height_range_id integer, add column price_range_id integer, add column width_range_id integer;

update isuumo.chair set depth_range_id = 0 where depth < 80;
update isuumo.chair set depth_range_id = 1 where depth >= 80 and depth < 110;
update isuumo.chair set depth_range_id = 2 where depth >= 110 and depth < 150;
update isuumo.chair set depth_range_id = 3 where depth >= 150;
...

add column を 2 個以上書くときの SQL の書き方が分からん、とググりながらやっている (地力不足)。短期決戦なんだから綺麗に書くよりも 「動けば良い」を合い言葉にしておくと良いのだろうなぁ、まだ気持ちを捨て切れてない。

blog.sushi.money

また、この過程で「ひょっとして condition.json から ranges 減らしたらベンチマーカーが送ってくるクエリパラメータの分散が減るんじゃね？」と思って試してみたがさすがにそんな甘い話は無かった。

SQL がまだホットスポット

[width_range_id, popularity] で複合インデックスを張ったが、1 要素だけの検索でも Using filesort が消えない。

mysql root@127.0.0.1:isuumo> explain select * from estate where door_width_range_id = 1 order by popularity desc, id asc limit 25 offset 50\G
***************************[ 1. row ]***************************
id            | 1
select_type   | SIMPLE
table         | estate
partitions    | <null>
type          | ref
possible_keys | door_width_range_id_and_popularity
key           | door_width_range_id_and_popularity
key_len       | 4
ref           | const
rows          | 5253
filtered      | 100.0
Extra         | Using index condition; Using filesort

1 row in set
Time: 0.005s

試しに id ASC を削ると Extra がめっちゃ綺麗になる。

mysql root@127.0.0.1:isuumo> explain select * from estate where door_width_range_id = 1 order by popularity desc limit 25 offset 50\G
***************************[ 1. row ]***************************
id            | 1
select_type   | SIMPLE
table         | estate
partitions    | <null>
type          | ref
possible_keys | door_width_range_id_and_popularity
key           | door_width_range_id_and_popularity
key_len       | 4
ref           | const
rows          | 5253
filtered      | 100.0
Extra         | Using where

1 row in set
Time: 0.005s

SHOW INDEX から popularity のカーディナリティはかなり高いのを知っていたので、「これ unique にできるんじゃね？」という作戦に出た。

具体的には

• 10 倍する
• id が大きい方から 0, 1, 2, ... を足す
• ORDER BY popularity DESC, id ASC を popularity DESC のみに変更

をやった。

レスポンスを返すときに 1/10 にするのを忘れていて、ベンチがコケて気づいて一瞬慌てた。シンプルに 10 倍したので計算で返せて助かった……。

この 10 倍して 1/10 して返す、みたいなのは、浮動小数点数を避けるために整数で計算したい！ってときなんかに実務でもよく使う手なので、自然と思いつけた。

突然登場する ActiveRecord。

require "erb"
require "active_record"

class Chair < ActiveRecord::Base
  self.table_name = :chair
end
class Estate < ActiveRecord::Base
  self.table_name = :estate
end

env = "development"
path = File.join(__dir__, "database.yml")
specs = YAML.load(ERB.new(File.read(path)).result)
ActiveRecord::Base.configurations = specs.stringify_keys
ActiveRecord::Base.establish_connection(env.to_sym)

Estate.group(:popularity).having("count(1) > 1").count.each do |popularity, _|
  Estate.where(popularity: popularity).order(id: :desc).each_with_index do |e, i|
    e.popularity = e.popularity + i
    e.save
  end
end

Chair.group(:popularity).having("count(1) > 1").count.each do |popularity, _|
  Chair.where(popularity: popularity).order(id: :desc).each_with_index do |e, i|
    e.popularity = e.popularity + i
    e.save
  end
end

DB 2 台構成に

SQL だいぶ綺麗にしたけどまだ DB の CPU がボトルネック。というので

• 101 は nginx/php
• 102 は chair 用 DB
• 103 は estate 用 DB

という使い分けに変えよう、という会話がシュッと行われて、id:uzulla にやって貰った。コネクション 2 本持って使い分けるという方針は即決まったんだけど、PHP で書ける自信が無かったので、手を動かせる人が居て助かった。

スコア変遷

なんと 20 時までは 872 が最高得点だったが、ラスト 1 時間で

• ボトルネックが DB の CPU 使用率
  • DB の CPU を使わせない、短時間でできることをとにかく考える
• 与えられた 3 台をうまく使う

という改善ができて、2125 まで爆上げできた。

20 時でスコアが固定された段階では 2100 ぐらいがボーダーっぽかったので、2125 は「他のチームが上げてきていたら無理だなー、でも少し夢があるなー」という会話ができるスコアで、ここまで辿り着けて良かったですね。いやーしかし悔しいな。

あと 1 手あれば 200 点ぐらい足せた可能性があり、ヌルポインターマリアユニバースが 2335 で本戦出場 ということを考えると、いやーこれは行けなくもなかったなー……。

コミュニケーション

• Discord でボイスチャット繋ぎっぱなしにしていた
• scrapbox にどんどんページを作っていった
  • 最新の alp や pt-query-digest の結果が勝手に貼られていくのは最高に便利だった
• 画面は結局シェアすることが無かった
• ペアプロすることもほぼ無かった

パラレルで動けるように次にやることを考える、というムーブをそれぞれが取れていたんじゃないかなぁ。つまり指揮官 3 人体制なのであった。

改善するとしたら

• 一度も自分でベンチマークの enqueue をしなかったので、dstat を眺めるということもやらなかった
  • 次の改善点の実感が足りない
  • 2 時間に 1 回ぐらいは自分で enqueue する、もしくはチーム全員で enqueue して dstat を見守る。
    • チーム全員で眺めると自然と方針を固める時間も取れて一石二鳥な気がする
• ブラウザでは結局動かさなかった
  • アクセスログとコードしか見てないので僕だけコミュニケーションが難しかった
• ペア作業を恐れない
  • 詰まってたら悲鳴上げてねーぐらいの声掛けはできていたので、信頼して任せているということなのかもしれないけど、まったく画面シェアが無いのはまぁ異常だろう
• PHP 慣れ
  • preload 周りは id:uzulla しかできない作業になっちゃってるンだよなぁ
  • 今回 AppArmor で少しハマってそうだけど手が出せなかった
• 「SQL 改善したらボトルネックが移るはず」と思ってなかなか最終構成の見極めができなかった
  • いやー、でもこれはそういうモノだと思っているな
  • 2 時間前ぐらいに決めようという緩い合意が取れていたことが Keep なのだろう

お疲れさまでした！

いやー、良問だった。データ量が大したことなくても検索は大変というのがよく分かる。 流れる SQL 一覧を作った瞬間に「GIS !!!!!????」という驚きがあったし、椅子が通るかどうかという recommend 検索も最高に面白かった。

過去最多の 1 日 500 組という暴力を捌いた ISUCON10 運営チームの皆さま、ありがとうございました。

2020-09-20 追記

isucon.net

まさかの繰り上がり当選した。やってまいります。