ISUCON公式Blog

WINNER'S PRIZE \1,000,000



   

2013.11.9 23:22 追記
--
こんにちは、櫛井です。

お題となるWebサービスを決められたレギュレーションの中で限界まで高速化を図るチューニングバトル、それがISUCONです。過去の実績も所属している会社も全く関係ない、結果が全てのガチンコバトルです。第三回 #isucon のフォトレポートをお届けいたします。

関連エントリ
優勝賞金ドドンと100万円! 第三回 ISUCON 開催のお知らせ #isucon : ISUCON公式Blog
ISUCON 本戦出場者決定のお知らせ : ISUCON公式Blog
第三回 ISUCON本選 関連エントリまとめ : ISUCON公式Blog

会場は渋谷ヒカリエのLINE株式会社オフィスです
DSC06928
DSC06929


開始の30分前にはほぼ参加者が揃う相変わらずの集まりのよさを発揮
DSC06871


今回はゴロ寝スペースや
DSC06872


セミナールームや
DSC06926


会議室も開放してみました
DSC06876


京都からお越しの方もいらっしゃいます。「これが… 東京…」って言っていたかどうかは不明。
DSC06875


満員御礼でございます
DSC06877


というわけで予定どおりスタート。私から諸注意の案内です。
DSC06881


本選の出題内容およびレギュレーションの発表は、出題担当の面白法人カヤック 藤原さんから。
ISUCON恒例(?)のストーリー仕立て。今回の問題は、画像版のTwitterです。
DSC06900


会場が分散しているので、諸々の情報はこの封筒の中に。
DSC06922



ザワザワ
DSC06925


ついに開始した第三回 ISUCON 、今回もリアルタイムに計測結果を表示しています
DSC06930


皆さん頑張っていらっしゃいます(会場は超静か…)
DSC06932
DSC06933


昨年は「サーバーのチューニングをするから塩サバ弁当よー!」とノリノリで提供してみたのですが
「サバアレルギーだったらどうするんだ」「会場がサバくさい」と地味に不評だったので、今年は
ヒカリエに出店している様々なテナントさんからお弁当を沢山取り寄せてみました。
DSC06934


大好評でした
DSC06939


仲良くお弁当。
DSC06940
DSC06942


こちらは運営部屋。リアルタイムでモリモリと対応しています。
DSC06938


「ふむふむ、真面目にやっとるのう」と会場を見まわる藤原さん
DSC06949


今回はモニター持ち込み組がチラホラいらっしゃいましたね
DSC06950
DSC06952


こちらは第一回、第二回と出題担当だった弊社のエンジニアたち。
今回は「LINE選抜」として、満を持して参加者としての登場です。
DSC06951


ティータイムにはポットでコーヒーを用意してみました。
「手厚い、手厚いのう…」と、こちらも好評だったようです。
IMG_8059


残り2時間を切り、いよいよ煮詰まってきた会場…
IMG_8065


残り30分くらいになり、その時は来ました。「一番最初に25000点に到達チームに贈られる賞」
が特別賞ですが、大きく上回る40000点が表示された!叩きだしたのはLINE選抜チームでした。
DSC06959


静かだった会場に歓声とどよめきが。
DSC06960


残り10分を切り、それぞれのやり切った雰囲気
DSC06962


18時になり、競技終了と共に拍手が巻き起こる会場
DSC06967


集計作業へ…
最終的には競技に使用した全てのサーバを再起動して数値を測定するので、最後の最後まで順位が
どうなるかはわかりません。(数値が出なければ順位が決まりません)

1時間ほどの間に参加者の皆さんはそれぞれの施策について話し合っていたり
DSC06970


というわけで結果発表!まずは特別賞から、LINE株式会社の人材支援室でマネージャーをしている
薮田さんからLINE選抜チームへ進呈。
DSC06975


おめでとうございます。
DSC06980


学生枠で出場した3組のうちの1位に贈られる「学生賞」はチーム「銀杏絶滅しろ」の皆さん。
全体でも6位という好成績でした。
DSC06990


そして優勝は………


LINE選抜「チーム生ハム原木」でした!
DSC06997


LINE株式会社の執行役員である池邉さんから、LINE選抜チームへ賞金100万円を進呈。
DSC07005


副賞であるロボダンボーは株式会社データホテルの冨成さんから進呈。
DSC07012


お、おめでとうございました!
DSC07028


過去2回はわりと僅差でしたが、今回は1位と2位のスコアが4倍以上という結果になりました。
DSC07032


ご参加いただいた皆さん、ありがとうございました!
DSC07047



本選参加者のエントリまとめはこちら
第三回 ISUCON本選 関連エントリまとめ : ISUCON公式Blog

Tweetはこちらへまとめています。
第三回 #isucon 本選Tweetまとめ - Togetter
Read more...

櫛井です。いよいよ今週の土曜に本選が開催となる ISUCON ですが、予選を勝ち抜いた皆さんは心と体の準備をされているかと思います。

さて、何度かお知らせしておりますが今回の ISUCON は優勝賞金ドドンと100万円!となっているのですが、共催をしていただいている株式会社データホテル様より副賞をご用意いただきましたので紹介したいと思います。

はい、こちらっ!
ダンボー

副賞:ロボダンボー+DATAHOTELロゴ入り外装スペア
ロボダンボーは、全身に11個のサーボモータを搭載し「歩く」「踊る」「首をかしげる」など様々な表現が可能です。また、動きに合わせて音声を鳴らしたり、両目のLEDを光らせるなど、豊かな表現ができる機能を搭載しています。(製品サイトより)

※優勝チームの人数分を進呈します


どうですか…。これ結構なお値段するんですよ。。「副賞としてロボダンボーをご用意しました」と連絡をもらった時は「えっ?」と二回くらい聞き返したレベルでした。いや、これは普通に欲しい。1つ余ったら欲しい。

というわけで本選出場の皆さん、当日は万全の体調でお越しください。渋谷ヒカリエ会場にてお待ちしております。(当日の流れ等はチームの代表者の方へ連絡していますので聞いていないという方は代表の方へ問い合わせてみてください)
Read more...

こんにちは、@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が公開されていますので試してみてください。

  • Read more...

    ↑このページのトップヘ