課題とスコープ
あなたは、エイリアスやバインディングを介して他のリソースを指すことができるリソースを持つファイル、組織、またはナレッジグラフAPIを保守しています。クライアントはWebDAVのDepth: infinityに類似した再帰的展開を要求します。走査、循環の報告、深さとノードのバジェットを設計し、508が不適切となる状況を説明してください。これはバックエンド、ストレージ、プラットフォームの面接に適した内容です。
RFC 5842では、ループが検出された後に無限の深さの操作を終了するために508を定義しています。これは汎用的なリダイレクトループやCPUタイムアウト用のコードではありません。グラフはテナントを跨ぐ可能性があり、すべてのエッジとノードで認可が必要であると仮定します。
面接官がテストしていること
- 再帰走査をスタックオーバーフローを待つのではなくグラフとしてモデル化しているか。
- 重複したノードと現在のパス上のノードを区別し、グローバルの訪問済み状態とパス状態を異なる役割に使用しているか。
- 深さ、ノード、エッジ、バイト数、時間のバジェットを設定し、クライアントが対処可能な障害を返しているか。
不十分な回答では最大再帰深度を追加するだけです。優れた回答では、安定したリソースアイデンティティ、パスの循環と共有サブグラフの区別、バジェットの枯渇、508の境界、マルチテナントにおけるキャッシュの安全性までカバーします。
最初に確認すべき質問
- この関係はツリー、DAG、または任意の有向グラフですか？DAGでも重複作業を避けるために訪問済みセットが必要です。任意のグラフでは現在のパスにおける循環検出も必要です。
- クライアントは完全な展開、ページ分割された結果、または到達可能性のみを必要としていますか？出力コントラクトによって、部分的な結果や非同期ジョブが有効かどうかが決まります。
- リソースIDはグローバルに一意ですか？エイリアスやテナント間バインディングでは、訪問済みキーを構築する前に正規化されたアイデンティティが必要です。
- バジェットは誰が制御しますか？サービス側でハードリミットを課す必要があります。クライアントが指定した深さでデータベースやメモリの消費量を直接決定させることはできません。
30秒の回答
「私は関係を有向グラフとしてモデル化し、各リソースを安定したIDに正規化します。走査中は、実際の循環を検出するための現在のパスセットと、共有サブグラフの再展開を避けるためのグローバルな訪問済みセットを保持します。サービスは深さ、ノード数、エッジ数、レスポンスバイト数、実経過時間にハードリミットを適用します。検出された循環は508を生成する可能性があり、バジェット枯渇時は明示的な制限エラーまたは非同期ジョブ状態を生成します。結果にはマスクされた循環エッジ、切り捨て理由、リクエストIDが含まれ、未認可ノードが含まれることはありません。テストでは自己循環、エイリアス循環、共有サブグラフ、拒否されたエッジ、敵対的な深いグラフをカバーします。」
ステップごとのソリューション
1. 508の境界を定義する
RFC 5842では、再帰的なリソース操作が無限ループに遭遇した場合に508を使用します。通常のURLリダイレクトにはリダイレクトチェーン保護が必要です。タイムアウトやバジェット枯渇には専用のエラーが必要です。ステータスは障害のクラスを説明し、ボディは診断情報を提供します。
2. リソースアイデンティティを正規化する
エイリアスをテナント、リソースタイプ、不変IDのタプルに解決します。パス文字列、大文字小文字の違い、異なるURLを訪問済みキーとして使用しないでください。エイリアス解決にもホップ制限が必要であり、グラフ走査が始まる前にループしないようにします。
3. パス状態と訪問済み状態を分離して保持する
pathは現在のDFSブランチを表し、path内のノードへのエッジは循環です。visitedはこのリクエストですでに完了またはキューに入れられたノードを表し、ダイヤモンド型のグラフでの重複作業を排除します。1つのセットに統合してしまうと、正当な共有を循環として報告するか、別のブランチの循環を見逃すかのどちらかになります。
4. バジェットと切り捨てルールを設定する
最大深度、ノード数、エッジ数、レスポンスバイト数、実経過時間を制限します。テナントおよびリクエストごとにバジェットを適用し、データベースの読み取りをページ分割します。枯渇時には、カウント、切り捨て理由、継続メカニズムを返します。プロトコルが完全な結果を要求する場合は、誤解を招く部分ツリーを返すのではなく、非同期走査ジョブを作成します。
5. 認可とキャッシュを処理する
各リソースを表示可能な結果に追加する前に認可します。キャッシュキーにはテナント、権限バージョン、走査パラメータを含める必要があります。そうしないと、あるテナントが循環診断から別のテナントの非表示ノードを推測する可能性があります。コストの高いグラフでは、正規エッジをキャッシュしつつ、リクエストごとに認可を再チェックします。
6. レスポンスの形状を選択する
循環が検出され、クライアントが診断情報を理解できる場合は、マスクされた循環ID、切断場所、リクエストIDとともに508を返します。クライアントがベストエフォートを望む場合は、truncatedとマークされた成功のページ分割コレクションを返します。これは508の操作全体の失敗とは異なります。原因が一致しない限り、データベースのスタックオーバーフローやプロキシの自己ループを508としてラベル付けしないでください。
7. 攻撃と障害パスをテストする
自己循環、AからB経由A、1つのノードに対する複数のエイリアス、共有サブグラフ、制限ちょうどの深さ、膨大なファンアウト、拒否されたテナント間エッジ、タイムアウトをテストします。各ノードが最大1回展開されること、拒否によって可視カウントが変化しないこと、エラーによって隠蔽されたリソースIDが漏洩しないことを検証します。
高品質な回答例
「私は再帰的展開を有向グラフの問題として扱います。エイリアスをテナントと安定したリソースIDに解決し、実際の循環には現在のパス状態を、共有サブグラフの重複排除にはグローバルな訪問済み状態を使用します。深さ、ノード、エッジ、レスポンスサイズ、時間のバジェットは、ページ分割されたクエリに渡されるハードリミットです。再帰的操作が実際に循環に遭遇し、クライアントがそのコントラクトをサポートしている場合にのみ508を返します。通常のリダイレクトやタイムアウトにはそれぞれのエラーを使用します。レスポンスには認可済みでマスクされた循環データとリクエストIDのみが含まれます。キャッシュキーにはテナント、権限バージョン、パラメータを含めます。テストでは自己循環、エイリアス循環、ダイヤモンドグラフ、拒否されたエッジ、敵対的な深さをカバーします。」
よくある間違い
- 最大深度と循環検出を同一視する → 正当な深いツリーが失敗する一方で、浅い循環が残る可能性がある → 循環にはパス状態を使用し、深さはバジェットとしてのみ使用する。
- グローバルな訪問済みのみを保持する → 共有サブグラフが循環として報告される → 現在のパスをグローバル走査状態から分離する。
- あらゆるタイムアウトに対して508を返す → クライアントがグラフの循環と過負荷を区別できない → ステータスを実際の原因と一致させる。
- 認可前に展開する → エラーの詳細から隠蔽されたノードが漏洩する可能性がある → 可視走査とカウントの前に認可を行う。
- キャッシュキーから権限バージョンを省略する → 古いアクセスの結果が可視のまま残る → キャッシュエントリをテナント、権限バージョン、パラメータにバインドする。
フォローアップの質問と回答
グラフがDAGの場合、なぜ現在のパス状態を保持するのですか？
データモデルがDAGを保証していても、マイグレーション、エイリアス、または並行書き込みによって一時的に違反が発生する可能性があります。パス状態は低コストな実行時ガードです。検出された循環は、その書き込み元も特定し、新しいバインディングをブロックする必要があります。
顧客が見つかったノードだけでも欲しい場合、508を返せますか？
部分的なデータを完全な508障害として偽装しないでください。完了したページ、切り捨て理由、継続カーソルを返すページ分割または非同期のコントラクトを定義します。508はクライアントがアトミックで完全な展開を要求する場合にのみ使用します。
高ファンアウトのテナントがデータベースを枯渇させるのを防ぐにはどうすればよいですか？
テナントごとの並行性、ノード、エッジ、クエリ時間、レスポンスバイトのクォータを設定し、バッチ先行取得を制限してバックプレッシャーを適用します。バジェットを超過したリクエストをキューイングまたは拒否し、テナントごとの消費量と失敗原因を監視し、クライアントが深さを増やすことで制限を回避できないようにします。