プロンプトとコンテキスト
ページネーションされたリモート API を1要素ずつ走査するイテレータを設計してください。各ページは最大100要素で pageToken を使用します。リクエストは失敗したり重複を返したりする可能性があり、呼び出し元は後で再開するために任意の時点でカーソルを保存します。インターフェース、不変条件、バッファリング、重複排除、リカバリセマンティクス、計算量、テストについて説明してください。
イテレータの設計は公開されている面接資料にも登場します。Java API では、次の要素の存在を確認するものとして hasNext() を、要素を返すか残っていない場合に例外をスローするものとして next() を定義しています。この設問は、おなじみのインメモリパターンを再開可能でバッチ処理を行うリモートイテレータへと拡張し、状態の境界に焦点を当てています。
面接官が評価するポイント
一般的な回答は、配列のインデックスを1つ書くだけです。優れた回答は、ページトークン、ページ内インデックス、配信済み要素、および呼び出し元によって確認（ACK）されたチェックポイントを分離し、リトライによって通知なくスキップや重複が発生してはならない理由を説明します。フォローアップでは、重複ページ、ページネーション中のデータ変更、hasNext() 後のクラッシュ、並行呼び出しなどを扱います。
重要な評価シグナルは、リモートのページネーションをローカル配列のように扱うのではなく、不変条件を使用して外部の副作用を制御できるかどうかです。
明確化のための質問
- 順序付けは安定していますか？ 不変の
(createdAt, id)順序を想定します。これがない場合、正確なリカバリは保証できません。 - リカバリは at-least-once（少なくとも1回）ですか、それとも exactly-once（厳密に1回）ですか？ at-least-once の読み取りを選択し、呼び出し元が安定した ID で重複排除できるようにします。リモートサービスにはリクエストを跨ぐトランザクションがありません。
- 行の挿入や削除は発生しますか？ スナップショットまたは一貫性トークンによって結果セットが固定されていると想定します。そうでない場合は、弱い走査のみを保証します。
- 並行呼び出しは許可されますか？ デフォルトではシングルスレッドでの使用とします。並行呼び出しにはロックまたは明示的な状態エラーが必要です。
- 失敗後にイテレーションを継続できますか？ 一時的なネットワークエラーは上限内でリトライします。認証、パラメータ、スナップショット期限切れのエラーは即座に伝播させます。
30秒の回答
「私はカーソルをスナップショットバージョン、次ページトークン、ページ内インデックスに分割します。イテレータは1ページをキャッシュします。hasNext() は配信状態を進めませんが、next() は1要素を消費してインデックスを進めます。永続化されたカーソルは呼び出し元が確認した最後の配信済み要素を表すため、リカバリ時に境界が再処理される可能性があり、at-least-once となります。後続のコードは安定した ID で重複排除を行います。API には安定した順序付けとスナップショットが必要であり、そうでない場合はより弱い一貫性として説明します。ネットワーク障害には制限付きのリトライを行い、恒久的なエラーは伝播させます。」
ステップごとの解説
ステップ 1：状態とインターフェース規約の定義
| 状態 | 意味 | 永続化対象か？ |
|---|---|---|
| snapshot | 固定された結果セットまたは読み取りバージョン | はい |
| pageToken | 次ページ用のサーバーカーソル | はい（空の場合あり） |
| index | 現在のページ内で次に配信される未配信の位置 | はい |
| lastId | 最後に配信された要素の安定した ID | 推奨 |
インターフェースは hasNext()、next()、checkpoint()、close() を公開できます。hasNext() はバッファを検査したり1ページを先読みしたりできますが、要素を配信済みとしてマークしてはなりません。next() は1つの要素を返し、index を進めます。checkpoint() はシリアライズ可能なトークンを作成し、その進捗を確認済みとするタイミングは呼び出し元が決定します。
ステップ 2：不変条件の確立
0 <= index <= len(buffer)
next() returns buffer[index], then increments index
replace buffer and pageToken only after a whole page succeeds
the recovery token represents only the caller-acknowledged prefix
permanent errors are never swallowed by a retry loop次ページのリクエストが失敗した場合は、古いバッファと配信位置を保持します。新しいページの取得に成功したものの、チェックポイントを保存する前にプロセスがクラッシュした場合、リカバリによって末尾が再処理され、at-least-once となります。配信前にチェックポイントを保存すると要素がスキップされる可能性があるため、順序が重要です。
ステップ 3：ページ読み込みと制限付きリトライの実装
class ResumableIterator:
def __init__(self, client, checkpoint=None, page_size=100):
self.client = client
self.page_size = page_size
self.snapshot = checkpoint.snapshot if checkpoint else None
self.token = checkpoint.page_token if checkpoint else None
self.index = checkpoint.index if checkpoint else 0
self.buffer = []
self.done = False
def has_next(self):
self._ensure_buffer()
return self.index < len(self.buffer)
def next(self):
self._ensure_buffer()
if self.index == len(self.buffer):
raise StopIteration
item = self.buffer[self.index]
self.index += 1
return item
def checkpoint(self):
return Checkpoint(self.snapshot, self.token, self.index)_ensure_buffer() は、現在のページが使い果たされたときに、指数バックオフと最大試行回数を用いて次のページをリクエストします。サーバー側のリクエストが成功した後にタイムアウトが発生する可能性があるため、リトライでは同じスナップショット/トークンを使用する必要があり、サーバーは安定したページまたは観測可能な重複境界を返す必要があります。
ステップ 4：重複、挿入、削除の処理
ページトークンだけでは、リトライ後の重複データを防げない場合があります。API が安定した id を返す場合は、id <= lastId であるリカバリ境界でプレフィックスを破棄します。複合ソートの場合は、完全な (createdAt, id) カーソルを比較します。無制限に増加する重複排除セットを保持しないでください。サーバースナップショットと境界トークンにより、重複排除をリカバリウィンドウ内に限定します。
スナップショットがない場合、現在のページの前に新しい行が表示されたり、削除によって次のページで要素がスキップされたりする可能性があります。保証できるのは、可視結果に対するベストエフォートの走査のみであり、exactly-once や強い一貫性ではありません。面接では、保証レベルを明示的に下げるか、スナップショットバージョンを要求します。
ステップ 5：チェックポイントとリカバリセマンティクスの定義
チェックポイントには、バージョン、スナップショット、トークン、ページ内インデックス、最後の安定した ID、フィルターダイジェスト、および有効期限を含める必要があります。フィルターダイジェストは、あるクエリのカーソルが別のクエリに復元されるのを防ぎます。有効期限は、サーバーがスナップショットを回収した後に異なる結果を誤って読み取るのを防ぎます。
チェックポイントからイテレータを再構築します。呼び出し元が item を消費した直後に保存した場合、リカバリ時にその要素が繰り返される可能性があるため、後続の書き込みは安定した ID に対して冪等（idempotent）である必要があります。ビジネス要件として重複が許可されない場合、進捗とビジネス結果はトランザクションを共有するか、後続のストアが重複排除テーブルを提供する必要があります。イテレータ単体で exactly-once を実現することはできません。
ステップ 6：計算量、バックプレッシャー、クローズ処理
バッファ空間は O(page_size) であり、ローカルでの進行は要素あたり O(1) です。リモート読み取りは、リトライを除いて約 ceil(N / page_size) です。hasNext() はネットワークリクエストを発行する可能性があるため、呼び出し元はコストゼロのものとして扱うべきではありません。先読みはレイテンシを隠蔽できますが、1ページまたはバイト数の上限を設定する必要があります。
close() は未処理の処理をキャンセルし、接続を解放します。サーバースナップショットには TTL が必要です。コンシューマがプロデューサより遅い場合、API はスナップショットを無制限に延長するのではなく、レート制限をかけるかスナップショット期限切れエラーを返すべきです。並行呼び出しは拒否またはシリアライズする必要があり、そうしないと2つの next() 呼び出しが同じインデックスを観測する可能性があります。
質の高い模範解答
「私はリモートイテレータを snapshot、pageToken、buffer、index、lastId を持つ小さなステートマシンとしてモデル化します。hasNext() はバッファ要素が存在することのみを確認し、next() は index を進め、checkpoint() は呼び出し元が確認済みのプレフィックスを保存します。ページ全体が成功した後にのみバッファを置き換え、一時的なタイムアウトは上限付きでリトライし、恒久的なエラーは伝播させます。
リカバリには、安定した順序付けとスナップショットトークンが必要です。チェックポイントには、クエリダイジェスト、ページ内インデックス、最後の安定した ID、有効期限も含まれます。リカバリによって境界が繰り返される可能性があるため、at-least-once を保証し、後続の書き込みを ID に対して冪等にします。スナップショットがない場合、挿入や削除によって保証が弱まります。
バッファは O(pagesize)、各 next は O(1)、リモートページは約 ceil(N/pagesize) です。テストでは、空ページ、重複ページ、期限切れトークン、サーバー成功後のタイムアウト、チェックポイントクラッシュ、ミューテーション、繰り返しのリカバリ、並行 next、バックプレッシャー、クローズ処理をカバーします。exactly-once には共有トランザクションまたは重複排除ストアが必要です。」
よくある間違い
- 症状 → リモート API を配列として扱い、1つの整数インデックスを復元する → 失敗する理由 → ページの境界や変更により、そのインデックスが別の要素を指してしまう → 修正方法 → スナップショット、トークン、ページ内インデックス、安定した ID を永続化する。
- 症状 →
hasNext()内でトークンを進める → 失敗する理由 → 呼び出し元が消費せずに検査だけを行い、その後クラッシュした場合にデータがスキップされる → 修正方法 →next()が要素を返した後にのみ配信状態を進める。 - 症状 → タイムアウト後に次のページに進む → 失敗する理由 → ページ全体が失われるか、成功したリクエストが重複する可能性がある → 修正方法 → 同じトークンをリトライし、安定した ID で重複排除する。
- 症状 → イテレータ単体で exactly-once を実現できると主張する → 失敗する理由 → チェックポイントの永続化とビジネスの副作用は単一のアトミックなトランザクションではない → 修正方法 → at-least-once を保証し、シンク側を冪等またはトランザクショナルにする。
- 症状 → 無制限の先読みとリトライ → 失敗する理由 → 処理の遅いコンシューマがメモリを枯渇させ、障害時に永久にブロックされる → 修正方法 → バッファ、試行回数、タイムアウト、スナップショット TTL に上限を設ける。
フォローアップの質問と回答
サーバーがスナップショットトークンではなくページ番号しか提供しない場合はどうしますか？
安定した複合キーカーソルを要求するか、弱一貫性の走査しか不可能であることを明示します。ページ番号は挿入や削除によってずれるため、スキップや重複がないことを保証できません。
シンクが各要素を1回しか受け入れず、重複排除ができない場合はどうしますか？
イテレータ単体では exactly-once を保証できません。進捗、ビジネス書き込み、チェックポイントを1つのトランザクションにまとめるか、冪等なシンクを要求します。そうでない場合は、重複が発生する可能性を規約に明記します。
1つのページでタイムアウトが繰り返される場合はどうしますか？
古いバッファを保持し、トークンを進めません。リトライ上限に達した後は分類されたエラーを発生させ、呼び出し元が一時停止、スキップ、再起動のいずれかを選択できるようにします。スキップする場合はギャップを記録する必要があり、通知なく次のページに進んではなりません。