代表的な面接トピック

安定したカーソルベースのページネーションAPIをどう設計するか？

バックエンド難しい
Offer.cc 編集チーム公開日 更新日

質問

注文テーブルには2億件のレコードがあり、継続的な書き込みが発生し、created_at DESC, id DESC でソートされています。1ページあたり50件のレコードを返し、前後へのナビゲーションをサポートし、ディープページネーションによるパフォーマンス低下を防ぎ、並行した挿入・削除・ステータス変更に対する保証を明示したAPIを設計してください。

問題とスコープ

あるマルチテナントの注文サービスはPostgreSQLを使用しています。その orders テーブルには2億件のレコードが含まれ、継続的な挿入とステータス変更が発生しています。運用コンソールはテナントとステータスで注文を絞り込み、常に created_at DESC, id DESC でソートし、1ページあたり最大50行を返します。created_at と id はともに非NULLであり、作成後は不変（イミュータブル）です。id は一意です。プロダクトとしては次ページおよび前ページへのナビゲーションが必要ですが、500ページ目への直接ジャンプは不要です。

ページネーションAPI、カーソルのペイロード、クエリ、およびインデックスを設計してください。設計では、同一の作成タイムスタンプ、ディープページネーション、リクエスト間での挿入と削除、ステータス変更による対象の変動、カーソルの改ざん、および双方向のナビゲーションに対処する必要があります。また、ライブトラバーサルと固定スナップショットを区別する必要があります。

2億行という規模と50行のページサイズは面接用の前提条件です。中核となるスキルは、APIのセマンティクスをデータベースのアクセスパス、並行性の境界、および検証計画へと変換することであり、これはバックエンドの設問です。リージョン間レプリケーション、シャーディング、およびクライアント側の一覧状態管理は、第1ラウンドのスコープ外です。

面接官が見ているポイント

最初のシグナルは、候補者がアルゴリズムを選択する前に整合性を定義しているかどうかです。「重複や欠落がないこと」には対象が必要です。それはオフセットページネーションによって生じるズレを回避することを意味するのか、それともブラウジングセッション全体が1つのデータベーススナップショットのように振る舞う必要があるのか？ 通常のカーソルは順序の境界の後から再開できますが、削除、ステータス変更、その他のフィルターフィールドを凍結するわけではありません。

2番目のシグナルは全順序（Total Order）です。クエリが created_at だけでソートされている場合、複数の注文が同値になり、データベースがそれらを任意に並べる可能性があります。一意な id を2番目のソートキーとし、両方の値をカーソルに含めることで、前のページの最後の行の直後の位置を正確に特定できます。

3番目のシグナルは、クエリ、インデックス、およびカーソルが同じ順序を実装しているかどうかです。tenant_id と status は等価フィルターです。created_at と id は範囲境界とソート順を形成します。したがって、候補となるB-treeインデックスは (tenant_id, status, created_at DESC, id DESC) です。比較述語、インデックス、および逆方向クエリがなければ、「offset」という単語を「cursor」に置き換えただけでは不完全です。

最後に、面接官は具体的なコントラクトとテスト計画を期待しています。優れた回答では、フィルターと認可スコープを署名付きカーソルにバインドし、ページサイズに上限を設け、並行挿入、境界行の削除、同一タイムスタンプ、および前後往復のナビゲーションをテストします。また、1つの技術を普遍的に正しいものとして扱うのではなく、ページ番号ジャンプを必要とする小規模で安定したデータセットに対しては、オフセットページネーションを有効な選択肢として残します。

明確化のための質問

  • これはライブリストですか、それとも固定スナップショットですか？ ライブリストでは、後続のページに一部の変更が反映される場合があります。固定スナップショットでは、トラバーサルが1つの集合を参照する必要があり、通常はバージョン管理されたデータ、マテリアライズドされた結果、またはリクエストをまたいで存続するスナップショットメカニズムを使用します。コストと有効期限ポリシーが異なります。
  • ユーザーは任意のページにジャンプする必要がありますか？ キーセットページネーションは連続する次へ・前へのナビゲーションには適していますが、「500ページ目」という情報だけではキーの境界が分かりません。ページジャンプが必須の場合は、深さを制限したオフセットを維持するか、アンカーを事前計算します。
  • ソートやフィルターのフィールドは変更される可能性がありますか？ created_at と id は安定している必要があります。変更可能な updated_at、価格、またはスコアでソートすると、レコードがすでにアクセスした境界を越えてしまう可能性があります。ステータスの変更も結果の所属を変化させるため、公開コントラクトの一部とする必要があります。
  • プロダクトは正確な総件数と最後のページを必要としますか？ 1行余分にフェッチすることで hasNextPage を判定できます。正確な totalCount は別の集計コストがかかります。もっと見る（load-more）形式のインターフェースでは、すべてのページでフルカウントを強制すべきではありません。
  • カーソルの有効期間はどのくらいですか？ スキーマの変更、フィルタールールの変更、署名キーのローテーション、およびスナップショットの保持期間はすべて有効性に影響します。サーバーには有効期限エラーと、最初のページから明示的に再開する方法が必要です。
  • ページング中にテナントのアクセス権やパーミッションが変更される可能性はありますか？ カーソルが現在のリクエストの認証および認可に取って代わることは決してありません。すべてのページで現在のプリンシパルが再チェックされ、カーソルは正規化されたフィルターとスコープにバインドされているため、テナント間で再利用することはできません。

30秒の回答

「まず、これがリクエスト間でのデータベーススナップショットではなく、ライブの順序付きトラバーサルであることを確認します。不変な created_at DESC, id DESC を使用し、一意のIDでタイムスタンプの重複を解消します。次ページ用カーソルは、前ページの最後の2つの値、バージョン、フィルターのフィンガープリントを保持し、URLセーフなエンコーディングとHMAC署名を使用します。クエリは (created_at, id) < (cursor_time, cursor_id)、同一の降順、および LIMIT 51 を適用します。50行を返し、余分な1行を hasNextPage の判定に使用します。対応するインデックスは (tenant_id, status, created_at DESC, id DESC) です。前ページ用には、比較とデータベースの順序を反転させ、その後レスポンスを反転します。新しく挿入されたデータによって後続のページがズレることはありませんが、削除やステータス変更は凍結されません。厳密なスナップショットには、バージョン管理されたデータまたはマテリアライズドされたセッションが必要です。同一タイムスタンプ、並行書き込み、境界の削除、カーソルの改ざん、およびディープページの実行計画をテストします。」

ステップバイステップの解説

まずはAPIコントラクトの定義から始めます。最初のページにはカーソルがありません。前方ナビゲーションは after を受け入れ、後方ナビゲーションは before を受け入れます。1つのリクエストに両方を含めることはできません。デフォルトのページサイズは50で、サーバー側で強制される範囲は1〜100です。レスポンスの形式は次のようになります：

json
{
  "data": [],
  "pageInfo": {
    "startCursor": "...",
    "endCursor": "...",
    "hasNextPage": true,
    "hasPreviousPage": false
  }
}

startCursor と endCursor は、返された最初と最後の行から取得されます。51行を要求し、50行のみを返すことで hasNextPage を判定します。逆方向のフラグを厳密にする必要がある場合は、もう一方の境界から小さなインデックス付き EXISTS クエリを実行します。after パラメータの存在だけで判定すると、先行するすべての行が削除された後に誤った結果になる可能性があります。

位置指定オフセットを複合境界に置き換える

最初のページのクエリは以下のとおりです：

sql
SELECT id, created_at, total_cents, status
FROM orders
WHERE tenant_id = $1
  AND status = $2
ORDER BY created_at DESC, id DESC
LIMIT 51;

次のページでは、前のページの最後の (created_at, id) のペアを厳密な小なり述語に配置します：

sql
SELECT id, created_at, total_cents, status
FROM orders
WHERE tenant_id = $1
  AND status = $2
  AND (created_at, id) < ($3, $4)
ORDER BY created_at DESC, id DESC
LIMIT 51;

PostgreSQLは行コンストラクタを左から右に比較し、最初に一致しないペアで停止します。これは2つの降順ソートキーの辞書順境界と一致します。両方のカラムを非NULLとして定義することで、行比較が NULL に達したときに発生する不明な結果（UNKNOWN）を回避できます。id は時間をエンコードする必要はなく、単一の created_at 値の中で一意で安定した同順位の解消手段を提供できれば十分です。

対応するインデックスは次のとおりです：

sql
CREATE INDEX CONCURRENTLY orders_tenant_status_created_id_idx
ON orders (tenant_id, status, created_at DESC, id DESC);

先頭の等価カラムにより、スキャンが単一のテナントとステータスに限定されます。末尾の2つのカラムが境界と順序を提供します。レスポンスフィールドを含めるカラム（INCLUDE）として追加するかどうかは、測定された行のサイズ、ヒープフェッチ、および書き込み増幅に依存します。すべてのレスポンスフィールドを INCLUDE にコピーすることはデフォルトではありません。頻繁なステータス変更でもこのインデックスがメンテナンスされるため、書き込みレイテンシ、WALボリューム、インデックスサイズを測定してください。

カーソルを進化可能かつ改ざん検知可能にする

カーソルは不透明なプロトコルであり、クライアントに created_at の値を組み立てるよう要求するものではありません。その論理ペイロードは次のようになります：

json
{
  "v": 1,
  "createdAt": "2026-07-16T02:30:00.123Z",
  "id": "ord_01J...",
  "filterHash": "sha256:...",
  "expiresAt": "2026-07-17T02:30:00Z"
}

サーバーは正規化されたペイロードにURLセーフなエンコーディングを適用し、HMACを付加します。Base64はエンコーディングであり、機密性を保つものではありません。境界値が機密情報である場合は、クライアントトークンに露出させず、代わりにサーバー側でランダムなカーソルIDの下に保存してください。filterHash は、少なくとも順序のバージョン、ステータスフィルター、および認可スコープ識別子をカバーする必要があります。サーバーが署名、バージョン、有効期限、およびフィルターのフィンガープリントを検証する前に、すべてのリクエストは現在のプリンシパルに対して認可されます。不一致がある場合は安定した invalid_cursor レスポンスを返し、最初のページからの再開を要求します。カーソルを新しいフィルターに暗黙的に適用してはなりません。

バージョンフィールドにより、将来の順序やエンコーディングの変更が可能になります。キーのローテーション中、検証側はカーソルの最大有効期間内であれば現在と過去の両方の検証キーを受け入れ、新しいカーソルの署名は現在のキーのみで行うことができます。ログには完全なカーソルや平文のフィルターではなく、エラーカテゴリとカーソルバージョンを記録します。

前のページを対称的に実装する

現在のページの先頭行が、より新しいレコードへナビゲートするための境界となります。述語を > に変更し、昇順でクエリを実行することで、データベースはまずその境界に最も近い50行を返します：

sql
SELECT id, created_at, total_cents, status
FROM orders
WHERE tenant_id = $1
  AND status = $2
  AND (created_at, id) > ($3, $4)
ORDER BY created_at ASC, id ASC
LIMIT 51;

51行目の検証用レコードを除去した後、サーバーは結果を反転し、公開用の降順で返します。LIMIT で降順のまま維持すると、境界の直前のページではなく、結果セット全体の先頭50行が選択されてしまいます。双方向で同一のフィルターフィンガープリントと順序バージョンを共有する必要があります。

並行変更下での保証の明示

ライブセマンティクスにおいて、カーソルは「この不変な境界より厳密に下にある行から継続する」ことを意味します。ユーザーが1ページ目を読んだ後に100件の新しい注文が届いたとしても、2ページ目は古い境界から再開されます。新しい行によって1ページ目の最後の行が2ページ目に押し出されることはありません。境界行を後から削除しても、カーソルが値を保持しているためトラバーサルが壊れることはなく、クエリがその行を再度見つける必要もありません。

これは固定スナップショットではありません。未読の注文が別のステータスから選択されたステータスに変更された場合、そのソート位置が現在の境界より下にあれば後から表示される可能性があります。フィルター条件から外れた注文は表示されなくなります。削除によってトラバーサルで観察される行が減ることもあります。カーソルに「1ページ目の開始時刻」を入れても、新しい挿入をフェンスで囲むだけであり、削除やステータス変更を凍結するわけではありません。

エクスポート、照合、または監査で1つの固定された集合の全メンバーを含める必要がある場合、1つの選択肢は、一致する注文IDとその順序を保存する短寿命のマテリアライズド結果です。もう1つは、タイムトラベルをサポートするバージョン管理されたデータに対する読み取りです。制御されたバックグラウンドジョブで単一のデータベーススナップショットを保持することもできます。それぞれの選択肢にはストレージ、トランザクション寿命、またはクリーンアップのコストが伴い、セッションの有効期限が必要です。ライブキーセットトラバーサルは通常、インタラクティブなリストに適しています。監査ワークロードには個別のスナップショットワークフローを用意するべきです。

オフセットページネーションを有用な範囲内にとどめる

オフセットページネーションはシンプルで、直接のページジャンプをサポートし、ページ番号に自然にマッピングされます。これは、小規模で安定した管理テーブルや、すでに固定された検索結果に対して機能します。そのコストは2点あります。PostgreSQLは依然として OFFSET より前の行を計算して破棄する必要があるため、オフセットが深くなるほど一般に多くの作業が必要になります。また、並行する挿入や削除によって位置番号が変化し、行の重複やスキップが発生する可能性があります。

キーセットページネーションはインデックス化された値の境界に作業を固定するため、ディープページであっても、単にオフセット番号が大きいという理由だけで先行するすべての行をスキャンして破棄することはありません。アンカーなしで任意のページにジャンプすることはできません。判断基準は明確です。変化するデータに対する深い順次トラバーサルにはキーセットを使用し、小規模または固定されたデータに対する限定的なページ番号ナビゲーションにはオフセットを使用します。集合全体を固定する必要がある場合は、どちらのページネーションスタイルとも独立してスナップショットメカニズムを追加します。

敵対的なケースでコントラクトを検証する

レイテンシを測定する前に、所属と順序を検証します：

  1. 同一の created_at を持つ120件の注文を挿入します。一意の id によってページ間での重複が防止され、結合されたトラバーサルが厳密な降順になっていることを確認します。
  2. 1ページ目を読み取った後、100件の新しい注文を挿入します。オフセット方式での位置ズレを再現し、キーセット方式の2ページ目が1ページ目の行を重複して返さないことを確認します。
  3. 次に進む前に1ページ目の最後の行を削除し、保存された境界によって正しい次ページが引き続き返されることを確認します。
  4. リクエスト間で未読の注文の status を変更し、結果がスナップショットとして報告されるのではなく、文書化されたライブセマンティクスに従っていることを確認します。
  5. カーソルの1バイトを変更する、テナントをまたいで再利用する、ステータスフィルターを変更する、期限切れのバージョンを送信するなどの操作を行います。すべてのリクエストが拒否される必要があります。
  6. IDと順序を確認しながら、3ページ進んで3ページ戻ります。結果サイズが0、1、50、51件のケースを含めます。
  7. 1ページ目、2ページ目、および深い境界に対して EXPLAIN (ANALYZE, BUFFERS) を実行します。期待される複合インデックス、ページサイズに近いスキャン行数を確認し、読み取りp95、書き込みp95、WALボリューム、およびインデックスサイズを記録します。

優れた回答の例

「まず保証範囲を限定します。この運用リストにはライブの順次ブラウジングが必要であり、直接のページジャンプや複数のHTTPリクエストにまたがるデータベーススナップショットは不要です。したがって、オフセットではなくキーセットページネーションを採用します。

順序は不変な created_at DESC, id DESC です。IDは一意な同順位解消キーです。これがないと、同じミリ秒で作成された注文の順序が安定しません。51行をフェッチして50行を返します。次のカーソルには最後の行のタイムスタンプとIDが格納され、次のクエリはまったく同じ順序で (created_at, id) < (?, ?) を使用します。等価フィルターは (tenant_id, status, created_at DESC, id DESC) の先頭に来ます。前のページに対しては、現在の先頭行が境界となります。> を使用し、最も近い51行を昇順でクエリしてから、レスポンスを反転します。

カーソルにはバージョン、2つの境界値、フィルターのフィンガープリント、有効期限が含まれます。URLセーフでエンコードされ、HMAC署名が付与されます。サーバーはすべてのページで再度認可を行い、改ざんされた、期限切れの、またはフィルターが一致しないカーソルを拒否します。境界行が存続していることには依存しないため、その行が削除されてもナビゲーションが停止することはありません。

整合性については、オフセットのズレによる重複を回避することを保証します。1ページ目の後に追加された新しい注文が以降のページに入り込むことはありませんが、ステータスの変更や削除によって未読の集合が変化する可能性はあります。照合で固定スナップショットが必要な場合は、マテリアライズドエクスポートセッションを作成するかバージョン管理されたデータを読み取ります。通常のカーソルにタイムスタンプを追加するだけでは完全なスナップショットにはなりません。

最後に、同一タイムスタンプ、並行挿入、境界の削除、ステータス変更、カーソルの改ざん、および前後往復のナビゲーションをテストします。その後、1ページ目、2ページ目、深い境界の実行計画を比較し、新しいインデックスが書き込みレイテンシとWALに与える影響を確認します。」

よくある落とし穴

  • ページ番号をBase64エンコードする → サーバーは依然として OFFSET を実行するため、パフォーマンスも位置ズレも改善されません → カーソルがインデックス付きの順序境界を表すようにします。
  • created_at のみを使用する → 同一のタイムスタンプは全順序を形成しないため、重複やスキップが発生する可能性があります → クエリとカーソルの両方に一意で安定した id を追加します。
  • ソート順と一致しない述語を使用する → 境界が公開順序を表さなくなり、重複やギャップが生じます → 単一の辞書順から ORDER BY、比較演算子、およびインデックスを導出します。
  • Base64を改ざん防止として扱う → クライアントがタイムスタンプ、ID、またはフィルタースコープを変更できてしまいます → 完全性のためにHMACを使用し、現在の認可を再実行します。
  • フィルターをカーソルのバインドから除外する → 保留中注文のカーソルを支払い済み注文のクエリに再利用すると、説明のつかないギャップが生じます → 正規化されたフィルター、順序バージョン、スコープを署名付きフィンガープリントに含めます。
  • 前ページのLIMITで降順を維持する → クエリは境界の隣のセグメントではなく、セット全体の先頭を返してしまいます → データベースの順序を反転し、トリミングして、レスポンスを反転させます。
  • キーセットが完全なスナップショットであると主張する → 削除、ステータス変更、変更可能なソートキーによって依然として所属メンバーが変わります → ライブセマンティクスを明記し、厳密な整合性が必要な場合はバージョン管理またはマテリアライズドスナップショットを追加します。
  • すべてのページで結果全体のカウントを行う → ページネーションは高速化されますが、totalCount が新たなボトルネックになります → カウントは、キャッシュ可能または概算の独立したプロダクト機能として扱います。
  • 1ページ目のみをテストする → 複合境界は2ページ目で初めて実行され、そこでインデックスの不一致が表面化する可能性があります → 最初の2ページ、ディープページ、および両方向の実行計画を検証します。

フォローアップの質問

プロダクトで変更可能な total_cents によるソートが必要な場合はどうしますか？

複合カーソルを (total_cents, id) にすることはできますが、それは同順位を解消するだけです。金額が編集されたレコードが、すでにアクセスした境界を越えて移動することを防ぐことはできません。ライブでの再並び替えが許容される場合は、重複や欠落の可能性を文書化し、クライアント側でIDによる重複排除を行います。安定性が必須の場合は、ブラウジングセッションの間ソート値を凍結するか、IDリストをマテリアライズするか、編集時に新しいバージョンを作成するようにします。不変キーの保証は適用されなくなります。

ユーザーが500ページ目に直接ジャンプする必要がある場合はどうしますか？

キーセットページネーションは500ページ目の境界を把握できません。まず、真のニーズが日付、注文番号、またはページラベルのいずれであるかを確認します。日付や注文番号はインデックス付きの検索アンカーになり得ます。数値のページ番号が必須である場合は、ジャンプの深さに上限を設けてその範囲内でオフセットを使用するか、定期的なページアンカーを保存して最も近いアンカーからキーセット検索を行います。ライブデータ下ではアンカーも古くなるため、バージョンまたはスナップショット識別子が必要です。

このAPIで2億行すべてをエクスポートできますか？

インタラクティブAPIの短寿命カーソルとライブセマンティクスは、長時間の監査エクスポートには適していません。バックグラウンドのエクスポートジョブを作成し、固定スナップショットまたはバージョン境界を不変のプライマリキーのチャンク単位で読み取り、オブジェクトストレージに書き込み、チェックポイントと検証カウントを永続化します。これにより、オンラインインデックスや署名フォーマットに単一のHTTPカーソルを無期限にバインドする代わりに、リトライ、有効期限、リソース制限、完了チェックが独自のライフサイクルを持つようになります。

ページネーション中の署名キーのローテーションはどのように行いますか？

カーソルにバージョンまたはキー識別子を含めます。カーソルの最大有効期間内であれば、検証側は現在と過去の両方の検証キーを保持し、新しいカーソルは現在のキーのみで署名します。その期間が経過した後に古いキーを削除します。セキュリティインシデントにより即時失効が必要な場合は、シームレスなナビゲーションのために侵害されたキーを受け入れるのではなく、一貫して invalid_cursor を返し、クライアントを1ページ目から再開させます。

境界行の削除は機能するのに、そのソートキーの変更が機能しないのはなぜですか？

次のクエリに必要なのはカーソルに保存されている2つの値だけです。境界行を再度見つける必要はないため、削除しても厳密な小なり述語は変わりません。ソートキーを編集すると、同じレコードが境界の片側からもう一方の側へ移動します。将来の範囲に再度入ってきたり、未読の範囲からすでにアクセスした範囲へジャンプしたりする可能性があります。安定したソート値は正確性の要件ですが、境界行が存続し続けることは要件ではありません。

公開情報ソース

Cursor Pagination Low-Level Design

techinterview.org

PostgreSQL 18 Documentation: LIMIT and OFFSET

PostgreSQL Global Development Group

PostgreSQL 18 Documentation: Row and Array Comparisons

PostgreSQL Global Development Group

PostgreSQL 18 Documentation: Multicolumn Indexes

PostgreSQL Global Development Group

Keyset Pagination

GitLab Docs

Using Pagination in the GraphQL API

GitHub Docs

Pagination

Stripe API Reference

関連する質問

PostgreSQLでダウンタイムゼロのスキーマ移行を実行するにはどうすればよいか？質問と回答を開く低速なPostgreSQLクエリをどのように診断・最適化しますか？質問と回答を開くホットキーの有効期限切れ時にキャッシュスタンピードを防ぐにはどうすればよいか？質問と回答を開く
無料で登録