ISUCON8予選問題においてPerl実装で25万点を突破する方法

この記事はDeNA Advent Calendar 2018の15日目の記事です。遅刻!

こんにちは、@karupaneruraです。今日はDeNAが問題提供したISUCON8予選に関する話です。

ISUCONとは

ISUCONはIiknajini Speed Up CONtestのことで、Webアプリケーションのチューニング技術を競うコンテストです。 競技開始時刻にそれまで秘密にされていたあるアプリケーションがチームごとにサーバーごとまるっと渡されて、それを制限時間内にどこまでチューニングできるかを競います。

サーバーでは参照実装としてある仕様を満たしたアプリケーションが動いていて、その外部仕様を崩さずに(外見上)同様の挙動をするアプリケーションをそれぞれのチームがチューニングしていきます。 そして、ベンチマーカーをチームごとに実行すると仕様や整合性のチェックとパフォーマンス計測が行われて総合的にスコアとして数値化されてランキングが作れるという感じです。

参照実装は各言語の実装が提供されていて、各々の得意な言語を使うことができるほか、フルスクラッチで書き直すことも許されます。ミドルウェアの制限もないので、時間の許す限り本当に各々がベストだと思うソリューションを選択できる競技です。ぼくはWebエンジニアリング技術の総合格闘技のような競技だと思っています。

ISUCON8はどうだったか

そんなISUCONですが2018年は第8回目のISUCON8として開催されました。主催はLINEさん、サーバー提供はGMOさん(ConoHa)、問題提供はカヤックさんとDeNAで行いました。 DeNAは予選問題、カヤックさんは本戦問題という形で役割分担をした形です。

僕は予選問題の作問と模範解答(事前チューニング)を行いました。 解説記事も書いています。(おかげさまで大変好評でした)

ところで、ISUCON8では感想戦という形でチューニングの続きを行ってもらえる試みをやったのですが、その際にこの模範解答のスコアを出していました。

261421点というスコアですが、25万点オーバーを安定して出していました。 作問者なので当然に勘所はわかってるし、問題をブラッシュアップしながら並行して育てたので競技参加者の皆さんと同じ条件下のスコアではないわけですが、ここまではPerlでチューニングできるという事実を示しています。ちなみに競技中の最高スコアは10万点ほどでした。

前置きが長くなりましたが、今回の記事はこのスコアを出す構成はどのようにして作られたのかを語っていきます。

模範解答を作る目的

模範解答は、そのアプリケーションを最適化したときにベンチマーカー側に問題が起きないことの確認、攻略の際にどのボトルネックがどのように現れるのかの確認のために作成しました。(便宜上、模範解答という呼び方をしています。) これがあることで、ベンチマーカー側のレースコーディション問題の発見や問題の調整の意思決定がすばやく行えます。また、 攻略難易度が高すぎる/低すぎるの判断や、問題の調整もしやすくなります。 そのため、模範解答は早めの段階から作成していました。

模範解答を作るときに考えたこと

上記のような目的があるので、競技中に到達し得るスコアより高いスコアを出す実装にする必要があります。 そのため、実装時間は度外視して極限までチューニングすることを考えました。

極限までチューニングするにはどうするか、全体観を得たらそこから逆算して設計を考えていきます。 今回の場合は大きな難関はマイページと予約/キャンセルです。ユーザー毎にレスポンスが変わる部分があるので、ISUCON2の模範解答のアプローチのような、静的ファイルとしてすべてのデータを書き出すといった方法はとりにくいでしょう。なので、動的にレスポンスを返す形で高速化していきました。

動的に返すレスポンスを最適化するには、最終的に返したいデータモデルから逆算して必要なデータを考えていきます。最小限の手数で高速にレスポンスを作るために今回はRedisを使いました。Redisは低レイテンシーでレスポンスを返してくれて、かつメモリ消費量がMySQLと比べて少なく済む点が今回の課題では有利に働きました。

基本的な戦略は以下です:

  • キャッシュできる情報は基本的にキャッシュする
  • レスポンスはRedisのデータだけで基本的に解決できるようにする
  • 更新はRedis上のデータとMySQLを更新する
  • レポートだけデータ量の多さと整合性を顧みてMySQLを使って返す

また、構成としては最終的にアプリケーションのCPUがボトルネックになったため以下の構成を採用しました:

  • nginx - h2o - app / mysql / redis
  • h2o - app
  • h2o - app

nginxをLBとして、h2oでhttpを受けてアプリケーションへはunix domain socketでデータを送ります。

アプリケーションの実装はこちら: webapp/perl/lib/Torb/Web.pm

基本的にはこの方針と解説記事に書いたアプローチを理解できればすべての実装に説明が付きます。 ほか、細かいMySQLやRedisのチューニングやカーネルパラメータのチューニングも当然やっていますが、それらは普通のことしかやってないので今回は特に紹介しません。リポジトリにあるのでよかったら見てください。

実装は難しい部分もあるので実装の分かりにくいポイントを紹介します

GET /initialize

ベンチマーカーからベンチマーク開始時に叩かれるデータ初期化用エンドポイントですが、ここはレギュレーション上一定時間以内の処理が許されています。 そこで、初期データをキャッシュに載せてしまうことで全体の高速化を図ります。

基本的にRedisにpipelineしてクエリを投げまくるだけなのですが、ユーザー毎の最終更新イベントを作るときに課題があります。 ユーザー毎の最終更新イベントは、各ユーザーが最後に予約/キャンセルしたイベントをユニークに5件表示するという機能です。これをRedisでやる場合はSorted Setを使ってユーザーとイベントの組み毎に最終予約/キャンセル時刻を入れておく必要があります。 しかし、これを素直に解決するとユーザー数ぶんのN+1問題になってしまいます。SQL一撃で解決するためには窓関数を使う必要があります。

-- https://github.com/karupanerura/isucon8-qualify-tuned/blob/master/webapp/perl/lib/Torb/Web.pm#L249
SELECT id, user_id, event_id, updated_at FROM (SELECT user_id, event_id, id, updated_at, ROW_NUMBER() OVER (PARTITION BY user_id, event_id ORDER BY updated_at DESC) AS `rank` FROM reservations) a WHERE a.rank = 1 GROUP BY user_id, event_id

これで一発です。MySQLは8.0から窓関数をサポートしているのでこういうことができます。

また、全体売上レポートも一定のデータはキャッシュしておくことができます。終了していないイベントでまだキャンセルされてないまたは終了したイベントの最も古い予約より古い予約は、すべて終了しているイベントかキャンセルされた予約になっているはずです。そのため、そのID以前までキャッシュすることができます。

-- https://github.com/karupanerura/isucon8-qualify-tuned/blob/master/webapp/perl/lib/Torb/Web.pm#L171
SELECT MIN(r.id) FROM reservations r INNER JOIN events e ON r.event_id = e.id WHERE NOT ((e.closed_fg = 0 AND r.canceled_at IS NOT NULL) OR e.closed_fg = 1)

こういう感じで取ってきてCSVをファイルに書き出して使っておくと便利です。 この実装ではPSGIのStreaming Responseのフォーマットでレスポンスを返しているので、それを直接つかってキャッシュファイルを生成することができます。(レスポンスをそのままファイルに書き込みます)

# https://github.com/karupanerura/isucon8-qualify-tuned/blob/master/webapp/perl/lib/Torb/Web.pm#L173
my $rid = $self->dbh->select_one('SELECT MIN(r.id) FROM reservations r INNER JOIN events e ON r.event_id = e.id WHERE NOT ((e.closed_fg = 0 AND r.canceled_at IS NOT NULL) OR e.closed_fg = 1)');
my $res = $self->render_report_csv('SELECT * FROM reservations WHERE id < ? ORDER BY id ASC', $rid);
$res->finalize()->(sub {
    my $header_line = shift;
    open my $fh, '>', "/tmp/report_all_prefix_$rid.csv" or die $!;
    return Plack::Util::inline_object(
        write => sub {
            print {$fh} @_;
        },
        close => sub {
            close $fh or die $!;
        },
    );
});

ちなみに、これらの処理の過程でそこそこのメモリアロケーションが発生します。psgix.harakiri.commit を使ってプロセスごと殺してまっさらにしておくとスッキリです。

GET /admin/api/reports/sales

前の項で触れたとおりキャッシュデータを使える場合はそれをまるっと流しつつ、解説記事でも触れたとおり mysql_use_result を使ってMySQLから受け取ったデータをそのまんま流しましょう。適度にバッファリングしてwriteすると本当はもっとよいです。 なお、KossyはデフォルトでStreaming Responseをサポートしていないので、以下のようなモンキーパッチでお茶を濁しました。(忘れてなければ年末正月あたりの暇な時間にPull-Requestを投げます)

# https://github.com/karupanerura/isucon8-qualify-tuned/blob/master/webapp/perl/lib/Torb/Web.pm#L981-L1001
package Kossy::Response {
    use Scalar::Util qw/reftype/;

    sub new_with_code {
        my ($class, $code) = @_;
        bless \$code, $class;
    }

    BEGIN {
        my $super = \&finalize;
        no warnings qw/redefine/;
        *finalize = sub {
            my $self = shift;
            if (reftype $self eq 'REF') {
                return $$self;
            }

            $self->$super(@_);
        };
    };
};

まとめ

こういうアプローチでISUCON8予選問題の模範解答としては25万点オーバーを安定して出すことができました。 普段あまり使わない機能もときと場合によっては便利に使えるので、たとえば仕事で突然ISUCONになったときのためにも普段から素振りしておけると良いですね。ちなみに僕は初めて使う機能が結構ありました!(窓関数とか) ISUCONを出題するとこんな感じで色々と遊ぶことができるので楽しいです。みなさんもチャンスがあればぜひ出題にチャレンジしてみてください!

また、DeNAでは大規模なトラフィックを捌く仕事もあって楽しいです。よかったらぜひ一緒に働きましょう!

16日目はrexitorgさんです!もう読めます: GAE/Go, Firestoreでマスターデータを管理してみた件

続きを読む
ツイート
シェア
あとで読む
ブックマーク
送る
メールで送る

Software Design 2011年9月号の特集に寄稿しました

お久しぶりです。最近グループが新設されてシステム統括本部 IT基盤部 Mobage基盤管理グループ所属になりましたiwanagaです。やってることは特に変わってませんが。。。

「ソーシャルゲームのためのMySQL入門」の続きを書こうと思っていた矢先に、Software Designの編集部の方にお声をかけて頂き、特集に記事を書かせて頂くことになりました。『ベンダ任せにしない 運用エンジニア「攻め」の仕事術』の第3章『「動き続けるものを作る」というオペレーショナルメンタリティ』ということで、私が日々携わっているMobageにおける運用エンジニアの現場の話を、結構細かめに書かせて頂きました。

続きを読む
ツイート
シェア
あとで読む
ブックマーク
送る
メールで送る

Web+DB PRESS vol.63 の Perl Hackers Hub に寄稿しました

320771787.jpg

初めまして、プラットフォームシステムグループの xaicron こと嶋田です。一部では鈴木と呼ばれていますが、実在する個人、団体とは関係ありませんのでご了承ください。

6/24 発売の Web+DB PRESS vol.63 に 「高速なWeb APIの実装とテスト」というタイトルで記事を書きましたのでちょこっと紹介します。

Mobage API を例に、どのようなことに気を付ければ高速な Web API を実装できるのかという割とニッチなネタを書きましたが、通常の Web アプリケーションであっても、そのまま転用して使えると思いますので「Web API とか興味ないし〜」と言う人も騙されたと思って読んでいただけると幸いです。

「Web API をOAuthに対応させよう」という記事や、pixiv さんの「段階的サービス拡張」という記事も載っているので、これ一冊あれば、Web API サーバーの全てを作ることが出来ますね!

また、見捨てられがちな DB や memcached を実際に使ったテスト方法についても少し説明してますので、この記事を読まれた方は、ぜひテストに挑戦していただければと思います。

樋口さん(大先輩ですので「さん」は欠かせませんね)が開発した Handler Socket についてもちょこっとだけ解説しています。 一部ではすでに導入されていて、すでに効果のほどが実証されており、今後もマッチする場所には積極的に使っていく予定です。 Handler Socket について詳しくは、こちらをご覧ください。

興味のある方は、ぜひお手に取って読んでみてください!

続きを読む
ツイート
シェア
あとで読む
ブックマーク
送る
メールで送る

ソーシャルゲームのためのMySQL入門その2

こんにちはこんにちは。11インチMacBook Airが欲しくてたまらないiwanagaです。前回の記事が幸いにもご好評を頂けた様で非常にうれしいです。嬉しくなって、ついがんばって第2弾を書いてしまいました。引き続き、ソーシャルゲームでよく使われるテーブルタイプ毎にちょっとしたテクニックを紹介していきます。

今回はちょっとライトな感じ&読み物になってしまっていますが「ユーザID単位で1つだけ持つデータ」と「パラメータなどのマスターデータ」についてご説明したいと思います。ちなみに次回はInnoDBのデータ構造の簡単な説明と複合プライマリーキーのデータについて、その次で紹介し損ねたちょっとマニアックなテクニックや性能管理のための手法を紹介することを予定しています。

続きを読む
ツイート
シェア
あとで読む
ブックマーク
送る
メールで送る

DeNA Technology Seminar #2 のスライド及び動画を公開します

この記事はすっかり公開し忘れていた物です。大変申し訳ありません。

気付けば、DeNA Technology Seminar の #3 の企画を立てている zigorou です。さて、だいぶ公開が遅れてしまった事を冒頭お詫び致します。
本、エントリ自体は 2010/07/02 に作成された物ですので、時間軸に関しては察してあげて下さいませ。

先日行われました DeNA Technology Seminar #2 にお越し頂いた皆さん、ust を視聴して下さった皆さんありがとうございます。
当日のスライド及び動画の方を公開致します。

続きを読む
ツイート
シェア
あとで読む
ブックマーク
送る
メールで送る

ソーシャルゲームのためのMySQL入門

こんにちはこんにちは。最近お腹痛いばっかり言ってることで有名なiwanagaです。

DeNAは外部的にはプラットフォーム的な部分の方がフィーチャーされることが多いですが、実はソーシャルゲームの提供も行っています。怪盗ロワイヤルとか、どこかで聞いたことがあるのではないでしょうか。

僕はDeNAでソーシャルゲームが誕生した辺りからずっとサーバサイドを見てきましたが、そんな運用の中で自分が貯めてきた知見とかTIPSをご紹介したいと思います。 かれこれ10タイトル近くはレビューしたり運用したりしてるため結構言いたいことはいっぱいあるので、小出しにしつつ評判よければ次も書きます。

ソーシャルゲームのためのMySQL入門一覧

「MySQLの話か、なんだアプリ開発の自分には関係ないな」と思ったそこのあなた!今回僕がこういう記事を書いている趣旨は、むしろ開発側の人たちにこそもっといいMySQLの使い方を知ってもらいたいと思ったからです。データストア層を使いこなせてこそ真のアプリ開発者ですよね!

続きを読む
ツイート
シェア
あとで読む
ブックマーク
送る
メールで送る

HandlerSocketソースコード公開しました

はじめまして、樋口と申します。

先日のDeNA Technology Seminar #2でお話させていただきました HandlerSocket Plugin for MySQL のソースコードを公開しました。

続きを読む
ツイート
シェア
あとで読む
ブックマーク
送る
メールで送る

MySQL Conference&Expo 2010に行ってきました

DeNA システム統括本部IT基盤部の岩永亮介といいます。お初にお目にかかります。

だいぶ報告が遅くなってしまったのですが、4月に参加してきた MySQL Conference 2010の報告を簡単にさせて頂きたいと思います。

続きを読む
ツイート
シェア
あとで読む
ブックマーク
送る
メールで送る

DeNA Technology Seminar #1 のスライド及び動画を公開します

ちょっと遅くなってしまいましたが、先日行われました DeNA Technology Seminar #1 の資料と動画を公開します。

続きを読む
ツイート
シェア
あとで読む
ブックマーク
送る
メールで送る

DBIx::ProfileManager で SQL Profiling

風邪を引きっぱなしで全然治らない山口です。恐らくネット上では zigorou と言うハンドルでご存知の方もいらっしゃるかもしれません。
まずは技術系のネタの第1弾です。

今回は実際にモバゲーオープンプラットフォームで用いている SQL Profiling の方法をご紹介致します。

続きを読む
ツイート
シェア
あとで読む
ブックマーク
送る
メールで送る