ISUCON14延長戦の記録③ N+1どころじゃない問題の改善

ISUCON14の延長戦をやってます

以下の記事の続きです。

furusax0621.hatenablog.com

前回はスロークエリログから必要なインデックスを割り出して追加しました。スコアは3,500程度まで伸びています。 ここからアプリケーションコードに手を入れていきます。

なお、最終的なコードは以下のリポジトリで公開しています。

github.com

N+1どころじゃない問題

出題者による解説・講評でも言及されていますが、アクセスログなどからもまず最初に目を引くのが /api/app/nearby-chairs エンドポイントの重さです。何が悪いのかは非常にわかりやすく、いわゆるN+1問題の派生と見ることができます。

https://github.com/furusax0621/isucon14-extend/blob/e5834de96efcf5e27cb7f4189951ee0f6fa8eb0d/webapp/go/app_handlers.go#L874-L941

N+1問題って？

ISUCONに参加している方にはお馴染みのアンチパターンですが、一回目のクエリで取得したN件のレコードでループを組み、そのループの中でまたクエリを組むような実装を言います。ループで発生するN回のクエリに、最初の一回分のクエリを加えることでN+1回のクエリが回ることからN+1問題と呼ばれています。

今回のテーブル定義で例を挙げるとすると、chairsテーブルとchairs_locationテーブルのような構成があると発生しやすいです。

DROP TABLE IF EXISTS chairs;
CREATE TABLE chairs
(
  id           VARCHAR(26)  NOT NULL COMMENT '椅子ID',
  owner_id     VARCHAR(26)  NOT NULL COMMENT 'オーナーID',
  name         VARCHAR(30)  NOT NULL COMMENT '椅子の名前',
  model        TEXT         NOT NULL COMMENT '椅子のモデル',
  is_active    TINYINT(1)   NOT NULL COMMENT '配椅子受付中かどうか',
  access_token VARCHAR(255) NOT NULL COMMENT 'アクセストークン',
  created_at   DATETIME(6)  NOT NULL DEFAULT CURRENT_TIMESTAMP(6) COMMENT '登録日時',
  updated_at   DATETIME(6)  NOT NULL DEFAULT CURRENT_TIMESTAMP(6) ON UPDATE CURRENT_TIMESTAMP(6) COMMENT '更新日時',
  PRIMARY KEY (id)
)
  COMMENT = '椅子情報テーブル';

DROP TABLE IF EXISTS chair_locations;
CREATE TABLE chair_locations
(
  id         VARCHAR(26) NOT NULL,
  chair_id   VARCHAR(26) NOT NULL COMMENT '椅子ID',
  latitude   INTEGER     NOT NULL COMMENT '経度',
  longitude  INTEGER     NOT NULL COMMENT '緯度',
  created_at DATETIME(6) NOT NULL DEFAULT CURRENT_TIMESTAMP(6) COMMENT '登録日時',
  PRIMARY KEY (id)
)
  COMMENT = '椅子の現在位置情報テーブル';

まずchair_locationsテーブルのレコードを取得し

SELECT * FROM chair_locations;

このクエリで取得できるN件のレコードでループを組み、chairsテーブルに問い合わせるというものです。

SELECT * FROM chairs WHERE id = ?;

解決方法としては、各テーブルをJOINしてしまうというのが一般的かなと思います。今回の例では以下のようにJOINすれば1クエリで必要な情報をすべて入手できます。

SELECT * FROM chair_locations AS cl JOIN chairs AS c ON c.id = cl.chair_id;

N+1どころじゃない問題って？

問題のコードに戻ります。該当コードですが、初期実装では次のようなロジックになっていました。

1. 椅子の情報を全件取得する（N件入手）
2. 椅子毎にループ
   1. 椅子が割り当てられたライドを全件取得（M件入手）
   2. ライド毎にループ
      1. ライドの最新ステータスを取得
   3. ライドの情報から、椅子が空いてない（＝ライド可能でない）ならコンティニュー
   4. 椅子の最新位置情報を取得

2のN回のループの中で2-2のM回ループが発生し、その中で一回（2-2-1）クエリが発行されています。更にN回ループの中では二回（2-1, 2-4）クエリが発行されています。 初回のクエリと合わせると、なんとN(M+2)+1回です。解説記事では2N+1問題と書かれていますが、このロジックは正確にはN(M+2)+1問題です！恐ろしい！

問題の分析

この問題が発生している原因ですが、一番の問題は椅子が空いている（＝ライド可能である）ことを知るために、椅子が過去に割り当てられたすべてのライドの状態を走査する必要がある点にあります。この情報を簡単に知る術があれば、わざわざライドを取得する必要はありません。

また、椅子の位置情報を保存する chair_locations テーブルは履歴を管理するテーブルであり、椅子の最新の位置情報を簡単に入手できないという点も問題です。椅子の最新の位置情報を表すレコードを特定できれば、最初のクエリにJOINすることで椅子と位置情報を一度に取得できるはずです。

N(M+2)+1問題を解消する

最終的な差分は以下のPull Requestになります。2つの問題を同時に解決しています。

github.com

椅子が空いているという情報をテーブルで管理する

椅子毎に「空いているかどうか」という情報を管理すれば良いと思ったので、chairsテーブルに is_free というカラムを追加し、ライドのライフサイクルに合わせてこのカラムを更新するように実装しました。

まずchairsテーブルへのカラム追加になるわけですが、スキーマ管理しているSQLファイルを直接編集してカラム追加したところ、デフォルト値を入れても初期データ投入でコケるようになってしまいました。。ちょっと原因がよくわからなかったので、インデックス作成と同じタイミングでカラムを追加するクエリを実行することにしました。

ALTER TABLE chairs ADD COLUMN is_free TINYINT(1) NOT NULL DEFAULT 1;

うっかりやりがちなのが、テーブル定義をキレイに見せるために既存のカラム定義の途中（例えば、 is_active の次とか）に挿入してしまうパターンです。ISUCONではほとんどのコードが SELECT * でレコードを取得しているので、カラムの順序が変わるとスキャン時に不具合を起こす可能性があります。ORM（sqlx）を使っているとはいえ、素直にカラム定義の最後に挿入するのが無難です。

カラム作成ができたら次は更新タイミングです。TRUE→FALSEになるタイミングはわかりやすく、椅子とライドがマッチングしたときです。椅子とライドのマッチングは定期実行される内部APIによって行われており、そのエンドポイントのトランザクションの一部として追加すればOKです。

一方、FALSE→TRUEになるタイミングの見極めは少し複雑です。一見するとライドが完了した、つまりユーザーがライドの評価をするエンドポイントのトランザクションの中でやれば良い気がします。しかし正直にそのタイミングで実装すると、おそらく「椅子がライド完了の通知を受け取る前に新しいライドに割り当てられた」という旨のエラーが発生し、ベンチマークに失敗します。アプリケーションマニュアルを読むと、次のように記載されています。

椅子は自分に割り当てられたライドが COMPLETED になるまで、他のライドを受理することができません。

また、椅子が自身の状態を受け取るための通知エンドポイントというものがあり、椅子はこのエンドポイントをポーリングすることで自身に割り当てられたライドの情報を管理しているらしいです。

このことから、椅子を空いているという状態に更新して良いのは「ライドが完了したという情報を椅子が受け取った」タイミングとなります。椅子の通知エンドポイントの中で、ライドの状態が COMPLETED のとき is_free カラムを更新するように実装しました。

椅子の最新位置情報をテーブルで管理する

これは単純に椅子の最新位置を記録するテーブルを追加しました。

CREATE TABLE chair_last_locations
(
  chair_id   VARCHAR(26) NOT NULL COMMENT '椅子ID',
  latitude   INTEGER     NOT NULL COMMENT '経度',
  longitude  INTEGER     NOT NULL COMMENT '緯度',
  updated_at DATETIME(6) NOT NULL DEFAULT CURRENT_TIMESTAMP(6) ON UPDATE CURRENT_TIMESTAMP(6) COMMENT '更新日時',
  PRIMARY KEY (chair_id)
)
  COMMENT = '椅子の最終位置情報テーブル';

管理方法も非常にシンプルで、chair_locationsテーブルにレコードが挿入される箇所を探し出し、同一トランザクション内でこのテーブルにUPSERTをかけるだけです。

初期データの考慮

ISUCONで毎度厄介になるのが、新しいテーブルやカラムを追加したときに発生する、初期データとのミスマッチです。今回は初期データの中に椅子や椅子の位置情報履歴が含まれているため、これらのデータから椅子の最新位置を復元しておかないと、初期状態がおかしなことになってしまいます。SQLに造詣の深い方ならINSERT SELECTなどを使ってスマートに復元できると思いますが、私のSQL力は貧弱なので愚直にchair_locationsテーブルを時系列順に取得し、chair_last_locationsテーブルにUPSERTする方法をとりました。。

なお、 is_free カラムの状態については特に復元をしていません。初期データの中に「現在稼働中のライド」が存在していたら困るのですが、初期データを検査したところすべてのライドが完了していそうだったので大丈夫だろうと判断しました。ちょっとここはズルいハックをしています。

改善後のクエリ

2つの修正により、N(M+2)+1問題のクエリは以下のようなシンプリな1クエリで実現できるようになりました。素晴らしい！

SELECT
    c.*, l.latitude, l.longitude
    FROM
        chairs AS c
JOIN
    chair_last_locations AS l
    ON
        c.id = l.chair_id
WHERE
    c.is_free = TRUE 
    AND
        c.is_active = TRUE;

まとめ・次回予告

アプリケーションコード改善の第一弾として、ループクエリによって非常に重くなっているエンドポイントを改善しました。 この状態でベンチを回したところ、該当エンドポイントは劇的に改善しましたがスコアは特に伸びませんでした。あれー？

気を落とさず次の改善箇所を探ります。つづく。