こんにちは、@acidlemon です。

ざっくりと書いたつもりなのに長編です。

本エントリでは、スコアがなかなか伸びなかった方々を主な対象として、実際に先週末実施した予選問題を解いていく方法を解説します。高スコアをたたき出した方々は参考までに「こんなやりかたでもここまでスコア伸びるんだなー」という感じで読んでください。

最初の方針は「派手なことをしない」「コンサバにやる」です。「とりあえず」という気持ちでmemcachedやRedis、もしくはvarnishやnginxでキャッシュし始めるとキャッシュの寿命のことを考え始めなければならず、疑心暗鬼になったりして難易度が上がります。まぁその辺は最終的には男気によって解決するものなのですが、その要素を排除したままできるだけスコアを上げてみましょう。

日曜夜よりアップされたみなさんの感想エントリなども拝見しており、やっぱオンメモリに置くのは速いよなぁなどいろいろな感想をもちました。しかし、もともとリアルISUCONをたくさん経験されている方の中には「それたしかにすごいけど実運用のサービスではちょっとできないよね…」といった感想をお持ちの方もいるかと思います。とりあえずRedisに全部データおいてみるとか、アプリのオンメモリにデータをため込むといったことをせず、堅実にスコアを上げていく方法を以下で解説していきます。

ミドルウェアやアプリのムダ処理排除

openrestyかnginxのインストール

今回はとくにnginxに関する罠がなかったので最初から入れ替えて問題を感じた方はいなかったのではないでしょうか。予選用AMIに最初から入ってるnginxは普通のnginxなのでLuaは使えません。もしLuaが使いたいならopenrestyをダウンロードしてきて自分でインストールするのが楽です。その場合でも設定ファイルはそのまま使えますので、最初は標準のnginxでスコア上げを行い、どうしてもダメならopenrestyに入れ替えてsupervisordに以下のような感じの設定を書き加えればよいですね。

[program:nginx]
directory=/usr/local/openresty/nginx
command=/usr/local/openresty/nginx/sbin/nginx -g "daemon off;" -c /etc/nginx/nginx.conf
user=root
redirect_stderr=true
stdout_logfile=/tmp/nginx.log
autostart=true

セッションストアの変更

InnoDB Memcached Pluginに入れてもろくな事がないので、Memcachedの接続先を11212ポートに変更します。また、フレームワークがサポートしているのであればファイル保存に変更するという手もあります。このとき、ファイルに保存するときに保存先を指定できるのであれば /dev/shm/tmp にできればtmpfsに載るのでmemcachedとさほど変わらないか、むしろ少し高いくらいのスコアになります。

InnoDB Buffer Poolの拡張

今回は初期状態でFailしないようにするためBuffer Poolに乗るかどうかギリギリという感じの初期データサイズになっています。インデックスを追加したりテーブルを追加したりするとBuffer Poolがあふれてしまうことがありえるため、これを拡張するのは重要です。初期データは200MBですので、512MBくらいまで広げておけば大体安心なかんじです。

外部プロセスでmarkdown変換してるところをなんとかする

基本的に今回のチェッカはmarkdownのチェックは非常にゆるめに作ってあります。これは他のMarkdown変換ライブラリを使っても大丈夫なようにすることを意図しています。なので、Discountあたりを使ってプロセス内で変換するようにしましょう。Discountなら今回のお題の言語に対してほぼ言語バインディングがそろっています。もちろん、別のMarkdownエンジンでもOKです。

こちらで確認したところ、クエリ改善途上で6000くらいだったスコアが、markdown変換をText::Markdown::Discountに取り替えて10500くらいまで上昇するというケースがありました。ちなみに予選後にTLに流れていたText::Markdown::Hoedownでは同条件で10600くらいなので、まぁ誤差レベルだとおもいます。本記事では最終的に20000を越えるスコアになり、その20000オーバーのときに再比較を行ったところDiscountが200ほど高い結果となりました。まぁ誤差だよねというレベルです。

スタイルシートで / を読みにいってるところをはずす

予選レギュレーションに「DOM構造は変化させない」というのがありましたが、採点条件にあるとおり「チェッカがDOM構造が変化していない」と判断していればちょっとくらい変えてもそれはアリです。なんでもありのスピードアップバトルです。ルールに縛られたりFAILを恐れたりせずにいろいろ試してみてください。ユーザからすればブラウザで見ていてもスタイルシートで / を読む読まないが変わったからといって見た目の変化はありませんよね。

uri_forの呼び出しが多すぎて非効率なのでなんとかする

なにをどう「なんとかする」かは個人のポリシーによりますが、一番高速になるのはメソッド呼び出しをやめて http://localhost とべた書きしていくことです。uri_forはPerlの場合Kossyが用意してしているものを使用しました。

出題チーム名誉顧問の @Songmu によると、Perlのuri_forが遅いのはPlack::Requestがbaseメソッドを呼び出すときに毎回URIオブジェクトを生成しているところから来ているので、Kossy::Request::baseを定義してURIオブジェクトをキャッシュして毎回生成しないようにすることが重要で、べた書きがイヤだなーという人はそれで対処すればよいとのことでした。つまり、この問題が無いPerl以外の言語の実装ではほとんどが出題側が初期実装に薄く実装したuri_for関数を使っているため、ベタ書きにしてもあまりスコアに寄与しない可能性もあります。

ただ、レンダリング時には1つのHTMLでuri_forメソッドが20〜130回くらいは呼ばれるので完全にメソッド呼び出しをなくせば関数呼び出すコスト分のスコア上昇はあるはずです。参考までに、Perlでは10000前後の時にこの改善を行うことで13000前後まであがることを確認しました。DBの改善が効いてきて大分スコアが上がってきたけどまだほしい、そんなときに結構効いてきます。

アプリのDB周りのクエリ改善

ここからは今回のメインであるクエリ改善に入ります。

mysqldが重いのを何とかする(第一段階)

とりあえずアプリを書き換えずにインデックスを張っていきましょう。

CREATE INDEX `memos_idx_is_private_created_at` ON memos (`is_private`,`created_at`);
CREATE INDEX `memos_idx_user_created_at` ON memos (`user`,`created_at`);
CREATE INDEX `memos_idx_user_is_private_created_at` ON memos (`user`,`is_private`,`created_at`);

この3つでとりあえずインデックス使わないクエリはなくなりました。たぶんこれだけだとあんまりスコアは伸びません。

mysqldが重いのを何とかする(第二段階)

不要そうなクエリを消します。

/ と /recent/:page でmemosを100件取ったあとにループクエリを発行してる(いわゆるN+1問題)ところを削除し、直前のクエリにJOINします。

SELECT memos.*,users.username FROM memos JOIN users ON users.id = memos.user 
WHERE is_private=0 ORDER BY created_at DESC, id DESC LIMIT 100

これをやるとMySQLを入れ替えなかった人はCPU使用率が跳ね上がったりしたかとおもいます。実はここには意図せず発生する罠があり、なぜかこのクエリで上記のインデックスが張ってある状態だとMySQL5.6の実行計画が狂います。具体的にはmemosに対してusersを1行ずつJOINする計画ではなく、usersに対してmemosを1行ずつJOINするという謎の実行計画になります。なので、とりあえずexplainしてダメなことを確認したらFORCE INDEXでmemos_idx_is_private_created_atを使うように強制変更します(ただ後で不要になります)。

また、filter get_user で毎回usernameのためにusersから1row引いていますが、これは /signin のときにセッションにusernameを入れることで削除できます。get_user 時にセッションからusernameを取ってきてidとusernameからなるハッシュ(連想配列)を作成すればOKです。

ここまでやると3000くらいまではあがるんじゃないでしょうか。

mysqldが重いのを何とかする(第三段階)

この項は「アプリの構造を変えないまま、まだ改善するならクエリをこう書き換えるよね」というものですが、これをやらずにアプリの構造変更を決断して第四段階に進んでもかまいません。 この時点でまだ圧倒的に / と /recent/:page が重く、explainするとrowsの読み出しが数万行発生しています。最終的には100行しか使わないので、せめて/ は100行しか読み出しが発生しないようにクエリを工夫します。

具体的には、数万rowを全部読み出してORDER BYしていたところを、インデックスだけで処理できるようにmemos.idだけを取得するサブクエリに書き換えてそれを自己結合します。すると読み出しが発生する行をほしい100行だけに絞り込めます。

SELECT memos.*,users.username FROM memos JOIN users ON users.id = memos.user JOIN
 (SELECT id FROM memos WHERE is_private=0 ORDER BY created_at DESC LIMIT 100) 
 AS tmp ON tmp.id = memos.id;

これでexplainするとderived2テーブルがでてきてちょっと複雑に見えますが、数万rowから100row選び出すところはUsing Where; Using IndexでmemosのPKEYを取り出すだけになります。この派生テーブルにはINDEXがないのでフルスキャンがかかりますが、100個のIDしか入ってないテーブルとのJOINのコストのほうが数万row読み出すコストよりも低くなるため、高速になります。

ただ、LIMITの後ろにOFFSETがついている /recent/:page 派生テーブルがOFFSETも含む行数(たとえばOFFSET 20000であれば20100行の派生テーブルとなる)ため、読む行自体は100rowになるもののフルスキャンの必要なテーブルとのJOINは割と重いものとなってしまいます。

/は十分に速くなったため、ここらへんで大体スコアが5000〜7000くらいになるのではないかと思います。

mysqldが重いのを何とかする(第四段階)

ここでベンチマーク1回分のslowlogをmysqldumpslowコマンドに食わせると、INSERTとUPDATEを除くと合計1秒以上かかってるのは以下の3クエリです。

Count: 1743  Time=0.01s (17s)  Lock=0.00s (0s)  Rows=100.0 (174300), isucon[isucon]@localhost
  SELECT memos.*,users.username FROM memos JOIN users ON users.id = memos.user 
  JOIN (SELECT id FROM memos WHERE is_private=N ORDER BY created_at DESC LIMIT N OFFSET N)
  AS tmp ON tmp.id = memos.id

Count: 2493  Time=0.01s (16s)  Lock=0.00s (0s)  Rows=1.0 (2493), isucon[isucon]@localhost
  SELECT count(*) FROM memos WHERE is_private=N

Count: 750  Time=0.00s (2s)  Lock=0.00s (0s)  Rows=100.0 (75000), isucon[isucon]@localhost
  SELECT memos.*,users.username FROM memos JOIN users ON users.id = memos.user JOIN
  (SELECT id FROM memos WHERE is_private=N ORDER BY created_at DESC LIMIT N)
  AS tmp ON tmp.id = memos.id

一番下の / で走るクエリはトータル2秒程度なので目をつむってもよさそうですが、上2つで合計33秒かかっているためかなりのCPU時間を食っていることになるのでこれらは何とかしないといけません。何とかするにはRedis/memcachedを投入するか、DBに別テーブルを追加するアプリの設計変更が必要がです。

一番上のLIMIT OFFSET外しは

Redisにis_private=0なメモを古い順にListへ投入し、必要なオフセットをアプリで計算してLRANGEで100件分のIDをとってくる

MySQLにpublic_memosテーブルを追加してidとmemoを古い順に投入し、WHERE id BETWEEN ? AND ? でmemoのIDをとってくる

というどちらかで実装できます。これをやると一番下の / のクエリも同様に改善できるので一石二鳥です。

真ん中のcount(*)は投稿があったときにis_private=1なら

Redisかmemcachedで特定のキーの値をincrする

MySQLにpublic_countテーブルを追加して UPDATE public_count SET cnt = cnt + 1 で加算する

というどちらかの処理を行うようにして加算する値を取ってくることで実装できます。いずれも前者でやったほうが速そうな雰囲気はありますが、MySQLでやっても実用的なレベルまでスコアが改善しますので、短時間で実装するのであれば後者で行った方が確実性があがります。

なお、ベンチマークが初期化する処理にはdrop database/create databaseが存在しないため、新しく作ったテーブルをドロップしません。テーブル追加作戦をとった場合、新しく作るpublic_memosテーブルのデータは一度格納してしまった後は消えませんので、あらかじめデータを入れておき、初期化スクリプトでベンチマーク初期時とおなじ状態に戻すクエリを実行すればOKです。

テーブル作成は

CREATE TABLE `public_count` (
  `cnt` int(11) DEFAULT NULL
) ENGINE=MyISAM DEFAULT CHARSET=utf8;

CREATE TABLE `public_memos` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `memo` int(11) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8;

という感じで作ります。このテーブルにデータを追加するスクリプトを書いてデータを入れた後、初期スクリプトで適用するSQLに以下を追加します。

UPDATE public_count SET cnt = 20540;
DELETE FROM public_memos WHERE id > 20540;
ALTER TABLE public_memos AUTO_INCREMENT = 20541;

ここまでできると10000越えが見えてきます。

order/newerをなんとかする

とりあえず最初にINDEXを2つ張っているのですが、ORDER BYして全部行読みしてるのであんまり実はINDEX張るだけでは意味がありません。ただ、viewをみると実はリンクのIDをつけるためにしか使っていないので、"SELECT *"となっているところを"SELECT id"にすることができます。するとUsing Indexになるので行読み込みが発生せず、ちょっとスコアがあがります。最適化の進み方次第ですが10600→11100程度のスコア改善はありました。

また、ループがかなり回るコードになっているので、一発で取れるクエリに書き換えることもできます。2つを一気に1クエリで取るのは大変なので、1クエリずつ飛ばします(UNIONでつないでもいいけど大した変わらないかと思います)。いろんな局面で"SELECT id"と2クエリで1rowずつ取るのを比べてみましたが、ほぼ誤差程度みたいな感じだったのでこの辺はお好みでという感じです。

大体これでDBのボトルネックが解消したので、workloadを2とか3にしつつスコアを調整していけば大体予選通過できるスコアがでます。

contentを毎回1行だけぶった切るのを何とかする

contentはmemoのサイズにもよりますがそこそこのサイズがあってmysqldの読み出し負荷が高いです。また、毎回レンダリング時に毎回正規表現をつかってsplitしているのでアプリ側のCPUにもそこそこ重いです。これを改善します。

ひとまず簡単にできるのは、SQLで1行にしてしまう方法です。

$memo.content.split('\r?\n').first() で呼び出しているのを $memo.title に変えて、SELECTしているとこで memos.content を substring_index(content,"\n",1) AS title に変更します。LIMIT OFFSETをpublic_memosに書き換えたあとであればここが一番のボトルネックですので、この改善で12500→19500のスコアアップがあることを観測しています。

また、ALTER TABLE memos ADD COLUMN ( title VARCHAR(255) ); してmemosにtitleカラムを追加するともっとスコアが上がります。既存のデータはinitスクリプトで最後に UPDATE memos SET title = substring_index(content,"\n",1); とやると初期データのマイグレーションも終わります。ちなみに、InnoDB Buffer Pool Sizeを指定しないままここまでくると、ALTER TABLE ADD COLUMN + UPDATEのコンボで初期化60秒制限にかかってしまいますのでご注意ください。

titleカラムを直接追加するとMySQLも余計な処理をしなくなるのでさらにスコアの上がり方は激しくなり、大体workloadを2か3くらいにして23000〜24000程度まであがります。

これで大体改善できるところはやりきった感じです。

まとめ

ここまでで「静的ファイルだけ捌いて全部裏に回すnginx」+「MySQLしか使わないWebアプリ」の組み合わせで23000〜24000程度まで上げられるということを説明しました。いかがでしょうか? 3人いるとはいえ時間内にすべてここまでやるのは難しいですが、安易にvarnishによるキャッシュに走らずともここまで上げられるということは分かっていただけたかと思います。

@fujiwaraの講評にもあるとおり、今回の出題には /recent/:page のチェックがかなり緩かったこともありvarnishを置くだけで一気にスコアアップというようなことが可能な状態になってしまっていましたが、本戦ではそうならないよう厳しくチェックしていきたいと気を引き締めています。

おまけ

ここまでMySQLだけでやってきましたが、実はまださらにMySQLだけで高速にできる部分があります。具体的には /, /recent/:page, /mypage の記事リストの部分をあらかじめレンダリングしてDBに入れておくという手法です。

/, /recent/:pageはpublic_memosテーブルにカラムを追加してそちらを引くようにし、/mypageはmypage_memosテーブルみたいなのを用意してそこへ格納します。/ と /recent/:pageの改善をいれるとスコアが24000→27500と上がり、/mypage用のレンダリング済み

も用意すると29000くらいまでスコアがあがりました。29000出たときの実行環境はStarmanで10worker, workloadは3でした。

同じようにmarkdownの変換結果をDBに入れておけば、/memo/:idも少し速くなりそうです。そこまでやると30000越えるかもしれませんね。ただ、今回はそこまではやりませんでした。

まぁただそういうHTMLのレンダリング結果のキャッシュは意固地にMySQLにいれようとせずに、memcachedにいれとけ説もありますねー。個人的にもそう思いますので、参考程度にご紹介しました。

なお、ベンチマークツール自体に限界があり、m3.xlargeでたたき出せる最高スコアは大体50000〜60000弱くらいになるようです。手元では一通り高速化したアプリからmemcachedにセッションに関する情報(username, token)を保存して、それをnginx-luaから読み出してHTMLを組み立てて返す手法などを使って56000程度まで出ることは確認しています。

オンライン予選で使用した問題が手元で再現できるAMIを公開しましたで予選時のAMIが公開されていますので試してみてください。