题干与适用场景
你维护一个文件、组织或知识图谱 API，资源可以通过别名或绑定指向其他资源。客户端请求递归展开，类似 WebDAV 的 Depth: infinity。请设计遍历算法、循环响应、深度和节点预算，并说明什么时候不该使用 508。题目适合后端、存储和平台岗位。
RFC 5842 将 508 定义为服务端在处理无限深度操作时发现循环并终止整个操作；它不是普通的重定向循环或 CPU 超时的通用替代码。假设资源图可能跨租户，边和节点都要经过权限检查。
面试官考察点
- 能否把树遍历问题识别为有环图，而不是只递归到栈溢出。
- 能否区分“发现同一资源”和“发现当前路径上的环”，选择 visited 集合与路径集合的不同职责。
- 能否为深度、节点数、响应大小和查询时间设置预算，并返回客户端可行动的诊断信息。
普通回答只说“加一个递归深度”。强回答会说明资源身份规范化、路径环与共享子图、预算耗尽和 508 的边界，并覆盖多实例缓存与权限泄漏风险。
回答前需要澄清的问题
- 资源关系是树、DAG 还是允许任意有向图？DAG 可以避免重复展开，但仍需 visited；任意图还要检测当前路径环。
- 客户端要完整展开、分页结果，还是只验证可达性？输出目标决定是否可用 208、部分结果或异步任务。
- 资源 ID 是否全局唯一？若绑定跨租户或允许别名，必须先规范化身份，否则同一节点可能被误判为不同节点。
- 预算由谁设定？服务端必须有硬上限，客户端的深度参数不能直接决定数据库和内存消耗。
30 秒回答框架
“我先把关系建模成有向图，规范化每个资源的稳定 ID。遍历时维护当前路径集合来发现真正的环，同时维护全局 visited 避免重复展开共享子图。服务端对深度、节点、边、响应字节和耗时设硬预算；发现环可返回 508，预算耗尽则返回明确的限制错误或异步任务状态。结果携带环边、截断原因和请求 ID，但不泄露无权访问的节点。测试要覆盖自环、跨别名环、共享子图、权限拒绝和恶意超深图。”
分步骤深入解答
1. 先确定 508 的边界
RFC 5842 的 508 针对递归资源操作发现无限循环。若是普通 URL 重定向，应使用重定向链保护；若只是超时或预算耗尽，不应伪装成 508。状态码表达原因，响应体再给出可诊断字段。
2. 规范化资源身份
把别名解析成租户、资源类型和不可变 ID 的三元组。路径字符串、大小写或不同 URL 不能直接作为 visited 键。解析别名本身也要有 hop 上限，避免在进入图遍历前就循环。
3. 同时维护路径集与 visited 集
path 表示当前 DFS 分支；边指向 path 中的节点才是环。visited 表示整个请求已经完成或排队的节点，用于共享子图去重。把两者混成一个集合，会把合法的菱形图误报成循环，或漏掉另一条分支上的环。
4. 设计预算与截断
至少限制最大深度、节点数、边数、响应字节和墙钟时间。预算按租户和请求级别计算，并在数据库查询中分页。预算耗尽时返回截断原因、已处理计数和继续方式；若协议要求完整结果，则创建异步遍历任务，而不是返回一个看似成功的部分树。
5. 处理权限与缓存
先做资源级授权，再把节点放入可见结果。缓存键必须包含租户、权限版本和遍历参数；不能因为一个租户曾经看到节点，就让另一个租户通过环诊断推断其存在。对高风险图，缓存解析后的邻接边，但仍在请求内重新检查授权。
6. 选择响应形式
发现环且客户端支持诊断时，返回 508，并提供环边的脱敏 ID、截断位置和请求 ID。若客户端只需要尽力结果，可返回成功的分页集合并标明 truncated；这与 508 的“整个操作失败”语义不同。不要把数据库栈溢出或反向代理自循环都统称为 508。
7. 验证攻击与失败路径
测试自环、A 指向 B 指向 A、同一节点多别名、共享子图、深度恰好达到上限、超大扇出、跨租户无权边和超时。断言每个节点最多展开一次，权限拒绝不改变可见计数，且错误响应不会泄漏隐藏资源 ID。
高质量示范回答
“我会把递归展开当成有向图问题。先把别名解析为租户加稳定资源 ID，再用当前路径集合检测真正的环，用全局 visited 去重共享子图。深度、节点、边、响应大小和耗时都设硬预算，并把预算传到分页查询。发现循环时，只有在这是递归资源操作且客户端能理解时才回 508；普通重定向循环或单纯超时使用相应的错误。响应只返回经过授权的脱敏环信息和请求 ID。缓存键要包含租户、权限版本和参数。测试覆盖自环、别名环、菱形图、跨租户边和恶意超深图，确保单请求不会无限消耗资源。”
常见错误
- 把最大深度等同于环检测 → 合法深层树也被拒绝，真正的浅层环可能仍隐藏 → 用 path 集检测环，深度只做预算。
- 只维护全局 visited → 共享子图被误报为环 → 区分当前路径与全局访问状态。
- 把所有超时都返回 508 → 客户端无法区分图循环与资源过载 → 让状态码反映真实失败原因。
- 先展开再授权 → 错误体可能泄漏隐藏节点 → 授权与结果计数都在资源级别执行。
- 缓存不含权限版本 → 旧权限下的结果继续可见 → 绑定租户、权限版本与遍历参数。
追问及应对
如果图是 DAG，为什么仍需要 path 集合？
系统数据模型声称是 DAG 不代表输入永远可信；迁移、别名或并发写入可能暂时形成环。path 集合是低成本的运行时保险，若发现环还应记录写入来源并阻止新的绑定。
客户要求“尽量返回已找到的节点”，还能返回 508 吗？
不能把部分结果伪装成 508 的完整失败。可以定义一个明确的分页或异步协议，返回已完成页、截断原因和继续游标；只有客户端要求原子完整展开时才用 508 终止操作。
如何防止恶意租户用高扇出图耗尽数据库？
为租户设置并发、节点、边、查询时间和响应字节配额，批量预取受限并采用背压。超限请求进入异步队列或被拒绝，监控每租户消耗与失败原因，不让客户端任意提高深度绕过预算。