Yappli Tech Blog

株式会社ヤプリの開発メンバーによるブログです。最新の技術情報からチーム・働き方に関するテーマまで、日々の熱い想いを持って発信していきます。

54億回の比較とFirebase API地獄 — CSVユーザーインポートをCPUとI/Oの両面から爆速にした話

Firebase API csv

はじめに

サーバーエンジニアの 水戸(@penguin4glte) です。

ヤプリには、CSV ファイルをアップロードするとアプリのユーザーを一括で登録・削除できる「ユーザー一括インポート」機能があります。今回は、この機能が大規模なデータで遅くなっていた問題を、CPU（計算量） と I/O（外部 API 呼び出し） という 2 つの異なる切り口から改善した話を書きます。

タイトルにある「54億回の比較」と「Firebase API 地獄」は、どちらも実際にぶつかったボトルネックです。

TL;DR

  • 大規模データでユーザー一括インポートが遅くなる・タイムアウトする問題を、CPU と I/O の両面から改善
  • CPU（計算量）：差分計算が O(n²) で、最大 約 54 億回の文字列比較が発生 → map 化して O(n + m) に
  • I/O（Firebase API）：ユーザー削除を 1 件ずつ呼んでレート制限地獄 → DeleteUsers バッチ API と UID の持ち回りで呼び出しを大幅削減
  • 結果：Firebase に約 4 万件登録された状態で 1 件の CSV をインポートする（＝約 4 万件が削除される）ケースで 約 30 分 → 約 2 分（約 15 倍）

CSVユーザーインポートの処理時間：改善前(約30分) → 改善後(約2分)

背景 — ユーザー一括インポートの仕組み

エンタープライズ向けの機能として、管理画面から CSV をアップロードすると、その内容をもとにアプリのエンドユーザーを一括で登録・削除できる仕組みがあります。

データの流れは、ざっくり次のとおりです。

  1. アップロードされた CSV を読み込む
  2. 既存のユーザー一覧と突き合わせ、「追加するユーザー」と「削除するユーザー」を算出する
  3. 認証基盤である Firebase Authentication と DB に反映する

小規模なら一瞬で終わります。ところが、数万件規模の CSV を扱うエンタープライズのお客様で、インポートがいつまでも終わらない・タイムアウトするという問題が起きていました。

調べてみると、ボトルネックは大きく 2 種類ありました。1 つは CPU を食いつぶす 計算量 の問題、もう 1 つは外部 API を叩きすぎる I/O の問題です。順番に見ていきます。

問題1：54億回の文字列比較（O(n²)）

何が起きていたか

「CSV のユーザー」と「既存のユーザー」を突き合わせて差分を出す処理に、CompareByEmail というメソッドがあります。メールアドレスをキーに、ユーザーを次の 3 つに振り分けるものです。

  • どちらにもいる（重複）
  • CSV にしかいない（＝追加対象）
  • 既存にしかいない（＝削除対象）

当時の実装は、こうなっていました。

func (users FirebaseAuthUsers) CompareByEmail(targets FirebaseAuthUsers) (onlySource, duplicated, onlyTargets FirebaseAuthUsers) {
    source := users
    for _, target := range targets {
        for _, user := range source {
            if user.isEqualEmail(target) {
                duplicated = append(duplicated, user)
                break
            }
        }
    }
    return source.filterNot(duplicated), duplicated, targets.filterNot(duplicated)
}

外側のループで targets を回し、内側で source を全件走査しています。さらに filterNot の中でも同じような二重ループが走ります。つまり計算量は O(n²) です。

CSV と既存ユーザーがそれぞれ数万件あると、比較回数はその掛け算で効いてきます。ログを解析してみると目を疑いました。ある大規模なインポートでは比較回数がなんと 約 54 億回 にまで達していたのです。処理時間が大きく膨らんでいたのも、無理のない数字でした。

どう直したか

やることはシンプルで、内側のループを map での参照 に置き換えます。

func (users FirebaseAuthUsers) CompareByEmail(targets FirebaseAuthUsers) (onlySource, duplicated, onlyTargets FirebaseAuthUsers) {
    sourceByEmail := make(map[string]FirebaseAuthUser, len(users))
    for _, u := range users {
        sourceByEmail[strings.ToLower(u.Email)] = u
    }

    duplicatedEmails := make(map[string]struct{}, len(targets))
    for _, t := range targets {
        key := strings.ToLower(t.Email)
        if u, ok := sourceByEmail[key]; ok {
            duplicated = append(duplicated, u)
            duplicatedEmails[key] = struct{}{}
        } else {
            onlyTargets = append(onlyTargets, t)
        }
    }

    for _, u := range users {
        if _, ok := duplicatedEmails[strings.ToLower(u.Email)]; !ok {
            onlySource = append(onlySource, u)
        }
    }

    return
}

一度 source を map[email]User に変換してしまえば、突き合わせは map の参照だけで済みます。ループは「map を作る」「targets を 1 周する」「source を 1 周する」の合計 3 回で、それぞれが独立しているため、計算量は O(n + m) になります。メールの大文字小文字を区別しないよう、キーは小文字化してそろえています。

54 億回オーダーだった比較が、ユーザー数に比例する回数（O(n + m)）まで減りました。map への展開でメモリ使用量は O(n) 増えますが、数万件規模ではせいぜい数十 MB 程度で、実用上の問題にはなりませんでした。

ハマったところ：同じメールでもプロジェクトが違えば別ユーザー

1 点だけ注意が必要でした。この差分計算には、DB 側のユーザーを扱う、ほぼ同じ作りの姉妹メソッドもあります。そちらには「同じメールアドレスでも、所属する GCP プロジェクトが違えば別ユーザーとして扱う」という仕様がありました。

map 化のときに、うっかりメールだけをキーにすると、別プロジェクトの同名ユーザーまで巻き込んで、誤って削除対象から外してしまいます。そこで、こちら側だけはキーを「メールアドレスと GCP プロジェクト ID」の複合キーにしています。

type emailProjectKey struct{ email, gcpProjectID string }
duplicatedKeys := make(map[emailProjectKey]struct{}, len(targets))

リファクタリングで計算量を変えるときは、こうした「元の比較条件」をうっかり落とさないよう気をつける必要がありました。同一メールが複数プロジェクトに跨るケースのテストもあわせて追加し、挙動を担保しています。

問題2：Firebase API 地獄

差分が出たら、削除対象になったユーザーを Firebase Authentication から消します。ここが 2 つ目のボトルネックでした。

旧実装：1 ユーザーにつき 2 回 API を叩く

旧実装は、削除対象ユーザー 1 人ごとに、次の 2 つの API を呼んでいました。

  1. GetUserByEmail — メールアドレスから UID を引く
  2. DeleteUser — その UID を指定して 1 件だけ削除する

これを goroutine プールで並列に回していたのですが、Firebase Authentication のアカウント削除には 10 件/秒 というレート制限があります。数万件を一気に消そうとすると、すぐに QUOTA_EXCEEDED エラーに突き当たります。

エラーが出たユーザーは再帰的にリトライしていたものの、そもそも API を叩く回数が多すぎて、最後はタイムアウトによる打ち切り処理でしのいでいる状態でした。まさに API 地獄です。

これを 2 つの方向から削りました。

改善1：バッチ削除 API に切り替える

Firebase には、複数の UID をまとめて削除できる DeleteUsers（バッチ削除）API があります。1 リクエストで最大 1,000 件まで削除できます。

1 件ずつ DeleteUser を呼んでいたのを、1,000 件ずつのバッチに分割して DeleteUsers を呼ぶ形に変更しました。これだけで削除系の API 呼び出し回数は、単純計算で 1000 分の 1 になります。

const (
    batchSize  = 1000
    maxRetries = 3
)
var deleteErrs []entity.FirebaseAuthUsersDeleteError
for _, batch := range slices.Collect(slices.Chunk(users, batchSize)) {
    uids := make([]string, len(batch))
    for j, u := range batch {
        uids[j] = u.UID
    }
    var result *auth.DeleteUsersResult
    err := retry.New(
        retry.Attempts(maxRetries),
        retry.DelayType(func(uint, error, retry.DelayContext) time.Duration { return 0 }),
        retry.RetryIf(func(err error) bool { return strings.Contains(err.Error(), "QUOTA_EXCEEDED") }),
        retry.OnRetry(func(n uint, _ error) {
            // QUOTA_EXCEEDED に対して exponential backoff でリトライする
            ad.doSleep(time.Duration(1<<n) * time.Second)
        }),
    ).Do(func() error {
        var doErr error
        result, doErr = client.DeleteUsers(context.Background(), uids)
        return doErr
    })
    // result からエラーを entity に詰め替える処理が続く
}

スライスを n 件ずつに分割するところは、Go 1.23 で入った slices.Chunk を使うと素直に書けます。

リトライは「常に待つ」のではなく、QUOTA_EXCEEDED が出たときだけ retry-go で exponential backoff（1 秒 → 2 秒 …）させています。制限に当たったときにだけ待つので、無駄な待ち時間が生まれません。

改善2：UID 取得の API 呼び出しをまるごとなくす

もう 1 つ、GetUserByEmail の呼び出し自体を消しました。

削除には UID が必要です。旧実装は「メールしか手元にないので、削除のたびに GetUserByEmail で UID を引く」という作りでした。これがユーザー数分の API 呼び出しになっていたわけです。

しかし、差分を取るために最初に呼んでいる ListUsers（既存ユーザー一覧の取得）のレスポンスには、もともと UID が含まれています。そこで、ユーザーを表す構造体に UID フィールドを足し、ListUsers の時点で UID も一緒に保持するようにしました。

type FirebaseAuthUser struct {
    Email string
    // ...
    UID   string // 追加
}

こうすると、削除対象のユーザーは UID を持った状態で渡ってきます。削除のために GetUserByEmail を呼ぶ必要がなくなり、ユーザー数分の API 呼び出しがまるごと消えました。UID を引くためだけに使っていた goroutine プールも不要になり、コードもシンプルになりました。バッチ分割やリトライのふるまいについては単体テストを追加し、チャンク境界やエラー系の挙動を確認しています。

検討したが見送ったこと：ListUsers の重複呼び出し

実はもう 1 つ、ListUsers を処理中に 2 回呼んでいる箇所があり、これも 1 回にまとめようとしました。1 回目で取得した一覧を引き回して使い回す、というアイデアです。

ただ、インポートの途中で Firebase 側の状態が変わるケースまで正しく扱おうとすると、「いまキャッシュしている一覧が本当に最新か」を保証するための条件分岐が増えてしまいました。バグの温床になりそうだったので、今回はあえて毎回素直に取り直す実装に戻しています。パフォーマンスと可読性のトレードオフで、後者を選んだ形です。

結果

今回入れた改善は、大きく次の 2 つです。

  • CPU 面：差分計算を O(n²) → O(n + m) に改善
  • I/O 面：削除系の API 呼び出しを「バッチ化」（呼び出し回数は約 1000 分の 1）と「UID 取得の省略」で削減

効果がはっきり出たのは、Firebase に約 4 万件のユーザーが登録された状態で、1 件だけの CSV をインポートするケースです。CSV に含まれない残りの約 4 万件が削除対象になるため、ここで大量の削除が走ります。改善前はこの処理に約 30 分かかっていましたが、改善後は約 2 分で完走します。おおよそ 15 倍の高速化です。

CSVユーザーインポートの処理時間：改善前(約30分) → 改善後(約2分)

まとめ

今回の改善で感じたのは、「遅い」の原因は 1 種類とは限らない、ということです。

  • ロジックの中で CPU を無駄に使っている（計算量の問題）
  • 外部サービスへ過剰にリクエストを投げている（I/O の問題）

この 2 つは、原因も対処法もまったくの別物です。ログやコードを追って「どちらが効いているのか」を切り分けることが、遠回りなようで一番の近道でした。

データ量が小さいうちは、O(n²) も per-user な API 呼び出しもまず問題になりません。ところが、エンタープライズのように桁が変わると、一気に牙をむきます。「件数が増えたときに何回ループが回り、何回 API を叩くのか」を意識しておくと、こうした地雷を踏みにくくなるなと改めて思いました。

皆さんの現場でも、最初は一瞬で終わっていたのに、データ量の増加とともに牙をむき始めたバッチ処理はありませんか？