何をやったのか

deployなどの足回りを整える
トラブルシューティング
StatsHandlerのN+1解消 by karupanerura · Pull Request #10 · karupanerura/isucon13 · GitHub
Tune reservation slots by karupanerura · Pull Request #16 · karupanerura/isucon13 · GitHub

なんやかんや、足回りを整えたりトラブルシューティングしたりで2時間くらい食ってたきがします。

StatsHandlerのN+1解消

順位を計算する処理があり、その順位とはtipの総額とリアクションの総数によって順位付けられていました。この際のもとの実装は以下のような感じです。

    # ランク算出
    my $ranking = [];
    for my $livestream ($livestreams->@*) {
        my $reactions = $app->dbh->select_one(
            q[
                SELECT COUNT(*) FROM livestreams l
                INNER JOIN reactions r ON r.livestream_id = l.id
                WHERE l.id = ?
            ],
            $livestream->id
        );

        my $total_tips = $app->dbh->select_one(
            q[
                SELECT IFNULL(SUM(l2.tip), 0) FROM livestreams l
                INNER JOIN livecomments l2 ON l2.livestream_id = l.id
                WHERE l.id = ?
            ],
            $livestream->id
        );

        my $score = $reactions + $total_tips;
        push $ranking->@* => Isupipe::Entity::LivestreamRankingEntry->new(
            livestream_id => $livestream->id,
            score => $score,
        );
    }

    my @sorted_ranking = sort {
        if ($a->score == $b->score) {
            $a->livestream_id <=> $b->livestream_id;
        }
        else {
            $a->score <=> $b->score;
        }
    } $ranking->@*;

    $ranking = \@sorted_ranking;

    my $rank = 1;
    for (my $i = scalar $ranking->@* - 1; $i >= 0; $i--) {
        my $entry = $ranking->[$i];
        if ($entry->livestream_id == $livestream_id) {
            last;
        }
        $rank++;
    }

うーん、では中間テーブルを作りましょう。

RedisのSortedSetを使うことも考えましたが、scoreが同順であった場合はlivestream_idの昇順となるように実装されているためそのへんをうまくやれるだけのRedis力が僕にはなかったです。（出来ないと思っていた。実はできるという話を聞いたけどどうやってやるのか知らないので知っているひとはコメントで教えてください。）

中間テーブルをこんな感じで作って

-- スコア
CREATE TABLE `user_scores` (
  `user_id` BIGINT NOT NULL PRIMARY KEY,
  `score` BIGINT NOT NULL,
  `user_name` VARCHAR(255) NOT NULL,
  INDEX ranking_idx (`score` DESC, `user_name` DESC)
) ENGINE=InnoDB CHARACTER SET utf8mb4 COLLATE utf8mb4_bin;

CREATE TABLE `livestream_scores` (
  `livestream_id` BIGINT NOT NULL PRIMARY KEY,
  `score` BIGINT NOT NULL,
  INDEX ranking_idx (`score` DESC, `livestream_id` DESC)
) ENGINE=InnoDB CHARACTER SET utf8mb4 COLLATE utf8mb4_bin;

更新時によしなに更新していくと、以下のような感じで順位がSQLだけで取得できるようになりました。

    $app->dbh->query('SET @r = 0');
    my $rank = $app->dbh->select_one(q!SELECT `rank` FROM (SELECT livestream_id, score, @r := @r+1 AS `rank` FROM livestream_scores ORDER BY score DESC, livestream_id DESC) a WHERE a.livestream_id = ?!, $livestream_id);

Window関数を使って DENSE_RANK() でなんとかする手もあるかもでしたが、うまくインデックスが効かないのでこういう感じにしました。

たしかまあまあスコアは上がった気がします。しかし、なんやかんやハマって2~3時間くらいこれで溶かしてしまった気がします。

reservation slotsのチューニング

元々の実装はこんな感じでした。

    # 予約枠をみて、予約が可能か調べる
    # NOTE: 並列な予約のoverbooking防止にFOR UPDATEが必要
    my $slots = $app->dbh->select_all_as(
        'Isupipe::Entity::ReservationSlot',
        'SELECT * FROM reservation_slots WHERE start_at >= ? AND end_at <= ? FOR UPDATE',
        $params->{start_at},
        $params->{end_at},
    );

    for my $slot ($slots->@*) {
        my $count = $app->dbh->select_one(
            'SELECT slot FROM reservation_slots WHERE start_at = ? AND end_at = ?',
            $slot->start_at,
            $slot->end_at,
        );
        infof('%d ~ %d予約枠の残数 = %d', $slot->start_at, $slot->end_at, $slot->slot);
        if ($count < 1) {
            $c->halt(HTTP_BAD_REQUEST, sprintf("予約期間 %d ~ %dに対して、予約区間 %d ~ %dが予約できません", TERM_START_AT, TERM_END_AT, $params->{start_at}, $params->{end_at}));
        }
    }

この手のはロックする範囲をいかに絞れるかがキモっぽいという直感と、幸いにもslotは減ることはあっても増えることがない仕様であることがわかったため、すでに空になっている予約枠を予め除外してロックを取ることでロックの競合をなるべく抑えるようにしてみました。

    # 予約枠をみて、予約が可能か調べる
    my %slots = @{
        $app->dbh->selectcol_arrayref(
            'SELECT id, slot FROM reservation_slots WHERE start_at >= ? AND end_at <= ?',
            { Columns => [ 1, 2 ] }, $params->{start_at}, $params->{end_at},
        )
    };
    if (any { $_ == 0 } values %slots) {
        $c->halt(HTTP_BAD_REQUEST, sprintf("予約期間 %d ~ %dに対して、予約区間 %d ~ %dが予約できません", TERM_START_AT, TERM_END_AT, $params->{start_at}, $params->{end_at}));
    }

    my $txn = $app->dbh->txn_scope;

    # NOTE: 並列な予約のoverbooking防止にFOR UPDATEが必要
    my $overed_slots = $app->dbh->select_one('SELECT COUNT(*) FROM reservation_slots WHERE id IN (?) AND slot = 0 FOR UPDATE', [keys %slots]);
    if ($overed_slots) {
        $c->halt(HTTP_BAD_REQUEST, sprintf("予約期間 %d ~ %dに対して、予約区間 %d ~ %dが予約できません", TERM_START_AT, TERM_END_AT, $params->{start_at}, $params->{end_at}));
    }

これも、たしかまあまあスコアは上がった気がします。

どうして複数台構成にした途端にスコアが落ちたのか

MySQLを2台目に追い出したのですが、どうやらその途端にDNS Serverのスループットが改善してDNS水責め攻撃の餌食となったようです。 2台構成が動いたのが終了10分前とかだったのでそこから元に戻すのは諦めました……。

次回に向けて

今回は素振りがほとんど出来なかったので素振りする時間をなんとか確保して、トラブルシューティングに費やす時間を減らし、チューニングの手札を増やしておきたいです。今回はnginxでキャッシュさせるといったこともほとんど出来ず、またnginx luaを使えば楽にいきそうな部分もあったのでそういったこともできるようにしていきたい。

次回もPerlで挑む覚悟で、実装移植がなかったら自前でいちからコードを書いてでもPerlで戦おうと思います。

感想

移植はモダンなPerlの機能がふんだんに使われており、面白い実装でした。（Entityクラスは正直いらなかった気がしますが……。）問題もボリューム満点で面白く、素朴なチューニングでスコアがちゃんと上がるような問題に仕上がっていてスコアが上がる楽しさも感じました。運営の皆さんには感謝の気持ちでいっぱいです。ありがとうございました。

時計を壊せ

駆け出してからそこそこ経ったWebプログラマーの雑記

ISUCON13にPerlで挑んだ

何をやったのか

StatsHandlerのN+1解消

reservation slotsのチューニング

どうして複数台構成にした途端にスコアが落ちたのか

次回に向けて

感想