質問と背景
この質問は、バックエンドエンジニアが深いページのパフォーマンス、同時書き込み時の安定した順序付け、そして明示的なカーソルコントラクトを同時に処理できるかどうかをテストします。クライアントが注文履歴や変化し続けるフィードを時間の降順で1ページあたり50行ずつ閲覧し、新しい行が継続的に到着する状況を想定します。クライアントが必要とするのは主に次のページであり、任意のページへのジャンプではありません。
このトピックはバックエンド、データサービス、プラットフォームのロールに適しています。カーソルが常に高速であると決めつけてはいけません。それぞれの制約によって選択が変わるため、まずはソート順、ページジャンプ、エクスポート、整合性、削除セマンティクス、レプリカ、インデックスを明確にします。
面接官が評価している点
優れた回答では、深い OFFSET が以前の行をスキャンして破棄する理由、非一意のソートキーが同時書き込み下でずれる理由、そして keyset ページネーションが安定した全順序と一致するインデックスを必要とする理由を説明します。また、ステートレスな keyset トークンとトランザクションを保持するデータベースカーソルを区別し、重複、欠落、削除された境界行、改ざんされたトークンに対するテストを提案します。
尋ねるべき確認の質問
- ユーザーはページ N へのジャンプや合計件数の確認を必要としていますか？純粋な keyset ページネーションではそれを直接提供できません。
- ソート順はどうなっていますか？タイムスタンプは一意かつ不変ですか、それともタイブレーカーとして一意の ID が必要ですか？
- クライアントは1回の巡回に対してライブビューを求めていますか、それともスナップショットを求めていますか？挿入と削除の見え方はそれぞれで異なります。
- クエリはレプリカ、シャード、またはテナントフィルターをまたぎますか？インデックスとトークンはそれらの条件をバインドする必要があります。
- クライアントはカーソルをデコード、変更、またはリプレイできますか？それによって署名、有効期限、バージョニングが決まります。
30秒の回答フレームワーク
「まず順序付け、ページジャンプ、整合性セマンティクスを明確にします。頻繁に変更される大規模なリストに対しては、一致する複合インデックスに支えられた created_at DESC, id DESC などの一意のタイブレーカーを持つ keyset ページネーションを使用します。次のリクエストには深い OFFSET ではなく、最後の行のソートキーを含めます。カーソルはフィルター、ソートバージョン、境界をエンコードし、署名されて有効期限が付与されます。巡回に固定スナップショットが必要な場合は、タイムスタンプまたはトランザクション型データベースカーソルを検討し、そのリソースコストを説明します。同時挿入、削除、重複タイムスタンプ、改ざんされたトークンを用いてコントラクトを検証します。」
ステップごとの回答
ステップ 1: ページネーションコントラクトを定義する
limit の上限、デフォルトのソート順、next_cursor、has_more、およびフィルターを指定します。安定した順序付けには全順序が必要です。行間でタイムスタンプが共有される場合、created_at だけでソートするのは曖昧になるため、不変の一意 ID を追加します。クライアントが前のページを必要とする場合は、単に次ページ用クエリを逆転させるのではなく、逆方向の比較と境界処理を明示的に設計します。
ステップ 2: OFFSETのパフォーマンスとズレを説明する
OFFSET k LIMIT n は通常、データベースが先行する k 行を特定してスキップする必要があるため、深いページでの処理負荷は k に比例して増加します。既に読み取られたページより前に挿入または削除が発生すると、後続のオフセットが移動し、重複や欠落が発生する可能性があります。ページジャンプが必要な、小さくほぼ静的な管理画面リストであれば OFFSET を許容できる場合もありますが、深さに上限を設け、実行計画でコストを検証します。
ステップ 3: 安定した全順序の上で keyset を実装する
降順の (created_at, id) の場合、最初のページには境界がなく、次のページは最後の行のキーを使用します。
-- first page
SELECT id, title, created_at
FROM posts
ORDER BY created_at DESC, id DESC
LIMIT 50;
-- next page: boundary comes from the last returned row
SELECT id, title, created_at
FROM posts
WHERE (created_at, id) < (:last_created_at, :last_id)
ORDER BY created_at DESC, id DESC
LIMIT 50;クエリはインデックス境界からシークし、前のすべてのページをスキップする代わりに、制限された行数のみをスキャンします。複合インデックスのカラム順序、フィルター、ソート方向はクエリと一致している必要があります。そうでなければ、理論上優れた keyset クエリであっても広範囲をスキャンしてしまう可能性があります。
ステップ 4: 検証可能なカーソルトークンを設計する
内部のオフセットをカーソルとして扱ってはいけません。境界キー、フィルターダイジェスト、ソートバージョン、有効期限を含めます。クライアントが変更できないように、トークンに署名するか認証付き暗号を使用します。受信時には、リクエストに対してバージョン、テナント、フィルターを検証します。ソート順が変更された場合は、同じトークンを異なる順序で解釈するのではなく、古いバージョンを拒否するか明示的に再開します。
ステップ 5: ライブまたはスナップショットセマンティクスを選択する
ライブ keyset ページネーションでは新しい行が先頭に表示され、すでに境界を超えた行は通常繰り返されません。境界行を削除しても再表示されることはありませんが、合計カウントは変化します。固定されたデータセットが必要なエクスポートや監査の場合は、読み取りタイムスタンプ、スナップショットバージョン、またはデータベースカーソルをコントラクトに含めます。データベースカーソルはトランザクションとリソースを保持し続ける可能性があるため、長時間の HTTP ページネーションに無条件で適しているわけではありません。
ステップ 6: レプリカ、シャード、境界行を処理する
レプリカの遅延により、プライマリから返された行が一時的に見えなくなることがあります。ルーティングを固定するか、確認済みの時間境界を保持するか、結果整合性をドキュメント化します。シャードをまたぐ場合、各シャードがローカル keyset を生成し、サービスがカーソル対応の k-way マージを実行できます。最後の境界行の削除、同一のタイムスタンプ、フィルターの変更をテストします。
ステップ 7: パフォーマンスと正確性を検証する
パフォーマンス検証には、深いページでの行スキャン数、P95レイテンシ、インデックス使用状況が含まれます。正確性テストでは、リクエスト間で挿入、削除、更新を行い、約束された重複や欠落の挙動をアサートします。本番環境のズレを具体的な境界とマッピングできるように、各ページのフィルター、ソートバージョン、最初と最後のキー、トークンバージョンを記録します。
優れた回答例
「まず、ユーザーがページジャンプ、合計件数、固定スナップショットのいずれを必要としているか、またソートフィールドが一意であるかどうかを確認します。継続的に書き込まれ、主に前方へ閲覧されるリストに対しては、keyset ページネーションを選択します。全順序と複合インデックスのために不変の created_at と一意の id を使用し、最後の行の2つのキーを次の範囲境界として使用します。深いページでも過去のすべての行をスキャンして破棄することはなく、境界前の挿入が以降のすべてのページをずらすこともありません。
フィルター、ソートバージョン、境界キー、有効期限を署名付きトークンにエンコードし、トークンのテナントとフィルターがリクエストと一致することを要求します。ライブセマンティクスの下では新しい行が先頭に表示されます。監査レベルの固定結果にはタイムスタンプまたは制御されたトランザクションカーソルを検討し、長時間のトランザクションコストを説明します。レプリカがある場合は、ルーティングを固定するか可視性境界をドキュメント化します。
最後に、深いスキャン、重複タイムスタンプ、挿入、削除、境界行の更新、レプリカ遅延、トークン改ざんを網羅した実行計画と並行性テストを検証します。ページジャンプが必須である小さな管理画面リストなら OFFSET を維持することもできますが、深さに上限を設け、レイテンシを監視します。」
よくある間違い
- カーソルは常に高速であると主張する → ジャンプや長時間トランザクションのコストを無視している → 制約に応じて OFFSET、keyset、データベースカーソルを比較する。
- 時間だけでソートする → 同一値がある場合に順序が不安定になる → 不変の一意 ID を追加する。
- トークンにオフセット数値を設定する → 深いページで依然としてズレが生じ、コストが高くなる → ソート境界とフィルターダイジェストを保持する。
- ライブ/スナップショットを未定義のままにする → クライアントが挿入や削除を解釈できない → API コントラクトで可視性セマンティクスを明記する。
- インデックスの方向とフィルターを無視する → keyset であっても多数の行をスキャンしてしまう → 実行計画で複合インデックスを検証する。
- クライアントのカーソルを無検証で受け入れる → テナントや古い境界が偽造される可能性がある → 署名、バージョンの検証、トークンの失効を行う。
フォローアップの質問と回答
フォローアップ 1: ユーザーが500ページ目にジャンプする必要があります。どうしますか？
小さくほぼ静的な管理画面リストであれば、上限付きの OFFSET が合理的です。大規模なリストの場合は、任意の深さで低レイテンシを約束するのではなく、事前に計算されたページ境界や検索・ソートフィルターを使用してユーザーが目的の領域を絞り込めるようにします。いずれの選択肢についてもコストと整合性の限界をドキュメント化します。
フォローアップ 2: created_at が編集可能です。カーソルは安定していますか？
いいえ。不変の作成時間と一意の ID を使用するか、ミュータブルなソートフィールドをスナップショットバージョンに固定します。ビジネス要件として変更可能なフィールドでソートする必要がある場合は、ライブビューでの位置の移動を受け入れるか、追加のストレージおよび読み取りコストを伴う固定バージョンを使用します。
フォローアップ 3: レプリカの遅延により次のページが短くなってしまいました。どう処理しますか？
整合性要件に応じてプライマリまたは同一レプリカに読み取りを固定するか、「指定時間/LSN 以降」境界を保持して待機タイムアウト後に明示的なステータスを返します。欠落した行を単にリストの末尾として暗黙的に扱ってはいけません。一時的な不可視性と has_more=false を区別してください。
フォローアップ 4: 重複や欠落がないことをどのように証明しますか？
制御された並行性テストを構築します。1ページ目を読み取り、境界の前に挿入し、境界行を削除し、同一のソートキーを挿入し、行を更新した上で、一意 ID セット、順序付け、約束された可視性を検証します。障害が発生した際に正確な境界で再現できるよう、ページ境界、トークンバージョン、スナップショット識別子をログに記録します。