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

感想戦をお楽しみください #isucon pic.twitter.com/QL23lgakUf
— かるぱねるら (@karupanerura) September 18, 2018

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