【ISUCON14】ランダム配車を近傍マッチングへ——乗車地点に近い椅子を選ぶ

前回は、Matcherが1回の呼び出しで処理する待機ライドを1件から最大10件へ増やした。マッチング待ちへの不満は33.3%から5.6〜10.0%へ減り、複数件化が待機列の解消に効くことを確認できた。

しかし、改善後のスコアは1,611点と1,873点で、改善前の1,758点を安定して上回らなかった。お迎え時間への不満も85.0〜94.4%残っている。

待機ライドを早く割り当てても、遠くにいる椅子を選べば乗車地点へ到着するまで時間がかかる。現在のMatcherは椅子を O​R​D​E​R BY RAND() で選んでおり、ライドの乗車地点も椅子の現在位置も判断材料に使っていない。今回は、このランダム配車を「乗車地点に近い空き椅子を選ぶ近傍マッチング」へ変更する。

TL;DR

• 変更内容: O​R​D​E​R BY RAND()をやめ、各ライドの乗車地点に最も近い利用可能な椅子を選択
• 改善前スコア: 1,611 / 1,873
• 改善後スコア: 5,408 / 5,215
• マッチ待ち不満: 5.6〜10.0% → 4.3% / 5.5%
• お迎え時間への不満: 85.0〜94.4% → 61.4% / 50.7%
• 結論: 複数件化で処理量を増やしたうえで近い椅子を選ぶと、マッチ待ちを悪化させず、お迎え時間とスコアを大きく改善できた

1. 前回の複数件化で残った課題

前回は、待機ライドを取得するSQLを LIMIT 1 から LIMIT 10 へ変更し、既存の椅子選択をループさせた。

S​E​L​E​C​T *
F​R​O​M rides
W​H​E​R​E chair_id IS NULL
O​R​D​E​R BY created_at
LIMIT 10;

この変更によってマッチング待ちは短くなった。一方、お迎え時間への不満は高いままだった。ボトルネックは「何件処理するか」から「どの椅子を選ぶか」へ移ったと考えられる。

現在のMatcherは、アクティブな椅子をランダムに1台選び、その椅子が使用中かどうかを別のSQLで調べる。

S​E​L​E​C​T *
F​R​O​M chairs
INNER J​O​I​N (
  S​E​L​E​C​T id
  F​R​O​M chairs
  W​H​E​R​E is_active = TRUE
  O​R​D​E​R BY RAND()
  LIMIT 1
) AS tmp ON chairs.id = tmp.id
LIMIT 1;

この処理には、次の問題がある。

1. ライドの乗車地点と椅子の現在位置を見ていない
2. 使用中の椅子も抽選対象になるため、空き椅子があっても見つからない場合がある
3. ライドごとに抽選と空き判定を繰り返し、クエリ数が増える
4. 10回の抽選に失敗すると早期 return し、取得済みの後続ライドも次回へ持ち越す

O​R​D​E​R BY RAND()と早期returnは今回の主題そのものではなく、近傍マッチングへ置き換えるべき現在の選択ロジックが抱える問題である。

2. 近傍マッチングに使えるデータ

ライドの乗車地点は、rides テーブルに保存されている。

• pickup_latitude
• pickup_longitude

椅子の位置は、chair_locations テーブルへ時系列で記録されている。

• chair_id
• latitude
• longitude
• created_at

近傍マッチングに必要なのは、各アクティブ椅子の「最新位置」である。chair_locations には (chair_id, created_at) の複合インデックスがあるため、椅子ごとの最新レコードをどう効率よく取り出すかが実装のポイントになる。

距離は、既存コードでも利用されているマンハッタン距離で比較できる。

|ride.pickup_latitude - chair.latitude|
+ |ride.pickup_longitude - chair.longitude|

絶対距離が小さい椅子ほど、乗車地点に近いと判断する。

ridesとride_statusesの役割

ridesはライド本体を表し、ユーザー、割り当てられた椅子、乗車地点、目的地点を保持する。一方、ride_statusesは状態変更の履歴であり、1件のライドに対して次の状態が時系列で追加される。

MATCHING → ENROUTE → PICKUP → CARRYING → ARRIVED → COMPLETED

ride_statuses.statusがライドの状態である。chair_sent_atは状態ではなく、その状態を椅子へ通知した日時を表す。同様に、app_sent_atはユーザーアプリへ通知した日時である。

既存Matcherは、非NULLのchair_sent_atが6件あることをライド完了の代用としている。

COUNT(chair_sent_at) = 6

これは現在の6状態を前提としており、状態が追加・変更されると意味が崩れやすい。より意図を明確にするなら、次の2点を別々に確認するほうがよい。

1. status = 'COMPLETED'が存在し、業務上ライドが完了している
2. chair_sent_at IS NULLの履歴が存在せず、椅子への通知も完了している

COMPLETEDだけで空きと判定すると、椅子が完了通知を受け取る前に次のライドが割り当てられる可能性がある。現在の通知APIは椅子に割り当てられた最新ライドを1件だけ見るため、業務状態と通知状態の両方を確認する必要がある。

3. SQLで近傍選択を段階的に確認する

いきなりMatcherを書き換えず、必要なデータをSQLで一段ずつ確認した。

アクティブな椅子の最新位置を取得する

まず、各アクティブ椅子について、chair_locations.created_atが最も新しい位置を取得した。

S​E​L​E​C​T
  c.id,
  cl.latitude,
  cl.longitude,
  cl.created_at
F​R​O​M chairs AS c
INNER J​O​I​N chair_locations AS cl
  ON cl.id = (
    S​E​L​E​C​T cl2.id
    F​R​O​M chair_locations AS cl2
    W​H​E​R​E cl2.chair_id = c.id
    O​R​D​E​R BY cl2.created_at D​E​S​C
    LIMIT 1
  )
W​H​E​R​E c.is_active = TRUE;

アクティブな椅子25台について、ID、現在座標、位置の記録日時を取得できた。実行時間は186msだった。

ここへ未完了ライドを持つ椅子の除外条件を加えると、結果は0件になった。SQLの失敗ではなく、ベンチ停止後もアクティブな25台すべてに未完了ライドが残っていたためである。

待機ライドの乗車地点を確認する

次に、最も長く待っているライドを1件取得した。

S​E​L​E​C​T
  id,
  pickup_latitude,
  pickup_longitude,
  created_at
F​R​O​M rides
W​H​E​R​E chair_id IS NULL
O​R​D​E​R BY created_at
LIMIT 1;

前回の検証で残した待機ライドが1件あり、乗車地点は(0, 0)だった。

データを変更せず距離計算を確認する

利用可能なアクティブ椅子が0台だったため、ここでは非アクティブかつ未完了ライドを持たない椅子を対象に、距離計算だけを確認した。これは診断用SQLであり、椅子の状態や割り当ては変更していない。

ABS(cl.latitude - 0) + ABS(cl.longitude - 0) AS distance

マンハッタン距離の昇順で並べると、現在地(-2, 4)の椅子が先頭になった。乗車地点(0, 0)までの距離は次の通りである。

|-2 - 0| + |4 - 0| = 2 + 4 = 6

これにより、「椅子ごとの最新位置を取得し、ライドの乗車地点との距離を計算して、近い順に並べる」という近傍マッチングの中心部分をSQLで確認できた。

4. 今回の改善方針

今回の目的は、待機ライドごとに「利用可能で、現在位置が乗車地点に最も近い椅子」を選ぶことである。

処理は次の流れを想定する。

待機ライドを作成時刻順に最大10件取得
  → アクティブかつ利用可能な椅子を抽出
  → 各椅子の最新位置を取得
  → 乗車地点との距離を計算
  → 最も近い椅子を割り当て
  → 同じ呼び出し内では割り当て済みの椅子を候補から除外

実装時には、次の点を確認する。

• 「利用可能な椅子」の判定を既存仕様と一致させる
• 同じ椅子を複数ライドへ割り当てない
• 最新位置の取得で全 chair_locations を繰り返し走査しない
• 距離が同じ場合の選択順を決め、結果を再現可能にする
• Matcherが同時実行された場合の競合余地を把握する

5. 実装

変更箇所は webapp/nodejs/src/internal_handlers.ts の internalGetMatching ハンドラーである。

待機ライドを最大10件取得する処理は残し、ライドごとに実行していた「ランダム抽選」と「抽選した椅子の空き判定」を、最寄りの利用可能な椅子を1回で取得するSQLへ置き換えた。

for (const ride of rides) {
  const [[matched]] = await ctx.var.dbConn.query<
    Array<Chair & { distance: number } & RowDataPacket>
  >(
    `
      S​E​L​E​C​T
        c.*,
        ABS(cl.latitude - ?)
          + ABS(cl.longitude - ?) AS distance
      F​R​O​M chairs AS c
      INNER J​O​I​N chair_locations AS cl
        ON cl.id = (
          S​E​L​E​C​T cl2.id
          F​R​O​M chair_locations AS cl2
          W​H​E​R​E cl2.chair_id = c.id
          O​R​D​E​R BY cl2.created_at D​E​S​C
          LIMIT 1
        )
      W​H​E​R​E c.is_active = TRUE
        AND NOT EXISTS (
          S​E​L​E​C​T 1
          F​R​O​M rides AS assigned_ride
          W​H​E​R​E assigned_ride.chair_id = c.id
            AND (
              NOT EXISTS (
                S​E​L​E​C​T 1
                F​R​O​M ride_statuses AS completed_status
                W​H​E​R​E completed_status.ride_id = assigned_ride.id
                  AND completed_status.status = 'COMPLETED'
              )
              OR EXISTS (
                S​E​L​E​C​T 1
                F​R​O​M ride_statuses AS unsent_status
                W​H​E​R​E unsent_status.ride_id = assigned_ride.id
                  AND unsent_status.chair_sent_at IS NULL
              )
            )
        )
      O​R​D​E​R BY distance, c.id
      LIMIT 1
    `,
    [ride.pickup_latitude, ride.pickup_longitude],
  );

  if (!matched) {
    break;
  }

  await ctx.var.dbConn.query(
    "U​P​D​A​T​E rides SET chair_id = ? W​H​E​R​E id = ?",
    [matched.id, ride.id],
  );
}

距離計算の?には、現在処理しているライドのpickup_latitudeとpickup_longitudeを渡す。距離が同じ場合はc.idを第2ソートキーにし、選択結果を安定させた。

利用可能な椅子が見つからない場合は、従来の早期returnではなくbreakでライドループを終了する。その後はハンドラー末尾の204 No Contentを返す。

型チェック

npx tsc --noEmit

コマンドはエラーを出さずに終了し、型チェックに成功した。

6. ベンチマーク結果

近傍マッチングの狙いは、お迎え時間を短縮してライド完了を増やすことである。スコアだけでなく、不満要因とMatcher・DBへの負荷も比較する。

改善後1回目はpass=true、スコア5,408、種別エラーなしだった。前回の複数件化後に記録した1,611点と1,873点を大きく上回った。

改善後2回目もpass=trueで、スコアは5,215だった。種別エラーはmap[5:4]で、ベンチマーカーの定義では「ユーザーのライド評価に失敗」が4件発生したことを示す。2回続けて5,000点台となり、近傍マッチングによるスコア改善には再現性が見られた。

確認したいこと

• お迎え時間への不満は85.0〜94.4%から減ったか
• ライド完了数とスコアは増えたか
• 複数件化で改善したマッチ待ち不満を維持できたか
• O​R​D​E​R BY RAND()を除いたことで結果の振れ幅は小さくなったか
• 最新位置と距離を求めるSQLが新しいボトルネックになっていないか
• Matcherの最大処理時間にスパイクが発生していないか

7. 結果の分析

お迎え時間とスコアへの効果

お迎え時間への不満は、前回の85.0〜94.4%から61.4%と50.7%へ低下した。同時にスコアは5,408点と5,215点まで伸びた。2回とも同じ傾向を示しており、乗車地点に近い椅子を選ぶ方針がライド完了とスコアへ寄与した可能性は高い。

マッチ待ちへの影響

マッチ待ちへの不満は4.3%と5.5%であり、複数件化後の5.6〜10.0%を維持、または改善した。近傍計算を追加しても、待機列の処理能力は大きく損なわれていない。

MatcherとDB負荷への影響

Matcherは1回目が91回、2回目が86回呼ばれ、平均処理時間は0.353秒と0.355秒だった。最大処理時間も3.404秒と3.092秒で、前回の最大13.147秒のような大きなスパイクは発生しなかった。

2回目のpt-query-digestでは、MySQL全体の実行時間は121秒、総検査行数は8.77 M行だった。前回の105〜112秒、8.98〜9.05 M行と比べると、検査行数はわずかに減った一方、総実行時間は増えている。

近傍マッチングで追加したchairs、chair_locations、rides、ride_statusesを参照するSQLは136回呼ばれ、合計約1.08秒、平均約8msだった。MySQL総実行時間に占める割合は0.9%であり、この計測では新しい主要ボトルネックにはなっていない。

一方、Nginxログ上ではMatcherの5xxが1回目に5件、2回目に3件発生した。コンテナログを確認すると、近傍SQLの例外ではなく、ベンチ計測スクリプトによるwebapp再起動が原因だった。

bench-with-slowlog.shは、Nginxアクセスログを初期化した後、docker restart development-webapp-1を実行して3秒待つ。その間も別コンテナのMatcherは500ms周期でAPIを呼び続けるため、webappの停止・起動中に数回のリクエストが5xxになる。ログに出ていたnpm error signal SIGTERMも、Node.jsプロセスの異常終了ではなく、この意図的なコンテナ再起動によるものだった。

再起動後のMatcherは204を返し、通常時は3〜5ms程度で応答していた。したがって、今回観測したMatcherの5xxはベンチ前処理に伴う計測上のノイズであり、近傍マッチングの失敗とは判断しない。

8. まとめと次の一手

前回の複数件化は、待機ライドを処理する量を増やす改善だった。今回の近傍マッチングは、割り当てる椅子の質を改善する取り組みである。

O​R​D​E​R BY RAND()による抽選をやめ、最新位置と乗車地点のマンハッタン距離が最小の空き椅子を選ぶようにした結果、スコアは1,611〜1,873点から5,215〜5,408点へ伸びた。お迎え時間への不満も85.0〜94.4%から50.7〜61.4%へ低下した。

一方、マッチ待ちへの不満は4.3〜5.5%に収まり、前回の複数件化による改善を維持できた。近傍SQLは平均約8ms、MySQL総実行時間の0.9%であり、今回の計測では主要ボトルネックになっていない。

これにより、「待機ライドを複数件処理する」と「近い椅子を選ぶ」はそれぞれ異なる不満要因へ効くことを確認できた。前者はマッチング成立までの待ち時間を減らし、後者は成立後のお迎え時間を短くする。処理量と割り当て品質の両方を改善したことで、初めてスコアへ大きく反映された。

ただし、お迎え時間への不満はまだ50%以上残っている。次は近傍SQLをさらに複雑にする前に、ライド完了数、椅子の稼働率、実移動時間への不満を確認し、次のボトルネックを測定する。