Posted inデータベース

OFFSETの先へ：APIスケーリングにカーソルベースのパジネーションが不可欠な理由

Database tutorial - IT technology blog
Database tutorial - IT technology blog

APIが限界に達した日

ある火曜日のこと、私たちのECプラットフォームがついに限界を迎えました。ステージング環境では1万点程度の製品数で「無限スクロール」機能は完璧に動作していました。しかし、本番環境でレコード数が250万件を超えた途端、ユーザーから不満の声が上がり始めました。モニタリングツールが示した現実は過酷なものでした。1ページ目のクエリはわずか15msで完了していましたが、「500ページ目」の取得には2.4秒もかかり、CPU使用率は85%まで急上昇していたのです。

これまでMySQL、PostgreSQL、MongoDBなどでシステムを構築してきましたが、このパターンを何度も目にしてきました。これらのエンジンにはそれぞれ強みがありますが、共通の致命的な欠陥があります。それが OFFSET です。数千行を超えるスケーリングを目指すなら、従来のスキップベースのロジックは即刻捨てるべきです。

失速の数学的背景：なぜOFFSETは失敗するのか

多くの開発者が LIMIT と OFFSET を使うのは、それが直感的だからです。20個ずつのアイテムの5ページ目が必要な場合、ロジックはシンプルに見えます。

-- 1,000行なら動作しますが、100万行では処理が止まります
SELECT * FROM orders
ORDER BY created_at DESC
LIMIT 20 OFFSET 80;

ここで問題が発生します。81行目から始まる20件のレコードを提供するために、データベースは単にその場所にジャンプするわけではありません。最初の80件をスキャンし、ソートしてから、開始地点に到達するためだけにそれらを破棄しなければならないのです。オフセットが1,000,000の場合、エンジンは100万行をメモリに読み込んでソートするという重労働を行い、その作業の99.9%をゴミ箱に捨てることになります。

これにより O(N) の計算量 が発生します。クエリ時間はデータ量に比例して増大します。これは、データベースが実際に高負荷にさらされるまで隠れているパフォーマンスの負債です。

戦略の比較

1. 従来の OFFSET/LIMIT

  • 長所: 書くのが非常に簡単。「10ページ目へ移動」のように、ユーザーが特定のページにジャンプすることも可能です。
  • 短所: スクロールが深くなるにつれてパフォーマンスが低下します。また、結果の「ドリフト（ずれ）」が発生しやすいという問題もあります。ユーザーが1ページ目を見ている間に新しいアイテムが追加されると、2ページ目に同じアイテムが再び表示される可能性があります。

2. カーソルベースのパジネーション（キーセットパジネーション）

データベースに何行スキップするかを伝える代わりに、前回終了した特定の座標を指定します。主キーや高精度のタイムスタンプなど、一意でソートされたカラムをポインタとして使用します。

-- 高パフォーマンスな方法
SELECT * FROM orders
WHERE id < 12345
ORDER BY id DESC
LIMIT 20;
  • 長所: 適切なインデックスがあれば、常に O(1) のパフォーマンスを提供できます。また、レコードのスキップや重複なしにリアルタイムデータを適切に処理できます。
  • 短所: 500ページ目に「ジャンプ」することはできません。「次へ」と「前へ」のナビゲーションのみをサポートします。

本番環境でのカーソルの実装

キビキビとしたレスポンスを求めるなら、カーソルが標準です。SlackやStripeのようなプラットフォームは、このように大規模なデータストリームを処理しています。私が本番環境で使用しているワークフローを以下に示します。

ステップ1：ポインタの特定

カーソルは一意であり、一貫してソートされている必要があります。標準的な id でも機能しますが、 created_at でソートする必要がある場合は、 id と組み合わせる必要があります。タイムスタンプだけを使うのはリスクがあります。2つのレコードが同じミリ秒を共有している場合、一方が完全にスキップされる可能性があるからです。

ステップ2：最適化されたクエリ

PostgreSQLやMySQLでは、最初のリクエストは以下のようになります。

-- 最初のページを取得
SELECT id, title, created_at 
FROM posts 
ORDER BY id DESC 
LIMIT 21; -- 「次」のページが存在するか確認するために21件取得します

ユーザーが次のバッチをリクエストすると、フロントエンドは最後のアイテムのID（例：ID 500）を返します。次のクエリは以下のようになります。

-- 次のセットに直接ジャンプ
SELECT id, title, created_at 
FROM posts 
WHERE id < 500 
ORDER BY id DESC 
LIMIT 21;

ステップ3：APIレスポンスの構造化

URLに内部データベースのIDを露出させるのは避けましょう。カーソルを不透明な文字列（opaque string）にエンコードすることで、後でフロントエンドを壊すことなく基盤となるロジックを変更できる自由度が得られます。以下は、PythonとFastAPIを使用したクリーンな実装例です。

import base64

def encode_cursor(record_id):
    return base64.b64encode(str(record_id).encode()).decode()

def decode_cursor(cursor_string):
    return int(base64.b64decode(cursor_string).decode())

@app.get("/posts")
def get_posts(cursor: str = None, limit: int = 20):
    # ベースクエリ
    query = "SELECT * FROM posts"
    
    if cursor:
        last_id = decode_cursor(cursor)
        query += f" WHERE id < {last_id}"
    
    query += " ORDER BY id DESC LIMIT 21"
    # ... クエリを実行 ...
    
    has_next = len(results) > limit
    data = results[:limit]
    
    # 次のリクエストのためのポインタを生成
    next_cursor = encode_cursor(data[-1]['id']) if has_next else None
    
    return {
        "data": data,
        "paging": {
            "next_cursor": next_cursor,
            "has_next": has_next
        }
    }

現場のメモ：苦労して得た教訓

1. インデックスは必須

カーソルパジネーションが速いのは、インデックスを使用して開始行へ直接ジャンプするからです。 WHERE 句と ORDER BY 句が複合インデックス（composite index）と一致していない場合、データベースはフルテーブルスキャン（full table scan）にフォールバックします。上記の例では、 id のインデックスが命綱となります。

2. 非一意なカラムでのソート

もし price でソートする必要がある場合、安定した順序を維持するためにカーソルに id を含める必要があります。SQLは以下のようになります。

-- 価格でソートし、IDをタイブレーカーとして使用
SELECT * FROM products
WHERE (price, id) < (99.99, 500)
ORDER BY price DESC, id DESC
LIMIT 20;

PostgreSQLは、これらの行値比較（row-value comparisons）を美しく処理します。MySQL 5.7以降もこれをサポートしていますが、古いバージョンでは同じ結果を得るためにより冗長な OR ロジックが必要になる場合があります。

3. UIについて正直になる

ステークホルダーの期待値を管理する必要があります。カーソルベースのパジネーションでは、フッターに「10,000ページ中1ページ目」と表示することはできません。ページ番号を犠牲にして速度を手に入れているのです。無限スクロールや「もっと見る」ボタンを使用する現代的なアプリでは、これがほぼ常に正解となります。

まとめ

OFFSET を捨てることは、私がこれまで実施した中で最も効果的な最適化の1つでした。テーブルが数千万行に成長しても、遅くて予測不可能なエンドポイントを、30ms未満でレスポンスを返す信頼性の高いものに変えることができました。APIコントラクトの設定には少し手間がかかりますが、パフォーマンス上の利点は絶大です。今日から新しいサービスを始めるなら、最初のコミットからカーソルを使用して構築しましょう。

Share:
Tags: