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でマスターデータを管理してみた件

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

「Perl徹底攻略」が7月23日に発売になります

61U-P7UQRZL._SL500.jpg

弊社のエンジニア達が執筆している、Perl 徹底攻略が 7月23日に発売されます。

本書の概要は、

『Perl徹底攻略』では,本誌で人気のリレー連載「Perl Hackers Hub」の過去記事を中心に,Perlの基礎からモダンなPerl開発までを名だたるPerlハッカー達が解説していくほか,小飼弾さんによるインタビュー記事や,伊藤直也さん,大沢和宏(Yappo)さんによる書き下ろしなど,内容満載でお届けします。

となっております。

Perl 新機能や、はまりがちなリファレンスの説明、今時の Perl 開発環境の構築方法などから始まり、Web 開発向けの Plack/PSGI の説明、Amon2 というフレームワークや Xslate という高速なテンプレートエンジンの話、データベースやキャッシュの上手な使い方など、盛りだくさんの内容になっております。

また、Web 開発にとどまらず、様々なトピックにも触れていますので、Perl や Web に興味が無い人でも楽しめる内容になっております。

著者より一言:

「モバゲーを支える技術が惜しみなく網羅されてるので、ぜひこの書籍を手にエントリーしてください!」

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

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 について詳しくは、こちらをご覧ください。

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

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

Perlの中をgdbで覗く

こんにちは。DeNAの樋口です。

Perlで書かれたアプリを動かしているときに、Perlのプロセスが今コードの何処を実行中なのか知りたいことがよくあります。そのような場合には、gdbで実行中のプロセスにアタッチし、Perlインタプリタインスタンスの内部を覗くことによって調べることができます。また同様の方法で、プロセスのコアダンプを取り、後でじっくりデバッガで調べることも可能です。

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

DeNA and YAPC Asia 2010

すっかり秋になりましたね。皆さん美味しいもの食べてますか?

DeNA では Perl を使っているのは周知の所ですが、先日行われた YAPC Asia 2010 にもスポンサーとして協賛し、また LT も含めてスピーカーとしても何名か参加しております。今回はそれぞれの発表について簡単に紹介し、また各スピーカーのスライドを公開しているブログエントリのまとめです。

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

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

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

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

DBIx::ProfileManager で SQL Profiling

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

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

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